[bitc-dev] Primary type arithmetic

[Eric Northup]

On Sat, 2005-02-05 at 16:26, Shawn Garbett wrote:
> I was thinking more like the following:
> 
> +, -, etc all double the word size. 

Unfortunately, this won't work.  Efficiency concerns
aside, BitC does not allow arbitrary sized
fixed-precision integers.  int8, int16, int32,
int64 are OK.  int65536 is not in the current spec.

Also, the size-increase makes it extremely difficult
to perform arithmetic in bounded storage.  How much
storage would an N-iteration loop require for the
loop variable?  And what happens if the program
runs out?

The set of "arbitrary precision integers which can fit into
a computer's memory" is _not_ closed over arithmetic
operations!  The result "out of memory" is not in the set
of arbitrary precision integers :-(

> The static type
> checker would catch any usage violating this. Then for
> wrap around, aka a ring, ring+, ring- etc. Then for
> exceptions on overflow or underflow, have bounded+,
> bounded-, etc.

I doubt that a static check is possible in the general
case.  I suspect it will end up being the halting problem.
For some cases, a proof can be constructed that overflow
never occurs, and thus need not be checked at runtime.
But what about the others?  I want our type-checker to
terminate!

> If the static type checker could give a custom message
> for type violations of +, -, then the programmer could
> be steered toward his possible intentions. The usage
> of ring and bounded, are somewhat self-documenting.

I would slightly prefer 'wrap+' over 'ring+', because
I get confused thinking about the abstract math
definition of a ring. 

I only see 2 (rather than 3) different classes of
operators:

-Fixed precision modular integer operations (2's
compliment) which wrap on overflow, and do not throw
exceptions.

-Fixed or arbitrary precision integers which throw an
exception on overflow.  Arbitrary precision "overflow" is
the out-of-memory condition, and presumably rare.  But
it is still possible.

If I recall, the original question was along the lines of:
 "should the (+, -, *, etc.) operators on fixed-precision
integers be the 'wrap-around' type, or the 'throw-
exception' type?".

I am leaning towards 'throw-exception'.  But I don't care
too strongly as long as both forms can be read unambiguously
and typed without contributing to repetitive-stress
injuries.

My reasoning for preferring 'throw-exception'-style
operators is that programmers who were not considering
problems of overflow will be reminded when it gets the
exception.  Programmers who _were_ considering overflow
have explicitly marked their intention by using the
wrap-around version of the operators.

--Eric