Parsing C++ is literally undecidable (2013)

http://blog.reverberate.org/2013/08/parsing-c-is-literally-undecidable.html

by umanwizard • 7 years ago

111 142 7 years ago

blog.reverberate.org

lallysingh3• 7 years ago

This is why the tools situation in c++ had been so far behind other languages like Java. You have to build a full frontend to even parse the language.

They're slowly becoming available via clang now, which is nice.

msla• 7 years ago

I wonder if it's possible to craft a non-gigantic C++ file which causes a clang frontend to crash.

earenndil• 7 years ago

For sure. Generally it boils down to a non-gigantic number of template instantiations or macro expansions that end up generating a huge parse tree.

jeeyoungk• 7 years ago

This is possible in almost all language, even Python (!!!) - see the Stack Overflow question https://codegolf.stackexchange.com/questions/69189/build-a-c...

pnako• 7 years ago

There is this funny competition: https://tgceec.tumblr.com/

You could pick the winning entries and use them as a corpus for a fuzzer and you might find compiler crashes.

gpderetta6• 7 years ago

ICEs [1] used to be very common from all front ends especially with malformed template code, but now a day I think most compilers don't report an ICE to the user as long as they managed to issue at least one diagnostic.

It is still not uncommon to se ICEs on some extreme template constructs.

[1] Internal Compiler Error, i.e. the compiler segfaulted or hit an internal assertion.

millstone2• 7 years ago

Java has generics and overloading; how far can you realistically get before building a full frontend? Honest question.

saagarjha3• 7 years ago

Anecdotal, but I’ve found it difficult to find a Java autocomplete plug-in that doesn’t run Eclipse in the background to work.

username90• 7 years ago

Java generics are just syntactic sugar for Object, so not a problem at all since you can't do anything with them.

