Software // Enterprise Applications
12:00 AM
Core System Testing: How to Achieve Success
Oct 06, 2016
Property and Casualty Insurers have been investing in modernizing their core systems to provide fl ...Read More>>

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
Newest First  |  Oldest First  |  Threaded View
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
Top IT Trends to Watch in Financial Services
IT pros at banks, investment houses, insurance companies, and other financial services organizations are focused on a range of issues, from peer-to-peer lending to cybersecurity to performance, agility, and compliance. It all matters.
Twitter Feed
InformationWeek Radio
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.