News for hackers. Stuff that matters.
Re:Ancient languages: Perl (2004) by dragonwriter on Monday August 05, 2013 @04:06PM (#6162586)
> As for parsing, it is impossible to parse Perl, as it is Turing-complete and nobody has solved the halting problem (yet).

Most Turing-complete languages can be parsed (even Ruby, which is, among currently-popular languages that aren't Perl, noted for being parsing-unfriendly.) Perl can't be parsed not just because it is Turing-complete, but because (unlike most other languages), parsing Perl requires simulating its execution and it is Turing-complete, which combined require solving the halting problem to parse perl.

Insofar as it is valuable to be able to parse code written in a programming language, perl's unique barrier to parsing is a drawback.

Re:Ancient languages: Perl (2004) by peterwwillis on Monday August 05, 2013 @05:05PM (#6163037)
Really the halting problem comes down to "Can we tell if a function will end or not?" A simple while ( time ) { 1 } will stop us from finding that out very nicely, so the fact that it's not parseable is actually a separate issue. (A much simpler halting problem using parsing is do 1;)

We could remove the ability for Perl to compile, interpret and execute code at run-time, which would mainly involve removing eval, use, require, import, do, etc. But would that be better or worse than not being able to "parse" Perl code?

(As an aside: Ruby is also subject to the halting problem, and thus cannot be parsed; you just can't get away from the pesky thing!)

Re:Ancient languages: Perl (2004) by dragonwriter on Monday August 05, 2013 @06:37PM (#6163639)
> Really the halting problem comes down to "Can we tell if a function will end or not?"

Except that "program" is usually used instead of function, that's the usual statement of the halting problem, not something it "comes down to".

> A simple while ( time ) { 1 } will stop us from finding that out very nicely, so the fact that it's not parseable is actually a separate issue.

The problem with parsing Perl is that Perl cannot be parsed independently of simulating its execution. That fact, combined with the halting problem, means that it cannot be parsed (or, more accurately, that any program that correctly parses Perl cannot be guaranteed to terminate on all valid inputs.)

> As an aside: Ruby is also subject to the halting problem, and thus cannot be parsed

All Turing-complete programming languages are subject to the halting problem. But that's not a problem for parsing most of them (including Ruby) the way it is for Perl because parsing most languages does not require simulating the execution of the code being parsed.

Ruby can be parsed, though its parser is notoriously ugly. [1]

[1] see, e.g., http://programmingisterrible.com/post/42432568185/how-to-par...

Re:Ancient languages: Perl (2004) by berntb on Monday August 05, 2013 @06:42PM (#6163663)
You might want to check chromatic's comment on this subject in this comment tree (he has written, amongst other things, my favorite Perl book and hence has gone over these subjects carefully). He argues the halting problem for the parser is only an academic problem.

Edit: https://news.ycombinator.com/item?id=6163283

Re:Ancient languages: Perl (2004) by MichaelSalib on Monday August 05, 2013 @05:10PM (#6163076)
With respect, this is incorrect. You can have load-time execution without making parsing impossible. See Common Lisp for an example.