implementing multiple values

[David A. Moon <Moon at SCRC-TENEX at MIT-MC>]

    Date: 13 Nov 1982 2117-EST
    From: HEDRICK at RUTGERS (Mgr DEC-20s/Dir LCSR Comp Facility)

    E.g. consider the following example from Maclisp:
    (multiple-value-list (progn (values 'a 'b 'c) nil)) --> (nil b c)

Certainly the only sane and rational definition is that returning one
value by traditional Lisp and returning one value by using VALUES with
one argument must do the same thing.  The Maclisp implementation of
multiple values is broken; this is because it was kludged into an existing
implementation as a set of macros.

    It seems fairly clear that this should return either (nil) or (a b c).

The former.

    Probably the last two definitions are going to require that every
    value computation will interact with the m.v. mechanism, an overhead
    I would like to avoid.

Certainly.  But there is no run-time overhead, there is only the overhead of
making the interpreter and the compiler understand multiple values, rather
than kludging them in on top.

    (defun foo nil (values a b c))
    (defun bar nil (foo))
    (defun baz nil (multiple-value-list (bar]

(foo) and (bar) return the same 3 values, (baz) returns a list of them.

    (defun baz nil (multiple-value-list
		     (cond ((moon-phase) (foo))
			   (t  (trunc 5 2]

(baz) returns a different number of values depending on the predicate.

    (defun bar nil (cond ((moon-phase) (foo))
			 (t (trunc 5 2]
    (defun baz nil (multiple-value-list (bar]

This is the same as the previous example.

    (defun baz nil (multiple-value-list (progn (foo]

progn makes no difference.

    (defun baz nil (multiple-value-list (progn (foo) nil]

This returns a list of one element, NIL, of course.

You left out the only case that isn't obvious, namely

    (prog1 (foo) (bleagh))

I believe the current c.l. definition is that this returns one value, a,
and multiple-value-prog1 also exists and returns three values.


Maybe it would be instructive to look at how the Lisp machines (both of
them) implement multiple values.  Although these are machines specially
microcoded for Lisp, there is nothing microcode-dependent about this.
There is no extra overhead when multiple values are not being used.

When a function is called by a multiple value receiving form, a bit is
set somewhere in the stack frame.  This bit is in a place that gets
cleared for free when a function is called expecting only one value.
When a function is called tail-recursively, another bit is set.  When a
single value is returned from a function, these bits can be ignored.
When multiple values are returned, the microcode for that (and it could
just as well be a run-time support routine) follows back through
tail-recursive calls until it reaches the guy who is going to receive
the values, then checks his bit to see whether he wants multiple values.
If so, all the values are returned; if not, only the first value is
returned.

In practice there are some complexities about just where the values sit
while the stack is being unwound.  But these don't affect the semantics,
depend on implementation details, and in fact differ between the "A" and
"L" varieties of Lisp machines.  On a machine with enough general registers,
such as the pdp-10 or the VAX, you would probably put the values there.

Function-calling takes care of all cases of multiple values.  In the
interpreter, the function is always EVAL.  In compiled code, if the <form>
argument to MULTIPLE-VALUE or MULTIPLE-VALUE-BIND does not compile into
a function call, the compiler expands out the multiple value passing.
Thus (MULTIPLE-VALUE-BIND (A B C) (VALUES D E F) body) is just LET.