How To Use What You Know

How to Use What You Know

Carl Hewitt M.I.T. Artificial Intelligence Laboratory

"II auhjt!cl S undt!rlltmda kno111lt!d·fl K if S "'"' K lllhent!vt!r npproprialfl." Allen Newell

Abstract

This paper surveys the state or the art In the development of problem solving mechanisms for PLANNER-like formalisms. A major design goal for such formalisms Is that "For ony ·illflll ,,;,.,,. nf lmn111lt'd·" lht!rt! arll no1urol t>lacea in 1h~ /ormaliam lo ,ror.t'Ju.rnll y r.mht!d I hr. knntnlt!d·r. ao 1ho1 il 111ill htt uat!d "'""" il ia a,.rnprioltt nnli nol u.at!li "'""" il ia inappropritJit!." Although this goal is still vtry far from being achieved, considerable progress Is bting made. This paper contains no major conctptual innovations a It hough It does describe and give the rationale for many of the design decisions that have been made In PLASMA [for PLANNER-like ~stem Modeled on Actors) which is currently being implemented at M.I.T. as part of a Programming Apprentice project and for other applications. The paper tries to delineate major unsolved problems and make suggestions for how some of them may be attacked. Argument! are presented against the competing predicate logic paradigm for the Implementation of knowledge-based systems.

!'clationship to QA-4 and POPLER

