Overview of the Programmer's Apprentice

1. Introduction

The Programmer's Apprentice (PA) is an interactive system for helping programmers manage the complexity of evolutionary programming. It is being designed and implemented at MIT by Charles Rich, Howard Shrobe and Richard Waters (only some of the modules in the system are actually running at the present time). The intent is that the programmer will do the hard parts of design and implementation, while the PA will act as 1 junior partner and critic, keeping track of details and assisting the programmer In the documentation, debugging, and modification of his program. In order to cooperate with the programmer in this fashion, the PA must be able to ·understand· what is going on. The central achievement of the Programmer's Apprentice project has been the development of a ·plan· representation which facilitates the cataloging of basic programming knowledge.

The ·plan· for a program is a network of operations interconnected by data flow and control flow links. This representation is a better vehicle for expressing the loaiCII interrelationships in a program than the programming lanauaae source code. A plan is segmented into a hierarchy of subsegments, each corresponding to 1 concepluel unit of behavior. The plan specifies how each non-terminal segment is constructed out of the segments conteined within it. Explicit dependency links are used to record the goal-subgoal and prerequisite relationships between 1 segment end Its subsegments. liken together, these links summarize how the behavior of 1 segment follows from the behavior of its subsegments and the way they ere connected by control flow and data flow. A final aspect of the plan representetion is that there may be more than one plen for 1 progrem or pert of 1 program, representing different points of view.

The plan representation is also used in the PA system to construct a library of common algorithms and data structure implementations. In general, the PA attempts to understand a programmer's code in terms of these femiliar plans.

This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technoloay. Support for the laboratory's artificial intelligence research is provided in part by the Advanced Research Projects A&ency of the Department of Defense under Office of Naval Research contract N99814-75..C-9643.

2. A Scenario of Use of the PA

The following imagined dialogue between a programmer and the PA is presented in order to illustrate the intended operation of the system. (Comments discussing the scenario are printed in italics.) The scenario illustrates the followin& basic areas in which the PA can assist a programmer:

1. DOCUMENTATION: The PA provides automatic, permanent, and in-depth documentation of the program. The PA remembers not only explicit commentary supplied by the programmer with the code, but also a substantial body of derived information describing the logical structure underlyin& the program.
2. DEBUGGING: Any discrepancy between the PA's understanding of the proarammer's intent and the actual operation of the program is reported to the programmer as a potential bua.
3. MANAGING EVOLUTION: Based on its knowledge of the loaic:al relationships between parts of a program, the PA is able to determine what parts of a program are affected by a proposed design change. It can use this Information to warn the programmer of impending difficulties.

The scenario traces the design, coding, and subsequent modification of a program which deletes an entry from a hash table. The scenario picks up in the middle of a session at a point where the programmer has already made many deslan choices and told them to the PA. In particular, he has stated the input-output specifications for the subroutine DELETE and chosen the basic data structures to be used. The hash table is implemented as an array of linked lists called ~uckets·. Each of the entries in a bucket is a dotted-pair whose CAR is the key for the entry.

Programmer: The pian for the routine DELETE has three main steps: the first one hashes the input key to get an index1 the second one fetches the bucket corresponding to that index from the table; and the third splices out the entry In the bucket whose key part is equal to the input key.

[The only. feature of this scenario which Is not a current reseMch goal of the ProgramtMr's Apprentice project is the use of n·tur·l English dialogue. Although the system should 1M ·ble to support 1 sophisticated natural language ·front-end", no effort has been eKpended in this direction to date.

The PA uses the pror,mmttr's outline of the t»sirn in ordflr to build · pl·n representing the progr·m's intended structure. References to b·sic progr·mming techniques such a ·spticinr out· (delefinr elements from · linl<ed list) fri1111r the retrlev.J of p/1ns from the pl·n libr·ry.]

PA: I think th·t there is 1 bug in this desi&n. If the input key is equel to the key pert of the first entry In 1 bucket then the first entry will not be spliced out.

[After constructing · pl1n, the PA uses its reaoninr 1bilitles In order to checl< for bugs. Above, the PA finds · bur 1nd report· it to the progr·mmer, fr·minr its response In terms of the ·splicing· pl1n. In renerll, if is the responsibility of the progr1mmer to supply corrections.]

