2 ms·
Unless something has changed a lot, C++ templates at least only used to be Turing complete if you assume you're allowed unlimited recursive template application
by vidarh 5y ago
Unless something has changed a lot, C++ templates at least only used to be Turing complete if you assume you're allowed unlimited recursive template applications, and compilers were free to restrict that (and did). Has that changed?
In theory I agree with you that this is horribly ugly - I very much prefer simple grammars (the irony being my favourite language to use is Ruby, which has an atrocious grammar). In practice these parses are rarely that hard to resolve.
- steerablesafe 5y agoWell, C++ now has constexpr functions that can run in compile time, and do basically arbitrary computation. But it also has implementation limits.
- praptak 5y agoIt's not the undecidability itself that is the problem though. The undecidability is just an indicator how horribly complicated C++ is to compile. You cannot even construct the full parse tree before evaluating a mini-language that is Turing complete. Related article: why C++ compilation is slow (https://digitalmars.com/articles/b54.html https://digitalmars.com/articles/b54.html)
- vidarh 5y agoI have a half-finished Ruby compiler sitting around, so I'm a bit jaded when it comes to how complicated something is to compile. C++ is complex, but at least it's reasonable well specified.