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

It's never too late.

Your workaround assumes that somehow is_nullary can determine, if perhaps only at run time, whether whatever is nullary or not. But an arbitrary function's prototype is not in general decidable, even at run time.

Here's some hand-waving, which I hope can render the basic idea plausible: Suppose you can determine whether a piece of arbitrary code establishes (or not) a nullary prototype for whatever. Since the code is arbitary, it can contain lots of stuff, so you've said you can do more or less a complete analysis of what Perl code does. That of course includes whether it ever finishes or not. So you've also solved the Halting Problem. But that you cannot do.

The two issues -- Halting Problem and undecidability, are intimately connected. Perl is unusual in allowing Turing-equivalent computing before the parse is determined, and in allowing this pre-parse computing to do things which will affect the parse. That's why Perl parsing is undecidable, while the parses for most languages are decidable.

I've just finished the second of a series of articles in The Perl Review on undecidability in the Perl context. In TPR I lay the proof out more slowly than I did here in perlmonks. My discussion in TPR is aimed at Perl programmers who may not have had any interest in Theory for its own sake. Eventually, I'll put that series of articles on the Internet.

This is a genuinely difficult area. Even those academics who've mastered the notation and memorized the results, have a very hard time with the ideas. This is why IMHO these topics so often are poorly explained.

Comment on Re^2: Perl Cannot Be Parsed: A Formal Proof Select or Download Code

Replies are listed 'Best First'.
Re^3: Perl Cannot Be Parsed: A Formal Proof by Anonymous Monk on Jun 12, 2009 at 04:46 UTC
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.	[reply]
Re^4: Perl Cannot Be Parsed: A Formal Proof by Jeffrey Kegler (Hermit) on Jun 23, 2009 at 16:23 UTC
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.	[reply]
Re^4: Perl Cannot Be Parsed: A Formal Proof by Anonymous Monk on Aug 13, 2009 at 20:25 UTC
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 } ... "` [download] 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.	[reply] [d/l]


Syntactic Confectionery Delight
	PerlMonks

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

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