1

XEROX COMMON LISP DESIGN DOCUMENT
LEXICAL SCOPING (COMPILED)
1

Lexical Scoping in Compiled Code
6

Bill van Melle, 9 Apr 86
Common Lisp code is by default lexically scoped.  Roughly speaking, this means that variables, block names and labels are accessible to any code within their lexical (textual) scope (typically, the body of a function), even if the variables, block names or labels are dynamically separated at run time from the code that refers to them.  In particular, the special form function can create an object (a closure) that can be passed to other functions and still access the lexical scope in which the function occurred. 
2

Summary of Problem
1

There are two principal kinds of lexical entity:
Variablesunless declared to be special, a variable is lexical.  Lexical variables are like Interlisp localvars in that they are invisible on the stack (free variable lookup does not see them); however the scoping rules are different.  All expressions within the lexical scope of the variable's binding form can access the binding independent of any frames that might happen to intervene dynamically at run time.  In particular, nested lambda expressions constitute closures that can be passed around arbitrarily and still access the variable's binding.  Furthermore, the binding is still accessible even if the function containing the binding has been exited, as long as the closure referring to the variable still exists.  That is, lexical variables have indefinite extent (they live until there are no more pointers to them).
Special variables, on the other hand, are exactly like specvars in Interlisp, and can be implemented in the same fashion; each binding is visible on the stack and is accessed from outside the binding frame via free variable lookup.  A variable cannot be both lexical and special; i.e., special variables are never "closed over".  Thus, nested lambda expressions refer to special variables via the same free variable lookup mechanism used by any other code within the dynamic scope of the binding (and hence might not even access the same binding as was lexically apparent, if some intervening frame happened to bind a variable of the same name).
Blocks & tagswithin the lexical scope of a block (or the many forms that define implicit blocks) it is possible to return-from the block; within the lexical scope of a tagbody, it is possible to go to any label in the tagbody.  A prog is a combination of block and tagbody and hence can accept either type of control transfer.  Note that this is significantly different from Interlisp, which prohibits any "compiled subfunction" from doing a non-local go or return.  Unlike with lexical variables, neither return-from nor go is permitted once the block or tagbody is exited, as these constructs have dynamic extent.
Mechanisms for implementing lexical scoping in the compiler and the interpreter need not be related at all, unless the ability to compile only a portion of an otherwise interpreted piece of code is desired.  The compiler can "see" all the references to lexical entities, and can therefore compile those references in whatever manner it finds most suitable.  Of course, it is desirable for the debugger to be able to access lexical variables, so the compiler's mechanism must be known, but such access need not be efficient.  This document deals principally with the design for compiled code: what a compiled closure looks like, and how it accesses lexical variables and performs lexical control transfers.  It also discusses a related topic, how unwind-protect interacts with the various forms of control transfer.  A separate document discusses the implications of lexicality for the interpreter.
It should probably also be noted that a Common Lisp compiler is sufficient to compile Interlisp functions if it is extended to handle Interlisp specvars declarations.  That is, anything declared a specvar is treated as a Common Lisp special variable; anything declared a localvar is a Common Lisp lexical variable (and specvar is the default).  In addition, specvars/localvars declarations inside a function are "pervasive", in that they apply to all bindings in the function, not just the ones in the binding form of which the declare is caddr; specvars/localvars declarations in files are proclamations.  The fact that Common Lisp allows non-local access to lexical variables and non-local go/return is not a problemthis is a strictly compatible extension to Interlisp in the sense that such forms could never have worked before ("it was an error").
2

Form of a Function Object
1

In Common Lisp, function is a data type, consisting of anything that can be applied to arguments (using apply or funcall): symbols, lists of the form (lambda --), values of the special form function, and code objects produced by the compiler.  Any object of type function can be stored into a symbol's function definition cell and thus called.  One can also test functionp of objects.  In Interlisp-D, on the other hand, compiled code is a second-class citizen when not the contents of a function definition cell.  Although one can obtain an object of type CCODEP by calling GETD, and pass such objects around, they are only available to be passed to PUTD; one cannot pass them to APPLY or APPLY*.
For Common Lisp, we must have the ability to funcall a compiled code object that is not the contents of a symbol's function definition cell (an "anonymous function").  In addition, we need to represent and call lexical closures (the value of the special form function when the form's lexical environment is referenced by the form).
Thus, we need a representation for the values of the function abstract data type that are not lists or symbols.  These include both simple compiled functions and compiled closures.  We propose the new datatype FUNCTION containing the following parts:
Codethe compiled code corresponding to the lambda expression that produced this function.  This looks essentially the same as the pointer that today lives in a symbol's function definition cell.
Binding environmenta pointer (or several pointers) to an area of storage in which the bindings of lexically referenced variables are stored.  This is normally a single area (at least conceptually), but for closures referencing variables from nested lexical contexts, it is a list of such areas.
Control blipsa list of pointers uniquely associated with the one or more dynamic frames corresponding to the code that is lexically apparent to the closure, used to identify the frames to non-local control transfer constructs.
Jump infoa table that contains, for each lexically referenced label, a pc corresponding to that label in the code.
Closurepa flag that is true if this is a closure, i.e., if any of the previous three fields is non-null.  If this flag is off, then this is an ordinary compiled function.
2

