Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Parsing C++ is literally undecidable (2013)

blog.reverberate.org

Post reply on HN
Print view View original

131–140 of 146 posts

Re: Parsing C++ is literally undecidable (2013)

#131

Post by biggestdecision »

pjmlp wrote: post #105
biggestdecision wrote: post #95

Earlier quoted context omitted.

Swift's GC is really a lot closer to modern C++ style memory management than the other languages you mentioned. If you use RAII & shared_ptr in C++ you are using the exact same techniques that Swift's "GC" uses.

And as proven by the ixy paper, quite slow versus tracing GCs.

I assume this is what you are talking about? https://www.net.in.tum.de/fileadmin/bibtex/publications/pape...

>A total of 76% of the CPU time is spent incrementing and decrementing reference counters.

ouch

Re: Parsing C++ is literally undecidable (2013)

#132

Post by V_Terranova_Jr »

thesuperbigfrog wrote: post #130
V_Terranova_Jr wrote: post #128

Earlier quoted context omitted.

Ada has been on the way out, at least in recent U.S. DoD flight system developments (and likely NASA as well) for a long time. I don't see this trend reverting any time soon. On the other hand, we can, and I hope will, move to much more rigorous approaches, such as the use of Rust, for flight software implementations. As you say, Rust was not specifically designed to compete with Ada, but accomplishes a number of sim…

>> Ada has been on the way out, at least in recent U.S. DoD flight system developments (and likely NASA as well) for a long time. I don't see this trend reverting any time soon. Yeah, C++ has been working out great on the F-35. >> On the other hand, we can, and I hope will, move to much more rigorous approaches, such as the use of Rust, for flight software implementations. Competition is good and more choices for bui…

>> Yeah, C++ has been working out great on the F-35.

The number of scary C and C++ architectures flying currently is quite troubling.

While DoD is coming to grips with the fact most aerospace primes take a 1990s approach to software development, other than mostly in research pockets, DoD is still not recognizing the impact of language choice. The late 90s push to embrace COTS threw a lot of baby out with the bathwater.

>> Competition is good and more choices for building avionics systems are welcome. I don't know of any DO-178C certified Rust implementations, but we need them.

One of the impediments to improvement actually is certification. Certification uses a lot of labor and paperwork-intensive proxies for code quality and configuration control that should be revisited in light of modern methods that can assure correctness-by-construction. I'm also not sure any major aerospace prime will generate demand pull for a certified Rust implementation without it being mandated in some fashion by a government regulator or customer (which I personally would not be opposed to).

>> Part of the issue is that high-integrity, hard real-time embedded systems are their own niche in terms of requirements. Java and C# are widely-used programming languages with hundreds of millions of lines of code deployed in business-critical production environments and yet both are unsuitable for avionics environments

Once running atop an RTOS of sufficient quality, what niche language features do you think would be required for avionics, given the widespread use of C and C++ there already? I can understand not wanting to run on garbage-collected runtimes like Java and C#, but once memory management has the determinism of something like Rust, what other functionality do you think is missing?

Re: Parsing C++ is literally undecidable (2013)

#133

Post by pjmlp »

biggestdecision wrote: post #131
pjmlp wrote: post #105

Earlier quoted context omitted.

And as proven by the ixy paper, quite slow versus tracing GCs.

I assume this is what you are talking about? https://www.net.in.tum.de/fileadmin/bibtex/publications/pape... >A total of 76% of the CPU time is spent incrementing and decrementing reference counters. ouch

Yep, that one.

Re: Parsing C++ is literally undecidable (2013)

#134

Post by Too »

bluGill wrote: post #93
coldpie wrote: post #81

Earlier quoted context omitted.

> 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 th…

Java had it first (by at least 10 years), but C++ IDEs do the same. Clang not being designed to make it impossible to access the AST has made this feasible for most IDEs. There are still cases where it cannot be done (macros), but in many cases it can be done now.

You can't reliably refactor members in a template because T might be any class. Example: template void foo(T bar) { bar.buzz(); }

Try renaming buzz in this context, you really don't know how many other classes that need the same rename. In Java and C# you know because of generic constraints and IDEs can leverage this information. Concepts in c++20 should hopefully solve this.

