Structured Planning and Debugging

STRUCTURED PLANNING AND DEBUGGING

Mark L. Miller and Ira P. �old~tein Artificial Intelligence l.aboralory l\lassachusetts·lnHilute Of Technnlogy · Cambridge, Massachusetts 02D9

Ah~tract

The SPADE theory uses linguistic formalisms to model the program planning and debugging processes. The rheo:>ry hegins with a taxonomy of buic planning concepts covering strategies fnr identi.ficalion, deco.mposilion and refnrmulation. A handle ·js prn·i·lr·l for recognizing interactions between goals and deriving a linear solution. A complementary tuonomy nf rational bugs and assnciate·l repair techniques is also provided. SPI\Of: introduces a new data structure to facilitate debugging -- the derivatinn tree nf the program.

SPADE generali7.eS recent work in Artificial Intelligence by Sussman and Sacerdoti on automatic programming, and e·lemb the theory of program design devclopml by the Struct·ured lrogramming movement. It provides a more structured information processing model of human problem solving th.an the pr.o·luction systems nf Newell and Simon, and articulates the type nf problem solving curriculum advncated by Papert's Logo Project.

I. A Multi-Faceted Approach

The SPADF. theory is being develope·) in three contc.ts:

I. Educatinn: an editor called SPADEf,-0 has been implcrnrnlr·l that encourages Hudcnts to define and ·lebug program< in term< of explicit SPADt: design choices, thereby providing a highly <lruclure·l programming environment.

1. AI: an automatic programmer called PATN has bern designed using an augmcntod tran~ition network embodiment of the SPADE theory. This rr.~ults in a framework which unifir< rrcrnt work on planning and debugging by Sacerdoti [75] and Sussman [15].
2. Psychology: a parser called PAZATN has been designr·l that applies the SPADE theory to the analy~is of programming prolocnls. PAZATN produces a parse nf the protocol that delineates the plannin,~t and debugging strategieK employed by the problem snh·er. PAZATN extends the series nf automatic prot.ocol analy1.er< ·levrlnpr<l at Carnegie-Mellon University [Waterman & Newell 72, 7:1; Bhaskar & Simon 76].

Hand -simulations of Pot\ TN and P AZATN on elementary programming problems and informal experiments with the SPADI·:t:-0 editor attest to the theory's cogency in accounting for a wide rangr of planning and debugging techniques [Goldstein & 1\lillcr 7iia,h; Miller & Goldstein 76b,c,d~

2. A Linguistic Analogy

In developing a representation for problem solving techniques, we have been guided by an analogy to compulalinnal lingui~tics, for three reasons.

1. The con~epts and algorithms of computational linguistics, though originally intended to explain the nature of language pu ~t', supply perspicuous yet powerful ducriplions of complex computations in general.
2. Computational linguidics decomposco computations inln syntactic, semantic, and pragmatic components. This decomposit.ion clari·fies the explanation of complex processes when viewed in the following manner: syntax formali1.u the range of possible deci.sions; semantics the problem description, and pragmatics th~. procedural relationship between the two.
3. Computational linguistics has un·lergone an r.vnlution of procedural formalisms, beginning with finite stal.e aut.nm~ta, later employing recursive transition networks (context free grammars), nr.·t. moving on to' augmented transition nelworh, and culmii·ating in the current set of theories involving frames [1\linsky 7li, Winngra·l 75, Schank 75~ Each phase captured some properties of languagc, hut wu incomplete and required generalization to more .Powrr.ful and

elaborate formalisms. Following this cvolutiona.ry sequence illuminates the complr.xity of language theory. We have puf'ue·l a similar evolutionary approach to clarify the complexity of problrm solving processes.

·To date, our theory of program design has cvolve<l as foiJn,.·s: we first explored context free grammars for planning and ·lehugging, and subsequently lhcir generaliution to ATN'F; we thcp c.arni!>r·l the metaphor of protocol analysis as parsing, initi·ally using the planni.ng and debugging grammars to reveal the consliluenl st.rucl nrc of protocols and later using the derivations prn·lucr.d by 1 he A'rN formalism; and, most recenlly, we have Atudied the use of a. chart-based parser to discover these analyses.

3. A Grammatical Theory of Planning

