This is possibly one of the most awesome emails I have ever received.
-------------------------------------------------------------------
I saw the suggestion that parsing Perl 5 could be reduced to the
Halting Problem on your PPI man page, and have carried it out
formally: http://perlmonks.org/?node_id=663393
I became interested because I've just released an alpha on CPAN of an
Earley's parser with LR(0) precomputation (http://search.cpan.org/
~jkegl/Parse-Marpa-0.202000/ ), and one potential application is as
an approach to Perl 5 static parsing. I wondered whether 100% is
achievable, and so determined to follow up on your hint.
Perl::Marpa is only in alpha at this point, but I'd be interested in
your thoughts about it, with relation to Perl 5 static parsing, and
in general. I think Parse::Marpa could have potential as a "utility
parser".
best, jeffrey kegler
-------------------------------------------------------------------
Not being a mathematician, although I was pretty confident the Halting Problem applied to Perl 5, there's no way I'd be able to sit down and write an actual proof.
I also don't even know what a "Lemma" is (although I can guess from the context) which makes having a named one even more fun.
My hope for Perl 6 is that is WILL be statically parsable (I'm still not entirely sure if it is or not, but I worry that it won't be).
Once you can statically parse software, it allows code to have an understanding of it's own structure, and greatly enhances the diversity of automated tools that can be written, and thus improves the language one of the most practical dimension, "How easy is this to write".
