issue CONSTANT-CIRCULAR-COMPILATION, version 6

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

Here's a new version of the writeup on this issue.  Since nobody has
spoken up for proposal FLAG after our last round of discussion, I've
replaced it with a new proposal YES.

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)
		V5, 06 Jan 1989, Sandra Loosemore (minor wording changes)
		V6, 08 Feb 1989, Sandra Loosemore (replace FLAG with YES)
Status:		**DRAFT**


Problem Description:

CLtL does not specify whether constants containing circular or
recursive references may be compiled.  It is also not clear whether
the compiler must preserve sharing of EQ substructures; that is, whether
subobjects that are EQ in the source code must remain EQ after being
compiled.

The proposals below apply to constants appearing in a file compiled by
COMPILE-FILE, which must inherently.  If proposal
QUOTE-SEMANTICS:SAME-AS-COMPILE-FILE passes, then the same constraints
would apply to all constants.  The minimal scope over which sharing would
be required to be detected is over a single call to EVAL or COMPILE.

In the proposals that follow, "preserving EQness" means that
subobjects that are EQ in the source code must remain EQ after being
compiled; that is, things don't get "less EQ" after compilation.
(Note that coalescing of constants implies that things may get "more
EQ".)


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 require 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:YES

State that objects containing circular references may legitimately
appear as constants to be compiled.  State that the compiler is
required to preserve EQness of substructures within a file compiled
with COMPILE-FILE.

  Rationale:

  Users seem to expect this functionality, and some implementations 
  already provide it.


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.  Neither the Explorer nor Symbolics Genera 7.x detects
EQness of list CDRs.  Lucid handles circular constants correctly.
Franz uses a flag to control whether or not to attempt to detect
circular constants.  KCL handles circular structures, but only detects
sharing of top-level structure (it does not traverse constants to look
for shared substructure).


Cost to implementors:

We know of no implementation that would have to change under proposal
NO.  

For proposal YES, 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
YES would offer users functionality that is currently not portable.


Benefits:

An area of ambiguity in the language is removed.


Discussion:

The issue of compiler speed is largely a red herring on this issue;
the overhead of detecting circularities is generally quite small.  The
main question is whether we should require some implementations to
completely redo their compiler/loader interface in order to support
circular constants.  

It has been argued that any "serious" implementation will support
circular constants anyway, because of customer demand.  However, since
there appears to be only one implementation (Lucid) that now
implements proposal YES in its full generality, perhaps the demand for
this feature is not really all that strong.

Earlier drafts of this writeup contained a proposal FLAG which would
have added a variable *COMPILE-CIRCLE*, similar to *PRINT-CIRCLE*.
However, there were unresolved problems about what would happen if the
value of this variable were altered within the file being compiled,
and it was generally agreed that this proposal didn't have any
particular advantages over proposal YES and just introduced
unnecessary hairiness.
-------