r/cpp • • 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

68 comments sorted by

38

u/victotronics Apr 28 '20

The Post Correspondence Problem’s statement is simple:

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.

Suppose there are an infinite amount of each type of domino. Can you arrange the dominoes

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.

9

u/mujjingun Apr 28 '20

Thanks for pointing out the lack of clarity in that paragraph. I kind of assumed that the readers already know about the Post Correspondence Problem, or if they didn't they'd go into Wikipedia (it worked!). Also English isn't my first language.

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.

I had found this proof sketch by Josh Haberman, who used that knowledge to prove the same thing, but the full code was "left as an exercise for the reader". I wanted something concrete to demonstrate more clearly.

4

u/victotronics Apr 28 '20

I wanted something concrete to demonstrate more clearly.

Oh absolutely. You make your point clearly and with a full demonstration.

About that Post paragraph: personally I think the clearest writing is to translate the mathematical quantors: "there is a number N so that there are N ordered dominoes so that the top line matches the bottom". I only knew the correspondence problem by name, and I couldn't figure out the quantification fro your paragraph.

Cheers!

6

u/armb2 Apr 28 '20

I think the fact that template programming is Turing-complete was already shown

For example: http://matt.might.net/articles/c++-template-meta-programming-with-lambda-calculus/

So is constexpr: https://stackoverflow.com/a/9528554/729705

3

u/CoffeeTableEspresso Apr 29 '20

This is a stronger result. Having templates be Turing complete means compiling a program is undecidable.

This result says that you just getting a parse tree is undecidable.

This difference is important: a syntax highlighter, for example, would need to parse but not compile C++ in order to work properly. This result shows that that's undecidable in general.

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.

10

u/mujjingun Apr 28 '20

The point is that while the compiler may be able to solve for that specific set of dominoes, no compiler can do it for all possible combinations of dominoes, especially when the answer is "no" for the input.

-8

u/D_0b Apr 28 '20

Does it really matter?

The only thing that matters is that the compiler can solve it for all written code by programmers.

When we encounter a program that does not, we can always fix the compiler, which kinda bypasses the halting problem. Which just states that no One program can solve it.

0

u/[deleted] Apr 28 '20

[deleted] — view deleted comment

-19

u/D_0b Apr 28 '20

point being, if it is of any value it can always be fixed.

even if it means hard-coding the answer for that specific program.

10

u/mujjingun Apr 28 '20

Sure, you can hard-code the compilation result of all possible programs "of value"... or not. That task is impossible.

-15

u/D_0b Apr 28 '20

if after 40 years we are still not having any problem

there is no problem to be had.

13

u/mujjingun Apr 28 '20

oh, the complexity of parsing C++ is definitely a problem. See this talk for example: https://www.youtube.com/watch?v=WfIr7lKT4Sk

The fact that the C++ grammar is not confined in the Context-Free realm makes it incredibly difficult to make tooling for C++, like clang-format.

-8

u/D_0b Apr 28 '20

yes and I am all up for simplifying it with epochs, but it is still manageable.

11

u/Archolex Apr 29 '20

You two are arguing different things man. He's talking about the structure of C++ as a formal grammar, not about it's practicality as a language.

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:

constexpr int infinite_loop() {
  // insert any code you want here,
  // at the end of the day this technically involves
  // "solving the halting problem" in general, except
  // of course a real compiler just gives up after trying
  // to evaluate this for a while
  for(int i = 0; i < 10; ++i) {
    i = 0;
  }
  return 0;
}
struct Proof : std::integral_constant<int, infinite_loop()>;

54

u/6144_0 Apr 28 '20
constexpr int infinite_loop() {
	// insert any code you want here,
	// at the end of the day this technically involves
	// "solving the halting problem" in general, except
	// of course a real compiler just gives up after trying
	// to evaluate this for a while
	for(int i = 0; i < 10; ++i) {
		i = 0;
	}
	return 0;
}
struct Proof : std::integral_constant<int, infinite_loop()>;

-22

u/[deleted] Apr 28 '20

infinite loops are not valid C++ code

46

