FIXNUM's aren't Bogus!

[Jon L White <edsel!jonl@labrea.stanford.edu>]

re: Xerox Common Lisp has 17-bit fixnums. LISP:MOST-POSITIVE-FIXNUM = 65535,
    LISP:MOST-NEGATIVE-FIXNUM = -65536.

This choice is quite arbitrary.  FIXNUM is not constrained to mean
"immediate" data type (indeed it was NOT an immediate in PDP10 MacLisp), 
and Xerox Lisp's FIXP could just have well been included in its FIXNUM
type; that would have yielded a range of 32 bits rather than 17.  At one 
time, at least some implementations of Interlisp-D had microcode to cover 
the case of FIXP's; so it was a relatively efficient type.

MacLisp may be considered to be the father of the modern FIXNUM -- it 
originated the trick of reserving a couple pages of write-protected memory 
filled in with a dense neighborhood of integers centered around 0; thus 
"consing" a small fixnum didn't require new storage allocations.  The 
critical meaning for FIXNUM's, however, is not merely that they be "small",
nor that basic operations on them not consume storage, but that they be 
operable in a few, fixed number of steps.  In fact, in compiled code, the 
basic operations (on fixnums) were always one PDP10 instruction [including 
the four rationals, shifting, and even HAULONG, the predecessor of CL's 
INTEGER-LENGTH.  Love that JFFO!]  A *uniform* representation for fixnums 
was the critical factor in compiling these operations into one machine 
instruction.

The opposite of FIXNUM is thus a datum that falls into the asymptotic 
algorithms of "bignums", whose operational timing is proportional to the 
length of the numbers involved. 

I propose this meaning for FIXNUM: that the basic integer operations
use algorithms that are not proportional to the size of the data;  it 
should be just about as fast to add numbers in the middle of the fixnum 
range as it is to add, say, 10 and 11.

I would _prefer_ that the range of positive FIXNUM's be at least as large 
ARRAY-TOTAL-SIZE-LIMIT, so that one can be assured that any legitimate 
array index is a FIXNUM.  However, I'll admit that this is of more
concern to an implementation on "stock" hardware with "general purpose"
indexing registers.


Regarding the portability issues raised by differing FIXNUM ranges --
I agree with all of Jeff Dalton's comments.  Championing portability
here is making a mountain of a molehill.


-- JonL --


P.S.  A candidate for early fixnums might also be Interlisp-10's assymetric 
     representation, wherein very small integers were "immediate" and 
     medium-sized integers fit into one word (maybe Lisp1.5 had a similar 
     scheme too?).  Although operating on such a representation did not 
     require use of an "asymptotic" algorithm, it did require so much more 
     time than the PDP10 MacLisp scheme that they were not considered 
     particularly "efficient" by the relevant community of users.  In fact,
     just decoding the representation cost a subroutine call.  [Who among 
     us remembers (JSP T, NUMVAL)?] 

P.P.S.  The more common technique now for representing fixnums is to
     notice that on byte-addressed machines (like VAX, MC68000 series,
     INTEL 80386, most Risc-type machines, etc.) the low-order two bits 
     or more of an address are redundant (cons cells requiring at least 4
     and probably 8 bytes of memory).  So the low-order two or three bits 
     can be used arbitrarily as datatype tag information, and a prudent 
     choice of the tag code leads to a very efficient FIXNUM implementation.
     Let fixnums have all "low-order" bits zero; thus data in a format like:
                          sxxx...xx0...0
     (where "s" is a sign bit and the "x"'s are arbitrary bits) will still
     be in that format after a machine "longword" addition or subtraction;
     and multiplication and division require at most a pre- or post- shift
     by a couple bits to retain that format.  Hence basic fixnum operations
     can still be done in about one machine instruction. [I credit Stallman 
     with first noticing the immense utility of this fact, back in 1978 
     when we were brainstorming the design of VAX/NIL].  Despite the vast 
     difference in implementational "tricks", PDP10 MacLisp and VAX/NIL
     share what I condsider to be the fundamental feature: low, constant-
     time value for basic operations costs.