Re: Parsing C++ is literally undecidable (2013)

#135

Post by pjmlp »

carlmr wrote: post #41
jokoon wrote: post #32

Earlier quoted context omitted.

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.

Counterpoint, when you write C++ you need to think about borrowing without the compiler telling you when you're making a mistake. Rust in that sense is easier than C++.

Only if you are not using a recent version of clang or VC++.

CppCon 2019: “Lifetime analysis for everyone”

https://www.youtube.com/watch?v=d67kfSnhbpA

It is available to play on Godbolt.

Re: Parsing C++ is literally undecidable (2013)

#136

Post by eru »

MauranKilom wrote: post #108
eru wrote: post #43

Earlier quoted context omitted.

> By far, most code doesn't allocate or free (and that's a good thing). Depends on the code you write. If, like in C++, non-stack memory management is painful, programmers tend to react like you suggest. In pure-by-default languages, you are creating new and destroying old objects all the time. (At least conceptually. A sufficiently smart compiler can eliminate most of that.)

Obviously depends on the use case, but since C++11 there is little to no pain involved in manual non-stack memory management. You clearly express the ownership semantics through things like std::unique_ptr and std::shared_ptr and if those make sense then everything works (minus problems like circular shared_ptr references, which exists in similar forms with GCs).

> (minus problems like circular shared_ptr references, which exists in similar forms with GCs)

Most GC can deal with circular references just fine?

Re: Parsing C++ is literally undecidable (2013)

#137

Post by MauranKilom »

eru wrote: post #136
MauranKilom wrote: post #108

Earlier quoted context omitted.

Obviously depends on the use case, but since C++11 there is little to no pain involved in manual non-stack memory management. You clearly express the ownership semantics through things like std::unique_ptr and std::shared_ptr and if those make sense then everything works (minus problems like circular shared_ptr references, which exists in similar forms with GCs).

> (minus problems like circular shared_ptr references, which exists in similar forms with GCs) Most GC can deal with circular references just fine?

Yeah, I didn't elaborate this enough (because it wasn't really the main point). When I said "similar" I meant "things holding onto things they should no longer be holding onto", not circular referencing in particular.

I realize that the kind of bug that leads to effective memory leaks with GCs has its own equivalent in manual memory management, but my overall point was that neither manual memory management nor GCs make you immune to leaks from badly designed or incorrectly implemented data structures. Each takes some aspect(s) of pain away.

Re: Parsing C++ is literally undecidable (2013)

#138

Post by MauranKilom »

waynecochran wrote: post #113
john_moscow wrote: post #100

As someone who had spent quite some time developing C++ refactoring tools, here's the most concise example of the problem: void func() { a d; } If a is a class template, the line in func() declares an instance of type "a ". If a is a global variable, it describes an invocation of the " " operators for 4 different variables. Maintaining a parse tree of this is a massive mess, especially if func() is a template itself…

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…

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

Re: Parsing C++ is literally undecidable (2013)

#139

Post by MauranKilom »

john_moscow wrote: post #120
fusilli_jerry wrote: post #117

Earlier quoted context omitted.

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…

Yeah, good luck with this one then: template void func() { foo::a d; }

Two-phase lookup requires this to be interpreted at template parse time as two comparisons and a comma operator, because a, b and c are dependent names (which, without further disambiguation with the typename or template keyword, are taken to be variables). This has been the case since the first ISO C++ standard (published in 1998).

Re: Parsing C++ is literally undecidable (2013)

#140

Post by perl4ever »

xiphias2 wrote: post #122
jokoon wrote: post #32

Earlier quoted context omitted.

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.

I wanted to understand why Ada is not used in systems programming if it's so great, and found the answer: ,,Ada developers either use a garbage collector, or they avoid freeing memory entirely and design the whole application as a finite state machine (both of which are possible in Rust, too, but the point is you don’t have to). Of course, Ada has range-checked arithmetic, which Rust doesn’t have (it needs const gene…

I didn't remember Ada having a garbage collector...

https://stackoverflow.com/questions/1691059/why-doesnt-ada-h...

Post reply on HN