small integers

[Rob_MacLachlan@LISP-PMAX1.SLISP.CS.CMU.EDU]

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) 

Advantages of this proposal:
 -- 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.

Disadvantages of this proposal:
 -- 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.]

Advantages of this proposal:
 -- Small integer arithmetic is the default, so efficient proramming comes
    more naturally.

Disadvantages of this proposal:
 -- Small integer arithmetic is the default, so extended integer use
    require awareness additional code and awareness of the distinction
    between small and extended integers.
________________________________________________________________