Status:Passed Jan 89 X3J13, as amended

Issue:FIXNUM-NON-PORTABLE

References:CLtL p. 14, 34, 43, 231

Category:CHANGE, CLARIFICATION

Edit History:Version 1, 11-Jul-88, Sandra LoosemoreVersion 2, 15-Sep-88, Masinter

Version 3, 23-Sep-88, Masinter

Version 4, 7-Dec-88, Masinter (two proposals)

Version 5, 16-Mar-89, Masinter (incorporate amendments)

Version 6, 17-Mar-89, Masinter (incorporate amendments correctly)

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

fixnumtype that are portable, given thecurrent definition. In particular, many programmers use

FIXNUMtypedeclarations where they really mean "small integer".

While most Common Lisp implementations have a

FIXNUMrangewhich is a subset of integers represeted and operated on most

efficiently, many also have several other subranges. The

partitioning of

INTEGERintoBIGNUMandFIXNUMis merelyconfusing in these implementations, and not useful.

CLtL p14 and p34 disagree about

BIGNUM. One says that

FIXNUMandBIGNUMare an exhaustive partition of theinteger space, the other says they might not be!

Proposal: FIXNUM-NONPORTABLE:TIGHTEN-DEFINITION

(1) Change the description of the type

FIXNUMto reflect that it isrequired to be a supertype of (

SIGNED-BYTE16).

(2) Define

BIGNUMto be exactly (ANDINTEGER(NOTFIXNUM))

(3)

requirethat (<=ARRAY-DIMENSION-LIMITMOST-POSITIVE-FIXNUM)

Example:

Consider an implementation with three numeric representations:

Fast (

INTEGER-1024 1023)Immediate 29 bits

Extended Multi-precision

Such an implementation would have to define

FIXNUMto be (ORFast Immediate).BIGNUMwould then refer to multi-precision integers.

Rationale:

Many programmers already use

FIXNUMto mean "small integer"; thisproposal makes this usage portable.

However, there is little portable use for the type

BIGNUM, and itis inconsistent with many current implementation techniques.

Removing it is an incompatible change for a weak reason.

Current Practice:

Xerox Common Lisp has 17-bit fixnums. Most other Common Lisp

implementations have

fixnumranges of 24 bits or larger. We knowof no implementation that currently violates the proposed minimum

size.

Several existing Common Lisp implementations have more than two

representations for integers, such that the FIXNUM/BIGNUM distinction

is confusing; they define

BIGNUMto cover all of the larger numbertypes.

Cost to implementors:

Slight. All implementations we know of already define FIXNUMs to be at

least 16 bits.

Cost to users:

Slight.

Benefits:

The

FIXNUMtype specifier would have a portable interpretation.

The language would be less confusing.

Discussion:

There was little consensus on whether to leave

BIGNUMin the language.

Earlier discussion of a related proposal contained several other more

controversial components (adding a constant MAX-INTEGER-LENGTH, allowing

MOST-POSITIVE-FIXNUMto beNILas well as an integer.) This proposalis an attempt to address the part that cleanup committee seemed to agree

on.

It is possible that an implementation have a single representation for all

integers, and no way to identify any efficient range of integers. Those

implementations might need to set

MOST-POSITIVE-FIXNUMand

MOST-NEGATIVE-FIXNUMto arbitrary values, consistent withthe requirement that (

SIGNED-BYTE16) is a subtype ofFIXNUM.

Other alternatives considered (and not necessarily mutually exclusive

with this proposal):

remove the

FIXNUMtype specifier entirely, while leaving a wayto query what is the most efficient range of integers

leave the range of FIXNUMs unconstrained and introduce a

SMALL-INTEGER type with a fixed range (but no promises about

efficiency) .

It might be possible to specify the required performance behavior

of FIXNUMs more concretely, e.g., specify 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

fixnumrange as it is to add, say, 10 and 11. This might be a useful way to

describe

the intent of the

FIXNUMrange, if not its specification.