[Cryptography] letter versus spirit of the law ... UB delenda est

[D. Hugh Redelmeier]

| From: John Denker <jsd at av8n.com>

|  1) Overflow could throw an exception.
|    1a) It might be possible to recover from the exception.
|    1b) Or it might not.

Crashing is generally a better policy than continuing with a wrong
answer.  This forces bugs to be noticed and to be fixed.  (Throwing
an exception instead of crashing would be OK except that programmers
would start to write code that intended to generate exceptions.)

In the work up to the first C standard, I kept an eye on what signed
overflow and "undefined" meant.  I intended to implement a debugging
compiler that would abort the program if signed overflow happened.  As
I understood the standard, this was a legal interpretation.  I am not
sure that it is true of subsequent revisions.

It used to be that it was possible on ordinary hardware to get an
exception on integer overflow for free.  IBM/360, for example.  For
an extreme example, see the IBM 709 Divide and Halt instruction.

To make that work, if unsigned and signed arithmetic were supported,
the architecture needed distinct signed and unsigned instructions.  On
the /360: A for signed add, AL for unsigned.  The PDP-11 designers
decided that since the values (in twos complement) were the same, the
distinction would be left in the condition code, for subsequent
instructions to interpret.  Every machine since the PDP-11 seems to
have copied this.

This made trapping on overflow expensive so nobody did it.  Intel 8086
even had an instruction "INTO" (Interrupt if overflow flag set) that
apparently nobody used (I think it got dropped from follow-on architectures).

If overflow traps, a signed type is no longer closed under those
operations.  But we were only pretending that the type is closed on
non-trapping machines: in place of overflow we get
wrong values.  What we do lose is associativity.
	maxint + (1 - maxint)
vs	(maxint + 1) - maxint
The second traps but the first does not.  With the normal
implementation these expressions compute the same value.
Associativity is useful for optimization.

If I were redesigning C, I would make it the compiler's job to ensure
that a mathematically correct value were computed from each
expression.  If the programmer then took such a correct value and
assigned it to a too-narrow variable or parameter, that would be an
error.  By the "as-if rule", most wide arithmetic could be optimized
away.  I have not studied how much extra this would cost.  It would
make C a lot simpler.