[antientropic]

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]

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]

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]

>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 ?

[mtlmtlmtlmtl]

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/

[namibj]

CPP needs to feed into itself (pipe stdout into stdin), if you want it to be turing-complete.

[gpderetta]

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.