Low-performance Design for Multiple Values in Interlisp-D Bill van Melle, 6 Feb 86 Outline of Design This is based on a message Masinter sent last year plus van Melle's earlier design for a high-performance version (see {Eris}CML>MValues-Full.tedit for that design and background considerations). The main idea is that most of the work is in the multiple-value returner. It looks inside the caller to see in what form, if any, the caller wants to see the values. The compiled code in the caller is arranged so that if multiple values are not being returned, the code following a multiple-value call computes the appropriate null values; if multiple values are being returned, the returner takes care of the values and adjusts the caller's PC to skip that code. Values are passed transparently thru tail-recursive calls by virtue of the multiple-value returner seeing the opcode RETURN following the call; in such cases, it iterates the procedure on that frame's caller. Compiler Architecture There are three interesting "compilation contexts" for multiple values, only two of which are really needed: Multiple Values as a listfor the special form multiple-value-list. The caller expects to see a list of values. Exactly n multiple values spreadfor the special forms multiple-value-bind and multiple-value-setq. The caller expects to see exactly n values (n is known at compile time) pushed on the stack. When a "return value" form is compiled in one of these contexts, special code is executed to assure that the value is in the desired form. If the form is a function call (the usual case), a special opcode is emitted after the function call whose purpose is to munge a single value into multiple form, or be recognized (and skipped) by a multiple value returner. If the form is a multiple-value returning form, the values are produced in the desired form. If the form is any other non-multiple-value returning form, its single value is coerced into a "single multiple value" of the desired form. In order to avoid hair in unbinding, any binding form (that really requires a dynamic bind, e.g., of a special variable) encountered while in the "spread" context must be compiled as a separate frame. A third context might be desired: Multiple values spread plus a countfor the special form multiple-value-call. The caller expects to see some number of values (not known at compile time) plus a count of those values. However, this context is not really needed if we choose to define multiple-value-call in the following obvious but inefficient fashion: (defmacro multiple-value-call (fn . forms) (apply ,fn (nconc @,(for f in forms collect (multiple-value-list ,f))))). Multiple Value Receiving Opcodes I am describing this as an opcode, though initially it could as well be a function call. It is only executed in the case where a single value was returned to it. MVLISTreceives values as a list. The opcode's action is "CONSNIL", i.e., (lambda (x) (list x)). Compilation of Multiple Value forms (multiple-value-list form) Compile form in multiple-value-list context. That is, any terminal function call in form is followed with MVLIST. Any terminal single-valued form is compiled as list of one element. Any terminal (values v1 ... vm) form compiles directly as list. (multiple-value-setq v1 ... vn form) Compile form in Spread[n] context. That is, any terminal single-valued form is followed by an explicit push of n$1 NIL's. Any terminal (values v1 ... vm) form simply compiles (pushes) the m values, then pops excess values or pushes n$m NIL's. Any terminal function call in form is followed with MVSPREAD[n], which is defined as MVLIST; n$1*[COPY CAR SWAP CDR]; CAR All of the above cases are then followed by SETQ vn; POP; SETQ vn-1; POP; ... SETQ v1 Net stack level effect: one push. Alternatively, can optimize the function call case by doing the spread and the SETQ's together: MVLIST; for i from 1 to n-1 compile [COPY CAR SETQ vi POP CDR]; CAR; SETQ vn; v1 the final push of v1 being needed because the value of the multiple-value-setq form is the first value. (multiple-value-bind (v1 ... vn) form . other-forms) Compile form in Spread[n] context, then BIND [v1; ...; vn]; (progn . other-forms) followed by the appropriate unbind or return. Larry indicates possible fakery by compiling it as (let ((v1 (magic-spread n form)) (v2 (nothing)) ... (vn (nothing))) . other-forms), where magic-spread does the spreading as described above, and (nothing) compiles as something that pushes nothing but fools the compiler into thinking it had. Of course, the compiling context of the multiple-value-bind itself is transmitted to the final subform of the inside progn. If none of the bound variables is special, this whole mess could just be a multiple-value-setq with the local bindings established earlier. (multiple-value-prog1 form . other-forms) (values-list (prog1 (multiple-value-list form) . other-forms)). (values v1 ... vn) If in return context, compile closed, followed by RETURN (function VALUES is described below). If not in one of the multiple value contexts, compile as prog1. (values-list list) If in return context, compile closed, followed by RETURN. If not in one of the multiple value contexts, is no-op. If in multiple-value-list context, compile as the identity (i.e., list itself is the desired list). If in spread context, spread list by the appropriate MVSPREAD[n], described above. The function VALUES VALUES is a normal Interlisp lambda* function. It is called by interpreted code and by the values special form in return context. VALUES examines its caller's caller (hereafter referred to as the returnee) to see whether and how multiple values are desired. Specifically, it fetches the byte at the pc indicated in the returnee's frame, and handles one of 3 cases: RETURNThe returnee executed a tail-recursive function call; thus multiple values must be transmitted transparently. Set returnee to be the returnee's caller and iterate. MVLISTThe returnee expects values as a list. Increment the returnee's pc (so that it skips the MVLIST instruction). Construct and return (normally, i.e., from VALUES to its caller) a list of VALUES's arguments. Anything elseThe returnee does not expect multiple values, so just return (normally) the first argument to VALUES. Notes: VALUES could be unwinding the stack as it goes, but by returning normally we can take advantage of regular RETURN microcode to do the unwinding quickly. The function VALUES-LIST is analogous to VALUES, except it takes only one argument, which is the list already bundled up. This operation of VALUES makes it important that the compiler not emit a RETURN where multiple values are expressly inhibited, and also not rearrange instructions in such a way that an MVLIST is moved away from immediately after the function call it follows. Examples of the former: (let (a) (setq a (foo)) a) (values (foo)) Neither of these expressions is equivalent to (foo), as both are required to return a single value. It might be necessary for the compiler to insert a NOP before a RETURN that follows either of those forms. CONS-less version One could imagine the following version of "spreading" that did not cons. However, the stack munging involved is almost surely more expensive than the consing. Here it is for the record, in case some part of it seems suitable for microcode boost: Distinguish spread from MVLIST by another opcode: MVSPREAD.Nreceives N values spread. The opcode pushes N$1 NIL's on the stack. Instead of the hairy destructuring sequence of opcodes, the spread context compiles as the single opcode MVSPREAD.N (with N the alpha byte). Then the function VALUES has another case to worry about: MVSPREAD.NThe returnee expects n values spread on stack. This is the least pleasant case, as we need to extend returnee's frame. Free the frames between here and returnee (preparing to return from here to returnee). Fetch the instruction's alpha byte n, and increment its pc beyond the whole instruction. Then perform the following "atomically", probably in misc context: Ensure that there is space to extend returnee's frame by n cells, i.e., a free block of sufficient length follows frame; if not, need to copy returnee as in stack overflow. Lengthen returnee's frame by n cells, and blt n values from VALUES's arguments to those last n cells; if VALUES received fewer than n arguments, store NIL's for the remaining values. Finally, return to returnee. It is unpleasantly inefficient to use the misc context to extend returnee's frame in the MVSPREAD case. If \FREESTACKBLOCK didn't think guard blocks were fair game, we could optimize the most common case, viz., returnee immediately followed by its callee, which frame is larger than the set of values to be returned: uninterruptably splice returnee's callee out of the stack, turn it into a guard block, store a free block header in the place following what will be the end of callee's frame, lengthen callee's frame, blt values. The stack remains parseable at all times during this operation. The ufn for MVSPREAD.N bears great similarity to the MVSPREAD case of VALUES, but without the handiness of having a destroyable frame following the frame being extended. We could optimize MVSPREAD.N in the common case of some small number of values by defining the ufn as a function of, say, 6 arguments. The microcode would then make space for 6 NIL's to be pushed as a side effect of calling the ufn, and the ufn need only adjust its BF to be smaller (and store NIL into its first arg). On the other hand, MVSPREAD.N ought to be easily microcoded.  ( ($100H(00($( (00((( TIMESROMAN TIMESROMAN GACHA  TIMESROMAN  TIMESROMAN  TIMESROMAN  :  HV m//.% 0 V  "9m B3+$ ! 5 $IU X$+#,r   '   c    , :K. ( 2 P 2~<V![;le(  K1j] .e %  #i %"   ;Y    q V*  %z