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

Defining the Undefinedness of C (2015) [pdf]

fsl.cs.illinois.edu

Post reply on HN
Print view View original

81–90 of 91 posts

Re: Defining the Undefinedness of C (2015) [pdf]

#81

Post by dragonwriter »

Retra wrote: post #80
gh02t wrote: post #60

Earlier quoted context omitted.

> Undefined means : the compiler can omit this case and assume it never happens. That's not the whole picture though. The standard actually says that anything can happen in undefined cases. > However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the fir…

Anything can happen because the compiler will assume it doesn't happen. "Undefined behavior" essentially means, "If you try to do this, you have written a program that is not C, and you should not be handing it to a C compiler expecting it to do anything correctly ." If you were to try to write a program that accurately detected whether the given input is a meaningful C program, you'd have to solve the Halting Proble…

No, undefined behavior is still valid C (if it wasn't, it would be an invalid construct, not a valid conatruct with UB.)

It's just C whose actual behavior is unspecified (and, because the standard is outright perverse, makes the entire program's behavior undefined) by the standard and, if you are especially lucky, explicitly defined by the particular C implementation. But maybe not even then.

Re: Defining the Undefinedness of C (2015) [pdf]

#82

Post by iainmerrick »

tom_mellior wrote: post #61
simias wrote: post #27

Earlier quoted context omitted.

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…

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.

"Mathematically correct" doesn't seem like the right way to think about it, since the whole problem is that it isn't correct!

Re: Defining the Undefinedness of C (2015) [pdf]

#84

Post by gumby »

kps wrote: post #66
gumby wrote: post #56

Earlier quoted context omitted.

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

Point of order: the PDP-7 had 18-bit words (and no smaller addressable unit).

Thanks for the correction.

Re: Defining the Undefinedness of C (2015) [pdf]

#85

Post by adrianratnapala »

tom_mellior wrote: post #62
bbatha wrote: post #28

Earlier quoted context omitted.

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? (Perhap…

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

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.

Re: Defining the Undefinedness of C (2015) [pdf]

#86

Post by tom_mellior »

iainmerrick wrote: post #82
tom_mellior wrote: post #61

Earlier quoted context omitted.

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.

"Mathematically correct" doesn't seem like the right way to think about it, since the whole problem is that it isn't correct!

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

Re: Defining the Undefinedness of C (2015) [pdf]

#87

Post by littlestymaar »

gh02t wrote: post #60
littlestymaar wrote: post #25

Earlier quoted context omitted.

Undefined means : the compiler can omit this case and assume it never happens. Take integer overflow for instance: an implementation-defined behavior means in case of overflow the compiler can either wrap, crash, or have a saturation at max value. Undefined behavior means the compiler can assume it doesn't happen and optimize with this information in mind. For instance, the following code : for(i = 0; i With the unde…

> Undefined means : the compiler can omit this case and assume it never happens. That's not the whole picture though. The standard actually says that anything can happen in undefined cases. > However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the fir…

> > Undefined means : the compiler can omit this case and assume it never happens.

> That's not the whole picture though. The standard actually says that anything can happen in undefined cases.

Well, that's right the standard says the compiler can do anything they want, including erasing all data from your hard drive or summoning a demon in your nose [1], but in practice I've never seen any compiler attempt such things.

What compilers usually do with UB is assuming it will never happen and use this invariant as an optimization hint.

[1] : http://catb.org/jargon/html/N/nasal-demons.html

Re: Defining the Undefinedness of C (2015) [pdf]

#88

Post by littlestymaar »

nayuki wrote: post #78
iainmerrick wrote: post #37

Earlier quoted context omitted.

That's a good example, thanks! Reminds me of the Java binary search bug: https://research.googleblog.com/2006/06/extra-extra-read-all... I think the correct code here would be something like: for (j = i; j Or something like that. Obviously that's rather awkward, with the risk of a sneaky off-by-one bug. (Edit to add: heh, just noticed I'm assuming max+1 won't overflow!) It would be great to have a C-like language tha…

The silver lining in that Java bug is that it is guaranteed to compute the same wrong negative indexes every time on every platform, and it is guaranteed to throw ArrayIndexOutOfBoundsException when the array is attempted to be indexed. Though the code is wrong, it is at least consistently wrong and loudly wrong. The same cannot be said for a similar bug implemented in C.

Well nobody prevents you from writing a compiler that will have this exact same behavior for the C language. In practice it doesn't happen because this «good citizen» compiler will produce code being slower than GCC or Clang on all benchmark, and since nowadays people mostly use C when performance is critical, this compiler will not be used by anyone.

Why even bother writing C if you all you achieve is Java, PyPy or JavaScript level in term of performance ?

Re: Defining the Undefinedness of C (2015) [pdf]

#89

Post by steveklabnik »

smitherfield wrote: post #53
steveklabnik wrote: post #41

Earlier quoted context omitted.

To be clear here, overflow is a "program error" in Rust; it's specified to panic in debug builds, and any build where it doesn't panic is defined as wrapping two's compliment. I tried to toss this into godbolt, but the optimizer is too good of course, it will optimize away the entire if if my_signed_int is a literal. Here's one without optimizations: https://godbolt.org/g/tBZcTA It seems to compare 1 to 1, and then b…

Rust does do the loop condition (well, comparing `my_signed_int` to INT_MAX) even with optimizations: https://godbolt.org/g/dnBEJi (You need to put a side effect such as I/O in the conditional branch for it not be optimized away, "pub" before the function declaration for it not to be eliminated as dead code, and pass `my_signed_int` as an argument so the condition isn't constant-folded). Clang OTOH optimizes away the…

Ah, nicely done.

Re: Defining the Undefinedness of C (2015) [pdf]

#90

Post by fundabulousrIII »

lotyrin wrote: post #36
fundabulousrIII wrote: post #26

My good god. Do you actually believe that this scenario reflects a weakness in C or a C compiler?

Yes? In the grandparent's solution, I should be able to e.g. collection.map, the type system and/or hints from myself should inform the compiler whether or not there are side-effects, if runtime bounds checks are needed, if this is something that can and should be turned into SIMD or concurrent threads. OR I should be able to write some mildly-portable assembly-type algo using intrinsic functions that represent preci…

Your approach is emblematic of programming as a culture of production versus a culture of understanding. I don't agree with any approach which characterizes a language as good or bad based on it's ability to read minds and make decisions based on the unknown.

When you mandate safe behavior based on any expert rules-based or heuristic system you have to leave the unsafe option open which is _just_ as bad.

Post reply on HN