results of analyzing answers to my question about m.v.'s

[HEDRICK at RUTGERS]

Having started this discussion on multiple values, I feel some
responsibility to prevent it from going off into unnecessary directions.
What I was trying to do was to determine what was needed to implement
m.v.'s.  Moon's response, as well as a private interchange with Steele,
gave the information I needed.  Since other people seem to share my
original concerns, it seems worthwhile telling everybody the design I
have arrived at from this information. To be honest, I would prefer to
see a definition wherein an m.v. producer is an error unless there was
some m.v. receiver there to receive it. That is easy to implement.  But
I am now convinced that there are designs for implementing the existing
C.L. semantics without incurring unreasonable overheads on conventional
machines.

Let me approach this by successive approximation.

Stage I.  M.v. producer is called only when there is an m.v. receiver
to receive the value.

The Maclisp implementation will work here.  (VALUES A B C) simply saves
away the values of A, B, and C in some global places.  MV-LIST (or
anything else) just takes values from that global places and returns
them.  In most cases this mechanism would suffice taken alone. However
there are a couple of cases (MVPROG1 and MVCALL) where  multiple values
have to be saved while an arbitrary computation is done.  Thus it is
probably best for the values to be stored on a stack.  This will allow
for the possibility that m.v.'s can be done recursively.  The simplest
implementation is to push the number of m.v.'s on the top of the stack.
As long as every m.v. producer has an m.v. consumer, this implementation
should be sound.

Stage II.  The real case.

The problem is that the receiver may not call the producer directly.
Furthermore, we have no way of getting rid of m.v.'s if they are
produced erroneously, e.g.
   (multiple-value-list (values a b c) nil)
Thus I propose the following:

  - VALUES and VALUES-LIST will produce multiple values only if they
	know they are going to be used
  - we establish a protocol that allows us to follow the stack to
	see whether they are going to be used

The trickiest part is the second.  This is going to require some care
in the translator, but I claim that it is not that complex.  We have
three categories of calls:

  - calls where multiple values are required.  These are calls
	made by MV-LIST, MV-BIND, etc. (the m.v. consumers).  If the
	thing called would not normally produce m.v.'s, we need to
	convert the single normal value to a single m.v.
  - calls where multiple values are not allowed.  There are calls
	such as all but the last in a PROGN, where any m.v.'s are
	discarded.
  - calls where m.v.'s are returned if available, but are not required.
	I have it on good authority that the only case where this applies
	is terminal calls, i.e. the last call in a function (last being
	judged in execution, not lexically.  e.g. in
		(defun foo nil (cond (x (bar)) (t (baz]
	(bar) is a terminal call.

Let's ignore the third case for the moment.  All we need is some way to
mark calls so VALUES can tell whether m.v.'s are really going to be
used.  Clearly we want to mark the calls where m.v.'s are going to be
used, as opposed to those where m.v.'s are not going to be used, since
we want the overhead to be confined to users of m.v.'s. On the PDP-10
the obvious way to do this is to put a special instruction after the
call.  One way to do this is to put a particular no-op after each such
call. (Since the PDP-10 has several million kinds of no-ops, we can
afford to use one as a flag.)  Then VALUES would simply look up the
stack and see if its return address points to such a no-op.  As it
happens, we will probably do something a bit trickier.  We will probably
use a call to a routine MAKE-MV.  Thus a call done inside MV-LIST would
look like
  (MULTIPLE-VALUE-LIST (FOO) (BAR))
	CALL FOO	;m.v.'s not needed - nothing special
	CALL BAR	;m.v.'s needed - flag it with CALL MAKE-MV
	CALL MAKE-MV
	CALL MULTIPLE-VALUE-LIST ;do the actual return of the m.v.'s

The idea is that when we return from BAR, we will do a skip return if
we are actually returning multiple values (I will show how that happens
in a minute).  In that case the m.v.'s are left as is.  If we are not
returning m.v's, we do the normal return, and fall into the call to
MAKE-MV.  MAKE-MV is the routine that takes the conventional single
value and stores it away as a single multiple value.  Clearly this is
going to have to be done anyway when m.v.'s are needed, so we might as
well use CALL MAKE-MV as the flag that m.v.'s are required.

Now, we have two ways of implementing this, either of which is fairly
easy:

1) make sure that all terminal calls are compiled as jumps.  This is
a fairly standard optimization.  If done reliably, it guarantees that
the third case I ignored above will never occur.  VALUES will simply
be able to look at the place where it called directly, with no fancy
stack chasing.  If the return address points to CALL MAKE-MV,
VALUES puts the m.v.'s onto the mv stack, and takes the skip return.
Otherwise it returns the first of the m.v.'s, ignores the rest, and
does a conventional return.  If you choose this implementation, then
you will have to look at forms such as MVPROG1, which explicitly pass on
m.v.'s in contexts other than terminal calls.  They will have to
do calls that require m.v.'s, save those m.v.'s, and then themselves
return as VALUES (or any other m.v. producer) would do (i.e. looking
at their return address and throwing away the m.v.'s if they are not
required).

2. Have VALUES detect terminal calls, and simply follow the stack up
until something is found which is not a terminal call.  Otherwise
do things as in 1.  (That is, once you find something other than a
terminal call, look to see whether the return address there points to
MAKE-MV...)  If you choose this implementation there is a simple
modification for handling MVPROG1 and similar forms.  Add yet another
special mark (i.e. a no-op used only for this), call it MVFLAG.

   (mvprog1 (foo) (bar))
	call foo
	mvflag
	push returned value
	call bar
	pop returned value
	return

If somewhere inside FOO there is a call to VALUES, the stack search
will detect MVFLAG as the next instruction after the return address.
MVFLAG will be treated like a terminal call, i.e. the stack search
will continue to see whether the caller of the MVPROG1 really needed
the m.v.'s or not.  If so, they will be put on the m.v. stack, and
then the caller will retrieve them.  (The call to BAR will not be
pass on m.v.'s because of the POP after it.  This POP prevents the
next thing from being a RETURN, and thus prevents it from looking
like a terminal call.)

This mechanism has the advantage that if my informants are wrong, and
there is some context other than terminal calls that preserves m.v.'s,
we can handle it by putting MVFLAG there.

Both of the mechanisms suggested have only slight overhead, and that
overhead exists only if m.v.'s are used.  The extra no-op's are used
only in code compiled for m.v. receivers (or constructions such as
MVPROG1 that explicitly protect m.v.'s).  The m.v. producers need
only look up the stack to see what to do.  m.v.'s are never produced
if they are going to be thrown away.  I think that these mechanisms,
or something closely related, should work on machines other than the 
PDP-10.

I am not pleased with this sort of hackery, but it is no worse than
that needed to implement default arguments, &REST, and funarg's.
I would rather see Lisp free from this sort of thing, but I think I
have shown that it is possible to do with acceptable overhead and
no increased complexity in the compiler (except that you must be
able to detect terminal calls, something that all compilers known to
me do anyway).


None the less, I do not accept the argument that it is too late to
eliminate M.V.'s from Common Lisp, should people decide to do so.
Clearly the time to eliminate things is now.  We will be able to add
things later, but not to remove them.  But you should realize that
I am really a reactionary.  If it came to a vote, I would vote against
default arguments, &REST, and multiple values.
   --------