&Rest Lists

[ELIOT@cs.umass.edu]

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

Is it an instruction, or a microcoded subroutine?  :-)

   The only extra
   inefficiency that APPLY might incur is the one YOU are advocating --
   copying its last argument -- which makes your reasoning circular.

I looked at both VAXLISP and NIL to see what they do.  Both of these
implementations spread the arguments out on the stack in the calling
function and collect them back into a list when entering the function
with the &Rest argument.  Consequently they might use stack lists,
but they cannot share list stucture as you are proposing.

A normal function call [i.e. (foo 1 2 3)] gets compiled as a series
of individual PUSHES as the arguments are evaluated.  (Equivalently,
memory for the entire set of arguments can be allocated on the stack
and individual values MOVEd into the correct location.)

A function call using APPLY would PUSH the initial arguments and then
call a hand-coded assembly routine to push the rest of the arguments.
Consequently, the state of the stack when FOO is entered is the same
regardless of how FOO gets called, so FOO cannot differentiate
calls moderated by APPLY from normal function calls.  Your APPLY
microprogram might do something similar, and it certainly could.
Calls made using APPLY are not specially optimized.  However, FOO can
be compiled using full knowledge of the body of FOO.  So if FOO does
not return its &Rest list it can be CONSed on the stack.  On a LISPM
you might find it possible to change some type bits in the stack words
to make the arguments PUSHed onto the stack into a CDR-coded list.

While we are discussing such low-level issues, it is worth thinking about
how difficult it is to take advantage of the possibility of sharing 
&Rest lists.  Basically there are two ways to do it.  If you are willing to
give up or tremendously complicate separate compilation you can compile
a function CALL using special knowledge of the definition of the Callee.
For example, a call using APPLY could jump into the middle of the
function entry sequence, after the point where &Rest lists normally
get created.  This would be a major break with Lisp tradition.  Alternatively,
you must use several different calling conventions and pass along 
enough information so that the Callee knows how its arguments have been 
encoded.  This will slow down every function call by the amount needed 
to encode/decode this information, and complicate the implementation
considerably.  Which option do you prefer?

   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.

I don't use APPLY very much.  I am sure that neither of us are
biased because of our programming styles, right?


APPENDIX

The rest of this message is an edited dribble file, showing how NIL
compiles function calls using &Rest arguments.  My comments are
shown /* C Style */ to distinguish them from comments inserted by
the disassembler.  I deleted several screenfuls to shorten the message,
so this does not fully illustrate how much hidden complexity there is
in a function call.

(:OPENED "VAX5::OFFICE$DISK:[ELIOT]FOO.TXT;2") 
(defun foo (&rest x)
  (setf (cadr x) 'bang))

(defun bar (z)
  (apply #'foo z))

(defun baz (a b c)
  (foo a b c))

;[Compiled foo bar and baz.]

(defvar z '(1 2 3))
Z 
(bar z)
BANG 
z
(1 2 3)					;Didn't get side effected.

(disassemble 'foo)
  0:  WORD 1024                 ;Save register(s) FLP
  2:  MOVAL l^-420,FLP
  9:  MINICALL CL$MS_HNDL_RS,(COMPILER:REQ 0)
  13: MINICALL CL$MS_ANDREST_LIST,-8(FP)
  17: MOVL AR1,b^-8(FP)
  21: MOVL b^-8(FP),AR1
  25: MINICALL CL$MS_CDR
  28: PUSHL AR1
  30: MOVL b^4(FLP),AR1         ;'BANG
  34: MINICALL CL$MS_SET_CAR
  37: RET

(disassemble 'bar)
  ...				/* 15 lines deleted */
  41: PUSHL b^-4(FLP)           ;#'FOO
  50: MINICALL CL$MS_STACKIFY	/* The arguments get spread out here */
  54: CALLS R0,@b^8(SP)
  58: RET

(disassemble 'baz)
  /* 13 lines deleted */
  33: PUSHL b^24(AP)
  36: PUSHL b^20(AP)
  39: PUSHL b^16(AP)
  50: PUSHL b^-4(FLP)           ;#'FOO
  55: CALLS s^#6,@b^8(SP)
  59: RET

==============
Vaxlisp is similar.  BAZ essentially compiles into a jump to FOO. BAR
remains complex.
==============