Hacker News Reader

Comment by Denvercoder9 | Hacker News Reader

Maybe I'm missing something, but I don't see what's special about Carbon here. In C++ the compiler can also optimize pass-by-const-reference to pass-by-value, and they do. It just can't do it across an ABI boundary, but that should only be an issue with dynamic libraries, and Carbon has to follow the standard ABI there as well. Just make sure the compiler knows it doesn't have to follow the standard ABI for every symbol in your program, e.g. by enabling LTO and setting -fvisibility=hidden. See what happens `add` is made static: https://godbolt.org/z/KsqxP5Pxh (I also had to change foo() to avoid the compiler hardcoding the result of the single call in `add`).

View on HN

That optimization is quite fragile.

For example, try putting `puts("hello");` at the beginning of `add`. Now neither GCC nor Clang performs the optimization. Why? Because `puts` could theoretically modify the value behind the reference, so the value loaded is not necessarily the same as the value at the beginning of the function, which makes things more complicated, so both compilers give up.

As another example, GCC and Clang both perform the optimization within a translation unit, but if the function definition and the call are in different translation units, GCC doesn't perform the optimization even with LTO, and Clang doesn't perform it with ThinLTO (but does perform it with full LTO). Meanwhile, many projects don't compile with any form of LTO, which is a reasonable decision to improve compilation speed and predictability.

Neither compiler is smart enough to perform the optimization for virtual calls in almost any situation.

Carbon doesn't do the next logical optimization, and only converts a const& parameter to a value. If a function has parameter "const struct_with_two_floats&", and reads it, calls puts(), then reads it again, Carbon will not be willing to optimize out the "redundant" read.

It seems odd to break with C++ semantics for small parameters only; I'd expect it to either break for all parameters or no parameters.

EDIT: looks like Carbon is not doing this optimization for small values either. Its docs on parameters say, "This binding will be implemented using a pointer, unless it is legal to copy and copying is cheaper". And the OP link says, "the compiler is allowed to convert that to a T [copy] under the as-if rule." That seems like no extra optimization is enabled other than changing the function calling convention. And the "as-if" rule would require looking at the function body to check if the value could be changed (by things like puts()). I hope my understanding is wrong because this does not make sense. The word "legal" is ambiguous, so hopefully they mean something else!

I have been burned many times in the past by "the compiler is allowed to optimise something away".

You write your code assuming such an optimisation will happen, and for some reason, the compiler decides not to apply the optimisation. Perhaps the wind was blowing in the wrong direction, or it was in a bad mood, or you forgot to specify -fvisiblitly=hidden.

The exciting part here is that it happens by default, and the compiler is required to do it. I don't have to think about it, and the ABI automatically does the thing best for performance.

I don't think that fvisibility=hidden on its own is sufficient, it does not allow the compiler to break the call abi as the function could still be called from another .o (which will only know the mangled name of the original function). You need fvisibility=internal (or maybe fno-semantic-interposition but I'm not sure if it's enough).

I think you just need LTO if you want full optimization without regards for the ABI constraints

>Maybe I'm missing something, but I don't see what's special about Carbon here.

It's nothing really out of the ordinary ... also that particular optimization is meager in practice (on the order of 1%?). I know everything improvement adds up, but the author talks about it as if it was a game changer. I like the enthusiasm, though :D.

The "ABI now or never" paper suggests somewhere on the order of 5-10%, and that's without considering the escape pessimization. Especially with the rapid expansion of smart pointer usage (and for good reason!).

Given the major selling point of C/C++ is performance, that's not an insignificant amount.

I think the alias analysis “pro” is overblown, it’s UB to take the address of a parameter via any mechanism other than explicitly taking the address - which a compiler obviously sees, and because it’s UB the compiler optimizes is free to assume no one is taking the address. Then for any parameters that are passed by reference the compiler has to assume there are other references so there’s no gain.

Honestly the only thing that really stood out as nice is the default pass by word-sized value, in the context of templates - it’s a thing that is achievable in C++, but requires a bunch of obnoxious additional templates that aren’t even part of the standard library so everyone ends up reimplementing the same cruft. Happily I believe there’s a proposal to add this exact functionality.

