Finishing section 1, adding initial footnotes, restyling markdown text

[mudman.git] / md / debugging.md

---
title: 'A Dynamic Debugging System For Muddle'
author: Joel Mayer Berez
date: January 1978
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 and 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 need not be modified in order to handle each
  new extension to Muddle and/or each new user-defined primitive.
---

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.

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.

Introduction
============

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.

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.

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.

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.

[^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