issue CONSTANT-CIRCULAR-COMPILATION, version 4

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

Here's a new version incorporating a new proposal and Cris's suggested
change to the FLAG proposal.

Forum:		Compiler
Issue:		CONSTANT-CIRCULAR-COMPILATION
References:	Issue CONSTANT-COLLAPSING
		Issue QUOTE-MAY-COPY
Category:	CLARIFICATION, ADDITION
Edit History:   V1, 07 Nov 1988, Sandra Loosemore
		V2, 14 Nov 1988, Cris Perdue
		V3, 12 Dec 1988, Sandra Loosemore (merge versions 1 and 2)
		V4, 03 Jan 1989, Sandra Loosemore (add PRESERVE-SHARING-ONLY)
Status:		**DRAFT**


Problem Description:

CLtL does not specify whether constants containing circular or
recursive references may be compiled, or whether the compiler must
preserve sharing of EQ substructures.

The proposals below apply to COMPILE-FILE, since it must inherently
copy structures.  If issue QUOTE-MAY-COPY is resolved in favor of
allowing COMPILE and possibly EVAL to copy structures, the same
constraints would also apply in those situations.  [We would also have
to decide upon the scope over which sharing must be detected in such
situations; the minimal scope would be over a single call to EVAL or
COMPILE.]


Proposal CONSTANT-CIRCULAR-COMPILATION:NO

State that it is an error for an object containing a circular reference to
appear as a constant to be compiled.  State that the compiler is not
required to preserve EQness of substructures.

  Rationale:

  This proposal would not require any existing implementation to change.

  Disallowing portable programs from containing circular constants
  allows compiled file loaders to use somewhat simpler implementation
  strategies (for example, to build constants in a strict bottom-up
  fashion).


Proposal CONSTANT-CIRCULAR-COMPILATION:PRESERVE-SHARING-ONLY

State that it is an error for an object containing a circular
reference to appear as a constant to be compiled.  State that the
compiler is required to preserve EQness of substructures within a file
compiled with COMPILE-FILE.

  Rationale:

  Disallowing portable programs from containing circular constants
  allows compiled file loaders to use somewhat simpler implementation
  strategies (for example, to build constants in a strict bottom-up
  fashion).

  Some programs (such as PCL) have come to depend on COMPILE-FILE 
  preserving the EQness of uninterned symbols, and it is cleaner
  to requiring sharing to be preserved in general instead of making
  symbols be a special case.  Requiring sharing to be preserved still
  allows loaders to build constants bottom-up.


Proposal:  CONSTANT-CIRCULAR-COMPILATION:FLAG

Add to the definition of Common Lisp a special variable:

*DUMP-CIRCLE*						[Special variable]

State that if the (compile-time) value of *DUMP-CIRCLE* is NIL, it is
an error for an object containing a circular reference to appear as a
constant to be compiled.  State that the compiler is required to
preserve EQness of substructures within a file compiled with
COMPILE-FILE when *DUMP-CIRCLE* is non-NIL.  (Note that this differs
 from *PRINT-CIRCLE*, which is not required to detect sharing.)

The initial value of *DUMP-CIRCLE* is implementation-dependent.

  Rationale:

  As with *PRINT-CIRCLE* for printing, writing representations of
  objects to a stream is much faster if the implementation does not
  attempt to support circular, self-recursive, mutually-referential,
  etc. substructure.


Current Practice:

A-Lisp preserves EQness of substructures (since it makes an effort to
collapse isomorphic structures) but signals an error if an attempt is
made to compile a circular constant.  PSL and Utah Common Lisp both
get stuck in an infinite loop if an attempt is made to compile a
reentrant structure.  The TI Explorer compiler is able to reproduce
recursive lists and arrays, but currently hangs in a loop on a
circular list.  Lucid and Symbolics can handle circular constants
correctly.  Franz uses a flag to control whether or not to attempt to
detect circular constants.


Cost to implementors:

We know of no implementation that would have to change under proposal
NO.  For proposal FLAG, some implementations would require sweeping
changes; in some cases a completely different dumper/loader strategy
would have to be implemented.  The cost of proposal
PRESERVE-SHARING-ONLY would fall somewhere in between.


Cost to users:

The situation now is that programs which depend upon circularity or
sharing of substructure being preserved by the compiler are already
nonportable.  Proposal NO simply formalizes the status quo.  Proposal
FLAG would offer users functionality that is currently not portable.


Benefits:

An area of ambiguity in the language is removed.


Discussion:

JonL has argued against proposal CONSTANT-CIRCULAR-COMPILATION:NO, saying

  I don't see any performance justification; and even if there were, I'd
  look at it with a very jaundiced eye, favoring interpreter/compiler
  consistency over nickle-and-dime issues of compiler speed.

Loosemore thinks PRESERVE-SHARING-ONLY is the "right" solution, but
would also support CONSTANT-CIRCULAR-COMPILATION:NO because it is the
most consistent with current practice -- no implementations would be
required to change and no currently portable programs would be
invalidated.  While one could make an argument for this proposal on
the basis of improving compiler speed, the compatibility issue is seen
as far more important.

There was also quite a bit of discussion about how this proposal
relates to the requirement in CLtL (p. 69) about preserving the
EQLness of references to symbolic constants.
-------