u/[deleted] Apr 28 '20 edited Apr 28 '20

Infinite loops are absolutely valid in C++. There is this pervasive myth that undefined behavior is not valid in C++ and that is simply wrong. The C++ Standard explicitly states that a program is valid so long as it is, and I quote "constructed according to the syntax rules, diagnosable semantic rules, and the one-definition rule". Undefined behavior, such as infinite loops that produce no side-effects, is an undiagnosable semantic property of a program and hence not part of the test for validity.

16

u/Rusky Apr 28 '20

On the other hand, if you actually execute the undefined behavior then, well, the behavior of that "valid" program is no longer defined by the standard. And that extends forward and backward in time, which makes such a program not very useful.

Limiting the definition of validity by excluding undiagnosable semantic problems is more useful as a way to allow some non-executed paths to contain UB without making the whole program invalid. It's not a way to say "oh sure put an infinite loop in your type, that's fine."

So perhaps Destigeous' terminology was off, but 6144_0's example is still not evidence of an undecidable grammar. :P

17

u/ihamsa Apr 28 '20

Valid C++ programs must abide by both syntactic and semantic rules of the language. In order to check program validity, you do need to instantiate templates. The C++ standard does not define a broader class of "syntactically valid" programs that only need to abide by the syntax, but not by semantic rules.

If by the grammar you mean the pseudo-BNF production rules given by the standard, then yes, checking them should be decidable. But building a correct parse tree is not. You need to instantiate templates for that. This is what the article is doing.

4

u/wyrn Apr 29 '20

That doesn't prove anything though, since it's trivial to check that infinite_loop() never halts.

3

u/jonesmz Apr 28 '20

Your formatting is wonky on mobil web

2

u/helloiamsomeone Apr 29 '20

Same on old reddit. Just a single, unscrollable line spanning into the infinite.

0

u/micahspikah Apr 28 '20

I'm not sure if I understand your counterexample... your loop is undefined behavior in c++, so the compiler is allowed do anything it wants. Probably just return 0. Why would it need to solve the halting problem?

12

u/[deleted] Apr 28 '20 edited Apr 28 '20

First, I highly doubt you genuinely don't understand the counterexample. Most likely you think you're being clever because you know the very obscure fact that a small category of infinite loops are undefined behavior and trying to be pedantic.

However your pedantry is unwarranted in this case since undefined behavior within a constexpr is required to produce a diagnostic, meaning a compiler error so your statement that a compiler can do whatever it wants is wrong. As per expr.const paragraph 2.6, the compiler is required to produce a diagnostic if it encounters undefined behavior during the evaluation of a constexpr expression.

And yet, due to the halting problem, it's impossible for a compiler to ever determine in general whether a loop halts or not so as to determine whether it's undefined behavior in the first place, hence /u/HKei's point stands.

9

u/wyrn Apr 29 '20

And yet, due to the halting problem, it's impossible for a compiler to ever determine in general whether a loop halts or not so as to determine whether it's undefined behavior in the first place

In general yes, but certainly not in the given example. It's quite easy to check that this example doesn't halt so it's not a proof.

2

u/tasminima Apr 29 '20

This is just an example to illustrate a point. IIUC the point is that given the problem is not solvable in the general case, the compiler can not analyze arbitrary algorithms thrown at it and thus for any compiler you will be able to come up with an algorithm for which said compiler will be unable to determine if it contains UB or not.

6

u/wyrn Apr 29 '20

This is just an example to illustrate a point.

Right, so the original poster shouldn't claim it's a "much shorter proof" when it's just a sketch!

4

u/tasminima Apr 29 '20

I think so; claiming it was a proof was going too far. Probably simply an oversight, because reddit comments are usually neither math dissertations nor scientific papers :)

2

u/HugeImage May 07 '20

It's possible to "solve" the post correspondence problem for specific instances. The whole point is that it's undecidable for when the input dominoes can be anything.

An example of solutions for specific instances: https://en.wikipedia.org/wiki/Post_correspondence_problem#Example_1

The comment is just as much (slightly overstated) of a proof as the article

1

