;;; -*- Mode:gate; Fonts:(HL12 HL12I HL12B CPTFONTB HL12BI HL12B HL12I ) -*- =Node: Introduction to Stack Groups =Text: 3INTRODUCTION TO STACK GROUPS* A 1stack group* (usually abbreviated `SG') is a type of Lisp object useful for implementation of certain advanced control structures such as coroutines and generators. Processes, which are a kind of coroutine, are built on top of stack groups (see 4(PROCESSES-0)Processes*). A stack group represents a computation and its internal state, including the Lisp stack. At any time, the computation being performed by the Lisp Machine is associated with one stack group, called the 1current* or 1running* stack group. The operation of making some stack group be the current stack group is called a 1resumption* or a 1stack group switch*; the previously running stack group is said to have 1resumed* the new stack group. The 1resume* operation has two parts: first, the state of the running computation is saved away inside the current stack group, and secondly the state saved in the new stack group is restored, and the new stack group is made current. Then the computation of the new stack group resumes its course. The stack group itself holds a great deal of state information. It contains the control stack, or 1regular PDL*. The control stack is what you are shown by the backtracing commands of the error handler (2Control-B*, 2Meta-B*, and 2Control-Meta-B*); it remembers the function which is running, its caller, its caller's caller, etc., and the point of execution of each function (the 1return address* of each function). A stack group also contains the dynamic environment stack, or 1special PDL*. The name `stack group' derives from the existence of these two stacks. Finally, the stack group contains various internal state information (contents of machine registers and so on). When the stack group is running, the special PDL contains all the dynamic bindings that are shadowed by other bindings in this stack group; bindings that are current reside in the symbols' value cells. When the stack group is not running, all of the dynamic bindings it has made reside in its special PDL. Switching to a stack group moves the current bindings from the special PDL to the symbol value cells, exchanging them with the global or other shadowed bindings. Switching out of a stack group does the reverse process. Note that 2unwind-protect* handlers are 1not* run by a stack-group switch (see 2let-globally*, 4(EVAL-1)Variable Binding Constructs*). Each stack group is a separate environment for purposes of function calling, throwing, dynamic variable binding, and condition signalling. All stack groups run in the same address space; thus they share the same Lisp data and the same global (not lambda-bound) variables. When a new stack group is created, it is empty: it doesn't contain the state of any computation, so it can't be resumed. In order to get things going, the stack group must be set to an initial state. This is done by 1presetting* the stack group. To preset a stack group, you supply a function and a set of arguments. The stack group is placed in such a state that when it is first resumed it will apply this function to those arguments. The function is called the 1initial function* of the stack group. =Node: Resuming of Stack Groups =Text: 3RESUMING OF STACK GROUPS* The interesting thing that happens to stack groups is that they resume each other. When one stack group resumes a second stack group, the current state of Lisp execution is saved away in the first stack group and is restored from the second stack group. Resuming is also called 1switching stack groups*. At any time, there is one stack group associated with the current computation; it is called the current stack group. The computations associated with other stack groups have their states saved away in memory and are not computing. So the only stack group that can do anything at all, in particular resuming other stack groups, is the current one. You can look at things from the point of view of one computation. Suppose it is running along, and it resumes some stack group. The state of the computation state is saved away into its own stack group, and the computation associated with the called stack group starts up. The original computation lies dormant in the original stack group, while other computations go around resuming each other, until finally the original stack group is resumed by someone. Then the computation is restored from the stack group and gets to run again. There are several ways that the current stack group can resume other stack groups. This section describes all of them. Each stack group records a 1resumer* which is 2nil* or another stack group. Some forms of resuming examine and alter the resumer of some stack groups. Resuming has another ability: it can transmit a Lisp object from the old stack group to the new stack group. Each stack group specifies a value to transmit whenever it resumes another stack group; whenever a stack group is resumed, it receives a value. In the descriptions below, let 1c* stand for the current stack group, 1s* stand for some other stack group, and 1x* stand for any arbitrary Lisp object. Stack groups can be used as functions. They accept one argument. If 1c* calls 1s* as a function with one argument 1x*, then 1s* is resumed, and the object transmitted is 1x*. When 1c* is resumed (usually--but not necessarily--by 1s*), the object transmitted by that resumption is returned as the value of the call to 1s*. This is one of the simple ways to resume a stack group: call it as a function. The value you transmit is the argument to the function, and the value you receive is the value returned from the function. Furthermore, this form of resuming sets 1s*'s resumer to be 1c*. Another way to resume a stack group is to use 2stack-group-return*. Rather than allowing you to specify which stack group to resume, this function always resumes the resumer of the current stack group. Thus, this is a good way to go back to the stack group which called the current one, assuming that this was done through a function call. 2stack-group-return* takes one argument which is the object to transmit. It returns when something resumes the current stack group, and returns one value, the object that was transmitted by that resumption. 2stack-group-return* does not change the resumer of any stack group. The most fundamental way to do resuming is with 2stack-group-resume*, which takes two arguments: the stack group, and a value to transmit. It returns when someone resumes the current stack group, returning the value that was transmitted by that resumption, and does not affect any stack group's resumer. If the initial function of 1c* attempts to return a value 1x*, the regular kind of Lisp function return cannot take place, since the function did not have any caller (it got there when the stack group was initialized). So instead of normal function returning, a ``stack group return'' happens. 1c*'s resumer is resumed, and the value transmitted is 1x*. 1c* is left in a state (``exhausted'') from which it cannot be resumed again; any attempt to resume it signals an error. Presetting it will make it work again. Those are the ``voluntary'' forms of stack group switch; a resumption happens because the computation said it should. There are also two ``involuntary'' forms, in which another stack group is resumed without the explicit request of the running program. If an error occurs, the current stack group resumes the error handler stack group. The value transmitted is partially descriptive of the error, and the error handler looks inside the saved state of the erring stack group to get the rest of the information. The error handler recovers from the error by changing the saved state of the erring stack group and then resuming it. When certain events occur, typically a 1-second clock tick, a 1sequence break* occurs. This forces the current stack group to resume a special stack group called the 1scheduler* (see 4(PROCESSES-1)The Scheduler*). The scheduler implements processes by resuming, one after another, the stack group of each process that is ready to run. 3current-stack-group-resumer* 1Variable* Is the resumer of the current stack group. 3current-stack-group* 1Variable* Is the stack group which is currently running. A program can use this variable to get its hands on its own stack group. =Node: Stack Group States =Text: 3STACK GROUP STATES* A stack group has a 1state*, which controls what it will do when it is resumed. The code number for the state is returned by the function 2sys:sg-current-state*. This number is the value of one of the following symbols. Only the states actually used by the current system are documented here; some other codes are defined but not used. 2sys:sg-state-active* The stack group is the current one. 2sys:sg-state-resumable* The stack group is waiting to be resumed, at which time it will pick up its saved machine state and continue doing what it was doing before. 2sys:sg-state-awaiting-return* The stack group called some other stack group as a function. When it is resumed, it will return from that function call. 2sys:sg-state-awaiting-initial-call* The stack group has been preset (see below) but has never been called. When it is resumed, it will call its initial function with the preset arguments. 2sys:sg-state-exhausted* The stack group's initial function has returned. It cannot be resumed. 2sys:sg-state-awaiting-error-recovery* When a stack group gets an error it goes into this state, which prevents anything from happening to it until the error handler has looked at it. In the meantime it cannot be resumed. 2sys:sg-state-invoke-call-on-return* When the stack group is resumed, it will call a function. The function and arguments are already set up on the stack. The debugger uses this to force the stack group being debugged to do things. =Node: Stack Group Functions =Text: 3STACK GROUP FUNCTIONS make-stack-group* 1name* &rest 1options* Creates and returns a new stack group. 1name* may be any symbol or string; it is used in the stack group's printed representation. 1options* is a list of alternating keywords and values. The options are not too useful; most calls to 2make-stack-group* don't need any options at all. The options are: 2:sg-area* The area in which to create the stack group structure itself. Defaults to the default area (the value of 2default-cons-area*). 2:regular-pdl-area* The area in which to create the regular PDL. Only certain areas specially designated when they were created may be used for regular PDLs, because regular PDLs are cached in a hardware device called the 1pdl buffer*. The default is 2sys:pdl-area*. 2:special-pdl-area* The area in which to create the special PDL. Defaults to the default area (the value of 2default-cons-area*). 2:regular-pdl-size* Length of the regular PDL to be created. Defaults to 3000 octal. 2:special-pdl-size* Length of the special PDL to be created. Defaults to 2000 octal. 2:swap-sv-on-call-out* 2:swap-sv-of-sg-that-calls-me*These flags default to 1. If these are 0, the system does not maintain separate binding environments for each stack group. You do not want to use this feature. 2:trap-enable* This determines what to do if a microcode error occurs. If it is 1 the system tries to handle the error; if it is 0 the machine halts. Defaults to 1. It is 0 only in the error handler stack group, a trap in which would not work anyway. 2:safe* If this flag is 1 (the default), a strict call-return discipline among stack-groups is enforced. If 0, no restriction on stack-group switching is imposed. 3sys:pdl-overflow* (3error*) 1Condition* This condition is signaled when there is overflow on either the regular pdl or the special pdl. The 2:pdl-name* operation on the condition instance returns either 2:special* or 2:regular*, to tell handlers which one. The 2:grow-pdl* proceed type is provided. It takes no arguments. Proceeding from the error automatically makes the affected pdl bigger. 3eh:pdl-grow-ratio* 1Variable* This is the factor by which to increase the size of a pdl after an overflow. It is initially 21.5*. 3eh:require-pdl-room* 1regpdl-space* 1specpdl-space* Makes the current stack group larger if necessary, to make sure that there are at least 1regpdl-space* free words in the regular pdl, and at least 1specpdl-space* free words in the special pdl, not counting the words currently in use. 3stack-group-preset* 1stack-group* 1function* &rest 1arguments* This sets up 1stack-group* so that when it is resumed, 1function* will be applied to 1arguments* within the stack group. Both stacks are made empty; all saved state in the stack group is destroyed. 2stack-group-preset* is typically used to initialize a stack group just after it is made, but it may be done to any stack group at any time. Doing this to a stack group which is not exhausted destroys its present state without properly cleaning up by running 2unwind-protect*s. 3stack-group-resume* 1s* 1x* Resumes 1s*, transmitting the value 1x*. No stack group's resumer is affected. 3si:sg-resumable-p* 1s* 2t* if 1s*'s state permits it to be resumed. 3sys:wrong-stack-group-state* (3error*) 1Condition* This is signaled if, for example, you try to resume a stack group which is in the exhausted state. 3stack-group-return* 1x* Resumes the current stack group's resumer, transmitting the value 1x*. No stack group's resumer is affected. 3symeval-in-stack-group* 1symbol* 1sg* &optional 1frame* 1as-if-current* Evaluates the variable 1symbol* as a special variable in the binding environment of 1sg*. If 1frame* is not 2nil*, it evaluates 1symbol* in the binding environment of execution in that frame. (A frame is an index in the stack group's regular pdl). Two values are returned: the symbol's value, and a locative to where the value is stored. If 1as-if-current* is not 2nil*, the locative points to where the value 1would* be stored if 1sg* were running. This may be different from where the value is stored now; for example, the current binding in stack group 1sg* is stored in 1symbol*'s value cell when 1sg* is running, but is probably stored in 1sg*'s special pdl when 1sg* is not running. 1as-if-current* makes no difference if 1sg* actually 1is* the current stack group. If 1symbol*'s current dynamic binding in the specified stack group and frame is void, this signals a 2sys:unbound-variable* error. =Node: Analyzing Stack Frames =Text: 3ANALYZING STACK FRAMES* A stack frame is represented by an index in the regular pdl array of the stack group. The word at this index is the function executing, or to be called, in the frame. The following words in the pdl contain the arguments. 3sg-regular-pdl* 1sg* Returns the regular pdl of 1sg*. This is an array of type 2art-reg-pdl*. Stack frames are represented as indices into this array. 3sg-regular-pdl-pointer* 1sg* Returns the index in 1sg*'s regular pdl of the last word pushed. 3sg-special-pdl* 1sg* Returns the special pdl of 1sg*. This is an array of type 2art-special-pdl*, used to hold special bindings made by functions executing in that stack group. 3sg-special-pdl-pointer* 1sg* Returns the index in 1sg*'s special pdl of the last word pushed. .need 1800 The following functions are used to move from one stack frame to another. 3eh:sg-innermost-active* 1sg* Returns (the regular pdl index of) the innermost frame in 1sg*, the one that would be executing if 1sg* were current. If 1sg* is current, the value is the frame of the caller of this function. 3eh:sg-next-active* 1sg* 1frame* Returns the next active frame out from 1frame* in 1sg*. This is the one that called 1frame*. If 1frame* is the outermost frame, the value is 1nil*. 3eh:sg-previous-active* 1sg* 1frame* Returns the previous active frame in from 1frame* in 1sg*. This is the one called by 1frame*. If 1frame* is the currently executing frame, the value is 2nil*. If 1frame* is 2nil*, the value is the outermost or initial frame. 3eh:sg-innermost-open* 1sg* Returns the innermost open frame in 1sg*, which may be the same as the innermost active one or it may be within that. In other respects, this is like 2eh:sg-innermost-active*. 3eh:sg-next-open* 1sg* 1frame* Like 2eh:sg-next-active* but includes frames which are 1open*, that is, still accumulating arguments prior to calling the function. 3eh:sg-previous-open* 1sg* 1frame* Like 2eh:sg-previous-active* but includes frames which are 1open*, that is, still accumulating arguments prior to calling the function. 3eh:sg-frame-active-p* 1sg* 1frame* Returns 2t* if 1frame* is active; that is, if the function has been entered. Running interpreted code involves calls to 2eval*, 2cond*, etc. which would not be there in compiled code. The following three functions can be used to skip over the stack frames of such functions, showing only the frames for the functions the user would know about. 3eh:sg-next-interesting-active* 1sg* 1frame* Like 2eh:sg-next-active* but skips over uninteresting frames. 3eh:sg-previous-interesting-active* 1sg* 1frame* Like 2eh:sg-previous-active* but skips over uninteresting frames. 3eh:sg-out-to-interesting-active* 1sg* 1frame* If 1frame* is interesting, returns 1frame*. Otherwise, it returns the next interesting active frame. .need 1800 Functions to analyze the data in a particular stack frame: 3sys:rp-function-word* 1regpdl* 1frame* Returns the function executing in 1frame*. 1regpdl* should be the 2sg-regular-pdl* of the stack group. 3eh:sg-frame-number-of-spread-args* 1sg* 1frame* Returns the number of arguments received by 1frame*, which should be an active frame. The rest argument (if any) and arguments received by it, do not count. 3eh:sg-frame-arg-value* 1sg* 1frame* 1n* Returns the value of argument number 1n* of stack frame 1frame* in 1sg*. An error is signaled if 1n* is out of range, if the frame is active. (For an open frame, the number of arguments is not yet known, so there is no error check.) The second value is the location in which the argument is stored when 1sg* is running. The location may not actually be in the stack, if the argument is special. The location may then contain other contents when the stack group is not running. 3eh:sg-frame-rest-arg-value* 1sg* 1frame* Returns the value of the rest argument in 1frame*, or 2nil* if there is none. The second value is 2t* if the function called in 1frame* expects an explicitly passed rest argument. The third value is 2t* if the rest argument was passed explicitly. If this is 2nil*, the rest arg is a stack list that overlaps the arguments of stack frame 1frame*. If it was passed explicitly, it may still be a stack list, but not in this frame. See 4(MANLISTSTR-2)Stack Lists* for more information on stack lists. 3eh:sg-frame-number-of-locals* 1sg* 1frame* Returns the number of local variables in stack frame 1frame*. 3eh:sg-frame-local-value* 1sg* 1frame* 1n* Returns the value of local variable number 1n* of stack frame 1frame* in 1sg*. An error is signaled if 1n* is out of range. The second value is the location in which the local is stored when 1sg* is running. The location may not actually be in the stack; if not, it may have other contents when the stack group is not running. 3eh:sg-frame-value-value* 1sg* 1frame* 1n* &optional 1create-slot* Returns the value and location of the 1n*'th multiple value 1frame* has returned. If 1frame* has not begun to return values, the first value returned is 2nil* but the location still validly shows where value number 1n* will be stored. If 1frame* was called with 2multiple-value-list*, it can return any number of values, but they do not have cells to receive them until 1frame* returns them. In this case, a non-2nil* 1create-slot* means that this function should allocate cells as necessary so that a valid location can be returned. Otherwise, the location as well as the value is 2nil*. 3eh:sg-frame-value-list* 1sg* 1frame* &optional 1new-number-of-values* Returns three values that describe whether 1frame*'s caller wants multiple values, and any values 1frame* has returned already. The first value is a list in which live the values being, or to be, returned by 1frame*. The second value is 2nil* if this frame has not been invoked to return multiple values, a number which is the number of values it has been asked for, or a locative, meaning the frame was called with 2multiple-value-list*. In the last case, the first value includes only the values 1frame* has returned already, and the locative points to a cell that points to the cons whose cdr should receive the next link of the list. The third value is how many values 1frame* has returned so far. If 1new-number-of-values* is non-2nil*, it is used to alter the ``number of values already returned'' as recorded in the stack group. This may alter the length of the list that is the first value. The value you get is the altered one, in that case. 3eh:sg-frame-special-pdl-range* 1sg* 1frame* Returns two values delimiting the range of 1sg*'s special pdl that belongs to the specified stack frame. The first value is the index of the first special pdl word that belongs to the frame, and the second value is the index of the next word that does not belong to it. If the specified frame has no special bindings, both values are 2nil*. Otherwise, the indicated special pdl words describe bindings made on entry to or during execution in this frame. The words come in pairs. The first word of each pair contains the saved value; the second points to the location that was bound. When the stack group is not current, the saved value is the value for the binding made in this frame. When the stack group is current, the saved value is the shadowed value, and the value for this binding is either in the cell that was bound, or is the saved value of another binding, at a higher index, of the same cell. The bit 2sys:%%specpdl-closure-binding* is nonzero in the first word of the pair if the binding was made before entry to the function itself. This includes bindings made by closures, and by instances (including 2self*). Otherwise, the binding was made by the function itself. This includes arguments that are declared special. 2symeval-in-stack-group* can be used to find the value of a special variable at a certain stack frame (4(STACKGROUPS-1)Stack Group Functions*). =Node: InputOutput in Stack Groups =Text: 3INPUT/OUTPUT IN STACK GROUPS* Because each stack group has its own set of dynamic bindings, a stack group does not inherit its creator's value of 2*terminal-io** (see 4(IOSYSTEM-2)Standard Streams*), nor its caller's, unless you make special provision for this. The 2*terminal-io** a stack group gets by default is a ``background'' stream that does not normally expect to be used. If it is used, it turns into a ``background window'' that will request the user's attention. Often this happens when an error invokes the debugger. If you write a program that uses multiple stack groups, and you want them all to do input and output to the terminal, you should pass the value of 2*terminal-io** to the top-level function of each stack group as part of the 2stack-group-preset*, and that function should bind the variable 2*terminal-io**. Another technique is to use a closure as the top-level function of a stack group. This closure can bind 2*terminal-io** and any other variables that should be shared between the stack group and its creator. =Node: An Example of Stack Groups =Text: 3AN EXAMPLE OF STACK GROUPS* The canonical coroutine example is the so-called samefringe problem: Given two trees, determine whether they contain the same atoms in the same order, ignoring parenthesis structure. A better way of saying this is, given two binary trees built out of conses, determine whether the sequence of atoms on the fringes of the trees is the same, ignoring differences in the arrangement of the internal skeletons of the two trees. Following the usual rule for trees, 2nil* in the cdr of a cons is to be ignored. One way of solving this problem is to use 1generator* coroutines. We make a generator for each tree. Each time the generator is called it returns the next element of the fringe of its tree. After the generator has examined the entire tree, it returns a special ``exhausted'' flag. The generator is most naturally written as a recursive function. The use of coroutines, i.e. stack groups, allows the two generators to recurse separately on two different control stacks without having to coordinate with each other. The program is very simple. Constructing it in the usual bottom-up style, we first write a recursive function that takes a tree and 2stack-group-return*s each element of its fringe. The 2stack-group-return* is how the generator coroutine delivers its output. We could easily test this function by changing 2stack-group-return* to 2print* and trying it on some examples. 3(defun fringe (tree)* 3 (cond ((atom tree) (stack-group-return tree))* 3(t (fringe (car tree))* 3 (if (not (null (cdr tree)))* 3 (fringe (cdr tree))))))* Now we package this function inside another, which takes care of returning the special ``exhausted'' flag. 3(defun fringe1 (tree exhausted)* 3 (fringe tree)* 3 exhausted)* The 2samefringe* function takes the two trees as arguments and returns 2t* or 2nil*. It creates two stack groups to act as the two generator coroutines, presets them to run the 2fringe1* function, then goes into a loop comparing the two fringes. The value is 2nil* if a difference is discovered, or 2t* if they are still the same when the end is reached. 3(defun samefringe (tree1 tree2)* 3 (let ((sg1 (make-stack-group "samefringe1"))* 3(sg2 (make-stack-group "samefringe2"))* 3(exhausted (ncons nil)))* 3 (stack-group-preset sg1 #'fringe1 tree1 exhausted)* 3 (stack-group-preset sg2 #'fringe1 tree2 exhausted)* 3 (do ((v1) (v2)) (nil)* 3 (setq v1 (funcall sg1 nil)* 3 v2 (funcall sg2 nil))* 3 (cond ((neq v1 v2) (return nil))* 3 ((eq v1 exhausted) (return t))))))* Now we test it on a couple of examples: 3(samefringe '(a b c) '(a (b c))) => t* 3(samefringe '(a b c) '(a b c d)) => nil* As stack groups are large, and slow to create, it is desirable to avoid the overhead of creating one each time two fringes are compared. It can easily be eliminated with a modest amount of explicit storage allocation, using the resource facility (see 4(MANLISTSTR-3)Defining Resources*). While we're at it, we can avoid making the exhausted flag fresh each time; its only important property is that it not be an atom. 3(defresource samefringe-coroutine ()* 3 :constructor (make-stack-group "for-samefringe"))* 3(defvar exhausted-flag (ncons nil))* 3(defun samefringe (tree1 tree2)* 3 (using-resource (sg1 samefringe-coroutine)* 3 (using-resource (sg2 samefringe-coroutine)* 3 (stack-group-preset sg1 #'fringe1 tree1 exhausted-flag)* 3 (stack-group-preset sg2 #'fringe1 tree2 exhausted-flag)* 3 (do ((v1) (v2)) (nil)* 3(setq v1 (funcall sg1 nil)* 3 v2 (funcall sg2 nil))* 3(cond ((neq v1 v2) (return nil))* 3 ((eq v1 exhausted-flag) (return t)))))))* Now we can compare the fringes of two trees with no allocation of memory whatsoever.