&Rest Lists

[ELIOT@cs.umass.edu]

   From:	IN%"Moon@SCRC-STONY-BROOK.ARPA"  "David A. Moon" 20-MAR-1988 08:07
   Subj:	&REST args
   
   For the record, I strongly disagree with this.  I believe Common Lisp should
   specify that the value of an &REST parameter is permitted, but not required,
   to share structure with the last argument to APPLY.  I have two reasons for
   this belief (both of which have come up on the mailing list before).

I disagree with this.  As I stated in an earlier message I think that Common
Lisp should prohibit sharing of list structure in the last argument
to APPLY.
   
   1. In no other place does Common Lisp automatically unshare structure,
   except when the user is explicitly modifying the structure (as in REMOVE).
   Making APPLY automatically unshare would be a semantic wart.

Common Lisp does commit itself to doing whatever has to be done so that
interpreted and compiled code behaves the same.  Actually I don't care
whether that last argument to APPLY can be shared.  But I stongly
believe that Common Lisp should do whatever has to be done so that
all variants of the same function call are equivalent.  Consider:

(setq x '(1 2 3))

[1] (apply #'foo 1 2 3 NIL)
[2] (apply #'foo 1 2 (cddr x))
[3] (apply #'foo 1 (cdr x))
[4] (apply #'foo x)
[5] (funcall #'foo 1 2 3)
[6] (eval (cons 'foo x))
[7] (eval (list 'foo 1 2 3))
[8] (foo 1 2 3)

I strongly believe that all of [1-8] are the same function call and
must have the same semantics.  Since the list, x, cannot be modified by
[1, 5, 7, 8]  it should not be allowed to modify it in [2, 3, 4, 6].

   2. If APPLY copies its last argument, recursive programs that receive an
   &REST argument and pass it to APPLY become inefficient.  A linear time
   algorithm can change to a quadratic time algorithm.  While the efficiency
   could be regained through compiler flow analysis in many cases, I think
   it's better not to put the inefficiency into the language in the first
   place.

Using APPLY is probably inefficient anyhow.  If this kind of recursive
function has to run quickly it would probably be better to define an
auxillary function with a fixed number of arguments to do the real work.
Besides, most function calls are not made using APPLY.  Recursive
function calls using APPLY are too rare to justify a blemish in the
semantics of all function calls.

Common Lisp already has a large number of undefined cases.  I don't
think that a possible minor optimization of a special case of using
APPLY is sufficiently important to justify allowing any ambiguity in the
semantics of &Rest lists.  Especially since it is acknowledged that a
good compiler can probably implement the unambiguous semantics equally
efficiently.

Some might argue that the correct way to disambiguate this situation is
to specify that APPLY must share its final argument with any &Rest list
argument as much as possible.  This doesn't make sense to me.  I don't
believe that it would make Common Lisp more efficient to any significant
degree.  I think it creates an undesirable inconsistency in the
semantics of function calls, as I argued above.  Furthermore, modifying
&Rest lists as a way to indirectly modify some argument to APPLY sounds
like one of the worst dirty programming tricks I have heard of in a long
time.  The possibility of causing exceedingly obscure bugs makes my skin
crawl.