Adding section 4

[mudman.git] / md / debugging.md

% A Dynamic Debugging System For Muddle
% Joel Mayer Berez
% January 1978

MIT Technical Memo 94

Laboratory for Computer Science\
Massachusetts Institute of Technology\
545 Technology Square Cambridge, Massachusetts 02139

Copyright
=========

This research was supported by the Advanced Research Projects Agency
of the Department of Defense and was monitored by the Office of Naval
Research under Contract No. N00014-75-C-0661.

This report was originally published in the United States in January
1978 without a copyright notice and without subsequent registration
with the U.S. Copyright Office within 5 years. Doing at least one of
those was a requirement of United States copyright law at that time.
This report is therefore in the public domain in the United States for
failure to comply with the required formalities. This means you're
free to download, modify and redistribute this report. People outside
of the United States must check the copyright laws of their country
before downloading or redistributing.

Abstract
========

Program debugging is a time consuming process. Conventional debugging
techniques and aids typically give the user a narrow view of the
program's operation, making debugging difficult. A debugging system
that would present a clear overall picture of a program's behavior and
would be both flexible and simple to operate would be a valuable tool.
Such a system was designed and implemented in for Muddle, a high-level
applicative programming language. This report discusses: the design
alternatives considered during the debugging system's design and
implementation phases, the reasons for the resulting design choices,
and the system attributes. A major attribute of the system (MEND) is
that it does not simulate the program being debugged but instead
monitors it from another process. This attribute results in a robust
and viable debugging system, because MEND not be modified in order to
handle each new extension to Muddle and/or each new user-defined
primitive.

This report reproduces a thesis of the same title submitted to the
Department of Electrical Engineering, Massachusetts Institute of
Technology, in partial fulfillment of the requirements for the Degree
of Bachelor of Science.

Acknowledgements
================

I wish to thank Al Vezza, for supervising this work and guiding me
along the road to winnage; Stu Galley, for the original idea; Bruce
Daniels and Gerald Farrell, for laying some of the ground work I have
built upon; Brian Berkowitz and Chris Reeve, for patiently repairing
my ailing Muddles; Marc Blank and Tak To, for support work and for
providing me with company during all-night console sessions; and all
of the other ITS and DynaMod hackers who have built a system well
worth using.

I Introduction
==============

I.1 Background
--------------

A time-consuming and frustrating aspect of computer programming is the
debugging of faulty programs. Current debugging techniques involve
tracing through the present operation of the program and mentally
comparing its action with one's concept of what should be happening.
With few exceptions, an understanding of where the program fails to
conform to "correct" operation must be made before the cause of the
failure can be determined and corrective action taken. This is where
much of the difficulty occurs.

In conventional debugging, it is rare for the programmer to have
available any more than the most basic aids. One usually has to
extrapolate from a bare minimum of information (such as machine
generated error messages) or one may be buried under a large excess of
information, most irrelevant (such as a core dump). Even with the more
advanced aids, the programmer typically gets but a small window in the
operation of the program through which, sooner or later, she or he
will locate the problem. A well-localized fault will be relatively
easy to spot compared to a global problem that the programmer may only
catch glimpses of through the debugging window.

In a compiler language, the programmer's best hope is to insert
statements to print intermediate results or to try to separate the
program into easier-to-handle modules. There are a few more advanced
aids available[^1], but their use is limited. One problem is that the
program is, in effect, first translated into a lower-level language
(generally "machine" language) and then executed interpretively in
that language. The original symbols and syntax of the source program
are lost, or saved only with great difficulty, making analysis and
manipulation of the executing program a very painful process.

If the programmer is using an interpretive language with facilities
for interaction, things are considerably easier. The common technique
is to stop execution at strategic points and examine the state of the
environment. Since this is done interactively, with the source program
still available in more or less its original form, the cause of the
problem can often be found in less time than it could otherwise. one
of the best example of this approach is the use of DDT (Dynamic
Debugging Tool/Technique)[^2][^3].

DDT basically works with machine-language programs. However, by freely
translating between numbers and symbols through the use of a table
generated by the assembler, DDT makes programs look to the programmer
like symbolic assembly-language programs. The user of DDT can operate
in free-run mode or in n-step (statement) mode, switching between them
at will. In either case one can set a breakpoint at any statement,
which will cause execution to stop just before the statement is
executed. Whenever stopped in DDT, the user can examine or change the
contents of any location. This can be done in several data modes
(e.g., unsigned octal, full ASCII, sixbit, etc.) including the use of
symbols to represent addresses. Arbitrary numeric expressions can also
be evaluated without affecting the program.

