CONSTANT-COMPILABLE-TYPES:SPECIFY, V4

[cperdue@Sun.COM (Cris Perdue)]

Here at last is V4 of the proposal, much cleaned up I think from
before.  I have attempted to respond to as many as possible of the
concerns, complaints, etc., about the previous version, so worry if
something really important to you is not fixed here.

The issue of potential immutability of constants has been removed from
this proposal.  I have not yet finished reassembling that material into
another proposal, and expect to do so by the first of the year.  I do
not intend to change it, just to split it out from this one.

---------------------------------------

Issue:		CONSTANT-COMPILABLE-TYPES
References:	CLtL pp. 56, 77-80, 324
		Issue CONSTANT-MODIFICATION
		Issue CONSTANT-CIRCULAR-COMPILATION
		Issue CONSTANT-ARRAY-ATTRIBUTES
Category:	CLARIFICATION, ADDITION
Edit history:	11/07/88, V1 by Cris Perdue
		11/14/88, V2 by Cris Perdue
		11/22/88, V3 by Cris Perdue
		12/20/88, V4 by Cris Perdue
Status:		DRAFT

Problem description:

CLtL does not specify what objects can be in compiled constants and it
does not say what relationship there can or must be between the
constant passed to the compiler and the one that is established by
compiling and then loading its file.  Relevant remarks in CLtL
concerning file compilation and the definition of QUOTE suggest that
the compiler handles constants in ways that are not actually possible.

Introduction to the proposal:

The proposal CONSTANT-COMPILABLE-TYPES:SPECIFY attempts to spell out
what types can appear in compiled constants, and what it means when
they appear.  Unless stated otherwise, in this proposal where the term
"constant" is used, it means a quoted constant, not a named
(defconstant) constant.

The key is a definition of a form of equivalence between Lisp objects,
"similarity as constants".  Code passed through the file compiler must
behave as though quoted constants in it are equivalent to quoted
constants in the corresponding interpreted "source" code.  This
proposal only concerns quoted constants to be processed by
COMPILE-FILE.

For the benefit of users, this proposal tries to define a fairly large
set of types that all Common Lisp implementations are to handle.  It
also attempts to leave room for implementations to differ.  Some
implementations have made opposing choices because the language
doesn't specify one over the other.  Some implementations already
handle constants that this proposal defines as not legal in Common
Lisp programs, and that is useful to users of those systems.
Different implementors have different amounts of resources to apply to
their system, and implementations differ in their whole approach in
some cases.

We try to set up a framework where some controversies can be defined
clearly and resolved as separate issues.

One of these is the question of when, if ever, to permit "coalescing"
of constants.  Some implementations already take advantage of the
license given on page 78 of CLtL to gain some efficiencies.  This
proposal provides definitions that make it possible to broaden the
conditions where coalescing is permitted.

Another question is whether "circular" constants are compilable.  Most
implementations are capable of supporting circular constants.  Still, this
proposal avoids requiring all implementations to handle circular
constants.  Implementations that do not handle circular constants
presumably also do not make sure that shared structure remains shared,
sort of the opposite of coalescing.  This proposal avoids requiring
shared structure to remain shared across compilation.

Some implementations "lose information" about some constants during
compilation.  We try to limit this proposal enough to reduce the
number of unhappy implementors to a bare minimum.

In this version, the question of immutability of some attributes of
objects in compiled constants is not addressed.  Cris has taken that
material out of this proposal and is constructing a new proposal
covering just that issue.  This proposal does define the concept of
"basic attributes" of various types of objects, and the other proposal
will refer to it, stating that most basic attributes of most types of
objects may be treated as immutable when the object appears in a
compiled constant.

Proposal:  CONSTANT-COMPILABLE-TYPES:SPECIFY

An object may be used as a quoted constant processed by COMPILE-FILE
if the compiler can guarantee that the resulting constant established
by loading the compiled file is "similar as a constant" to the
original, plus a few other restrictions.

A few types, such as streams, are not supported in constants.  In
other words, an object containing one of these is not considered
similar as a constant to any other object.  We say that it is an error
for these objects to appear in a (compiled) constant.  Still some
implementations may support them and define how they are treated.

Some types of objects are treated as aggregate objects.  For these
types, being similar as constants is defined recursively.  We say that
an object of these types has certain attributes, and to be similar as
a constant to another object, the values of the corresponding
attributes of the two objects must also be similar as constants.

This kind of definition has problems with circular or "infinitely
recursive" objects such as a list that is an element of itself.  We
consider the idea of depth-limited comparison, and say that two
objects are similar as constants if they are similar at all finite
levels.  This idea is implicit in the definitions below, and applies
in all the places where attributes of two objects are required to be
similar as constants.

The rest of this proposal consists of a definition of the notion of
two objects being "similar as constants", organized by type, with some
notes about the additional constraints that the compiler must meet:

Number, Character

If either of two objects is a number or character, the two objects
are similar as constants if and only if they are EQL.

(Note that for cross-compilers it is not always possible to satisfy
this requirement for floating point numbers and complex numbers with
floating point parts.  If it is necessary to choose two different
floating point values due to cross-compilation, each value chosen must
be one of the two adjacent, exactly representable numbers such that
the interval between them contains the other number.  Other numbers
and characters are represented exactly, so they can be compared if
they are representable on both architecture, an issue for some
characters.)

Random-state

Only the operations PRINT, MAKE-RANDOM, and RANDOM apply to
random-states.  Let us say that two random-states are functionally
equivalent if applying RANDOM to them repeatedly always produces the
same pseudo-random numbers in the same order.  

Two random-states are similar as constants exactly if copies of them
made via MAKE-RANDOM-STATE are functionally equivalent.

Symbol

