Stack Parser
============

The Scheme interpreter normally uses a stack, or a stack-like object, to implement continuations.  The information stored in the stack is extremely useful for debugging.  In fact, when an error occurs, it is often the only information available.  Error messages generated by the interpreter often contain some information that was obtained from the stack.

Normally, the stack is examined by means of the debugger.  However, much of the design of any debugger is a human interface, and there will always be someone who does not care for a particular debugger.  In that case, it is desirable for that person to be able to write another debugger without too much trouble.  Further, there are situations in which it is desirable for a program to analyze the stack, rather than a human, particularly when handling error conditions.

Thus it is desirable to have some programming interface for examining the stack.  This section describes one such interface, called the stack parser.  The stack parser is intended to be the lowest level in a heirarchy of stack inspecting interfaces, and because of this it provides very little functionality.  Its basic purpose, as the name conveys, is to parse the stack into meaningful pieces, called stack frames.  In addition, it interprets a small subset of the data that it parses in order to hide some uninteresting details of the interpreter's representation.  However, an important principle in the stack parser's design is that it should provide all of the information in the stack, no matter how trivial.  Thus even the ``hidden'' data can be accessed when necessary.

Note: at this time the stack parser does not understand how to parse the stack frames created by compiled code.  For this reason, we will ignore compiled code; when we have finished implementing the part for compiled code this section will be revised to reflect any relevant changes. However, much of what is written here applies equally to compiled code frames.

Continuations and Stack Frames
------------------------------

Before discussing the structure of stack frames, we need to describe how the information stored on the stack is related to the program being executed.  This involves the concept of continuations.  A continuation is a procedure which is associated with a particular expression in a program.  The continuation is closed at the start of the expression's evaluation.  Once the value of the expression is computed, the continuation is invoked with that value as its argument.  It is the continuation's responsibility to continue the execution of the program according to the semantics of the containing expression (of which the original expression is a part).

The stack is a mechanism used by the interpreter to implement continuations efficiently.  Whenever a subexpression is evaluated, some information is pushed on the stack, along with a return address.  The return address can be thought of as identifying the continuation's code, while the other information is the ``environment'' in which the continuation is closed.  This block of information, the return address plus closing ``environment'', is parsed by the stack parser into a single stack frame.

Thus we can see that the basic action of the stack parser is to break up the stack into frames, each of which contains one return address and some associated data.  Each of these frames corresponds directly to a continuation, which in turn corresponds directly to some expression in the program being executed.

Now, one of the unusual features of the Scheme language is that it possesses first-class continuations.  Continuations, as we have described them above, are not first-class because they are not objects that can be pointed at or passed around by programs.  However, Scheme provides a mechanism, call-with-current-continuation, which will construct an object to represent the continuation of the expression in which it appears.  In order to prevent confusion, we will refer to first-class continuations as external continuations, and the continuations informally defined above as internal continuations.  This will facilitate statements such as: ``an external continuation is a Scheme object which represents an internal continuation''.

Basic Stack Parsing
-------------------

This leads us into the next topic, which is the overall structure of the stack parser.  We have already defined the basic action, namely parsing the stack into frames which have a one to one correspondence with internal continuations.  What we have not defined is how the stack parser is invoked to produce these frames.

We mentioned earlier that the stack parser can hide certain pieces of information that it is interpreting in other ways.  None of the procedures in this section hide any information; the next section will describe how the information hiding is performed.

The following procedure is the main entry to the stack parser.  In subsequent definitions, an argument called STACK-FRAME is assumed to be an object of type stack-frame.

 -- procedure+: continuation->stack-frame continuation
     Parses a continuation into a sequence of stack frames. CONTINUATION must be an external continuation.  The returned value is the first stack frame in the sequence, which corresponds to CONTINUATION.