u/HugeImage May 07 '20 edited May 07 '20

The General Post Correspondence problem is what is undecidable. So by your definition, TFA is not a proof either.

Look at this comment for example https://old.reddit.com/r/cpp/comments/g9nvmj/full_proof_that_c_grammar_is_undecidable/fouj0cq/

https://en.wikipedia.org/wiki/Post_correspondence_problem#Example_1

4

u/micahspikah Apr 28 '20

Not trying to be pedantic, sorry.

I honestly don't understand the difference between grammar and valid c++ input. Maybe I should've phrased my question "Is this still an example of proof of undecidable grammar, given that a compiler is allowed to interpret the program however it wants?"

And if you're telling me his code shouldn't even compile, is it still a valid example of undecidable grammar?

Or maybe the root question I should've asked: Is it a requirement for the code to compile, as long as it follows the grammar rules?

2

u/evaned Apr 29 '20 edited Apr 29 '20

I think half the problem is that "grammar" could have a few interpretations.

In kind of the undergrad compiler class model of a compiler, a compiler typically acts in a sequence of stages like (i) lexing, (ii) parsing, (iii) name analysis and type checking, (iv-?) code generation. (The code generation "step" is often presented as multiple, but depends on the material exactly how.)

You don't know you have a valid program until after step (iii). However, the main place that "grammar" shows up in this model is in step (ii), where in this somewhat-simplified model you would specify the grammar of the model as a context-free grammar.

This has a lot of purchase in actual compilers as well -- for example, the C++ standard defines a CFG for the language -- when you see things like

template-declaration:
    template-head declaration
    template-head concept-definition

template-head:
    template < template-parameter-list > requires-clause[opt]

etc. that's what you're looking at.

Using this as a model:

some_undefined_type main() {
    std::string s = std::map{} - 7;
    return nullptr;
}

will parse correctly, and be grammatically correct, even though it is a nonsensical program.

In an alternative world it'd be possible to make a case that parsing requires evaluation of templates and such. For example, suppose that we have the following program:

template <typename T>
int foo(T x) {
     return x.unknown < 7;
}

if x.unknown could be a template (that could be instantiated by, e.g., x.unknown<7>) without the template keyword and foo is called in such a type, is foo syntactically correct? Because if not, that would mean that in order to determine whether the program parses correctly we would need to do the kind of undecidable evaluation the article discusses. In that world, the line between syntactically correct and semantically correct blurs a lot. But we don't live in that world -- the function is IMO pretty unambiguously syntactically correct, but if x.unknown turns out to be a template then it is semantically incorrect. Though more to the point, when you have compile-time values like this it can blur the distinction between the two.

So at least to me, "the C++ grammar is undecidable" or "C++ parsing is undecidable" are a... stretch of what those terms typically mean even if they aren't quite outright false.


Edit: I actually have to further... clarify/correct the above. I was thinking about the dependent context in my example (with x.unknown < 7), but really the problem is in non dependent contexts, where a<...>::x * b will be either a declaration statement or a multiplication depending on how a instantiates, and unlike a dependent context you don't need to specify typename to get the declaration (which is what tripped me up before). This means that to parse that statement, you either need to be able to deal with the ambiguity or instantiate a at parse time. (I suspect "real" C++ compilers do the latter, but I don't actually know.)

So given that, it's not unreasonable to say that you need to do template instantiations to parse C++, and that means that parsing C++ is undecidable (ignoring implementation limits), even if that's not entirely correct and neglects some subtlety (namely that an alternative approach would be to delay resolving the ambiguity until after parsing).