One main advantage of DDT is that the debugging environment is very
similar to the language environment the programmer used to write the
program. One has to learn only the DDT commands rather than an
entirely new language. Another advantage is the user's ability for
viewing the results of the changes. In addition, one can quickly see
the results of the changes and act accordingly.

The main deficiency of DDT is that, although is names include the word
"dynamic", its operation is really static. The application program can
run freely, but when the programmer wants to see what is taking place,
the program must be stopped. Although the real interest may be about
changes on a gross scale, perhaps thousands of program statements, if
one does not know exactly where the program is misbehaving, one may be
required to suspend execution of it every few instructions to examine
variable in order to obtain a true picture of the program's behavior.
This the programmers see *not what is taking place*, but *what has
taken place*, and through small windows at that. This is inefficient,
and the programmer can become bogged down in detail that hinders the
discovery of the true problem. The situation can be improved with the
use of breakpoints that allow the program is execute freely until a
breakpoint is reached, at which point the program halts. DDT is a
powerful tool but still leaves much to be desired in a debugging tool.

ESP[^4][^5] (Execution Simulator and Presenter) is one solution to the
static problem. It really is dynamic is that large amounts of data are
constantly being displayed for the programmer while the program is
being executed (actually, simulated). The information is presented in
graphic form to improve readability and reduce confusion. A user of
ESP may watch areas of the display where data of particular interest
are being presented. One also has many options including control over
the speed of execution, the type of quantity of data displayed, and
special (more flexible than just a breakpoint) conditions for halting
execution. In this way one can structure and control the picture
presented to more easily understand what the simulated program is
doing. And that is one key step in the process of debugging.

Like DDT, ESP has deficiencies also. These are mainly in the area of
editing and DDT-like examination of a faulty program. DDT is a
sophisticated language that ESP does not attempt to entirely replace.
The flaw in ESP is that it is not compatible with DDT. Ideally both
should be simultaneously available to the programmer, who can use
features of each as the need dictates.

DDT and ESP work with a low-level language whose operation can be
shown fairly simply. For example, ESP often shows flow of control by
just displaying the actual section of program being executed and
pointing to the current statement[^6]. It also draws lines to show
where branching has occurred and in some cases even indicates looping.
The display philosophy can be readily extended to higher level
languages that are line oriented, like BASIC, but it fails with
applicative ones, like LISP or Muddle. The latter type does not use a
linear control flow, but uses a complex depth-first tree structure.
Furthermore, quite complicated data structures can be built (or
themselves executed) that bear little relation to the appearance of
the program.

