[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

small integers

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

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)))

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>:

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

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
 -- 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
 -- 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-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)
		(* 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

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.