Perl Cannot Be Parsed: A Formal Proof

http://www.perlmonks.org/?node_id=663393

by fogus • 17 years ago

65 52 17 years ago

jrockway• 17 years ago

The value of this is extremely limited. The Perl that most people write can be parsed just fine.

(Just like many programs halt, even though it's proved that this is not the case for any input to any turing machine.)

barrkel3• 17 years ago

What about modules that people use that abuse this power? All it takes is third parties to mess up the ability to analyse the syntax...

Though I agree it's not a problem for actually trying to execute a Perl script.

chromatic2• 17 years ago

Third parties have the ability to "mess up" code only in so far as code written to those APIs use syntax that Perl 5 cannot resolve statically. In other words, Perl 5 encapsulates those messes unless you choose to spread them.

andreyf3• 17 years ago

The Perl that most people write can be parsed just fine.

Not true. The example he shows to not be statically parseable is:

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

(because you need to know the value of `whatever' to parse it)

nkurz• 17 years ago

I'm not sure I agree with you. You do have a point though:

1) Any programmer who writes this line of code as anything other than a lesson in obfuscation should be taken out and shot.

2) Speaking as a Perl programmer who has maintained others' code, _many_ Perl programmers should be taken out and shot.

How about: "Except for pathological constructs that should probably be avoided anyway, the Perl that most people write can be parsed just fine." As I see it, the Perl attitude is that these constructs should be forbidden by social contract rather than by the language itself. Sort of like the farmer who refuses to put a lock on his fuel pumps in case someone really needs to fill a tank in an emergency.

tedunangst2• 17 years ago

Is 'whatever / 25 ; # / ; die "this dies!";' an example of the perl most people write, or just an example of what perl detractors claim most people write?

chromatic2• 17 years ago

You don't need to know its value, only its syntactic type -- in almost all but the most pathological cases, a clever static parser can identify that.

mgreenbe• 17 years ago

It is an object lesson in concrete syntax design. This result probably won't be of interest to Perl hackers for precisely that reason.

neilk• 17 years ago

I don't think so. It is an example of how Perl's interpreter changes what a program means, based on information gathered at runtime. The halting problem stuff is just a formalization of the difficulty, to show that in some cases it's actually impossible to parse.

Try this one:

   #!/usr/bin/perl 

   BEGIN {
     my $x = int(rand(2));
     print "randomly picked $x\n";
     if ($x) {
       eval ' 
         sub foo($) {
           print "executed foo()\n";
         }
       ';
     }
   }
   foo / 25; #/ ; die "DIED\n";
   print "DID NOT DIE\n";

This is technically parseable but only by thinking of it as a program that branches at every call of 'foo'. And think about what would happen if many such cases interacted.

"Modern" Perl programmers use a lot of syntax-perverting trickery, so this isn't as unlikely as it may appear.

nothingmuch3• 17 years ago

can you please point to a real example of code like this?

just because a pathological case is possible, doesn't mean that it's actually common, or even existent.

draegtun2• 17 years ago

   "Modern" Perl programmers use a lot of syntax-perverting trickery, 
    so this isn't as unlikely as it may appear.

"Modern" Perl programmer do the complete opposite!

This code completely ignores all the best practices that "Modern" Perl programmers adhere to so its is very unlikely to appear anywhere but in places like Perlmonks, Reddit & Hacker News ;-)

mst3• 17 years ago

Actually, we tend to use a limited set of things that's designed to parse sanely.

people using a 'sub ()' prototype for anything except a CONSTANT_NAME will be taken behind the bikeshed, shot, eviscerated, cremated, resurrected, shot again, and then told it's now their responsibility to project manage the repainting as penance.

teilo• 17 years ago

And yet ... it is.

To quote Lao Tsu:

"The Tao that can be parsed is not the true Tao."

Who knew? (Probably Larry)

andreyf3• 17 years ago

Keep in mind that the term "parse" here is being used in its strict sense to mean static parsing -- taking a piece of code and determining its structure without executing it. In that strict sense the Perl program does not parse Perl. The Perl program executes Perl code, but does not determine its structure.

A less alarmist title would have been "Perl cannot be parsed unambiguously without runtime information". A less technical summary:

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

Could be parsed both as (using parentheses to show arguments):

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

Or:

    whatever / 25; # the rest is a comment

This depends on whether `whatever' is a function of one argument or not, which you don't know until runtime.

cabalamat2• 17 years ago

I once attempted to learn Perl, several years ago. I always felt I was walking on quicksand because I was never sure how a program should be parsed. It's nice to confirm that it wasn't just my unfamiliarity with the system; the actual design of the lanugage is deeply, deeply defective.

andreyf3• 17 years ago

Meh, "defective" is a strong word. It really depends on what you want out of your language - if you want static code analysis or a macro system, then yes, it's defective. If you're looking to write a language that people use to write scripts here and there, then it's just a question of taste.

andrewljohnson• 17 years ago

I learned Perl in a single week to do a dirty job that needed doing in the 90s. I'd use Python for the task today.

draegtun2• 17 years ago

   ... lanugage is deeply, deeply defective

With great power comes great responsibility ;-)

If i switch on warnings it will provide... well warnings on this example! If I run Perl::Critic over it then it spews lots of things that I should be concerned about!

You're unfortunately over sensationalising what is otherwise a very good Perlmonks article.

mst3• 17 years ago

perl tries to be more human friendly; the trick is to write the code in the way that seems to best express your intent to a human reading it, and assume that the compiler will do the right thing.

Later you'll be able to work out the rules that it uses to resolve things and take advantage of them, but perl is designed for people who -don't- want to be thinking about what the compiler's doing while writing code.

Alternatively, you can simply -not use- the syntax sugar and thereby avoid needing to worry about it for your own code.

nothingmuch3• 17 years ago

Interestingly, C suffers from a somewhat similar ambiguity, where not the results of runtime-at-compile-time but rather type definitions affect the parsing.

http://calculist.blogspot.com/2009/02/c-typedef-parsing-prob...

pmjordan2• 17 years ago

In C++, the problem becomes so bad that the language designers capitulated in some instances, and you have to tell the compiler if something is a type or an identifier. Haven't tested this example, but you get the point:

  struct test
  {
    typedef int bar;
  };

  template <class T> struct foo
  {
    typename T::bar x; // if you leave off 'typename', it won't compile
  };
  
  foo<test> y;
  y.x = 5;

What I don't quite understand is why, if it won't compile in the first place (i.e. there is no ambiguity, just correct or incorrect), you need to specify it in the first place. I suspect it somehow makes compiler implementation easier.

haberman3• 17 years ago

It's not about making compiler implementations easier -- it's about protecting template authors against having someone write:

    class MyBadClass {
      static int bar;
    };
    foo<MyBadClass> y;

By writing "typename", the template author can indicate that "T::bar" the template author can indicate that "bar" is expected to be a type, not a variable. This is explained in more detail here: http://pages.cs.wisc.edu/~driscoll/typename.html.

haberman3• 17 years ago

In C++ that problem gets worse. To parse:

    Template<params>::InnerDef * y;

...you have to know whether InnerDef is a type or a number. If it's a type, this is a declaration of a pointer y. If it's a number, it's a multiplication which is then discarded.

The problem is that to know whether InnerDef is a type or a number you have to instantiate Template<params>. But C++ templates are Turing-complete: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.3...), so performing this instantiation would be undecidable except that C++ defines a recursion depth limit.

