issue QUOTE-MAY-COPY, version 3

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

Here is the latest and greatest version.  The major addition is that I
have greatly expanded the discussion section.  The only change to the
proposal part is that I have added wording to clarify how this relates
to the the other proposals on constants, in response to an earlier
suggestion. 


Forum:		Compiler
Issue:		QUOTE-MAY-COPY
References:	CLtL p. 55, 78, 86, 143
		Issue CONSTANT-COLLAPSING
		Issue CONSTANT-COMPILABLE-TYPES
		Issue CONSTANT-MODIFICATION
Category:	CHANGE/CLARIFICATION
Edit History:   V1, 5 Dec 1988, Sandra Loosemore
		V2, 10 Dec 1988, Sandra Loosemore
		    (comments from Dalton, JonL)
		V3, 3 Jan 1989, Sandra Loosemore
		    (comments from Pitman et al)
Status:		**DRAFT**


Problem Description:

May QUOTE return a copy of its argument?  In particular, is it
permissible for COMPILE to copy quoted constants to read-only
memory, or to coalesce equivalent constants?


Background:

CLtL p. 86 states that (QUOTE <x>) simply returns <x>.  On
p. 55 it is mentioned that the only self-evaluating forms that may
be copied are numbers or characters.   It is also stated that an
implementation is permitted to collapse (or coalesce) EQUAL constants
appearing in code to be compiled.

Because of its nature as a file processor, COMPILE-FILE generally must
cause copies of constants to be constructed when the compiled code is
loaded.  In a number of existing Lisp implementations, COMPILE also
causes constant objects to be copied and/or coalesced.  Since it is
permissible for an implementation to implicitly compile even
"interpreted" code (p. 143), the semantics of constants seen by EVAL
may also be affected if the in-memory compiler (as well as the file
compiler) is allowed to copy or coalesce constants. 

The arguments for allowing constants to be copied can be summarized
briefly as follows.  Copying constants to read-only memory can result
in less work for garbage collectors.  If there is hardware support for
write-protection of memory, this may also be used to cause an error to
be signalled if an attempt is made to modify the constant.  Coalescing
equivalent constants can lead to significant memory savings in some
applications (although this savings is likely to be less for individual
functions compiled with COMPILE than entire programs compiled with
COMPILE-FILE).

The primary argument against allowing constants to be copied or
coalesced is that doing so causes information to be lost, and in the
case of COMPILE and EVAL, there is no inherent reason why this
information must be discarded.  Some people also feel that allowing
QUOTE not to return a value that is EQ (or even EQL) to its argument
would be a substantial, incompatible change from its "traditional"
semantics. 


Proposal QUOTE-MAY-COPY:ALWAYS:

  Change the description of QUOTE to indicate that (QUOTE <x>) returns
  an object equivalent to <x>, which may or may not be EQ to <x>.  
  Likewise, a self-evaluating form may also return an equivalent copy 
  of the object.

  The equivalence relationship is defined in the writeup for issue
  CONSTANT-COMPILABLE-TYPES, and only those objects for which this
  relationship is defined may appear as quoted or self-evaluating
  constants.  The restrictions placed on compiled constants in
  issue CONSTANT-CIRCULAR-COMPILATION apply to constants in code 
  processed by EVAL and COMPILE, as well as COMPILE-FILE.  EVAL and
  COMPILE may also coalesce constants, as described in issue 
  CONSTANT-COLLAPSING.

  If an implementation chooses to copy constants, the copying may only
  happen once each time the form containing the constant is processed
  with COMPILE or EVAL (see examples below).

  Rationale:

  This proposal would make the treatment of constants uniform across
  COMPILE-FILE, COMPILE, and EVAL.


Proposal QUOTE-MAY-COPY:NOT-EVAL-OR-COMPILE:

  Clarify that self-evaluating forms and quoted constants always
  evaluate to objects that are EQL to the original, except in the case
  of code compiled with COMPILE-FILE (where an equivalent but possibly
  non-EQL object is returned).  The restrictions on compiling constants
  in issues CONSTANT-COMPILABLE-TYPES and CONSTANT-CIRCULAR-COMPILATION
  apply only to COMPILE-FILE.  Only COMPILE-FILE may coalesce constants
  (issue CONSTANT-COLLAPSING).

  Rationale:

  This proposal is the most consistent with the semantics described in
  CLtL.  It would make the treatment of constants uniform across
  COMPILE and EVAL.