The basis for SPADE is a taxonomy of frequently observed planning concepts (fig. 1). We arrived at 'this taxonomy by

introspection, by examinink problem solving protncols [l\lillrr & Golddein 76b], by studying the literature on prnhlem snlving [Polya 57, 65, 68; Newell & Simon 72; Sussman 75; Sacerdoti 75], ami by enumerating techniques for finding procedural snlutinns to problems cxpreued as predicate calculus formulae [f:m,Jen & Kowalski 76]. This last criterion demonstrates that the taxonn.my is currently incomplete -- for example, techniques for handling disjunctions have not yet been analyzed thoroughly enough to warrant inclusion. However, the taxonomy is adequate for ·a wide range nf elementary programming problems.

There arc three major cJa·ues of plans in the tuonomv : identification, decomposition, and reformulation. Identification means recognizing a problem as previously solved. Decompnsition refers to strategies for di·iding a problem into simpler sub--problems . Reformulation plans alter the problem descriptio'n, seek ing a representation which is more am·r.nahle to identification or decomposition. The figure indicates how these classr.s of plans· arc further subdivided in the SPAD~: theory.

Planning, according to the theory, is a process in which the problem solver selects the appropriate plan type, and then carries nul the suhgoals defined by that plan applied to the current problem. From this viewpoint, the planning la.onomy represents a dr.cisinn l.rec of alternative plans. The decision pro~ess can be m·odcled by the context free grammar given below. The grammar explicitly ·Lairs which plaf!ning rules involve recursive application of ·olution teciTnique~ to subgoals: selup, interface, mainUep, cleanup, an<l Th~ rr1111mr 16 wrlll~n usint lh~ fo/lowint synln "I" i6 di6junclion, "·" is ord~red conjundion, "&" Is unordered conjundion, "< ... >~" is iler·tion, { . . .} is oplion11ily, lnd · lower cu~ p/true in quo I Ilion m~rh (~f. , ·,~~·' sl~p· J deKribe6 · lerte~l il~m which 16 not further erp,.ded In lh~ 1r1mmr.

PLAN ·> IDENTIFY I DECOMPOSE [ REFORMULATE

IDENTIFY ·) PRIMITIVE I DEFINED

DEFINED ·> ·call user subprocedure· & PLAN

DECOMPOSE ·> CONJUNCTION I REPElJTION

CONJUNCTION ·> SEQUENTIAL I PARALLEL

SEQUENTIAL ·> [SETUP] + (MAINSTE·P + [INTERFACE]>* + [CLEANUP]

PARALLEL ·) <PLAN)

SETUP ·) PLAN

MAINSTEP ·) PLAN

INTERFACE ·> PLAN

CLEANUP ·> PLAN

REPETITION ·) ROUND I RECURS ION

ROUND ·) ITER· PLAN I TAIL· RECUR

ITER-PLAN ·> "repeat step· + SEQUENTIAL

TAIL-RECUR ·> ·stop step· + SEQUENTIAL + "recur .step"

The SPADE theory is not restricted to any particular domain. However, to provide concrete eumplc~, we have concent.ratr<l on problems from elementary Logo graphic~ programming [Papert 71 J This domain wu cho~cn because of the availability of exten~ivc student performance data. The grammar rule~ for primitives in thi~ domain arc:

PRIMITIVE ·> VECTOR I ROTATION I PENSTATE

VECTOR ·> (FORWARD I BACK) + "number"

ROTATION ·) (LEFT I RIGHT) + "number·

PENSTATE ·> PENUP I PENDOWN

A typical la~k undcrt~kcn by beginners in the Logo environment is lo draw a wishingwcll picture using the computer (fig. 2.). Fig. 3 illustrates a solution lo the wishingwcll problem with its hicrarchical annotation according to our planning grammar.

FIGURE 2

The grammar characterizes the decision process involvrtl in selecting plan~ from the taxonomy. We illu~tralc il~ utility in the next two sections by constructing an editor that emboolie~ the gramma.r and analyzing debugging in terms of the grammar. Then we , ·how how the grammar can he augmented to include nol only thr. ayntax of plano, but their Rcmantics and pragmatics as well.

~. SPADEE-0, A Planning A~~i~tant