There's a nice writeup of this problem in the C++ FQA: http://yosefk.com/c++fqa/web-vs-c++.html.

rjurney• 17 years ago

Another case of science telling us what we already know?

salvadors2• 17 years ago

Another case of science telling us that what we always strongly suspected but could never be 100% sure about, was indeed correct.

This is (in the general case) more useful than people tend to realise.

Dove2• 17 years ago

This result fills me with visceral glee, for it is very much the way of perl.

Kaizyn• 17 years ago

This is old and incorrect. Adam Kennedy released the PPI module and has been working steadily on the Padre editor which is capable of refactoring Perl code as well as parsing it.

Padre: http://padre.perlide.org/ PPI: http://search.cpan.org/dist/PPI/

salvadors2• 17 years ago

No it's not. PPI's goal is only to do a "good enough" job. It explicitly states in the documentation that it is not capable of actually parsing Perl code and the discussion he gives in that documentation was what led to this formal proof being developed. Furthermore, in the PerlMonks discussion linked, Adam also commented: "This totally makes my day. Would you mind if I converted this to POD and included it the documentation for PPI?"

cjg5• 17 years ago

The halting theorem, which this result relies on, relies on the infinte length of the tape in the turing machine.

gdp4• 17 years ago

And? That doesn't change the result. Whether you can implement the turing machine or not is irrelevant, it's simply that you are able to frame the problem as "does this halt?", which is unanswerable in the general case.

"Running out of storage" doesn't really count as "termination", especially because we can't reasonably answer the question "will this run out of storage?" in the general case either.

cjg5• 17 years ago

If you restrict yourself to a limited amount of storage then it is possible to decide if a given program halts.

There are not many pieces of code that run with an infinite amount of storage.

Perl Cannot Be Parsed: A Formal Proof

Related Stories