Re^3: Perl Cannot Be Parsed: A Formal Proof

[Anonymous Monk]

Your workaround assumes that somehow is_nullary can determine, if perhaps only at run time, whether whatever is nullary or not.

But this is an entirely different problem. No one claims that calling halt() doesn't make any sense just because it is statically undecidable. This is true for arbitrary programs ( functions ) in a Turing complete language and no one claims that function composition is useless because we can never know whether all of them terminate. The implicit assumption of your article is that the parser derives one and only one parse tree ( solves all ambiguities ) from an expression and only this assumption has to be given up. The assertion becomes much weaker then:

A Perl parser can't resolve all ambiguities of a Perl program by context sensitive analysis

and the solution to this to derive multiple parse trees for an expression and wrap them into a common node that can represent a conditional expression for example.

[Jeffrey Kegler]

What you say is true -- in fact I am writing a parser which does ambiguous parsing, and it was that which motivated the investigation which resulted in this proof.

However the claim is that Perl parsing is undecidable -- and listing the possible decisions does not make it decidable. Coming up with all the multiple parse trees may produce an answer adequate for most, or in particular cases, all practical purposes. But it does not decide the parse.

Similarly, we deal with the halting problem adequately for practical purposes with every program we write. However, the halting problems remains undecidable, and that remains a useful thing to know as we in practice write 1000's upon 1000's of programs which must and do halt.

[Anonymous Monk]

I agree, completely. However, the question of whether one can do what you claim remains open. Put another way, if you have an ambiguous program e_0, can you transform it into the equivalent program P

P = "
if (C_0) { e_0 }
elsif (C_1) { e_1 }
elsif (C_2) { e_2 }
...
"

where C_i are conditionals determining which way to parse e_0, and e_i are syntactic permutations of e_0 that force Perl to parse in the particular way dictated by C_i?

The broader conjecture is: Given an arbitrary e_0, there exists program transformation F(e_0) = P such that P is (a) finite, (b) parsed exactly one way by Perl, and (c) operationally-equivalent to e_0 -- e_0 and P produce equal results for equal inputs in all contexts.

This would be a useful result for compiler hackers. It says that you can take a Perl program and statically transform it into a syntax that is guaranteed to remain unchanged during execution. This property allows you to design more aggressive program transformations and optimizations, unencumbered by the confusion of "what might the interpreter do to the program structure?"

Perl is cool and all, but the fact that it isn't supported by a uniform conceptual model (small kernel of concepts from which many broader concepts are composed) will keep preventing fast compilers/interpreters and good tool support, in general.