issue CONSTANT-CIRCULAR-COMPILATION, version 3

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

I have merged versions 1 and 2 (which was labeled version 1), and
attempted to summarize the discussion.  We seem divided on this issue
so I think it would be reasonable to present both alternatives to the
full committee.  There are other possibilities as well -- for example,
we could require the compiler to support sharing but not circularity
(which would help with the uninterned symbol problem already noted for
issue CONSTANT-COMPILABLE-TYPES) , say "signals an error" instead of
"is an error", and the like.  Let me know if you have suggestions.



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)


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.


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: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 not required to
preserve EQness of substructures.

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.

  *PRINT-CIRCLE* is also not required to detect EQness of substructures.


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.


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 supports issue 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.  There is less reason for
not requiring shared references in ordinary quoted constants to be
preserved than for disallowing circularity, but we would have to
define the scope over which such sharing would have to be detected.
-------