I also loathe their desire to listen to the BNF maximalists insistence on not having any “ambiguity” from <>s. I’m sorry it’s clearly parseable, and <>s are the standard token for decades. Switching to []s doesn’t make it less conceptually ambiguous, if anything it makes it more ambiguous to a human reader. The only people who don’t want <>s are PLT academics obsessed with forcing their dragon book idea of what a grammar should be. You can’t argue you’re doing it because the ambiguity in a grammar or lexer is bad, because then you would also drop infix operators.

Then in carbon the more reasonable adoption of pascal’s : notation for typing a variable or parameter removes the most common case of the supposedly terrible ambiguity anyway.

> it’s UB to take the address of a parameter via any mechanism other than explicitly taking the address - which a compiler obviously sees, and because it’s UB the compiler optimizes is free to assume no one is taking the address.

I don't get that: can you express in C++ a code that "take the address of a parameter via any mechanism other than explicitly taking the address"?

Consider this C code (also "works" if compiled as C++):

    int main(void) {
        int x = 0;
        int arr[1];
        int *p = arr + 1;
        *p = 42;
        return x;
    }

On a lot of systems (e.g., https://godbolt.org/z/jYqM8TT3Y), it just so happens that `x` is right above `arr` on the stack, so that code will return 42. But that code is absolutely UB.

The more general name for this concept is "pointer provenance". Basically, you can't pull pointer values out of thin air; you have to derive them from operations rooted at taking the address of something within the same allocation.

That's a buffer overflow. The optimizer doesn't need to reason about changing the behavior of such things.

The point is that on systems where that code returns 42, `p` has the exact same value it would if I did `int *p = &x;` instead, but not the same provenance.

And because C++ says "one past the end" pointers are a thing, both these pointers can exist.

As written p is a one-past-the-end pointer into object arr, but the address one past the end of arr may well be the address of x. If pointers are just addresses, these pointers are the same... right?

Neither C nor C++ currently actually explain how this works for their "abstract machine" in the standards documents. The reality is that your C++ compilers (and any non-toy C compilers) have pointer provenance because it's a nightmare to optimise C programs without, but since it isn't documented anywhere (my understanding is that C23 might fix this for C by taking a TS and an equivalent fix via P2318 could land in C++ 26) it's difficult to say if you ever find bugs in their behaviour.

> And because C++ says "one past the end" pointers are a thing, both these pointers can exist.

While one-past-the-end pointers are allowed to exist, they are not allowed to be dereferenced.

> these pointers are the same... right

The entire point of provenance is that even though their numerical values are the same, they are not the same.

> Neither C nor C++ currently actually explain how this works for their "abstract machine" in the standards documents.

While it isn't mentioned explicitly, it can be inferred from other things that the standard does say. The compiler authors didn't just make it up.

> it can be inferred from other things that the standard does say. The compiler authors didn't just make it up.

They didn't "just make it up" but well, here's (a draft of) TS 6010 explaining where it comes from, alas it's not "inferred from other things that the standard does say" but rather riffing on a phrase from a discussion about a defect report...

""In a committee discussion from 2004 concerning DR260, WG14 confirmed the concept of provenance of pointers, introduced as means to track and distinguish pointer values that represent storage instances with same address but non-overlapping lifetimes. Implementations started to use that concept, in optimisations relying on provenance-based alias analysis, without it ever being clearly or formally defined, and without it being integrated consistently with the rest of the C standard.""

TS 6010 will, some day, actually define how this works. Well, it will define how it should work, and assuming compiler vendors can be bothered to implement TS 6010 then it becomes how it actually works.

In TS 6010 (which again, is not how your C or C++ compiler works today, and in the best case won't be how your C++ compiler is required to work until at least 2027 or so) the rules go roughly like this:

* If you've got an actual pointer to a living object via some legitimate means, e.g. you used the & operator in C, that works

* If you try to make pointers from somewhere else, e.g. doing arithmetic on pointers that point to a different object, this only works if you've previously done some operation which might cause non-pointer stuff to be aware of this pointer, e.g. you cast a pointer to an integral type or you type-punned a pointer and then looked at the bytes

* However, the compiler is obliged to give you the benefit of the doubt about pointer types, if it's possible you knew how to make a Doodad* with this address in it, then the fact that you also knew how to make a Foo* with the same address doesn't matter, your program is allowed to make a Doodad* not a Foo* if it wants

Thus, your example up thread is still Undefined Behaviour under TS 6010, because you've got no reason to believe the memory layout is the way it actually was. But if you use some type punning hack to get the address of x into that pointer instead, TS 6010 says that works and is not Undefined Behaviour.

C/C++ language lawyering (which I did as a hobbyist a few years ago) reminds me a lot of SCOTUS and US constitution debates these days.

That’s the point - it’s UB to go off the end of an array, or more generally to dereference a pointer outside of the bounds of the target object (yes, buffer+buffer_length is a valid pointer for the purpose of comparisons, but dereferencing it would be UB).

However in practice you can do this, and walk the stack to find the parameters or what have you, and then you’ve got a pointer to a parameter without the compiler being aware of it. But this is all explicitly UB, so it’s ok for the compiler to be unaware of it, and it’s free to do whatever codegen it wants given the assumption that UB can never happen.

Imagine the parameter is passed on the stack, I can take the address of a local variable (which in general forces it to be on the stack), I can then walk up the stack from that address to where the parameter is.

This is undefined behavior. Because it is UB that compiler is allowed to assume it cannot happen. Therefore I have the address of a parameter, and can pass that to a closure or whatever, and the parameter has escaped, but the compiler doesn't know.

More importantly by definition the compiler does not need to know, because a program that does that is no longer well defined.

> I also loathe their desire to listen to the BNF maximalists insistence on not having any “ambiguity” from

Odd that you put ambiguity in quotes. I guess it's not real ambiguity then.

Ivory tower academics, as you see them, actually care about stuff because it affects you. I've heard too many times the knee-jerk response of "it's just theory" as if that actually meant anything. Try implementing it yourself and you'd start to understand that little bits of crap typically don't add, they multiply (Edit: and I'm hurting from exactly this right now), so don't diss theory until you've (ironically) had some practice with it.

I put ambiguity in quotes, because the only people who claim it makes things ambiguous are theoreticians - who you appear to have decided I think of as being "ivory tower" which we'll address in a bit - who favor a theoretical definition of what a grammar should be, and disregard (1) how people understand language, programming or otherwise, (2) insist on a mathematical definition of grammars, and grammar classes, that doesn't reflect reality. Insisting on that mathematical definition of what a grammar is, is the thing that creates the ambiguity that is so despised here, and (3) want to prioritize the ease of parsing for a dumb parser over the reality in which a parser has actual contextual information.

It's also well understood that for (2) this theoretical ambiguity is not actually a real problem for humans - the things for which reading is actually important - because otherwise they would not allow infix operators, which are ambiguous according to their definition, but much like languages that they have chosen to define as ambiguous, infix is not.

In that theoretical model of grammars we define the power of different classes of parsers to go something like LL < LALR < LR < GLR. This is how the mathematical theory of grammars goes, and everything beyond LL is basically required to be based on some PDA. The ambiguities in the PDA's state transitions are what "prove" a grammar to be ambiguous. Further LL parsers are considered the least powerful, and incapable of parsing the majority of grammars, especially those that belong to "real" languages.

The problem is that this model of grammars is arbitrarily restricted, and many (I would guess most real world) parsers for "real" languages are not any of these classes, which is certainly odd given the completeness indicated by theory. That's because this restricted definition of what a parser is says that most real world programming languages require an LALR parser, and in reality the big ones likely need LR or GLR.

In the real world, what is used could probably be classed as LL(infinity), which is impossible according to the theoretical parser classes in use. The reason that we use these impossible LL(infinity) parsers, is because they are human writable, and human understandable, and also vastly faster than the state machines LALR parsers (think bison and yacc IIRC), even more so for LR, and slower again for GLR (even if you can get away with a tomita parser, if you could find a generator for one). Additionally all the non LL parsers can only be reasonably implemented via state machine, and beyond trivial examples, a human is not going to be able to write the state transition tables, let alone modify it in future.

That means using a tool to generate the parser for you, and this really is the heart of the theoretical definition being used, to be a "real" parser, you need to be able to make a tool that will read a BNF grammar, and have it produce a program that will be able to take some text, and then, accumulating no state beyond a stack and its current state, produce an AST.

I have never been shown any justification for why this makes a grammar more understandable, it is simply stated as fact that being easier for a machine to parse means being easier for a human. The contra to that is that most people seem find infix much easier to understand than the non ambiguous pre- and post-fix notations. You could argue that's familiarity, but I would say "so what?" that people can find the "ambiguous" grammar easier to understand than the non ambiguous one indicates that the claim of "easier for machine == easier for people" to not stand up.

Anyway that giant wall of text is my position, and that is why I don't accept "<> for generics is ambiguous" as the sole justification for a change from the root language this is meant to be a replacement for. If they were creating their own language then sure, they could go ham and make the least ambiguous language that they liked (but lisp I think has technically already done that), but that is not what Carbon is doing.

Finally (and so the Great Wall of text continues) on your "ivory tower academic" accusation, I disagree. Academic CS is hugely valuable, and having been in CS academia for many years I feel I am allowed to express my disagreement with some of it.

If credential waving is needed, for academics: my masters is in programming language theory, and I was the TA for among other things my university's courses on programming language theory, parsing, etc. In industry I've worked on clang for many years, and for parsing specifically I wrote the javascript parser in javascriptcore.

I understand parsing, and I understand the PLT subfield of CS.

My frustration with academic PLT is more that by confining the definitions of what is a valid grammar, or what is a real parser, we don't see any real research into into those aspects of PLT and in my experience it seems like an area where we just treat the dragon book as being the definition of everything that matters. Then we turn around say anything that doesn't fit neatly in that definition must be bad, and can be ignored.

>because otherwise they would not allow infix operators, which are ambiguous according to their definition

This is not true, infix operators can be easily encoded in BNF as a series of rules, each rule recognizing expressions unique to it as well as all the expressions of higher precedence. The following for example is a grammar that parses the four arithmetic operations with the usual precedence.

Expr ::= Addition

Addition ::= Term ((PLUS | MINUS) Term)*

Term ::= Prim ((MUL | DIV) Prim)*

Prim ::= NUM | OPEN_PAREN Expr CLOSE_PAREN

>The problem is that this model of grammars is arbitrarily restricted

It is restricted, but not arbitarily so. There is a very natural constraint that explains why Parsing Theory doesn't like ad-hoc parsers in the way you hate so much : the parser shouldn't depend on the "content" of the stream. The easiest way to see what I mean by this is to demonstrate how one violation of it works : C++'s ambiguous "X Y();" is either a function prototype or a variable declaration, depending on whether Y is a valid type name. This is extremely ugly to me, a parser shouldn't accumulate type information while it's parsing, even if it's as trivial as a set of type names. This is an entirely different concern that should be left to an entirely different module of the compiler. C++'s syntax is full to the brim of such ugly corners, the standard doesn't even bother to specify a binding BNF on the implementations!

Compiler Theory settled on an interface design where the parser must be able to output a concrete syntax tree from a stream without relying on global ad-hoc state like a table of special names or whatever. You framing it as "accumulating no state beyond a stack and its current state" is being unfair, it would be like framing the point of local variables as just a limiting thing that we invented arbitarily : Yes, that's the entire point, No, it's not arbitary, it's intentionally limiting, because the resulting design is easier to understand and simply more elegant.

>lisp I think has technically already done that

There is a middle ground between lisp's austere and misguided "F*k You, Why Should Parsing Be Hard Just To Please Your Eyes?" syntactical philosophy, and between C++'s and Perl's "Lol, Grammars Are For Weaklings". Complex syntax is good, it automates the tedious tree-layout that is the text of lisp programs, you don't need to repetitively state the precedence and hierarchy of code elements, the parser infers some of them for you. However, as in all "The Machine Infers Things" situations, we have to be careful with the rules of inference. We don't want the machine to infer counter-intuitive things, or fail to infer entirely. CFGs formalism is an elegant tradeoff.

>we don't see any real research into into those aspects of PLT

It might be the other way around, that allowing arbitary ad-hoc state in the parser results in too ugly a formalism or no interesting formalism at all, therefore people settled on disallowing it. It's like how theoretical mechanics famously hates friction, it isn't arbitary or born of prejudice, it's just that friction is too ugly and hard to yield an elegant and concise theory, therefore people just pretend that it doesn't exist.

On the surface, it doesn't seem hard to try and formalize some of the real-world parser hacks into the grammar formalism. For example, C++'s "this should be parsed as X unless the name is in a certain set then it should be parsed as Y" doesn't appear too wild a constraint type to encode in a formal grammar, my suspicion is that if you try to do it you will either discover that (a) it doesn't actually change any of the implication of traditional theory, and therefore it is just a "sugar" over traditional constraints : cool, but it technically doesn't tell us anything new (b) it significantly changes the implications and guarantees of theory, to the point that it's not an elegant or beautiful theory anymore. You can introduce control flow into prolog, but why bother ? it wouldn't be prolog anymore.

I don't want to imply that Academia is all-seeing or all-wise, but it is a very powerful novelty-rewarding machine, if there is Anything theoretically interesting to be gained from formalizing parsing hacks, I find it very hard to believe it hasn't been studied in 65+ years of grinding on parser theory and formal grammars.

>I would guess most real world parsers for "real" languages are not any of these classes

I find this too strong a claim. I would bet money it's false for anything but C, C++, Perl, Ruby, and let's say PHP just to be safe. Mention any language that isn't on this blacklist, and I bet I can find BNF-like description of the grammar that tells you perfectly well how to obtain a CST from text, which means they are CFG.

> Odd that you put ambiguity in quotes. I guess it's not real ambiguity then.

Because a parser is never really ambiguous is it? Nobody writes a parser that has a random decision on which rule to take.

In parser theory there is such a thing as an ambiguous grammar. Parser generators detect such a grammar and never produce an actual parser for it. So in a sense most parser that you actually use don't have ambiguous grammars by definition. That said, you could have a manually written parser that thinks it implements an "ambiguous grammar", but in reality chose an deterministic (even if possibly arbitrary l) resolution of the ambiguity.

It's still ok talk about the grammar as being ambiguous no matter what a purported implementation of such grammar is deterministic (because it ultimately does not implement the actual grammar)

I guess I don't understand why we use languages for writing grammars that let you express ambiguity in the first place.

I think parser generators were a mistake.

I agree it's a pain. Could you share some alternatives?

Imperative parsing - PEGs or just plain old recursive descent.

Ok that's about the "parser generator" part. But what about the "formal grammar" part?

Do you really want your language to be defined by a particular imperative parser implementation?

I'm asking because I do have a practical problem: my team has a hand crafted parser for a language. It should follow a spec written in EBNF. That spec could be ambiguous it's not because an automated tool checks that that EBNF grammar is not ambiguous.

I find the ability to document the grammar using something that everybody understands (BNF and variants) to be very useful. Yet, your comment seems to imply that since it allows ambiguous grammars we should be using it.

EDIT: our grammar is implemented by three different parsers, written in two programming languages.

> Do you really want your language to be defined by a particular imperative parser implementation?

Yes please. The code defines completely and unambiguously how the language is parsed.

If the code only handled parsing the grammar, I'd be with you, but more than half of a parser deals with what to do with what you just parsed which may be quite different between the various implementations of the grammar

for someone who is the founder of TruffleRuby (I've checked, and you are <https://docs.oracle.com/en/graalvm/enterprise/21/docs/refere...>), you sure have made some very odd comments and I don't know what to make of them.

> you sure have made some very odd comments and I don't know what to make of them

Well they’re from practical experience aren’t they.

Well, first you don't seem to understand what 'ambiguity' means in the context of parsing "Nobody writes a parser that has a random decision..." which is weird. It's a very establish meaning here.

Then you say "I guess I don't understand why we use languages for writing grammars that let you express ambiguity in the first place" without any suggestions, or even if this is possible, or if it is, whether the resulting language might be too constrained to be useful (interesting question though. Edit: even context-free grammars have ambiguity, eg. the regexp "aa" is legal but ambiguous for sentence "aaa").

Then "I think parser generators were a mistake" which is surreal. If you've ever had the tedious misfortune to write one manually, you know how much faster it is to have the computer do that work.

So I am thrown a bit here.

If you choose to specify your language using a class of grammar which permits ambiguity, then you have to resolve that ambiguity.

If instead you choose to specify your language using a class of grammar which does not permit ambiguity, then you don't have to resolve it because it never existed.

That's the point.

The suggestion is to either specify your language using a formal grammar which does not permit ambiguity, or to specify your language imperatively, using a reference parser.

I've written many parsers, both using parser generators and manually. I'd choose to write one manually. In fact, I'm currently looking at a project at work right now to take a generated parser and to re-write it manually because it's easier to work with.

That's a pretty mainstream opinion amongst professionals in the industry - not sure why you think it's surreal or why it's throwing you.

> If you choose to specify your language using a class of grammar which permits ambiguity, then you have to resolve that ambiguity.

I added an edit after which you may not have seen:

   even context-free grammars have ambiguity, eg. the regexp "aa" is legal but ambiguous for sentence "aaa"

So what grammar can you suggest that's even weaker than context-free (to make expressions of ambiguity impossible) and still useful?

> I'd choose to write one manually

Matter of taste I guess.

> So what grammar can you suggest that's even weaker than context-free (to make expressions of ambiguity impossible) and still useful?

It doesn’t need to be weak. For example use a Parsing Expression Grammar.

PEGs are ambiguous, just that that's resolved by rule ordering. From the wiki page (https://en.wikipedia.org/wiki/Parsing_expression_grammar#Amb...)

"A PEG parser generator will resolve unintended ambiguities earliest-match-first, which may be arbitrary and lead to surprising parses"

> PEGs are ambiguous

You're misunderstanding the rhetoric there - they're unambiguous by construction because they deterministically resolve earliest-match-first - a well-defined rule.

It's impossible to write an ambiguous PEG. Any grammar you write in a PEG is never ambiguous. A grammar you write using a CFG can be ambiguous.

As your own link says "Unlike CFGs, PEGs cannot be ambiguous".

Or read Ford's original paper https://bford.info/pub/lang/peg.pdf - they solve "the ambiguity problem by not introducing ambiguity in the first place".

(I wrote a much-cited thesis on PEGs and issues such as ambiguity in precedence parsing - I'm not just talking off the top of my head here.)

You're the expert, thanks for the pointers!

> which a compiler obviously sees

Not if it's in a different compilation unit, it doesn't. Or if it's just not inlining the function for some reason, then it probably also doesn't. Which is why Carbon's restriction here is so useful and practical.

Ok, I'm willing to accept be wrong here. My interpretation of what I read is that Carbon is disallowing taking the address of a parameter. Very specifically:

    void f(int i) { &i; /* disallowed */ }

I think that's a trivial case and is hopefully obviously easy to detect, and I know we're considering relevance to escaping which this doesn't do, but it seems that taking the address is explicitly disallowed regardless of use. Anyway given the many references to references, lets do

   void g(int &i) { &i; /* disallowed once more */ }

To me this seems no harder to detect, but this does seem like a case where banning taking the address /could/ impact things. But I can't see what the win is.

I'm assuming its a different TU or something else that prevents inter procedural optimization. Could you give some examples where this allows performance wins?

That is what Carbon prevents, yes. And, inside a particular function that does it, it's obviously easy to detect. But in the calling function, it's not easy to detect.

If in boo.cpp you call your g() function which is in foo.cpp, how does the compiler know if it's taking the address or not? It's in a different compilation unit. All the compiler knows at that point is there's a function 'g' that takes an int by reference. It has no idea what 'g' does with it, it doesn't even know where 'g' is - that won't be known until link time. So the compiler is forced to be conservative and allow for 'g' to do anything that C++ allows - which includes stashing the reference somewhere or const_cast'ing away a const& into a mutable reference.

This is where Carbon's win comes in. Since that behavior just isn't allowed, the compiler doesn't have to be conservative. It doesn't need to somehow see into different compilation units to perform helpful optimizations (critically for const unique_ptr& or const shared_ptr&)

Why not just use parentheses, because, you know, templates are just AOT-functions behind the scenes! Try to come up with an example where this syntax is worse than (angle or square) brackets...

Reply on news.ycombinator.com