8 ms·

Perl Cannot Be Parsed: A Formal Proof

65 points by fogus 17y ago

jrockway 17y 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.)
- barrkel 17y 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.
  - chromatic 17y 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.
- andreyf 17y 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 17y 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.
    - arohner 17y ago
      >As I see it, the Perl attitude is that these constructs should be forbidden by social contract rather than by the language itself. In most other languages with "dangerous" constructs, having the dangerous construct usually allows power that isn't possible using only safe constructs. Is it the case that this is useful in some circumstances, or is it just poor design?
      - Dove 17y ago
        It is useful writing one-shot programs on the command line. Perl's idioms can allow very powerful programs to be written very quickly in very small spaces. But any code that is saved to a file and run more than once should lean a bit more toward clarity of expression. Three rules the pathological counterexample breaks: put parens around your function calls if they might otherwise be ambiguous; put =~ before a regexp if its identity might otherwise be unclear, and for heaven's sake put your line breaks in sensible places. This snippet exists to be pathological, and would quickly lose its ambiguity if written by anyone with reasonable habits of self-expression. I am glad perl allows the balance between ruthless speed for programmer-efficiency and expressive clarity for maintainer-efficiency, for sometimes I write short one-shots and sometimes I write bulletproof modules, and I write many things in between. But don't use habits suited to the former in the latter case. If you do that, perl will shoot you repeatedly until you either improve or shoot yourself. And if you survive, then you will have to deal with the folks who inherit your code.
  - tedunangst 17y 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?
    - mbrubeck 17y ago
      You mean, is real-world code likely to contain a regular expression with a # character, or a comment with a / character following code with a / character? Not all the time, but it doesn't seem terribly outlandish.
      - tedunangst 17y ago
        I think a regex with # in it is common enough, but passed to a one-arg function? And followed on the same line by another statement? No. The example takes several things that could be individually probable and packs them into a single rather unlikely line.
  - chromatic 17y 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 17y 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 17y 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.
  - nothingmuch 17y 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.
    - scott_s 17y ago
      That it's even possible is relevant - most programming languages can be parsed.
      - nothingmuch 17y ago
        There's nothing preventing symbol table modifications done by Perl modules at compile time to be reified into some sort of linkage unit, with which a parser could then statically parse the code. Similarly it's possible to prove that a certain block of code does nothing but link in such deterministic units, removing the nondeterminism of function prototypes. Most of the source code out there can be parsed statically without resorting to anything drastic. The semantics of this hypothetical Perl 5 variant do differ, but as a strict subset it will still properly most of the useful code out there.
        scott_s 17y ago
teilo 17y ago
And yet ... it is. To quote Lao Tsu: "The Tao that can be parsed is not the true Tao." Who knew? (Probably Larry)
andreyf 17y 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.
- deleted 17y ago
  [deleted]
- cabalamat 17y 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.
  - andreyf 17y 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.
    - tolmasky 17y ago
      Yes, but for a more practical example, this is defective in that it cannot be syntax highlighted correctly.
      - barrkel 17y ago
deleted 17y ago
[deleted]
nothingmuch 17y 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-problem.html http://calculist.blogspot.com/2009/02/c-typedef-parsing-prob...
- pmjordan 17y 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.
  - haberman 17y 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 http://pages.cs.wisc.edu/~driscoll/typename.html.
    - pmjordan 17y ago
      Yes, but my argument is that such an instantiation could easily be determined automatically. The declaration T::bar x; makes no sense under any circumstances if T::bar is not a type. Ergo, putting typename in front is redundant.
      - haberman 17y ago
rjurney 17y ago
Another case of science telling us what we already know? :D
- salvadors 17y 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.
Dove 17y ago
This result fills me with visceral glee, for it is very much the way of perl.
- Kaizyn 17y 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/ http://padre.perlide.org/ PPI: http://search.cpan.org/dist/PPI/ http://search.cpan.org/dist/PPI/
  - salvadors 17y 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?"
deleted 17y ago
[deleted]
cjg 17y ago
The halting theorem, which this result relies on, relies on the infinte length of the tape in the turing machine.
- gdp 17y 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.
  - cjg 17y 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.
    - gdp 17y ago
      OK, I'm not sure I agree with that in the general case either, but that still wouldn't be important to the proof. We can safely assume infinite tape and then the proof is fine. If you think we must implement the turing machine in order for the proof to be believed, then you've only weakened the proof to "The static parsing behaviour of Perl is dependent on the length of tape available", which is basically just reducing the problem to a rather unhelpful interpretation of "deterministic behaviour", approximately equivalent to the example using randomisation (except you move the random element from the program under consideration to the environment in which it is being considered). Am I missing why you think this is a significant point?
      - cjg 17y ago
        If the tape is finite then there are a finite number of states. In which case a halting oracle can exist - it detects repeated states. I can't see how we can assume an infinite tape exists - there has never been such an implementation, nor is it easy to see how this might be achieved. The weakened proof only proves that a static parse could be possible if we give the parser enough tape. The size of tape for the parser is determined by the size of tape the perl program is allowed. I'm afraid I don't understand your statements about deterministic behaviour or randomisation.