Using continuation->stack-frame, combined with operations described below, we can obtain a stack frame corresponding to any internal continuation that currently exists.  Normally only a small subset of the internal continuations have external continuations associated with them, because in normal programming external continuations are rarely needed.  But in some circumstances it is desirable to be able to invoke a particular internal continuation for which no corresponding external continuation is known to exist.  The following operation provides a means for constructing such an external continuation:

 -- procedure+: stack-frame->continuation stack-frame
     This operation is the inverse of continuation->stack-frame.  The argument STACK-FRAME must be an object of type stack-frame. The returned value is an external continuation which corresponds to STACK-FRAME.

Now, here are the basic operations on stack frames:

 -- procedure+: stack-frame? object
     This predicate is true iff OBJECT is an object of type stack-frame.

Earlier, when we defined internal continuations, we discussed how they are constructed by pushing a return address and some other information on the stack.  We will refer to the ``other information'' as the elements of a stack frame.  The elements of any particular stack frame always consist of a fixed number of Scheme objects.  Note that the return address is not considered one of a stack frame's elements.

 -- procedure+: stack-frame/return-address stack-frame
 -- procedure+: stack-frame/return-code stack-frame
     The value of stack-frame/return-address is the return address associated with STACK-FRAME.  Stack-frame/return-code is useful for interpreter stack frames, and might have been defined as follows:

          (define (stack-frame/return-code stack-frame)
            (return-address/code (stack-frame/return-address stack-frame)))

 -- procedure+: stack-frame/length stack-frame
     This operation returns the number of elements associated with STACK-FRAME.

 -- procedure+: stack-frame/ref stack-frame index
     This operation returns one of the elements associated with STACK-FRAME.  INDEX specifies which element, and must be a non-negative exact integer strictly less than the number of elements.  The elements are number in order from the top of the stack, in other words, smaller indices indicate elements that were pushed later in time.

 -- procedure+: stack-frame/next stack-frame
     This operation returns the next stack frame in the sequence.  This stack frame represents the continuation which is waiting for the result being computed by the continuation which STACK-FRAME represents.  The value of this operation is sometimes referred to as the next earlier stack frame, because the continuation it represents was constructed earlier in time than the continuation associated with STACK-FRAME.

The above procedures form a complete set.  With them, we can examine every object that is pushed on the stack.  Naturally, understanding what all those objects mean requires a detailed knowledge of how the interpreter uses each stack frame.  The stack parser does not, in general, provide any interpretation of the contents of a stack frame; that is not its purpose. However, it does interpret a specific subset of stack frames, and provides a mechanism to facilitate general interpretation.  The next sections discuss this in detail.

Subproblem Frames
-----------------

We now have a complete set of operations for accessing the contents of the stack.  However, there are several types of stack frames, most of them quite common, whose interpretation is either integral with the process of parsing the stack, or whose interpretation affects the meaning of other stack frames.  An example of the latter type is the frame which restores the interrupt mask to a particular value; this frame determines the interrupt mask which is active for all of the subsequent stack frames until another such frame is encountered.

An example of the former type will require some explanation of how the stack is used.  We will discuss a particular implementation of the stack which illustrates the relevant behavior (there are existing alternate implementations which do not behave this way).

In the example implementation, the stack is a reserved area of memory, separate from Scheme's heap, in which objects are pushed and popped using conventional machine instructions.  When an external continuation is constructed, a Scheme vector of the appropriate size is allocated and the contents of the stack are popped into it; in other words, the stack is copied into the heap.  This heap allocated copy is called a stacklet.  Then the external continuation is constructed, and among other things it contains a pointer to the stacklet.

However, after the external continuation has been made, the stack should appear to have all of those things still pushed on it, as well as anything we subsequently push.  So, what happens is we erase the reserved stack area, and then push a frame, of type join-stacklets, which contains a pointer to the stacklet we have just made.  Then we continue pushing and popping as normal.  However, if we return into the join-stacklets frame, it causes the contents of the stacklet to be copied back into the reserved stack area, and subsequently returns to the new top of stack.

We promised that this was leading up to an example, and so it is.  The stack parser notices stack frames of type join-stacklets, and treats them specially.  Because of the way these frames are used, they always appear at the end of a stacklet.  When the stack parser sees one, however, it continues parsing at the beginning of the stacklet pointed at by that frame.  Although join-stacklets frames appear in the output of the stack parser, they are uninteresting because the information in them has already been used.  Thus it is useful to be able to ignore them.

