5 ms·

Or worse than NP-hard: C++ template instantiation and the C preprocessor are Turing complete. (Except that I believe C++ requires some fixed limit on the maximu

Or worse than NP-hard: C++ template instantiation and the C preprocessor are Turing complete. (Except that I believe C++ requires some fixed limit on the maximum instantiation depth, but even so it's still exponential complexity.)

rocqua 5y ago
I believe you can encode paradoxes in C++ templating. Something about two specializations which are mutually impossible because they reference eachother. So you can say: A is of type T <=> B is not of type T B is of type T <=> A is not of type T Where <=> is if and only if. In which case it is paradoxical to say that A is of type T. But also paradoxical to say that A is not of type T.
- MauranKilom 5y ago
  Note that "a template for which no valid instantiation is possible" is actually ill-formed, no diagnostic required. That said, it's not clear to me what part of "you can write uninstantiable templates" is surprising, so I'm probably not understanding correctly. Maybe you could find the C++ code you're talking about? I would be interested.
Banana699 5y ago
>the C preprocessor are Turing complete That's surprising, the C preprocessor is pretty crippled. It's creator intentionally made it so people won't abuse it to create full blown mini languages. Did you get things mixed up or is there actually a way the c preprocessor can be turing-complete ?
- namibj 5y ago
  CPP needs to feed into itself (pipe stdout into stdin), if you want it to be turing-complete.
  - gpderetta 5y ago
    I believe that while you can't encode an infinite tape, you can very easily define an arbitrarily large tape, so, while not technically Turing complete, it is close enough.
- mtlmtlmtlmtl 5y ago
  Not sure whether this proves turing completeness of the preprocessor or not(probably not) but Simon Tatham has a great(and somewhat disturbing) write-up[1] on creating arbitrary control structures using macros in C. He even goes as far as providing a library of helper macros for doing things like making gensyms, etc. If nothing else, it does demonstrate that you can do a lot more in the preprocessor than you might think, and this is at least a significant subset of what true MP macros are used for in Lisp most of the time. Except much gnarlier... [1] https://www.chiark.greenend.org.uk/~sgtatham/mp/ https://www.chiark.greenend.org.uk/~sgtatham/mp/

rocqua 5y ago

I believe you can encode paradoxes in C++ templating. Something about two specializations which are mutually impossible because they reference eachother. So you can say: A is of type T <=> B is not of type T B is of type T <=> A is not of type T Where <=> is if and only if. In which case it is paradoxical to say that A is of type T. But also paradoxical to say that A is not of type T.

MauranKilom 5y ago
Note that "a template for which no valid instantiation is possible" is actually ill-formed, no diagnostic required. That said, it's not clear to me what part of "you can write uninstantiable templates" is surprising, so I'm probably not understanding correctly. Maybe you could find the C++ code you're talking about? I would be interested.

Banana699 5y ago

>the C preprocessor are Turing complete That's surprising, the C preprocessor is pretty crippled. It's creator intentionally made it so people won't abuse it to create full blown mini languages. Did you get things mixed up or is there actually a way the c preprocessor can be turing-complete ?

namibj 5y ago
CPP needs to feed into itself (pipe stdout into stdin), if you want it to be turing-complete.
- gpderetta 5y ago
  I believe that while you can't encode an infinite tape, you can very easily define an arbitrarily large tape, so, while not technically Turing complete, it is close enough.
mtlmtlmtlmtl 5y ago
Not sure whether this proves turing completeness of the preprocessor or not(probably not) but Simon Tatham has a great(and somewhat disturbing) write-up[1] on creating arbitrary control structures using macros in C. He even goes as far as providing a library of helper macros for doing things like making gensyms, etc. If nothing else, it does demonstrate that you can do a lot more in the preprocessor than you might think, and this is at least a significant subset of what true MP macros are used for in Lisp most of the time. Except much gnarlier... [1] https://www.chiark.greenend.org.uk/~sgtatham/mp/ https://www.chiark.greenend.org.uk/~sgtatham/mp/