+III MSTACK: MEND's Representation of the Control Stack
+======================================================
+
+III.1 Program Execution In Muddle
+---------------------------------
+
+MEND's primary role is to allow the applications programmer to
+visually monitor the execution of a program. In a language like
+Muddle, this is most easily accomplished by showing the programmer a
+picture of the control stack.
+
+A Muddle program consists of the evaluation of a single object. The
+object is usually structured in some manner and itself contains other
+objects. The most common object is the FORM. This is a list of objects
+in which the first is (or evaluates to) some function and the rest are
+arguments to that function. A FORM is evaluated by applying the
+function to its arguments, usually after the arguments are themselves
+evaluated. This evaluation actually is initiated by the Muddle
+interpreter by applying the function EVAL to the original object. EVAL
+takes an object as its argument and returns the value to which it
+evaluates.
+
+Figure 1 shows a (simplified) static representation of the evaluation
+of a Muddle object. Starting with the FORM (list of objects in
+angle-brackets) to be evaluated, the flow of control/evaluation may be
+described as a depth-first search through the tree pictured. The
+arrows represent values being returned to previous levels. At the end
+of this "search" the FORM returns the value shown at the top.
+
+ Figure 1:
+
+ 31
+ ↑
+ <+ .A .B .C 5>
+ ↑ ↑ ↑ ↑ ↑
+ + .A .B .C 5
+ ↑ ↑ ↑
+ 6 8 12
+
+Typically the control stack will start with one object on it, the FORM
+to be evaluated. This evaluation will first require that the objects
+in the FORM (possibly FORMs themselves) be added to the stack and
+evaluated. EVAL recursively calls itself for this purpose. The stack
+builds (downward, by convention) until some object is placed on it
+which ls known by EVAL to need no further evaluation. This object is
+returned as its own value to the previous level and values continue to
+be returned upward until a level is reached where another object must
+be evaluated. In this manner, the stack grows and shrinks until the
+topmost (initial) object returns a value.
+
+III.2 Monitoring Program Execution
+----------------------------------
+
+The manner in which the stack builds, the objects are evaluated, and
+the values are returned illustrate most of what the program is doing.
+Other factors, including side effects and complied code, will be
+discussed at the end of this chapter. MEND's main display therefore
+shows a representation of the stack being continuously updated as
+execution/evaluation proceeds.
+
+There are essentially two ways that MEND could follow the flow of
+control of the application program. The most direct way, as attempted
+by MUMBLE[^14] and discussed in the last chapter, would be for MEND to
+execute the application program by simulating the operation of Muddle.
+This type of simulation has been shown to require a complex end all
+too often fragile structure. The debugging program would need to be
+constantly updated to match changes and additions to the Muddle
+language , but more importantly it would fail to properly handle
+programmer-defined primitives, several varieties of which are provided
+for by Muddle.
+
+A far more satisfactory method is to allow Muddle to execute the
+application program in more or less its normal fashion but to stand
+beck somewhere and watch. Fortunately Muddle contains a mechanism
+ideal for this, called multiprocessing. Basically another control
+stack , or process, may be created (independent of the first) that may
+be used to execute a different function with its own set of variable
+bindings. One such process, in this case MEND, may place another, the
+application program, into a single step mode where the latter will be
+stopped before each call to EVAL and again as each call returns. The
+MEND process will at these points be restarted and given information
+about what the application process is doing. MEND stores this
+information in a multi-level structure it creates called an MSTACK.
+
+Each level of an MSTACK corresponds to a level of the control stack
+being monitored. Each level contains the original object (actually, a
+pointer to it) being evaluated at that level and a new object, called
+the "displayed object", that will or does contain the results of
+evaluating each of the arguments or elements of the original. The
+displayed object is initially the same as the original (in a real
+sense, it is the original) but is systematically rebuilt as each
+element is evaluated and replaced by what it returns. Thus MEND can
+keep track of the relationship between the changing display and the
+unchanging program. (Figure 2 shows the various stages that the
+displayed object corresponding to the FORM being evaluated in Figure 1
+goes through. Each stage would in fact be painted over the previous
+one so that all of these stages represent only one line of the screen.
+The down-arrow shown in some of the stages is a place-holder that
+represents an object that is actually expanded on the next line of the
+screen.) A pointer is also kept showing which element is currently
+above this on the stack to be evaluated unless, of course, this is the
+initial element of the stack.
+
+ Figure 2:
+
+ <+ .A .B .C 5>
+ <+ ↓ .B .C 5>
+ <+ 6 .B .C 5>
+ <+ 6 ↓ .C 5>
+ <+ 6 8 .C 5>
+ <+ 6 8 ↓ 5>
+ <+ 6 8 12 5>
+
+ 31
+
+III.3 A Displayed Representation of Program Execution
+-----------------------------------------------------
+
+The printed representation of the stack occupies the top section of
+the screen and is the most prominent and important characteristic of
+MEND. Most often, in fact, it is only necessary to watch this display
+as the application program is executed to ascertain where a bug is
+located or to observe exactly how the program operates. Therefore
+considerable time has been spent making the operation of the MSTACK
+and associated display as natural and informative as possible.
+
+Using the collected information described in the previous section, a
+representation of the stack is displayed as a number of lines, each
+corresponding to one level. Each line shows a level number and the
+displayed object printed in "&-printing", named for the printing
+function &[^15] created by Greg Pfister. Although strictly speaking
+the stack builds upward (towards higher memory locations), it seams
+more natural to display and speak of the stack as building from the
+top downward, in the direction that printing normally occurs. As each
+element of the bottom level (the bottom line on this section of the
+screen) is placed on the stack for evaluation, a new line is added
+beneath the previous bottom-level line showing that element, and the
+element is replaced in the previous line by a pointer ("↓") marking
+its location. When the element finally returns a value, the returned
+value will replace the pointer in the displayed object.
+
+To avoid visual distraction, a minimum of updating is done on the
+screen. In most cases random access is used to replace only those
+lines that have changed. In general the complete stack will not fit in
+the display area allocated for it (whose size is user adjustable) so a
+scrolling procedure has been devised. The complete display area is
+rewritten whenever an attempt is made to write past the bottom or
+erase upward past a certain level while some lines are invisible
+because they have been scrolled off. The scrolling parameters have
+been selected to optimize the number of lines visible on the average
+vs. the frequency of scrolling. Level numbers allow the user to see
+how much is hidden "above the screen" and how deep the evaluation is
+nested.
+
+III.4 MEND Program Steps Vs. Muddle Steps
+-----------------------------------------
+
+To make it easier for the programmer to follow what the application
+program is doing, the speed of execution of the program must be
+controllable. MEND does this by inserting a constant, user adjustable
+delay between program "steps." One MEND step is not precisely the same
+as one Muddle step. Remember that a Muddle step is one call to or
+return from EVAL. Each MSTACK level, and therefore each displayed
+line, will have two Muddle steps associated with it. At the first
+step, MEND will create the level and add one line to the screen. At
+the second step, MEND will erase that line and put the returned value
+back into the previous line. For clarity MEND adds a third step
+between these two which actually occurs at the second Muddle stop.
+Before substituting into the previous line, the current one is first
+replaced by the returned value, the normal delay occurs, and then the
+"second" step occurs as described.
+
+Some types of Muddle objects are self-evaluating; EVAL will simply
+return the object it was given. Although nothing interesting has
+happened, two steps have occurred. In this case MEND will avoid
+clutter by pretending that no steps have occurred. (MEND only does
+this with built-in types that MEND recognizes, and the programmer
+should recognize, as being self-evaluating. Programmer-defined types
+that are self-evaluating will generate the usual number of MEND
+steps.)
+
+Another case of disparity between Muddle and MEND stops is more
+complex. First some further explanations about Muddle objects are
+needed Generally the interesting objects, the ones that generate MEND
+steps, are linear (usually list) structures containing a number of
+other Muddle objects, as are the FORMs described earlier. Normally
+during evaluation of such an object the elements will be evaluated one
+at a time from first to last. However this sequence is not always
+followed by Muddle. MEND cannot directly determine which element is
+about to be evaluated at each call to EVAL. It is only given the
+object to be evaluated itself and not its position in the parent
+structure. It is normally sufficient to do a comparison of this object
+with the elements of the parent, starting with the first element
+believed to not yet have been evaluated. Naturally, if the elements
+are evaluated out of order, this procedure may fail to find the
+desired match, because a Muddle object may contain the same element in
+two or more positions. Thus it is possible to match the
+about-to-be-evaluated object to the wrong occurrence of it. Further
+complications arise because some functions can sometimes back up and
+re-evaluate their arguments.
+
+A strong attempt was made to make MEND dependent only upon the general
+characteristics of Muddle functions and not upon specific exceptions
+and idiosyncrasies. It was felt to be desirable to make MEND
+independent of both future changes to the language and
+programmer-defined "primitives" that would not be known to MEND.
+Besides, without actually simulating Muddle it is not possible to
+always get the information MEND needs. It was felt that the "general
+rule" approach would take care of a sufficiently large number of cases
+without falling into the simulator problem.
+
+It was determined after some experimentation, however, that MEND could
+not be made to work properly without some specific knowledge about
+several important cases in Muddle. Two functions, PROG and REPEAT,
+allow for branching the flow of control. They are normally
+first-to-last functions as described above but at times control may
+jump backwards to re-evaluate some elements. MEND was implemented so
+that if it cannot locate an element in its normal search path, it will
+start looking again from the beginning of the structure. If it is then
+found, the displayed object will be reinitialized to be as if
+evaluation had not yet proceeded past that point. Evaluation will then
+continue normally.
+
+Another phenomenon of Muddle that we must discuss is what this author
+labels the "clause" behavior. A clause is a list of objects given to a
+function as a single argument. The list is not itself evaluated, but
+some or all of its elements are evaluated. The most common function
+illustrating this behavior is COND, a general purpose conditional
+function. COND's arguments are all lists of objects. It sequences
+through these lists, evaluating the first object in each, until an
+evaluated object returns something considered "true." Then the rest of
+the objects in that list are evaluated and COND returns what the last
+object in the list returns. MEND's normal search path only looks at
+top-level elements and would therefore never find the ones actually
+being evaluated.
+
+This phenomenon seemed to be more widespread than the PROG/REPEAT one
+and could not be easily attributed to certain functions. The solution
+chosen here was to in all cases do a nested search in elements that
+looked as if they might be clauses. (The search actually goes one
+extra level deep to allow for certain special cases.) When a match is
+found in a clause, MEND will for clarity generate extra steps to make
+it appear to the user as if first the clause and then its appropriate
+element was put on the stack for evaluation. The clause will stay on
+the stack until some element that is not above it in the evaluation
+tree is evaluated. At that time the clause will be removed in an
+orderly manner, and the new element or clause plus element will be put
+onto the stack. To do this smoothly, up to six MEND steps may have to
+be generated for the one Muddle step. (See the example in Appendix A.)
+
+III.5 What the User Does Not See
+--------------------------------
+
+MEND, in its display of the MSTACK, attempts to show the user
+everything of importance that is happening as the program is executed.
+However certain features of Muddle cannot be captured in this sort of
+representation.
+
+One such feature is the existence of compiled code. Although Muddle
+was originally intended to be a high-level interpretive language, an
+assembler was written[^16], producing machine code that executes in
+the Muddle environment, to allow programmers to create "primitives"
+that perform functions not otherwise available in Muddle. Once the
+assembler was written, it was natural that a compiler[^17] followed.
+It translates normal Muddle code into Muddle assembly code which is
+then assembled. Typically Muddle programs are tested interpretively
+and, when fully debugged, complied in order to obtain a major increase
+in speed of execution.
+
+A call to a compiled (or assembled) function usually looks to the
+programmer and to MEND like a call to a Muddle primitive. The
+operation of the function is not seen except when it calls uncompiled
+functions. This does not present a major problem to MEND since
+generally only uncompiled functions are being debugged, and the
+compiled ones encountered are hopefully performing known functions
+properly.
+
+One feature of Muddle that MEND is unable to cope with is the
+interrupt system. The programmer may enable a large class of
+interrupts and assign handling functions wherever desired. Examples
+Include interrupts for characters being typed to a certain input
+channel and notification that the system is about to be brought down.
+(MEND uses interrupts to catch single character commands and to catch
+errors.)
+
+Recall that MEND monitors application program execution by placing its
+process into a single-stepping mode. When Muddle passes control to an
+interrupt handier, it temporarily causes the process to leave
+single-stepping mode. This is necessary partially because such a
+handler may be specified to run in a process other than the current
+one at the time of the interrupt. It unfortunately makes the handler
+invisible to MEND. it is therefore not currently possible to use MEND
+to debug interrupt handlers.
+
+There is a whole series of side-effects, such as printing by the
+application program, that are not directly seen in the MSTACK
+representation but are made visible by various other features of MEND.
+These will be discussed where appropriate in later sections.
+