3 ms·

"all it does is perform optimizations that are correct under the extra assumption that there is no Undefined Behavior." How did the compiler writers reach the

by somat 4y ago

"all it does is perform optimizations that are correct under the extra assumption that there is no Undefined Behavior." How did the compiler writers reach the point where they were able to read "undefined behavior" as "does not happen" rather than "specification left this undefined so that the compiler can define it" I don't think there is anything wrong with undefined behavior, I do however expect the compiler documentationto have an extensive section on stuff undefined by the specification. for example: when a signed integer would exceeds the maximum value this compiler just lets it go and it does whatever the underlying hardware would do. on amd64 this will overflow to a negative value.

mort96 4y ago
The specification has a separate concept for "specification left this undefined so that the compiler can define it": implementation-defined behaviour.
jcranmer 4y ago
There's a note in the C99 rationale explaining how compilers can use undefined behavior (specifically, with regards to signed overflow) to perform certain optimizations (specifically, reassociation of integer addition). I'd go back to C89, but the documents before the work effort to make C99 are not available on the WG14 website. > I do however expect the compiler documentation to have an extensive section on stuff undefined by the specification. There is an entire section of the C specification that lists every single undefined behavior. What more do you want?
- kps 4y ago
  https://www.lysator.liu.se/c/rat/title.html https://www.lysator.liu.se/c/rat/title.html has the C89 Rationale. “The terms unspecified behavior, undefined behavior, and implementation-defined behavior are used to categorize the result of writing programs whose properties the Standard does not, or cannot, completely describe. […] Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose.”
  - jcranmer 4y ago
    For the commentary on undefined behavior, I find N790 (https://www9.open-std.org/jtc1/sc22/wg14/www/docs/n790.htm https://www9.open-std.org/jtc1/sc22/wg14/www/docs/n790.htm) to be a better assessment of what the C committee thinks about undefined behavior: First consider the term "unspecified behavior". Most commentators on the Standard are of the opinion that this has the following properties: (1) There are a number of possible courses of actions, or the behavior is one that generates a result and then has a number of possible results. (2) The implementation can make any of the available choices, and can make different choices at different places or times. (3) The implementation need not document its choices. (4) No matter what choice the implementation makes, it cannot affect anything outside the range of that choice. If a value has to be chosen, it must be a valid value for that type. Property number 4 is the interesting one: it is usually taken to mean that the implementation cannot generate a spurious signal, branch to a random place in the code, or choose a trap representation. All of these, of course, are valid "undefined behavior".
- deleted 4y ago
  [deleted]
- somat 4y ago
  My thought process, note that I am not a compiler writer, runs along these lines. undefined behavior is valid code(it is not a syntax error), it has to do some thing, that thing should be documented, if the spec does not want to document it, then the implementation should. don't make the assumption that because it is undefined it will never happen.
  - jcranmer 4y ago
    It is not practical to constrain what happens in the case of undefined behavior, even if you discard the potential of the compiler to optimize assuming undefined behavior can't happen. For example, what memory has and hasn't been written when a trap occurs isn't. Hell, on some architectures (hi Alpha!), an unknown amount of code will continue executing after the trapping instruction before the trap handler gets around to being invoked. Similar insanity is also in play when data races are involved (if data races are undefined, you can pretend that all code is sequentially consistent and there is a nice, simple, global total order of memory accesses. Data races cause memory accesses to not even be a consistent partial order.) Or take pointer provenance. Writing to an unknown memory location may cause printf in another thread to instead call system("rm -rf /"). How the hell is one supposed to document the potential behavior of undefined behavior when undefined behavior is so inherently unconstrainable, and "undefined behavior can do anything" is considered unacceptable documentation?
  - pklausler 4y ago
    What you're talking about is "implementation defined" behavior, which is a distinct concept from "undefined behavior".
- fsckboy 4y ago
  >> "specification left this undefined so that the compiler can define it" >> I do however expect the compiler documentation to have an extensive section on stuff undefined by the specification and he should have said which is defined by the compiler so your response is not to what he meant > There is an entire section of the C specification that lists every single undefined behavior. What more do you want? a similar section wrt the compiler he is using, because he's talking about "behavior undefined by C but defined by implementation"
  - jcranmer 4y ago
    > a similar section wrt the compiler he is using, because he's talking about "behavior undefined by C but defined by implementation" That's called implementation-defined behavior. And there is a section in C that lists all the implementation-defined behavior, and all the compilers are supposed to document what they define the implementation-defined behavior to be (glares at Clang).
deleted 4y ago
[deleted]
kps 4y ago
I've said before¹ that I'm convinced that ‘undefined behavior’ was an actual mistake by the C89 committee that would not have been accepted if anyone at the time had realized the future implications. It is precisely “a license for the compiler to undertake aggressive optimizations that are completely legal by the committee's rules, but make hash of apparently safe programs” (as dmr said of `noalias`²). ¹ https://news.ycombinator.com/item?id=30024867 https://news.ycombinator.com/item?id=30024867 ² https://www.lysator.liu.se/c/dmr-on-noalias.html https://www.lysator.liu.se/c/dmr-on-noalias.html
- rramadass 4y ago
  > was an actual mistake by the C89 committee Agreed. Apparently the first compiler written by Dennis Ritchie had no UB (i have not been able to find more info. on this). See also the article published in IEEE : Dealing With C's Original Sin by Chris Hathhorn and Grigore Rosu.
jessermeyer 4y ago
Compiler, Language, and Software engineer people do not often overlap, and so neither do their constraints. Over time you see opposing drift occurring, where language people end up designing languages nice for language development, software engineers design software nice for software development, and so on.. Consider what is nice for compiler development but is not nice for software engineering.
tialaramex 4y ago
> How did the compiler writers reach the point where they were able to read "undefined behavior" as "does not happen" rather than "specification left this undefined so that the compiler can define it" If they want the compiler to define it, the specification can say so, and on several things it says exactly that. This is what the phrase "implementation defined" is for. The example of Undefined Behaviour which is most commonly given in this sort of argument - and you chose the same - is integer overflow. Why can't it just do what I meant? And you're right, the language could have chosen to do what you meant here and it did not. There are lots of options and you don't like the option C chose. I'll talk about that in a moment. But more generally, Undefined Behaviour isn't at all like that. What happens if I cast my local telephone number to an integer pointer and then dereference the pointer ? Today that's Undefined Behaviour in C, but if we think that means "the compiler documentation should say" then what should it say? "It does whatever the underlying hardware would do" is a circular definition, this is a computer program, what the hardware does is whatever we told it to do. So maybe you say well, it emits this particular machine code. Congratulations now your "compiler documentation" reads like the source code for the compiler and your users still don't know the answer because guess what, the CPU vendor can't do any better with that either. Now, back to those integer overflows. We can do a whole bunch of things here, and they all have different consequences. WUFFS says this is forbidden, you get a compiler error. If your code can overflow, that's a bad WUFFS function it does not compile. Several languages including Python just don't have overflow. Your integer types just get bigger, this may be annoyingly slow in some cases, but like actual integers from grade school you won't just accidentally make one that's too big by mistake and something weird happens. We could wrap the integers as you seem to prefer. This is what Rust's Wrapping<> types always do and several languages provide alternate arithmetic operators to request wrapping We could saturate the integers, which means they stop at the edge of the overflow. This is what Rust's Saturating<> types do, and again I believe some languages have saturating operators (at least addition and multiplication anyway) We could make arithmetic operations all "checked" so that they can fail if there would be overflow. The check could be in the form of a soft error, or it could cause something more dramatic like Rust's panic. Or like C we can just say we refuse to define this, don't do it.
kevincox 4y ago
Rather than look at it as "does not happen" it may be helpful to think of "if this does happen anything is correct". So you can then split the codepaths into parts where the compiler is strictly specified in what it has to do (defined behaviour) and parts where anything is "correct". Of course the most optimal solution is to just produce the best code you can for the first category, because what code also happens to be "correct" for the second category. Of course this is equivalent to "does not happen" but may make more sense as to why the compiler acts this way.

by somat 4y ago

mort96 4y ago

The specification has a separate concept for "specification left this undefined so that the compiler can define it": implementation-defined behaviour.

jcranmer 4y ago

There's a note in the C99 rationale explaining how compilers can use undefined behavior (specifically, with regards to signed overflow) to perform certain optimizations (specifically, reassociation of integer addition). I'd go back to C89, but the documents before the work effort to make C99 are not available on the WG14 website. > I do however expect the compiler documentation to have an extensive section on stuff undefined by the specification. There is an entire section of the C specification that lists every single undefined behavior. What more do you want?

kps 4y ago
https://www.lysator.liu.se/c/rat/title.html https://www.lysator.liu.se/c/rat/title.html has the C89 Rationale. “The terms unspecified behavior, undefined behavior, and implementation-defined behavior are used to categorize the result of writing programs whose properties the Standard does not, or cannot, completely describe. […] Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose.”
- jcranmer 4y ago
  For the commentary on undefined behavior, I find N790 (https://www9.open-std.org/jtc1/sc22/wg14/www/docs/n790.htm https://www9.open-std.org/jtc1/sc22/wg14/www/docs/n790.htm) to be a better assessment of what the C committee thinks about undefined behavior: First consider the term "unspecified behavior". Most commentators on the Standard are of the opinion that this has the following properties: (1) There are a number of possible courses of actions, or the behavior is one that generates a result and then has a number of possible results. (2) The implementation can make any of the available choices, and can make different choices at different places or times. (3) The implementation need not document its choices. (4) No matter what choice the implementation makes, it cannot affect anything outside the range of that choice. If a value has to be chosen, it must be a valid value for that type. Property number 4 is the interesting one: it is usually taken to mean that the implementation cannot generate a spurious signal, branch to a random place in the code, or choose a trap representation. All of these, of course, are valid "undefined behavior".
deleted 4y ago
[deleted]
somat 4y ago
My thought process, note that I am not a compiler writer, runs along these lines. undefined behavior is valid code(it is not a syntax error), it has to do some thing, that thing should be documented, if the spec does not want to document it, then the implementation should. don't make the assumption that because it is undefined it will never happen.
- jcranmer 4y ago
  It is not practical to constrain what happens in the case of undefined behavior, even if you discard the potential of the compiler to optimize assuming undefined behavior can't happen. For example, what memory has and hasn't been written when a trap occurs isn't. Hell, on some architectures (hi Alpha!), an unknown amount of code will continue executing after the trapping instruction before the trap handler gets around to being invoked. Similar insanity is also in play when data races are involved (if data races are undefined, you can pretend that all code is sequentially consistent and there is a nice, simple, global total order of memory accesses. Data races cause memory accesses to not even be a consistent partial order.) Or take pointer provenance. Writing to an unknown memory location may cause printf in another thread to instead call system("rm -rf /"). How the hell is one supposed to document the potential behavior of undefined behavior when undefined behavior is so inherently unconstrainable, and "undefined behavior can do anything" is considered unacceptable documentation?
- pklausler 4y ago
  What you're talking about is "implementation defined" behavior, which is a distinct concept from "undefined behavior".
fsckboy 4y ago
>> "specification left this undefined so that the compiler can define it" >> I do however expect the compiler documentation to have an extensive section on stuff undefined by the specification and he should have said which is defined by the compiler so your response is not to what he meant > There is an entire section of the C specification that lists every single undefined behavior. What more do you want? a similar section wrt the compiler he is using, because he's talking about "behavior undefined by C but defined by implementation"
- jcranmer 4y ago
  > a similar section wrt the compiler he is using, because he's talking about "behavior undefined by C but defined by implementation" That's called implementation-defined behavior. And there is a section in C that lists all the implementation-defined behavior, and all the compilers are supposed to document what they define the implementation-defined behavior to be (glares at Clang).

deleted 4y ago

[deleted]

kps 4y ago

I've said before¹ that I'm convinced that ‘undefined behavior’ was an actual mistake by the C89 committee that would not have been accepted if anyone at the time had realized the future implications. It is precisely “a license for the compiler to undertake aggressive optimizations that are completely legal by the committee's rules, but make hash of apparently safe programs” (as dmr said of `noalias`²). ¹ https://news.ycombinator.com/item?id=30024867 https://news.ycombinator.com/item?id=30024867 ² https://www.lysator.liu.se/c/dmr-on-noalias.html https://www.lysator.liu.se/c/dmr-on-noalias.html

rramadass 4y ago
> was an actual mistake by the C89 committee Agreed. Apparently the first compiler written by Dennis Ritchie had no UB (i have not been able to find more info. on this). See also the article published in IEEE : Dealing With C's Original Sin by Chris Hathhorn and Grigore Rosu.

jessermeyer 4y ago

Compiler, Language, and Software engineer people do not often overlap, and so neither do their constraints. Over time you see opposing drift occurring, where language people end up designing languages nice for language development, software engineers design software nice for software development, and so on.. Consider what is nice for compiler development but is not nice for software engineering.

tialaramex 4y ago

> How did the compiler writers reach the point where they were able to read "undefined behavior" as "does not happen" rather than "specification left this undefined so that the compiler can define it" If they want the compiler to define it, the specification can say so, and on several things it says exactly that. This is what the phrase "implementation defined" is for. The example of Undefined Behaviour which is most commonly given in this sort of argument - and you chose the same - is integer overflow. Why can't it just do what I meant? And you're right, the language could have chosen to do what you meant here and it did not. There are lots of options and you don't like the option C chose. I'll talk about that in a moment. But more generally, Undefined Behaviour isn't at all like that. What happens if I cast my local telephone number to an integer pointer and then dereference the pointer ? Today that's Undefined Behaviour in C, but if we think that means "the compiler documentation should say" then what should it say? "It does whatever the underlying hardware would do" is a circular definition, this is a computer program, what the hardware does is whatever we told it to do. So maybe you say well, it emits this particular machine code. Congratulations now your "compiler documentation" reads like the source code for the compiler and your users still don't know the answer because guess what, the CPU vendor can't do any better with that either. Now, back to those integer overflows. We can do a whole bunch of things here, and they all have different consequences. WUFFS says this is forbidden, you get a compiler error. If your code can overflow, that's a bad WUFFS function it does not compile. Several languages including Python just don't have overflow. Your integer types just get bigger, this may be annoyingly slow in some cases, but like actual integers from grade school you won't just accidentally make one that's too big by mistake and something weird happens. We could wrap the integers as you seem to prefer. This is what Rust's Wrapping<> types always do and several languages provide alternate arithmetic operators to request wrapping We could saturate the integers, which means they stop at the edge of the overflow. This is what Rust's Saturating<> types do, and again I believe some languages have saturating operators (at least addition and multiplication anyway) We could make arithmetic operations all "checked" so that they can fail if there would be overflow. The check could be in the form of a soft error, or it could cause something more dramatic like Rust's panic. Or like C we can just say we refuse to define this, don't do it.

kevincox 4y ago

Rather than look at it as "does not happen" it may be helpful to think of "if this does happen anything is correct". So you can then split the codepaths into parts where the compiler is strictly specified in what it has to do (defined behaviour) and parts where anything is "correct". Of course the most optimal solution is to just produce the best code you can for the first category, because what code also happens to be "correct" for the second category. Of course this is equivalent to "does not happen" but may make more sense as to why the compiler acts this way.