One reason for calling our theory of planning and olr.hugging Jlruclured is lo emphasize tbe· link between our re~r.arch and the Structured Programming movement. Dahl, Dijhlra, and Hoare [72) .call for a style of programming which reflcr.ts r.ohcrenlly ~lrur.t.urr.·l problem solving; but a detailed formali7.alion of what thi~ ~tyl~ entails is lacking. Our efforts in this direction, therdorr., ~upplr.rnr.nt the work of Dijkslra and others. How can we judge, though, whether a particular grammar of plans captures the planning tlccisions involved in solving problems for some domain? One methodol?i:Y iR ln incorporate the grammar into an editor (SPADEF.-0) who~e purpMr. is to augment and direct the capab;.lities .. of a human user. Thr. critical question then becomes the extent lo which the editing system aiols or hinders the user.

Suppose a problem solver is defining a Logo program for drawing the wishingwell shown earlier. ·Jn SPA rn:E-0, this is accomplished by applying the planning .grammar in generative rnotlc:

la . What 1s the name or your procedure?

lb . )11\1

• Za . The rule 1s: PLAN·> IDENTIFY ! ·DECOMPOSE I REFORMULATE. What now?

Zb. )DECOMPOSE

·

SPADEE-0 thus encourages users to arlicul~lc their dr.~ign decisions in lop-down order. At the same lime, the system allows tlu' user lo escape from this strict tlisciplinr. if an altcrnaliW! ~oluti.on order seems preferable. This was illuslratetl by the i1~r.r'~ "later" instruction, which suspends the current goal for suh~equenl solution.

SPADEE-0 was implemented hy a.signing an in.tnrpretivr. procedure to each grammatical operator. [n r.«r.nce, the eolitor is a bookkeeper for the 11ser's goal tree. Though simple, the ctlitor senr.s three useful purposes.

I. From an educational slandpoi.nt, the ctlilor· encourages sludenll to articulate their problem solving .trategir.s. The fundamental hypothesis of the Logo Project, as presented by Papr.rt [71], is that such articulate problem solving is beneficial to the learner. SPADEE-0, with its extreme form of articulation, provitlr.~ an experimental vehicle for eval11alin&: Papcrt's claim. Our cxperirn~nt will be lo test whether students exposed to SPADEE-0 learn L"go fader than controls whose problem solving is ·more lacil.

2.. From ~n AI standpoint, its usc will indir.atc whc.thcr the planning grammar is adequate, or whether cerl.ain plans ar.e not present that competent problem so.lvcrs fed arc ncce~~ary.

3. From a psychological standpoint, we will collect tran~cripts of individuals using the editor and formulate pcr~nnnl grnmmnr~ ba<~tl on the particular rules usually employed by ·each u~cr. The persnnal grammar will model lhe problem solving skills of lhal individual. In the past we have manually analyzed protocols ·from stand art! l.ogn. SPADEE-0 protocols, with their explicit planning choices, ~houlol he far more revealing.

5. RAID, A Debugging A~~istant

SPADE include~ a theory of debugging. ·Such a tl.rory i~ e~scntial, ~ince problem ~olvcr~ mu~t often formulate plans in the face of imperfect knowledge and limited re~ource~ . lln<ler ~uri. circumHances, even carefully reasoned judgments may he mi~takcn.

Given a grammatical theory of planning, debugging can he analyzed as the localization and repair of error~ in applying grammar rules' during planning. Since our planning rule~ were coMtrurtr·l from operators for conjunction, disjunction, an·l optionality, lhrrr basic classes of errors arise:

1. syntactic bug~, in which the basic grammar is violate,), ~uch as when a required r.onjuncl is mis~ing;

2. semantic bugs, in which a s.cman.tic .cons I rain! arising J rorn the particular problem is violated, such as ·when a synlaclically oplional constituent, 11eeded because of the semantics of the particular problem, is missing;

3. pragmatic bugs, in which an inappropriate selection from a scl of mutually e·clusive di·juncu is made.

Fig. 4 exemplifies these bug typu. Although .additional Fl GURJ: t,A - SYNTM;TJ C,,I.L,\' JNCOlWI-:CT 1·1. ,\~J

A Nf.Cf:~S/\RY C"UNJt; :~CT 1r. MTr. ~: ! ~ : ·:

