small integers

[Jeff Piazza <piazza>]

   Date: Fri, 09 Oct 92 03:22:39 -0400
   From: Scott_Fahlman@SEF-PMAX.SLISP.CS.CMU.EDU

I would have thought this was obvious enough that someone else would
have mentioned it, but no one has, so perhaps it isn't.

Rather than focusing on different integer classes, it's possible to
cast the issue as one of using different operations.  That is, the ADD
operation on a typical CPU doesn't implement addition; it implements a
different operation (like "addition modulo 2^32") that is "close
enough" for most purposes.  Reflecting this in the programming
language, we would have, instead of two different 5's, two different
+'s: one under which the <small-integer> class is closed, and one
under which it isn't.  With the former operation, when the arguments
are provably small integers, the compiler can generate a machine ADD
instruction, and also conclude that the result will be a small
integer.  (This avoids having to declare every intermediate result,
which is certainly unpleasant.)

I can't think of particularly good names this morning, so let's
suppose for now that the two versions of addition are named fix+ and
int+, supported by binary-fix+ and binary-int+, respectively.  Then +
can be re-cast as a macro which expands either into fix+ or int+,
depending on declarations.  The result of this would be that one could
write a correct program easily, or obtain an efficient program with a
small amount of declaration effort.  Where it's necessary to mix the
two kinds of addition, one may write explicit calls to int+ or fix+
with cluttering the code too much.  (A drawback of the "+ as macro"
plan would be that one would have to write (reduce int+ 0 list-o-nums)
where one could write (reduce + 0 list-o-nums) today.)

Note that binary-fix+ (the "mod 2^n" operation under which
<small-integer> is closed) can be realized as a (sealed) generic
function containing only two methods: one handles the case of
small-integer arguments, and the other handles all other cases by
calling binary-int+.  New methods would be added only to binary-int+.

Similar remarks apply to -, *, and /.

Opinions?

/JEP