Hacker News Reader

Comment by c0m0 | Hacker News Reader

For the people out there that's not so into CS, and does not understands it's implications. It basically means you could write a perl program that could cause an infinite loop in the interpreter (or compiler). This I would presume independant of the actual implementation of the compiler and intrepreter as that would only mean this is a bug report for the specific implementation, and not a problem with the language design.

View on HN

perl works fine, and you aren't going to unexpected trigger an infinite loop due to some bug in the language definition.

What you can't do is tell how to parse a piece of perl without running the program.

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

These are an expounding upon this link. In most languages, you can at least tell what things are. This is a function. That's a variable. In perl, there are constructs whose parsing depend on what a given bit of code was defined as previously, and that definition can be predicated on code execution. This leaves you in a situation where you cannot tell if something is a division and comment or a regex without knowing whether a function takes arguments. ( see link )

If you can't in general parse a piece of perl without "running the program" as you yourself mentioned then I'm pretty sure that parsing it can definitely trigger infinite loops as perl language is definitely turing complete during run time. So your statement is a contradiction.

The comment said you won't cause an infinite loop during parsing due to a bug in the language definition, not that you can't do so at all. Perl lets you run arbitrary code during parsing, so of course it's possible to run an infinite loop while parsing. But you can only do that by actually writing an infinite loop in your code, not by writing something that confuses the parser into looping forever.

Actually the problem has more implications, as it's an effect of parsing the code. Any IDE:s that have advanced features that rely on parsing and analysis of the code can be caught in an infinite loop and stop responding.

The sad part is, in the general case it's impossible for the parser (or any other process overviewing it) to decide if it's actually caught in an infinite loop or not, that's why they call it undecidability.

In theory, yes. Of course in practice, it's not so bad: they can run the parser in a different thread, they can put hard limits on how long they run, etc.

(The hard limit is how C++ gets parsed, I think. Since parsing C++ is also undecidable thanks to weird interactions with template metaprogramming.)

Yes, templates are turing complete.

https://github.com/knome/metabrainfuck/blob/master/bf.cpp

Does attempting to autocomplete such a template cause issues for IDEs? I used emacs when writing it, so I've never tested such a thing.

For simpler languages you can implement logic in the editor / IDE for things like precise autocomplete and parsing.

For C++ even precise syntax colouring would be undecidable---and just hard to get the logic right. There are two ways out: (1) implement an approximation and the occasional impression, (2) ask the compiler for help. I think the llvm project helps with the latter.

(What does emacs have to do with things? Or do you mean you are using emacs without any special support for C++? With the right modes you can turn your emacs (or vim etc) into basically a fully fledged IDE.)

Reply on news.ycombinator.com