A lZSJ categories (including execution and efficiency hug~) mu~t he ·ldincd to make this taxonomy of bugs complete, the~e das~M arc ·a,Jequale to characterize many examples which arise in r.lcmcnlary programming. ·

RAID is a debugging assistant for SPADI~E-0 im'plemcnld on the basi~ of thi~ taxonomy of errors. As SPA J)~~E~O ·prompts the u<cr through the planning process, those choices which might .lead t.o syntactic, semantic, or pragmatic bu11s .are recorde·l by the sy<tcrn. In ~ubscqucnl debugging episodes, RAID alerts the user to the relevant bug warnings, thereby aiding in diagnosis. Moreover, the SPADEE-0 planning cdito·r can then be reinvoked to guide repair of the bug by resuming planning in the context of the culpable decision. An interaction with RAID that would arise from premature execution of a program is illustraled below:

The u·cr htu conlinucd dP./ining rhe wi.,hinJriMII progrrrm ltP.Ifllll earlier, wirh iu currenl definirion as 'hown in /if(. 4b. /llrl·m.tf(lt an inirial SETUP and 4it I NTERF /ICE havP. nor yer bP.en ~upplird, lhc u·cr rcqutl·U cs-ecurion ofthn program.

lb. >RUN WISHINGWELL 2a . OK . (Fig. 4b ·how· I he re·ulr.) What no111 2b . >Diagnose 3e. lha rule 1s: DIAliNOSE -) <PARSE )CODE )MODELl PROCESS/ Which type of d11gnos1s do you want to use7 3~. >Parse 4a. lhe rule is : PARSE -> SYNTAXISEMANTICSIPRAGMATJCS . Which bug type do you want to consider? 4· . )Semant 1cs 5a . The following optional steps are missing: The SETUP and the WELL-POLE INTERFACE. 5b. >Repair &a . The rule 1s : REPAIR -> COMPLETE I REPLAC£. &b . )Complete intarhce between wl11 and pole. 71 . The rule 1s : COMPLETE -) PLAN -) IDENTIFY I

In this example, the interaction with Sl' ADKE-0 was again guided by 1 grammar; thiA debugging grammar is given below.

DIAGNOSE ·> <PARSE I CODE I HODEL I PROCESS>"

· PROCESS - > <ASK I TRACE) CODE -> "print definition· MODEL -> RUN PARSE -> SYNTAX I SEMANTICS PRAGMATICS SYNTAX -> "review conjunctive choices in plan· SEMANTICS -> "review optional choices in plan" PRAGMATICS -) "review disjunctive choices in· plan" REPAIR -) COMPLETE I CORRECT COMPLETE -) ·solve for missing conjunct· CORRECT -> "choose alternative disjunct" RUN· -> ·run code line· +("error msg") +(DEBUG.] ASK ·> "print definition" I "print value· . . . TRACE -) (S.ELF -DOC ) + RUN SELF-DOC -> "add break" 1 "add print" I "add trace·

The g~ammar i5 intended to include the traditional dchugging strategies employc<l by programmers as well as the PA .RSE-hasr~l strategies made possible by the derivation tree.

For more complex programs, there will be lao m~ny pnlrntial bug locations for RAID's undirected advice to be helpful. Hence, following SPADEE-O's Jlruclurcd bookkMping ph'ilnsorhy, wr. allow . the user to set caveats during planning regarding those ·lc~isions which appear to be potential trouble spots. In t.hi~ fashion, SPADEE-0 permits an exploratory style of problem solving, as illustrated bel(lw.

SuppOII'I· rhe widtingwcll program iJ pari of n larf(e projrr.l. Tlof'n lhtJ numbP.r of oplionfll eonJiiluenu tl.al ""'"' nol b · .,,. dP./i,..,d . will be largn. The u.·P.r will probably have ~omn itui~rhr inlo wloir.h of rhe"' i· aclually needed. To faciliratr.· dr.bll.f(f(inf(, rhn JUP.r i· enr.ouragcd ro p/acr. caveal· al rho·e d~ci,ioru he ~u·pncl· mny requirtl truer debug gin g.

61. Do you 11ant to dafine the optional SETUP7

6b . >No .

Ta. Do you wish to record a caveat htre7

Tb. )Yes .