Java overloading is simple since all functions are in the same file (so doesn't change overload behavior depending on which files are imported) and Java lacks the user type casts C++ has, so just pick the signature fitting all provided values (with numeric casts) or throw.

lallysingh3• 7 years ago

The grammar is still context free.

jonstewart2• 7 years ago

Can you be more specific and/or support the argument that the tools for C++ are behind what's available for Java?

Visual Studio has had Intellisense since forever, clang-format can enforce style standards, static analyzers these days are amazing, the address sanitizer and valgrind find memory problems easily, etc.

coldpie• 7 years ago

Can you be more specific and/or support the argument that the tools for C++ are behind what's available for Java?

The most obvious example to me is in Eclipse, you can right-click on a field in a Java class and choose to Rename it. It will then correctly update that field's name across the entire codebase. AFAIK this is impossible in C & C++ because they are such complicated languages to parse. Macros alone make this feature effectively impossible.

lallysingh3• 7 years ago

A C++ parser needs a semantic analyzer. The grammar is context sensitive. Eyeball a full year for an engineer to get one that's actually standards compliant. I've written a Java parser in two weeks in grad school while taking classes. You can easily use a parser generator (like ANTLR) because you have a context-free grammar.

millstone2• 7 years ago

Why shouldn't C++ templates be Turing-complete? Template metaprogramming is a great strength of C++. The language is gross but the result is quite powerful.

jchw• 7 years ago

I don't feel as though the article is making value judgements based on the conclusions. At least I didn’t see anything. The implicit conclusion may be “wow, C++ is ridiculous,” but to be honest I didn’t feel that kind of tone when reading this article.

That doesn’t mean it doesn’t matter though. The decidability of C++ grammar certainly matters to folks that are parsing C++ code.

GolDDranks• 7 years ago

The problem isn't that C++ templates are Turing complete. In fact, many similar macro systems are. The problem is that the result of template/macro expansion may affect the parsing of other places, so you can't parse the non-template parts separately from the Turing-complete parts.

saagarjha3• 7 years ago

I don’t think it was designed to be Turing-complete, so it’s a lot more annoying than it could be when you try to use it this way.

bluGill6• 7 years ago

The early template designers specified a limit of template recursion (16 IIRC) which they thought was more than deep enough for any real use, and would ensure that it wasn't Turing complete (truing complete of course requires no limit to template recursion depth). However soon after people started finding deeper template recursion depths were required for the real problems they wanted to solve.

rienbdj2• 7 years ago

Can we design a language (cpp-prime?) that is basically c++ but makes parsing easier? I'm thinking reduce the keyword reuse, use different symbols for multiplication and pointers etc. The code would be easy for c++ developers to read and converting between the two could be automatic. However, we would be able to build tooling for this new language much more easily. It would also compile quicker.

saagarjha3• 7 years ago

jstimpfle3• 7 years ago

C has its own parsing problems.

skocznymroczny• 7 years ago

In theory that's D. D was designed to be easier to parse than C++, for example, it uses Foo!Bar and Foo!(Bar, 4) template syntax rather than Foo<Bar> and Foo<Bar, 4>. On the other hand, it still uses templates and supports mixins (basically #define on steroids), so while it's easy to parse, large chunks of code don't exist until compile time so can't be indexed by IDEs perfectly.

pjmlp18• 7 years ago

And as much as I like their community, I feel it already lost its spotlight opportunity, due to their lack of manpower vs other languages offerings and continuous improvements.

Even if C++ is a little baroque, C++17 and now C++20 provide many of the D's benefits, while keeping all the libraries, and finally we are getting Java like C++'s tooling to just throw it away.

rienbdj2• 7 years ago

Not quite, because D brings many other things. I mean something that is equivalent to C++, with all of the same semantics, but a less ambiguous grammar.

pjmlp18• 7 years ago

It is called Ada.

choeger3• 7 years ago

Take an upvote!

xiphias23• 7 years ago

Rust seems to be the most successful zero-overhead language competitor to C++, though it's far not as mature as C++ yet.

jokoon3• 7 years ago

Rust has a high learning curve (borrowing, etc). Rust is a competitor to ADA, not C++. You can certainly ask developers to write things in rust instead, and even progressively rewrite codebase in rust since it's compatible with C++, but a language is about adopters, and ease of learning for beginners and students.

gpderetta6• 7 years ago

You could, but the incompatibility is not necessarily worth it.

There was some talk to take advantage of the transition to modules to be able to mark translation units as implementing a specific version of the standard (I think rust doese something similar) to allow for backward incompatibile Evolution of the language.

The committee doesn't seem to keen because they fear the language fragmenting and from a more practical point of views we will be still #including legacy code into new modules for at leas a decade (and I'm probably wildly optimistic).

gmueckl6• 7 years ago

With the glacial pace in which new language features are picked up by users of C++, I'd be surprised if modules have significant adoption in the first decade after C++20. It'll probably take at least two to three years to get stable support in most of the tooling and then anther couple of years until people start to believe that they are battle tested enough.

fanf2• 7 years ago

Damian Conway has a couple of papers from 1996 suggesting a better syntax for C++ http://users.monash.edu/~damian/papers/#Human_Factors_in_Pro...

oblio• 7 years ago

You know your proposal failed when there's people born back then that have just finished college this year and they still won't be able to use the changes you proposed ;-)

cmrdporcupine• 7 years ago

Oh, you haven't read this classic paper?

http://users.monash.edu/~damian/papers/PDF/ModestProposal.pd...

"We describe an alternative syntactic binding for C++. This new binding includes a completely redesigned declaration/definition syntaxfor types, functions and objects, a simplified template syntax, and changes to several problematic operators and control structures. Theresulting syntax is LALR(1) parsable and provides better consistency in the specification of similar constructs, better syntacticdifferentiation of dissimilar constructs, and greater overall readability of code."

etalian• 7 years ago

I wondered the same a while ago, and it turns out you can, in fact to test this hypothesis I ended up implementing such a language myself. The resulting syntax can express every construct from modern C++, is fully LALR(1) (no ambiguities and no vexing parses), has fewer keywords and is in general shorter than the equivalent C++ code, and once you know the syntax it is (subjectively) easier to read too (no spiral rule for example). Plus of course it can fully interoperate with existing C++.