Both POPLER {for POP-2 PLANNER} [Davies 1972) and Q.A-1 [Rulifson et. al. 1972) are basically cleaner versions of PLANNER-71. POPLER made important c?ntributions In studying how to translate English quantifiers Into a procedural form and in pointing out the a.nbiguity of the 1011 statement or PLANNER. A statement or the form (&Oil (on A B)) In PLANNER-69 could be satisfied either by demonstrating that A ~lready is on B or by changing the world so that A is on B. Q.A-1 d('rivcs from srries of question answering programs done at SRI in the late 1960's and early 1970's. The Q..A-2 and Q..A-3 [Green and Raphael 1971) systems were both resolution-based uniform proof procedure theorem provers. Q..A-1 abandoned the rt~olution-based theorem prover problem solving paradigm and adopted the procedural embedding or knowledge approach of PLANNER. The most original contribution or Q..A-1 was Rulifson's development or a context mechanism.

Q.A-1 and POPLER also made some important improvements of the syntax of PLANNER-liir.e languages. PLASM A has continued in this tradition of making improvemtnts to make PLANNER-like formalisms more readable by making them more "English-like". However, II Is Important not to .be misled Into reading more Into the symbols In the code than i~ really there. In every case the the semantics of the Engli~h symbols must be impltmented elsewhere in other modules to realize the desired behavior. For example we shall glibly make assertions in the data base such as (A ia-on B) . However, at some place [eilher explicitly or implicitly) code must be provided which specifies how actors created by the template ( ... ia-on ... ) behave In matching and how they Index themselves in the data base. There is the potentiality for doing the indexing cleverly taking advantage . of the fact that ia-o11 Is a transitive asymmetric relation. 1\ut In order to do so the specialized code must be made known to the ( ... ia-nn ... )template.

The major advance accomplished in PLASMA has been to explicitly base the semantics of a PLANNER-like formalism on actors. The actor semantics have resulted In a number of improvements In PLASM A over Q..A-1, POPLER, and CONNIVER.

Programming Methodology

Actors make a contribution to the "declarative-procedure" controversy in that they subsume both the behavior or pure procedures [functions] and pure declaralives [data structures) as special cases. Discussions of the controversy that do not explicitly recognize the ability of actors to serve both functions may be doomed to sterility.

Actor semantics promotes a programming methodology which consists of the following activities:

Deciding on the natural kinds or objects to have In the domain.

Deciding for each kind of object what kind of messages it should receive.

Deciding for each kind or object what It should do when It rl'ceives each kind of message.

The above is a generalization or the programming methodology pioneered by SIMULA In which we have unified classes, procedures, and co-routines. Once the above decisions have been made, it should be possible to directly Implement the design directly without. circumlocutions.

!Jnlficntlon of Pattern-Directed Invocation

We do not want to have to explicitly store every piece of knowledge wh.ich we have but would like to be able to derive conclusions from what Is already known using procedures. The syntactic form (wht!n ... lry .. .) as in (111h11n !riner 1ry ~)or completely ~quivalently the syntactic form (lo ... 1ry ... ) as In (lo trill!!: ''.Y body) creates a plan [high level goal-oriented procedure] that can be invoked by pattern directed invocation by a trigger which matches lriccer. There Is a great deal or confusion in the literature about "demons". The phrase "completely equivalently" above Is meant to emphasize that there really is just one pattern directed invocation primitive. Implementing "antecedent" [working forward) plans entails facing the same issues as Implementing "consequent" [working backward] plans. These problems Involve doing rrtrieval, data base updates, and dealing with multiply applicable plans.

The following are kinds or plans which could be defined In tl'rms of the above general pattern directed Invocation machinery. Additional kinds of plans can be defined as they are needed with the user defining their semantics by writing procedures for the triggers and bodies.

(tn (lif!rttnn·tratf! ~.>.:polhesis) lry ~) (t""rn (nul!rlinK slalemenl) try body) (In (lii·ar.hif!vf! condition) try body) (t,/t.,n (dl!nyin, !_latemenl) try body) (to (rl!/ull! hypothesis) try body) (In (!inti description) try ~) (to (nl!ltirt'f' condition) try body)

(to (inmrntitttfl !lereotype) try body)

(to (ron/rant ··hypothesis ~~>1111 e·contredidory·hypothesil) try ~I

The process of invoking plans in worlds Is controlled by recommendations made at the site where 1 request Is made of the world to achieve a particular goal. We envisage that problem solving would begin in a world with an Initial class of plans. !!!. many cues most of the plans that are used In the ultimate solution of the problem need to be constructed by other plans during the problem solving process.

World Directed Invocation

World directed Invocation [Hewitt et. al. 1973, Stansfield 197S, Freuder 1975] Is Invocation of procedures on the basis of a fragment of a micro-world instead of a single assertion or goalu In previous PLANNER-like fo·malisms. It Is a generalir.alion of pattern directed invocation [Hewitt 1969) such that more than one assertion is taken into account In direcling the Invocation. We foresee that the further developmtnt of world directed Invocation and plans will play an important role in future development of PLANNER-like languages. Within the actor model of computation, the only way a piece of knowledge can be used Is for actors, which have the knowledge, to be smt messages which cause them to act on it. We foresee that programming d lstribution networks In worlds to handle world-directed Invocation will be important for effective modular distribution of knowledge. World directed Invocation Is still In a relatively undeveloped state by comparison with pattern directed Invocation which has been Implemented In many PLANNER-like languages.

An Important issue Is how to maintain control over the Invocation process. Two general mechanisms for this control are recommendations [Hewitt I.JCAI-69, I.JCAI-71] end clustering [Goldstein 1973, Stansfield 19~. Marcus 19751 Clustering is the technique of gathering together plans that have overlapping domains of applicability. Suppose we have two plans plen 1 and plen 2 :

(plenl ·

;plenl ia tlfl/innfl to 611 tilt! /ollollli"t

(lo (odif!tH! (·a i·-on ·b)) try ~~~))

(plan2 ·

;plan2 ia tlt!/int~tl to '" tlot~ /olloll>int

(to (oeltint~ (·a ia-on ·b)) try body 2 1)

Further suppose that if b has a clear top then plen 2 Is much better than plenl. We could cluster the two plans Into one as follows:

(plan 3 ·

(lo (odit!tJft (·· b-on ·b)) try

(flt!monJtroM (b lto·-o-dt!or-rop) (tllcn: ~~· (I' hi!:

bodrt)))J

One of the earlier and better examples of clusterinc Is found In Goldstein's design of geometry experts [each for a particular coal like congruence) which are responsible for choosing the best or at least the order of applying the plans for that goal.

An example of the use of a recomrMndation Is the following:

which attempts to achieve block X on block Y by first attempting to use plan 1 but if that doesn't work then using plen 2 .

Nested Continuation Control Structure

The u~e of nested "rltl!n:" and "cbn:" continuations as In the above example together with complaint-departments seems to solve the scoping control problem which had been plaguing PLANNER-like languages for some time. Sandewall [1973) and a revised version of Q..A-i independently developed nested continuation control structure for PLANNER-like languages. CONNIVER attempted to solve the scoplng control problem by Introducing possibility lists and Landln-style non-hierarchical gotos. However possibility lists proved to have several deficiencies. They introduced side-effects Into the basic communication mechanism between methods In CONNIVER which made it difficult for users to debug their programs since doing a lry·nod operation to print the next possibility destructively Interferes with the operation of the programs being debugged.

"7'/tl!ir [Sussman and McDermott) ·nlurion, to KiN tilt! .,.,, oee"'' to tltl! irnpll'rnt!nlttlion primiriw.· o/ PI.IJNN,.:R. i1 /toMlt!fH!f', anml'lltin· n/ n rl!lf'OKrttdt! Jlcp (tr>ltol orf! CONNIV,.;R', ll!mo.nlir.l?), nllltottlflt ,,a,mttlieally ull!/ul a"fl imporranl in tlut Jllort tf!fm, II ht!lll!r anlutinn i· 111 titH! 11111 u111r aeef!U to o '""o"in·/·1 lt!t o/ t>rimitivc rnntrol ohililit!· in on nplieit '"""'""todo,.ol trlterrto r.onr.l!rnrd .,;,, ll!!dur.litlfl control."

Hayes: "Some Problema end Non·P'roblema In Represenlelion Theory·

Nested continuation control structure gives us the ability to influence or control any decision to the extent we desire while still retaining the high level goal oriented nature of PLANNER. PLASM A is able to accomplish this by basing Its semantics on actor message passing and slightly changing the syntax of PLANNER-71. The change In syntax provides us with natural places to incorporate the control Information and enables us to avoid the gratuitous side effects In PLANNER-71.

In terms of the actor model of computation, control structure is simply a pattern of passin~ messages. CONNIVER represented a substantial advance over PLANNER-69 [implemented as MICRO-PLANNER by Sussman, Winograd, and Charniak) in increasing the generality of &oal-orlmted computations that can be performed. However this Increase In generality comes at the price of lowering the level of the language of problem solving. It forces users to think In low level implementation terms such as "possibillly lists" and "a.Jinb·. We propose a shift In the paradigm of problem solving to be one of a !Ociety of lndividua!s communluting ~ P!!!!!!.c. messages. Within this semantic paradigm PLASMA acts as a flexible transparent medium for expressing desired behaviors without forcing the user to always think In low level Implementation terms. It raises the level of problem solving while retaining the flexibility to control any decision by the medular addition of more knowledge.

Complaint Departments

The "generate and test" method of Newell and Simon Is a fundamental procedural schemata. An Intuitively appealing extension to the generate and test method Is to allow the consumer to talk back to the generator with complaints, advice, and encouragement. PLANNER-69 had a mechanism for attempting to do this [called "failure messages"] that was so clumsy as to be essentially unuseable. In a very nice piece of work, Scott Fahlman improved on this mechanism to construct an extremely sophisticated blocks world construction program. His Idea was to construct "gripe handlers" which communicate by making use of assagnments to the local variables of gripe handlers and Landln-style non-hierarchical gotos to transfer control. However, the gripe mechanism Is still awkward because of the necessity of side-effect~ng the handler which Introduces the possibility of gripes accadentally clobbering each other or gripers accidentally clobbering the variables of other procedures. The message passing semantics of actor control structure seems to provide a fairly elegant simple mechanism for customers to talk back to gener~tors. [The idea Is an adaptation of the stream concept of Landan.] The customer receives a complaint department alone with each new candidate produced by the gener.ltor. At a later point the customer can send a message to the complaint department that contains the complaint or advice plus any other actors that might be of use. These complaint departments are used In conjunction with the nested continuation control structure described above to help maintain the desired degree of control over the high level goal-oriented plans of PLASMA ..

Frames

Three Important frame meohanlsms are:

plans: as In PLANNER-like languages, Newton's square roo.t algorithm, Charnlak's supermarket plan, Hewitt's blrthdaJ party plan, Schank's restaurant plan, etc.

circumstantial situations: as In a frame or reference In physics, a McCarthy frame, the assassination or Kennedy, a motion picture frame, etc.

stereotypical situations: as In the definition of the concept of a chair, Minsky's room frame, etc.

?f course the above fuzzy classification does not Include many

amportant aspects of frames. However, as a matter of research strategy, we would like to Investigate how the above three framing mechanisms can co-exast In a single problem solving system. To this end we are Implementing a mechanism which we call a stereotype to enable us to use these three framing mechanisms simultaneously. The stereotype mechanism attempts to deal with only a small number of the Issues that have been raised by frames [1975 TINLAP pre-prints] as a "fromeworll for ropro1onlin6 .tcnoll>lod_.o· [Minsky 19741 Ry Implementing prototype systems using the stereotype mechanism, we hope to gradually discover how to bring the above frame mechanisms Into active cooperation. We define a stereotype to consist of the followlnst:

:r \.ullection of characteristic objeots

oharnctcristlo relations for those objects

a st't of plnns invoked by world directed Invocation for transforming the rt'lations It s~t"ms that many of the behaviors attributed to frames by Minsky can bt' rt'alizt'd by stereo:ypes. The characteristic objects of a stert'otype corrt'spond clmely to the slots of a Minsky frame and tht' characteristic relations or a stereotype correspond to the constraints of a Minsky frame. Minsky calls simple unary characteristic relations markers. Stereotypes communicate by making assertions in the data base and by world directed invocation.

We instantiate stereotypes somewhat differently from the way in which Minsky instantiates frames. Our approach Is to plug In ddinite c<~ndidates for all the characteristic objects of a strreotypt' that we can and use anonymous objects (1-ferbrand, Skolcm] for the rest. Defaults are done as assertions tagged to indicate that they are defaulted so that they can be easily displact'd if an anomaly denlops. Defaults as tags on assertions have an important advantage over the default values for the slots of a Minsky frame In that often a default relationship Is known bctwt'en two ob jccts of a stereotype even though no default value Is appropriate for either object. For example, there Is a default rt'lationship between the month or the date of the birthday party and the month of the birthday or the guest of honor. However, tht'rt' is no P.articular month which is a very good default value for t'ither. The use of anonymous objects In PLASMA enables us to rt'ason explicitly about various possibilltes using assertions and go<~ls in the data base without complicating Its Identifier binding mechanism. Previous PLANNER-like formalisms have placed the burden of doing the communication on the binding mechanism. This process of Instantiation Is closely related to the process of further specification emphasized by Newell and Moore In Merlin.

Situational Tags Instead of QA-4 Contexts

"II aitu11tinn s i· tho f'ompll'tl! Jllltl' of the unitH!nfl ol on imtont nf tirnto... Sinr.e tho unitlf'rlfl h tno lllr«ll for r.ompleto tltoarriptinn, 11·11 ahnll n111H!r r.ompl111t!ly rlear.rihe o aiauotion; ll>f! aholl only Rille fnr.ll nhnul ailunliona. ne1e {nell will be uaetl lo dedueo furtht'r f11r11 nhoul thnl aituation, about futurll ailu111iona onlf ohoul dtuntinr·· tlonl p<!nnn· can hrinR oboul from chal lituallon.

We Jlonll furlher t111um11 tloal lhl' l11w1 of motion lfe111rmine frnm !I aitu111ion nil fulure ai1u11tiona. irt.h aaaumption i· lliffir.ull In aquore wilh quanlum mer.hanica, and rrl111it1ily ~r.lla ua chal any nui~r11m11nt of aimulconl'ily In t'llrnu in differt!nl ploct!l ia nrhi1r11ry. II owerH!r, we ore prorl't'din< on 1h11 bruit chnl modltrrt 1·h.vair.a i· irrel11r>onl In r.nmmnn ar.nae tlr.ciflinR whal to do, anll ill pnrlir.ulnr i· frrt~lerH&nl 111 aolt~in< Jill! 'fret! will problt~m'.}" McCarthy and lloye1 1969

Although we shall use tags on assertions and goals to rt'lativize them to particular situations, hypotheses, and contt'xts, we do not want to make any of the global assumptions of McCarthy and Hayes. All of our situations will be local. For example, wht'never one situation precedes another, we shall allow for the possibility that there is a third distinct si·uation which Is neither before the former nor after the latter. For a discussion of the issues involved in this decision for the actor model of computation see Greif and Hewitt [1975].

Tht' followmg fuzzy categories are examples of circumst<~ntial situations: physical states, mental states, logical hypothrticals, hypotheses, view points, goal situations, prt'dictions, and .defaults. The following are some simple t'xamplt's of assertions that use such situational tags:

((A ia-on B) in ailu1tion1) (silu1lion1 ocew."e4-be/ore 1111-of·R.,_ ((A ia-lt~/1-o/ B) in view5l ((John btu 11061 in dre1"'7l ((Nixon b-innocent) in lllind-of·P·tl (-.(A h-on B) In 101l5l ((John b-ot home) on Jlnulry·1·1114)

PLASMA does not use the Q.A-1 context mechanism (Rulifson et. al. 1972): instead it uses explicit tags In assertions to keep track of the state of affairs in various situations. One problem with the usual use of the Q.A-1 context mechanism Is that the problem solver is forced to attempt to propagate all changes ·in the situation immediately on a frame shift since otherwise inconsistent information will be inherited from the previous situation. Another problem with the ~-i context mechanism is that it is somttimes difficult to reason explicitly about various situations using it because situations [frames) are not explicitly part of the assertions and goals.

For example consider two contexts such that in the first Neil Is standing on the earth and in the second he is standing on the moon. This can be accomplished using contexts by generating two new contexts [call them conlext4 and conlext 5 ] and then asserting (Neil i··arantlin11-on earth) with-respect-to conlext4 ~nd asserting (Neil i·-a1antlin11-on moon) with-respect-to conlext5. However, consider the assertion that the weight of Neil in the first context is greater than his weight in the second. This Is not an assertion that can be made with respect to either context alone. Instead it seems that it is necessary to incorporate tags for both contexts into the assertion.

Events that are viewed from several different viewpoints can be difficult to handle. For example, consider the problem faced by Miss Marple in solving a murder mystery which happened at a party attended by several guests. Each guest has a fairly coherent story to tell but [at least] one of them Is lying. Gerry. and Marilyn are two guem [considered by Miss Marple to be generally reliable] who witnessed the shooting. Gerry's description is contained in conlext7 whereas Marilyn's description is in conlexla. We would like to construct a new context which Inherits information from both these descriptions. However, In the Q.A·i context mechanism a sub-context Inherits assertions only from the one singlt context of which it Is an extension created by the push-context primitive. or course, there will be some s)ight discrepancies between Gerry's description and Marilyn's description even though both are "thoroughly reliable upstanding citizens". Methods for dealing with this problem are not well understood and will be discussed further later In the paper.

However, without the example of the Q.A-1 contexts to guide us, we could never have realized how to deal with these problems using situational tags. [The context mechanism In CONNIVER was modeled on the one In Q.A-1.]

It Is easy to see how the abilities of Q.A-1 contexts can be implemented using situational tags. As a first approximation In which erasing in contexts is not implemented, the following procedure will work.

(demonslr·le·in·contexl ·

(lo (tltlmOiulrall! (·sl·tement in ·conted)) lry (find (context inlot'riu-/rnm ··nolher-conlexl) (llol!n:

(dcmonalralc (st1lement in ·nolher·contexi)))))J

Ofttn in frame transitions, it is necessary to be able to make deductions in both directions across the transition. For example suppose that we are told the following Information:

"""'·" i11lorrill!tl on11 lountlrtltl lloouaon4 tlollor~ /rom loia IX''""" Jill ontl Jade 111loo tlictl autltlcnly ll!allinK 110 111ill. Tltttl··· rtiiJuirtl thai 1lo11 tl·lalc in aur.h r.tuea be tlit~itlf!tl f!IHinly omon6 tloe r.loiltlr11n.

We can derive the following Information for the Initial situation s:

((Henry h -alit,..) in s) (((Henry inltt'riu llOOK) from Jill·end·Jeck) in t) (-.(Jill·end-Jeck arc-nlilll!) in t) ((Jill··nd·J·ck ortl-parllnU-o/ Henry) in 1) ((Jill··nd·Jeck lc/t-na-ltlill) In a) Furthermore we need to know numerous rules such as the following: (111ht1n (naal!rlinK ((Jill··nd·Jeck ore-parenu-o/·penon) In a)) try (naat'rl ((peraon inlollriu llOOK) /rom Jill··nd·Jeck) In a)) (V (·> (·p "11 "52) (implitla '" ((p ia-olitH!) in a 2 ) (s2 ia-o/ll!r a1 ia-o/ter (birth p))) ((p ia-alit~t~) in a 1 ))))

Tht1 nrs-1 tiny, lfcnry m111 hh o14er lorotltttr P··l (111loo b -~ mial!rly/ in l'iml!a Squartt.

((Henry looa-brother P1ul) in a') ((Paul 11-oliw) In e') (a' u (1 4oy) loter-1loo11 1) (P1ul 11-/rutoll U·1· P1ul) > (·&· He~y))

From the above circumstances we can draw some reasonable hypothetical conclusions. Certain new Information can be derived about s from ·'·

(((Peul inlol!riu llOOK) /rom Jill··nd·Jeck) in 1) UP1ul ia-olitJr) In siUill··nd·Jeck ere-parenu-o/ P·ull in a)

Now, additional information can be derived about a' from 1.

UP1ul ha· I lOOK) i11 a')

Notice how in this example information has migrated back and forth between · and ·' in both directions.

The Blocks World

The blocks world has proved to be one of the most fruitful micro-worlds for research in artificial intelligence. It motivated

the introduction of a large number of the Important features of PLANNER-69 [MICRO-PLANNER] which was used to good advantage by Terry Winograd as an convenient high level goal onented procedural formalism in which to translate natural language. The following are simple properties of the blocks world expressed in the quantificational calculus. In order to be effectively and efficiently used for many purposes this knowledge needs to be procedurally embrdded in various plans.

Oi1~ of the miljor aims of th~ Programming Apprmtice Project Is to scrutinize the relationships and d~pendmcies engendered by these embl'ddings.

[definition-of·has-a-cleu-top 1 (V (·> [=x ·.s] (iff ((x luu-a-dear-lop) in a) ;for all s anl 1 ;s luu a dear lop in 1i1ua1ion 1 if and only if ~ ~~ (x i· the-table) ;t: i1 the I able or (-. ((J (·> [·y] ((y il-on x) in a))) in a))))))] ;it i· not thn ca1n rhal there i· ·ome y on s in 1i1ualion 1 [is·on·implies·is-above 1 (V (1> [·x ·y ·s] (im,,r;.,, ((x b-on y) in s) ((x i·-oboiHI y) in s))))] [transitivity-of-above 1 (V (·> [ ·x ·y ·z ·s] (implie· (I\ ((x il-obovc y) in s) ((y il-abotlfl z) in s)) ((x il-abotH! ;r) in s))))] [above-is-not-reflexive 1 ;for all s, y, anl 1 ;if s il on y 1he11 ;s il abotlfl y ;for all s, y, 1, and 1 ;if ;s i· abotlfl y anl ;y h abotHI 1 ;1 he11 s il aiJotlfl · (V (1) [ ·x ·s] ;for all s anl 1 ((-. (x b-ahotH! x)) in a)))] ;il b nol 1h11 ctue thai s b abotHI luel/

Planning

We have found it useful to Incorporate two types of worlds c<~lled utopia [desired situation] and reality [achieved situation) In every problem solving situation. Our desire Is to Incorporate PLANNING Into problem solving using "islands" (Minsky 1963) as stepping stones. The utopia of one problem solving situation Is tilken as the reality of another. Sometimes working f._orward from what Is known toward the goal Is a good strategy. Sometimes working backward from the goal Is a good strategy. Usuillly il combiniltlon of both Is best.

"It u:ill bc u·orrh a relatively nnormou· effort lo find 1ur.h 'island·' in lloe 1o1l111ion of r.omplcs problt!ml. Nore tloal l!tll!n if on11 cnr.ounlcrctl, 111y, 10 6 failure· of aur.h pror.ctlurtta bcfortt '"""""· "''" 11:ould alill """" ~rained n fnr.tor of pcrhap1 10 10 in otlf!r-all lrinl rctlur.lion! ?_'hu1 prar.lir.nlly any abilily al all In 'plttn,' or 'nnnly:rt!,' n problcrn tl'ill be pro/itablt! 1 if thfl problt!m i· diffir.ull." Atart·in Atinllry in "Sit!pl Toii!Orll /Jrti/ir.inl lnll!llillencf!"

An islilnd is a problem solving situation for which It Is not known whether it is achievable from reality or whether utopia c<~n be achievl'd from It; but there is reason to hope that both are in fact possible. It might be imagined that such islands are extremely difficult to find. But as Gerry Sussman hu polnted out; such Islands are proposed all the time In PLANNER-like formillisms. In order to demonstrate that a block x Is above il not her block z, it is suH icient to demonstrate that there Is a block y such that x is above y and y Is above :r.

(demonstrate-is-above 1 ;tle[int! '"" plan demonslrale-ia·above aa follo1111

(lo (tlcnronllrolc (·x i·-obotltt ·r) in ·u frnm ·r) (tlt!motulrnle ((x i·-alootHI ·y) in ·s from r) (llocn: (tlemon11ro1e ((y i·-ahovc :r) in u from s))))))

The pli!n demonstrate-is-above attempts to find an Island 1 with a demonstrated y is above z. We will explain more sophisticated forms of island construction in examples given later In the paper.

block y such that it Is known that x is above y and It can be The following ilre examples or convenient plans for use In our blocks world that procedurally embed some of the above knowledge: (achieve·clear·top · ;lhe ,,tan achieve-clur·lop i1 llefinell 10 h: (lo (nr.hicvc: (·x ha·-o-clt!ar-lop) in ·u /rom ·r) ;to ""hit>Vt' lloal :1r h111 a clettr top in utopia u from reality r lry (either ;t!JII··r (tlcmonllrnlfl ((x i· the-table) in u) ;tlcmon~lrale thai :1r ia lhfl 1tthl11 in u (tli·nrhic11e ;or lfiaar.hit>tHI (J (·> (·y) ;lhol thcrfl i· 1ome bloclr y 1uch thai (y i·-on x)))))))) ;y i· on s [disachieve-on 1 ;rht> plan diuchieve-on i· define~. to be: (lo (tli·achittlltl (·x h-on ·y) in ·u from ·r) try ;1o ar.hiniHI s il nnl on y in uropio u /rom reality r (ttr.hict·t' ((x hoa-a-deor-lop) in ·r' from r) (I hen: (nchitoiH! ((x il-on (not y)) in u from r')))))J ;ttchicve s- bcin11 on 1ome olljer.l 111hfch ia nol y [ echieve·on 1 (lo (ochitoJJc (ex i1-on ·y) in ·l! frnm ·r) try (nr.hir.tJI! ((I\ (x hn·-a-c/ear-lop) (y lttta-a-dr.ttr-lop)) in ·r' from r) ''"""' (,,.,, x on y rl!luhin~r-in u from r'))))) [ '''"' ·x on ·y rc·uhin~r-in ·u from ·r) 1 (tlemorulrale (I\ .,,..., s on y re1uhin11 in u /rom r i1 le/inel 10 6e: ((x hn·-a-clcar-lop) in r) ((y httl-a-clcar-lop) in r)) (I hem (nur.rl (I\ (u rc·ulu-/rom (pul x on yin r)) ((x i·-on y) in u) ((x hn·-a-dcar-lop) in u) (.., ((y hna-o-r./r.ar-lop) in u))))))] Constraint Analysis The linear strategy for achieving a conjunct (1\ conjunct 1 ... conjunclk)

is to allempt achiev·e [and pro!ect] each conjunct In turn In the ord~r which they are present~d . If this runs Into a protection violation, an auempt is made [on th~ basis of th~ kind of violation] to reorder the conjuncts and continue as ~fore. Th~ problem givf'n bf'low was invented by Allen Brown as an example of a simple blocks world probl~m that cannot ~ solnd using the "linf'ar" sllategy without backtracking trying first one conjunct first then the other. We present this as a very simple Illustration of how planning using "islands" can help keep the problem solvin~ constrained and avoid search. None of this Is rMant as a criticism of Sussman who designed and partly Implemented a r~ally interesting problem solving system. His work Inspired us to further develop the constraint analysis approach which Is a variant of the "means-ends" analysis used by Newell and Simon. The in ilia I situation [reality J r Is It h very desireable for usertions about utopia [the goal situations] u well a., rrality [Chr ar.hievrd situations] Co be txplicitly placed In thr data bue so u to br rudily available to platu workjng forwards and backwards. Among other things, this implements a version of "continuously available output from processes" which has been advocated by Bobrow and Norman.

Solution Working Backwards from Utopia

Constraint analysis can be used to straightforwardly solve the Brown blocks world problem as follows. Clearly, the Initial state Is not a solution to thr problem, [i .e. u Is not r) because ((C ia-tlflot·t! A) in r) is incompatible with ((A i·-allotlf! C) fn u). The easiest way to solve the problem is by working backwards from utopia u doing constraint analysis. Constraint Analysis Is a planning technique in which abstract reasoning is used to derive the necessary structure of the possible solutions to a problem. !!!, working backwards (rom a situation, attrmpt to eliminate the constraints that don't hold In reality. If utopia u is to ~achieved from a previous state u 1 , it must be that the following holds about ur

(u rNulu-/rom lt>ul A on Bin u1)) ((A htu-o-r.lrnr-lnp) in u) ((B h-on C) in u1) ((-. (8 ia·nllot·r A)) in u1) 0 ~ ((-. (C ia·nl1ot>r A)) in u 1 ) A ((A hn·-n-df'nr-lt>/1) in u1) ((B lonJ-o-r.lrnr-lnp) in u1)

Again it Is easy to see that the problem is not solved [ul Is not r). If utopia u1 is to be achieved from a previous state u 2 , It must~

(u1 rra11lU·/rnm ltml 8 011 C in u2)) ((-. (C h ·ol>t>l·f' A)) in u 2 l ((-. (C ia-ol>nt·r B)) in u2l ((8 hn··n·rlrnr·lt>/1) i11 112) ((C l~t~a·n· rlrnr·lt>t>l i11 112)

that the followin~ holds about u 2 :

The problem is still not solved for the same reason. [Note that u2 must have been obtained from some previous situation UJ by moving C since this Is the only way to eliminate the constraint that It is not the case that C Is above A.]

(u2 rNulu·/rom lt·ul Con new·support·for-c in UJl) · [c J ((C ia·nn !'ew·supporl-for·C) in ~2) ((C llna·o-drnr-lnt>l in u3l

where new·support-for·C Is some position. Notice how limited and abstract the knowledge of utopi" u 3 has become In the course of abstractly planning backwards. Now It seems possible that u3 might be r. So create a new hypothesis h.

((u 3 · r) irt h) ((!:'Gw·support-for·C I A) in h) ((new·support·for-C I B) in h) ((new·supporl·for·C I C) in h) ;ainr.e -.((C 1·-···~~~~ A) In u2) ;·lnt:e .. ((c b-·""" I) In uz>

;dne11 you COII 1 1 ptll ltlllllllhinlf on fUel/

Having nothing else to choose for new·aupporl·tor-c. choose the table:

((new·supporHor·C · the-table) f11 h)

Now reason forward from r u'sing the plan constructed by reasoning backwards from u. The first step Is to construct a world r 1 from r:

(r1 rNu/u-/rnm (11u1 Con the·l·bl· In r)) ((u 2 · r 1 ) in h) ((Cia-on the·t·ble) in r1l ~ ((8 i·-on the·l·ble) in r1) ~ l I _IA.w ((A ia-onlhe·table) i11 r1l lc"1 8 r-;-J ((A lltJJ·n-r.f,.or-lnp) in r1l _L:J ____ __. __ _._ __ .._JtU_A....;.........&.. ((8 hn·-o-dl'nr-lop) in r1) ((C hna-tJ-dt!llr-lop) in '1)

Everything se-ems to be going well, so attempt the next step In the tentative plan which Involves generating a world r 2 from· r 1 :

(r2 rl'au/u-/rnm lt>UI 8 on C In '1)) ((u 1 · '2) in h) ((C ia-on lhe·l·blo) in r2l ((A ia-on the·l·ble) in r2l ((8 ia-oll C) in r2l Cr3 rrau/u-/rom (pul A 011 I ill r2ll ((u · r 3 ) in h) ((B ia-on C) in r3l ((A h-on B) in r3l We have achieved our goal in r3: ((A (A h -on B) (B i·-on C)) in r3) The hypothesis h has led to the followint plan for solving the problem: (,,fnr." (C on the·l·ble) (lht!n: lt·lnr.r (8 on C) (lhrn: (11/nr.r (A en I))))))

The above ~olution can be variabalized uslnc procedural' abstraction [Hewitt 1971; Sussman 1973) into a procedure as follows:

[to-a~hieve·three·ctack1 · ,,.,_,,.,;,.,>~! ((/\ (·x i·-nn ·y) (·y i·-on ·z)) lry /n·m (·r rnnrninin, {(z hn·-o-clt'nr-lnp) (y htu-o-cltoor-lop) (z i·-on x)})) Ct>larc (z on the-table) ''''"'" Ct>larc (y on z) """": Ct>larc (x on y))))))))

Notice that in the above example that the plan to·achieve·three·llack 1 which we generated does not have as pre-requisites the following irrelevant Incidental features of the original problem specification: (x h-on the-table) and (y i·-on the-table) . The reason is that the above features are never rrlied upon in the symbolic evaluation of the plan solution.

Working Backwards then Forwards

We would like to consider the problem of realizing the ~ utopia u from a different Initial situation 1 deKrlbed below:

((0 i·-on the-table) in 1)

((A i.-on 8) in 1)

((B i··on the-table) in 1) ~

((A htu-o-dtoor-lnt·l in 1) B

/JL t":=-1

((C i·-on the-table) in s) I pA I ll5l ...(M..oo

((C ho·-o-dtoor-lnp) in 1) -.!..~IL.-!. __ _!. _ _::_.J__.....l.u-.J~~.L

The analysis proceeds much as before In terms of generating utopia u 1

(u rto·uha-/rnm Ctntl A on Bin u1))

((A hna-o-d,.or-rnp) in u1)

((B h-nn C) in u 1 )

((-. (B h-nhotll! A)) in u1)

((., (C h-olrnt·l! A)) in u1)

((A hna-o-dt!or-rnp) in u1)

((B hoa-o-dtoor-lnp) In u1) ·

utopia u 1

and then utopia uz.

(ul rt!aulu-/rnm Ct·ul Bon C in uz))

( (((., ((CC ~~-n,hot·to BA)))) ~n uz)l

., U-n Ollf!

rn Uz

((B hna-o-dtonr-l,p) in uz)

((C hna-o-dtoor-r,p) in uz)

1..,_/S 1

utopia u 2

Comparing the new utopia with the original reality s, it Is not obvious how to further constrain the structure of the solution. However, notice that u 2 is compatible with 1 exc~pt that B must have a clear top in u., whereas A Is on B In 1. Thus there Is a potentiality that uz can be reached from s by clearing the top of B In s to produce a new situation s 1 . In working forwards from a situation, attempt to satisfy the constraints that hold In utopia. In order to do this A must be put some place which we shall denote by new-support-lor-A.

(sl rtoaulu-/r"m Ct>ul A on new·supporl·for·A)) ((A ia·n11 !:!Ow·support·for·A) in 11) ((B ia-oll the·lable) in '1) ((C ia-nn lhe·lable) in 11) ~ ((A lrna-o-dtonr-lnp) in 11) rp;1 ((B hoa-o-dl!or-lnp) in ·1l l!!J There are no readily discernible lncompatlbilltes between u 2 and s 1, so cr·cate a hypothesis k as follows: We Immediately conclude: ((C hna-a-dtonr-lnp) in '1) ((now·supporl·for·A I C) in k) ((new·supporl·for·A I A) in k) ((new·supporl·for·A I B) in k) ;linr.n ((C luu-e-eleer-lop) In uz) Our hypothesis k gives us a tentative plan to be debugged. We first generate situation '2 from 11- I~ I m (sz rl!·ulu-/r"m (pur Bon C in ·zll ..@l..W_ ((ul · sz) ill k) (s3 rl'aulu-/rom ''*' A on 8 in 1z)) ((u · 13) in k) ((A i·-on B) in IJ) ((B i·-on C) In 13) [l5] Thus the hypothesis k has led to a plan for solving the problem: (,,tarn (A 011 (nnd (nol A) (nor B) (nol C))) (rhr.n: Ct>lar.n (B on C) (rhnn: (,,lace (A on 8)))))) Again by procedural abstraction we have: [to·achieve·lhree·llackz · (lo-or.hinf}(! ((1\ (·x b-on ·y) (·y 11-on ·z)) lry /rom (·r r.nnroinln, {(z hoa-e-elt~or-lop) (x hoa-o-elner-lop) (x b-on y)J)) (plat:n (11 on (nnd (nol x) (nol y) (nol z))) (rhnn: (trlor.r. (y on z) (lhnn: Ct·lor.e (x on y))))))))

A rrally interesting area for future research Is how to recognize that both the plans lo·achieve·lhreo~·slack 1 and to·achieve-three·slack 2 are instances of the more general plan "llrrild n .rnrk /rom lhl! """om uti. An important research aru for the future is that of Integrating plans using clustering, nriabalization, and othrr yet to be discovered techniques.

Predicate Logic as Programming Language

In this paper we oppose t!le thesis that "prt!dir.olt! lo,ir. h a u·t!/ul nnd t>ror.rir.ol, hi,h-ltolll!l, non-dl!ll!rmini·rir. pro,rommin, '""If"" 1ft' tdrh ·nund lhtonrl!lirnl /nundttliona" [Robert Kowalski In

"Predicate logic as Programming lan~u·.:e"l The deficiencies of ~I!!: ... J!!t'liicatt- cakuhu :u a programming language art tractd !,lad to the iruth-throrttic [Tanld 1930] mnantics of logic. The nub of the difficulty srems to be the way In which meaning 15 defined; in that axioms may convry truth but not pragmatic information. We explain how tht brhavioral semantics alleviate some of the difficulties with truth·throretic srmantics. This work i~ presented u~ing ~ctors, a semantic concept in which no active process is ever allowed to treat anything as an ob jec:t; Instead a pohte request must be extended to accomplish what Is

desired .

~ecessity of a Unified Formalism

For some years now we have been working to achieve the goal of a unified formalism and semantics for knowledge based systems. The record of our progress is published In the Proceedings of the International Joint Conferences on Artificial Intelligence beginning with the first conference In 1969. In the course of this research we have developed the Thesis of Procedural Embedding of Knowledge: The U5eful knowledge of a domain i5 intrimically bound up with the specialized procedures for its use. An important corollary Is that the fundamental technique for the reprrsrntation of knowledge Is Procedural J<nowledge Bast Construction.

"Mflrt! Jt>t·ci/irally: I tl'i/1 nr~u~ lhnl rompulalion i1 b~ll rnf(artlt!d n· n l>rou·· n/ rnnlroll~tl tl~tlurlion . II "'ill "" /urlfoer arf(ut!tl tlonl lhn 1wo oApl!rU (A/>~ci/yin~ lhn ronlrol rncrloaniam) af prOf(rornminf( nrc I>~·· ·~l"'rolttl ~rplidlly, a· 1h11 lrintla of lanifUOifC irwoh·~d hnt·c quite diuirorl ·~mnruir·."

Pal Hayes: "Computation and Deduction"

A satisfactory theory for tht rrpresentation of knowledge should have Q'!!: unified totally intrgrated formalism and semantics. For example we should not have ont formalism and semantics for rxpressing declaratives and a ~eparate (as proposed by Hayes) formalism and semc,ntics for expressing procedures. Having two formalisms (with different semantics) erects an arbitrary pernicious barrier between two ends of a useful continuum. One technique which shows great promise toward automating the development of procedural knowledge base acquisition is that of Progressive Refinemrnt of Plans (Dijkstra; Wirth 1971; Cheatham and Wegbreit 1973; Hewitt 1971, 1975]. This technique involvts the transition from very high-level goal-oriented procedures to more particular efficient implemtntations for special circumstances. As such it spans the spectrum from relatively domain-independent goal-oriented (declarative?] modes of computation to particular efficient (procedura P) modes. The facility with which Progressive Rtfinem('nt of Plans can be automated depends on having ~ formalism and srmantics to span the above spectrt.m.

Problems with Truth-Theo1·etlc Semantics

"!'for !nr~kinro !!:"'"'"ir 1/otnry '!/_ I'C (predicate calculus) nnd iu !!lnlitlf'J ~ !}~ !!.'!!..!. /lrf'ri~l! tlrttlulll ~ lontlC ~ loolll !!, /oncutJctt ~ r~[rr!.!!. ~·· rrnlingui·lir rnririn"

Pal Hayes: "Computation and Deduction"

The definition of raUTH as formalized by Tarskl for the quantificational calculus is one of the crowning achievements of mathematical logic. It has clarified the semantics of ordinary mathematical theorems and led to the developmt'nt of truth-theoretic model theory which is a flourishing mathematical field in its own right . We contend that it Is less satisfactory as a sem.-ntic base for a tgeory of ;~ction and change. Tarsklan semantics characterizes predicate logic in the following sense: Godcl proved that for the first order quantiflcational calculus that the class of sentences deducible by the classical laws of logic is exactly the same as the ones which are true by Tarskl's definition. The notion of truth formalized by Tarskl Is very smooth but we contend that it glosses over semahtlc distinctions that are cruc1al to the development of knowledge·based systems.

The deductions of plans in a PLANNER-like formalism have the potential to carry more conviction (in the sense of Richard Weyhrauch and other logiciansl than proofs in the classical predicate logic. (For example a proof of a formula of the form <4> im,,li .. · 'IJI) carries conviction if It demonstrates a "causal" connection from cl> to 'IJI.) This is because our minds are better <~t grasping constructive relationships between plans than global relationships established by asserting that a class of axioms is true or consistent. Two plans can affect each other only If there is a behavioral causal connection of "wheels and. cogs". We seem to be able to design, control, and debug plans better than axioms.

In the real world no formal principle !! universally literally ~· An0ul;~an be stretched beyond its range of applicability to produce contradiCtions. Except in mathematics all useful principles are hemmed in with !JUalifications, hedges, and ~· 1\ now ledge is better expressed procedurally In the form of !._ough-minded skeptical plans that actively attempt to guard against their misuse. The business of actively searching out hidden anomalous situations is as important as the business of making deductions that carry conviction. Indeed, much of the conviction carried by a set of plans is dependent on their ability to withstand repeated, meticulous, rigorous attempts at refutation from as many dirtctions of attack as can be conceived. No principles (mcluding the classical laws of logic] are sacred against criticism when anomalies are detected.

No satisfactory method for testing the consistency of non-trivial sets of axioms in the quantificational calculus has brcn devtloped. For E'Xample inconsistent formulations or the "Blind Hand Problem" (a particular toy robot problem] have been produced in the quantiflcational calculus. Their inconsiStency has been discovtrt'd almost by accident as proofs by contradiction get short('r and shorter until the negation of the desired consequence is found to be superfluous to the proof! People are quite tolerant of minor inconsistencies. The inability of the quantificational calculus to tolerate any inconsistt'ncy ~ !.!.! in formulating problems is a sir,n of excessive semantic ~· An example of the kind of problem engendered by this rigidity when dealing with common sr.nse knowledge is given below. In general we feel that a contradictiOn is evidence for a ~in one's plans or world model and that to satisfactorily resolve the bug, It may be necessary to examine !.!.! the assumptions being made Instead of onty rne most recent one. \..urrenuy lntrt ar~ uu guuu wdp ·u debug classes of axioms, whereas there is a well established and rapidly dtveloping technology for debugging procedures (Minsky and Papert 1972; Sussman 1971; Goldstein 1971; Hewitt and Smith 197!1).

~ehnviornl Semantics for Logic

'Tn d~f~ml /irar -nrdrr lnf(ir i· uro/tuhioronhl~: hotlll'l·~r. I dn wnnl In ,.,.,,,,,~j : ~ rlonl il i· llo~ ~rmnrolirt n/ l""tlirnltt ln~rlr wloirlo I td1h In l"r.crn'r."

Hayes: "Some Problems and Non-Problems in Representat ion Theory"

We agrte with the above comment of Hayes (except that we have a different notion of semantics for the ~nguage of the predicate c:~lculus). The way in which the rul~s of natural deduction follow from the procedural mechanisms of PLASMA, demonstrates how deduction can usefully be considered to be a ~pecial case of computation. Furthermore, by implementing the usdul part of the behavior of the quantiflcational calculus In PLASM A, we will obtain a behavioral semantics of the quantificational calculus from the underlying actor semantics of PLASM A. Consider a formula of the form Vx.t[x) which means th:~t for every x we have th:~t 4·[x) is the use. The procedural meaning of the formula consists of plans for how It can be used. The plans we are attempting to develop for V and the other logical operators are reminiscent of natural deduction except that we have four introduction and elimination rules [demonstrate, refute, assert, and deny) to give us more flexibility In dealing with negation. An example is the following plan:

[to-demonstrate-a-V · ;th" t>lan lo-demonslrate·a-V i· dt!/inml 10 be (to (dt!mnrulrnlt! (V ·41) in ·u frnm ·r) lry ;to rl~mnrulralt! (V 41) in in ulot>ia u /rom rMiily r lry (1,1 ;lei ([g · (anonymous-object-in r)JI ;~ ht! on oru1nymou· ohjccl in r (dt!mnn·traln ((~ &) in u frnm r))))) ;nllr.mpl 1a J,mon.,rolt! 41 of~ in u /rom r

In addition we include the nonlogical operators echieve and · di~achieve to give us similar flexibility in dealing with state changes. The following plan is an example:

[to-diuchieve-a-V · (to (di·adoi"''" (V ·~) in ·u frnm ·r) lry ;In lraru/orrn rralily r ·o 1h111 (V ~) dol'· nol hold in ulopio 11 (di·orloit't>c ((,Z, (E (objects u))) in u /rom r)))] ;nllcmpl In di~nrhicvtt to/ aomn objt!r.l in u /rom r

Our intent in attempting to formulate plans like the above Is to try to characterize the useful behavior of V, 3, v, 11, impliec, and ... We do ~c:>!. intend for them to be used as the code to define a genera I unaf orm proof procedure. Instead they are Intended to be mcd a~ template schemata in progressive refinement to construct more ~ptcialized domain dtptndent plans. The classical rules of lor,ic are intent;led to generate all the true sentences from a given class of true srntences. Our behavioral definitions are intended to define the justifiable behavior of the logiul operators that ~i'rries conviction.

garbage in--Garbage out

In the quantificational ulculus from a sentence of the form (11 ~ (-. ~)), every statement Is deducible no matter how nonsensical' The following plan schemata realizes this behavior · [:~!though in our view this behavior Is usually quite harmful}

(gico · (In (dt'mnn·lrnln (·~ in ·u /rom ·r)) lry (dt'mnrulrllll! ((1\ ·~ (-.·~))in u from r)))]

!.nconsistcncics in Common Sense Knowledge

"/Ill qttt'Aiinrr· r.onufllin~ /o~ir.n/ implirotion in /irll ordr.r ln~tir rnn ''" rl't>lnrt'd by qur..,ion· ronr.l!rnin~ un·ali·/inbilily of ·t'rtlt'rtrr.· in ('/ntuo/ form."

Robert Kowalski: "Predicate Lo,ic as Pro,rammin' l·ncu·,·"

The ci&O plan graphically illustrates a fundamental problem with lhe truth-theoretic semantics for the predicate calculus. The presence of the 'ico rule in the quantificational calculus casts a shadow of doubt on the reliabtlity of all of the computations of the system. For example the following set of assertions (McDermott 1973) is not consistent. llowever, a problem solving ~ystem should not be able to conclude that 1+1 · 3 from the inconsistency!

(birds fly) (robins c birds) (ostriches c birds) (Fred /it,ttl·in the-zoo) (robins //y) (Fred tlor..,r'l-//y) (ostriches dorr'l-/ly) (pencuins c birds) (pen.:uins n~vcr-ar~ robins) (penr.uins dnrr'l·//y) (pencuins nr.lll!r·nre ostriches) (the-zoo i··/or.olttd-in Sydney) (Fred ( birds)

A more reasonable conclusion is that Fred might be an ostrich or a penguin. We feel that this problem of inconsistency is ripe for further research along the lines of McDermott [1973), Sussman (1974), Goldstein [1971). Kuipers (19711. Rubin (1975). Smith and Hewitt [1975), Erman and Lesser (1975), and McLennan [1975).

Every rlubitable usertion in the rlata base needs to have t'xplicitly recorded exactly which rules and asser!Jons were used in its derivations. When an anomaly Is detected particular specialized diagnosing routines must be Invoked to deal with the confrontation.

lndireot Proof

Indirect proof is often a very useful technique In problem solving. The classical natural deduction rule for Indirect proof takes the following form:

[indirect-proof · (to (dcmorulrolr. ((-. ·t) in ·u /rom ·r)) lry (/I! I ([r' · (exlension-for-contndiction r)]l (nut'rl 14> in r') (t/ot'll: (tll!lrttrrulroll! ((11 ·~ (-. ·~)) in r')))))))

However, it is easy to generate 'ico using classical·negation and indirect proof. We are working to develop a more limited form of indirect proof in which the contradiction must depend In an essential way on the hypothesis being refuted. The behavioral semantics of tf.,,,t'ndin~t·on ·needs to be carefully worked out to produce a deduction system that more nearly captures the logicians' notion of conviction as discussed above. Again a key technique for attacking the problem is to explicitly record for every assertion the rules and hypotheses used In Its derivations.

Further Work

The PLASM A system described in this paper Is currently being implemented at the MIT Artificial Intelligence Laboratory. The best version which currently runs was coded In LISP by Howie Shrobe. A better humanly engineered version has been designed and coded by Carl Hewitt in PLASM A with the extensive aid of Marilyn McLennan. The nt'w implementation has been translated into LISP by the members of a st'minar this spring with the following participants: Russ Atkinson, Mike Freiling, Kt'nneth Kahn, Marilyn McLennan, Keith Nishihara, Howie Shrobe, Kathy Van Sant, and Akl Yonezawa . The translation was made possible by LISP macros written by Russ Atkinson which makes the LISP code of the Implementation closely resemble the PLASM A which it Implements. A rough draft of a primer by Brian Smith and Carl Hewitt for the new Implementation exists.

Next fall the Implementation will be used as a basis on which to build the higher level problem solving mechanisms described in this paper in order to implement some knowledge-based problem solving systems. One project is the implementation of a Programming Apprentice. The emphasis thus far in the projt'ct has been the elucidation and formalization of the semantic principles involved. Procedures for analysis have been chosen for their ability to illustrate particularly difficult semantic problems. Examples that have been analyzed are pure queues [Hewitt and Smith). hash tables [Rich and Shrobe). Impure queues [Yonezawa], and various versions of the re<tders·wrilers problem [Greif]. Each of these' examples Is about one p<t~e of code in a high level language. But it takes an aver<tge progr<tmmcr a half hour or so to really ·mderstand each one if it is bein~ encountered for the first time. We would like to continue this approach by analyzing even more difficult examples such as the dtsk directory system of a time-sharing system and the Steele·Dijkstra parallel garba~e collection <tlgorilhm. However, In addition we plan to take a larger system consisting of about ten or fifteen pages or code in order to test our techniques on whole systems. In this regard, following a suggestion of Michael Dertouzos, we plan to try the programming apprentice on a bud~etary assistant program that aids in the construction and balancing of budgets.

Acknowledgements

This paper is a greatly elabor<tted written version of a talk delivered at the "Special Session on Formalisms for Artificial Intelligence" at IJCAJ-73 at Stanford in August 1973. The research rt'ported in this paper was sponsored by the MIT Artificial Intelligence and Laboratory and Project MAC under the sponsorship of the Office of Naval Research.

Writing this paper would not have been possible without extensive convtrsations with Richard Weyhrauch. Candy Bullwlnkle, Kenneth Kahn, Marilyn McLtnnan, Keith Nishihara, and Guy Steele made helpful comments and criticisms which considerably improved the intelligibility of this paper. Mitch Marcus suggested an improved Iitle for the paper and also made very helpful suggestions. Conversations with Allen Brown, Martin van Emden, Pat Hayes, Bob Kowalski, Marvin Minsky, /\lien Newell, Earl Sacerdoti, Gerry Sussman, and Richard Waldin~er have proved to be of great value in writing this paper. Although this paper has emphasized the deficiencies of truth-theoretic semantics for knowled~e-based programming, we have learned a great deal from studying systems for attempting to use predtcate lor;ic as a problem solvin~ formalism and interacting with the implementors of such systems. Ira Goldstein, Howle Shrobe, and Gerry Sussman contributed valuable suggestions and criticisms on how to clarify the 'oals of this paper.

~ibliogrnphy

Davies, D. J. M. "POPLER: A P'OP'-2 PLANNER" MIP'·It. Sc'-1 ef A·l. University of Edinburr;h.

Davies, D. J. M. "Representin& Ne&alion in a P'LANNER System" Proceedinr;s ef AISB Cenference. July, 1 !f74. Sussex.

Erman, L. and Lesser, V. "A Multi-Level Or&anizetlon for Proltlem Solvin& Usinc Many, Diverse, Cooperetin& Sources ef ICnowled&·· CMU. March, 1975.

r.hlman, S. "A Planninc System for Robot Constructien Taskl" M.I.T. AJ. TR-283. Ma~ 1973.

Freuder, E. "Sucttestion end Advice" M.t.T. A.l. Vision Flash 43. March, 1973.

Greif, I. "Semantics of Communicalin& Parallel Processes" Ph.ll .. M.I.T. September, 1975.

Greif, I. end Hewitt, C. "Actor Semantics ol PLANNER-73" Preceedina· of ACM SIGPLAN·SIGACT Conlerence. January, 1975.

Goldstein, I. "Elementary Geometry Theorem Provine" M.I.T. A.l. t.Aemo 280. April, 1973.

Goldstein, I. P. "Underslandinc Simple Picture Procrams" l"roceHinc·

of AISB. Sussex. July, 1974.

Hayes, P. J. "Computation and Deduction" Proc. W'CS Sympesium. Czech. Academy of Sciences. 1973.

Hayes, P. J. "Somo Problems .~nd Non-Problems in Representetion Theory" Proceedintts of AISB. Sussex. July, I 974.

Hewitt, C. "PLANNER: A Lancuac· lor Manipulatin& Models elllll l"rovin& Theorems in a Robot" IJCAI-59. Washin&lon, D. C.

Hewitt, C. "Procedure! Embeddina of ICnowted&· In PLANNER" IJCAI-71. London. Sept, 1971 .

Hewitt, C. "Procedural Sem1nlics" in N1lural lan&UI&e P'roce11ina Cour~nt Computer Science Symposium 8. Al&orithmics P're11. 1971.

Hewitt, C. et. al. "A Univers1l Modular ACTOR Form1tism" IJCAI-73. Stanford. Auc, 1973.

Hewitt, C. and Smith, B. "Towards 1 Pro&rammin& Apprentice" IEEE Journal ol Software En&ineerinc. March, 1975.

Hewitt, C. "STEREOTYPES IS 1n ACTOR Approach Tow1rd Solvin& the Problem of Procedur1l Atl1chment in FRAME Theorlet" TINLAP Pre-prints. June 10·13, 1975. M.I.T.

ICow·lski, R. "Predic1te C1lculus 11 Procramminc L1n1U11·" IFII"·74. Vol. 3. pp. 569·574.

Kuipers, Ben. "An Hypothesis-Driven Recocnition System for the Blocks World" MIT ·AI Workin& Paper 83. March, 197 4.

Landin, P. J. "A Correspondence Between ALGOL 60 1nd Church's Lambda-Notation" ~ACM, February, 1965.

M~rcus, Mitch. "Di1r;nosis 11 1 Notion of Gr1mm·" TINI.AP Pre·printt June I 0·13, 1975. M.I.T.

McCarthy, J. and P. H1yes, "Some Philosophical Prolttems From lhe Shndpoint of Artificial lntelli&ence" Machine lntellicence Vol. 4. American Elsevier Publishin& Company. New York. 1961.

McDvrmott, 0. "Assimilation of New Information by 1 Nalur1l Lencuaa· Underslandin& System" MIT AI Memo 298. 197 4.

Mclennan, M. "Hypotheses 1nd Reful1lions as en Aid lei Compvter

Vision" Thesis Pror;ress Report. Edinbur&h. June, I !f75.

Minsky, M. ·~steps Toward Artilicial lntelli&ence" Proceeclin&· el Institute of Radio En&ineers. Jan. 1961.

Minsky, M. "A Framework for Representinc Knewled&e" MIT At t.Aemo 306. June, 197 4.

Moore, J. 1nd Newell, A. "How can MERLIN undersi1IMI?" O.p.,lment of Computer Science. CMU. 1973.

Newell, A. and Simon, H. Human Preblem Solvinc Prentice-Hall. I t72. Rich, C. end Shrobe, H. "Unclerstandin& LISP Pre&rams: Towards ·

Pro&r·mmers Apprentice" M.I.T. A.l. Workin& Paper 12.

Rubin, A. "Hypothesis Formation 1nd Ev1luation in t.Aeclical Oia&nosis" MI.T. A.f. TR-315. Jan. 1975.

Rulilson Johns f ., Derksen J. A., and Walclinr;er lt. J. "QA4: A Procedural Calculus lor Intuitive Rusoninc" Ph. D. Sl1nlerll.

Sacerdoti, E. "Piennin1 in 1 Hiererchv of Altslractien Soaces" IJCAI-73. Sandewall, E. "Conversion ol f'redicate-calcuhll Axiems, V1ewM 11 Non-Deterministic Pro&rlms, to Correspolllllinc Deterministic .Pror;rems" IJCAI-73.

Stansfield, J. L. "Prottramminr; 1 Oialocue Teachinc Silu1tien" Ph.D. Thesis. University ol Edinbur&h. January, 1975.

Sussman, G. J. "The Virtuous Nature of Bu&s" Preceellin&s of AISB. Sussex. July, 197 4.

hie, A. "INTERPLAN: A Plan �ener~lion System Which C1n 0.1l With Interactions Between Goats" MIP'·R·IOt . Etlinbur&h. O.cemller, 1974.

W·rren, D. H. D. "WARPLAN: A System for Generalinc lltans" Dept. of

Computation Lor;ic Memo No. 75. June l!f74.

Winottrld, T. "Five Lectures on Artificial lntelli&ence" Stenferll A.t. Memo. September, 197 4.

Wirth, N. "Pro&rtm Oevelol'ment lily Sle11wise "·linemen!" CACM. Vol 14. p~ 221-227. l!f71 .