Hacker News Reader

Comment by int_19h | Hacker News Reader

It amazes me that with all the focus on memory safety, most PLs still don't handle integer overflow sensibly by default: you either get guaranteed wraparound (which silently gives wrong values), or straight up undefined behavior as in C and C++. The latter won't change at this point, of course, but why do new designs insist on following their lead? Safety should always be opt-out, not opt-in.

And sure, overflow checks aren't free - but this is something that has been optimized in CPUs for decades.

View on HN

Graydon Hoare originally wanted integers to be promoted to bignums on overflow, but that didn't happen.

https://graydon2.dreamwidth.org/307291.html

That's really the only proper solution for this problem.

Not necessarily the only proper solution--hard failure, like array out-of-bounds errors, is also often an acceptable solution.

That highly depends on the execution environment. In Erlang for instance that would be an acceptable solution. But most other environments don't deal nearly as gracefully with runtime errors.

MIPS on GCC defaulted to trapping integer overflows, but they had non trapping instructions too.

When reading this headline, my very first thought was "we wouldn't have this problem if more people used Ada" for that very reason.

I don't even think Rust can do something like

   type Element is Integer range 100 .. 1000;

Pascal can also do this.

That's correct, Rust does not have this, in principle Pattern Types (a possible future Rust feature) could do this, but you probably wouldn't use them for this purpose.

WUFFS can do this, it calls such types "refined" types - and indeed WUFFS can also do:

  assert n_bits < 12 via "a < b: a < c; c <= b"(c: width)

What that's saying is "As the programmer I say on this line n_bits is strictly less than 12, and I claim you can prove that based on knowing the value of width, and here's why"

WUFFS doesn't know how to create such a proof, it's in quotes because WUFFS has a list of proofs a human gave it, baked in, and just accepts any of those proofs, after all a human mathematician assured it these are true. But it can check the rest of your assertion given this proof, and if that fails your software doesn't compile.

WUFFS requires that it can see why everything you're doing is OK, whether that's indexing into an array (if you write dogs[k] where dogs is an array of 16 dogs, WUFFS needs to be certain that k is strictly in the range from zero to fifteen inclusive, or the program won't compile) or arithmetic (if bits is supposed to be an integer between one and thirty two inclusive then we can't very well do bits = k * 2 can we, because k might be zero)

As a result WUFFS gets to be entirely safe. As a side effect (and also with the help of some clever SIMD friendly language design choices) WUFFS gets to go very, very fast. And all for the very affordable price of abandoning generality. The next Doom, Excel, Apache and Linux cannot be written in WUFFS. But the question is why your thumbnail making code, or your file compressor is written in anything else.

Depending on what you allow in predicate types, you end up making type inference (and/or type checking) an undecidable problem.

In Common Lisp, you can write

  (deftype element () `(integer 100 1000))

and in this case, a "smart" compiler like SBCL will be able to infer the bounds of (the element x), but for more complex predicates, like

  (deftype even-element () 
    `(and (integer 100 1000)
          (satisfies evenp)))

I highly doubt there is a single CL compiler out there that'd be able to e.g. optimize (logand 1 (the even-element x)) into the constant 0. Thus declaring types like this -- in Common Lisp at least -- is only really useful for documenting code and run-time validation.

Extant cl compilers are quite primitive. Well known and uncomplicated analyses exist that can cope with this; e.g. in llvm https://godbolt.org/z/nadbG5zGs

The guaranteed wraparound of "unsigned" types in C and derivatives is not very helpful.

While the "signed" types in C are well defined kinds of integers, which nonetheless have unpredictable behavior on overflow, the "unsigned" types are ambiguous, because they correspond to 4 different primitive types (each of these 4 being available in various sizes, i.e. 1-bit, 8-bit, 16-bit, 32-bit, 64-bit or 128-bit).

By primitive types I mean types for which the modern CPUs implement distinct dedicated hardware instructions. The 4 types are non-negative integers, integer residues (a.k.a. modular numbers), binary polynomials and Galois-field binary polynomials.

The same operation, e.g. multiplication, is implemented with different algorithms for each of these 4 types.

Moreover, while a 64-bit "unsigned" may be interpreted as a 64-bit non-negative integer or a residue modulo 2^64 or a 64-bit binary polynomial or a value in GF(2^64), there are 2 additional interpretations between which there are subtle differences, as a 64-element array of 1-bit non-negative integers or as a 64-element array of residues modulo-2. The failure to be aware of the differences between the operations that can be performed with these 6 types and using a single name for all can easily lead to bugs.

The wraparound is correct for integer residues modulo 2^N, but it is wrong for non-negative integers, which are more frequent in most applications.

Also the implicit conversions of unsigned types are very bad in C and derivatives. They are some times correct for non-negative integers, but they are always wrong for integer residues. While a small-size non-negative integer may be converted without losses to a bigger size, for integer residues the reverse is true, they can be converted correctly only towards smaller sizes.

Therefore, the unsigned types of C are defined wrongly both when interpreted as non-negative integers and when interpreted as integer residues. Most other languages are not better.

While there are many applications where either non-negative integers, integer residues, binary polynomials or Galois-field binary polynomials are needed, so unsigned C types must be used for lack of a better alternative, the use of "unsigned" types requires extra care in comparison with using the signed types (e.g. all implicit conversions must be avoided) and it must be clearly documented what kind of "unsigned" is really meant (preferably by defining dedicated types for the various possible interpretations; in C++ it is possible to also define correct operations with them, replacing the built-in operators with undesirable behavior).

Very interesting thoughts. I have also seen one programming languages, ehich I cannot find anymore, which doesn't differentiate between signed and unsigned integers as types. Instead, there are just various sized integers, and for each operation you must choose between signed and unsigned semantics. Kind of like Javas >>> and unsignedToString.

I am not sure I follow. unsigned types in C are residues and not binary polynoms or Galois fields (also you can of course store them in unsigned integers).

The conversions work, e.g. conversion to a smaller unsigned type are reduced. That some other conversion work does seem convenient to me and not a problem.

One can, of course, define types in C for Galois fields and access them using functions that do the correct operations (and by wrapping it in a struct one can also prevent regular operations to be used on such type). In C++ one can overload the builtin operators, but I am not terrible sure this is even a good idea.

There’s also Rust’s half-measure of overflow in release mode, panic in debug mode.

It takes two lines in your Cargo.toml to turn overflows into panics in release mode in rust, if you don't mind the performance hit.

Or more sensibly you can set clippy lints to disallow any operation that may overflow, forcing you to specify the desired behavior (either with the .{wrapping,checking,saturating}_{sub,add,mul,div} functions or the Saturating<Type> etc wrappers)

Okay thanks.

Similarly, with C#, you can compile with exception-on-overflow for integers. This is all great, but this should really be the default behavior for basic arithmetic operators, even in release builds. For cases where you want overflow (or saturation, or UB) there should really be distinct operators. Maybe something like <+> for wraparound, [+] for saturation etc.

Reply on news.ycombinator.com