Lexical Variable Reference
1

Any lexical variable that is "closed over", i.e., referenced inside a nested function form, must actually live in a chunk of storage (herein generically referred to as a "vector") separate from the frame, so that it remains accessible even after the frame exits.  All references to such variables, either locally or inside a closure, are indirected to the vector.
Binding & Local References
1

On entry to a let or other form that binds closed-over lexical variables, the compiled code creates a vector of sufficient length to hold such variables, and stores the vector in a local variable, say pvarn.  Creating this vector substitutes for the normal action of binding the variable(s).  Local references to the mth such variable are indirected:
	To load:	To store:
	PVARn	PVARn
	GETBASEPTR.2m	newvalue
		RPLPTR.2m
If an argument to a function happens to be a closed-over lexical variable, the argument must be copied into such a vector and referenced there.  Nested lets can collapse their variables into a single vector only if the inner let is not in a loop, or if no closure assigns to the variable (i.e., the multiple closures created in the loop are not behaviorally distinguishable).  For example, each let in the following must have its own separate storage:
(let (a)
     ...
     (do -- (let (b)
                 ...
                 #'(lambda (x) (setq b (+ a x))))))
Closure Creation
1

To create a closure over a set of lexical variables, the code creates a FUNCTION object, fills the code slot with the compiled code for it and fills the binding environment slot with the vector in which the variables' bindings live.  If there is more than one such vector (in the nested binding case), it fills the binding environment slot with a list of the vectors.
Closure Call
1

Function call is extended as follows: calling a compiled closure is exactly like normal function call, except that the compiled code (function header) is fetched out of the FUNCTION object, rather than from a symbol's definition cell, and (if the closurep flag in the closure is true) the frame that is created has the first local variable initialized to the closure (FUNCTION object) itself.  The code inside the closure will probably want to start by fetching the contents of the Binding environment slot of the closure and storing it in some other local.  Variable references inside the closure code are indirected thru that local variable, in the same manner as described above for local references.  In the case of multiple vectors, the closure code can either "spread" the list of vectors into n local variables on entry to the closure, or else make references to the variables via additional CARs and CDRs first.
GC Considerations
1

For simplicity of implementation, the vectors and their contents are reference counted.  The vector therefore lives as long as either the frame in which it is a local variable exists or the closure in which it is stored persists, which is exactly the correct semantics.  The bindings inside the vectors are thus, in effect, non-stack bindings whose stores are reference counted (much like global variable value cells).
Vector representation
1

Most anything will do.  One simple possibility is to use cons cells, one per binding.  Each closed-over lexical variable is thus allocated a "vector" by calling CONS, and reference is via CAR and RPLACA instead of GETBASEPTR and RPLPTR.  Creating the closure involves creating a list of all the individual binding conses needed.
"FVAR hack"
1

It was once proposed that the indirection to lexical variables be done via the free variable mechanism, as follows: each lexical variable is treated by the compiled code as a free variable, but one whose name does not appear in the name table.  On entry to the binding construct or closure, each free variable's binding slot is initialized to a pointer pointing at the variable's storage cell.  References to the variable are then by the FVARX or FVARX_ opcodes.  This saves one instruction and one or two bytes per variable reference, at the cost of greater time and complexity to bind the variable or enter the closure.  To make this more efficient than the indirect method described above would probably require implementing a new opcode "set fvar binding slot".  It does not appear at this time that the extra complexity is worthwhile.
2

Lexical Control Transfer
1

There are two control transfer forms whose targets are lexical: go and return-from (return is a special case of return-from).  It is possible to go or return-from out of a closure (or any form that is likely implemented using closures, such as catch) as long as the target of the control transfer still dynamically exists.  return-from could be considered a special case of go, where the target is "the end of the block", except that return-from can return a value (or multiple values).  Thus, if the block being returned from appears in a value context it is necessary that return-from and go operate somewhat differently.
The important points here are
(1) the control transfer form must have a way of identifying the exact target frame, even if there are many recursively established blocks of the same name dynamically appearing between the return-from and the frame whose block was lexically apparent to the return-from (similarly for go and same-named tags that might intervene).
(2) following a go, the target frame's dynamic stack depth must be correct for the code being executed at the target of the go.
(3) after the block or tagbody is exited, any closures referring to it must be prohibited from attempting a go or return-from.
These points are addressed in the following design.
Establishing the target
1

Any context that is to be the recipient of a non-local go or return-from is compiled as a separate frame.  On entry to the context, the code stores in a distinguished place in the frame a "Control blip", an object that uniquely identifies this dynamic invocation of this particular lexical context.  This blip identifies the frame to the constructs that wish to transfer control to (or out of) this context.
A simple and probably entirely adequate implementation is to have the blip be a freshly-minted cons, and store it as the value of a distinguished special variable, say *CLOSURE-MARKER*.  Storing it in a fixed place in the frame, say pvar0, might additionally aid the search for the frame.  Of course, this conflicts with pvar0 being the place proposed above that closure call stores the closure object.  The compiled code for such functions could, of course, move the closure object into pvar1 after entry and still use pvar0 for the control blip, as long as the debugger knows about this possibility.
Closure Creation
1

When a closure is created that references block or tagbody labels, the code creates a FUNCTION object and stores into it the following: its binding environment (if any), as described in the previous section; a list of the control blips of any block or tagbody frames that will be referenced; and for a closure inside a tagbody, a jump table, described below.  Note that in the case of nested blocks and tagbodys, the code creating the closure needs access to all the blips, not just the one readily available in the current frame.  The compiler can either arrange for the blip to be passed as an argument to the inferior frames, or it can access the blip, which is in a known frame relative to the current frame, in the manner described later under OptimizationsVariable Reference.
The jump table contains a program counter (pc) for each label reachable by a non-local go.  Each pc denotes a place in the compiled code that is prepared to accept a non-local go to the label.  Said code may need to worry about fixing the dynamic stack depth before arriving at the code for the "real" label.  This is discussed below.
The jump table need contain only pc's, as the identity of the tags themselves is not required at runtimethe compiled code knows which labels are possible targets, and a go need only make reference to the nth pc in the jump table in order to go to the nth label.  The contents of the jump table are completely known at compile time, so the obvious representation for the jump table is a literal list.
Execution
1

When a closure wants to perform a non-local go or return-from, the procedure is as follows:
Search the stack for the frame that binds a control blip that is eq to the blip in the closure object corresponding to the target block or tagbody (recall that the closure (function object) is accessible to the code inside the closure as a local variable).  If none is found, signal an error "Attempt to go to a label (return from a block) no longer dynamically extant".
Unwind the stack back to that frame, respecting any unwind-protect's along the way.
For go, set the frame's pc to be the pc from the jump table corresponding to the desired label, and return to the frame.  For return-from, cause a return from the frame with the value(s) passed to return-from.
These can be handled by internal functions
(si:non-local-go closure blip-index label-index) and
(si:non-local-return closure blip-index values).
The blip-index is the index of the block or tagbody frame in the list of blips in the closure.  The label-index is the index of the go label in the jump table.  Both are known at compile time, of course.
In the case of go, someone must fix the stack depth inside the target frame.  This is because the compiler cannot know in advance how many values have been pushed on the stack, or local/special variables bound, before some function was called by which route the closure executing the go came into control.  However, the compiler does know the absolute stack depth at the point of the label.  This leads to a choice of two ways to fix the stack depth:
The code at each non-local go's pc executes a new opcode that resembles UNBIND but takes an absolute stack depth.  The opcode pops cells off the stack, unbinding things indicated by any bind marks it encounters, until the absolute stack depth is as desired.
The compiler stores into the jump table the desired stack depth, and si:non-local-go "manually" fixes the stack depth.  Note that the stack depth for all labels in a single tagbody is the same (they are all at the "top level" of the tagbody), so a list of the stack depths for each blip could be another field in the closure, rather than a part of the jump table.  However, this would prevent tagbody frame merging; see Optimizations.
The latter choice may be easier to implement in the short term, as it requires no microcode, but the former seems more desirable.  Note that the proposed version of UNBIND is fully adequate for the existing uses of UNBIND, as the compiler does know the absolute stack depth that will exist after the UNBIND, so there is no reason (other than a little compiler work and an extra opcode byte per unbind) not to replace the old UNBIND with the new.  Note also that the new UNBIND resembles that proposed for Tamarin.
2

Optimizations
1

The sections above describe a sufficient mechanism for handling lexical variable reference and control transfer.  However, there are several cases in which some part of the generality of that solution can be dropped.
Variable Reference
1

There are several cases where a closure is created for control purposes only, because a separate frame is needed: the inside of a catch, for example, or any of the contexts described herein as needing to be a separate frame.  In such cases, no code other than the caller will ever "see" the closure, and it is known that the frame running the closure is the immediate descendent of the caller.  This means that references to lexical variables of the caller can be resolved at compile time.  If we introduce new opcodes PVARn.m and PVAR_n.m, meaning reference the nth local of the mth frame back, it is possible to avoid creating closures at all, and simply compile the separate frame as an anonymous function with no explicitly passed lexical context.
Fewer Conses
1

In the common case where the blip list or jump table has a single element, one could store just the single element, not a list of one element, and have si:non-local-return and friends test consp.
Frame Merging
1

Frames can be merged if the compiler can determine that there is no behavioral distinction.  In deciding what needs to be a separate frame, the important criterion is that when the target context is exited, the control blip must vanish, or the compiler must ensure that it is no longer possible for the closure to run and see the blip.  For example, in
(defun testA --
      (block foo
            (tagbody --
                     #'(lambda -- (go bar)
                               -- (return-from foo))
                bar  --
            )
            (more-stuff))
      --)
the names foo and bar are both closed over.  However, if the compiler can assure that the code inside more-stuff can no longer reach the closure (e.g., it is all inline), then the block and tagbody can be compiled as a single frame.
In many cases, one can avoid introducing a new frame in the first place.  For example, in
(defun testB --
      (some-stuff)
      (tagbody --
               #'(lambda -- (go bar) -- )
          bar  --
      )
      (more-stuff))
assuming there is no reference to the block testB, the tagbody need not be compiled as a separate frame inside foo.  Rather, the compiler emits code that creates and stores the control blip on entry to the tagbody code, and removes the blip (sets it to nil) on exit from the tagbody code.  Note that if the tagbody were inside a loop, the code still must create a fresh control blip on entry to it each time (just as it would if the tagbody were a separate frame).
Ordinarily, a block requires a new frame if a closure is to be able to perform a non-local return-from from it.  However, if the block appears in other than value context (so that the return-from is for control transfer only, not value), or the value being returned is a constant, the compiler can change the return-from into a go to a fictitious block-exit label and thereby avoid compiling the block as a separate frame.
2

Other Issues
1


Anonymous functions
1

Should values of function that are not closures have the same representation as closures, but with all the interesting fields null?  What does fsymeval (the equivalent of Interlisp GETD) return for a vanilla compiled function?
The present proposal is that both take the form of a FUNCTION object whose lexical content is null; the closurep field being false tells the calling microcode not to store the closure object in the frame's first local.  The only argument in favor of using the current CCODEP objects instead (and extending APPLYFN to recognize them as well) is one of spacevanilla compiled functions have no need to take up the 3 cells and one flag that a full-blown closure does.
Function call microcode; function definition cell
1

The APPLYFN opcode needs to be extended to recognize not only symbols, but also objects of data type FUNCTION, and perform closure call as described above (or vanilla function call if the closurep bit is off).
Similarly, the FNx opcodes need to be extended to recognize a closure in a symbol's definition cell.  Currently, a symbol's function definition cell contains a pointer to a raw compiled code object, and a bit saying the object is ccodep.  In Common Lisp, it is necessary that the definition cell be able to contain either a vanilla compiled function or a compiled closure in a way that microcode can call it (interpreted closures can be handled the same way interpreted functions are now, viz., by the interpreter).
Proposal A: Store vanilla compiled functions as now (as code pointers with the ccodep flag set).  For closures, store the FUNCTION object in the definition cell and have function call microcode test the type of the definition cell's contents if it fails the ccodep test.  This is clearly how to do it in a tagged architecture, but requires an extra type test in Interlisp-D.  On the other hand, the same type test is needed in any case for APPLYFN.
Proposal B: When storing a closure in a definition cell, set a new bit that says "I am a closure".  Function call microcode is extended to test the new bit (if the ccodep bit is off), and perform a closure call.  This trades a type test for a bit test.
Proposal C: All compiled functions (normal or closure) are stored as FUNCTION objects in the definition cell and are "ccodep".  Function call microcode performs closure call, respecting the bit in a vanilla FUNCTION that says there is no lexical context.  Disadvantage: This requires an extra memory fetch per function call for vanilla functions (to get the code out of the FUNCTION object), which one would expect to be the common case, as well as a small amount of extra storage per function.  Advantages: This simplifies the microcode by combining the two cases into one.  Also, fsymeval and #'foo do not need to cons up a FUNCTION object. 
Exceedingly Feeble Interim Proposal: Like B, but no new "closure bit"; just store the FUNCTION object in the definition cell as if it were an expr definition.  Microcode (function call and APPLYFN) sees that the ccodep flag is off and punts to the interpreter, which laboriously builds the desired frame.  Clearly undesirable in the product, but allows a start without microcode.
Compiled file representation
1

We need to have a way of dumping a closure's code as a literal of the function that creates the closure.   Currently subfunctions are dumped as separate code objects with a gensym'ed name composed from its parent; the literal in the calling function is that name, with the code residing in the gensym's function definition cell.  We could continue to do this for now.  Devising a way to do it as a part of a function's literals would have the slight advantages of consuming fewer atoms, being correctly gc'able (if the caller is gc'ed, so is the closure code), and being simpler for LOADFNS.
Note that
(let (a) (defun f1 --) (defun f2 --))
creates closures (assuming the function bodies reference a).  On the compiled file, this probably appears as anonymous code that creates two closures and stores them in the definition cells of f1 and f2, followed by a call to that anonymous code.
Debugger
1

It would be desirable to extend the "name table" in a compiled code object to allow the break package to find the values and, ideally, the names of lexical variables that are stored outside the frame.  The current state is that there is a primary name table, which identifies the names and frame locations of all specvars; this is used by free variable lookup and need not change.  There is also a "localvar argument" name table, which has the same format and is used to identify the names of the arguments to a function, for the benefit of ARGLIST.  This latter table could be superseded by one that is stored separately from the code (for locality reasonsit is not needed by running code), and which contains identification of every variable bound in the code.
2

The Unwinder
1

The procedure described above for lexical control transfer invokes the "stack unwinder", whose job it is to (a) effect the control transfer and (b) ensure that unwind-protects are honored:
(si:unwind blip return-case),
where blip is the identifying control blip from the closure and return-case is one of
gothe function unwinds the stack so that the caller of si:unwind is positioned to return to the desired frame.
returnsame as go, but the desired frame is tossed as well, so that the caller of si:unwind is positioned to return to the desired frame's caller.
The returned value is NIL if the target frame is not found, in which case the caller signals the appropriate kind of errror.  On success, the returned value is T, in which case the caller does a return of the appropriate value(s) (in the case of return-from) or twiddles the returnee's pc and returns no values (in the case of go).  This is fairly straightforward with existing stack routines.  Sample code for si:unwind:
(let* ((unwinder (my-caller))
       (target (caller-of unwinder)))

     ;;; search for frame binding blip

      (loop
         (if (top-level-frame-p frame)
            then ; error--target not found
                 (return-from unwind nil)
           elseif <target binds blip>
            then (if return-case = return
                    then   ; go back one frame further
                         (setq target (caller-of target)))
                 (return)
           else (setq target (caller-of target))))

     ;;; target frame found, now unwind

      (for frame_(caller-of unwinder)
         until (EQ frame target)
         do (if <frame is an unwind-protect>
              then <evaluate frame's cleanup forms>)
            (deallocate-frame  ; discard frame, point unwinder at next frame back
               (prog1 frame (setf (caller-of unwinder)
                                  (setq frame (caller-of frame))))))
      t)
The deallocate-frame clause has to be done atomically, of course, but it's okay for errors or any other arbitrary code to happen inside the execution of the cleanup forms.  This code is oversimplified, since spaghetti complicates the issue; more on this below.  caller-of is really (fetch (FX CLINK) of --).  my-caller is \MYALINK.  The deallocate-frame clause can be implemented using the system's fairly general stack hacker \SMASHLINK, but it's actually a special case one might want to handle more cleverly, so as to avoid incrementing and then immediately decrementing the use count of the new frame.
This leads to the question of what the stack format of an unwind-protect's frame is.  A fairly straightforward way is to compile
(unwind-protect form . cleanup-forms)
as
(multiple-value-prog1
  (let ((*cleanup-forms* #'(lambda () . cleanup-forms)))
       (declare (special *cleanup-forms*))
       form)
   . cleanup-forms)
In other words, during the evaluation of the protected form, unwind-protect binds a distinguished variable whose value is a closure that executes the cleanup forms (in the proper lexical context, of course).  The stack unwinder notices that a frame binds this distinguished variable, and calls the closure before tossing the frame away.  Actually, the unwinder has to notice every binding of the variable in the frame, for the case of nested unwind-protects.  Note that unwind-protect need not be a separate frame when compiled this way (except as dictated by closure constraints), since unbinding *cleanup-forms* effectively exits from the unwind-protect context.
The only reason the variable *cleanup-forms* needs to be special is so the unwinder can find it.  Alternatively, one could bind the cleanup-form closure in a local variable in a distinguished location and set a bit in the frame saying it's there.  This would allow the unwinder to more quickly detect unwind-protect frames, but requires that every unwind-protect compile as a separate frame.
Throw as return-from
1

Note that throw looks a lot like return-from.  Specifically, if catch compiles as a call to a closure of one argument, the catch tag, and the code of the closure stores the catch tag in its frame in the distinguished "control blip" location, then throw uses virtually the same code as return-from.
(defun si:non-local-return (closure blip-index values)
  (if (si:unwind (nth (function-blips closure) blip-index) t)
     then (values-list values)
    else (error "Attempt to return from a block no longer extant" closure)))
(defun si:internal-throw (tag values)
  (if (si:unwind tag t)
     then (values-list values)
    else (error "Unknown tag" tag)))
RESETLST
1

Interlisp-D's version of unwind-protect consists of RESETLST and related functions.  RESETLST can almost be implemented in terms of unwind-protect, except for RESETLST's feature of binding the special variable RESETSTATE to one of NIL, ERROR, RESET during the evaluation of the cleanup forms.  For this, we can extend si:unwind with a RESETSTATE argument that defaults to ERROR (the global value of RESETSTATE is NIL).  The other trickiness is that RESETLST's "binding" of its cleanup forms is special, in the sense that one can write RESETSAVE in a context not lexically enclosed by the RESETLST.  So
(RESETLST . forms)
can compile as
(let (*resetforms*)
     (declare (special *resetforms*))
     (unwind-protect
        (progn . forms)
        (resetunwind *resetforms*)))
where resetunwind is a function that maps down its argument, interpreting the forms placed there by RESETSAVE.  RESETSAVE operates by pushing forms onto *resetforms*.   si:unwind and any caller of it must be careful not to bind *resetforms*, so that the value in the RESETLST frame is visible to the resetunwind.  In addition, nested RESETLST's must be compiled as separate frames, in order that both bindings of *resetforms* are acted on.  This constraint is not implied by the macro expansion of RESETLST shown above, so some compiler mechanism would be required to force it.  One probably wants also to have the compiler recognize (lambda nil (resetunwind *resetforms*)) as a well-known function whose constant value is stored in the unwind-protect frame, rather than consing a fresh one for every RESETLST.
RESETFORM and RESETVARS can be written in terms of RESETLST.
Of course, all user code that calls RESETLST, RESETSAVE, RESETFORM, etc. must be recompiled.
HARDRESET
1

The current RESETLST and friends have the property that their cleanup forms are executed even after a HARDRESET (or ^D from [Tele]Raid).  This is because, even though HARDRESET throws away the stack and rebuilds it from scratch, the cleanup forms were all consed onto a global list, RESETVARSLST, accessible from the process handle in which the RESETLST was running.  This is not true in the unwind-protect proposal described above.
There are two apparent alternatives:
(a) handle unwind-protect in a manner analogous to RESETLST: in addition to binding the cleanup closure in the unwind-protect frame, the code can push the closure onto a global (per process) list, and pop it off on exit (or inside si:unwind, in the error case).  In order to get the cleanup forms generated by RESETSAVE, it would probably be better to compile RESETLST very similarly to its current strategy:
(let ((resetvarslst0 RESETVARSLST))
     (declare (special resetvarslst0))
     (unwind-protect
        (progn . forms)
        (resetunwind0 resetvarslst0))),
and have RESETSAVE act exactly as it does nowpush cleanup forms onto RESETVARSLST.  resetunwind0 is a function that pops cleanup forms off the global RESETVARSLST and executes them until it encounters the tail resetvarslst0.  resetvarslst0 is declared special only to avoid consing a closure over it every time.  HARDRESET would then walk down RESETVARSLST for each process, either calling cleanup closures or interpreting a RESETSAVE form.  RESETLST, of course, would not also push the (resetunwind0 resetvarslst0) closure onto RESETVARSLST, though it would bind it, as usual, as the *cleanup-forms* closure of the unwind-protect.
(b) have HARDRESET carefully walk its way back up the stack of each process, gathering a list of all cleanup closures from any unwind-protect frames it encounters"carefully" because one of the reasons for HARDRESET is to recover the world if the stack gets seriously mangled.  The stack walker would have to recognize RESETLST frames specially so that it also gathered up the special binding of *resetforms*.
Alternative (a) costs an additional cons per unwind-protect, but this might be insignificant relative to the cost of constructing and binding the cleanup closure.  Alternative (b) defers the expense until it is really needed (i.e., during a HARDRESET), but fails completely if the stack is mangled enough that one cannot follow stack links upward.
This discussion of getting at the *resetforms* binding raises an interesting question: what is the dynamic environment in which an unwind-protect's cleanup forms are executed?  The silver book is silent on this question.  The implementation of unwind-protect described above implies that it is the dynamic environment of the unwind-protect frame, or more precisely, the dynamic environment seen on entry to the frame called under the unwind-protect frame.  The translation of RESETLST depends on this.
Spaghetti considerations
1

The question here is, when should an unwind-protect's cleanup forms be run?  When running pure Common Lisp, the answer is straightforward: whenever you throw, return-from or go to some dynamic ancestor of the unwind-protect.  However, in Interlisp-D, spaghetti stacks allow two activities that complicate the issue: one can return to a frame that is not one's direct ancestor, and one can return to a frame more than once (by retaining a pointer to a frame after it has been returned to).
Consider the former case first: returning to a frame in a different "stack group", i.e., different chain of control.  This is what is happening in coroutines, and also in the multiprocessing mechanism (though in a highly stylized way that does not make direct use of spaghetti functions).  Code in stack A has a pointer to a frame in stack B.  When it wants to let B run, it stores away a pointer to some ancestor frame of itself, and returns to the saved B frame (typically using RETFROM or RETTO, releasing B's pointer at the same time).  B does the same sort of thing to let A run.  Or to use process switch as an example, consider the action of, say, a call to AWAIT.EVENT in process A.   AWAIT.EVENT calls the "scheduler", which looks around for another runnable process, call it B.   The scheduler stores in process A's handle a pointer to the AWAIT.EVENT frame and simultaneously causes a return to the frame pointed to in process B's handle.
So long as these control transfers happen in a disciplined way, so that no code retains a pointer to a frame after returning to (or from) it, the solution is reasonably obvious.  The act of returning to a frame in another stack group causes the release of all frames between the returner and the frame whose pointer the returner saved for later resumption.  The releasing happens somewhat indirectly, rather than explicitly, inside \DECUSECOUNT under \SMASHLINK.  In the process switch example, all the frames of the "scheduler" are discarded, back to the AWAIT.EVENT frame.  Obviously, one should run the cleanup forms of any unwind-protect frames discarded during this stack switch.
The question is more complicated when somebody retains a pointer to a frame after control has returned to that frame.  In theory, it is possible to again return to the same frame, using RETFROM or RETTO.  In order to manage such nonsense, the system maintains a use count for each frame.  Ordinarily, the use count of a frame is 1, meaning it is pointed to (implicitly) by whoever was called by the frame, or by the processor itself if the frame is the currently running frame.  Creating a pointer to a frame increments the use count.  Releasing the pointer (either explicitly or by gc) decrements the use count.
The currently running frame always has use count 1nobody is allowed to point at the frame that is "in the processor".  Thus, whenever the system attempts to return to a frame whose use count is greater than 1, something must give.  What happens is that the system makes a copy of the frame, gives it reference count 1, decrements the reference count of the old frame, and runs in the copy.  Of course, this copying action increments the use count of the frame's immediate ancestor, so if the copy tries to do a return, then the copying action must be done on the ancestor as well, and so on (assuming someone is still holding on to a pointer to the original frame).  Thus, the holder of the pointer to the old stack frame still sees the old environment, unchanged by the frame having been returned to.
So now when are frames discarded?  A frame is discarded when its use count goes to zero.  The "well-disciplined case" described earlier is a special case: returning to another stack group decrements the use count of the returner.  Its use count goes to zero, so it is discarded, which decrements the use count of its immediate ancestor.  This repeats until you discard the frame whose immediate ancestor is the one you retained a pointer to for later resumption: its use count goes from 2 to 1, and all is back to normal.  It's easy enough to see that unwind-protect frames discarded in this well-disciplined fashion must have their cleanup forms run.
But what about frames that are discarded because their use count went to zero in some other scenario?  Specifically, what happens when someone does a RELSTK on a stack pointer, or a stack pointer is garbage collected (which does an implicit RELSTK)?  The problem is that we don't know whether the unwind-protect's cleanup forms have been run yet or not, and we presumably do not want to run them a second time, and we almost surely do not want to run them from inside the garbage collector.  There seem to be two cases, yes and no:
You return to an unwind-protect frame that someone else has a pointer to (directly or indirectly).  Later, someone releases the pointer.  In this case, yes, the cleanup forms have been run once, during the normal return from the unwind-protect, so there is nothing more to do.
You return to a frame that is an ancestor of an unwind-protect frame that someone else has a pointer to (directly or indirectly).  In this case, the stack unwinding between the returner and the returnee halts when it reaches the frame that someone else has a pointer to (since the frame's use count does not drop to zero), so the unwinder never sees the unwind-protect, so never runs the cleanup forms.
Note that the present RESETLST does not work properly in the second case, either, so perhaps there is no pressing need to resolve the problem.  However, it seems highly desirable that throwing thru an unwind-protect frame should run the cleanup forms, independent of whether someone (e.g., the break package) has a stack pointer that would prevent the unwind-protect frame from being discarded.
The only reasonable solution I have thought of is to constrain spaghetti to prohibit returning to a frame twice.  I am unaware of any interesting programs that this would disable.  Then we can arrange that whenever you unwind the stack and discover along the way a frame with use count greater than 1, you invalidate any stack pointers to that frame as you continue unwinding.
There are still some implementation difficulties with this solution.  One is how to invalidate the stack pointers.  Two methods suggest themselves:
Scan all stack pointers in memory, looking for ones that point to the frame in question.  Smash them.  There is a well-defined algorithm for locating all pointers of a specified datatype, but it runs in time proportional to the size of virtual memory.
Mark the frame itself invalid in some way, rather than discarding it.  For example, turn on the frame's "invalid" bit (a new bit) and have all code that dereferences stack pointers check that the invalid bit is off.  Alternatively, smash the frame's access and control links to zero, and don't decrement its use count.  Attempting to return to the frame will invoke the "hard return" code, which can notice that the frame is a zombie and cause an error.  Unfortunately, this error would occur too lateyou would be in this orphan stack group, rather than in the environment that did the return to the invalid frame.
A second problem is to know when to invalidate a frame (or the pointers to it).  It is clear in the case of throw, return-from, and go, since those all act within a single stack group, and hence any frame along the way with use count greater than 1 must be invalidated.  However, when returning from one stack group to another, it is unclear how to decide how far back to peel the stack.  You can only peel it as far back as the first frame with reference count greater than 1.  If someone subsequently releases its pointer to that frame, rather than returning to it, you would expect to want the unwind-protect cleanup forms to be run, but it is unclear in what environment to run themprobably in the access environment of the frame being released, but the control environment of the releaser.  If the releaser is the garbage collector, then you'd have to do it by the \CAUSEINTERRUPT mechanism so that the unwinding doesn't happen in the garbage collector.  On the other hand, we can again point out that RESETLST in current Interlisp-D does not handle this case, so we could just warn that unwind-protect also doesn't work with arbitrary spaghetti machinations.

(LIST ((PAGE NIL (PAPERSIZE Letter FOLIOINFO (ARABIC)) (0 0 612 792) ((HEADING NIL (HEADINGTYPE FOOTINGR) (72 27 540 36) NIL) (TEXT NIL NIL (72 72 504 648) NIL))) (PAGE NIL (PAPERSIZE Letter FOLIOINFO (ARABIC)) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD RIGHT) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY MODERN OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO (ARABIC)) (288 12 288 36) NIL) (HEADING NIL (HEADINGTYPE FOOTINGR) (72 27 540 36) NIL) (HEADING NIL (HEADINGTYPE RECTOHEAD) (72 762 540 36) NIL) (TEXT NIL NIL (72 72 504 648) NIL))) (PAGE NIL (PAPERSIZE Letter FOLIOINFO (ARABIC)) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD RIGHT) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY MODERN OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO (ARABIC)) (288 12 288 36) NIL) (HEADING NIL (HEADINGTYPE FOOTINGR) (72 27 540 36) NIL) (HEADING NIL (HEADINGTYPE RECTOHEAD) (72 762 540 36) NIL) (TEXT NIL NIL (72 72 504 648) NIL))))))``

