3 ms·
Oh, that's nice. I wanted that decades ago, when I was working on program verification. Templates have made a lot of progress if this can be done entirely in C+
by Animats 7y ago
Oh, that's nice. I wanted that decades ago, when I was working on program verification. Templates have made a lot of progress if this can be done entirely in C++ templates. I once wrote, but never published, "Type Integer Considered Harmful", back when there were still 16-bit integers in most C programs. I wanted ranges on everything, like Ada. As a practical matter, integer overflow became less of an issue with 32-bit.
Sizes of intermediates are a big issue. When you write
int_32 a,b,c,n;
...
n = (a*b)*c;
how big is each part? My thinking on this was that it's the compiler's job to prevent overflow in intermediate values where the final result will not overflow. So, above, you'd have to compute (m * n) as a 64-bit product, do a 64-bit divide, and only then check that the result fit in n.
is legal to compute in 32-bit, but requires overflow checking on the intermediates. If an overflow occurs, there will be an overflow in the result. (Although, the case where some values are zero is an issue. Suppose a * b overflows but c is zero so it doesn't matter. That's probably an error.)
Sometimes you have to use larger sized intermediates. For
int_32 m,n,p;
...
n = (m * n) / p;
how big is each part? Above, you'd have to compute (m * n) as a 64-bit product, do a 64-bit divide, and only then check that the result fit in n.
To do this right, you need something in the compiler that can do basic reasoning about machine arithmetic. Something that knows, for example, that
uint_16 n;
...
n = (n + 1) % 65536;
cannot really overflow and can be optimized down to a plain unsigned 16-bit add.
If you try to to this through linguistic type analysis only, it's not going to be satisfactory.
You need to be able to prove out inequalities.
- Animats 7y agoBotched the editing near the examples. Sizes of intermediates are a big issue. My thinking on this was that it's the compiler's job to prevent overflow in intermediate values where the final result will not overflow. When you write int_32 a,b,c,n; ... n = (a*b)*c; that's legal to compute in 32-bit, but requires overflow checking on the intermediates. If an overflow occurs, there will be an overflow in the result. (Although, the case where some values are zero is an issue. Suppose a * b overflows but c is zero so it doesn't matter. That's probably an error.) Sometimes you have to use larger sized intermediates. For int_32 m,n,p; ... n = (m * n) / p; how big is each part? Above, you'd have to compute (m * n) as a 64-bit product, do a 64-bit divide, and only then check that the result fit in n.
- rasz 7y agoThis was more or less the source of infamous Turbo Pascal 'Runtime Error 200: Divide by zero', twice! http://ss64.net/merlyn/pas-r200.htm#Why http://ss64.net/merlyn/pas-r200.htm#Why