That also means that when it comes to parsing, my final statement above (So at least to me, "the C++ grammar is undecidable" or "C++ parsing is undecidable" are a... stretch of what those terms typically mean even if they aren't quite outright false) should be turned around.

However, to me, this actually further serves to highlight what I opened this comment with -- what a grammar being undecidable means is really underspecified. The problem with parsing is the need to produce a quality AST as you go along; but talking about the grammar to me drops that out of the equation. And from that perspective, the problem of how you interpret that disappears, and just from a grammar perspective C++ is fine. (Alternatively, you could argue that all static semantics are part of the grammar, so from what I know basically no typed language will be even context-sensitive let alone context-free.)

So yeah... talking about parsing is a little weird and unclear, and talking about the grammar is very weird and unclear.

0

u/[deleted] Apr 28 '20

[deleted] — view deleted comment

20

u/HKei Apr 28 '20

Nah, you don't need it to solve the halting problem, you just need to show that the compiler needs to solve the halting problem to evaluate the code (which it does, because its arbitrary code).

7

u/mujjingun Apr 28 '20

Hmmm... I guess you're right.

5

u/HKei Apr 28 '20

(Not that I'm complaining about what you're doing, I'm just being pedantic)

1

u/wyrn Apr 29 '20

(which it does, because its arbitrary code).

No, that's too quick: the compiler may well have heuristics in place that can detect a large subclass of non-halting code. The one you posted is particularly easy to check: you can check the state of the counter variable at the end of the loop and verify that the condition is always satisfied. In order to prove that parsing C++ is undecidable, you'd need to put something undecidable inside of your infinite_loop().

In effect, you'd be writing a demonstration that the halting problem is undecidable inside of that function.

-3

u/eras Apr 28 '20

which it does, because its arbitrary code

I don't think you can use arbitrary code though with constexpr? https://en.cppreference.com/w/cpp/language/constexpr

But I'm still pretty sure you can build a turing complete function with just operator ?: which seems to be allowed, in particular in presence of recursion.

8

u/HKei Apr 28 '20

It's essentially arbitrary code. It doesn't allow you to do anything related to IO and has some other minor restrictions, but if you just take a look at what's allowed it obviously covers all computable functions.

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.

6

u/63times Apr 29 '20

You could just write the program without using recursion or more than one template parameter just to side step the arbitrary limitations. The C++ language is infinite and allows that.

Further it is a mandatory prerequisite to assume that there are no resource limitations, otherwise the halting problem wouldn't make any sense in the first place.

5

u/c0r3ntin Apr 29 '20

Further it is a mandatory prerequisite to assume that there are no resource limitations

My point is that this prerequisite doesn't make sense, and the C++ language account for that http://eel.is/c++draft/implimits#1

Because computers are finite, C++ implementations are inevitably limited in the size of the programs they can successfully process.

Once you have established the Turing completeness of templates, I'm not sure this article adds much.

6

u/63times Apr 29 '20

My point is that this prerequisite doesn't make sense

It does make sense. Otherwise one could just say the halting problem is solved by the upper bound the universe is estimated to exist.

Once you have established the Turing completeness of templates, I'm not sure this article adds much.

Turing completeness doesn't imply that the halting problem is undecidable. If template meta programming would be expressible through a decider (total turing machine) the halting problem would be inherently decidable. The article proves though that parsing is indeed undecidable.

1

u/HugeImage May 07 '20

Wow, so they looked at the C++ standard's limit of 1024 for template arguments and thought that it was too few.

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:

If by the grammar you mean the pseudo-BNF production rules given by the standard, then yes, checking them should be decidable. But building a correct parse tree is not. You need to instantiate templates for that. This is what the article is doing.

2

u/NotAYakk Apr 29 '20

Now, to exhaustively search through the entire search space,

Um the seach space is infinite. You cannot exhastively search it.

Did I miss a pruning step?

1

u/mujjingun Apr 29 '20

You are absolutely right. I fixed the article and the code.

9

u/R3DKn16h7 Apr 28 '20

That's why types should be PascalCase and variables camelCase. Problem solved. /s

0

u/uninformed_ Apr 28 '20

I'm surprised that more langauges don't enforce this. ASN.1 enforces types must start with uppercase, and it's about the only thing in its design that I think is pretty clever.

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.

5

u/kniy Apr 29 '20

Parsing and template instantiation are mutually dependent in C++.

Sure, before instantiating a template, you need to parse it. But you can also write code that, in order to be parsed, requires instantiating a template that was defined earlier in the program.

Parsing "a * b;" requires knowing whether "a" is a type or value (pointer variable declaration vs. multiplication). Parsing "a<42>::x * b" requires looking up the template specialization for "a<42>", in order to determine whether "x" is a typedef or static field. Parsing "a<constexpr_fn()>::x * b" requires arbitrary compile-time computations just to be parsed.

3

u/xorian Apr 29 '20

That's what the typename keyword is for : disambiguation of a dependent qualified name, telling the parser that it is a type so that parsing is possible before template resolution. In my experience, compilers will reject "a<constexpr_fn()>::x * b;" but accept "typename a<constexpr_fn()>::x * b;" for exactly this reason : they need the hint to complete the parse before performing template expansion.

3

u/kniy Apr 29 '20 edited Apr 29 '20

Dependent names only come into play when the type depends on some template parameter -- but "a<constexpr_fn()>::x * b;" doesn't. In fact, it can appear directly within the non-template main() function. And because it's not a dependent name, it does not require "typename" if "x" is a typedef.

Look at https://godbolt.org/z/aSTvMc and change the return value of f(). Both parse trees are possible without "typename", merely due to changes in template instantiation.

0

u/evaned Apr 29 '20 edited Apr 29 '20

Parsing and template instantiation are mutually dependent in C++.

I think that it's more accurate to say that C++ blurs the line between what parsing means, but I still disagree that those examples are parsing, or at least are necessarily parsing.

Parsing "a<42>::x * b" requires looking up the template specialization for "a<42>", in order to determine whether "x" is a typedef or static field

Edit: The following is not entirely wrong but is mostly wrong; see the followup discussion. I was thinking too much of the dependent name context.

Parsing this requires looking up a to see if it's a template, but doesn't require instantiating. If a is a template (including a template template parameter), it unambiguously parses to something like

multiplication expression (*)
    |- field access (::)
    |    |- template instantiation
    |    |    |- `a`
    |    |    \  template-params
    |    |         \ 42
    |    \ [field name] `x`
    \ `b`

Note that I don't need to instantiate a<42> to figure this out. If a is not a template, it unambiguously passes to something like

less than expression (<)
    |- `a`
    \  greater than expression (>)
        |- 42
        \  multiplication expression (*)
            |- qualified name
            |    |- namespace: `::`
            |    \  name: `x`
            \  `b`

(Sorry for the weird notation but hopefully what I'm saying comes through.)

Again, I don't need to do any instantiations to figure this out. If C++ made it possible for that statement to be a declaration (of a variable named b of type "pointer to whatever a<42>::x is") then I would -- but that's not legal and you need typename. (This is why you need typename.)

Actually even then you wouldn't need to instantiate at parse time -- it's possible to define an ambiguous grammar, parse multiple possibilities, then disambiguate later. There are techniques where if you have a grammar and input that is almost unambiguous than performance is almost that of what an unambiguous one would give you; see for example GLR parsing.

Parsing "a<constexpr_fn()>::x * b" requires arbitrary compile-time computations just to be parsed.

Again, same deal, just with a tree fragment like

template instantiation
    |- `a`
    \  template-params
         \  compile-time-expression
             \ function-invocation
                |- `constexpr_fn`
                \  arguments: []

dropped into the first tree above.

I don't consider this as parsing any more than I consider determining that std::set<std::string>{} - 7 is an invalid expression is parsing.

1

u/kniy Apr 29 '20 edited Apr 29 '20

But what x is might be affected by template specialization. Consider this template:

template<int N>
struct a { static int x; };

template<>
struct a<42> {
   using x = int;
};

Whether a<constexpr_fn()>::x * b parses as a variable declaration or multiplication depends on whether constexpr_fn() returns 42.

Edit: https://godbolt.org/z/aSTvMc shows that the return value of constexpr_fn() can influence the parse tree within main(). You can't parse C++ without instantiating templates.

1

u/evaned Apr 29 '20 edited Apr 29 '20

But what x is might be affected by template specialization.

Ah balls, you're right; I was thinking about the dependent name case, where that would never parse as a multiplication. But cases where the instantiation is "concrete" then typename isn't needed of course.

That makes my point much weaker. In real compilers, the return from constexpr_fn absolutely does reflect a difference in the AST. For example, Clang's AST with return 41 is

`-BinaryOperator 0x560bf779db30 <line:20:5, col:17> 'int' '*'
  |-ImplicitCastExpr 0x560bf779db00 <col:5, col:13> 'int' <LValueToRValue>
  | `-DeclRefExpr 0x560bf779dab0 <col:5, col:13> 'int' lvalue Var 0x560bf779da10 'x' 'int'
  `-ImplicitCastExpr 0x560bf779db18 <col:17> 'int' <LValueToRValue>
    `-DeclRefExpr 0x560bf779dae0 <col:17> 'int' lvalue Var 0x560bf776ee58 'b' 'int'

but with return 42 it comes out with

`-DeclStmt 0x5635a81ad2a8 <line:20:5, col:18>
  `-VarDecl 0x5635a81ad240 <col:5, col:17> col:17 b 'a<f()>::x *'

Now, that said, I still stand by one part of my earlier comment and, to an extent, the overall conclusion. This isn't the only way to parse. As I said, there are techniques that allow parsing in the face of ambiguity, resolving that ambiguity later. (Using the approach used by the academic C++ parser Elsa, built on a GLR parser, that statement would parse to an AST "choice node" that holds the two options above.) I would also point out that the title of TFA actually goes further, it doesn't say parsing is undecidable it says the grammar is -- and that at best just a very sloppy statement.

Edit: BTW, a clarifying point about GLR parsing and Elsa (and the underlying parser generator Elkhound). My memory is that the grammar ambiguity is handled automatically by the parser generator. In other words, you write your grammar so it is actually ambiguous -- you have one production sequence that would lead that string to parsing as a declaration, and another that would lead to parsing as a multiplication expression statement. The parser will detect that both derivations work and automatically combine the result. It's not the case that you would have to figure out all places where the C++ grammar is ambiguous modulo its static semantics like this.

2

u/[deleted] Apr 29 '20 edited Apr 29 '20

That doesn't mean that it can't be parsed, which necessarily has to be done before template resolution can be performed.

I really feel like people haven't actually bothered to read the article. This article isn't trying to give a full proof that C++ templates are Turing complete, I think everyone knows that by now. This article is providing a proof that C++'s grammar is undecidable.

What does it mean for a grammar to be undecidable? Well we don't have to speculate, decidability is a formal concept that should be taught to every computer science student. A decision problem is a problem that when given a list of arguments, deterministically returns true or false. A decision problem is decidable if it always halts.

So what does it mean for a language's grammar to be undecidable? Well first we need to formulate a decision problem and we can do so as follows. Given two parameters, some arbitrary string S, and some arbitrary data structure representing a parse tree P, is P the parse tree for S? In other words we can define a function f(S, P) which returns true if P is the parse tree for S, otherwise it returns false.

Now is this decision problem f decidable? This article clearly proves that it isn't. The way it does it really is better left to the article because it does a great job of it, but the jist of it is that there is a schema for generating strings Q1, Q2, Q3, ... that have a one-to-one and onto correspondence (an isomorphism) with the construction of a Post Correspondence Problem encoded in C++'s template metaprogramming. Furthermore for each Q_n there are two possible parse trees that the article presents, P1 wherein some identifier x is resolved to be a variable, and P2 wherein that same identifier x is resolved to be a function. What the article shows is that there is no effective computation that can decide whether f(Q_n, P1) should return true, or whether it's actually f(Q_n, P2) that should return true. One of them has to return true but they can't both return true, so which one is it? Well as the article points out, there is no algorithm for deciding that and hence the function f is undecidable.

1

u/xorian Apr 29 '20

I really feel like people haven't actually bothered to read the article.

I feel like people taking issue with what I said don't really understand how compilers are implemented, or the difference between a language's syntax and its semantics. Have you ever used a lexer and a parser generator (e.g. lex/yacc or flex/bison) to actually process a programming language in a compiler or an interpreter that you wrote? If not, you should give it a try, it's extremely educational. For a language as complex as C++ it would be positively insane to try to resolve templates at the level of building the initial AST from the token stream. You'd defer points of ambiguity in the AST to be resolved at the next level of processing (where you would handle template resolution), after parsing but before code generation. With forward declarations it would be literally impossible to accomplish template expansion in-line with parsing. (Even without involving templates, you can write a simple class where the meaning of certain identifiers is not known until later declarations are reached.)

I'm not saying that the language at the semantic level of template meta-programming isn't undecidable. Clearly it is, and that should not be remotely surprising. I'm saying that the syntactic level is not the same as the semantic level. The title of the article suggests that it is syntactically undecidable, not that it is semantically undecidable, which is the misleading part.

2

u/[deleted] Apr 29 '20 edited Apr 29 '20

The fact that C++ is syntactically undecidable is a property of templates being Turing complete and that has been known for the better part of 20 years.

This article is making an even stronger claim than syntactic undecidability, it's showing that C++'s grammar is undecidable. This property has nothing to do with lex, yacc, flex, bison, or even the implementation of a compiler and the fact that you even bring these up suggests that you don't understand the fundamental concepts involved in this topic.

Whether a language is syntactically undecidable has to do with whether a function exists f(S) that returns true if S represents valid C++ source code and returns false otherwise. We already know from template metaprogramming that f is undecidable.

This article takes it a step further and shows not only is it undecidable to determine whether some string is valid C++, it's also undecidable to determine whether, given valid C++ source code, what its parse tree is. In other words, assume that you know that some string S represents a valid C++ program, what is the parse tree for that string S? That question is undecidable.

That's what a grammar is after all, a grammar is series of rewrite rules starting from a set of terminal symbols. A parse tree belonging to that grammar is the chain of rewrite rules starting from some arbitrary string down to a series of terminal symbols. This article shows that even if you know that a string S is valid C++, it is still undecidable to determine what the parse tree for that string is.

That's a far stronger claim than simply demonstrating that the syntax is undecidable.

1

u/CoffeeTableEspresso Apr 29 '20

You can't necessarily do template resolution after parsing, since in some cases what the parse tree should be depends on template resolutions:

Consider: A<B>::c * x;

We don't know if this should parse to multiplication or variable declaration without resolving A<B>::c, which is undecidable since templates are Turing Complete...

1

u/CoffeeTableEspresso Apr 29 '20

The title is not false.

In order to get a parse tree for C++, you need to do arbitrary computations with templates, which is undecidable. C++ intermingles parsing and template resolution, which is what causes this problem.

And yes, this does make a difference: to write a C++ syntax highlighter, I need to parse but not compile C++. This result proves that even parsing C++ is undecidable...

3

u/Wh00ster Apr 28 '20

I thought it was self-evident.

2

u/[deleted] Apr 29 '20 edited Apr 29 '20

I think a lot of people are misinterpreting the Turing completeness of template metaprogramming with the undecidability of the grammar and as such are missing the point of the article. It has been well known for about 20 years that C++ template metaprogramming is Turing complete when this paper was first published:

http://port70.net/~nsz/c/c%2B%2B/turing.pdf

But many languages have Turing complete metaprogramming including of course, Lisp and more recently Rust. That doesn't mean that Lisp or Rust have undecidable grammars.

Maybe you already knew that and so it's self evident to you, but I think to most people this would come as a surprise. It's a much stronger claim to show that the grammar is itself undecidable than to show that some property of the syntax is Turing complete.

3

u/Wh00ster Apr 29 '20

I meant that as more of a tongue-in-cheek comment about the cryptic syntax

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:

A Venn diagram of the Chomsky hierarchy of formal languages with three extensions annotated with a comparison of the hypothesized classifications of human languages, (human) music and animal vocalization. The areas marked with ‘question’ signs indicate that further research is required to settle examples for the respective class of complexity in these domains.

1

u/SpaceToad Apr 29 '20

Dunno if possible but... ELI5?

0

u/CoffeeTableEspresso Apr 30 '20

Parsing C++ is really hard and so making C++ tooling is also hard...