# small integers

• To: info-dylan@CAMBRIDGE.APPLE.COM
• Subject: small integers
• From: Rob_MacLachlan@LISP-PMAX1.SLISP.CS.CMU.EDU
• Date: Wed, 07 Oct 92 17:57:37 -0400

```It isn't really clear from the book, but the Dylan <integer> class
evidently supports extended-precision arithmetic.  Since small integers are
ubiquitous, good small-integer preformance is crucial for all manner of
applications.  There must be some way of informing the compiler that
arimthmetic operands are small integers and that the result will be a small
integer.

Suppose <integer> has a subclass <small-integer>.  We could then use this
type to declare arithmetic operands:
(bind (((x <small-integer>) stuff)
((y <small-integer>) more-stuff))
(+ x y))

This helps the compiler somewhat, but leaves open the possibility of
integer overflow.  What happens when <small-integer> arithmetic overflows?
In most Lisp implementations (such as Common Lisp), the answer is that a
non-small integer results.  Declarations are necessary on each intermediate
result, so (x+y)*3 becomes:
(bind (((x <small-integer>) stuff)
((y <small-integer>) more-stuff)
((t1 <small-integer>) (+ x y))
((t2 <small-integer>) (* t1 3)))
t2)

This sort of stuff certainly makes C & FORTRAN look like higher-level
languages than Lisp.  I am proposing a set of related changes, divided into
two proposals.

Rob MacLachlan (ram@cs.cmu.edu)

________________________________________________________________
Small/extended integer proposal:

There shall be two disjoint subclasses of <integer>:
<small-integer>
<extended-integer>

The result of <small-integer> OP <small-integer> is always a
<small-integer>.  If over or underflow results, then an error should be
signalled.  <extended-integer>s are more "contagious" than
<small-integer>s.

The result of <small-integer> OP <extended-integer> is always
<extended-integer>.  Over/underflow results in a quiet transition to
extended precision arithmetic.

Numeric operations on non-integers with integer results
(truncate,floor,ceiling,round,/-variants,numerator,denominator, probably
real-part, imag-part) always return <extended-integer>s.

Note that a <small-integer> and an <extended-integer> may have the same
numeric value (such as 5).  In such a case, the class distinction serves to
control the over/underflow behavior.  AS may be used to convert between
integer classes:
(as <small-integer> some-integer)
(as <extended-integer> some-integer)

-- The <small-integer> type allows the use of efficient hardware-supported
arithmetic without first checking argument types.
-- Considering <small-integer> overflow to be an exception allows more
compact and efficient overflow handling to be compiled.  Delivered
applications might omit overflow checking entirely.
-- Considering <small-integer> overflow to be an exception allows complex
(nested) integer arithmetic expressions to be written much more
more naturally, since type assertions are not needed on intermediate
results.
-- Extended integer support as been pulled out into a separate class which
one could consider to be an optional library.

-- Two more classes.
-- Conceptual complexity in understanding the distinction between the two
classes.
-- Using the class to encode the extensibility attribute may be sort of a
bad pun, since it seems to clash somewhat with the normal conception of
subtype relations on integer types.  This is because the conflicting
demands of inheritance and subtypeness.

________________________________________________________________

Small integer integration proposal:

-- Sequence keys, array indices and collection sizes are implicitly
coerced to <small-integer>.  If an <extended-integer> argument is too
large to be a <small-integer>, then an error should be signalled.
-- Any integer literal which can be represented as <small-integer> is
small.

Paraphrase:
<small-integer> is the default integer class.  The obvious coding of
integer algorithms do not automatically extend into bignums.  You would
write extended FACTORIAL like this:
(define factorial
(method (n)
(if (= n 0)
(as <extended-integer> 1)
(* n (factorial (- n 1))))))

small-integer factorial could be written:
(define small-factorial
(method ((n <small-integer>))
(if (= n 0)
1
(* n (small-factorial (- n 1))))))
[efficient compilation would require recursive type inference or a way
to declare the type of the recursive call or of all calls to
small-factorial.]