4 ms·

I think it was an unintended consequence of the wording chosen by the ANSI C89 committee. The reality of pre-ANSI C was that if you wrote ‘+’, the expectation w

by kps 9y ago

I think it was an unintended consequence of the wording chosen by the ANSI C89 committee. The reality of pre-ANSI C was that if you wrote ‘+’, the expectation was that you'd get the target machine's ‘add’ instruction, no more and no less. It might overflow, it might not; it might crash or hang your machine on overflow or trap values — but that is all your problem, not the language's or compiler's. I worked on a commercial compiler at the time, and at the time, people took ‘undefined behaviour’ as acknowledgement that sometimes the effect of generated code could be surprising to people unfamiliar with the particular system, not as encouragement to screw the programmer.

simias 9y ago
That's a good explanation for invalid memory accesses and divisions by zero but I'm not aware of many architectures where addition overflow traps (it can trap on MIPS but there's an other instruction that simply wraps around). That being said I don't have an encyclopedic knowledge of instruction sets. I could be wrong though, after all compilers back then were a lot less clever than now so maybe they couldn't really make use of this information. I'd be curious to get a first hand testimony as to why certain UB exist in the first place.
- pjmlp 9y ago
  As someone that got introduced to C via SmallC and Turbo C 2.0 for MS-DOS, and avid reader of "The C User's Journal", one of the reasons was that ANSI C89 was supposed to standardize existing variants outside UNIX. No compiler vendor back then wanted to give up on their own specific deviations, given their existing customer base, proprietary OSes and extensions. So many of those vendor specific features got tucked away into implementation specific and UB buckets.
- tom_mellior 9y ago
  This is not first hand, but the commonly given reason for undefined signed integer overflow is that it allows for mathematically correct reasoning: x < x + 1 is true for all x. Or rather, the compiler may assume that it is true and optimize accordingly, since the programmer is trusted to avoid the undefined overflowing case.
  - iainmerrick 9y ago
    "Mathematically correct" doesn't seem like the right way to think about it, since the whole problem is that it isn't correct!
    - tom_mellior 9y ago
      Yes, but it wouldn't be correct the other way round either. Wraparound on signed overflow is a well-defined operation on CPUs, but it is nonsensical. In almost no computation will it give a result that is meaningful in the context of what the program is trying to do. If you try to compute the average of two positive numbers as (a + b) / 2 but get a negative result, it would be of no use if this were "well-defined". So from the point of view of a C compiler that exploits undefined signed overflow, if your code could overflow, it was probably already buggy, and you should have fixed it. (One problem with this line of reasoning is that it kind of also applies to unsigned numbers, but there C goes the other way.)
- spc476 9y ago
  The VAX. There's a bit in the condition codes register that indicates if overflow traps or not. Then there's the matter if ((char )0) causes a trap or not; on systems without a MMU, it probably won't trap [1]. It's differences like overflow and memory references that cause most of the UB you see in C. [1] On Linux, you can map a page to address 0. But that you can, doesn't mean you should.
bbatha 9y ago
I've never really understood why this couldn't be slotted in as "implementation defined behavior". `add` has a well defined meaning on every platform just because it differs shouldn't give the compiler license to change the meaning of my program for that platform. It should however platform specific optimizations based on overflow, etc. Could somebody provide me with an example of truly undefinable behavior? (Perhaps data races?)
- jcranmer 9y ago
  When C was first written, it wasn't necessarily possible on some architectures to get traps to trigger at the exact instruction on some hardware. Thus, any potentially-trapping instruction had to be undefined instead of implementation-defined.
- tom_mellior 9y ago
  > truly undefinable behavior Memory corruption is pretty undefinable. Imagine writing data through a wild pointer. The program might segfault immediately, or compute a wrong result but not crash, or crash at an arbitrary later point, or delete all your files, or... It makes no sense to try to enumerate all that might happen, so this cannot really be implementation defined (where the implementation must document what will happen).
  - adrianratnapala 9y ago
    Right, but it is not the plus operation that does this. You can reserve undefined behaviour to things like "write to a bad pointer". Then a particular ABI could say "if your pointer overflows (by a our system specific meaning of overlow) then you have a bad pointer". Merely doing a pointer increment just gets you implementation-defined behaviour. The UB only happens if you plough on. Such a setup wouldn't do much to save us from pointer bugs. But it would make optimizers more predictable.
_kst_ 9y ago
Which "add" instruction? Integer (signed or unsigned), floating-point? How big are the operands? What if the operands are of different types? What if the CPU doesn't have an "add" instruction? Or, perhaps more plausibly, doesn't have a divide instruction? C code defines run-time behavior (or fails to define it in some cases), not CPU instruction sequences. If you want assembly language, you know where to find it.
- Sprocklem 9y ago
  > Which "add" instruction? I believe the intention was whichever one matched the types. If you're adding 2 16-bit ints, it would use the 16-bit add instruction, if it existed or a larger one (then, in this case, cast it back down to 16-bits when appropriate). If it's a floating-point type, it would get a floating point add. [Edit: The compilers usually wouldn't provide a 16-bit int type if they didn't have the instructions to deal with it.] > What if the operands are of different types? C89 has well defined promotion rules. You'd convert the operands appropriately, then use the equivalent add. > What if the CPU doesn't have an "add" instruction? Then it would probably end up as a function call to a system specific function. Either way, it wouldn't do anything particularly unexpected for the system. > If you want assembly language, you know where to find it. C was originally just used as a high-level assembly language. I suspect people found it easier to reason about, even if it basically used the system instruction's behaviour.
gumby 9y ago
Also C was designed for PDP-7/PDP-11 style machines with 8-bit bytes, 16-bit words and the like. It was ported to a variety of other architectures which had to make assumptions and adaptations. These live in UB. One somewhat unfortunate side effect of the pervasiveness of C and Unix-style machines is that it encouraged CPUs to optimize for C rather than the opposite way around. The use of GPUs for non-graphics programming is a welcome improvement.
- kps 9y ago
  Point of order: the PDP-7 had 18-bit words (and no smaller addressable unit).
  - gumby 9y ago
    Thanks for the correction.

by kps 9y ago

simias 9y ago

That's a good explanation for invalid memory accesses and divisions by zero but I'm not aware of many architectures where addition overflow traps (it can trap on MIPS but there's an other instruction that simply wraps around). That being said I don't have an encyclopedic knowledge of instruction sets. I could be wrong though, after all compilers back then were a lot less clever than now so maybe they couldn't really make use of this information. I'd be curious to get a first hand testimony as to why certain UB exist in the first place.

pjmlp 9y ago
As someone that got introduced to C via SmallC and Turbo C 2.0 for MS-DOS, and avid reader of "The C User's Journal", one of the reasons was that ANSI C89 was supposed to standardize existing variants outside UNIX. No compiler vendor back then wanted to give up on their own specific deviations, given their existing customer base, proprietary OSes and extensions. So many of those vendor specific features got tucked away into implementation specific and UB buckets.
tom_mellior 9y ago
This is not first hand, but the commonly given reason for undefined signed integer overflow is that it allows for mathematically correct reasoning: x < x + 1 is true for all x. Or rather, the compiler may assume that it is true and optimize accordingly, since the programmer is trusted to avoid the undefined overflowing case.
- iainmerrick 9y ago
  "Mathematically correct" doesn't seem like the right way to think about it, since the whole problem is that it isn't correct!
  - tom_mellior 9y ago
    Yes, but it wouldn't be correct the other way round either. Wraparound on signed overflow is a well-defined operation on CPUs, but it is nonsensical. In almost no computation will it give a result that is meaningful in the context of what the program is trying to do. If you try to compute the average of two positive numbers as (a + b) / 2 but get a negative result, it would be of no use if this were "well-defined". So from the point of view of a C compiler that exploits undefined signed overflow, if your code could overflow, it was probably already buggy, and you should have fixed it. (One problem with this line of reasoning is that it kind of also applies to unsigned numbers, but there C goes the other way.)
spc476 9y ago
The VAX. There's a bit in the condition codes register that indicates if overflow traps or not. Then there's the matter if ((char )0) causes a trap or not; on systems without a MMU, it probably won't trap [1]. It's differences like overflow and memory references that cause most of the UB you see in C. [1] On Linux, you can map a page to address 0. But that you can, doesn't mean you should.

bbatha 9y ago

I've never really understood why this couldn't be slotted in as "implementation defined behavior". `add` has a well defined meaning on every platform just because it differs shouldn't give the compiler license to change the meaning of my program for that platform. It should however platform specific optimizations based on overflow, etc. Could somebody provide me with an example of truly undefinable behavior? (Perhaps data races?)

jcranmer 9y ago
When C was first written, it wasn't necessarily possible on some architectures to get traps to trigger at the exact instruction on some hardware. Thus, any potentially-trapping instruction had to be undefined instead of implementation-defined.
tom_mellior 9y ago
> truly undefinable behavior Memory corruption is pretty undefinable. Imagine writing data through a wild pointer. The program might segfault immediately, or compute a wrong result but not crash, or crash at an arbitrary later point, or delete all your files, or... It makes no sense to try to enumerate all that might happen, so this cannot really be implementation defined (where the implementation must document what will happen).
- adrianratnapala 9y ago
  Right, but it is not the plus operation that does this. You can reserve undefined behaviour to things like "write to a bad pointer". Then a particular ABI could say "if your pointer overflows (by a our system specific meaning of overlow) then you have a bad pointer". Merely doing a pointer increment just gets you implementation-defined behaviour. The UB only happens if you plough on. Such a setup wouldn't do much to save us from pointer bugs. But it would make optimizers more predictable.

_kst_ 9y ago

Which "add" instruction? Integer (signed or unsigned), floating-point? How big are the operands? What if the operands are of different types? What if the CPU doesn't have an "add" instruction? Or, perhaps more plausibly, doesn't have a divide instruction? C code defines run-time behavior (or fails to define it in some cases), not CPU instruction sequences. If you want assembly language, you know where to find it.

Sprocklem 9y ago
> Which "add" instruction? I believe the intention was whichever one matched the types. If you're adding 2 16-bit ints, it would use the 16-bit add instruction, if it existed or a larger one (then, in this case, cast it back down to 16-bits when appropriate). If it's a floating-point type, it would get a floating point add. [Edit: The compilers usually wouldn't provide a 16-bit int type if they didn't have the instructions to deal with it.] > What if the operands are of different types? C89 has well defined promotion rules. You'd convert the operands appropriately, then use the equivalent add. > What if the CPU doesn't have an "add" instruction? Then it would probably end up as a function call to a system specific function. Either way, it wouldn't do anything particularly unexpected for the system. > If you want assembly language, you know where to find it. C was originally just used as a high-level assembly language. I suspect people found it easier to reason about, even if it basically used the system instruction's behaviour.

gumby 9y ago

Also C was designed for PDP-7/PDP-11 style machines with 8-bit bytes, 16-bit words and the like. It was ported to a variety of other architectures which had to make assumptions and adaptations. These live in UB. One somewhat unfortunate side effect of the pervasiveness of C and Unix-style machines is that it encouraged CPUs to optimize for C rather than the opposite way around. The use of GPUs for non-graphics programming is a welcome improvement.

kps 9y ago
Point of order: the PDP-7 had 18-bit words (and no smaller addressable unit).
- gumby 9y ago
  Thanks for the correction.