Automatic Program Debugging
Proceedings of the Sixth International Joint Conference on Artificial Intelligence. .
© 1979 International Joint Conferences on Artificial Intelligence
Abstract
This paper presents a system <PHENARETE) uhich understands and improves lncomplet~ly defLned LISP programs, such as those.urLtten by students begtnntng to program in LISP. Thts system takes, as Lnput, the program uLthout any additional information. In order to understand the pro.gram, the system meta-evaluates l t, us log a library of pragmaticdescribing the construction and correction of general program constructs and a set of 6RBCLall~ts, describi~g the syntax and semantics of the standard LISP functions. The system can use Lts under~tandtng ~f the program . to detect errors in it, to debug them and, eventually, to JUStLfy Lts proposed modLfLcatLons. This paper gives a brief survey of the uorklng of the system, emphasizing some commented examples.
- 0 REFERENCES £1l CHAILLOUX J. ~10.3 manuel de r~!~rence." 06pt. lnformatique, Unlverslt~ Paris 8, RT-17-78 1978
- GOOSSENS D. "A System For Visual-Like Understanding of LISP Programs." Proc. AISB/GI Conference, Hamburg, RFA july 17-19, 1978 '
- GREEN C. & BARSTOW D. "On Program Synthesis Knowledge." Artif. Intell. 10:3 <1978) 241-279
- GREUSSAY P. "Contribution ~ La D6finition Interpretative et ~ l'Implementation des Lambda-langages." Th~se, Universit~ Paris 7, 1977
- IGARASHI S., LONDON R.L. & LUCKHAM D.C . "Automatic Program Logical Basis and its Acta Informatica, 145-182. Verification 1 : Implementation. " val. 4, <1975 )
- RICH C. & SHROBE H.E. "Initial Report on a LISP Programmer's Apprentice." IEEE Transactions on Software Engineeri ng SE-4:6 <1978> 456-467
- RUTH G.R. "Analysis of Algori thm Implementations." MAC-TR-130, M.I.T., Cambridge, 1974
- WERTZ H. "Un systeme de comprehension , d'amelioration et de correction de programmes incorrects." Th~se de 3~me cycle, Universit6 Paris 6, 1978
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
AUTOMATIC PROGRAM DEBUGGING
Harald WERTZ
C.N.R.S. LA 248 L.I.T.P. 2 place Jussieu 75005 Paris
& Departement d'lnformatique Universite Paris VIII -Vincennes 75571 PARIS Cedex 12
Abstract : This paper presents a system <PHENARETE) uhich understands and improves lncomplet~ly defLned LISP programs, such as those.urLtten by students begtnntng to program in LISP. Thts system takes, as Lnput, the program uLthout any additional information. In order to understand the pro.gram, the system meta-evaluates l t, us log a library of pragmatic ~ describing the construction and correction of general program constructs and a set of 6RBCLall~ts, describi~g the syntax and semantics of the standard LISP functions. The system can use Lts under~tandtng ~f the program . to detect errors in it, to debug them and, eventually, to JUStLfy Lts proposed modLfLcatLons. This paper gives a brief survey of the uorklng of the system, emphasizing some commented examples.
1.0 Introduction
Much effort is spent on the development of tools to hel~ ~rogrammers in constructing, debugging and verLfyLng programs. From simple editors and trace-packages, the trend is touards more and more sophisticated automatic programmers [3], automatic debuggers [7] automatic assistants [61, automatic verifiers [51 or even the construction of neu semantically more firmly based
programming languages <PASCAL, ALPHARD).
Most of these tools exhibit some ueaknesses such as : they impose too .many constraints on the intuitions of the programmer or they uork only on a very limited subset of possible programs (cf [7]) or they uork only on correct programs (cf [51).
Our aim in the design of our program understanding system uas three-fold
- -1- ue uanted to have a system uhich makes explicit the knouledge involved in constructing and debugging programs;
- -2- ue uanted our system not to verify the correctness of programs but their consistency and
- -3- ue uanted the system to provide ~ for improving and correcting programs.
To this endue have built a ~rogram understanding system capable of automatLcally correcting and improving programs. This system, PHENARETE, assists beginning programmers during the uritlng and debugging of their programs.
PHENARETE anlyses the text of the program and uhen it detects inconsistencies or informalities, lt constructs and proposes possible corrections or improvements. These propositions constitute for the beginning programmer a crucial component of his apprenticeship : basing on examples the process of improving and programs, and basing on inventing future programs. correctLng imperfect ~ the process of
2.0 Oyerview of the system
The system takes as input the draft version of a LISP program and delivers as result of its treatment one or more versions of the same program, corrected and improved. PHENARETE proceeds in several steps : first it effects a preliminary analysis of the text of the program to detect and correct surface errors. Surface errors are errors detectable by local anlysis : simple syntax errors such as misspellings or parenthesis errors and errors concerning the wrong number of arguments in function calls. During this first analysis PHENARETE collects information for the following steps. Every time it meets the name of a function it automatically activates a specialist, associated with this function, by the process of data driven function lnvocat ion. These specialists represent l ts knowledge about the use and the effects of the
associated functions.
The result of the first analysis a syntactically correct program is then meta-evaluated to verify the programs well-formedness. We say that a program is well-formed if it doesn't contain evident infinite loops, doesn't have statements never executed and if it doesn't contradict the set of rules incorporated in PHENARETE. Every proposition our system delivers is a well-formed
program.
When PHENARETE detects some informalities or inconsistencies, it annotates the corresponding part of the program and sends the code and the annotation to the repair-man, a module designed to eliminate errors. The system stops the analysis process when it doesn't find any more possible improvements.
3.0 Organisation of PHENARETE
The system is based on four main concepts :
- -1- During the analysis of a program, PHENARETE constructs an internal representation of the program in the form of cognitive ~. These may be considered as the nodes of a netuork-like representation of the program. Each cognitive atom is composed of a set of facets uhich represent its different aspects, about uhich questions could be asked. The facets are filled in during the analysis process.
We distinguish betueen three classes of cognitive atoms, those concerning variables, those concerning labels and those concerning functions.
- -2- A set of specialists, i.e. a set of procedural specifications of the syntaK and the operational semantics of the standard LISP functions. We distinguish betueen tuo different types of specialists :
- those describing the syntaK and - those describing the semantics
of the associated functions.
eKample : specialist CAR for the syntaK

paraphrasing CAR eKpects that its argument is - an atom and the type of the value of the argument is a list -a S-eKpression and the type of the value of that S-eKpression is a list (e.g. a function call) else CAR has to modify the argument until one of these tuo conditions is true
and the specialist CAR for the semantics

or in paraphrasing : CAR-N has an argument named X, uhich must be evaluated. One must vee i fy, if the type of value of the argument ls a list, all is ok, else, if the type of value of the argument isn't knoun, one has to create a hypothetical value of type LIST for X, else, one has to call the repair-man to change the teKt of the program in such a uay that the value of X becomes a list. The value of CAR is if there eKists already a CAR of X, this CAR, else one has to create a symbolic value for X, the CAR of uhich uill be the desired value.
Note that the internal description constructed during the analysis of each user function is used to construct tuo neu such specialists for each user function. The specialists are the agents of the meta-evaluation and they represent the systems knouledge about the programming language used.
- -3- An algorithm of meta evaluation [2] uhich helps the system to understand each of the possible paths of the program. This algorithm includes modules to determine the symbolic values on which the evaluation is carried on.
- -4- A set of pragmatic~ describing general program constructs and stereotyped methods to repair inconsistencies. These rules formalize and eKpress eKplicitly the knouledge activated by every programmer uhen he is reading a program. We do not use rules concerning the task domain of the programs : our intention uas . to build a system uhich does not ask for any additional information. The system should work in any possible task domain, numeric as uell as symbolic.
eKamples of pragmatic rules :
- rule of the dependence of a loop of the predicate ..
if no variable of the eKit-test of a loop is modified lnside the loop-body, then the loop is independent of the eKit-test and its eKecution is non-terminating or the loop uill never be eKecuted.
A slight refinement of this rule is the follouing rule :
(2) rule of the structural uell-formedness of loops ..
in a loop at least one of the variables used in the e~it-test has to change its value inside the body of the loop, in such a way that its structure is simplified and converges towards the satisfaction of the exit-test.
In order to use this rule, ue have implemented a small theorem prover uhich can prove the convergence by induction. For the proof of this rule, the theorem-prbver takes the symbolic value of the variables at the entrance of the loop, and the modified symbolic values of the same variables after ~ meta-evaluation of the loop-body and tries to prove the convergence touards the stop test. Let us give one last example of a pragmatic rule
(3) rule of the structure of recursive loops ..
in a recursive function, the recursive calls have to be inside of selection-clauses, and at least one of the clauses must not contain a recursive call.
Actually Ye have about a hundred rules incorporated in the system, dealing especially Yith iteration and recursion. For almost every rule ther exists a dual one indicating how to modify the program in such a Yay that the first one is satisfied.
4.0 A Commented Example
To use PHENARETE, the user has to give to the system only the text of the draft version of the program he yants to write, Yithout any additional information like input/output assertions, commentary, plans etc. The system Yill try to understand Yhat the user Yanted to do, and, if necessary, modify the text of the programm. To give some feeling of the Yorking of the system, let us examine some examples in detail : Our first example is a (very) erroneous version of the Yell known REVERSE function. Here is the actual input to the system :
? <P '(DE REV L1 L2 COND ULL L22 A1 T RYE A1 ONS CRA A1 A2))
After having corrected the spelling errors, PHENARETE proceeds to a first analysis where she uses only her syntactic knowledge. The result of this first analysis is a syntactically correct LISP program (i.e. a program accepted by any smart LISP interpreter or campi ler) :
SURFACE IMPROVEMENTS
<DE REV <Ll L2 > (COND <<NULL L2> L1 >
(T <REV L1 <CONS <CAR L1> L2>>>>>
These first lmprovements have eliminated all the syntactic errors. However, at least tYo semantic errors remain :
- -1- in the recursive call of REV, the first argument L1 is not modified. This creates an infinit recursion (rule 1).
- 2- even yith a modification of L1 in the recursive call, the recursion Yon't stop since the stop-test has as argument L2, a list Yhich grows longer and longer on succesive recursive calls (rule 2>.
PHENARETE can not disambiguate this function- it does not knoY anything of the intentions of the programmer - so it gives tyo different propositions :
PROPOSITION 1 :
<DE REV <Ll L2> <COND
<<NULL L2> L1 >
(<NULL L1) L2>
<T <REV <CDR L1 > <CONS <CAR L1 > L2)) » >
AT LEAST YOUR FUNCTION SEEMS OK.
In this first proposition, PHENARETE supposed the stop-test given to be correct, but that the user omitted a second stop-test for the case Yhere the second argument is not NULL at the initial call of REV.
PROPOS I TI ON 2 :
<DE REV <Ll L2> (COND
<<NULL L1 > L2> <T <REV <CDR L1> <CONS <CAR L1> L2>>>>>
AT LEAST YOUR FUNCTION SEEMS OK.
In this second proposition, PHENARETE supposed that the user inadvertently inverted the arguments of the stop-test, so she inverts the tYo arguments L1 and L2.
PHENARETE is assured that the two corrected versions of the initial draft-program (yhich are not identical) Yill stop and deliver a resu l t when executed.
Presently Ye are working on some extensions to PHENARETE as to find automatically the intentions and the goals of given pieces of code . We yould also like to adjoin to PHENARETE a module permitting an explanation to the user of 'the reasoning of the system. This would be a great help to the user.
The system is running on PDP-10, uses about 25k Yord memory, is implemented in~ [1,4], and is used by about 1000 students in our university. A more detailed description may be found in [8].
5.0 REFERENCES
- £1l CHAILLOUX J. ~10.3 manuel de r~!~rence." 06pt. lnformatique, Unlverslt~ Paris 8, RT-17-78 1978
- GOOSSENS D. "A System For Visual-Like Understanding of LISP Programs." Proc. AISB/GI Conference, Hamburg, RFA july 17-19, 1978 '
- GREEN C. & BARSTOW D. "On Program Synthesis Knowledge." Artif. Intell. 10:3 <1978) 241-279
- GREUSSAY P. "Contribution ~ La D6finition Interpretative et ~ l'Implementation des Lambda-langages." Th~se, Universit~ Paris 7, 1977
- IGARASHI S., LONDON R.L. & LUCKHAM D.C. "Automatic Program Logical Basis and its Acta Informatica, 145-182. Verification 1 : Implementation. " val. 4, <1975)
- £6] RICH C. & SHROBE H.E. "Initial Report on a LISP Programmer's Apprentice." IEEE Transactions on Software Engineering SE-4:6 <1978> 456-467
- RUTH G.R. "Analysis of Algori thm Implementations." MAC-TR-130, M.I.T., Cambridge, 1974
- WERTZ H. "Un systeme de comprehension , d'amelioration et de correction de programmes incorrects." Th~se de 3~me cycle, Universit6 Paris 6, 1978
@inproceedings{ijcai1979p209,
title = {Automatic Program Debugging},
author = {Wertz, Harald},
booktitle = {Proceedings of the Sixth International Joint Conference on
Artificial Intelligence, {IJCAI-79}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Bruce G. Buchanan},
year = {1979},
month = {8},
url = {https://ijcai.org/proceedings/1979/209},
}
TY - CPAPER TI - Automatic Program Debugging AU - Wertz, Harald T2 - Proceedings of the Sixth International Joint Conference on Artificial Intelligence, IJCAI-79 PB - International Joint Conferences on Artificial Intelligence PY - 1979 UR - https://ijcai.org/proceedings/1979/209 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: