Re:Proving that C++'s grammar is undecidable
by qppo on Tuesday April 28, 2020 @02:51PM
(#23010410)
Isn't it well known that C++ templates are Turing complete? Aren't most metaprogramming facilities in other languages as well?
[ Parent
| on HN ]
The problem here is that C++'s metaprogramming facilities have leaked into the parser to the extent that it's undecidable whether to parse that final declaration as a variable declaration or a function declaration.
So: arguably the grammar is decidable, but to parse C++ you need more than the grammar, you need the full metaprogramming machinery. That is, C++ has ended up in the same state as a language that simply provides Turing-complete macros.
Re:Proving that C++'s grammar is undecidable
by tines on Tuesday April 28, 2020 @10:58PM
(#23014802)
This is what I love about C++ that isn't provided by [m]any of the "modern" languages (not including Lisp). I want programs in my programs dangit!
Re:Proving that C++'s grammar is undecidable
by roca on Wednesday April 29, 2020 @01:30AM
(#23015703)
If you really want that, it seems better to provide them properly like Rust proc-macros than to provide them in C++'s awful half-baked form.
Re:Proving that C++'s grammar is undecidable
by adev_ on Wednesday April 29, 2020 @02:22AM
(#23016024)
> If you really want that, it seems better to provide them properly like Rust proc-macros than to provide them in C++'s awful half-baked form.
- C++-17 (-20) constexpr is one century in advance in front of rust macro in term of power and what you can do with it. It is not even comparable.
- C++20 compile time execution is currently pretty clean and has nothing to do with this template mess shown here. Definitively not "half baked".
Re:Proving that C++'s grammar is undecidable
by roca on Thursday April 30, 2020 @07:41PM
(#23037569)
Compile-time function evaluation is quite a different feature from macros. Most of what you would do with macros (e.g. output entirely new definitions of functions, types, etc) can't be done with constexpr at all.
And vice-versa.
Re:Proving that C++'s grammar is undecidable
by tines on Wednesday April 29, 2020 @02:08PM
(#23022260)
Yes. From what I understand, Rust's macros/generics are not Turing complete.
Re:Proving that C++'s grammar is undecidable
by steveklabnik on Wednesday April 29, 2020 @04:29PM
(#23023866)
They are. Procedural macros especially are a function that takes tokens and returns tokens, and have the full language at their disposal.
Re:Proving that C++'s grammar is undecidable
by tines on Thursday April 30, 2020 @11:43AM
(#23032092)
Ah interesting. But I imagine that token-based macros don't give you access to the types in the program being compiled do they? i.e. a c++ template can tell when two types are the same but a token level macro wouldn't be able to do that I think.
Re:Proving that C++'s grammar is undecidable
by steveklabnik on Thursday April 30, 2020 @11:45AM
(#23032113)
Correct.
Re:Proving that C++'s grammar is undecidable
by saagarjha on Wednesday April 29, 2020 @01:49AM
(#23015813)
Rust’s compile-time meta programming is lacking at the moment, unfortunately. It doesn’t have const generics yet, and the standard library is a bit anemic and this extends to the type programming utilities as well.
Re:Proving that C++'s grammar is undecidable
by pjmlp on Wednesday April 29, 2020 @02:26AM
(#23016049)
C++'s awful half-baked form comes with 40 years of IDEs, libraries, GUI tooling, OS and GPGPU SDKs, so while I do like Rust, I rather use C++ for the time being, as clunky as it might be.
Re:Proving that C++'s grammar is undecidable
by rowanG077 on Wednesday April 29, 2020 @10:15AM
(#23019487)
You can do it in Haskell with Template Haskell. You can also lift some computation to the type level with means they will run at compile time during type checking.
Re:Proving that C++'s grammar is undecidable
by quietbritishjim on Tuesday April 28, 2020 @05:49PM
(#23012547)
I could be mistaken but doesn't that just mean the value computed into a compile time constant can do arbitrary computation? Whereas I think this is saying that the Turing completeness leaks up to the parsing level.
No, constexpr is not the same thing as template expansion. The decidability problem as I understand it is, "does the template expansion halt?" And since the template syntax in C++ is Turing complete, the answer is "you can't know." I'm just confused how this is significant or different from any other recursive macro expansion, it doesn't seem surprising to me.
Re:Proving that C++'s grammar is undecidable
by mehrdadn on Tuesday April 28, 2020 @09:28PM
(#23014254)
No -- the Turing completeness of templates that people refer to just talks about the fact that templates are powerful enough to compute anything. It's a different issue from parsing the template syntax in the first place, which is the problem they talk about here.
Re:Proving that C++'s grammar is undecidable
by banachtarski on Tuesday April 28, 2020 @09:27PM
(#23014253)
Turing completeness and undecidable parsing grammars are completely orthogonal concepts.