Have been waiting to make it open source until I have finished writing the user manual (aiming for the end of this year), if that's interesting to you I post updates about it on twitter at cigmalang.

zamadatix• 7 years ago

Do you have any examples of the syntax?

BubRoss• 7 years ago

I say it all the time here, but there was a cool language called clay which was a great redesign of C with modern C++ techniques. It is not kept up anymore. It has an elegant design that, while not perfect, has a lot to offer.

http://claylabs.com/clay/

bluGill6• 7 years ago

There are been hundreds of attempts using a number of different ideas. The reason for C++ and not those alternatives is there is a lot of C++ code. If most of my code is C++ I don't gain anything from your new language as I spend most of my time maintaining old code. Even if I use your language for new code that means I constantly have to remember if I'm fixing a bug using C++ code rules or the new language rules. Some projects have successfully done this and eventually re-wrote everything. However others have not and the pain of a new language is a problem.

The other problems with that approach means C++ is everywhere.

I know that I can find a good compiler for C++ when I want to switch platforms. Will your new language support my new platform? Will your new language even exist? I've worked on a number of projects where the code was written in some language where the compiler vendor is out of business. This risk works against all new languages (some have overcome it, some have not).

With C++ I know if I need to hire more people I can hire experts to help out. If I choose your language do I have to pay my new employees to learn the language for the first few months? Learning my code (which is always hard no matter what the language) is already going to be a problem using something that nobody knows just makes it worse.

Will your language optimize well? C++ being everywhere means that compilers vendors have put a lot of effort into writing good optimizers. When performance matters C++ will often come in first because of this effort.

guenthert• 7 years ago

I read the suggestion as being about a new syntax for the existing language C++. For that you'd need 'only' a transpiler (and syntax high-lighter in your favorite support tools), quite possibly written in a readily available language, perhaps even C++. That should address your concerns regarding availability on various platforms and optimization. Your other concerns of course stand.

I, for one, find different languages with similar appearance needlessly confusing. I what the experience with different syntaxes for the same language would be.

_bxg12• 7 years ago

In other words it's the same network effects that weigh down any attempt at creating a new ecosystem. So if you're going to do that, you may as well start from scratch and do things better from the get-go.

mamcx• 7 years ago

Can we design a language (cpp-prime?)

I dislike, a lot, the C family of languages. I wish that the pascal or oCalm have "won". But being practical, we are stuck in this reality, so:

Is not "we". Is "them". I think only IF the core developers of that languages provide the "blessed" syntax it could actually catch up.

What I have wondered is why C/C++/JS not provide a "clean up" forward policy.

I think all involved are smart enough to see what is wrong with that langs (we always know what suck of what we build with time). Then say:

"This is $IDEAL-C we will targeting. This will fix this list of problems, and maybe this other list, BUT...

$IDEAL-C is a in-progress. Each change is iterative, and will deprecate in steps.

$BAD-C will be continued to be develop. $IDEAL-C transpile to $BAD-C. $IDEAL-C is another file extension. It will keep the same $IDEALS of $BAD-C.

Eventually, $IDEAL-C-STEP-1 will replace $BAD-C and become $BAD-C. And that until we reach $IDEAL-C! "

I know this look like what modern c/c++/js is doing, but the trouble is that that are additive changes. That mean triple work: Keep with $new, still have the problems of $old and maintain $both stuff at the time. What is lacking is doing subtractive changes and REMOVE what is wrong.

The key is transpiling, and not change the core tenants of the lang (ie: C stay as a razor edge).

The big problem, probably, is to not do drastic paradigm changes (ie: turn C in a functional lang), instead, clean the lang until is like what a good, idiomatic, modern developer of it will use.

I think is doable to make $IDEAL-C/C++/JS to be near identical to most developers and from a distance, not look different at all. Being progressive and in steps, provide auto-tranforming tools along the way and I think the community will move on.

