% A Dynamic Debugging System For Muddle % Joel Mayer Berez % January 1978 MIT Technical Memo 94 Laboratory for Computer Science\ Massachusetts Institute of Technology\ 545 Technology Square Cambridge, Massachusetts 02139 Copyright ========= This research was supported by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Office of Naval Research under Contract No. N00014-75-C-0661. This report was originally published in the United States in January 1978 without a copyright notice and without subsequent registration with the U.S. Copyright Office within 5 years. Doing at least one of those was a requirement of United States copyright law at that time. This report is therefore in the public domain in the United States for failure to comply with the required formalities. This means you're free to download, modify and redistribute this report. People outside of the United States must check the copyright laws of their country before downloading or redistributing. Abstract ======== Program debugging is a time consuming process. Conventional debugging techniques and aids typically give the user a narrow view of the program's operation, making debugging difficult. A debugging system that would present a clear overall picture of a program's behavior and would be both flexible and simple to operate would be a valuable tool. Such a system was designed and implemented in for Muddle, a high-level applicative programming language. This report discusses: the design alternatives considered during the debugging system's design and implementation phases, the reasons for the resulting design choices, and the system attributes. A major attribute of the system (MEND) is that it does not simulate the program being debugged but instead monitors it from another process. This attribute results in a robust and viable debugging system, because MEND not be modified in order to handle each new extension to Muddle and/or each new user-defined primitive. This report reproduces a thesis of the same title submitted to the Department of Electrical Engineering, Massachusetts Institute of Technology, in partial fulfillment of the requirements for the Degree of Bachelor of Science. Acknowledgements ================ I wish to thank Al Vezza, for supervising this work and guiding me along the road to winnage; Stu Galley, for the original idea; Bruce Daniels and Gerald Farrell, for laying some of the ground work I have built upon; Brian Berkowitz and Chris Reeve, for patiently repairing my ailing Muddles; Marc Blank and Tak To, for support work and for providing me with company during all-night console sessions; and all of the other ITS and DynaMod hackers who have built a system well worth using. I Introduction ============== I.1 Background -------------- A time-consuming and frustrating aspect of computer programming is the debugging of faulty programs. Current debugging techniques involve tracing through the present operation of the program and mentally comparing its action with one's concept of what should be happening. With few exceptions, an understanding of where the program fails to conform to "correct" operation must be made before the cause of the failure can be determined and corrective action taken. This is where much of the difficulty occurs. In conventional debugging, it is rare for the programmer to have available any more than the most basic aids. One usually has to extrapolate from a bare minimum of information (such as machine generated error messages) or one may be buried under a large excess of information, most irrelevant (such as a core dump). Even with the more advanced aids, the programmer typically gets but a small window in the operation of the program through which, sooner or later, she or he will locate the problem. A well-localized fault will be relatively easy to spot compared to a global problem that the programmer may only catch glimpses of through the debugging window. In a compiler language, the programmer's best hope is to insert statements to print intermediate results or to try to separate the program into easier-to-handle modules. There are a few more advanced aids available[^1], but their use is limited. One problem is that the program is, in effect, first translated into a lower-level language (generally "machine" language) and then executed interpretively in that language. The original symbols and syntax of the source program are lost, or saved only with great difficulty, making analysis and manipulation of the executing program a very painful process. If the programmer is using an interpretive language with facilities for interaction, things are considerably easier. The common technique is to stop execution at strategic points and examine the state of the environment. Since this is done interactively, with the source program still available in more or less its original form, the cause of the problem can often be found in less time than it could otherwise. one of the best example of this approach is the use of DDT (Dynamic Debugging Tool/Technique)[^2][^3]. DDT basically works with machine-language programs. However, by freely translating between numbers and symbols through the use of a table generated by the assembler, DDT makes programs look to the programmer like symbolic assembly-language programs. The user of DDT can operate in free-run mode or in n-step (statement) mode, switching between them at will. In either case one can set a breakpoint at any statement, which will cause execution to stop just before the statement is executed. Whenever stopped in DDT, the user can examine or change the contents of any location. This can be done in several data modes (e.g., unsigned octal, full ASCII, sixbit, etc.) including the use of symbols to represent addresses. Arbitrary numeric expressions can also be evaluated without affecting the program. One main advantage of DDT is that the debugging environment is very similar to the language environment the programmer used to write the program. One has to learn only the DDT commands rather than an entirely new language. Another advantage is the user's ability for viewing the results of the changes. In addition, one can quickly see the results of the changes and act accordingly. The main deficiency of DDT is that, although is names include the word "dynamic", its operation is really static. The application program can run freely, but when the programmer wants to see what is taking place, the program must be stopped. Although the real interest may be about changes on a gross scale, perhaps thousands of program statements, if one does not know exactly where the program is misbehaving, one may be required to suspend execution of it every few instructions to examine variable in order to obtain a true picture of the program's behavior. This the programmers see *not what is taking place*, but *what has taken place*, and through small windows at that. This is inefficient, and the programmer can become bogged down in detail that hinders the discovery of the true problem. The situation can be improved with the use of breakpoints that allow the program is execute freely until a breakpoint is reached, at which point the program halts. DDT is a powerful tool but still leaves much to be desired in a debugging tool. ESP[^4][^5] (Execution Simulator and Presenter) is one solution to the static problem. It really is dynamic is that large amounts of data are constantly being displayed for the programmer while the program is being executed (actually, simulated). The information is presented in graphic form to improve readability and reduce confusion. A user of ESP may watch areas of the display where data of particular interest are being presented. One also has many options including control over the speed of execution, the type of quantity of data displayed, and special (more flexible than just a breakpoint) conditions for halting execution. In this way one can structure and control the picture presented to more easily understand what the simulated program is doing. And that is one key step in the process of debugging. Like DDT, ESP has deficiencies also. These are mainly in the area of editing and DDT-like examination of a faulty program. DDT is a sophisticated language that ESP does not attempt to entirely replace. The flaw in ESP is that it is not compatible with DDT. Ideally both should be simultaneously available to the programmer, who can use features of each as the need dictates. DDT and ESP work with a low-level language whose operation can be shown fairly simply. For example, ESP often shows flow of control by just displaying the actual section of program being executed and pointing to the current statement[^6]. It also draws lines to show where branching has occurred and in some cases even indicates looping. The display philosophy can be readily extended to higher level languages that are line oriented, like BASIC, but it fails with applicative ones, like LISP or Muddle. The latter type does not use a linear control flow, but uses a complex depth-first tree structure. Furthermore, quite complicated data structures can be built (or themselves executed) that bear little relation to the appearance of the program. A good basic display for Muddle was used in MUMBLE[^7] (Gerald Farrell's monitor and debugging aid). The code being executed is shown in stack form. Each line shows a piece of code being evaluated. As each object in the bottom line is evaluated, it is replaced by a single downward-arrow symbol in this line and then printed on a new line. In this way the evaluation can be followed from the top level down to the current object being evaluated. Furthermore, after the bottom is reached, the value returned by each line replaces its symbol in the previous line. With this mechanism, the programmer can follow execution in a natural and reasonably clear representation. MUMBLE had some difficulties arising from the fact that it simulated execution rather than just watching it and letting it proceed naturally. This caused it to run slowly and to be complex yet fragile. At the time MUMBLE was written, the Muddle compiler was not yet perfected and the language itself lacked some of the multiprocessing features that would have made simulation unnecessary. Later Farrell replaced MUMBLE with a debugger utilizing new software related to single-stepping a process, which eliminated the simulation but also eliminated the feature reflecting results of an evaluation back into the original code. Also, a mode was added that allowed the programmer to attach conditions to parts of the program which would stop execution when and if a condition was false. This is as far as MUMBLE ever progressed, and it was not in use as of the time of the proposal for the current work. I.2 MEND -------- After the Muddle compiler became operational and many additional new software features became available, it appeared that it would be possible to design and implement a debugging system that would be comprehensive, easy to use, and reasonably fast. It was therefore proposed that a debugging system for Muddle called MEND (Muddle Executor , aNalyzer, and Debugger) be designed and implemented. It has the following characteristics. (A glossary of special terms, those in all capital letters, used here and throughout the rest of this memo may be found in Appendix B.) 1. MEND possesses a display similar to that of MUMBLE, including the replacement of arguments in a FORM by their values as they are evaluated. 2. Execution is monitored from another process (as opposed to being simulated as in ESP) using 1STEP and related features[^8]. 3. Execution speed is variable by the user including a static single or multi-step mode where desired. 4. MEND allows execution to run freely below a certain depth of evaluation or between certain points in the program and to run controlled elsewhere. 5. Unconditional and conditional breakpoints are available that can be attached to any object to halt execution before evaluation of that object. 6. The system is capable of keeping track of programmer specified conditions and of changing modes or giving some visible indication when the conditions are met (or not met). 7. Information, such as the local value of programmer specified ATOMs and the values of programer specified FORMs, is constantly displayed beneath the main display. 8. Each line in the main display area is &-printed (abbreviated printing, see glossary) and can be viewed in full at any time. 9. At any time, with execution stopped, the user can EVAL objects in the ENVIRONMENT of the program. This means the user can examine the state of the program or change it. I.3 Possible Additional Characteristics --------------------------------------- Certain other characteristics were seen as desirable for MEND but possibly beyond the scope of this project. If time permitted these features were to be included in the system: 1. The IMLAC multi-screen capability would be used to allow the user to rapidly switch between the debugger display and the program's own output. Other system output could also be put on additional pages. 2. The editor IMED (an editor for Muddle objects analogous to IMEDIT[^9]) would be tied into the system to allow easy editing. PRINTTYPE and READ-TABLEs would be used to allow breakpoints to be easily set and removed in IMED as single symbols. Other control codes and statements could also be inserted using this editor. 3. At the applications programmer's option and within certain limits, execution could be reversed either so that something different could be tried or for purposes of reexamining the process for something that may have been missed the first time. This feature could come in two possible forms, the UNDO package[^10] to actually reverse execution or a simulation displaying information previously stored by the system. I.4 Design and Implementation ----------------------------- MEND was designed with the intent of providing the application programmer with many options so that debugging could proceed in the most suitable manner for each situation. In the normal running state, MEND displays several kinds of information on the screen. Most important is an area showing the execution of the application program being debugged in stack form. The only other area that is always present is a line or two of status information about the current operation of MEND showing its current speed of execution (user adjustable) and the state of each modifiable mode. It was intended that the output of the application program be saved by MEND for later reference. The user of MEND could then elect to have the most recent output constantly displayed in a window on the main screen (see section on future work). If multi-screening were available, the output could be kept on another virtual screen. That screen could be displayed or made invisible at the user's option without stopping MEND. Information such as programmer specified values of ATOMs, structured objects, and, in general, the value of any Muddle expression may be constantly displayed. MEND is also capable of displaying such information on an exception basis according to some predescribed condition. Such information is &-printed but is viewable in full when desired. It is important for a debugging system like MEND to be compatible with and to take advantage of available software in related areas. One such area is editing. There were two Muddle editors in use when the proposal for this work was made, EDIT[^11] and IMED. The main difference between them is that IMED uses the local editing features of the IMLAC while EDIT does not. EDIT, however, has the advantage of being the only one that possesses breakpoint capabilities. Whichever proved to be most compatible with MEND (possibly both) would be slightly modified to allow the setting and removing of certain MEND codes including, in the case of IMED, breakpoints. Muddle itself has many features that greatly aid the debugging process. One of these is FRAMES. This function can be used to print the stack of functional evaluations and applications when execution is halted at any depth below the top level. At this point it is also possible to get the values of objects in the current ENVIRONMENT and to change them. One can even restart execution at a higher level after making such changes. Because the Muddle debugging features are quite powerful, MEND was designed to allow the user to stop execution (of the application program) and to use these aids or any others built in to Muddle with the MEND system itself transparent. Evaluation would take place in the ENVIRONMENT of the application program. MEND now includes the main features of all the debuggers that have been mentioned and enough other features that it should prove to be quit useful for the analysis and debugging of Muddle programs. It should also serve as a good example of the type of debugging system that can be built around an applicative type language. II Terminal Display =================== II.1 IMLAC Console Program -------------------------- One basic concern throughout the project was the display: how the information made available by MEND would be presented to the user. To a large extent the physical characteristics of Muddle, ITS[^12] (Incompatible Timesharing System, the operating system used on the Dynamic Modeling System computer), and the available terminals dictated what was reasonably possible. The terminal most commonly used by users of the Dynamic Modeling System is the IMLAC PDS-1. This is a minicomputer capable of having programs loaded into it from the PDP-10 host computer. One program written for it by Dave Lebling is MSC, a multiple-screen terminal program. Up to four virtual screens (or pages) can be created that will individually operate like the actual screen area of the standard terminal program (SSV[^13]). Output may be directed to any one of the screens and any screen may be visible or invisible at any instant of time, at the programmer's option. Selection of screen is controllable either by program from the host or locally by the user. It was originally Intended that MEND would use MSC for its normal display. One page would constantly show MEND's representation of the control stack of the application program. Output initiated by the program being debugged would go to a second page. A third page would be used for interaction with MEND and would show user typein along with any output from MEND that one was interested in seeing. The latter would include, by user request, full displays of both objects printed in an abbreviated form on the page containing the control stack of the application program and values being monitored or traced. The user could switch back and forth among the pages at will during the execution of the program. The application program would have a full standard screen to write onto, and ample room would be available for the information to be displayed by MEND. After a fair amount of testing, this proposal was discarded for the following reasons. First, MSC was supposed to look just like SSV for individual virtual screens. Unfortunately new features added to SSV had not also been added to MSC. A primary reason for this disparity was that the new features encroached upon the IMLAC's character space. An SSV with all current features can only hold about one and a half full pages of text, where a page is the amount that can be visible at one time. The overhead required for additional screens reduces it still further. Therefore, with all features included, four virtual screens could each only average about one-third full. Without many of the current features, people were reluctant to use MSC. The second and perhaps most devastating problem with MSC is that it is not properly supported by ITS as is SSV. Ordinarily the operating system will keep track of where on the page the terminal's cursor is and will properly handle such updating as deletions even in the face of random access performed (if done by request to the system). When using MSC, ITS does not realize that information is being written onto more than one screen and will therefore often move the cursor to the wrong position. MEND could completely control positioning for typeout and echoing on typein but that would add the large overhead of having to run a non-trivial routine for each character typed out on the display. Also, because MSC is not the standard console program, requiring the user to load it before using MEND might discourage the use of MEND. (It takes between about 30 seconds and a couple of minutes, depending upon system load, to load a new console program into the IMLAC.) From the outset it was intended that MEND be used routinely by programmers as debugging problems arose. Therefore it was decided that the proper way for such a system to operate was to use, as far as possible, the common environment so as to keep the overhead for invoking MEND small. This philosophy, which had been seen to affect the success of many earlier projects, decided between the alternatives and in this case led to the final decision to use SSV instead of MSC. II.2 Terminal Independence -------------------------- The MEND terminal handling capabilities are actually quite general and MEND does not depend exclusively on SSV. For the purpose of dividing the screen area into several sections, horizontal lines are sometimes drawn (see Appendix A showing sample display). With an IMLAC and SSV these lines could be drawn quite simply using graphics mode. However, for purposes of generality with regard to terminals, these lines are instead formed by using underbar characters (on a line of their own). By using no actual graphics MEND can be used with almost any display terminal having random access. MEND outputs display commands, such as clearing a line, as escape codes to ITS which then translates these into the appropriate commands for the terminal in use. ITS currently knows about several types of display terminals in use at the Laboratory for Computer Science, and other types of terminals located at foreign sites on the ARPA network may be handled by interface software that simulates a known type. Naturally MEND can handle a large range of possible line and screen lengths. (The current version of SSV provides four possible character sizes.) II.3 Control of Screen Sectioning --------------------------------- There still remained the question of how to handle the multi-sectioning of the displayed information. Originally three sections corresponding to the three virtual screens in the aborted MSC implementation were planned. The bottom section would hold user typein and application program output. Three possible methods of achieving this involved having ITS, Muddle, or MEND do various amounts of the work with increasing overhead and decreasing speed for those three, respectively. The most attractive solution utilized an ITS feature allowing the specification of an echo area at the bottom of the screen where echoed input would always be printed (with the echoing handled by the system, which is the normal case) . After some experimentation this method of handling the typein and application program output was rejected because typeout and deletion are handled by Muddle which ignores the echo area MEND would effectively have had to control all typeout and monitor all typein, which would have made the echo area useless. Experimentation with the second solution, an indirect method, involved monitoring of special Muddle memory locations where information concerning horizontal and vertical page positions is stored. It was soon discovered that Muddle becomes confused quickly, contains several bugs with respect to this position information, and generally has a poor idea of where it is actually printing. The third solution appeared to be the most painful from an implementation and efficiency point of view. MEND would need to control the printing of every character on output and certain characters on input, constantly checking page positions by querying the system. Not only did this slow output, but also MEND was forced to constantly move the cursor to a safe position in case Muddle managed to sneak some output past it, which it occasionally does. Fortuitously the problem was neatly solved when a little known feature of ITS was discovered. It Is possible to open a channel to the terminal in a mode that would cause all output to appear in the echo area. By creating this echo area and reopening Muddle's normal terminal output channel in this mode, it is possible to cause Muddle and the application program to think that the entire screen consists of only the echo area. All output including application program display escape commands is automatically routed by ITS to this echo area. MEND sends its output to a second channel opened in the normal mode, thereby allowing it to use an area of the screen unknown to and left untouched by the application program. The physical cursor stays where the last used logical cursor left it, thereby eliminating most of the unnecessary cursor movement, resulting in a more pleasing visual effect. As a result of this solution, the screen is divided into only two main sections. All typein appears in the lower section, whether it is to the application program or to MEND. Application program output also goes to the lower section, as does unstructured output produced by interaction with MEND. The upper section, in general, contains only those items that occupy one line of the display each. As will be explained later, these items include all output automatically displayed by MEND during execution of the application program. III MSTACK: MEND's Representation of the Control Stack ====================================================== III.1 Program Execution In Muddle --------------------------------- MEND's primary role is to allow the applications programmer to visually monitor the execution of a program. In a language like Muddle, this is most easily accomplished by showing the programmer a picture of the control stack. A Muddle program consists of the evaluation of a single object. The object is usually structured in some manner and itself contains other objects. The most common object is the FORM. This is a list of objects in which the first is (or evaluates to) some function and the rest are arguments to that function. A FORM is evaluated by applying the function to its arguments, usually after the arguments are themselves evaluated. This evaluation actually is initiated by the Muddle interpreter by applying the function EVAL to the original object. EVAL takes an object as its argument and returns the value to which it evaluates. Figure 1 shows a (simplified) static representation of the evaluation of a Muddle object. Starting with the FORM (list of objects in angle-brackets) to be evaluated, the flow of control/evaluation may be described as a depth-first search through the tree pictured. The arrows represent values being returned to previous levels. At the end of this "search" the FORM returns the value shown at the top. Figure 1: 31 ↑ <+ .A .B .C 5> ↑ ↑ ↑ ↑ ↑ + .A .B .C 5 ↑ ↑ ↑ 6 8 12 Typically the control stack will start with one object on it, the FORM to be evaluated. This evaluation will first require that the objects in the FORM (possibly FORMs themselves) be added to the stack and evaluated. EVAL recursively calls itself for this purpose. The stack builds (downward, by convention) until some object is placed on it which ls known by EVAL to need no further evaluation. This object is returned as its own value to the previous level and values continue to be returned upward until a level is reached where another object must be evaluated. In this manner, the stack grows and shrinks until the topmost (initial) object returns a value. III.2 Monitoring Program Execution ---------------------------------- The manner in which the stack builds, the objects are evaluated, and the values are returned illustrate most of what the program is doing. Other factors, including side effects and complied code, will be discussed at the end of this chapter. MEND's main display therefore shows a representation of the stack being continuously updated as execution/evaluation proceeds. There are essentially two ways that MEND could follow the flow of control of the application program. The most direct way, as attempted by MUMBLE[^14] and discussed in the last chapter, would be for MEND to execute the application program by simulating the operation of Muddle. This type of simulation has been shown to require a complex end all too often fragile structure. The debugging program would need to be constantly updated to match changes and additions to the Muddle language , but more importantly it would fail to properly handle programmer-defined primitives, several varieties of which are provided for by Muddle. A far more satisfactory method is to allow Muddle to execute the application program in more or less its normal fashion but to stand beck somewhere and watch. Fortunately Muddle contains a mechanism ideal for this, called multiprocessing. Basically another control stack , or process, may be created (independent of the first) that may be used to execute a different function with its own set of variable bindings. One such process, in this case MEND, may place another, the application program, into a single step mode where the latter will be stopped before each call to EVAL and again as each call returns. The MEND process will at these points be restarted and given information about what the application process is doing. MEND stores this information in a multi-level structure it creates called an MSTACK. Each level of an MSTACK corresponds to a level of the control stack being monitored. Each level contains the original object (actually, a pointer to it) being evaluated at that level and a new object, called the "displayed object", that will or does contain the results of evaluating each of the arguments or elements of the original. The displayed object is initially the same as the original (in a real sense, it is the original) but is systematically rebuilt as each element is evaluated and replaced by what it returns. Thus MEND can keep track of the relationship between the changing display and the unchanging program. (Figure 2 shows the various stages that the displayed object corresponding to the FORM being evaluated in Figure 1 goes through. Each stage would in fact be painted over the previous one so that all of these stages represent only one line of the screen. The down-arrow shown in some of the stages is a place-holder that represents an object that is actually expanded on the next line of the screen.) A pointer is also kept showing which element is currently above this on the stack to be evaluated unless, of course, this is the initial element of the stack. Figure 2: <+ .A .B .C 5> <+ ↓ .B .C 5> <+ 6 .B .C 5> <+ 6 ↓ .C 5> <+ 6 8 .C 5> <+ 6 8 ↓ 5> <+ 6 8 12 5> 31 III.3 A Displayed Representation of Program Execution ----------------------------------------------------- The printed representation of the stack occupies the top section of the screen and is the most prominent and important characteristic of MEND. Most often, in fact, it is only necessary to watch this display as the application program is executed to ascertain where a bug is located or to observe exactly how the program operates. Therefore considerable time has been spent making the operation of the MSTACK and associated display as natural and informative as possible. Using the collected information described in the previous section, a representation of the stack is displayed as a number of lines, each corresponding to one level. Each line shows a level number and the displayed object printed in "&-printing", named for the printing function &[^15] created by Greg Pfister. Although strictly speaking the stack builds upward (towards higher memory locations), it seams more natural to display and speak of the stack as building from the top downward, in the direction that printing normally occurs. As each element of the bottom level (the bottom line on this section of the screen) is placed on the stack for evaluation, a new line is added beneath the previous bottom-level line showing that element, and the element is replaced in the previous line by a pointer ("↓") marking its location. When the element finally returns a value, the returned value will replace the pointer in the displayed object. To avoid visual distraction, a minimum of updating is done on the screen. In most cases random access is used to replace only those lines that have changed. In general the complete stack will not fit in the display area allocated for it (whose size is user adjustable) so a scrolling procedure has been devised. The complete display area is rewritten whenever an attempt is made to write past the bottom or erase upward past a certain level while some lines are invisible because they have been scrolled off. The scrolling parameters have been selected to optimize the number of lines visible on the average vs. the frequency of scrolling. Level numbers allow the user to see how much is hidden "above the screen" and how deep the evaluation is nested. III.4 MEND Program Steps Vs. Muddle Steps ----------------------------------------- To make it easier for the programmer to follow what the application program is doing, the speed of execution of the program must be controllable. MEND does this by inserting a constant, user adjustable delay between program "steps." One MEND step is not precisely the same as one Muddle step. Remember that a Muddle step is one call to or return from EVAL. Each MSTACK level, and therefore each displayed line, will have two Muddle steps associated with it. At the first step, MEND will create the level and add one line to the screen. At the second step, MEND will erase that line and put the returned value back into the previous line. For clarity MEND adds a third step between these two which actually occurs at the second Muddle stop. Before substituting into the previous line, the current one is first replaced by the returned value, the normal delay occurs, and then the "second" step occurs as described. Some types of Muddle objects are self-evaluating; EVAL will simply return the object it was given. Although nothing interesting has happened, two steps have occurred. In this case MEND will avoid clutter by pretending that no steps have occurred. (MEND only does this with built-in types that MEND recognizes, and the programmer should recognize, as being self-evaluating. Programmer-defined types that are self-evaluating will generate the usual number of MEND steps.) Another case of disparity between Muddle and MEND stops is more complex. First some further explanations about Muddle objects are needed Generally the interesting objects, the ones that generate MEND steps, are linear (usually list) structures containing a number of other Muddle objects, as are the FORMs described earlier. Normally during evaluation of such an object the elements will be evaluated one at a time from first to last. However this sequence is not always followed by Muddle. MEND cannot directly determine which element is about to be evaluated at each call to EVAL. It is only given the object to be evaluated itself and not its position in the parent structure. It is normally sufficient to do a comparison of this object with the elements of the parent, starting with the first element believed to not yet have been evaluated. Naturally, if the elements are evaluated out of order, this procedure may fail to find the desired match, because a Muddle object may contain the same element in two or more positions. Thus it is possible to match the about-to-be-evaluated object to the wrong occurrence of it. Further complications arise because some functions can sometimes back up and re-evaluate their arguments. A strong attempt was made to make MEND dependent only upon the general characteristics of Muddle functions and not upon specific exceptions and idiosyncrasies. It was felt to be desirable to make MEND independent of both future changes to the language and programmer-defined "primitives" that would not be known to MEND. Besides, without actually simulating Muddle it is not possible to always get the information MEND needs. It was felt that the "general rule" approach would take care of a sufficiently large number of cases without falling into the simulator problem. It was determined after some experimentation, however, that MEND could not be made to work properly without some specific knowledge about several important cases in Muddle. Two functions, PROG and REPEAT, allow for branching the flow of control. They are normally first-to-last functions as described above but at times control may jump backwards to re-evaluate some elements. MEND was implemented so that if it cannot locate an element in its normal search path, it will start looking again from the beginning of the structure. If it is then found, the displayed object will be reinitialized to be as if evaluation had not yet proceeded past that point. Evaluation will then continue normally. Another phenomenon of Muddle that we must discuss is what this author labels the "clause" behavior. A clause is a list of objects given to a function as a single argument. The list is not itself evaluated, but some or all of its elements are evaluated. The most common function illustrating this behavior is COND, a general purpose conditional function. COND's arguments are all lists of objects. It sequences through these lists, evaluating the first object in each, until an evaluated object returns something considered "true." Then the rest of the objects in that list are evaluated and COND returns what the last object in the list returns. MEND's normal search path only looks at top-level elements and would therefore never find the ones actually being evaluated. This phenomenon seemed to be more widespread than the PROG/REPEAT one and could not be easily attributed to certain functions. The solution chosen here was to in all cases do a nested search in elements that looked as if they might be clauses. (The search actually goes one extra level deep to allow for certain special cases.) When a match is found in a clause, MEND will for clarity generate extra steps to make it appear to the user as if first the clause and then its appropriate element was put on the stack for evaluation. The clause will stay on the stack until some element that is not above it in the evaluation tree is evaluated. At that time the clause will be removed in an orderly manner, and the new element or clause plus element will be put onto the stack. To do this smoothly, up to six MEND steps may have to be generated for the one Muddle step. (See the example in Appendix A.) III.5 What the User Does Not See -------------------------------- MEND, in its display of the MSTACK, attempts to show the user everything of importance that is happening as the program is executed. However certain features of Muddle cannot be captured in this sort of representation. One such feature is the existence of compiled code. Although Muddle was originally intended to be a high-level interpretive language, an assembler was written[^16], producing machine code that executes in the Muddle environment, to allow programmers to create "primitives" that perform functions not otherwise available in Muddle. Once the assembler was written, it was natural that a compiler[^17] followed. It translates normal Muddle code into Muddle assembly code which is then assembled. Typically Muddle programs are tested interpretively and, when fully debugged, complied in order to obtain a major increase in speed of execution. A call to a compiled (or assembled) function usually looks to the programmer and to MEND like a call to a Muddle primitive. The operation of the function is not seen except when it calls uncompiled functions. This does not present a major problem to MEND since generally only uncompiled functions are being debugged, and the compiled ones encountered are hopefully performing known functions properly. One feature of Muddle that MEND is unable to cope with is the interrupt system. The programmer may enable a large class of interrupts and assign handling functions wherever desired. Examples Include interrupts for characters being typed to a certain input channel and notification that the system is about to be brought down. (MEND uses interrupts to catch single character commands and to catch errors.) Recall that MEND monitors application program execution by placing its process into a single-stepping mode. When Muddle passes control to an interrupt handier, it temporarily causes the process to leave single-stepping mode. This is necessary partially because such a handler may be specified to run in a process other than the current one at the time of the interrupt. It unfortunately makes the handler invisible to MEND. it is therefore not currently possible to use MEND to debug interrupt handlers. There is a whole series of side-effects, such as printing by the application program, that are not directly seen in the MSTACK representation but are made visible by various other features of MEND. These will be discussed where appropriate in later sections. [^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]: G.J. Farrell, A System for Muddle Programming, M.S. Thesis, Department of Electrical Engineering, M.I.T., August, 1973 [^15]: S.W. Galley, Pre-loaded Pure MDL RSUBRs, SYS.11.28, Programming Technology Division Document, Laboratory for Computer Science, M.I.T., November 1975 [^16]: B. Daniels, The MDL Assembler, SYS.11.07, Programming Technology Division Document, Laboratory for Computer Science, M.I.T., (in preparation) [^17]: C. Reeve, The MDL Compiler, SYS.11.25, Programming Technology Division Document, Laboratory for Computer Science, M.I.T., (in preparation)