3 ms·
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 nice
by peterwwillis 13y ago
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!)
- MichaelSalib 13y agoWith respect, this is incorrect. You can have load-time execution without making parsing impossible. See Common Lisp for an example.
- dragonwriter 13y ago> 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-parse-ruby http://programmingisterrible.com/post/42432568185/how-to-par...
- berntb 13y agoYou 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 https://news.ycombinator.com/item?id=6163283