Forum:		Compiler
Issue:		CONSTANT-COLLAPSING
References:	CLtL p. 78, 87
		Issue CONSTANT-MODIFICATION
		Issue CONSTANT-COMPILABLE-TYPES
		Issue EQUAL-STRUCTURE
		Issue QUOTE-SEMANTICS
Category:	CHANGE
Edit History:   V1, 07 Nov 1988, Sandra Loosemore
		V2, 12 Dec 1988, Sandra Loosemore
		V3, 03 Jan 1989, Sandra Loosemore
		V4, 06 Jan 1989, Sandra Loosemore
		V5, 11 Mar 1989, Sandra Loosemore
		V6, 22 Mar 1989, Sandra Loosemore (comments from Moon)
Status:		Proposal GENERALIZE passed March 89.


Problem Description:

CLtL states that an implementation is permitted to "collapse" or
coalesce constants appearing in code to be compiled if they are EQUAL.
The definition of EQUAL does not permit coalescing of more general
isomorphic data structures (such as arrays), which is often desirable.

This proposal deals only with changing the test which is used to
determine whether two constants may be coalesced.  Issue
QUOTE-SEMANTICS deals with whether coalescing may be performed only by
COMPILE-FILE, or by COMPILE and EVAL as well.  If proposal
QUOTE-SEMANTICS:SAME-AS-COMPILE-FILE passes, then coalescing could be
performed on all constants.

This proposal uses the terms "source code", "compiled code", and
"similar as constants" that are defined in proposal
CONSTANT-COMPILABLE-TYPES:SPECIFY.

The term "coalesce" is defined as follows.  Suppose A and B are two
objects used as quoted constants in the source code, and that A' and
B' are the corresponding objects in the compiled code.  If A' and B'
are EQL but A and B were not EQL, then we say that A and B have been
coalesced by the compiler.


Proposal CONSTANT-COLLAPSING:GENERALIZE:

State that an implementation is permitted to coalesce constants
appearing in code to be compiled if and only if they are similar as
constants, unless the objects involved are of type SYMBOL, PACKAGE,
STRUCTURE, or STANDARD-OBJECT.


Rationale:

There is little reason why implementations should not be allowed to
perform more general collapsing of objects, since the arguments
against doing so also apply to collapsing of EQUAL objects, which
is already permitted.  The arguments for coalescing of EQUAL data
structures (primarily space reduction) also apply to coalescing of
data structures that are equivalent under a more general coalescing
predicate.

Objects of type SYMBOL and PACKAGE cannot be coalesced because the fact
that they are named, interned objects means they are already as
coalesced as it is useful for them to be.  Uninterned symbols could
perhaps be coalesced, but that was thought to be more dangerous than
useful.  Objects of type STRUCTURE and STANDARD-OBJECT could be
coalesced if a "similar as a constant" predicate were defined for them;
it would be a generic function.  Currently LOAD-OBJECTS only defines how
COMPILE-FILE and LOAD work together to construct an object in the
compiled code that is equivalent to the object in the source code,
and a different mechanism would have to be added to permit coalescence.


Current Practice:

Both PSL/PCLS and A-Lisp collapse isomorphic arrays and structures,
and certain other data types that are defined internally as structures
(RANDOM-STATEs, for example).  Lucid Common Lisp also uses a more
general coalescing predicate than EQUAL.


Cost to implementors:

For implementations that currently coalesce based on EQUAL or that do
no coalescing, there is no associated implementation cost.

For implementations that currently coalesce things that this proposal
forbids them to coalesce (such as STRUCTUREs or uninterned symbols),
the implementation cost is probably small.


Cost to users:

Programs that depend on objects not being coalesced except when they
are EQUAL may break under this proposal.  The only way one would be
able to detect that coalescing has taken place is if objects that were
not EQL in the source file become EQL after compilation; accessors on
the objects would return the same values regardless of whether or not
coalescing has taken place.


Benefits:

Collapsing of isomorphic arrays may lead to significant memory savings
in some applications.


Discussion:

This proposal depends heavily on issue CONSTANT-COMPILABLE-TYPES.

Some people believe that if the definition of EQUAL weren't "broken",
there wouldn't be any need for this proposal.

There is no inherent reason why the "coalescing predicate" must be the
same as the relationship used by the compiler/loader to construct
equivalent copies of objects of constants, but making the same rules
be applied in both situations simplifies the language somewhat.