I have see, partially, the idea applied with C#, so I think is doable?

P.D: Probably $IDEAL-C must only fix a very small list of stuff, initially. For example, lets say "Remove dangling IFs from C. END"

That its. This small-scope is I think, the key to make the experiment worthwhile.

alexhutcheson• 7 years ago

There's not really a need anymore, because LibClang[1] has solved the parsing problem. Historically it was really hard to write tooling (syntax highlighters, static analyzers, scripts to update build dependendencies, etc.) for C++ due to the difficulty of parsing the language. In the past several years, that has completely changed - you just call LibClang to handle the parsing for you, and work with the high-level abstractions provided by LibClang instead of munging the text yourself. There are lots of reasons to want to replace C++, but "it's hard to write a parser" is no longer a relevant one.

[1] https://clang.llvm.org/docs/Tooling.html

MauranKilom6• 7 years ago

You indeed no longer have to do the parsing, but I've been told that even the AST is a beast because the language is so complicated. Corner cases abound. (Note: Have not used libclang myself, but I look at clang ASTs on godbolt from time to time).

_bxg12• 7 years ago

C--

petters• 7 years ago

If it is not SomeType, then ::name is a typedef for int and the parse tree is declaring a pointer-to-int named x.

Doesn't this require "typename" at the beginning of the line?

MauranKilom6• 7 years ago

No, not in this instance. typename is needed to mark dependent names as types, but you can only have dependent (i.e. on a template parameter) names within templates.

choeger3• 7 years ago

This is one of the major issues with these languages that were initially designed by amateurs (I mean that in the positive sense, someone who does something because they care about it, and not because they are paid to do it). Often they simply did not see the long-term benefit of adhering to the limits of a "standard" architecture (i.e., context-free, unambiguous grammar, decidable static analysis (lookup!), multi-pass implementation). Yet these hackers still made a successful product. Now others must live with the consequences (for another example, have a look at javascript's scoping - I strongly suspect that it was a beginner's mistake that made it into production).

That particular syntactic ambiguity in C++ would have been trivial to fix (and could still be fixed today!), but no one really cares (and it would not be backwards compatible...).

Another example is the current situation with modules in C++. Instead of looking into the diverse ML implementations or even Java and trying to get the system right, the current discussion goes into wild compiler hacks just to avoid a simple limitation on filenames.

rightbyte• 7 years ago

If I remember correctly Stroustrup was working at Bell labs in the initial phases of the cpp design with a formal education in CS. Hardly an amateur? Inexperienced maybe.

smitty1e• 7 years ago

For a random sampling of the internet, being a critic of a complex system is trivial.

Offering an alternative that's an objective improvement, much less, on par with the status quo?

Not so much.

vkazanov• 7 years ago

"Formal education in CS" is not the same as, say, a degree related to programming languages or compilers.

pjmlp18• 7 years ago

The problems with modules is not getting the system right, the module proposal owners are well aware how to do it.

The problem was the politcal wars of tons of companies that don't want to let go of their in-house build systems based on translation units just to make use of modules.

So the end result is a compromise to make some of those big names happy.

einpoklum3• 7 years ago

Can you give a specific example of something which was "bent up" from its more appropriate standardization to placate those large companies?

bigcheesegs• 7 years ago

What do you mean by wild compiler hacks?

choeger3• 7 years ago

For instance the proposed solution where the compiler becomes a service that blocks compilation of a unit until it has seen all the module dependencies.

gpderetta6• 7 years ago

Yet these hackers still made a successful product.

Worse is, was and always will be better. It seems that's an unchanging law of software design. Practicality, getting things done and catering to user needs always beats purity, elegance and soundness.

TeMPOraL• 7 years ago

Less rosy view: sacrificing quality to increase adoption or decrease time to market always wins, so on the market, all software moves towards being the worst possible design that's still fit for purpose.

Alternative phrasing: the market runs on greedy optimization, which means a lot of value that could be gained is simply unreachable.

skohan• 7 years ago

