Thoughts on Integers (2023)

> C has a confusing array of machine-dependent types such as ptrdiff_t and size_t

What's confusing about them? They're basically what int and unsigned int were supposed to be. It's just that they realized they had produced a pile of unextensible shit so they had to add new names.

While they were at it, they produced the next version of unextensible shit so now int128 can't be added.

I found the support of the idea that for integers the overflows should be handled by "wrapping" as exceedingly dumb.

Those where overflow results in wrapping are not integers and any such wrapping is an error that is difficult to detect and detecting it destroys the performance much more than using true integers.

The programming language C did a mistake by having only 2 integer types "signed" and "unsigned" and many modern programming languages have copied the same mistake without thinking. Moreover, the standard committees have made everything worse by defining relatively recently that overflow on "unsigned" integers must be handled by "wrapping", in which case they are no longer "unsigned integers", but they are integer residues modulo 2^N, which is a very different kind of mathematical object, for which the implicit integer promotion rules of C/C++ become broken, so now the standards define incompatible mathematical properties for the unsigned integers.

First of all, a programming language must offer as primitive types all the types that are implemented in hardware.

Instead of 2 types "unsigned" and "signed", the modern CPUs, like the Intel/AMD x86-64 CPUs or the Arm Aarch64 CPUs, implement no less than 8 distinct data types, all 8 being available in different sizes, which should be available as primitive types in any decent programming languages. This means that the CPU instruction sets have at least a few instructions where the operands are interpreted as having one of those 8 data types.

The 8 integer data types are:

1. (signed) integers where overflow is detected

2. (signed) integers where overflow is handled by saturation (i.e. with infinities)

3. non-negative integers where overflow is detected

4. non-negative integers where overflow is handled by saturation

5. integer residues (most instructions use residues modulo 2^N, but there are also a few instructions for residues modulo 2^(N-1); for residues overflow results in wrapping)

6. bit strings

7. binary polynomials

8. binary polynomial residues (which are elements of Galois fields)

Non-negative integers and integer residues are very different things and the confusion between them cannot result in anything else but bugs.

Conversions between non-negative integers are correct only from a smaller size to a bigger size.

On the contrary, conversions between integer residues are correct only from a bigger size to a smaller size. For example, if you have the residue 65535, you can convert it to 255, because 65535 modulo 256 is 255. But if you have the residue 255 you cannot convert it to a 16-bit number, because there are 256 different 16-bit numbers that have the same 255 residue when converted to 8-bit, and you do not know how to choose one of them.

In any programming language that claims that it is a safe language both the overflow of (signed) integers and the overflow of non-negative integers a.k.a. unsigned integers must generate exceptions. Otherwise any claim of safety is just a lie. The only acceptable alternative to exceptions is to use saturation, which allows the propagation of the errors so that they can still be detected in the final results.

That does not mean that every arithmetic operation must be checked for overflow. There are many cases when a compiler can determine at compile-time that an overflow is impossible, like in most operations with indices or with loop counters, so in such cases the compiler can omit the overflow checks. Otherwise they must be inserted, and especially in release builds, where undetected errors can have much more serious consequences than in debugging builds.