a. . OK . ROOF, POLE, and \IELL ere pending .' .. .

Another mechanism to make SPADEE's and RAID's advice more directed is to supply the sema11tics for problems. This is the topic of

SQUARE X; TRIANGLE Y; INSIDE X Y;

then a decompo~ilion that draws the ~quare and triangle inrlepr.nrl~ntly and then attempt< to fit them together to achir.ve the in<irle rclatinn will fail. However, a problem description of tho following form allow< a Kucce~dul rlccompositinn:

SQUARE X, WITH SIDE · 100;

TRIANGLE Y, WITH SIDE · 300;

CENTER OF )( · CENTER OF Y.

The INTERACTIONS prr.dicale is a conjunction of te<ts on thr. model register. Each lest is responsible lor rletr.cling a gi,.r,n non-linearity. A corresponding action modifies the morlrl , arlrling new statements to make the interaction explicit. The R D 'l Nl·:~n:NT I nor is the repository for what S.,s<man [75) calls the Critics Gallery. The theo.retical progress of PATN is to integrate the Critic< Gallery concept into a tlrenry of planning. In Sussman's HAC. I\ ~:R, the crit irs gallery and library of programming technique< were separate rnnolulcs: there was no inlegralcrl theory.

Of coinsc, at any point in time the system may he unaware of a given type nf non-linearity. In such cues, the ahs~ncc nl an interaction teGL will !carl to a sequential decomposition that ultimately fails. The design of a program for debugging such failures is thr. su bjcct of the next section.

7. DAPR -- An ATN lnr Debugging

PATN can make mistakes. That i~, PATN will sometimes introduce what we term rational bug- into its plan~, rlue In making arc transitions with imperfect knowlcrlge of subtleties or interactions in the task domain. Hence, PATN must be equipped with a · complementary debugging module, DAPR (fig. 7).

.,

"'

"

~

..

DAPR's ta&k is easier than that ~·f RAID: DAPR must analyt.t­ the closed set of bug types to which PATN is subject, whereas RAID i~ intended to assist human programmers in finding and correcting a wide assortment of bugs. DAPR employs three diagnostic techniques:

model, procus, and plan diagnosi~. 1\lodcl rliagno~is i~ ti1e basic technique. It amounts to comparing the effect~ of executing a plan tn a- formal description or its .goals, t.o rlctcrmine if, anol in what fashion, the plan has failed. Another OAPR technique, hased nn Su«rnan"· HACKER [75), is cumining the st.ate of the procr.s< at the tirnr of the error manifestation. Plan diagnosis, a DAPR first, involves examining the cavcttil left by the planner as varinus nnrle< were constructed.

DAPR will also be used to provide additinnal guidanre tn RAID. This illustrates the synergism po<siblc when crlur.ational, psychnlo):!ir.al and AI facets of a cognitive theory arc sturlicrl in an intr.gratcrl f11shion . . This integration is further excmplifierl in the next scr.tinn when we apply the SPADE theory to protocol analysis.

8. PAZATN, a Protocol Analyr.r.r

As soon as one has an heuristically adr1uatc th~ory of program design, it is natural t.o ask, "Can the theory provirle an account of how pt!oplt! design programs?". An experimental tuhniquc wr employ for answering this q·ucstion is the analysis of protocols r.oller.te<l du¥ing problem solving scssiono. By adopting this m~th,rlolngy we follow the precedent established in ·eminal <tu·lir.A r.nnoluctcol at Carnegie Mellon llniver·ity [Newell & Simon 72; Watcrmau & Newell 72, 73; Bhaskar & Simon 76). Our work extc~ds their approarh along three dimensions.

1. With the exception of the recent Bhaskar & Simon rffnrt , the Cl\1\J studies have been rc<trictcrl to very limited ·lomain< "'cl' as cryptarithmctic. Rather than limiting the task rlomain, we limit thr. range of re~pnnses. Typically protocols arc tranHript.inns of think-aloud vcrbalir.ation<; we focus on the more restrictrrl interactions arising from a problem solving ~cssion at a cnrnputrr console. The analyf'is task in this selling is to interpret usrr act inn< --editing, executing, tracing, etc. --in terms of the SPADE theory of planning and debugging.

