Issue: REST-LIST-ALLOCATION (Version 3)

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

    Date: Tue, 13 Dec 88 21:15 EST
    From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>

    This is a tough issue.
    .... discussion elided for brevity ....
    On the basis of the reasoning presented above, my position is that we
    should do the following two things:

     - Drop the NEWLY-ALLOCATED and MUST-SHARE variants as practically
       infeasible and ramp up MAY-SHARE.

I strongly agree with this.  MUST-SHARE is out because some implementations
cannot implement it.  NEWLY-ALLOCATED is not as bad, but I want to rebut an
argument that was given in favor of it:

  (defvar *message*)
  (defun set-message (&rest mess)
    (setq *message* mess))
  (let ((winner (list 'a 'winner)))
    (apply #'set-message winner)
    (setf (cdr winner) (list 'loser))
    winner)
  Is *message* (A WINNER) or (A LOSER)?  With MAY-SHARE, the answer is
  implementation-dependent, with NEWLY-ALLOCATED the answer is (A WINNER).

Consider this similar program:

  (defvar *message*)
  (defun set-message (mess)
    (setq *message* mess))
  (let ((winner (list 'a 'winner)))
    (funcall #'set-message winner)
    (setf (cdr winner) (list 'loser))
    winner)
  The answer is (A LOSER).

All I did was change APPLY to FUNCALL, and remove the corresponding
&REST.  I find it inconsistent if calling with APPLY is guaranteed to
copy one of the arguments, but calling with FUNCALL is not.  I think
all the example shows is that programs with side-effects are generally
more difficult to understand than programs without side-effects, and
we certainly won't fix that by tweaking the definition of APPLY.

     - Extend MAY-SHARE to include a mechanism that seriously addresses
       the fact that sometimes we need to get a particular kind of
       functionality. Perhaps declarations like
	 (REST-LIST-SHARING :NEVER)
	 (REST-LIST-SHARING :SOMETIMES)     
	 (REST-LIST-SHARING :ALWAYS)
       or
	 (REST-LIST-ALLOCATION :NEW)
	 (REST-LIST-ALLOCATION :UNSPECIFIC)
	 (REST-LIST-ALLOCATION :SHARE)

Upin reflection, I don't support this part.  I can't understand why a
portable program would ever depend on (REST-LIST-SHARING :ALWAYS),
unless it's going to perform side-effects on the &rest list as a way of
passing information back to the caller.  But I strongly believe that
side-effecting such a list is a really bad idea.  Any program that needs
to create and modify a list should use an explicitly created list that
is passed as a normal argument, not the implicitly created list received
as an &rest argument, in my opinion.  Also, as Kent pointed out there
might be implementations in which (REST-LIST-SHARING :ALWAYS) is
impossible to implement.

The other reason for using (REST-LIST-SHARING :ALWAYS) might be a belief
that it enhances efficiency.  But it seems to me that if sharing was
more efficient than not sharing, the implementation would be doing it
already, and in general the implementor knows better than the PORTABLE
programmer what implementation technique for rest arguments is most
efficient.

This leaves (REST-LIST-SHARING :NEVER).  The only justification for this
I can see that is that the program is going to perform side-effects on
the &rest list and wants them insulated from the caller, and furthermore
doesn't want the overhead of calling COPY-LIST in implementations that
don't share.  This is certainly not as unreasonable as
(REST-LIST-SHARING :ALWAYS), but it's still pretty specialized.  I have
two objections to doing this with a declaration rather than with
imperative code.  First: why should

  (defun foo (&rest x)
     (declare (rest-list-sharing :never))
     (remf x :frob)
     ...)

compile into different instructions than

  (defun foo (&rest x)
     (setq x (copy-list x))
     (remf x :frob)
     ...)

An implementation that never shares can easily notice the redundant
call to COPY-LIST and remove it.  All we need is a hint to programmers
and implementors that this is an expected optimization.

Second: declarations other than SPECIAL declarations are supposed to be
"completely optional and correct declarations do not affect the meaning
of a correct program."  A declaration about rest-list-sharing that
makes it valid to perform side-effects on a rest-list clearly does not
fit this dictum of CLtL.  On the other hand, if even with the declaration
it is still not correct to perform side-effects on a rest-list, then
I don't see any use for (REST-LIST-SHARING :NEVER); it can only make a
program slower.

In conclusion, REST-LIST-ALLOCATION:MAY-SHARE without additional
declarations is the only proposal that I find viable and consistent
with the rest of Common Lisp.