Issue CONSTANT-CIRCULAR-COMPILATION Writeup

Option YES passed 17-0-1 at meeting of Mar-89.

-----

Forum:		Compiler

Issue:		CONSTANT-CIRCULAR-COMPILATION

References:	Issue CONSTANT-COLLAPSING

		Issue QUOTE-SEMANTICS

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)

                V7, 11 Mar 1989, Sandra Loosemore (error terminology)

		V8, 18 Mar 1989, Sandra Loosemore (changes per Moon, Masinter)

Status:		Ready for release



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 EQL substructures; that is, whether

subobjects that are EQL in the source code must remain EQL after being

compiled.


The proposals below apply to constants appearing in a file compiled by

COMPILE-FILE.  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 EQLness" means that

subobjects that are EQL in the source code must remain EQL after being

compiled; that is, things don't get "less EQL" after compilation.

(Note that coalescing of constants implies that things may get "more

EQL".)



Proposal CONSTANT-CIRCULAR-COMPILATION:NO


State that conforming programs must not contain circular objects

appearing as constants to be compiled.  The consequences of compiling

a program containing such an object with COMPILE-FILE and/or LOADing

the output produced by COMPILE-FILE for such a program [and, if we

accept proposal QUOTE-SEMANTICS:SAME-AS-COMPILE-FILE, compiling it

with COMPILE or evaluating it interpretively] are undefined.


State that the compiler is not required to preserve EQLness 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 conforming programs must not contain circular objects

appearing as constants to be compiled.  The consequences of compiling

a program containing such an object with COMPILE-FILE and/or LOADing

the output produced by COMPILE-FILE for such a program [and, if we

accept proposal QUOTE-SEMANTICS:SAME-AS-COMPILE-FILE, compiling it

with COMPILE or evaluating it interpretively] are undefined.


State that the compiler is required to preserve EQLness 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 EQLness 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 EQLness 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 EQLness 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

EQLness 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.


Portable CommonLoops reportedly requires EQLness of uninterned symbols

to be preserved across a file, and would break under proposal NO.

According to Cris Perdue:


  I am told that support for PCL requires the kinds of guarantees about

  uninterned symbols [that say EQLness will be preserved].  Jim Kempf

  here at Sun tells me he believes that this is true.  John Foderaro

  said that Franz made their compiler give this behavior in order to

  support PCL.


  Jim Kempf says he believes that certain GENSYMs appear in multiple

  pieces of initialization code across a file in PCL, and the

  initialization code only works if symbols EQ at compile time map to

  symbols that are EQ at load time.



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.


Since it is usually fairly simple to detect circular constants,

Loosemore would support an amendment to proposals NO and

PRESERVE-SHARING-ONLY to change the word "undefined" to "unspecified",

adding:


  Implementations must either correctly handle the circular reference

  or signal an error.  


This is similar to the language which is already used in proposal

CONSTANT-COMPILABLE-TYPES:SPECIFY.