65 points by fogus 17y 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.)

barrkel 17y 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.
- chromatic 17y 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.
andreyf 17y 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 17y 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.
  - arohner 17y ago
    >As I see it, the Perl attitude is that these constructs should be forbidden by social contract rather than by the language itself. In most other languages with "dangerous" constructs, having the dangerous construct usually allows power that isn't possible using only safe constructs. Is it the case that this is useful in some circumstances, or is it just poor design?
    - Dove 17y ago
      It is useful writing one-shot programs on the command line. Perl's idioms can allow very powerful programs to be written very quickly in very small spaces. But any code that is saved to a file and run more than once should lean a bit more toward clarity of expression. Three rules the pathological counterexample breaks: put parens around your function calls if they might otherwise be ambiguous; put =~ before a regexp if its identity might otherwise be unclear, and for heaven's sake put your line breaks in sensible places. This snippet exists to be pathological, and would quickly lose its ambiguity if written by anyone with reasonable habits of self-expression. I am glad perl allows the balance between ruthless speed for programmer-efficiency and expressive clarity for maintainer-efficiency, for sometimes I write short one-shots and sometimes I write bulletproof modules, and I write many things in between. But don't use habits suited to the former in the latter case. If you do that, perl will shoot you repeatedly until you either improve or shoot yourself. And if you survive, then you will have to deal with the folks who inherit your code.
- tedunangst 17y 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?
  - mbrubeck 17y ago
    You mean, is real-world code likely to contain a regular expression with a # character, or a comment with a / character following code with a / character? Not all the time, but it doesn't seem terribly outlandish.
    - tedunangst 17y ago
      I think a regex with # in it is common enough, but passed to a one-arg function? And followed on the same line by another statement? No. The example takes several things that could be individually probable and packs them into a single rather unlikely line.
- chromatic 17y 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 17y 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 17y 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.
- nothingmuch 17y 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.
  - scott_s 17y ago
    That it's even possible is relevant - most programming languages can be parsed.
    - nothingmuch 17y ago
      There's nothing preventing symbol table modifications done by Perl modules at compile time to be reified into some sort of linkage unit, with which a parser could then statically parse the code. Similarly it's possible to prove that a certain block of code does nothing but link in such deterministic units, removing the nondeterminism of function prototypes. Most of the source code out there can be parsed statically without resorting to anything drastic. The semantics of this hypothetical Perl 5 variant do differ, but as a strict subset it will still properly most of the useful code out there.
      - scott_s 17y ago

teilo 17y ago

And yet ... it is. To quote Lao Tsu: "The Tao that can be parsed is not the true Tao." Who knew? (Probably Larry)

andreyf 17y 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.

deleted 17y ago
[deleted]
cabalamat 17y 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.
- andreyf 17y 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.
  - tolmasky 17y ago
    Yes, but for a more practical example, this is defective in that it cannot be syntax highlighted correctly.
    - barrkel 17y ago

deleted 17y ago

[deleted]

nothingmuch 17y 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-problem.html http://calculist.blogspot.com/2009/02/c-typedef-parsing-prob...

pmjordan 17y 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.
- haberman 17y 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 http://pages.cs.wisc.edu/~driscoll/typename.html.
  - pmjordan 17y ago
    Yes, but my argument is that such an instantiation could easily be determined automatically. The declaration T::bar x; makes no sense under any circumstances if T::bar is not a type. Ergo, putting typename in front is redundant.
    - haberman 17y ago

rjurney 17y ago

Another case of science telling us what we already know? :D

salvadors 17y 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.

Dove 17y ago

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

Kaizyn 17y 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/ http://padre.perlide.org/ PPI: http://search.cpan.org/dist/PPI/ http://search.cpan.org/dist/PPI/
- salvadors 17y 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?"

deleted 17y ago

[deleted]

cjg 17y ago

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

gdp 17y 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.
- cjg 17y 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.
  - gdp 17y ago
    OK, I'm not sure I agree with that in the general case either, but that still wouldn't be important to the proof. We can safely assume infinite tape and then the proof is fine. If you think we must implement the turing machine in order for the proof to be believed, then you've only weakened the proof to "The static parsing behaviour of Perl is dependent on the length of tape available", which is basically just reducing the problem to a rather unhelpful interpretation of "deterministic behaviour", approximately equivalent to the example using randomisation (except you move the random element from the program under consideration to the environment in which it is being considered). Am I missing why you think this is a significant point?
    - cjg 17y ago
      If the tape is finite then there are a finite number of states. In which case a halting oracle can exist - it detects repeated states. I can't see how we can assume an infinite tape exists - there has never been such an implementation, nor is it easy to see how this might be achieved. The weakened proof only proves that a static parse could be possible if we give the parser enough tape. The size of tape for the parser is determined by the size of tape the perl program is allowed. I'm afraid I don't understand your statements about deterministic behaviour or randomisation.