&Rest Lists

[mike%acorn@oak.lcs.mit.edu (mike@gold-hill.com after 1-April-88)]

    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.  

This "analysis" stuff is not really valuable.  Without global program
knowledge, the vast majority of these cases will be undecidable. If
you pass any cons of the rest arg to any function, and return the
value of any other function, then you can't decide it because the two
functions could communicate via shared state: e.g.,

--> file 1:
  (let ((shared-state nil))
    (defun bar (x)
       (setq shared-state x))
    (defun foo ()
        shared-state))
  
--> file 2:

  (defun test (&rest arg)
    (bar arg)
    (foo))

Clearly, TEST returns its rest arg, and the only way for the compiler
to know this is to have global knowledge of the functions FOO and BAR
The only way around this is to re-write test:

   (defun test (&rest arg1)
    (let ((arg (copy-list arg1)))
      (bar arg)
      (foo)))

Which is exactly what you have to do to eliminate sharing when the 
default is to allow sharing. (Note that in this case, the compiler
could infer that arg1 could be a "stack-list" :-)  

My point: relying on the compiler to "infer" stuff that should be
directly expressable is a bad idea. It should be clear that if
the default is to share rest-arg conses passed by apply, one 
can get the desired behavior possibly at the cost of having to
call copy-list. If the default is to copy, then in most cases,
the compiler will not be able to eliminate the copying and there
will be run-time cost. 

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

Having mulitple function entry points to support different calling
conventions sounds like a good strategy to exploit compile-time
knowledge of the structure of the called function. A classic example
of this is for type-checking. If checked and unchecked entries are
available, then the compiler can set up an unchecked call if the
types are known to be correct. There need be no run-time set-up or
overhead.
    
...mike beckerle
Gold Hill