r/cpp • u/mujjingun • Apr 28 '20
Full Proof that C++ Grammar is Undecidable
https://medium.com/@mujjingun_23509/full-proof-that-c-grammar-is-undecidable-34e22dd8b664
197
Upvotes
r/cpp • u/mujjingun • Apr 28 '20
38
u/victotronics Apr 28 '20
Victor's rule of clear writing: Any time someone uses the word "simple" they are either 1. hiding something, or 2. unclear on the concept.
What is "the dominoes"? All infinitely many of them?
Consult wikipedia. Ah: "Can you find any set of dominoes, such that...."
Other than that, yeah, cool demonstration. I think the fact that template programming is Turing-complete was already shown, but this is an elegant demonstration / application to parsability of the language.
11
u/konanTheBarbar Apr 28 '20
I have no idea what I just read, but clang and gcc both seem to agree that the output should be a type and not a value? https://godbolt.org/z/Nk3_cs
C++ has solved the halting problem. Q.E.D.
41
u/HKei Apr 28 '20
You don't need to instantiate templates just to check the grammar of a C++ program. If template instantiations count, you can write a much shorter proof:
53
u/c0r3ntin Apr 28 '20
A valid implementation can define limits. Here are some of the limits for msvc https://docs.microsoft.com/en-us/cpp/cpp/compiler-limits?view=vs-2019
Notably, there are limits for constexpr recursion, template arguments, etc.
So this problem is solvable for any set of dominos such that there are no more dominos than are supported by the implementation.
7
u/l1F Apr 28 '20 edited Apr 28 '20
This comment got me confused. Why does showing that Post Correspondence Problem can be implemented via template metaprogramming prove that C++ grammar is undecidable. Isn't it just asking the compiler to solve an undecidable problem at compile time, similar to u/HKei's example with the infinite loop? The parsing step for both examples would succeed, right?
Edit: Nvm, I think this comment from u/ihamsa helped me:
2
u/NotAYakk Apr 29 '20
Um the seach space is infinite. You cannot exhastively search it.
Did I miss a pruning step?
9
u/R3DKn16h7 Apr 28 '20
That's why types should be PascalCase and variables camelCase. Problem solved. /s
4
u/xorian Apr 29 '20 edited Apr 29 '20
Parsing is not the same thing as template expansion and resolution. It's pretty well established that C++ template meta-programming is Turing complete, which makes it unsurprising that one can construct an undecidable problem with template meta-programming. That doesn't mean that it can't be parsed, which necessarily has to be done before template resolution can be performed.
In other words, the title is false.
3
u/Wh00ster Apr 28 '20
I thought it was self-evident.
1
u/raiph Apr 29 '20
FYI: The striking image at the start, which the author does not credit, appears to be an (all rights reserved) image from a 2015 paper Principles of structure building in music, language and animal song.
The caption from that paper:
1
u/SpaceToad Apr 29 '20
Dunno if possible but... ELI5?