In defense of amateurs, there is also something to be said for the ergonomics which come out of designing a language iteratively, against concrete use-cases, rather than from a purely theoretical direction.

amelius• 7 years ago

This is one of the major issues with these languages that were initially designed by amateurs (I mean that in the positive sense, someone who does something because they care about it, and not because they are paid to do it).

As opposed to a "professional" who is told by their boss to implement X before the end of the day?

yati• 7 years ago

Maybe interesting for people here is also the undecidability of parsing Perl: http://www.jeffreykegler.com/Home/perl-and-undecidability

einpoklum3• 7 years ago

Key point:

In practice, compilers limit template instantiation depth, so this is more of a theoretical problem than a practical one.

seanmcdirmid• 7 years ago

Magic numbers to limit undecidability are incredibly fragile. You think you have all the cases covered and another comes up, or the numbers need to be enlarged because of some reasonable code being rejected.

Better to have this problem in the parser than the type checker, at least.

einpoklum3• 7 years ago

There's no assumption that all the cases are covered up. Only some. The point is - in practice, don't try to go in too deep with templates.

john_moscow2• 7 years ago

As someone who had spent quite some time developing C++ refactoring tools, here's the most concise example of the problem:

  void func()
  {
    a < b , c > d;
  }

If a is a class template, the line in func() declares an instance of type "a<b, c>".

If a is a global variable, it describes an invocation of the "<" and ">" operators for 4 different variables.

Maintaining a parse tree of this is a massive mess, especially if func() is a template itself (and hence the meaning of a would change based on the instantiation).

fermenflo• 7 years ago

Thank you, as someone with no C++ background, this example makes the issue at hand much clearer.

waynecochran3• 7 years ago

I have never written code to translate templates. Do you actually build a syntax tree for the template itself? I always assumed you would just store a simpler representation of the template (e.g., just a string of lexemes) and only build syntax trees when the template is instantiated.

Of course you still need to "parse" the template when it is encountered but you have to do it without semantic information (e.g., you don't know what `a` will expand to until instantiation) -- I guess that is the problem.

It is funny that Lisp's defmacro doesn't have this problem because the code itself is a syntax tree.

MauranKilom6• 7 years ago

Either of your mentioned options for implementing template parsing were used by implementations when C++ was conceived (but before it became an ISO standard). Your "token string" approach is the route that Microsoft took with MSVC, whereas other compilers went with what later became standardized as "two phase lookup".

In short: Token stream alone is not enough. You need to decide whether T::A * b; is a pointer declaration or a multiplication immediately when you parse the template. If A is a dependent name (i.e. if T is a template parameter), it is assumed to be a variable (if that's not correct, the programmer must use typename or template).

MSVC has only recently completed their implementation of two-phase lookup, some twenty years after it was defined as the correct option in the ISO C++ standard. They have an excellent writeup here: https://devblogs.microsoft.com/cppblog/two-phase-name-lookup...

rozab• 7 years ago

Do Java and C# not have any problems like this?

waynecochran3• 7 years ago

Generics are not templates (i.e., not instantiated at compile time) so you avoid a lot of this mess.

fusilli_jerry2• 7 years ago

To be clear here though, you can always (*undecidably, but subject to practical constraints) fully parse a template definition into a parse tree, and that parse tree will not change for any instantiation.

In your example, 'a' is known at parse time to either be a type or a value even if it's a template parameter, so the statement will always parse one way or another. Of course, 'a' itself may change in type or value so the problem is still unwieldy and, probably key to your use case, requires knowledge of type information from a possibly far-off part of the translation unit.

john_moscow2• 7 years ago

Yeah, good luck with this one then:

  template <typename foo> void func()
  {
    foo::a < foo::b , foo::c > d;
  }

waynecochran3• 7 years ago

Might as well throw in the most vexing parse (https://en.wikipedia.org/wiki/Most_vexing_parse) with it:

    void func()
    {
       a < b , c > d();
    }

Parsing C++ is literally undecidable (2013)

Related Stories