&Rest Lists

[Barry Margolin <barmar@Think.COM>]

    Date: Wed, 23 Mar 88 12:50 EDT
    From: ELIOT@cs.umass.edu

       From:	IN%"Moon@SCRC-STONY-BROOK.ARPA"  "David A. Moon" 20-MAR-1988 08:07
       Subj:	&REST args
   
    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.  

How did the compiler/interpreter distinction enter into this?  No one
has proposed distinguishing them.  In the environment I use, they both
behave the same regarding &rest lists.  And even so, the compiler and
interpreter are allowed to have different ways of dealing with a
situation that is undefined ("is an error", to use CLtL wording),
because portable applications are not permitted to depend on the
behavior in such situations.

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

I disagree with this.  [5, 7, 8] don't even reference the list x, so how
can they be considered the same?  And the difference between [4] and [6]
would be quite obvious if any of the elements of x were objects that
don't self-evaluate, e.g.:

(setq a 1 b 2 c 3 x '(a b c))

(apply #'list x) => (a b c) (which, by the way, should not share
			    structure with x)

(eval (cons 'list x)) => (1 2 3)

       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.  

I sure hope not!  Many implementations of EVAL use APPLY internally for
all function calls, something along the lines of:

(apply (symbol-function (car form)) (mapcar #'eval (cdr form)))

(yes, this is extremely simplified, I know that the real thing is much
more complex).

						 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.

It's not just recursive calls.  Consider all the functions that take
arguments just like FORMAT.  They all call various intermediate
functions, which call other intermediates, and eventually they call
FORMAT itself.  The &rest list shouldn't be duplicated at each call.

Many other functions take &rest arguments that are simply passed on to
other functions using APPLY.

    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.

I don't think anyone is actually suggesting that people intentionally
modify &rest lists.  Personally, I prefer making it be undefined whether
&rest lists share, so programmers aren't tempted to write such code.

                                                barmar