Software // Enterprise Applications
Commentary
7/26/2008
12:00 AM
Commentary
Commentary
Commentary
50%
50%

A parable about undefined behavior

Once upon a time there was a Very Large System written in C.  The VLS developers  had found a troublesome bug, which they traced down to strange behavior in the C compiler.  Specifically, one of the developers had written a statement that looked like this:

    if ((c = a - b) == 0) { /* ... */ }

They had discovered that when a was a large positive number and b was a large negative number, it was possible that the result of the subtraction would overflow.  In that case, the value of c might be zero, but the code in the braces would not be executed.

They duly reported this bug to the compiler's author, and were informed that this behavior was not a bug: If the evaluation of a - b overflows, the result is undefined and the implementation can do as it pleases.

The VLS developers were incensed.  Surely, if you assign zero to a variable and then test the value of the variable, you should be entitled to assume that the test will show that the variable is zero.  Not so, said the compiler author.  If your program causes an overflow to occur, that program is invalid, and the compiler has no obligations about what it should do with invalid programs.

On the surface, this attitude may seem like needless stubbornness on the compiler author's part.  However, the reason for his attitude becomes apparent when we look a little more closely at the computer's instruction set.  This particular computer did comparisons by means of a tiny register called the condition code.  This register contained two bits, which meant that it could represent one of four states.  Those states were usually negative, zero, positive, and overflow.  Many arithmetic operations, particularly including addition and subtraction, would set the condition code to reflect the result of the operation.  One could test the state of the condition code with a conditional jump instruction.

Now consider the code that the compiler generated for the expression ((c = a - b) == 0).  It would begin by loading a into a register and subtracting b.  This subtraction would set the condition code to reflect the result.  The next instruction would store this result in c, an operation that does not change the condition code.  Therefore, it would be possible to follow this store instruction by a conditional jump that would test whether the result of the subtraction (and therefore the value of c) is zero.

What happens if the subtraction overflows?  Then the condition code is set to the overflow state, and checking against zero fails (because overflow state is not the same as zero state).  In other words, the actual value of c cannot affect the outcome of the conditional jump if an overflow has occurred.

Of course, it would have been possible to change the compiler to insert an extra instruction that would test the value of c.  Doing so, however, would have imposed the time and space overhead of that instruction for all programs, not just ones in which overflows happened to occur at inopportune times.  He took the view that the language definition says that overflow is undefined, and therefore that it would be inappropriate to try to define it for the sake of mere convenience.

When a programming language definition talks about undefined behavior in a context that is not obvious, it is often possible to discover the reason by thinking about what the implementation would have to do in order to define the behavior reliably in that context.

Comment  | 
Print  | 
More Insights
Building A Mobile Business Mindset
Building A Mobile Business Mindset
Among 688 respondents, 46% have deployed mobile apps, with an additional 24% planning to in the next year. Soon all apps will look like mobile apps and it's past time for those with no plans to get cracking.
Register for InformationWeek Newsletters
White Papers
Current Issue
InformationWeek Tech Digest, Dec. 9, 2014
Apps will make or break the tablet as a work device, but don't shortchange critical factors related to hardware, security, peripherals, and integration.
Video
Slideshows
Twitter Feed
InformationWeek Radio
Archived InformationWeek Radio
Join us for a roundup of the top stories on InformationWeek.com for the week of December 14, 2014. Be here for the show and for the incredible Friday Afternoon Conversation that runs beside the program.
Sponsored Live Streaming Video
Everything You've Been Told About Mobility Is Wrong
Attend this video symposium with Sean Wisdom, Global Director of Mobility Solutions, and learn about how you can harness powerful new products to mobilize your business potential.