So, getting back to the main topic for this section, there are several types of frames which normally it is useful to ignore (in the terminology used earlier, we wish to ``hide'' these frame types).  The mechanism used to distinguish interesting frames, which in this case is all other frames, is the following:

 -- procedure+: stack-frame/subproblem? stack-frame
     This predicate is true iff STACK-FRAME is a subproblem frame.  All frames for which this predicate is false are handled specially in some way by the stack parser and are not usually interesting to look at.

 -- procedure+: continuation/first-subproblem continuation
     This operation is like continuation->stack-frame except that it skips over any non-subproblem frames, returning the first subproblem frame in the sequence, or #f if there are none.

 -- procedure+: stack-frame/next-subproblem stack-frame
     This operation is like stack-frame/next except that it skips non-subproblem frames, returning the next subproblem frame in the sequence, or #f if there are no more.

As we mentioned above, there are certain kinds of frames whose interpretation affects the meaning of other frames.  There are several of these, and they all operate in a similar manner.  The example given earlier was the frame used to restore the interrupt mask.  This frame is pushed by operations such as without-interrupts, which turn off interrupts for the extent of a particular procedure call.  This saves the interrupt mask which is in effect at the time of the call by pushing it on the stack.  But the stack parser notices these frames and keeps track of them, so that it can associate the correct interrupt mask with each stack frame.

