Recognition in a Program Understanding System

1. INTRODUCTION

The goals of our research project are twofold: one, to develop a working definition of Program Understanding which is capable of incorporating all of the diverse pieces of information expert human programmers employ in understanding a orogram, including efficiency tradeoffs, proeram comments, knowledge of the task domain, language dependent and independent programming knowledge; two, to define a set of problem solving methods which use such knowledge in constructing an understanding of a computer program. This paper addresses the second of these goals, particularly the types of recognition methods most suited to the program understanding task. The remainder of this section provides the preliminary background for our discussion of recognition in section 2. To lest our ideas, we arc currently developine an AI system which accepts actual programs from a specific domain, and produces explanations of the programs in the framework we have defined.

I .I . Description Trees

We view a program as the final product of a hierarchical desien process similar to Wirth's notion of step-wise-refinement. We define a Description Tree (OT) as a hierarchical plan structure generated from this process. Our DT hils much in common with Brown's[3] hierarchical deo;criplions, de Kleer's[4] plan fragment description's, and Rich and Shrobe's[8] complete program descriptions.

For any given task specification, there can exist a possibly larr.e number of different DTs, one for each unique final program (Barstow[l] defines a ·refinement tree· which is i'lni'llogous to a superlrec of all DTs generated from the same specification).

1.2. Pro,rem Buildin1 Blocks

The basic conceptual programming unit of our system Is called a program building block or pbb, and is in most ways equivalent to what Rich and Shrobe[8] refer to as a Segment in their Programmer's Apprentice. Each pbb has a set of data inputs, pre-conditions which must hold on entry, a set of resulting outputs, and post-conditions which are true on exit. Other types of information which help guide recognition may also be attached to a pbb, eg. possible mnemonic names. Figure 1 shows a pbb that copies a file to a lin~~d-lisl.

(pbb file -to-list-copy (INPUT: file I) (PRE -COND: type( file I,SEQUENTIAL)) (OUTPUT: linked-list I) (POST -COND: type(linked-lisii,LINKED-LIST) map Ito I (linked- list l,file 1)) (MNEMONICS: READSFILE COPYSFILE)]

Figure I: Example pbb

1.3. Implementation Plans

