perlmeditation
Jeffrey Kegler
<p>As [id=http://perlmonks.org/?node_id=791908|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 <i>The Perl Review</i>.
[ This is [href://http://www.jeffreykegler.com/Home/perl-and-undecidability|now available online] ].
Despite this, some confusion remains on whether, in general, Perl might be
"dynamically" parseable.
<p>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.
<readmore>
(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.)
</readmore>
<p>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.
<p>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.
<readmore>
<p><b>Fallacious Counter-Argument:</b> 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.
<p>Consider the following code snippet:
<c>
sub runtime_nullary {
my $function = shift;
return 0
if not defined( my $prototype = prototype $function );
return $prototype eq q{};
} ## end sub runtime_nullary
print 'nullary dunno: ';
say runtime_nullary('dunno') ? 'yes' : 'no';
print 'result is ';
say dunno +4;
</c>
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.
<ol>
<li>Something like the above snippet can placed to execute first (or early) in the run phase of the arbitrary code.
<li>We can place this snippet in the arbitrary code so that we always reach the snippet and execute it.
<li>Once <tt>runtime_nullary</tt> runs, we know whether the function named in its argument is nullary or not.
<li>We can run <tt>runtime_nullary</tt> on any function we like, and on as many functions as necessary.
</ol>
<p>So therefore, <b>Fallacious Conclusion:</b> We can determine, for arbitrary Perl code, whether any Perl function has a nullary prototype or not.
<p>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.
<p>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.
<p>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.
<p><b>Update, 11 Oct 2009:</b> 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 <i>The Perl Review</i>.
<p><b>Update, 12 Oct 2009:</b> Based on feedback from [blokhead] and [ikegami], revised the Fallacious Counter-Proof to emphasize that the problem lies in determining nullarity for <b>arbitrary</b> code.
</readmore>