T(��
(rr

/



�

T/




�

T)


T)2


T(``
(rr
1��

�
81``

�
81``

�
8(��
(r�
(``)``

T)``

TB
�

�
PAGEHEADING	RECTOHEADA
�




�
PAGEHEADINGFOOTINGR
TIMESROMAN
TIMESROMAN
GACHA
TIMESROMAN

GACHA

TIMESROMAN

TIMESROMAN

TIMESROMANMODERN
MODERNMODERNMODERN

HRULE.GETFN
MODERN

"
HRULE.GETFN
MODERN

!
HRULE.GETFN
MODERN

rx
HRULE.GETFN
MODERN





HRULE.GETFN
MODERN

1
�
c
�,C �5��
�
�
HRULE.GETFN
MODERN



HRULE.GETFN
MODERN

PA\	�H-�A5�!�
(�t�
HRULE.GETFN
MODERN



HRULE.GETFN
MODERN

M

	
HRULE.GETFN
MODERN

�
o
!











�F�6
p
	
HRULE.GETFN
MODERN

H
 
	
HRULE.GETFN
MODERN

��	
	
HRULE.GETFN
MODERN


�
	
HRULE.GETFN
MODERN

�
^
	
HRULE.GETFN
MODERN


�
�
HRULE.GETFN
MODERN





HRULE.GETFN
MODERN

@RK':�
	�9,	j	N4
	
HRULE.GETFN
MODERN

7
P_Ej
7

	
HRULE.GETFN
MODERN

*�<
 
t
WW��!
.
�	
	
HRULE.GETFN
MODERN

,	A?�	4	x<+	



	




1]
�	+�	EY5}E
�,Ow'&
HRULE.GETFN
MODERN






HRULE.GETFN
MODERN

�
	
HRULE.GETFN
MODERN

�
�







�
	
HRULE.GETFN
MODERN

�

	
HRULE.GETFN
MODERN


a
�
Q
D$Z
�,1\(wH2rB
HRULE.GETFN
MODERN





HRULE.GETFN
MODERN



	
HRULE.GETFN
MODERN

v*5� �1
	
HRULE.GETFN
MODERN

Ze
�
z
6
�
E���

V_�
	
HRULE.GETFN
MODERN

G

&9
�-
	
HRULE.GETFN
MODERN

�
HRULE.GETFN
MODERN





HRULE.GETFN
MODERN

�	

68	/R	8�
UFR	J!FE
�"`	"2��		
J
�

:9	


	>
6
=
,>r


!
	
HRULE.GETFN
MODERN


�!#
�
d
	
HRULE.GETFN
MODERN


'
+
F	

!N	,	

	`'S		 	2G9G7'@2

		$			
	
HRULE.GETFN
MODERN

R	8	k2'%	4j	F	))q*			460

J	E	%,

			mA	hE-�	b"UcC_
	
HRULE.GETFN
MODERN

%e!


���Y
fJ

^<,�<	
V#(V�U2�	�"	0
$#��
y�	�	hl
�
zN:
���z