Any non-primitive pbb can be decomposed into sub-parts (also pbbs) linked by dataflow and teleology. We call this decomposition an lmplementotion Plan or /P (for more details, see Rich and Shrobe's(8] concept of ·deep plan"). In terms of the DT, for any non-terminal node B, all sons of B constitute the sub-parts of an IP of B.

2. CONSTRUCTING A DESCRIPTION TREE

Our initial goal is to build a system that constructs a DT given simply the task specification and the program code; however, we are including design features which will enable it to use knowledge from preprocessed mnemonic names and comments. While the final system is not intended as an explicit model of human behavior, a guiding principle In the design is that it should use, wherever feasible, mechanisms derived from the analysis of human protocols.

2.1. Justification of a Top-down Approach

The essential control structure of the system is to start with an ini tial hypothesized Implementation Pl.tln, hypothesizing and confirming further refinements and decompositions, halting when the lowest level pbbs (ie. leaves of the DT) match the actual code. There are several reasons why a lop· down method is preferred. First, a top-down approach provides a useful high level understanding even when forced to halt before reaching the lower levels of the Description Tree. For example, being able to identify sections of a program which read a file into an array, sort the array, and merge the array with another file is useful even if exact details have not been (or cannot be) worked out for the read, sort or merge Implementation Pi.tlnJ.

Second, from our observations, human programmers generally employ lop-down methods when attempting to understand a program. If a program understanding system employs the same basic lop-down approach, then a user of the system should be able to follow, in a natural way, the system's progress. If the actions of our system can be easily understood by the human user, then it is feasible to consult the user when the system decides it needs help. Both the value of using a human expert as an active partner and the importance of conforming to his problem solving methods has been well documented in the AI literature.

2.2. Templates

In our system, pbbs are considered to be independent of the particular implementation language in the sense that, while they may a~sume the existence of certain data structures or lypinr_: conventions, the pbbs cannot be compared directly to the !;Iring of characters that form the program. The informat ion to make this comparison is represented in our system by a structure we call a template (This term was selected on the basis of a structure proposed to fulfill a similar function in a model of human programmer behavior, llrooks[2)).

A template links together information about the way In which a function or operation is performed in a particular programming language. In many respects, our use of templates resembles the use of axiomatic assertions to describe the effects of pieces of syntax (Hoare[5)); however, for U!;e in our system, we have extended that idea by ecneralizing the notion of syntactic type from just those !.lructures which are primi tive in the programming language to encompass any kind of pattern in the surface structure of the code which has an associated function. For example, the function of ;,looping though an array" might have associated with it the followil'g pattern:

Note that there are places in the pattern in which arbitrary, unmatched pieces of code can occur.

2.3. Distinctive Features and Beacons

To verify a hypothesi1.ed refinement or decomposition, code must be found in the program text which helps validate the hypothesis. To do this, a template must be found whose function is the needed one and whose pattern matches some portion of the code. The expected number of templates in our system is large so that matching templates efficiently is a central problem.

Our initial approach in solving this problem was based on an observation about the way human programmers look for particular functions in a program. Programmers generally associate with each function a set of distinctive feo.tureJ which enable them to locale the function in the code. For example, an interchange of two elements of an array is a distinctive feature of sort routines. We therefore thought that templates could be grouped into sets of distinctive features for each pbb in our system, and that a hypothesized pbb could be bound to the code by searching for just those distinctive fcatureJ associated with its function. A further observation on human programmers caused us to modify that approach somewhat.

While human programmers look for distinctive feo.tureJ to help confirm their hypotheses, they also notice particularly salient features of other pbbs. We term these unusually !;alieni features beaconJ. For example, a programmer looking for (hypothesizing) a sort routine might also identify the file-to-list-copy pbb of figure 1 by noticing a READ statement (beacon) somewhere else in the program. We felt that such behavior was advantageous in our system as well for nominating new hypotheses, and modifying and refining existing hypotheses; the approach we use for obtaining this behavior is a. dynamically adjustable saliency ordering for matching templates.

2.4. Bindin11

Once a template is matched, the code is bound to the assottaled pbb. This binding is both for operations and data structures so that each surface data structure is bound to its associated input or output slot. For example, suppose that the pbb of figure 1 was bound to the piece of code In figure 2.

I= I 100 REA[)(20,900,ENDE200)NEW(I+ 1) NEW(IH+2 1=1+2 GO TO 100 200 NEW(I)cO

NEW is now bound to linkedlisl 1. This allows us to in effect attach the piece of information "holds linked list" to NEW and move the system's understanding of NEW away from the surface and closer to the domain.

If more than one template matches a particular piece of code, only the more detailed is actually bound. For example, if a section of code was both matched by a Quicksort template, and a more general, abstract sorting template, the code would be bound to the Quicksort pbb.

2.5. Searchinc the Code

There arc several possible outcomes when attempting to bind a particular hypothesized pbb. First, a template might exactly match the hypothesized pbb. In this case, the system has no new information regarding possible refinements to the matched pbb, and hence, must choose a refinement to try using its own local information. Currently, a fixed order list of refinements is used, but in the future, a more efficient decision process could be used to take into account the type of knowledge experienced programmers carry around as rules of thumb, such as "use a linked list if data is going to be inserted or deleted frequently", or the inverse "use an array if the data is relatively static" (see also Kant's "implementation selection rules" (6)).

• If a template matches a more refined pbb than the one hypothesized, then the more abstract pbb can be replaced in the corresponding Implementation Plan with the new refined one. The effects of this new, more detailed pbb are allowed to ripple throughout the links of the IP, generally causing the refinement of other sub-parts in the IP. An attempt will be made to match each of these new, more refined sub-parts, causing possibly still further refinements and rippling effects.

The depth-first search for clistincti.11e features may be preempted by the matching of a beacon. If the ~>.aeon's associated function is a sub-part of the current hypothesized plan, then the system will bind the sub-part and allow any rippling effects to take place. In at least some cases, this will result in the deactivation of the current clistincti11c features being searched for, and the activation of more refined templates. The overall control flow will thus be opportunistic, working on those parts of the Implementation PlAn for which the most information Is available.

2.6. When Thincs Go Wronc

In lh" ideal case, a matching piece of code can be found for each hypothesized sub-part in a plan; in practice, of course, this seldom occurs, and a number of things can go wrong. Two of the more common are: 1) no template can be matched for a particular pbb, and 2) a beacon template is matched for a pbb that is not part of the current hypothesized plan. In the first case, if many other pbbs in the plan are still unmatched and if an alternative plan is available, then the system will adopt the alternative plan. In most cases, however, an attempt will be made to match the missing pbb by assembling it out of smaller functions. In this case the system does behave in a bottom-up manner.

In the second case, tho system attempts to revise the hypothesized plan to incorporate the unexpected match. We have not yet defined a satisfactory method for this modification which avoids the problem of re-binding already successfully bound sub-parts, but we are considering approaches which attempt to minimize the number of changes (see for instance the similarity networks of Minsky[?)).

3. CONCLUSION

The system we have described possesses several unique features. First, (I allows a useful partial understanding to be developed whenever lime, the task, or lack of knowledge make a full understanding unattainable or unreasonable.

Second, by noticing the behavior of human programmers, the notion of distincti11e features and beacons was incorporated into the system. These features, in combination, allow the system to act in an opportunistic fashion, exploiting whatever looks most promising as recognition proceeds.

Finally, a knowledge representation called templates was defined. Templates link a syntactic pattern with a particular function, and are general enough to be used in both top-down and bottom-up search.

REFEREf\ICES

• [ 1] BARSTOW, D. ( 1978) Automatic Construction of Algorithms and Data Structures Using a Knowledge Base of Processing Rules PhD Thesis, AIM-308, Stanford AI lab
• [2) BROOKS, R. ( 1975) A Model of Human Cognitive Behavior in Writing Code for Computer Programs PhD Thesis, Dept. of Psychology, Carnegie Mellon University 1975
• [3) BROWN, A. (1977) Qualitative Knowledge, Causal Reasoning, and the localization of Failures PhD Thesis, AI-TR-362, MIT AI lab
• [ 4] de KlEER, J. (1977) A Theory of Plans for Electronic Circuits Working Paper 144, MIT AI lab
• [5) HOARE, C. (1969) An Axiomatic Basis for Computer Programming CACM 12, 1969
• KANT, E. (1979) Efficiency Knowledge for Program Synthesis PhD Thesis (forthcoming), Stanford AI lab
• MINSKY, M. (1975) A Framework fro Representing Knowledge The Psychology of Computer Vision, P. Winston (ed.) McGraw-Hill 1975
• [8) RICH, C. and SHROBE, H. (1976) Initial Report on a LISP Programmer's Apprentice AI-TR-354, MIT AI lab, Cambridge, Ma.