Here are the operations that access the information gained by noticing this type of frame:

 -- procedure+: stack-frame/dynamic-state stack-frame
     Returns the dynamic state associated with STACK-FRAME. This is the object that would be returned by calling current-dynamic-state if that stack frame were active.  This information is saved on the stack by dynamic-wind.

 -- procedure+: stack-frame/fluid-bindings stack-frame
     Returns the set of fluid variable bindings associated with STACK-FRAME.  This information is saved by fluid-let when deep fluid binding is enabled.  Normally this is used only on multiprocessors.

 -- procedure+: stack-frame/interrupt-mask stack-frame
     Returns the interrupt mask associated with STACK-FRAME. This information is saved by several operations, including without-interrupts.

 -- procedure+: stack-frame/reductions stack-frame
     Returns the history information associated with STACK-FRAME.  The history is a debugging mechanism which records the value of the expression and environment each time that the interpreter evaluates an expression.  This information is stored in a special structure which has separate recordings for each subproblem.  This procedure returns the set of recordings for the subproblem assiciated with STACK-FRAME.  For more information on this, see the history code (there's no documentation yet).

Stack Frame Types
-----------------

The final topic of this section is how the stack parser supports building more powerful stack analysis tools.  As was stated earlier, the stack parser itself provides very little functionality.  In particular, it doesn't try to interpret the contents of most stack frames in any way.  Instead, it provides a means of attaching additional information to particular types of stack frames, so programs can use that information to decode the meaning of the stack frame's contents.

To provide this functionality, each stack frame has associated with it a special object called a stack frame type.  Two stack frames which have the same return address share the same type object.  In general, the idea of a stack frame type is that all stack frames which result from closing the same continuation are similar, in that they will be laid out on the stack in a uniform way, and that the corresponding items in each frame will have the same meaning in all such frames.  Thus, such a class of stack frames shares a unique stack frame type object which can be used to attach information which describes all of the frames in the class.

 -- procedure+: stack-frame/type stack-frame
     This procedure returns the stack frame type object associated with STACK-FRAME.

 -- procedure+: stack-frame-type? object
     This predicate is true iff OBJECT is a stack frame type object.

This is the basic mechanism available for attaching things to stack frame type objects:

 -- procedure+: stack-frame-type/properties stack-frame-type
     This procedure returns the unique 1D-table object associated with STACK-FRAME-TYPE.  Arbitrary objects can be associated with STACK-FRAME-TYPE by entering them in the table (see 1D Tables).

For stack frames constructed by the interpreter, there is a one to one correspondence between return codes and stack frame types.  The following procedures capture this correspondence (note that this may change with the introduction of compiled code stack frame types):

 -- procedure+: microcode-return/code->type code
     Returns the stack frame type object associated with CODE. CODE must be a non-negative exact integer in the appropriate range for microcode return codes.

 -- procedure+: stack-frame-type/code stack-frame-type
     Returns the microcode return code associated with STACK-FRAME-TYPE.  This is the inverse of microcode-return/code->type.

Return Addresses
----------------

REP Loop
========

The MIT Scheme Read-Eval-Print loop (abbreviated REP loop) is more complex than that of many other Lisp (or Scheme) implementations. This complexity can be attributed to fundamental differences in the MIT Scheme dialect: first class continuations and environments. Other Lisps, lacking these features, make do with a simple REP loop.  At any given time there is just one continuation and one environment, so no more is needed.

The situation in MIT Scheme is significantly different.  Instead of a single REP loop there is a tree of REP loops, each with its own state.  Each REP loop is associated with a single continuation, and the tree structure reflects the structure of the underlying continuations.  The state of a REP loop includes a first class environment, and expressions are evaluated relative to that environment when the loop is active.

When the standard error handler is invoked, a new REP loop is added to the tree, as a child of the previous REP loop.  The environment of this REP loop is sometimes different than that of the original REP loop.  When the error is fixed, the REP loop can be exited in a variety of ways, causing the original REP loop to become current again.  Alternatively, an error occurring within the error REP loop will cause yet another REP loop to be added to the tree.  This process prevents new errors from eradicating the state of old errors before they are fixed.

This section describes how to program REP loops.  Some familiarity with the use of REP loops is assumed.  These are built up from a simpler mechanism, command loops, which can be used for other kinds of interactive programs (such as debuggers).

Using REP Loops
---------------

Command Loop
------------

Command loops are used to capture a useful part of the REP loop abstraction.  In particular, they implement the organizational tree structure and I/O control, but do not specify the particular form of command interaction.  Instead, the creator of the command loop supplies a procedure which is responsible for reading input, interpreting it, and writing any relevant output.

The nodes in the command loop tree structure are cmdl objects. These objects are created using the make-cmdl procedure, and each contains a parent (another cmdl), a driver (the interpreter procedure), and some state.

 -- procedure+: make-cmdl parent input-port output-port driver state message
     This procedure creates a new cmdl object and attaches it to the cmdl tree.  PARENT must be another cmdl object or #F, INPUT-PORT must be an input port, OUTPUT-PORT must be an output port, DRIVER must be a procedure of one argument, and MESSAGE must be a cmdl-message object.  STATE may be any object.

     This procedure invokes DRIVER on the new cmdl object repeatedly.  While DRIVER is executing, the new cmdl object is the value of nearest-cmdl.  The value of DRIVER must be a cmdl-message, which is printed immediately upon return. MESSAGE is printed, once, before the first call to DRIVER.

     Make-cmdl does not return normally.  To exit the dynamic context of this procedure, a non-local transfer of control must be used (see Proceeding).

 -- procedure+: push-cmdl driver state message
     This useful procedure calls make-cmdl, passing the value of nearest-cmdl as the parent, and using the parent's I/O ports.

 -- procedure+: cmdl? object
     This predicate is true iff OBJECT is a cmdl object.

 -- procedure+: cmdl/parent cmdl
 -- procedure+: cmdl/level cmdl
 -- procedure+: cmdl/input-port cmdl
 -- procedure+: cmdl/output-port cmdl
 -- procedure+: cmdl/state cmdl
 -- procedure+: cmdl/driver cmdl
 -- procedure+: set-cmdl/input-port! cmdl input-port
 -- procedure+: set-cmdl/output-port! cmdl output-port
 -- procedure+: set-cmdl/state! cmdl state
     These procedures access and modify various components of a cmdl object.  All of the components correspond directly to arguments passed to make-cmdl, except for cmdl/level.  The latter is a positive integer that counts the depth of CMDL in its tree; if CMDL has no parent, the level is 1, otherwise it is one more than the level of its parent.

 -- procedure+: nearest-cmdl
     This procedure returns the cmdl object that is currently active.

 -- procedure+: cmdl/base cmdl
     This procedure, starting from CMDL, finds the ancestor that has no parent.

The following two procedures are useful for altering the flow of control within command loops.

 -- procedure+: cmdl/proceed-continuation cmdl
     One of the components of every cmdl object is the ``proceed continuation'' that was active at the time of its creation.  This continuation is useful for exiting the command loop and resuming the computation that was previously in effect.  This procedure returns the proceed continuation associated with CMDL.

 -- procedure+: cmdl/continuation cmdl
     Each time the command loop executes its DRIVER, the continuation of the driver is saved.  This procedure returns that continuation for CMDL.  This continuation is useful for aborting the execution of the driver, and should be invoked with a cmdl-message as its value.

CMDL Messages
-------------

The cmdl-message abstraction provides a uniform interface for defining and combining a variety of message generators.  It is preferable to using strings because the system can alter the form of the printed message to fit different user interfaces (such as Emacs).

cmdl-message objects are created and passed into the command loop mechanism (usually as the value of a command loop driver), where they are invoked to print their value.  Most messages are generated using the following procedure:

 -- procedure+: cmdl-message/standard string
     Creates and returns a new cmdl-message object that prints STRING.  This object has customization hooks that cause it to behave specially for Emacs.

 -- procedure+: cmdl-message/strings . strings
     Creates and returns a new cmdl-message object that prints each of the argument STRINGS, in order, separated by newlines.

 -- procedure+: cmdl-message/null
     Returns a cmdl-message object that prints nothing.  This is most useful in conjunction with cmdl-message/append.

 -- procedure+: cmdl-message/active thunk
     Creates and returns a new cmdl-message object that invokes THUNK to print its message.  THUNK should be a procedure of no arguments that prints a message on the current output port.

 -- procedure+: cmdl-message/append . messages
     Returns a new cmdl-message object that causes each of the argument MESSAGES to print sequentially.  The arguments must all be cmdl-message objects.

 -- procedure+: cmdl-message/error message . irritants
     This creates a cmdl-message object that uses format-error-message to write its message (see Error Messages).

CMDL Interrupts
---------------

The procedures described in this section are used to alter the flow of control within command loops in very fixed ways.  Normally, these procedures are invoked by typing specific key sequences on the console keyboard, for example, G normally invokes the procedure cmdl-interrupt/abort-top-level.  The procedures accept no arguments, and they never return; they are invoked specifically to effect a non-local transfer of control.

 -- procedure+: cmdl-interrupt/abort-nearest
     This procedure aborts the current computation and resumes the nearest command loop.  This is done by invoking (cmdl/continuation (nearest-cmdl)).

 -- procedure+: cmdl-interrupt/abort-previous
     This procedure aborts the current computation and resumes the parent of the nearest command loop, i.e. (cmdl/continuation (cmdl/parent (nearest-cmdl))).  If the nearest command loop has no parent, this is equivalent to cmdl-interrupt/abort-nearest.

 -- procedure+: cmdl-interrupt/abort-top-level
     This procedure aborts the current computation and resumes the ``top-level'' command loop, i.e. (cmdl/base (nearest-cmdl)).

 -- variable+: cmdl-interrupt/abort-top-level/reset?
     If the value of this variable is true, cmdl-interrupt/abort-top-level will proceed from the ``top-level'' command loop instead of resuming it.  This normally causes the entire command loop tree to be exited and a new one to be started.

     By default this variable has a false vaue.  Practical consequences of setting this to a true value include discarding the REP loop history and and resetting the prompt whenever G is typed.

 -- procedure+: cmdl-interrupt/breakpoint
     This procedure interrupts the current computation and starts a breakpoint REP loop.  The REP loop inherits its state from the nearest REP loop.  Proceeding from the breakpoint causes the interrupted computation to resume.

Proceeding
----------

The proceed mechanism is mostly orthogonal to the command loop mechanism, except that the current proceed continuation is recorded whenever a new command loop is made.  The basic idea is that there is always a current proceed continuation, and proceed invokes that continuation on some value.  The current proceed continuation is dynamically bound by with-proceed-point.

The precise value passed to the proceed continuation is determined by the value filter, which is dynamically bound at the same time as the proceed continuation.  The proceed filter is a procedure that is passed the proceed continuation and a list of arguments.  It then performs some action, usually invoking the continuation, based on the arguments.

An example of an unusual value filter is the one used by the standard error handler.  This value filter, if given a null list of arguments, invokes the proceed continuation.  Otherwise, it skips over one stack frame in the continuation and invokes the next frame with the first argument.  This implements the following behavior: calling (proceed) from an error causes the erring expression to be retried (sometimes useful for unbound variables).  Calling (proceed VALUE) ignores the erring expression, returning VALUE as if the expression had completed evaluating and returned that value.

 -- procedure+: with-proceed-point value-filter thunk
     This procedure executes THUNK with new dynamic bindings for the proceed continuation and the proceed value filter.  The proceed continuation is bound to the continuation of the call, while the proceed value filter is bound to VALUE-FILTER.

 -- procedure+: with-standard-proceed-point thunk
     This procedure is like with-proceed-point except that it supplies a standard value filter.  The standard value filter invokes its argument continuation on the first argument in the argument list, or the non printing object if there are no arguments.

 -- procedure+: current-proceed-continuation
     Returns the current proceed continuation.

 -- procedure+: proceed . arguments
     Invokes the current proceed value filter on two arguments: (1) the current proceed continuation, and (2) the list ARGUMENTS.

REPL
----

A REP loop is a specific type of command loop designed to evaluate Scheme expressions.  A REP loop is distinguished from other command loops by its state component, which contains several items specific to the evaluation of Scheme expressions, and by its driver component, which understands how to read expressions from the input port, evaluate them, and write the results to the output port.  In addition, REP loops provide input prompting, input and output histories, and control over the evaluation environment and syntax table.

REP loops are represented by Scheme objects called repl objects.  These objects satisfy the cmdl? predicate.

 -- procedure+: make-repl parent environment syntax-table prompt input-port output-port message
     This procedure, corresponding to make-cmdl, creates a new repl object, attaches it to the command loop tree structure, and repeatedly executes the REP driver, which reads an expression from the input port, syntaxes it, evaluates it, and returns the result as a cmdl-message object.

     ENVIRONMENT must be a first class environment, SYNTAX-TABLE must be a syntax table, and PROMPT must be a string.  All other arguments are the same as for make-cmdl.

 -- procedure+: push-repl environment message prompt
     This procedure corresponds to push-cmdl.  It creates a new repl object, inheriting its unspecified components from the nearest available repl object.

 -- procedure+: repl? object
     This predicate is true iff OBJECT is a repl object.

 -- procedure+: repl/prompt repl
 -- procedure+: repl/environment repl
 -- procedure+: repl/syntax-table repl
 -- procedure+: repl/reader-history repl
 -- procedure+: repl/printer-history repl
 -- procedure+: set-repl/prompt! repl prompt
 -- procedure+: set-repl/environment! repl environment
 -- procedure+: set-repl/syntax-table! repl syntax-table
     These procedure access and modify the standard components of a repl object.  The other accessors and modifiers defined on cmdl objects may also be used.

 -- procedure+: repl/parent repl
     This procedure is similar to cmdl/parent, except that it skips over any ancestors that are not repl objects.

 -- procedure+: nearest-repl
     This procedure is similar to nearest-cmdl, except that it skips over non-repl objects to find the nearest REP loop.

 -- procedure+: repl/base repl
     This procedure is similar to cmdl/base, except that it finds the farthest ancestor that is a repl object.  That ancestor may have a valid cmdl/parent, except that it is guaranteed not to have a valid repl/parent.

 -- procedure+: nearest-repl/environment
 -- procedure+: nearest-repl/syntax-table
     These procedures are useful abbreviations for getting the environment and syntax table, respectively, of the nearest repl object.