Issue BOGUS-FIXNUMS (Version 2)

[sandra%cdr@cs.utah.edu (Sandra J Loosemore)]

Issue:		BOGUS-FIXNUMS
References:	CLtL p. 14, 34, 43, 231
Category:	CHANGE, CLARIFICATION
Edit History:   Version 1, 11 Jul 1988, Sandra Loosemore
                Version 2, 27 Jul 1988, Sandra Loosemore (change direction)

Problem Description: 

Implementations of Common Lisp are required to support two disjoint
subsets of integers, fixnums and bignums, with the promise that
fixnums have a more efficient representation.  However, nothing is
guaranteed about the range of integers which are fixnums: "Exactly
which integers are fixnums is implementation-dependent; typically they
will be those integers in the range -2**n to 2**n - 1, inclusive, for
some n not less than 15."

There are few uses of the fixnum type that are portable, given the
current definition.  In particular, many programmers use FIXNUM type
declarations where they really mean "small integer".

Furthermore, it is conceivable that an implementation could support
only a single internal representation for integers, and some
implementations do support more than two representations with varying
ranges and degrees of "efficiency".  In such a case, arbitrarily
partitioning integers into "fixnums" and "bignums" becomes an
artificial contrivance which is more likely to confuse users than to
ensure portability of code.


Proposal: BOGUS-FIXNUMS:TIGHTEN-DEFINITION

(1) Change the wording at the top of page 14 of CLtL:

  In most Common Lisp implementations, there is a range of integers that
  are represented or operated on more efficiently than others; each such
  integer is called a FIXNUM.  Common Lisp is designed to hide this
  distinction as much as possible; the distinction between fixnums and
  non-fixnums is visible to the user in only a few places where the
  efficiency of representation or operation is important.  Exactly which
  integers are fixnums is implementation-dependent.  However, it is
  required that (SIGNED-BYTE 16) be a subtype of FIXNUM in every
  implementation of Common Lisp.  If an implementation does not provide
  a distinguished representation for small integers in this range, then
  the types INTEGER and FIXNUM are considered equivalent in that
  implementation.  See MOST-POSITIVE-FIXNUM and MOST-NEGATIVE-FIXNUM.

(2) Change the wording at the top of page 34 of CLtL to indicate that
FIXNUM is a subtype of INTEGER (removing the reference to BIGNUM).

(3) Remove BIGNUM from the table of standard type specifier symbols on
page 43 of CLtL.

(4) State that the constants MOST-POSITIVE-FIXNUM and
MOST-NEGATIVE-FIXNUM are allowed to have a value of NIL to indicate
that the implementation does not have a particular FIXNUM
representation distinct from other integers. 

(5) Introduce a new constant, MAX-INTEGER-LENGTH.  This is the maximum
number of bits appearing in any integer; therefore, it is an upper
bound on the INTEGER-LENGTH function.  The value can be NIL if there
are no limits short of memory availability.


Rationale:

Many programmers already use FIXNUM to mean "small integer"; this
proposal makes this usage portable, and allows programmers to use the
FIXNUM type specifier in a way similar to how the "int" type is used
in C. 


Current Practice:

Xerox Common Lisp has 17-bit fixnums.  I know of no other Lisp which
claims to be an implementation or subset of Common Lisp that has
fixnums less than 24 bits long.

Several existing Lisps have more than two representations for
integers, including Lisp 1.6 and Portable Standard Lisp.  The only
Lisps that exist now that have a single integer representation appear
to be subsets that do not support infinite-precision arithmetic (for
example, XLisp and A-Lisp).

A number of implementations place constraints on the size of integers
apart from memory availability.  For example, the maximum number of
bits may be constrained to fit in a fixed-length field. 


Cost to implementors:

Slight.  All implementations I know of already define FIXNUMs to be at
least 16 bits and would only have to remove the BIGNUM type specifier
(or document it as an extension to the language) to be in compliance
with the proposal.


Cost to users:

Slight.  The removal of the BIGNUM type specifier will affect user code
but it appears to be little-used.  Code which assumes that the values of
the constants MOST-POSITIVE-FIXNUM and MOST-NEGATIVE-FIXNUM are fixnums
would have to be changed to allow for the fact that they might be NIL.


Benefits:

The FIXNUM type specifier would have a portable interpretation.

Introducing a new constant to describe the maximum size of integers makes
it possible to describe an implementation's exact limitations on the range
of integers it supports.  This constant would also be useful for the
description of subset implementations.


Discussion:

An earlier proposal on this issue to remove the FIXNUM type specifier
entirely was almost universally hated.

Masinter and Fahlman expressed agreement with the general direction of
the current proposal.  Pitman would like to see the range of FIXNUMs
remain undefined and a SMALL-INTEGER type with a fixed range (but no
promises about efficiency) introduced.  JonL would like to see a
guarantee that the value of the constant ARRAY-TOTAL-SIZE-LIMIT be a
fixnum (for efficient array addressing on stock hardware). 

Dalton suggests that the FIXNUM type should be made analagous to the
"int" type in C.  While the original K&R definition of C didn't
guarantee anything about integer sizes, the ANSI C standard requires
ints to be at least 16 bits long.

Addition of the MAX-INTEGER-LENGTH constant was suggested by Stan Shebs.
-------