&Rest Lists

[Barry Margolin <barmar@Think.COM>]

   Date: Thu, 24 Mar 88 17:12 EDT
   From: ELIOT@cs.umass.edu

      From: Barry Margolin <barmar@think.COM>
      To: ELIOT@cs.umass.EDU

   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.  

What extra function call?  I would hope that the compiler will inline
code calls to APPLY.  (apply #'foo '(1 2 3)) should generate code at
least as good as (foo 1 2 3), and the only difference between (apply
#'foo '(1 2 3)) and (apply foo '(1 2 3)) should be whether it extracts
the function from FOO's function or value cell.  In the implementation
I use (a Lispm), APPLY is a single instruction.  The only extra
inefficiency that APPLY might incur is the one YOU are advocating --
copying its last argument -- which makes your reasoning circular.

						    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.

Well, I know that I use APPLY a whole lot.  Not as often as LIST and
CAR, certainly, but more often than I would have expected.

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

These solutions only work for built-in functions.  Portable code can't
call FORMAT-1.  I certainly could make non-&rest versions of my
functions, but this means that I must write two functions when I
previously would have written only one, and if I make all my &rest
functions just invoke the non-&rest versions I also incur an extra
function call (like you thought was inherent in using APPLY).

Also, if you were going to do

	(apply #'format str fmt arg2 rest)

and you recoded it to call FORMAT-1, you end up with

	(format-1 str fmt (cons arg2 rest))

Actually, this last argument isn't as compelling as I first thought,
because it only reduces efficiency in implementations that cons &rest
lists on the stack, and we've decided that they are violating the
standard by doing this.

I think these are good efficiency justifications for making the
sharing behavior of &rest lists and list given to APPLY be undefined.

						barmar