2. The CMU thcnry centers on thr. ,rodurlion ayalrm.· modd. Although productions arc Turing universal, thy cncourag~ a lc._ hierarchical, less local program organi7.alifln than th~ linguistic formali·ms of the SPADE theory. In PATN, each arc transition, consisting of a predicate and an action, can -he thought nf as a production. However, PATN organi7.e5 lhcsc produclinM into loral contexts, c.ach of which consists of the arcs uiting frnm a l:i'·~n nn·lr.. Not all of the arc productions arc present at any mnmcnt in time; an arc is present only when the problem solver is at the relevant nook In the prorlucl ion systems discussed in 1/umnn Prohlt!m So/t·illll' [Newell & Simon 72), all of the productions arc always pre<f'nt anti ar~ tested in serial order.

3. CI\IIJ analyses S(C based on the ,roh/l!m brha11ior ll'rtiJ>I>. Pursuing an analogy to computational linguistic<, we dclinc an interprc.la~ion or a protocol to he a pttr.<l! lru "fl'plr.mrntr.rl hy ~emantic and pragmatic annotati"on. The parse tree characlr.ri7.~< the constituent structure of the protocol. Semantic and pragmatic annotation -- variables and a~~crtions attaciJcd to nodes of the par<r tree -- formalir.c the problem dc~cription and the rationale for particular planning choices. Annotated parse trees closely reflect the local 5tructure of PATN's linguistic problem solving machinery, leading more directly to inference~ regarding imlivirlual difference~ than i~ evident from problem behavior graph~. .

Ruven Brook~ [75) applied the CMU approach to thr programming domain, developing a model of coding - - the translation of high level plans into the 6latcment5 of a particular programming language -~ anrl testing the model by analyr.ing protocols. His mo1ld is a set of production rules whose conditions match the pallr.rn< of plan clements and whose actions generate code statements. Protocols arc analyt.~d manually, with the experimenter attempting to infer the plan which is then expanded by the production system into cnrlc paralleling that of the protocol. The processc~ of undcr~tanoling the problem, generating the plan, and debugging arc not formal i1.r.rl. SPADE goes beyond this in that it can be used to par<c protocols anrl that the parse constitutes a formal hypothesis rcgarrling nnt only the coding knowledge but also the planning and debugging strategies employed by the problem solver.

(Miller & Goldstein 76b] provides an r.umplc of such analysis being performed by hand. The example is a segment from a protocol 1r..cul hundred lin~ long in which a high school student uses l.ngo to draw the letters of his name. By eummmg the ~:rarnrnar rulr< present in the .derivation, we can oh<erve variou< properties of the ~tudent'~ problem solving such as: reliance on r.ert a in planninr, choices to the c.r.lu<ion of others (e.g., the <tudcnt emplo)·rd iteration, but never recursion); the mi<u<e of certain optional constituents (r.f.! ., .· setup was usually included in each PrOcedure even when it was unnecuury); and certain ~ituation~ where his prohlrrn snlvinf.! violate~ the grammar and hence is ~usr.eptihle to <ynt.artir. error< (r.f.! ., programs were often c.ecuted before their <ubprore<lurcs ha<l hrrn defined).

J u~t as a context free grammar is incomplete as a t henry . of planning, likewise a parse i~ only a partial analy~is of a protocol. Thr theory of annotation developed in the PATN work lr<l u< from describing only the ~yrrlaclic ~lruclurl! to more cnmplete analy<r< of pro.locols: an interpretation of a protocol is the selection of a particular annolalcd PATN plan derivation. Fig. 8 shows such an

. · . ~ ..

co "

analysis of a simplified protocol in which a wishingwell program i< defined, executed and debugged.

PAZATN is a chart-based par<er [Kay 7J; Kaplan 1:1) being implemented to interpret protocols in terms o(PATN'~ annotate·l plan derivations [Miller & Goldstein 76d). It will operate by causin~: PATN to de-viate . from its preferred approach in re<pnn<e to bouom-up evidence (fig. 9). By taking advant.age or' par<inf.! stra·tegie~ developed in research on <peer.h un·lrrstanding · [Lc«er et al. 75; Patton & Robinson 75], a< well a< the er.onornir.al chart representation of ambiguities, PAZATN ha< been ~ucr.e&<fully hand.-~imulated on ten Logo protocol<. .

PAZATN will operate by matching PATN-f.!enerated plans with protocol data. Two chart~ .will br. u~ed .to repre<eut altern.a.t ive interpretations. The PLANCifART keeps tra~k of the set of p_l~·.r~ihl·~ subgoals which have bern proposed by PATN. t"ig. iO s1,,;;.., a planchart for a wishingwdl in which PATN has propoSI" I two ,alternative decompositions. The structure is a chart her.ausr. it .<harr< substructures, as exemplified by the co,;mon ~olution to the WELL subgoal poi'nted .to by·'both wishingwell 'decomposii.ion'ii-. : The ' DATACHART records ·th.e ~tate of partially completed inte,rprctati<>n<.

These chart~ arc grown as follows. Fir<t PAZATN rr<Jursts PATN to generate it~ most plausible plan. This plan i< insr~t r.~ into the PI.ANCHART. Then protocol event~ arc analy7.r.<l one hy 'onr., arul matched with subgoals in the PATN plan. The match is recor<lrtl in the DATACHART. H no plausible matches arc foun<l , PATN is a<krtl to generate the next most plausible plan. The PLANCH ART is thereby cxtrnded. Common subgoals ~hare the same structure in the chart.

At fir~t, PAZATN will he implemented inlcract.ivcly, with tlte user -- a psychologist analy1.ing a protocol -- directing PAZATN to select different PATN plans. This follows the incremrntal implementation strategy useol in two of the Ci\IIJ protocol anal)'7.crs [Waterman & Nc.wdl 72; Bha<kar & Simon 76). PAZATN, even in -its early interactive stages, ~hould provide strong evidence rcgaroling PATN's adequacy as a cognitive theory. ·

PAZATN will also be tested in the SPADEE context. Below is FIGURE 11 OATACHART LINKING PROTOCOL EVENTS TO PLANCHART LEAVES

a hypothetical dialogue with SPADEE-2., reprc~enling the original SPADEE-0 augmented by both PATN and PAZATN.

11·. Solving for WISHINGWELL. Pending subgoals a.re : ROOF, POLE, WELL, interfaces. What now? lb. )SQUARE

