Nice TWiki > Dev > CheckedIntegerArithmetic TWiki webs:
Dev | Doc | Main | TWiki | Sandbox
Dev . { Changes | Index | Search | Go }
The current behaviour of numeric type is to silently overflow. In some cases this is what is needed, and in some cases you don't really care, because it is guaranteed no overflow will occur. However, there are also situations in which you would like a runtime exception to be thrown when overflows/underflows occur (hello, Isaac!).

The JVM does not directly support this arithmetic mode. However, at least for non-long types, it is possible to perform operations on a larger JVM type than the declared type, and then check for overflows. This has of course a small performance hit, but much less than using objects (BigInteger? for instance). So it might be possible to add new types that have overflow detection semantic and good performance. I'll focus on int, but this should be doable for shorter types too. What cases are useful in practice?

Since we want to retain the current semantics for int, we should add a new type, with the meaning "a 32 bit signed integer not modulo 2**32" (that is, which throws an exception when an overflow occurs). I'm not sure what the best name for it would be. integer is a possibility, but I was also considering it for infinite length integers (that is an alias for BigDecimal?). Other ideas: checkedInt (not pretty), checked-int (better, but a new convention for type names), cint (cryptic). Let's use cint in this document, it's short :-) how about checked as a modifier, as in "checked int"?

Regarding typing, int should be a subtype of cint, because you gain "safety" by considering an int as a cint. On the other hand, going from cint to int would later allow overflows to occur, so it should not be automatic. I would also think that cint should be a subtype of long, does that make sense?

Regarding implementation, one possibility is to represent cint as long in the JVM, and to check the result of each operation. Another possibility is to represent cint values as int, but operations on cint values would be performed on long, and the result checked before conversion back to int. The former might be more efficient (less conversions), while the later is more economous in space, which is especially interesting if you have an array of cint. Alternatively, is it possible to detect all/most overflows by working on int only (for instance, for addition, if both numbers are positive, there is overflow if the number is negative)?

-- DanielBonniot - 21 Dec 2003

Overflow detection is possible with int for addition and substraction by sign check. For multiplication, i am not quite shure if even long would be enough. -- TWIkiGuest?

The multiplication of two 32 bit numbers fits on 64 bits without overflow (because log(a*b) = log(a)+log(b)). So it seems we could use int to represent cint, and use temporarily a long for multiplication.

Could somebody actually write the operations as Nice methods (using int as the type)? So a int checkedAddition(int,int) method, ... -- DanielBonniot

I don't think that overflow checking should a part of primitive types because it's not clear when the check should happen(when the result is assigned to a cint or one or both of the operands are cint). Whether to do checking is a property of operators so checked methods or code blocks make more sense.

I have doubts about the usefulness of this proposal and this is VM issue and not a language thing. -- ArjanB - 22 Dec 2003

One way to look at it is that there are three kinds of integer types: modulo integers (higher bits are discarded), limited length (checked) integers and inifite length integers (BigInteger?). Mathematically, the first one makes sense (computing a hash value for instance), and of course the last one too. Checked integers would be useful when modulo is clearly incorrect, but you expect that 32 (or 64) bits will be enough. Using BigInteger? would incur a significant performance penalty, but modulo integers would hide errors if they occur.

So from a language point of view, all three types make sense. Therefore it is not a bug that the JVM does modulo arithmetic, it's useful. If we can use it to provide checked arithmetics too, then all the better.

Rgarding when checks happen, it's simple: they should happen when operations are performed on checked integers. So if you do an operation on two int it will not be checked, if one is int and the other cint, then the type system will decide to call the checked operator, and so there will be a check. With overloading on the result type (which is not available at the moment), we could also say that using the result of a int,int operation as a cint should be a checked operation.

-- DanielBonniot

Many folk seem to forget that JVM does modulo arithmetic - there's a large community for whom this just isn't a problem - whatever I might think. And this isn't something novel that people would be excited about.

Maybe work should concentrate on really ordinary things that will be used a lot (Visibility? Properties?) and really extraordinary things that are made possible by the type system (XML support? Variance sugared syntax?).

-- IsaacGouy - 23 Dec 2003

I agree with these priorities. On the other hand, I believe that the way to accelerate the development of Nice also lies in doing more things in parallel. This means that while the people familiar with the core compiler (Arjan and me) look at features like constructors and properties, it only helps if others are working on tools, libraries, ... In particular, I believe that checked arithmetics is not a hard feature, and that it can be implemented at 90% as user libraries. If somebody provides the checked operations on ints, it should be a matter of say 30 minutes to add the cint type to the compiler. So it won't really slow us down :-) -- DanielBonniot - 24 Dec 2003

With the addition of type declarations(which could allow declaring subtypes of primitives too) CheckedIntegerArithmetic can be a library thing for 100% -- ArjanB

"type declarations" Is there a proposal? -- IsaacGouy - 24 Dec 2003

A cint type seems too low-level since it's tied to JVM details rather than the problem space. I think it would be more useful and more high-level to have checked integer types with a user-specified range. For example, integers in the range [1...100]. That way you find out earlier about incorrect values and the compiler can choose an int, long, or BigInteger? implementation as appropriate. Operations done with these integers would use intermediate values as large as necessary to prevent overflow and do the runtime check when assigning to a non-temporary. (Of course, it's more work for the compiler.) -- BrianSlesinsky - 30 Dec 2003

You may want to check out Javolution and JScience for some nifty ideas. Particularly LargeInteger? (in JScience), and some other stuff in there. I think the idea of using a long for multiplication is good (i.e. result = (long)a * b), then you can do a simple overflow = (result != (int)result). For addition/subtraction, basically, you just have to check that the sign bit (i.e. MSB) is the same as one of the operators. So for result = a + b, overflow = ( (result >> 31 != a >> 31) && (result >> 31 != b >> 31) ) -- MotiN - 17 Jan 2005

Topic CheckedIntegerArithmetic . { Edit | Attach | Ref-By | Printable | Diffs | r1.12 | > | r1.11 | > | r1.10 | More }
Revision r1.12 - 17 Jan 2005 - 20:08 GMT - MotiN Copyright © 1999-2003 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.