Issue CONSTANT-COLLAPSING Writeup

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:		Ready for release



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.