Za . OK . WELL has been solved by o call to SQUARE . SQUARE has already been solved . What now?

PAZATN will increue the editor's flexibility in han<lling ambiguous events, and in alleviating what might seem to snme usrrs to be an excessive allocation of lime and effort to .t~r. planning pha<r.

9. Conclusions

The usc of tools from computational linguistic~ ~- grammar<, ATN's, derivation trees, parsing algorithms, rha~t~ -- has lr.<l In a perspicuous representation for a thMry of planning ami ·,Jrhugging. Computational linguistics is also responsible for suggesting the propitious decomposition of problem solving processes into r.omponcnts involving syntactic, semantic and pragmatic knowledge.

Our multi - faceted approach -- studying problem solving in the three distinct contexts of AI, education, and psychology -- hol·h nul the possibility of a synergi~Lic cUed. But proof of this must. await further experimentation: Although all of the programs ha,·r. heen designed and hand-simulated, as of this writing only the SPA OEI·>O ed itor has been implemented. Furthermore, the theory has nnt ) 'CL been exercised in enough cont.r.xls to prove it~ generality. Howr.··cr, at least for .the three domaiM in which the theory has bren uplnre<l -- Logo, the Blor.ks World, and elementary r.alculus -- it has provi<letl a unified treatment of plans and bugs, a significant stride for a theory of program design.

The .utomtflc problem solvint tsped "'IS supported by the Advtn~d Rese·rch Projects Atency of the Deptrlmenl of Defense under Office of Ntvsl Researclt contrecl N000/4-75-C- 0643, the eductliontlupecl by the Ntlion·l Science Foundttion under trltll C40708X, 111d the proloaJI 1n1ly·is upecl by Me Boll Berenek & Newm1n lntellitenl lnslruclion·l Systems Group under controcl MDA 903-76-C-0/08 jointly sponltDred by Advon~d Re·earch Projects A1ency, Air Force H<lm111 ResoiJt'ces Llbortlory, Army Research lns/ilvte, ltld N1111li Personnel Resetrdt & Development Center.