A good basic display for Muddle was used in MUMBLE[^7] (Gerald
Farrell's monitor and debugging aid). The code being executed is shown
in stack form. Each line shows a piece of code being evaluated. As
each object in the bottom line is evaluated, it is replaced by a
single downward-arrow symbol in this line and then printed on a new
line. In this way the evaluation can be followed from the top level
down to the current object being evaluated. Furthermore, after the
bottom is reached, the value returned by each line replaces its symbol
in the previous line. With this mechanism, the programmer can follow
execution in a natural and reasonably clear representation.

MUMBLE had some difficulties arising from the fact that it simulated
execution rather than just watching it and letting it proceed
naturally. This caused it to run slowly and to be complex yet fragile.
At the time MUMBLE was written, the Muddle compiler was not yet
perfected and the language itself lacked some of the multiprocessing
features that would have made simulation unnecessary. Later Farrell
replaced MUMBLE with a debugger utilizing new software related to
single-stepping a process, which eliminated the simulation but also
eliminated the feature reflecting results of an evaluation back into
the original code. Also, a mode was added that allowed the programmer
to attach conditions to parts of the program which would stop
execution when and if a condition was false. This is as far as MUMBLE
ever progressed, and it was not in use as of the time of the proposal
for the current work.

I.2 MEND
--------

After the Muddle compiler became operational and many additional new
software features became available, it appeared that it would be
possible to design and implement a debugging system that would be
comprehensive, easy to use, and reasonably fast. It was therefore
proposed that a debugging system for Muddle called MEND (Muddle
Executor , aNalyzer, and Debugger) be designed and implemented. It has
the following characteristics. (A glossary of special terms, those in
all capital letters, used here and throughout the rest of this memo
may be found in Appendix B.)

1.  MEND possesses a display similar to that of MUMBLE, including the
    replacement of arguments in a FORM by their values as they are
    evaluated.
2.  Execution is monitored from another process (as opposed to being
    simulated as in ESP) using 1STEP and related features[^8].
3.  Execution speed is variable by the user including a static single
    or multi-step mode where desired.
4.  MEND allows execution to run freely below a certain depth of
    evaluation or between certain points in the program and to run
    controlled elsewhere.
5.  Unconditional and conditional breakpoints are available that can
    be attached to any object to halt execution before evaluation of
    that object.
6.  The system is capable of keeping track of programmer specified
    conditions and of changing modes or giving some visible indication
    when the conditions are met (or not met).
7.  Information, such as the local value of programmer specified ATOMs
    and the values of programer specified FORMs, is constantly
    displayed beneath the main display.
8.  Each line in the main display area is &-printed (abbreviated
    printing, see glossary) and can be viewed in full at any time.
9.  At any time, with execution stopped, the user can EVAL objects in
    the ENVIRONMENT of the program. This means the user can examine
    the state of the program or change it.

I.3 Possible Additional Characteristics
---------------------------------------

Certain other characteristics were seen as desirable for MEND but
possibly beyond the scope of this project. If time permitted these
features were to be included in the system:

1.  The IMLAC multi-screen capability would be used to allow the user
    to rapidly switch between the debugger display and the program's
    own output. Other system output could also be put on additional
    pages.
2.  The editor IMED (an editor for Muddle objects analogous to
    IMEDIT[^9]) would be tied into the system to allow easy editing.
    PRINTTYPE and READ-TABLEs would be used to allow breakpoints to be
    easily set and removed in IMED as single symbols. Other control
    codes and statements could also be inserted using this editor.
3.  At the applications programmer's option and within certain limits,
    execution could be reversed either so that something different
    could be tried or for purposes of reexamining the process for
    something that may have been missed the first time. This feature
    could come in two possible forms, the UNDO package[^10] to
    actually reverse execution or a simulation displaying information
    previously stored by the system.

I.4 Design and Implementation
-----------------------------

MEND was designed with the intent of providing the application
programmer with many options so that debugging could proceed in the
most suitable manner for each situation. In the normal running state,
MEND displays several kinds of information on the screen. Most
important is an area showing the execution of the application program
being debugged in stack form. The only other area that is always
present is a line or two of status information about the current
operation of MEND showing its current speed of execution (user
adjustable) and the state of each modifiable mode.

It was intended that the output of the application program be saved by
MEND for later reference. The user of MEND could then elect to have
the most recent output constantly displayed in a window on the main
screen (see section on future work). If multi-screening were
available, the output could be kept on another virtual screen. That
screen could be displayed or made invisible at the user's option
without stopping MEND.

Information such as programmer specified values of ATOMs, structured
objects, and, in general, the value of any Muddle expression may be
constantly displayed. MEND is also capable of displaying such
information on an exception basis according to some predescribed
condition. Such information is &-printed but is viewable in full when
desired.

It is important for a debugging system like MEND to be compatible with
and to take advantage of available software in related areas. One such
area is editing. There were two Muddle editors in use when the
proposal for this work was made, EDIT[^11] and IMED. The main
difference between them is that IMED uses the local editing features
of the IMLAC while EDIT does not. EDIT, however, has the advantage of
being the only one that possesses breakpoint capabilities. Whichever
proved to be most compatible with MEND (possibly both) would be
slightly modified to allow the setting and removing of certain MEND
codes including, in the case of IMED, breakpoints.

Muddle itself has many features that greatly aid the debugging
process. One of these is FRAMES. This function can be used to print
the stack of functional evaluations and applications when execution is
halted at any depth below the top level. At this point it is also
possible to get the values of objects in the current ENVIRONMENT and
to change them. One can even restart execution at a higher level after
making such changes. Because the Muddle debugging features are quite
powerful, MEND was designed to allow the user to stop execution (of
the application program) and to use these aids or any others built in
to Muddle with the MEND system itself transparent. Evaluation would
take place in the ENVIRONMENT of the application program.

MEND now includes the main features of all the debuggers that have
been mentioned and enough other features that it should prove to be
quit useful for the analysis and debugging of Muddle programs. It
should also serve as a good example of the type of debugging system
that can be built around an applicative type language.

II Terminal Display
===================

II.1 IMLAC Console Program
--------------------------

One basic concern throughout the project was the display: how the
information made available by MEND would be presented to the user. To
a large extent the physical characteristics of Muddle, ITS[^12]
(Incompatible Timesharing System, the operating system used on the
Dynamic Modeling System computer), and the available terminals
dictated what was reasonably possible.

The terminal most commonly used by users of the Dynamic Modeling
System is the IMLAC PDS-1. This is a minicomputer capable of having
programs loaded into it from the PDP-10 host computer. One program
written for it by Dave Lebling is MSC, a multiple-screen terminal
program. Up to four virtual screens (or pages) can be created that
will individually operate like the actual screen area of the standard
terminal program (SSV[^13]). Output may be directed to any one of the
screens and any screen may be visible or invisible at any instant of
time, at the programmer's option. Selection of screen is controllable
either by program from the host or locally by the user.

It was originally Intended that MEND would use MSC for its normal
display. One page would constantly show MEND's representation of the
control stack of the application program. Output initiated by the
program being debugged would go to a second page. A third page would
be used for interaction with MEND and would show user typein along
with any output from MEND that one was interested in seeing. The
latter would include, by user request, full displays of both objects
printed in an abbreviated form on the page containing the control
stack of the application program and values being monitored or traced.
The user could switch back and forth among the pages at will during
the execution of the program. The application program would have a
full standard screen to write onto, and ample room would be available
for the information to be displayed by MEND.

After a fair amount of testing, this proposal was discarded for the
following reasons. First, MSC was supposed to look just like SSV for
individual virtual screens. Unfortunately new features added to SSV
had not also been added to MSC. A primary reason for this disparity
was that the new features encroached upon the IMLAC's character space.
An SSV with all current features can only hold about one and a half
full pages of text, where a page is the amount that can be visible at
one time. The overhead required for additional screens reduces it
still further. Therefore, with all features included, four virtual
screens could each only average about one-third full. Without many of
the current features, people were reluctant to use MSC.

The second and perhaps most devastating problem with MSC is that it is
not properly supported by ITS as is SSV. Ordinarily the operating
system will keep track of where on the page the terminal's cursor is
and will properly handle such updating as deletions even in the face
of random access performed (if done by request to the system). When
using MSC, ITS does not realize that information is being written onto
more than one screen and will therefore often move the cursor to the
wrong position.

MEND could completely control positioning for typeout and echoing on
typein but that would add the large overhead of having to run a
non-trivial routine for each character typed out on the display. Also,
because MSC is not the standard console program, requiring the user to
load it before using MEND might discourage the use of MEND. (It takes
between about 30 seconds and a couple of minutes, depending upon
system load, to load a new console program into the IMLAC.)

From the outset it was intended that MEND be used routinely by
programmers as debugging problems arose. Therefore it was decided that
the proper way for such a system to operate was to use, as far as
possible, the common environment so as to keep the overhead for
invoking MEND small. This philosophy, which had been seen to affect
the success of many earlier projects, decided between the alternatives
and in this case led to the final decision to use SSV instead of MSC.

II.2 Terminal Independence
--------------------------

The MEND terminal handling capabilities are actually quite general and
MEND does not depend exclusively on SSV. For the purpose of dividing
the screen area into several sections, horizontal lines are sometimes
drawn (see Appendix A showing sample display). With an IMLAC and SSV
these lines could be drawn quite simply using graphics mode. However,
for purposes of generality with regard to terminals, these lines are
instead formed by using underbar characters (on a line of their own).
By using no actual graphics MEND can be used with almost any display
terminal having random access. MEND outputs display commands, such as
clearing a line, as escape codes to ITS which then translates these
into the appropriate commands for the terminal in use. ITS currently
knows about several types of display terminals in use at the
Laboratory for Computer Science, and other types of terminals located
at foreign sites on the ARPA network may be handled by interface
software that simulates a known type. Naturally MEND can handle a
large range of possible line and screen lengths. (The current version
of SSV provides four possible character sizes.)

II.3 Control of Screen Sectioning
---------------------------------

There still remained the question of how to handle the
multi-sectioning of the displayed information. Originally three
sections corresponding to the three virtual screens in the aborted MSC
implementation were planned. The bottom section would hold user typein
and application program output. Three possible methods of achieving
this involved having ITS, Muddle, or MEND do various amounts of the
work with increasing overhead and decreasing speed for those three,
respectively.

The most attractive solution utilized an ITS feature allowing the
specification of an echo area at the bottom of the screen where echoed
input would always be printed (with the echoing handled by the system,
which is the normal case) . After some experimentation this method of
handling the typein and application program output was rejected
because typeout and deletion are handled by Muddle which ignores the
echo area MEND would effectively have had to control all typeout and
monitor all typein, which would have made the echo area useless.

Experimentation with the second solution, an indirect method, involved
monitoring of special Muddle memory locations where information
concerning horizontal and vertical page positions is stored. It was
soon discovered that Muddle becomes confused quickly, contains several
bugs with respect to this position information, and generally has a
poor idea of where it is actually printing.

The third solution appeared to be the most painful from an
implementation and efficiency point of view. MEND would need to
control the printing of every character on output and certain
characters on input, constantly checking page positions by querying
the system. Not only did this slow output, but also MEND was forced to
constantly move the cursor to a safe position in case Muddle managed
to sneak some output past it, which it occasionally does.

Fortuitously the problem was neatly solved when a little known feature
of ITS was discovered. It Is possible to open a channel to the
terminal in a mode that would cause all output to appear in the echo
area. By creating this echo area and reopening Muddle's normal
terminal output channel in this mode, it is possible to cause Muddle
and the application program to think that the entire screen consists
of only the echo area. All output including application program
display escape commands is automatically routed by ITS to this echo
area. MEND sends its output to a second channel opened in the normal
mode, thereby allowing it to use an area of the screen unknown to and
left untouched by the application program. The physical cursor stays
where the last used logical cursor left it, thereby eliminating most
of the unnecessary cursor movement, resulting in a more pleasing
visual effect.

As a result of this solution, the screen is divided into only two main
sections. All typein appears in the lower section, whether it is to
the application program or to MEND. Application program output also
goes to the lower section, as does unstructured output produced by
interaction with MEND. The upper section, in general, contains only
those items that occupy one line of the display each. As will be
explained later, these items include all output automatically
displayed by MEND during execution of the application program.

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.

IV Issuing Commands to MEND
===========================

IV.1 Types of Commands
----------------------

There is a need in debugging systems similar to MEND for two types of
commands for controlling operation. One type is a set of short,
immediate-action commands that the user of the debugging system may
issue at any time, such as a command to completely stop all activities
of the debugging system and to exit. The other type is the set of all
commands not belonging to the first set. This includes commands that
take arguments and those that can only be given while the application
program is suspended from execution.

IV.2 Immediate Interrupt-Level Commands
---------------------------------------

In MEND's normal mode, various actions occur automatically. Most
importantly, the application program is executing and the displayed
representation of the MSTACK is being updated correspondingly. During
this time the programmer may type ahead to the application program,
but, since there is only one physical cursor that is used by both
MEND's display and typein echoing that must therefore jump back and
forth between the two text entry positions, a large amount of typein
is awkward. Therefore, all immediate action commands that the user can
issue while MEND is in automatic mode are single characters. To
minimize the chance of conflict with typein that the executing
application program might read, MEND immediate action commands are
invoked by typing certain ASCII control characters. Furthermore typing
one of these control characters causes an interrupt to occur which is
handled by MEND and allows immediate response.

Note that this arrangement requires that there be certain reserved
characters, as listed below, that cannot be used to communicate with
the application program. Normally this presents no difficulty. An
alternative method was considered that required the reservation of
only one control character. However, the user would be required to
type an additional character as an argument signifying what function
is intended. There did not seem to be a great advantage to this scheme
and it was considered after the first scheme had been implemented. For
this and other reasons stated later in this section, the alternative
scheme was discarded.

From the user's viewpoint, the currently implemented interrupt-level
commands are as follows. (ASCII control characters are represented by
"↑" followed by the corresponding letter.)

  ---- ------------------------------------------------
  ↑L   clear screen, reprint stack and input
  ↑Q   Quit from current MEND
  ↑E   End automatic mode
  ↑B   Begin automatic mode
  ↑U   Unprint (stop displaying stack)
  ↑P   Print (start displaying stack)
  ↑O   skip Over (completely evaluate) current object
  ↑N   Next step (used when not in automatic mode)
  ---- ------------------------------------------------

The command invoked by typing ↑L is for housekeeping purposes. It
causes extraneous information (e.g., old program output) to be cleared
from the screen and all MEND-related constantly-displayed information
to be reprinted. Unread input is also reprinted.

The command invoked by typing ↑Q is used to exit from an invocation of
MEND. It has the effect of stopping all actions related to monitoring
the application program and allowing the program to continue normally.
In this way a programmer may discard MEND and continue running the
application program without the need for restarting it at the
beginning.

The two commands invoked by typing ↑E and ↑B switch MEND between
automatic mode, the only one described thus far, and non-automatic
(command) mode. Command mode will be described in the next section.

Sometimes it is desirable for the sake of saving both computer time
and the application programmer's time to turn off printing of the
MSTACK. MEND will continue to monitor program execution and store the
appropriate information but it does not display it. Nor does it pause
between steps in the normal manner. This is mainly useful when
breakpoints are present to turn on printing or switch to command mode.
At that time MEND will know how it got to the current level and will
be able to display the MSTACK as usual. Two commands invoked by typing
↑U and ↑P toggle the state of printing.

Whenever the programmer is satisfied that a particular call of a
function is working properly or for some reason he or she is not
interested in seeing the details of evaluation of some object, typing
↑O just before the object's evaluation invokes a command that causes
MEND to skip over that evaluation and continue normal monitoring and
display immediately after a value is returned. Unlike turning off the
printing, no monitoring is performed here at all so the evaluation
proceeds as fast as it would without MEND. This is actually handled by
causing Muddle to leave single-stepping mode during the evaluation of
the object.

The last command, invoked by typing ↑N, is special in that it is
ignored in automatic mode. Its actions in command mode will be
described in the next section. It is an interrupt-level command mainly
for convenience and compatibility with DEBUGR.

Bruce Daniels' DEBUGR is the prototype Muddle multiprocessing
debugging system. It provides a simple user interface to Muddle's
single-stepping functions that makes single-stepping through a Muddle
program appear similar to single-stepping through an assembly-language
program with DDT[^18][^19]. The choices of characters for invoking
many of the MEND functions were based upon the characters used to
invoke similar functions in DEBUGR. Many of DEBUGR's command
invocation characters were in turn based upon those in DDT. The object
of all of this is to build character/command associations in the
user's mind that may be carried over from one system to the next.

Several other control-character commands are handled by MEND
invisibly. That is, the user may not be aware that they are being
handled. Most of these are commands that are already being handled by
other subsystems but must be intercepted by MEND to maintain
consistency in its environment. Two of this type, invoked by typing ↑S
and ↑G, are already set up in an initial Muddle and a third, invoked
by typing ↑F , is set up by the subsystem EDIT, which is called by
MEND as described in the next section. All three of these are used to
escape to various command levels. MEND has its own command level (see
next section) and must in many cases escape to that one instead to
maintain control. Until a method was discovered for having ITS section
the screen, it was necessary to also interrupt on carriage-returns
(↑M, the new-line character) on input to insure that typein was kept
in the proper section.

IV.3 MEND's Command Level
-------------------------

Sometimes the user may wish to stop the application program at some
point to examine it in more detail or to alter it or its environment
in some way. Alternatively the user may want to issue commands to MEND
that require arguments. A command level is provided for both of these
activities.

The command level differs from the automatic mode described in the
last section in two ways. First, the application program is not
continually executing. It runs one step at a time under the direct
control of the user rather than automatically. Second, in
non-automatic mode typein is normally passed to MEND instead of the
application program, even that class of typein which does not produce
immediate action.

When the application program is stopped, the user may either request a
service from the debugging system or examine and/or modify the program
and/or its environment. Since editing functions form a large part of
the latter class of actions, it was decided that instead of requiring
the user to "import" an editor, MEND should provide an editor by
making one available at command level.

It is generally believed and empirical evidence indicates, that
creating a new editor is "the kiss of death" for a Muddle subsystem. A
number of Muddle editors have been tried over the years and the only
one that finally became generally accepted (and is now pre-loaded in
Muddle) is EDIT[^20] . Members of the Muddle community will tolerate
minor changes to EDIT, but they will not accept a new editing system.
The situation is analogous to one of the major obstacles blocking the
acceptance of ESP. Programmers were accustomed to using DDT to examine
and modify their machine-language programs. ESP was not compatible
with DDT and therefore did not provide the familiar interface desired.

In view of the situation, it seemed desirable to incorporate EDIT into
the command level, essentially unaltered. EDIT uses a special reader
that either interprets input as a command to it or passes input on to
the normal Muddle reader. At first the task of superimposing a MEND
reader on top of both of these appeared difficult. After much
discussion with the current maintainer of EDIT, a very satisfactory
solution was arrived at.

A general capability was added to EDIT allowing the specification at
runtime of a table of EDIT-like commands to be handled by
programmer-defined functions. This table is searched before EDIT's
command table and thereby provides a capability to override standard
EDIT commands. MEND basically uses an invocation of EDIT as its
command level with all MEND commands included in a table as described.
EDIT-format commands are all one or two letters and may take suffix
arguments. Currently the MEND table includes the following commands.
(FIX here means a Muddle object of type FIX, i.e., a fixed-point
number. FLOAT means a floating-point number. PPRINT[^21] is a function
that prints a Muddle object in a format which indicates the positions
of its elements and sub-elements in the tree hierarchy.)

  NAME   ARG TYPE   MEANING
  ------ ---------- --------------------------------------------------
  ?      none       type out short summary of MEND commands
  ??     none       type out complete summary of all commands
  O      any        Open object or MCSTACK level n (if arg n is FIX)
  V      none       toggle Verbosity
  N      FIX        do Next n steps (like ↑N)
  OV     none       skip OVer current object (like ↑O)
  Q      none       Quit EDIT & return to automatic mode (like ↑B)
  QM     none       Quit MEND (like ↑Q)
  SN     FIX        Set number of lines used for stack display
  SV     FIX        Set leVel below which MEND will not 1STEP
  SD     number     Set Delay time (FIX or FLOAT) between steps
  PD     FIX        Pprint Displayed object in level n
  PO     FIX        Pprint Original (actual) object in level n
  AI     any        Add an Item to the list being monitored
  DI     FIX        Delete Item number n from the list
  PI     FIX        Pprint Item number n

What the user types to the command level is inspected by EDIT. If it
looks like an EDIT command, it is looked-up in the MEND command table
or the EDIT one and handled as appropriate. Otherwise it is passed to
the Muddle reader. In general any interesting (useful) input that
Muddle should read and evaluate will not look like an EDIT command, so
there is no confusion.

As can be seen from the table, the MEND commands include general
information retrieval ones (? and ??), system tailoring ones (V, SN,
SV, and SD), and commends that allow objects to be accessed in special
MEND locations (O, PD, PO, AI, DI, and PI. The O command is special in
that it allows an object known only by its location in the MSTACK to
be opened for examination and alteration by the normal EDIT commands.
The remaining commands duplicate control-character commands except
that they are read at normal input level rather than at interrupt
level.

The most powerful feature of this command level is seen when Muddle
objects are evaluated. This level, and therefore the evaluation, uses
stack space below the application program and in the same process. All
bindings and pending evaluations of the program are above the command
level where they may be examined and modified at will. Most of what
constitutes MEND is in another process safely removed and hidden from
the user. Even the small amount of overhead constituting the command
level function is hidden from functions such as FRAMES[^22], which may
be used to view the levels of the application program's current
control stack. The effect is much the same as that of Muddle's
listening loop which is invoked at the current bottom of the stack in
case of error, to allow the programmer to run any program (evaluate
any object) to find and correct the problem.

Note that for critical examination of the program, the user may
request that it be continued for a limited number of steps (usually
one) with control then being returned to him or her at the command
level. One normally would employ such a feature when the program is
executing statements near the area of suspected trouble but it is not
entirely clear how or why the program is misbehaving.

IV.4 Breakpoints
----------------

Normally MEND operates in automatic mode where the application program
is running continuously. If one is aware of a particular area of
concern, one cannot and should not have to see that area as it is
reached and quickly type ↑E in order to stop the program. One may have
the program running with a very small delay time or have the printing
turned off.

In their simplest form, MEND breakpoints stop the program when
evaluated, putting the user in command mode if she or he was not
already in it. This is the Muddle equivalent of DDT breakpoints, which
stop a program at a certain instruction. The breakpoints can also be
conditional, where the evaluation of an arbitrary object determines
whether or not to actually break at that point.

The breakpoints as so far described are very much like the breakpoints
that can be set by EDIT. As a matter of fact, EDIT is used to set and
clear these breakpoints just as it would be in the absence of MEND.
The only real difference is that, when MEND is present, a MEND
function is called to handle the break instead of an EDIT function.

MEND breakpoints would be useful even if they only did what was just
described. However they are more powerful. A standard EDIT-style
breakpoint is a call to the break function with a number of arguments.
The first of these is the object at which the breakpoint is set, which
will be evaluated when the user returns from the breakpoint and whose
value will be returned by the break function to the application
program. The next is the conditional object and the rest are objects
to be evaluated and printed at each break. MEND's break function
handles these as EDIT's does but also looks for a recognized ATOM
(variable name), which may come after or replace the conditional. If
such an ATOM is found, it will cause a special action to occur instead
of stopping the program:

  ------- ---------------------------------------
  ON      printing will be turned on (like ↑P)
  OFF     printing will be turned off (like ↑U)
  GO      free-run the object (like ↑O)
  PRINT   just print arguments & continue
  ------- ---------------------------------------

Other arguments will still be printed and all actions are still
predicated upon the value of the conditional.

The first two special ATOMs (ON and OFF), perhaps coupled with manual
control, are used to allow the MSTACK to be viewed only during areas
of interest while maintaining maximum speed in other places. The next
one (GO) is used to avoid wasting time examining the details of a
functional call that is known to be working and is probably evaluated
repeatedly. When the break function returns, single-stepping resumes
as before the break. The last special ATOM (PRINT) is used to give
information at key places that might not otherwise be seen.

One thing that was considered extremely important was to make MEND's
breakpoints compatible with those of EDIT. The problem is that a
breakpoint inserted outside of MEND might still be present when MEND
is started and vice versa. As has been stated EDIT breakpoints work
almost exactly as usual when handled by MEND's break function. The
converse is not quite true. EDITs break function will ignore the
significance of a special ATOM end simply print it as a normal
argument. Fortunately, an ATOM evaluates to itself. If it is in the
conditional position it will always be considered "true" and no harm
will be done.

It would be easy to extend this arrangement to other special ATOMs if
other functions were considered useful. The above seem to form a basic
set in this system. At least they are useful and no one has yet
suggested another type of breakpoint that would also prove useful.

[^1]: G.A. Mann, "A Survey of Debug Systems", Honeywell Computer
    Journal 1973, volume 7, number 3, pages 182-198

[^2]: Digital Equipment Corporation, "DDT-10 Programmer's Reference
    Manual", Assembly Language Handbook, DEC-10-NRZA-D

[^3]: B. Bressler, DDT: A Debugging Aid, SYS.06.01, Programming
    Technology Division Document, Laboratory for Computer Science,
    M.I.T., November, 1971

[^4]: S.W. Galley, Debugging with ESP -- Execution Simulator and
    Presenter, SYS.09.01, Programming Technology Division Document,
    Laboratory for Computer Science, M.I.T., November, 1971

[^5]: S.W. Galley and R.P. Goldberg, "Software Debugging: The Virtual
    Machine Approach", Proceedings of the Association for Computing
    Machinery Annual Conference, November, 1974, volume 2, pages
    395-401

[^6]: M.H. Liu, DETAIL: A Graphical Debugging Tool, S.B. Thesis,
    Department of Electrical Engineering, M.I.T., February, 1972

[^7]: G.J. Farrell, A System for Muddle Programming, M.S. Thesis,
    Department of Electrical Engineering, M.I.T., August, 1973

[^8]: S.W. Galley and G. Pfister, Muddle Programming Language Primer
    and Manual, Laboratory for Computer Science, M.I.T., May, 1977

[^9]: J. Haverty, IMEDIT Editor Program for Use with the Imlac
    Terminals, SYS.08.01.02, Programming Technology Division Document,
    Laboratory for Computer Science, M.I.T., August, 1972

[^10]: B. Berkowitz, UNDO, Undergraduate Research Report, Programming
    Technology Division, Laboratory for Computer Science, M.I.T.,
    December, 1974

[^11]: N. Ryan, EDIT: The Muddle Editor, SYS.11.14, Programming
    Technology Division Document, Laboratory for Computer Science,
    M.I.T., August, 1974

[^12]: D. Eastlake, R. Greenblatt, J. Holloway, T. Knight, and S.
    Nelson, ITS 1.5 Reference Manual, Memo No. 161A, Artificial
    Intelligence Laboratory, M.I.T., July 1969

[^13]: P.D. Lebling, SSV User's Manual, SYS.52.07, Programming
    Technology Division Document, Laboratory for Computer Science,
    M.I.T., (in preparation)

[^14]: S.W. Galley, Pre-loaded Pure MDL RSUBRs, SYS.11.28, Programming
    Technology Division Document, Laboratory for Computer Science,
    M.I.T., November 1975

[^15]: B. Daniels, The MDL Assembler, SYS.11.07, Programming
    Technology Division Document, Laboratory for Computer Science,
    M.I.T., (in preparation)

[^16]: C. Reeve, The MDL Compiler, SYS.11.25, Programming Technology
    Division Document, Laboratory for Computer Science, M.I.T., (in
    preparation)