&Rest Lists

[ELIOT@cs.umass.edu]

   From: Barry Margolin <barmar@think.COM>
   To: ELIOT@cs.umass.EDU
   
       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.

I was using an analogy to try to clarify my line of reasoning.  I am not
saying that Common Lisp should actually specify that APPLY copy the list
structure in its final argument, but I am saying that this may be
required in order to correctly implement the semantics that I fell APPLY
should have.  Good compilers are free to implement APPLY so that it
shares list structure as long as it does not affect the semantics.
Calls to any function which provably does not modify its &Rest lists
could be implemented more efficiently by such a compiler.
   
      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?

Ignore what happened before the actual function call to FOO.  At the
moment FOO actually is called all of its arguments are EQ in all of
these cases.  Obviously, my intuituiton is that a function call should
be completely defined by its arguments but not by the computation that
produced them.  And I believe that the function call makes explicit what
constitutes a distinct "argument", regardless of the function
definition.  Consequently I think that "&Rest x" means that x is a list
of the rest of the argumentS - (plural).  In other words the argumentS
that are collected into an &Rest list are totally distinct.

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

This only applies to interpreted code, not compiled code.  And a real
interpreter can be written using implementation dependant primitives,
so the defined Common Lisp behavior of APPLY has nothing to do with
the real efficiency of anything except explicit calls to APPLY.
Certainly normal function calls need not be effected.

What I mean by saying that "Using APPLY is probably inefficient
anyhow" is that you will incur the overhead of a full extra function
call that probably cannot be optimized away.  Truly efficient code
requires modifying the arguments so that the list is passed directly,
rather than using &Rest lists, so you can eliminate the function call
involved in using APPLY.  
   
   						 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

I agree that modifying &Rest lists is bad programming style.  But I also
think that leaving issues undefined is bad language design, unless there
are very compelling reasons.  Compelling reasons include externally
imposed constraints on an implementation (forcing us to live with
ambiguity in the Common Lisp file system operations) and the possibility
of major optimizations on different types of machines.  Ambiguity in the
implementation of Arrays allows different types of machines to be used
for efficient CL implementations.

The special case of using APPLY to call a function with an &REST
argument fits neither of these categories.  Anything that can be made
more efficient by allowing the last argument of APPLY to be shared as
part of an &Rest list can be implemented MORE efficiently by using a
normal function call directly.  For example, you suggest that FORMAT
like functions could not be implemented efficiently.  They could be
implemented like this:

(defun format (stream fmt &rest args)
  (format-1 stream fmt args))

(defun format-1 (stream fmt args)
  ...)

(defun errror (fmt &Rest args)
  (format-1 *error-io* fmt args)
  (call-debugger))

(defun warn (fmt &rest args)
  (format-1 *error-io* fmt args)
  (when *break-on-warnings* (call-debugger)))

(defun break (fmt &rest args)
  (format-1 t fmt args)
  (break-loop))

etc.