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 generalpurpose 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 nonTuring 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) counterargument. In what follows I deal with one.
Fallacious CounterArgument: 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 counterproof.
Consider the following code snippet:
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;
First take some Perl code. It must be free of fatal errors, but otherwise can be "arbitrary". ("Arbitrary" in mathspeak means "anything you like".) Now let's make 4 observations about it.
 Something like the above snippet can placed to execute first (or early) in the run phase of the arbitrary code.
 We can place this snippet in the arbitrary code so that we always reach the snippet and execute it.
 Once runtime_nullary runs, we know whether the function named in its argument is nullary or not.
 We can run runtime_nullary on any function we like, and on as many functions as necessary.
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 14.
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.
Update, 12 Oct 2009: Based on feedback from blokhead and ikegami, revised the Fallacious CounterProof to emphasize that the problem lies in determining nullarity for arbitrary code.
Re: Perl is not Dynamically Parseable
by chromatic (Archbishop) on Oct 12, 2009 at 04:26 UTC

Accurate and true, however if I catch you writing code like that for any purpose other than this proof, I will take your keyboard away.
Practically speaking, this is not a problem in Perl programs reasonably written with maintainability in mind.
 [reply] 

The code examples for the TPR undecidability series were intended as thought problems. Typically they were meant to fail in thoughtprovoking ways, ways that were usually unexpected. Truly not the kind of code you'd like to maintain.
In one of my TPR drafts, I said that, if you read my code without understanding its objective, you'd think the proof was that I have no idea how to write code. I think that remark wound up on the cutting room floor.
 [reply] 

 [reply] 
Re: Perl is not Dynamically Parseable
by blokhead (Monsignor) on Oct 12, 2009 at 15:41 UTC

Perhaps a clearer distinction is the following:
It is easy to determine whether a defined sub has a nullary prototype.
Indeed, your runtime_nullary sub determines just that. And "defined" here is important, as we will see below. On the other hand,
It is undecidable to determine whether an arbitrary computation (say, the BEGIN phase of a perl script) results in defining a sub with nullary prototype.
This is demonstrated by your previous undecidability posts. I agree with ikegami in terms of how things are worded. Your "fallacious conclusion" is not fallacious.
Its wording makes it sound like the hard part is: given a code ref, determine its prototype.
But you can always determine the prototype of a Perl sub. What you can't do is determine whether an arbitrary piece of code will result in defining a nullary prototyped sub. Update: it is this "given arbitrary code" part that I think is not formally exposited in your post.
The thing about "reaching" the determining code is a red herring. It's just part of one (bad?) method of trying to determine the outcome of an arbitrary computation  by running the computation and then (when it is done) looking for its result. Of course we know that can't work, but it's not saying much more than "you can't wait for a computation to finish, when you're not sure whether the computation will finish".
You could say that this is directly analogous to the halting problem itself. It is easy to determine whether a Turing Machine that has already halted has halted with 0 or 1 on its output tape  just look at the tape! However, it is undecidable to determine, given a Turing machine, whether it will eventually halt with 0 or 1.
In our context, the sub's prototype is just a place to store the outcome of an arbitrary Turing Machine computation. The problem of reading or interpreting the computation's outcome (determining the sub's prototype) is not undecidable, it's the problem of determining what that outcome of an arbitrary computation will be.
I hope this helps making the distinction clearer & more precise.
 [reply] 

Thanks for the feedback. In response, I've revised the original post in a way that I hope improves it.
An alternative approach would be to simply state the result and that it is a direct and almost trivial consequence of Rice's Theorem. This result is indeed so trivial mathematically that it is unpublishable, but in a math journal, that's how it would be presented. The article would be very short.
Because of the significance of these results, I've labored to present them to readers who are Perlliterate, but not fluent in Theory of Computation. The risk is always that a translation from mathspeak will seem sloppy to those who understand it and unconvincing to those who don't.
 [reply] 

Concerning your update:
So therefore, Fallacious Conclusion: We can determine, for arbitrary Perl code, whether any Perl function has a nullary prototype or not.
It's not clear what that means. Are you talking about a function declaration in the source, a function instance produced by a given parser instance, or the function instances produced by every parser instance.
First, let me concede that the Fallacious Conclusion does follow from Observations 14.
You can't concede the validity of an argument. You are making an assertion.
And your assertion is false. The conclusion doesn't follow from the premises (anymore?).
Perl's compile phase does have Turing machine power,
You can't use that premise. That's the conclusion of the argument you're trying to verify.
 [reply] 
Re: Perl is not Dynamically Parseable
by ikegami (Pope) on Oct 12, 2009 at 21:37 UTC

The approach I would have taken:
The hypothesis is
Perl cannot be parsed
which is to say
There exists a program for which two instance of the Perl parser produce different output
which is true if
There exists a function call in a program for which two instance of the Perl parser have different prototypes for the named function.
This is actually very simple to prove by example.
However, you tried to prove this by counterproof. That means you need to disprove the counterhypothesis
For every function call in every program, every instance of the Perl parser will have the same prototype for the named function.
No problem there either. This can be disprove with the same example.
 [reply] 

I'd very much look forward to seeing a full writeup of this proof. I suspect that many will prefer it to any of mine. In fact, one of the people who prefer your proof might be me.
It is very common in math to publish new proofs of old results. In any field, the first statement of something is seldom either the clearest or the most elegant.
 [reply] 

BEGIN {
*call_to_inspect = ( rand() < 0.5
? sub ($) {}
: sub (@) {}
);
}
You can detect some changes in the compiletime state of a prototype by its effect on context.
BEGIN {
*call_to_query = ( rand() < 0.5
? sub ($) {}
: sub (@) {}
);
}
sub inspector { print wantarray ? 1 : 0, "\n" }
call_to_inspect(inspector());
Let's observe:
>perl a.pl
1
>perl a.pl
1
>perl a.pl
0
>perl a.pl
1
Therefore, there exists a function call in a program for which two instance of the Perl parser have different prototypes for the named function.
Therefore, there exists a program for which two instance of the Perl parser produce different output.
Or for short, Perl cannot be parsed.
 [reply] [d/l] [select] 



However, you tried to prove this by counterproof.
Actually, no. The whole presentation of the counterargument only attempts to prove that that line of counterargument (which has been put forward in a few variations) fails. It doesn't attempt to prove Perl Unparseability. If that was your expectation I can certainly see why you saw it as falling short. My presentation of the counterargument is like an exposition of a variation on the Sicilian Defense intending to show a chess maven why he should never play it.
Arguably the post might have been stronger without it. I've dumped it into a "readmore".
The proof is given in three forms in the TPR articles. The strongest form is the one that uses Rice's Theorem. The other two may be considered explanations intended to help those trying to understand why Perl Parsing Undecidability is provable.
 [reply] 

 [reply] 

 [reply] 





Re: Perl is not Dynamically Parseable
by ikegami (Pope) on Oct 12, 2009 at 05:15 UTC

Fallacious Conclusion: We can in general determine whether any Perl function has a nullary prototype or not.
It's not fallacious. There's no guarantee that the answer won't change later or that it'll be the same at the same point of execution in a different interpreter, but we can indeed determine whether any Perl function has a nullary prototype or not.
 [reply] 

It's fallacious because you need to know you will reach the code which can make the determination. And to know, in general, that you will reach that nullaritydetermining code you've got to know the answer to the Halting Problem in every form it can take. Being able to determine the nullarity of a Perl function, given arbitrary Perl code, amounts to being able to fully predict the operation of a Turing machine.
 [reply] 

 [reply] 





