6 ms·

Isn't it well known that C++ templates are Turing complete? Aren't most metaprogramming facilities in other languages as well?

• quietbritishjim 6y ago
  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.
  • qppo 6y ago
    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.
    • mehrdadn 6y ago
      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.
• banachtarski 6y ago
  Turing completeness and undecidable parsing grammars are completely orthogonal concepts.
• roca 6y ago
  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.
  • tines 6y ago
    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!
    • roca 6y ago
      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.
      • saagarjha 6y ago
        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.
      • adev_ 6y ago
        > 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".
        • tines 6y ago
          Yes. From what I understand, Rust's macros/generics are not Turing complete.
          • steveklabnik 6y ago
            They are. Procedural macros especially are a function that takes tokens and returns tokens, and have the full language at their disposal.