Finish Appendix B; fix footnote references.

[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 (see section II.1) 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[^7] 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 &[^14] 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[^15], 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[^16] 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[^2][^3]. 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[^11] . 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[^14] 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[^13], 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.

V Final Thoughts about MEND
===========================

V.1 Monitoring of Values
------------------------

A feature that was originally considered to be important, and is
present in ESP[^4][^5], is the constant monitoring of values. This
feature has not been too happily received in MEND, but that may be
due more to the current implementation than to an inherent lack of
utility.

Ideally one should not have to see the object being monitored or its
value if one does not want to. The debugging system should be capable
of performing certain actions upon, for example, a change in value.
This would be analogous to conditional breakpoints except that the
test would be performed after each step of execution of the
application program rather than at certain arbitrary times.

One problem with the above scheme is the difficulty of testing for a
change in value (the basic test). For example, the value of an object
being monitored may be some sort of structure. During execution the
application program may not explicitly change the value of the object
but may change an element of the structure that the object evaluates
to. Assuming MEND had saved a pointer to the structure, if it now
evaluated the object being monitored, it would again find that
structure and assume that the value had not changed. However since an
element of the structure had changed, the programmer would probably
want to be notified.

The only solution to the above dilemma is to at each step save a
complete representation to all levels of the value of the object in
some form that cannot be affected by the application program. This
can be done by, at each step, unparsing the value to be saved for
future tests into its printed (string) representation. Then the
comparison of current and previous values will simply be a string
comparison, not subject to sharing by the values. Unfortunately this
may create incredible amounts of "garbage." In fact, a circular list
(quite legal) will produce a string of infinite length!

The solution finally chosen was to print the values of the objects
being monitored at each step and to let the user visually compare
versions. The values are &-printed as usual but may be examined in
full at will.

When tested it became immediately obvious that the constant
reprinting wasted time and was distracting. A feature was added to
cause printing to occur only at controllable intervals, but that
produced other problems. Primarily the user might not see a change
that had occurred at one step until some later step when valuable
information had already been lost. One would also not have the
opportunity to take immediate action.

What needs to be done at this point is to reduce the emphasis on such
pathological cases as described above. Printing should only occur at
well defined moments (i.e., when requested or when some recognizable
condition occurs). Only gross and easily testable changes in value
should be watched for (i.e., the value is a new object, entirely).
Conditional monitoring should be installed analogous to the
conditions of breakpoints. With all of this testing, a variety of
indications should be available as with breakpoints.

V.2 Control Stack Display
-------------------------

MEND's display of the application program's control stack has proven
to be by itself a highly useful debugging aid. This display can be
and often is used without any of MEND's other features to debug a
faulty program. It should also be emphasized that a valid use of this
display is to monitor a working program in order to understand its
operation. In this case, where the user of MEND is completely
unfamiliar with the operation of the application program, MEND's
step-by-step display of program execution is even more useful than in
the normal debugging situation.

One of the unique features of MEND's "trace" of the application
program is that MEND shows both the code being executed and the
results of that execution. Since Muddle is an applicative language,
most of the results consist of values returned by evaluated objects.
By reflecting the returned values back into the original code, MEND
shows intermediate results in an intuitive manner for the user.

Other programming languages could also benefit from this sort of
display. Too often a trace routine provided for debugging in a
language shows only results of execution, such as value assignments,
without showing the corresponding program steps, or it shows program
steps but leaves it to the programmer to insert instructions to show
intermediate results. What the programmer really needs to see is a
well-integrated display of both program instructions and results,
such as MEND provides.

Muddle is an exceptional language in that the MEND display was
implemented fairly cleanly with just a package of Muddle functions
and without changes to the interpreter itself. With suitable language
enhancements, however, a similar display could be provided for LISP
or any other LISP-like language. Although major compiler
modifications would be required, a stack-oriented display might also
be suitable for a block structured language like ALGOL.

Especially in a block structured language, where instructions might
be treated in groups rather than individually, but also in
applicative languages, it would be useful to be shown variable
bindings as they occur. Muddle does not provide any information about
the occurrence of bindings, so the programmer is not informed of such
occurrences by MEND. However when major modifications are made in a
language to provide a display similar to MEND's, it would probably be
a mistake not to include a provision for notifying the programmer of
variable bindings and unbindings as they occur.

V.3 Simulation Vs. Multiprocessing
----------------------------------

Besides its control stack display, MEND's other major feature, and
its major difference from debugging systems like EEP or the first
version of MUMBLE, is its use of multiprocessing rather than
simulation to follow application program execution. (Even debugging
aids that use multiprocessing often do not work the way MEND does.
While MEND is a program written in the same language and running
concurrently in the same interpreter as the application program, some
debuggers , such a DDT, are machine language programs running near
the application program, and others are simply complied into the
language itself.) This feature is perhaps the key to MEND's success
as a debugger. The choice to avoid simulation certainly reduced the
size and complexity of MEND by two or three times and similarly
affected run time. What remains to be discussed are the tradeoffs
involved in the choice. The advantages just mentioned heavily favor
the multiprocessing solution but there are other considerations.

If MEND had been implemented using simulation, it would for the
evaluation of each object determine which elements need evaluation;
evaluate those elements by recursively calling MEND's own evaluation
simulator; determine whether some function should be applied;
determine the effects of the required functional application, if any;
and cause those effects while displaying some representation of them
for the programmer. In short, MEND would duplicate the actions of
Muddle while maintaining and updating its own information about those
actions. Therefore MEND would at all times know exactly what the
application program was doing and could never miss some important
effects of execution or be fooled by an unusual program. In the
previous section it was stated that it is desirable to show the
occurrence of variable bindings to the programmer. This feature would
be easy to implement in a debugging system that simulated execution
of the application program.

But what about a debugging system using multiprocessing? A
multiprocessing debugger, such as MEND, allow s the application
program to execute more-or-less freely in its own process while
monitoring it from another process. Since MEND id not in direct
control of the application program, it must rely for its information
on whatever data it is given by the multiprocessing mechanism built
into Muddle and on inferences based on examination of the application
program's environment, its knowledge of the general behavior of
Muddle programs, and some specific knowledge of special cases. The
occurrence of variable bindings is not decipherable from the
information that MEND can gather. Fortunately, as has been previously
shown, MEND does have the information essential to the creation of
its display and the display is a sufficient debugging tool.

Monitoring execution of the application program from another process
provides sufficient information for a useful debugging system while
simulation of the application program provides enough information for
a more comprehensive system. Therefore if speed and size of the
debugger were not important factors, then, although not a necessary
choice, simulation would be the favored choice for a debugging system
except for one other factor.

The simulator needs much more knowledge of specific details of the
behavior of program functions than does the monitor. In fact the
simulator must know exactly the effects of each function that might
be used in the application program. Uncompiled user-defined functions
are no problem. They consist merely of one or more applications of
other functions to given arguments. Complied user-defined functions
cannot be dealt with at all without actually creating a simulator for
machine language programs, a project comparable in magnitude to the
design and implementation of all of the other parts of the simulator
combined! The remaining functions are Muddle's built-in primitives.
They are well defined but frequently change (usually upward
compatibly). Furthermore new primitives are constantly being added. A
simulator for Muddle programs would therefore quickly become
outdated.

Given the problems of a simulator and the relatively few drawbacks of
a monitor, it is clear now why MEND was implemented as the latter.
The same arguments apply to debugging systems for other languages.
Whenever the appropriate multiprocessing features exist, with
sufficient information available about execution in another process,
a debugging system based upon simulation of the application program
should be rejected in favor of a monitor-type system. MEND has proven
to be an effective debugging aid and should serve as a good example
of the latter type of system.

VI Suggestions for Future Work
==============================

VI.1 Monitoring of Access
-------------------------

Because of the problems described in Section V.1 concerning the
monitoring of values, there was not enough time to work on a related
but more interesting feature for MEND. Frequently the main piece of
information that is available about a bug Ii a program is that at
some point a certain data area (variable value, list slot, etc.) is
being "clobbered" by function(s) unknown.

Rather than watching the program execution in detail to find the
culprit, it would be far more useful to set a break point on access
to the location in question. This could be done by having MEND
redefine all data access functions to watch for certain locations.
Not only would that be messy, but it goes against one of the basic
philosophies of MEND. With good reason, as described earlier, MEND
tries to alter its environment as little as possible. (For example,
what if the application program redefined one of the functions also?)

Muddle again provides the answer. The code already exists for
monitoring read or write access to any standard data location. It is
only necessary to set up the proper type of interrupt handler with a
pointer to the location to be watched. Each time the specified type
of access occur, the handier will be called with all of the
particulars.

MEND should have commands installed for creating and destroying such
handlers. For consistency and to facilitate remembering for the user,
the possible actions of this handler upon being called should be
similar to those of breakpoints and of monitoring of values.

VI.2 Other Unimplemented Features
---------------------------------

Three other proposed features were not implemented due to an acquired
belief that the value of each of these features in relation to the
goals of this work was not worth the time required to properly
implement it. However each of these features has merit and may be
desirable in some future, more comprehensive debugging system.

The first such feature involves saving all output of the application
program for the programmer to refer back to. This has the
implementation difficulty that there is no easy way to separate
application program output from much of the MEND output. All
application program output and certain MEND output goes to the lower
section of the screen utilizing the same output mechanism (i.e.,
standard Muddle output to the primary terminal output channel). No
distinction is made between the two kinds of output. A distinction
could be made, by having MEND do all of its output through yet
another terminal output channel (a second channel is currently used
for the upper screen section), but another consideration made the
effort seem not worthwhile. In practice, programs that produce a lot
of output usually send it to a file and not to the terminal. Since
only small amounts of output are usually sent to the terminal, a
short output history, such as that which is present on the screen
itself, is generally sufficient.

The second unimplemented feature would have allowed the setting of
MEND breakpoints using the editor IMED. This would have meant sending
a function out to the IMLAC where, local editing would have been used
to create, or delete such breakpoints. PRINTTYPE and READ-TABLEs
would have been used to allow for setting normal breakpoints and the
special MEND types (ON, OFF, etc.) using one or two mnemonic
characters.

The primary reason that this feature was not implemented was that
EDIT wad chosen to be the MEND editor instead of IMED. That choice
was made partly because EDIT is in many respects the more powerful of
the two, but mostly because EDIT is the editor now used almost
exclusively by Muddle programmers. In fact, EDIT is now pre-loaded in
Muddle while IMED is not. Another reason for rejection of this
feature was that it would have made MEND, or at least this part of
it, terminal dependent.

In a different environment a similar feature might be quite useful.
IMED still has the large advantage over EDIT that by constantly
displaying the entire function while the programmer moves the cursor
around in it, creating and deleting MEND "command symbols" at will,
the user is provided with a much better feel for the debugging
environment being set up than with EDIT.

The third feature would allow the user to reverse execution of the
application program or to simply back up to some previous point. This
was suggested in two varieties, an actual undoing of all effects of
the program on a step-by-step basis or simply showing previous states
of the MSTACK. The first version would have used UNDO[^10], a package
of functions to actually back up a program to some previous state.
UNDO however violates a primary design goal of MEND. It works by
redefining every Muddle function that has a side-effect, thereby
causing most of the negative effects of simulation that were
previously discussed. Unfortunately the way UNDO works is really the
only reasonable way such a package could work, short of modifying
Muddle Itself, and even UNDO is not foolproof.

The only practical way this feature could be implemented is in its
second variety. It would be possible to store (in a file, probably)
information specifying the state of the MSTACK (at each step and to
allow the programmer to view previous steps in some comfortable
manner. The time required to implement this feature, though, put it
outside the scope of this work.

VI.3 Immediate Action Commands
------------------------------

Empirical evidence suggests that one more interrupt -level immediate
action command would be highly useful. Currently the user may skip
over the complete execution of a single object by typing ↑O just
after the object is placed on the stack for evaluation. The user may
also want to rapidly complete the evaluation of some object that is
already executing. For example, one may have watched the first few
objects in a REPEAT loop being evaluated and now wants to free-run
the application program until the looping is finished. For such a
case, a command should be available to skip over the evaluation of
the current object and all others at the same level (i.e., finish
evaluation of the object on the previous level).

Further use of MEND may indicate a need for other interrupt-level
commands. (Perhaps certain interrupt-level commands should somehow be
able to take arguments?)

VI.4 Terminal Handling
----------------------

The MSC implementation of MEND was discarded because of problems
specific to the current operating environment. In a suitable
environment, multi-screening is still seen to be a useful feature for
a similar debugging system. It has even been suggested that something
of the sort could be implemented using two separate terminals. One
terminal would look to the application program just like the terminal
it would have seen in the absence of MEND. The other terminal would
be used for communications with MEND. Not only would this eliminate
output conflicts between the application program and MEND, but with
two keyboards there would be no need to have a reserved character set
for MEND interrupt -level commands. Of course, it might be difficult
for the user of such a system to coordinate activities between the
two terminals.

Another area where MEND might be improved is its knowledge of the
terminal being used. As has been previously discussed, it currently
assumes certain basic display functions and relies upon ITS to
understand the requirements of the terminal. Although ITS handles the
job well, it is not the only operating system that Muddle may run
under. This author, in fact, actively uses Muddle under TENEX, an
operating system that lacks the terminal code to support MEND. To
properly work under most operating systems, MEND would have to be
tailorable to individual terminal codes and requirements and would
have to do much more of the work than under ITS.

It has been proposed that MEND could be made to work in some fashion
with the basic ASCII printing terminal, something that nearly all
terminals and operating systems can simulate. However it is the
opinion of this author that MEND would lose much of its value under
such conditions. Watching the stack grow and shrink, and seeing
objects replaced by their values, gives the user more of a feel for
what the application program is doing than a long stream of
sequentially printed lines ever could.

Appendix B: Glossary of Terms
=============================

&: A function pre-loaded in Muddle that prints objects in an
abbreviated form to fit in a programmer-specified number of character
positions.

1STEP: A built-in Muddle function used by one program to single-step
another for debugging purposes.

ATOM: A Muddle variable.

COND: A built-in Muddle function providing a general conditional
capability. The arguments to CONO are lists. Muddle evaluates the
first element of each list in turn until an element returns a
non-false value. Then the rest of the elements in the current list
are evaluated and COND returns what the last element in the list
returns.

DDT: A program used to debug assembly language programs.

DEBUGR: A program utilizing Muddle's single-stepping functions to
show a programmer the step-by-step execution of a program. DEBUGR is
an attempt to provide a DDT-like debugger for Muddle programs.

EDIT: A pre-loaded editor for Muddle objects. EDIT works within
Muddle by restructuring the object being EDITed according to the
specifications of the programmer. EDIT allows one to define one's own
commands or to redefine those of EDIT.

ENVIRONMENT: A Muddle object which specifies a particular set of
variable bindings. An ENVIRONMENT is normally cumulatively built up
as the control stack of a program builds and ATOMs are bound. The
ENVIRONMENT actually corresponds to a particular point on the control
stack. A program may have an object evaluated in an ENVIRONMENT
specifying the current state of another running program. The effect
is as if the latter program had evaluated the object.

ESP: A debugging system for assembly-language programs.

EVAL: A build-in Muddle function that evaluated an object and returns
the value of that object

FIX: A Muddle object that is an integer.

FLOAT: A Muddle object that is a floating-point number.

FORM: A list of Muddle objects which is evaluated by applying the
first element (some function) to the rest of the elements (its
arguments). "Execution" in Muddle generally refers to the evaluation
of a FORM. The evaluation of that FORM will often require the
evaluation of other FORMs (the arguments to the function or FORMs in
the body of the function ).

FRAMES: A pre-loaded function that shows the programmer a printed
representation of the control stack of the current program.

IMED: An editor for Muddle objects that works by outputting an object
to the IMLAC where the local editing functions are used.

IMLAC: A minicomputer with a keyboard and CRT display used as an
intelligent terminal.

ITS: A general-purpose time-sharing operating system developed by the
Artificial Intelligence Laboratory at M.I.T.

LVAL: A built-in Muddle function that returns the local value of a
given ATOM. The local value is that which was last bound to the ATOM
In the current ENVIRONMENT.

Muddle: An applicative programming language used to inclement MEND.

MEND: Muddle Executor, aNalyzer, and Debugger. The subject of this
report.

MSC: Multi-Screen Console program for an IMLAC. This gives the IMLAC
used as a terminal a capability for having several virtual screens
that may be accessed and displayed independently.

MSTACK: A structure that MEND builds to contain a representation of
the control stack of the application program.

MUMBLE: An early debugging aid for Muddle programs providing a
display of the application program's control stack.

PPRINT: A pre-loaded Muddle function that "Pretty-PRINTs" an object
in a format which indicates the positions of its elements and
sub-elements in the tree hierarchy.

PRINTTYPE: A built-in Muddle function allowing the programmer to
specify exactly how any particular type of object should be printed.
May be used to output characters that will be interpreted as special
commands on input. See READ-TABLE.

PROG: A built-in Muddle function used for sequential execution of
Muddle objects (generally FORMs). This function provides for binding
of ATOMs to be used within the PROG's scope and then evaluates each
of the objects in its body, usually in order. It is possible,
however, to alter the flow of control by branching forward or
backward to another part of the PROG body. See REPEAT.

READ-TABLE: A table that may be set up in Muddle to specify how any
character should be treated on input. See PRINTTYPE.

REPEAT: Like PROG except that when the end of the body of objects is
reached, control returns to the beginning.

SSV: The normally used IMLAC console program. See MSC.

UNDO: A Muddle program that stores information about the execution of
an application program so that the execution may be backed up to some
previous point at any time.

[^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 Muddle RSUBRs, SYS.11.28,
    Programming Technology Division Document, Laboratory for
    Computer Science, M.I.T., November 1975

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

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