Progr1mmer: Modify the plan as follows. Add a finel step which compares the bucket after splicing with the bucket before splicing and stores the new bucket in the teble under the index if the two initial cells ere not ldentkel.

PA: OK, the plan now seems correct.

[The progr1mmer then types in the code for [ELETE.]

Programmer:

(defun delete (key) ; hash table delete routine. (prog (bktl bkt2l

(setq bktl ltbl (hash key))

bkt2 (bkt-delete key bktlll

lcond ((not (eq bktl bkt2ll

1 check if first entry deleted.

(store ltbl (hash key)) bktlllll)

[The PA ·n·lyzes the code written by the progr1mmer in orw to construct · pl·n for it. Comp·inr this pl~n with the pl·n directly descriN<I by the progr·mmer, the PA discovers ·n implemenf1fion bug. The bug is so simple th·t the PA cen surgesf · correction.]

• PA: This code is not consistent with your plan. When the first entry is deleted, the code stores the bucket before spllclf'll, r1ther than the bucket 1fler splicing. Did you me1n: ·1sTORE ITBL !HASH KEVIl BKT2l~

Programmer: Yes, fix the code.

[Some time l·fer if is necessary to mille · modificllfion to the originll design. The PA helps the (perh·ps new) prorr·mmer mllintllin consistency.)

Programmer: I want to make 1 change in the represent1tion of buckets in the hashing programs. A bucket now hiS two parts: a count field and a list of entries IS before. The count field will contain an integer equal to the length of the list of entries. Let a bucket be a dotted-pair whose CAR is the count and whose COR is the list of entries.

[The PA inspects the logicll dependencies in the pl·ns for the progr·ms being worl<ed on in order to determine the specific w1ys in which the progr·ms c1n be ·fleeted by the proposed ch1nges.]

• PA: The proposed change will affect DELETE as follows: After the bucket is fetched, it Is passed to BKT -I:ELETE which does the 1ctu1l deletion. However, BKT -I:ELETE requires 1 list of entries while in this new implement1tion, 1 bucket is no longer just a list of entries.

Protremmer: Chenge the specifie~tions of BKT -I:ELETE so that it expects as input 1 bucket of the new type, rether than 1 list of entries.

[ ·- ·nd so the session continues with the PA loollinr over the proJr·mmer's shoulder.]

3. Current Status of the PA

Rich 1nd Shrobe [ 1) laid out the besic idea of 1 pl1n 1nd the initi1l design of the PA. Since that time Rich, Shrobe 1nd W1ters h1ve been working together on further 11pects of the theory along with design end implementation of the PA system.

Rich's work [2] centers on the plen library. He is using the plen represent1tion to form1lize 1 number of common techniques in non-numeriCII progremmin& Involving trees, lists, 1nd 1rr1ys. He is 1lso studying the use of this librery in the PA system for 1nalyzin1 1lre1dy-written progrems 1nd to provide hi&h level 1bstr~etions for interactive pro&rem synthesis.

Shrobe [3] hiS implemented 1 deductive module, c1lled REASON, which c1n re1son about progrems represented by pl1ns. REASON is a dependency besed system which m1inteins 1n explicit record of Its control lnform1tion within the seme form1lism es is used to represent f~ets. An accompenyi"l erticle in these proceedings describes how REASON reasons ·bout destructive modific1tions to complex end potentielly shered d1ta structures.

W1ters [4] has implemented 1 system which Cln analyze the code for 1 program 1nd produce 1 structured plan for the entire pro&rem. The b1sic ide1 behind Waters' work (which is described in det1il in 1n ~ecomp1nying 1rticle in these proceedings) is that pl1ns for most progrems ere built up in · sm1ll number of stereotyped ways, and th1t fe1tures in the code for 1 program can be used to determine the structure of the plen for the progrem.

Our go·l for the immediate future is to construct 1 prototype system which exhibits the kind of behavior shown in the scenerio. To do this, 1n interactive module must be built, 1nd the modules which have 1lready been constructed must be connected together into 1n integr1ted system. Looking further ·head, 1ddition1l modules (such 1s · simple pro&rem synthesis module, and one dealing with efficiency issues) will be added to the PA, 1nd the eKisting ones strengthened so th1t the PA cen teke over more responsiblity from the human progremmer.