Theorem: Parsing Perl 5 is Undecidable

We first establish Adam Kennedy's conjecture as a lemma. The proof will follow immediately from that and the Halting Theorem.

Kennedy's Lemma: If you can parse Perl, you can solve the Halting Problem.

To prove Kennedy's Lemma, we assume that we can parse Perl. In particular this means we can take the following devilish snippet of code, concocted by Randal Schwartz, and determine the correct parse for it:

whatever  / 25 ; # / ; die "this dies!";

Schwartz's Snippet can parse two different ways: if whatever is nullary (that is, takes no arguments), the first statement is a division in void context, and the rest of the line is a comment. If whatever takes an argument, Schwartz's Snippet parses as a call to the whatever function with the result of a match operator, then a call to the die() function.

This means that, in order to statically parse Perl, it must be possible to determine from a string of Perl 5 code whether it establishes a nullary prototype for the whatever subroutine. Since we've assumed we can parse Perl, we can assume that a subroutine to do this exists. Call the subroutine which takes as its only argument a Perl 5 code string, and returns true if and only if that code string establishes a nullary prototype for the whatever subroutine, is_whatever_nullary().

To drag the Halting Theorem into this, we'll need to simulate a Turing machine or its equivalent. It's very evident that Perl 5 is Turing-complete. No referee at a math journal would require something that obvious and that tedious to be proved. The term used in these cases is "left as an exercise to the reader". But in this case, there is an Acme::Turing, so the exercise apparently has already been done.

We wrap the Turing machine simulator of our choice in a routine that takes two strings as its arguments, and treats the first string as the representation of a Turing machine, and the second as its input. Call this run_turing_machine.

Now we write a routine, call it halts(), which takes the description of a Turing machine and its input. We have it create (but not run) a Perl 5 code string to run the Turing machine simulator on the machine description and input from our two arguments, and then establish a nullary prototype for whatever. We next ask is_whatever_nullary() whether the nullary prototype for whatever was established. Our halts() routine might look like this:

sub halts {
    my $machine = shift;
    my $input = shift;
    my $code_string_to_analyze = qq{
          BEGIN {
               run_turing_machine("\Q$machine\E", "\Q$input\E");
               sub whatever() {};
          }
     };
    is_whatever_nullary($code_string_to_analyze);
}
[download]

$code_string_to_analyze is passed as an argument to is_whatever_nullary(), which claims to be able to figure out, somehow, if the nullary whatever prototype is established. is_whatever_nullary() does not necessarily run $code_string_to_analyze. In fact if the Turing machine simulation does not halt, is_whatever_nullary() can't run $code_string_to_analyze, not and live up to the assumption that it will tell us whether the prototype is established or not. To do this, is_whatever_nullary() must somehow figure out when $machine does not halt with $input. Since the next thing in $code_string_to_analyze is the nullary prototype, if $machine halts with $input, is_whatever_nullary() will return true. If $machine does not halt with $input, the statement establishing the nullary whatever prototype will never be reached, and is_whatever_nullary() must return false.

So, given the assumption that we can parse Perl, halts() returns true if and only if the Turing machine $machine halts with input $input. In other words, halts() solves the Halting Problem. Kennedy's Lemma was that, if you can parse Perl, you can solve the Halting Problem. So this proves Kennedy's Lemma.

It's well known that the Halting Problem cannot be solved. Kennedy's Lemma establishes that if we can parse Perl 5, we can solve the Halting Problem. Therefore we cannot parse Perl 5.

QED