Proposal QUOTE-MAY-COPY:NOT-EVAL:

  Clarify that quoted or self-evaluating constants appearing in code
  processed by EVAL must return an object that is EQL to the original.
  In functions that have been compiled with COMPILE or code that has
  been compiled with COMPILE-FILE, an equivalent (but possibly
  non-EQL) copy of the object may be returned instead.

  The equivalence relationship is defined in the writeup for issue
  CONSTANT-COMPILABLE-TYPES, and only those objects for which this
  relationship is defined may appear as quoted or self-evaluating
  constants in code to be compiled.  The restrictions on constants
  described in issue CONSTANT-CIRCULAR-COMPILATION apply to both
  COMPILE-FILE and COMPILE, and both may coalesce constants as
  described in issue CONSTANT-COLLAPSING.  There are no restrictions 
  on what kinds of objects may appear in code processed with EVAL, and
  EVAL may not coalesce equivalent constants.

  If an implementation chooses to copy constants, the copying may only
  happen once each time the form containing the constant is processed
  with COMPILE (see examples below).

  Rationale:

  This proposal is the most consistent with current practice.


Test Cases/Examples:

#1: (Behavior of COMPILE)
    
    Suppose the function FOO is defined:

        (defun foo () '(a b c))

    Under all three proposals, multiple calls to FOO must always return
    EQ values, regardless of whether FOO is interpreted or compiled:

        (eq (foo) (foo))  ==> true

    Proposals ALWAYS and NOT-EVAL allow FOO to return a "different" EQ
    value after it is compiled:

        (setq old-foo (foo))
        (compile 'foo)
        (eq old-foo (foo)) ==> ??? under ALWAYS or NOT-EVAL
			       true under NOT-EVAL-OR-COMPILE


#2: (Behavior of EVAL)

        (let ((x  '(a b c)))
	    (eq x
	        (eval (list 'quote x))))

    Under proposal ALWAYS, this may or may not return true.  Proposals
    NOT-EVAL-OR-COMPILE and NOT-EVAL guarantee this to return true.

        (let ((x  '(a b c)))
	    (eq (eval (list 'quote x))
	        (eval (list 'quote x))))

    Under proposal ALWAYS, this may or may not return true (each call to
    EVAL may construct its own copy of X).  Proposals NOT-EVAL-OR-COMPILE
    and NOT-EVAL guarantee this to return true.


Current Practice:

Implementations in which COMPILE copies constants include PSL/PCLS and
Kyoto Common Lisp.  In Lucid Common Lisp, constants are not normally
copied by COMPILE, but since COMPILE does coalesce constants, it may
cause QUOTE to return an object which is not EQL to its original
argument.

There do not appear to be any implementations in which constants are
copied by EVAL.


Cost to implementors:

Proposal QUOTE-MAY-COPY:NOT-EVAL-OR-COMPILE would cause significant
problems for some implementations.  For example, PSL/PCLS would
require major changes to its memory management scheme and garbage
collector as well as the compiler to bring it into compliance.

Proposal QUOTE-MAY-COPY:NOT-EVAL could potentially cause problems for
compiled-only implementations in which the in-memory compiler normally
coalesces or makes copies of constants.  There does not appear to be
any existing implementation that would be affected. 

Note that neither QUOTE-MAY-COPY:ALWAYS or QUOTE-MAY-COPY:NOT-EVAL
-require- constants to be copied or coalesced; neither proposal would
require changes to those implementations that currently don't touch
constants.


Cost to users:

Proposals QUOTE-MAY-COPY:ALWAYS and QUOTE-MAY-COPY:NOT-EVAL would have
the result of explicitly stating that programs which depend on COMPILE
preserving EQLness of constants are nonportable.  (This is the de
facto situation now.)  Such programs could continue to work in those
implementations in which COMPILE does not copy or coalesce constants. 

The impact of allowing constants to be copied in interpreted code
(proposal QUOTE-MAY-COPY:ALWAYS) is unknown.  It could be argued that
any code that depends on constants not being copied or coalesced is
broken, since it would not work when compiled in some implementations. 


Benefits:

The semantics of QUOTE are clarified.


Discussion:

There has been some confusion about the names of the proposals.  Note
that proposal QUOTE-MAY-COPY:ALWAYS implies that copying is always
*permitted*, but is not required under any circumstances.

This issue has caused a very lengthy debate on the cl-compiler mailing
list, with no consensus arising yet.  Following are comments
summarizing various people's positions.

Jeff Dalton says:
  Just to make this clear, I currently favor [proposal NOT-EVAL-OR-COMPILE]:
  would like to have EQL-identity preserved except when file operations
  are involved.

Kent Pitman originally supported NOT-EVAL-OR-COMPILE, but now says:
  I asked Moon about his feelings on this. He thinks pretty strongly that
  the ALWAYS option is the only practical one to pursue. Partly, he says,
  because it's maximally compatible with current practice and partly
  because it avoids making COMPILE-FILE seem different.

  In principle, I favor option ALWAYS, permitting copying of quoted 
  structure to a constants area in any of EVAL, COMPILE, or COMPILE-FILE
  situations, as appropriate to the implementation.
    
  It should not be concluded from this that I favor restrictions on the
  kinds of data which may be quoted, however. The wording of option ALWAYS
  should be ammended to say that such copying is permitted only when the
  system can reliably deduce whether such copying is `appropriate,'
  and avoid it in cases where it is not. The purpose of such wording would
  be to avoid placing restrictions on what kinds of structures a user can
  or cannot quote.
    
  So, for example, if an implementor cannot in some context figure out how
  to detect circularities in quoted structure in order to either decline
  copying or correctly copy the circular form, then the implementation is
  not permitted to attempt copying in such contexts.
    
  Note however that because of special considerations forced by the external
  representation of data in compiled files, I go along with (and encourage)
  the establishment of a known subset of types which can be quoted (or used
  as self-evaluating constants) in code to be reliably processed by the file
  compiler. Coincidentally, such restrictions might make it easier for an
  implementation to know whether copying was going to succeed in the case of
  loading compiled code from a file, but technically these restrictions are
  not motivated by any consideration of what kinds of structures might or 
  might not be possible to QUOTE.

  My inclination is also to believe that copying should not be done
  repeatedly, and we should find a way to express this. That is, repeated
  execution of code in the same execution environment should return an EQL
  result (or some such). This is important to guaranteeing efficiency. Even
  in copying implementations, it is not necessary that such constants be
  allocated in a  read-only area or some such to achieve this effect. For
  example, quoted structure could be placed in a special array and QUOTE 
  could be implemented using AREF. What is important is that any of these
  permissions we give for copying not be taken for a license that QUOTE
  should be implemented by COPY-TREE or some other operation which cannot
  be done in constant time.


Dan Pierson says:
  I also support QUOTE-MAY-COPY:NOT-EVAL-OR-COMPILE.  In the absence of
  overwhelming opposing reasons, we should not diminish traditional Lisp
  functionality.  While NOT-EVAL may be more in line with current
  practice of a couple of implementations, the argument that these
  implementations are already broken is at least as strong as the
  argument that we shouldn't break them by pointing out that they don't
  conform to the language standard.

  However, my position on this is not unalterable.

Sandra Loosemore says:
  I oppose NOT-EVAL-OR-COMPILE on the grounds that it differs from current 
  practice and would involve a substantial conversion cost for some 
  implementations; either of the other two alternatives would be acceptable 
  instead since they involve essentially no conversion cost for either 
  implementors or users.  I am not convinced that the modifications to
  proposal ALWAYS suggested by Pitman wouldn't cause just as much work
  for some implementations as forbidding copying entirely.  If the 
  modifications applied only to the behavior of EVAL and not COMPILE, that 
  would be OK.

  Many people have referred to "tradition" in their arguments on this
  issue.  Different implementations have different traditions, and what 
  seems "broken" to one person may seem perfectly natural to another 
  person who comes from a different background.

JonL White says:
  I favor giving as much leeway as possible to 
  the implementors for making memory-management optimizations.  While one
  implementor may choose not to do any such work, and another may even go 
  out of his way to assure EQLness over an unlikely set of circumstances,
  this should not constrain the third from doing the "classic" thing.  In
  short, I don't see the value of adding constraints that
     (1) invalidate much existing practice, and
     (2) appear to be purely of theortical value.
  Making "compiled code" (read: compile-file) work as closely as possible to 
  interpreted code is _not_ "purely of theortical value."

  QUOTE-MAY-COPY:ALWAYS is the only proposal that both recognizes the 
  prevalent practice and pays (at least) lip service to the question of
  compiled/interpreted consistency.

Cris Perdue notes:
  My personal intuition is that (potentially) readonly constants are
  created sometime during loading of a compiled file, and that as far
  as a user of the language is concerned, the constants are *created*
  in their coalesced, copied, readonly, or whatever state.

  There may be other self-consistent and reasonable points of view.  This
  point of view makes sense to me, fits CLtL's existing specification of
  QUOTE, and I think satisfies Pitman's concerns.
-------