4 ms·

Am I right in thinking that all undefined behavior must have a defined outcome in the implementation? Otherwise, I would guess that "proven correct" is only rel

Am I right in thinking that all undefined behavior must have a defined outcome in the implementation? Otherwise, I would guess that "proven correct" is only relevant for the compilation of programs that cannot enter UB territory. Given Moonchild's comment about all optimizations retaining semantics, this leaves me wondering what happens with some of the more notorious UB-with-optimization footguns, such as the elimination of a chunk of code because an unsigned variable cannot go negative. If such optimizations are performed by this compiler, does the "all optimizations retain semantics" rule mean that this code elimination would be applied before any optimization (to avoid there being a difference between the before and after semantics)? I am not saying that would be wrong, but I am curious about how these cases are handled.

tialaramex 5y ago
No. There's "Implementation Defined" behaviour where the compiler vendor is expected to explain what their compiler (and maybe operating system, hardware architecture, site installation) does in these cases. But "Undefined Behaviour" says that anything might happen. The reason to be so vague is that this frees the compiler to conclude that it can ignore this scenario. Whatever it does can't be wrong for Undefined Behaviour, so, it needn't consider any cases that trigger this. This makes it actually practical to produce reasonable object code for good programs that don't actually have Undefined Behaviour. The practical alternative is that you can just outlaw a huge amount of stuff so that there's no problem for the compiler. For example you could say OK, my language refuses to admit that pointers are just an integer which happens to correspond to a machine address. Anything that depends on that is just removed from the language entirely. But now you can't do a lot of clever tricks, so, you abandon C and move to a language where you can get your job done. Rust's approach is to put all that stuff that - if you get it wrong - is horribly unsafe and require its "unsafe" keyword. So in one sense it's actually two very similar languages, the safe language which you would have abandoned for a lower-level language because it can't get what you need done, and the low-level language where if you screw up everything catches fire. This would not have been practical in the 1970s but it is practical today. The semantics of undefined behaviour are exactly the same before and after any transformation of the program, because any behaviour is a semantically reasonable implementation of your program. You screwed up, not the compiler.
- tialaramex 5y ago
  Two real world examples I built: 1. In Rust I have a type named OnewayLess that insists it has equivalence (implements the Eq trait) and is totally ordered (implements the Ord trait), yet, in defiance of reason, it also insists that any of its members are less than anything when asked, even themselves. This is incoherent nonsense, but it's safe under Rust. Rust promises that even though I am clearly a lunatic who doesn't understand what equivalence and ordering mean, my programs do not have Undefined Behaviour. If I try to sort a vector of this type, that won't reformat my hard disk, or more practically change unrelated data in the program. However, it very well might take forever (the sort keeps looking for the smallest object and never finds it) or run out of memory (the sort might try to keep references to the infinitely many "lesser" items from the vector) and that isn't undefined, that's just consequences of my reprehensible type design. 2. In our RDF storage engine written in C an older version contained a mistake in which an array of temporary pointers might get partially overwritten. In C there is no safety checking, these are raw memory addresses, and dereferencing a pointer that now might be garbage is Undefined Behaviour so all bets are off. It could do absolutely anything. If the compiler is instead required to somehow check, when referencing them, that these are still good pointers, the performance of many C programs is ruined, even though our bug was in unrelated code.
  - mannykannot 5y ago
    Sure, but this does not seem to provide any insight into how, in this compiler, the preservation of semantics under optimization plays out in optimizations which assume the program will never attempt to perform UB.
    - tialaramex 5y ago
      I feel like that's very well covered already when I wrote: "The semantics of undefined behaviour are exactly the same before and after any transformation of the program" [emphasis added] I think you've got this idea that Undefined Behaviour somehow means that the behaviour is defined but is being kept secret from you. It isn't. The behaviour really is Undefined. Doing further transformations to it is therefore always harmless.
bregma 5y ago
Dividing by zero is undefined behaviour. It's fairly straightforward to provide a proof, given a definition of division by zero, that 1 = 0. It's often done in first-year introduction to algebra classes. It would be correct, then for a compiler to substitute the value 1 everywhere the programmer used the value 0 (or NULL, or '\0') and still produce a valid program with the same behaviour because 1 and 0 have been proven to be equivalent. So no, you are not right in thinking all implementations must define undefined behaviour. Undefined is undefined. C code containing undefined behaviour is not valid C code and the compiler to only required to produce correct output when the input is valid C code.
- mannykannot 5y ago
  That is a fair point about divide-by-zero [1], but the very post I was replying to gave an example of where this compiler does say explicitly what happens in one case of what falls under undefined behavior in the C standards. To clarify, what I am interested in here is the interaction of C-standard UB with any guarantee this compiler may give with regard to semantics preservation under optimization. [1] In reality, the hardware will do something, and deterministically in every case that I am aware of, when the divide operation is invoked with zero as the divisor. Computer division is not an exact implementation of mathematical division.
  - bregma 5y ago
    > To clarify, what I am interested in here is the interaction of C-standard UB with any guarantee this compiler may give with regard to semantics preservation under optimization. To clarify my point: undefined behaviour has any semantics you might want it to have. Anything and everything is semantically correct even under optimization. Even if the compiler says it will do one thing and then does another: it's correct either way. The computer may "do something" with division by zero. Or the compiler might completely elide the code and replace it with a picture of a teapot before it even gets as far as hitting a register in anger. It's still valid, semantically, because you're dividing by zero from which you can prove anything and everything.
