|Perl: the Markov chain saw|
Perl is not Dynamically Parseableby Jeffrey Kegler (Hermit)
|on Oct 12, 2009 at 04:11 UTC||Need Help??|
As already suggested in perlmonks, the proof that Perl parsing is not, in general, decidable applies equally to all parsing by the Perl interpreter or by Perl scripts. This point had already been made in my series on "Perl and Undecidability" in The Perl Review. [ This is now available online ]. Despite this, some confusion remains on whether, in general, Perl might be "dynamically" parseable.
The Perl Parsing Undecidability proof shows that a Turing machine cannot, in general, parse Perl. Whether running a script, or parsing, the Perl interpreter, and any program implementing the Perl language is, as far as Perl parsing goes, a Turing machine.
(A Turing machine is the best and most standard theoretical model for all general-purpose languages and machines. Technically, Perl features like access to the system clock are not in the Turing machine model, but it is simpler, and entirely safe, to ignore these non-Turing Perl features. The system clock isn't going to help you parse Perl.)
This means that how you define "static" and "dynamic" Perl parsing does not matter. All Perl processing is at best equivalent to a Turing machine. And therefore none of it suffices to parse Perl in general.
The confusion does have a reasonable basis in some common sense observations. In practice, Perl almost always does parse itself just fine, despite any difficulties people may have writing tools to analyze Perl scripts. And there is a very convincing (though fallacious) counter-argument. In what follows I deal with one.
Fallacious Counter-Argument: First, let's reduce the problem of Perl parsing to the issue of determining whether a function's prototype is nullary or not. If it's proved that determining nullarity is, in general, decidable, it reduces my original proof to rubble. It probably also generalizes to a full counter-proof.
Consider the following code snippet:
First take some Perl code. It must be free of fatal errors, but otherwise can be "arbitrary". ("Arbitrary" in math-speak means "anything you like".) Now let's make 4 observations about it.
So therefore, Fallacious Conclusion: We can determine, for arbitrary Perl code, whether any Perl function has a nullary prototype or not.
First, let me concede that the Fallacious Conclusion does follow from Observations 1-4. Let me also concede that Observations 1, 3 and 4 are correct. And let me also concede that if Fallacious Conclusion is correct, my Perl Parsing Undecidability Proof (and probably any other) is kaput.
But what about Observation 2? It looks solid, but it hides a major fallacy. We reach the run phase only if we get out of the compile phase. True, this is something we usually take for granted, but if we assume the compile phase eventually ends (or that we can tell whether it will or not), we assume there is no Halting Problem in the compile phase. And if we assume that there is no Halting Problem in Perl's compile phase, we assume that the compile phase does not have Turing machine power.
Perl's compile phase does have Turing machine power, and therefore is subject to the Halting Problem. This is not just a fact, but it is exactly that property of Perl which causes Perl parsing to not, in general, be decidable. The ghost of the Halting Problem must always haunt those who seek the power of the One Universal Machine to Bind Them All.
Update, 11 Oct 2009: I simplified the code snippet a bit to focus on my point in this post. The original is on page 25 of the Fall 2008 issue of The Perl Review.