4 ms·
Too many years ago, I wrote something in-house, now lost, titled "Type integer considered harmful". I was arguing for the idea that everything should have an ex
by Animats 5y ago
Too many years ago, I wrote something in-house, now lost, titled "Type integer considered harmful". I was arguing for the idea that everything should have an explicit range, written
foo: 0..100;
This was around the time Ada was being designed. The way I wanted this to work is that the size of intermediate variables was determined by the compiler, with the following rules:
- Unless a named typed variable result will overflow, no unnamed intermediate variable can overflow. The compiler must size intermediate temporary values accordingly.
- If this requires a larger intermediate variable than the machine can provide, a compile error is reported.
The implication is that you often need longer integers than you'd expect. Expressions such as
x = a + b - c
x = (a + b) / c
with signed values, all, say, 32-bit integers, can overflow in a+b without overflowing x.
So such expressions have to be computed in 64 bits, then checked for overflow. This eliminates hidden overflow in intermediates. An expression with only one operator never overflows in a recoverable way, so it just has to be checked, not expanded.
That was written in an era when there were computers in use with word sizes of 8, 12, 16, 18, 24, 32, 36, 48, 60, and 64 bits. So word size was more of a practical issue than it is now, when non power of 2 machines have died off. Also, machines of that era tended to be slower on longer values. Much slower on some machines which had to do double-length arithmetic in software. Thus, there was a performance hit for this approach, which was the main objection.
- tialaramex 5y agoWUFFS call that type refinement, although you are free to refine much larger types e.g. you can say base.u32[0 ..= 15] and this is a 32-bit unsigned integer... that can't be more than 15. WUFFS not only refuses overflow (you get a compiler diagnostic) it also infers these refinements from array sizing so as to (at compile time) ensure bounds errors never occur. If you try to index into an array of 426 integers with k, WUFFS will go ahead and refine k to the 0..425 range. Of course Ada (and presumably your proposal) are for general purpose software, whereas WUFFS is specifically targeted at software for well, Wrangling Untrusted File Formats Safely. So it's fine for some things to be completely impossible in WUFFS (e.g. you cannot write "Hello, World" in WUFFS, because WUFFS intentionally has no idea what a "string" is, or what "console output" is).
- SAI_Peregrinus 5y agoWUFFS calls them that because the formal name for the concept is a Refinement Type[1]. [1] https://en.wikipedia.org/wiki/Refinement_type https://en.wikipedia.org/wiki/Refinement_type
- Someone 5y ago> An expression with only one operator never overflows in a recoverable way, so it just has to be checked, not expanded (Nitpick: I think you intended to write either always or unrecoverable) _If the target CPU doesn’t have status flags indicating overflow_, that may be more work than using a larger intermediate. For a+b, detecting overflow after the fact highly likely is faster, but already is a bit convoluted if a and b are signed and, thus, can be negative (https://stackoverflow.com/a/45261894 https://stackoverflow.com/a/45261894) For a×b https://stackoverflow.com/questions/1815367/catch-and-compute-overflow-during-multiplication-of-two-large-integers https://stackoverflow.com/questions/1815367/catch-and-comput... has a simple algorithm, but it requires a division by b. I don’t see that perform well. Possibly, double size multiplication and then testing for overflow beats that (but, if the CPU has a ‘count leading zeroes’ instruction, I would use that (https://stackoverflow.com/a/59109502 https://stackoverflow.com/a/59109502. I haven’t checked that for correctness, but even if it can’t be made correct, it likely can provide a fast path for most multiplications that your program does) For CPUs with an overflow bit, the compiler can use it, but not all CPUs have that.
- deleted 5y ago[deleted]