- a1369209993 5y ago

tialaramex 5y ago

No. There's "Implementation Defined" behaviour where the compiler vendor is expected to explain what their compiler (and maybe operating system, hardware architecture, site installation) does in these cases. But "Undefined Behaviour" says that anything might happen. The reason to be so vague is that this frees the compiler to conclude that it can ignore this scenario. Whatever it does can't be wrong for Undefined Behaviour, so, it needn't consider any cases that trigger this. This makes it actually practical to produce reasonable object code for good programs that don't actually have Undefined Behaviour. The practical alternative is that you can just outlaw a huge amount of stuff so that there's no problem for the compiler. For example you could say OK, my language refuses to admit that pointers are just an integer which happens to correspond to a machine address. Anything that depends on that is just removed from the language entirely. But now you can't do a lot of clever tricks, so, you abandon C and move to a language where you can get your job done. Rust's approach is to put all that stuff that - if you get it wrong - is horribly unsafe and require its "unsafe" keyword. So in one sense it's actually two very similar languages, the safe language which you would have abandoned for a lower-level language because it can't get what you need done, and the low-level language where if you screw up everything catches fire. This would not have been practical in the 1970s but it is practical today. The semantics of undefined behaviour are exactly the same before and after any transformation of the program, because any behaviour is a semantically reasonable implementation of your program. You screwed up, not the compiler.

tialaramex 5y ago
Two real world examples I built: 1. In Rust I have a type named OnewayLess that insists it has equivalence (implements the Eq trait) and is totally ordered (implements the Ord trait), yet, in defiance of reason, it also insists that any of its members are less than anything when asked, even themselves. This is incoherent nonsense, but it's safe under Rust. Rust promises that even though I am clearly a lunatic who doesn't understand what equivalence and ordering mean, my programs do not have Undefined Behaviour. If I try to sort a vector of this type, that won't reformat my hard disk, or more practically change unrelated data in the program. However, it very well might take forever (the sort keeps looking for the smallest object and never finds it) or run out of memory (the sort might try to keep references to the infinitely many "lesser" items from the vector) and that isn't undefined, that's just consequences of my reprehensible type design. 2. In our RDF storage engine written in C an older version contained a mistake in which an array of temporary pointers might get partially overwritten. In C there is no safety checking, these are raw memory addresses, and dereferencing a pointer that now might be garbage is Undefined Behaviour so all bets are off. It could do absolutely anything. If the compiler is instead required to somehow check, when referencing them, that these are still good pointers, the performance of many C programs is ruined, even though our bug was in unrelated code.
- mannykannot 5y ago
  Sure, but this does not seem to provide any insight into how, in this compiler, the preservation of semantics under optimization plays out in optimizations which assume the program will never attempt to perform UB.
  - tialaramex 5y ago
    I feel like that's very well covered already when I wrote: "The semantics of undefined behaviour are exactly the same before and after any transformation of the program" [emphasis added] I think you've got this idea that Undefined Behaviour somehow means that the behaviour is defined but is being kept secret from you. It isn't. The behaviour really is Undefined. Doing further transformations to it is therefore always harmless.

bregma 5y ago

Dividing by zero is undefined behaviour. It's fairly straightforward to provide a proof, given a definition of division by zero, that 1 = 0. It's often done in first-year introduction to algebra classes. It would be correct, then for a compiler to substitute the value 1 everywhere the programmer used the value 0 (or NULL, or '\0') and still produce a valid program with the same behaviour because 1 and 0 have been proven to be equivalent. So no, you are not right in thinking all implementations must define undefined behaviour. Undefined is undefined. C code containing undefined behaviour is not valid C code and the compiler to only required to produce correct output when the input is valid C code.

mannykannot 5y ago
That is a fair point about divide-by-zero [1], but the very post I was replying to gave an example of where this compiler does say explicitly what happens in one case of what falls under undefined behavior in the C standards. To clarify, what I am interested in here is the interaction of C-standard UB with any guarantee this compiler may give with regard to semantics preservation under optimization. [1] In reality, the hardware will do something, and deterministically in every case that I am aware of, when the divide operation is invoked with zero as the divisor. Computer division is not an exact implementation of mathematical division.
- bregma 5y ago
  > To clarify, what I am interested in here is the interaction of C-standard UB with any guarantee this compiler may give with regard to semantics preservation under optimization. To clarify my point: undefined behaviour has any semantics you might want it to have. Anything and everything is semantically correct even under optimization. Even if the compiler says it will do one thing and then does another: it's correct either way. The computer may "do something" with division by zero. Or the compiler might completely elide the code and replace it with a picture of a teapot before it even gets as far as hitting a register in anger. It's still valid, semantically, because you're dividing by zero from which you can prove anything and everything.
a1369209993 5y ago