News for hackers. Stuff that matters.
Re:Perl Cannot Be Parsed: A Formal Proof by jrockway on Thursday August 13, 2009 @01:08PM (#761216)
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.)

Re:Perl Cannot Be Parsed: A Formal Proof by neilk on Thursday August 13, 2009 @02:14PM (#761361)
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.

Re:Perl Cannot Be Parsed: A Formal Proof by mst on Thursday August 13, 2009 @04:12PM (#761593)
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.

Re:Perl Cannot Be Parsed: A Formal Proof by draegtun on Thursday August 13, 2009 @03:36PM (#761526)

   "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 ;-)

Re:Perl Cannot Be Parsed: A Formal Proof by nothingmuch on Thursday August 13, 2009 @02:43PM (#761432)
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.

Re:Perl Cannot Be Parsed: A Formal Proof by scott_s on Thursday August 13, 2009 @03:21PM (#761498)
That it's even possible is relevant - most programming languages can be parsed.
Re:Perl Cannot Be Parsed: A Formal Proof by nothingmuch on Thursday August 13, 2009 @08:22PM (#762067)
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.

Re:Perl Cannot Be Parsed: A Formal Proof by scott_s on Thursday August 13, 2009 @10:09PM (#762207)
That's not the point. It is interesting, from a programming language theory perspective, that Perl 5 can not be parsed statically. The person who wrote the proof sketch cares very much about the practical implications of that theoretical result because he's writing Perl parsing libraries.

Also, what you're describing is no longer static parsing.

Re:Perl Cannot Be Parsed: A Formal Proof by andreyf on Thursday August 13, 2009 @02:00PM (#761319)
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)
Re:Perl Cannot Be Parsed: A Formal Proof by nkurz on Thursday August 13, 2009 @02:41PM (#761424)
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.

Re:Perl Cannot Be Parsed: A Formal Proof by arohner on Thursday August 13, 2009 @03:17PM (#761494)
>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?

Re:Perl Cannot Be Parsed: A Formal Proof by Dove on Thursday August 13, 2009 @11:36PM (#762301)
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.

Re:Perl Cannot Be Parsed: A Formal Proof by tedunangst on Thursday August 13, 2009 @02:42PM (#761428)
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?
Re:Perl Cannot Be Parsed: A Formal Proof by mbrubeck on Thursday August 13, 2009 @03:17PM (#761493)
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.
Re:Perl Cannot Be Parsed: A Formal Proof by tedunangst on Thursday August 13, 2009 @04:18PM (#761612)
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.
Re:Perl Cannot Be Parsed: A Formal Proof by chromatic on Friday August 14, 2009 @05:14PM (#763861)
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.
Re:Perl Cannot Be Parsed: A Formal Proof by mgreenbe on Thursday August 13, 2009 @02:04PM (#761330)
It is an object lesson in concrete syntax design. This result probably won't be of interest to Perl hackers for precisely that reason.
Re:Perl Cannot Be Parsed: A Formal Proof by barrkel on Thursday August 13, 2009 @01:29PM (#761253)
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.

Re:Perl Cannot Be Parsed: A Formal Proof by chromatic on Thursday August 13, 2009 @05:10PM (#761698)
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.