A symbol can only be similar to a symbol.  References to symbols are
permitted in any constant.  References to interned symbols are "by
name".  If the symbol is interned, its name and the name of its home
package identify it.

A symbol with a home package is similar as a constant to a symbol when
the names of the symbols and the names of the home packages of the
symbols are similar as constants.  (Both symbols must have home
packages.)  Within a Common Lisp "address space", this implies that
the symbols are EQ.

If a symbol is not interned, i.e. its home package is NIL, it is
treated in a rather special way.  To be similar as a constant to
another symbol, both symbols must be uninterned and have the same
name.

Constants that contain uninterned symbols have to satisfy extra
constraints.  If an uninterned symbol appears in a certain set of
places in one constant, it must appear in the same places in both
constants.  If we consider the set of constants that appear in a file,
in its functions, top level forms, etc., the constants in the compiled
form of the file must be similar, all together, to the constants in
the source.  It is as if there were a constant list with all the
file's constants as members.  These conceptual lists for the source
and compiled versions of a file must be similar as constants.

Package

A package can only be similar as a constant to a package.  References
to packages are permitted in any constant.  References to packages are
"by name": two packages are similar as constants when their names are
similar as constants.  Within a Lisp "address space", packages with
the same name are EQ.

At load time, the package becomes the same as returned by
FIND-PACKAGE, given the package name.  An error is signalled if no
package of that name exists at load time.

OTHER TYPES
-----------

For each of the types listed below, if either object is of the given
type, the two objects are similar as constants exactly if the other is
of that type and the values of all of the specified attributes are
similar as constants.

The attributes listed here can be called the "Basic Attributes" of
objects of each of these types.

Cons	     CAR, CDR.

Array	     For 1-dimensional arrays:
	     LENGTH and ELT for all legal indices.

	     For arrays of other dimensions:
	     ARRAY-DIMENSIONS, ARRAY-ELEMENT-TYPE, AREF for all legal
	     indices.

	     Note that array constants in a compiled file may lack
	     displacement, fill pointers, or adjustability, where the
	     constants in the source had them, but the compiler may
	     not produce constant arrays that have these features from
	     ones that do not.  The point is to make sure that
	     declarations are not violated as a result of compilation.

Structure    Slot values, name of structure type (a symbol reference).

Hash-table   Keys and values.  The table's test is of course unchanged
	     also.  It is an error to compile a constant containing a
	     a hash table that has keys that are similar as
	     constants.

Readtable    Character syntax type for each character in the table;
	     function for each readmacro character, mappings for
	     dispatch macros; whether terminating or nonterminating
	     for each readmacro.

Pathname     Each pathname component

Stream, Compiled-Function
             It is an error for a stream or compiled-function
	     to appear in a compiled constant, but the
	     language may be extended in the future to support certain
	     cases.

Function     Function constants that are not compiled-functions and do
	     not close over any (lexical) variables are permitted in
	     compiled constants.  Two functions are similar as
	     constants when they are operationally equivalent.  Use of
	     global function bindings, global macro bindings, and
	     special variables must be considered external
	     dependencies for this purpose, and constants appearing in
	     the functions need only be similar as constants (at level
	     n-1?).

Generic-function, Method
	     Help is needed from the CLOS committee to determine what
	     to do here.

Standard-object
	     Help is needed from the CLOS committee to determine what
	     do do here.

Rationale:

This proposal appears to reflect user demand and appears not to exceed
the capabilities of most implementations of the language.

Current practice:

This is believed to be very close to compatible with the Franz, Lucid,
Coral, and Texas Instruments implementations.  It is probably
compatible or nearly compatible with other "Lisp Machine"
implementations.

Adoption cost:

Not known.  Probably moderate or low -- for most implementations.  The
cost would be to implementors rather than users since this part of the
language is currently underspecified.  The author believes the cost
will be reasonable for KCL, an implementation where there is some
concern about this issue.

Benefits:

Users would be able to use aggregate objects in constants with
confidence about the behavior of their code.

Conversion cost:

Where this proposal *requires* different behavior than an existing
implementation, there is a conversion cost for users of that
implementation.  It appears that this cost will be small, less than
the cost of leaving things unspecified.

Esthetics:

Since there is no adequate definition at present, a fuller definition
would be more esthetic.

Discussion:

This proposal does leave some user-visible attributes of objects
unspecified across the compile-and-load process, except that they must
be consistent with the attributes that must be retained.  This
situation is a compromise between the desire for full specification on
the one hand, and on the other hand the desire to leave freedom for
different implementations to remain different and to support some
optimizations such as compacting hash tables and "simplifying" arrays.

Proposals will be entertained for tighter specification of datatypes
such as arrays.

The full extension of the concept of coalescing of constants is to say
that they can be coalesced exactly when they are similar as constants.

Comparing functions is hard.  One could define an operation that
converts an interpreted function into a lambda expression.  One could
say that interpreted functions are similar as constants when their
associated lambda expressions are similar in the appropriate sense.
This similarity of lambda expressions would be syntactic, but would
have to allow for possible inline macro expansion.  Other
transformations would have to be prohibited, or the functions would
have to report themselves as compiled.

This proposal seems to deal with the question of how to test whether
constants in different Lisp address spaces are similar as constants.
That appears to be important.

We need someone expert with floating-point computation to review the
discussion of similarity of floating point numbers as constants.

The definition of similarity for random-states supports the
possibility of random states that are immutable because of being in
compiled constants.

Interest has been expressed by a number of people including users, in
support for user-definable "dumping" of CLOS objects and structure
instances.  That seems to be recognized as powerful and important, but
we are looking for an appropriate person to make a proposal or
proposals.

This subsumes the isse CONSTANT-ARRAY-ATTRIBUTES.