BEINGS: Knowledge as Interacting Experts

BEINGS: KNOWLEDGE AS INTERACTING EXPERTS

Douglas B. Lenat

Artificial lntelligl'nce l.aboratory Stanford Univer~ity. Stanford. California

preCist>ly what rach is domg, they can takr. their extracted bits of knowlP.clge. organize them, fonmlizP. them, and program them. {A consCious P.ffort along thl'Sl' lines was marie in [8). wherP. experts gradually replaced thenuelvt>s by programs. lnstt>ad of d1scussmg how to wrne a spt>ech p1ogram, they did speech recognition. until each ont> could intro~pt>ct suffiCil'ntly 11110 his own acuvltll'S to formalize thrml For our task, one P.xpects the psychologists to dommate thl' early diSCUSSions, later y1eldmg to programmers. Tht> pro jl'ct ~ponsor might be pass1vP., submitting a· single spt>cification order for the program, or active, participating in the work as a (somewhat priveleged) member of the team. This individual is thl' one who wants the final product, ht>ncr will be called the ustr.

How could Bemgs do this? Thrrr. would bt> somt> little pro~r .lm cont~ining information about CONCEPT -FORMATION (much more than would be usrd m wntmg any smglt> concept formation program). anothe1 Remg who knows how to manag;e ~ group to WRITE-PROGRAMS. and many lowt>r· level ~J>f'Ciahm. for f'Xamplt> INFO-OBTAINER, TEST, MOOIFY­ DA T A-STRUCTURE, UNTIL -LOOP, ·VISUAL -PERCEPTION, AVOID­ CONTRADICTION, PROPOSE-PLAUSif!LE-NAME. L1~P. the human spt>Cialists, thl' Bt>1ngs would contam far too much mformatlon, far too melliorntly replr~P.nted, to be ablt> to say "we ourst>IVP.S constitute the dt>med program'" They would havf' to dmuss. and pP.rhaps carry out, the concrpt formation ta~k . Thry would wnte ~peciahzed ven1ons of tht>mselves, programs whiCh could do t>xactly what the Bemgs did to carry out thl' task, no more nor less (although they would hopt>fully take much lt>ss time, be mort' customized). This activity IS rt'ft'rr<'d to in thl' sequel as 1111t~matic pr~gramming. Some Bt>ings (t>.g.. TEST) may have sevf.'ral distinct, strt'amlined fractions of themselve$ in the final program. Bemgs (e.g., PROPOSE-PLAUSIBLE-NAME) which only aided otht>r Betngs may not havt> any correlates in the final synthemrd code.

An exp~nmental ~ystt>m, PUPG. was dt>sl~nl'd and partially lmplrmP.ntrd . PUPS synthemrd a COil(Ppt' formation pro~ram (sumlar to [7]). but the user. who 1~ human, must critical queriP.s. A grammatical inferrncl' program and a simplt> property list maintenance routine were also generated. A few new Beings had to be added to PUPS to synthesize

comr. up with ct>rtain sp('cific answers to some of the Beings' them.

Tht> nt>xt ~ection 1llmtrates how tht> t>Xperts might have cooperatP.d on thl' task of wnting thl' concept formation program. St>ctlon ~ descnbes the program they produced. NPxt comP.s the Bemg hypothem: complt>x but standard anatomy. Latt>r sections t>xplain this, both theort>tically and by P.xaminmg the bt'havior of the actual PUPS pool of 100 Beings. Tht> appt>ndix t>xhibits a typical Bt>ing.

The input/output behav1or of the demrd conct>pt format ton p1 ogram IS spcCihl'd in thiS ~ect1on , and we eav,.sdrop un ~ Simulated group uf speCiah~ts as they get to wo1 k on wntmg 11 . As the presentation of thl' t>xperts' activities bf'COillP.S more speCific. thl' rt",tdt'r's wrrently vague concr.pt1on of Bemp w1ll be madl' less .1morphous (bt>cause Be1ngs are constr~mt>d to carry on approximately the same discussion as the experts bt>low do)

Abstract

Knowll'dge may be organized as a community of interacting modules. Each module is grantl'd a compll'X structun~. to simulate a particular P.Xpl'rl in some small domain. An l'XIt>nclt>d' analogy is drawn to a group of coopt>rating human ~pecialists. Basf.'d on this, an intt>rnal constraint is imposl'd on thl' modult>s: Tht'ir structure must be standard ovt>r thl' entire community. Some advantagt>s of a uniform fonnalism are thP.rf.'by prt'st>rved. An expt'rimt>ntal community was implrmentf.'d for the task domain of automatir. programrnin~. It has managed to syntht'size a few mductJVP. mft'rP.nct' LISP programs, nonformally, from spt>ofic restnctP.d dialogues with a human user

Consider an intf.'rdisciplmary f.'nterprise, attt'mpted by a community of human P.xpl'rts who are ~pl'cialists in .. and only in .. their own fields. What modt's of interactions will be productivP.' Thl' dominant paradigm might well settle into qzustiMzing and answning P.ach other. Instead of a chairman, ~upposl' thl' group adopts rult>s for gaining the floor, what a spt>ahr may do, and how to rt>solve disputt>s. WhP.n _a top1c is bemg cons1derrd, one or two experts might recogruze It and speak up. In tht' course of their exposition tht>y might nt>ed to call on otht>r spec1ahsts. Th1s might bt> by name, by specialty, or s1mply by posing a new sub.question and hoping SOfll('Ont' could rt'cogmze Ius own rP.Ievance and voluntP.er a mggPstaon. Such tramfers would be more common at the brgmnmg. wht'n thf.' task 1s (by assumption) too grneral for any onP. m.:-mbrr to comprFhend. As the qul'stzons focus on more speoflC issut·s, single md1viduals should be .lhll' to supply compk1e solutions. If the task is to construct somP.thmg, then the actiVIties of the experts should not be strictly verbal. OftP.n, one will recogn1ze Ius relevance to the currP.nt situation and as~ to rl~ soml'lhing: clarify or modify or (rarely) crf.'ate.

What would it mean to simulatr the above activity? Imagine sevt>ral little programs, each one modt>lling a differt'nt expert. What should each program. callt>d a Bring, be capable of? It must possess a corpus of spt>cific facts and strategit>s for its designated speciality. It must intt>ract via qut>stioning and answrring otht'r Beings. Each Being should be able to recogmzl' when it is relt'vant. It must set up and alter structurt>s, just as thl' human spt>Cialists do.

Let us rt>tum to our mel'ling of human expl'rts. To be more concrete, suppose tht>1r task is to desig-n and code a larg,. computt>r program: a conct>pt forma'tion system[2). Expt>rts who w1ll be ust'ful mcluclt> SCil'ntific programmt'rs, non -programming psycholog1m. system hackt>rs, and managP.mrnt prrsonnPI. What happPm in thl' ensuing sf'ss1on~ Whrn an P.XJ>f'll part1r1pates, hr. Will rrther bt> a1d1nr: a wll·~:tr. ur 111 ~unw rl111iwlty ur elsl' transft>ning a tmy, wstom11·~d IJit of h1~ P.Xpertm· (f~cts ~bout his 1\l'ld) into a programmP.d funct1on whiCh ran rio somethuw The final codr. ref~cts thl' mr.mh~1 s' ~nowl~cl[:l', in that ~('n;~ . One way thP. ~ession nu~ht procred 1s for t h~ spr.CI~hm to actually do the concept formation ta~k . A~ they becoml' familiar with what pall of their own P.xpertlsl' is being called upon, and in what ways, tht>y can brgm to 1solate it. When it is clear Ext~rnally , thE' concept formation task can be specified as follow~: piwu·ps of stn1ctun~s (built out of s1mpl~ geometrical shap~s) w1ll he presPnted one after another. For each such ~crnr, the (OilC('pt formation progr~m. call it CF, must guess its nam, Thf' presenter w1ll then reveal the correct name of th~ structurr. CF must qu1ck ly learn to identify s1mple structurP.s (ARCH, TOWER). and mmt nevf?r make the same mistakE' tw1ce in a row. Assume, as given, a process which extracts a description of a visual scene.

Our group of experts are givt'n this specification for CF. Assume that the mer (the fmancial ~po·uor) is available for resolvmg important qut'stions, via messenger. and he may in fact ask qur.stlons of the _group. Whenever an expert speaks, ahnost all the others in the room hear l11m. Usually only a few can benefit from what he says, and fewer still care to react . The convt'rsatwn in the room might go something like the following (the suggf"stive names of the experts are of course coincidental):

GENL-MANAGER: Can anybody here figure out what to do, what the user's saying? (wavE's the input/output specifications m thE' a1r)

PGM-MANAGER : I can. He wants a computt'r program to be wnttf'n. If somebody will explain the task "con-cept­ for -ma -tion" to me a lutle more clearly, I'll delegate It properly

PSYCH: Prrmll me to asmt you. I know all about concept formation. In fact, my mastrr's thf"sis .. .

PGM-MANAGER : Wall, the user must be told that we'll be able to handle thE' job for him.

MESSENGER: Herf", I can take that message. Go on with your work .

PGM-MANAGER : We need a name for this program. Somrbody gt't onf", plt'aSt'.

NA MER : How about "CONCEPT"? Maybt' JUSt "CF". Let's ask tht' ust:'r to dl"cidf".

MESSENGER : (pantmg) I just came back from there! Alright, I'm gomg .. User says to call it "CF".

PGM-MANAGER : Now then, I have four people in mind, one of whom must take over now in an important way. Each of them always wants to do something different.

CHOOSER: Givr me their names and I'll choose the best one for you.

PGM-MANAGER: They are INFO-OBTAINER, INFO­ USER , PGMMER, and ANALYST.

CHOOSER: You four I?Xperts each must JUStify to me why you should take conrrol now.

INFO-OBTA!NER: We already have some unused information, so I guess I can wait.

INFO-USER: Let me have the Aoor1 I know what to do with tht:' ust'r's sprcificat1on.

PGMMER : Well, I suppose I could set up some "empty" top-lrvel function, er ...

ANALYST: Marginal profits accruing from my working at this point in time do not warrant...

CHOOSER: Okay, INFO-USER, you seem to be the only rt>levant rxprrt .

INFO-USER : First thing is for PSYCH to tell us how to actually dn conct'pl formation .

PSYCH: Tht>n.· are several decisions to bt' made, depending on what you r independent variables and your expennu~·~tal setup are. For e>xample>, are we studying one individual, or must our program adapt to simulate many dHfP.rf"nt sub JE'Cts? Must stimulus items be JUSt classified, or class1fu~d and orde>red, or classified and ordered and metri1erl? Art" the scenrs left in vit'w indefimtt'ly, or just the cunP.nt scrnP., or is even that ont" just ftashe>d before thl' ~11h J"CI for a limited time' May the ~ub Jt'Ct make wrlltPII notes' Can he le>arn from poSIIIVt' Instances of the COIKI'pt~? from nr.gative uHtances' Is there to be any positive transfer effect...?

DEFER: Hold on here; we can't swamp the> user with lots of unnecessary questions. Let's go through each one and see if it can wait. Cons1der the dec1s1on about the task being classificatory, comparmve. or metncal. What is the first situation where that deciSIOn really matters'

• WHEN-NEXT: This involves a hst of alternatives. Who knows about that?

ALTERNATIVES: I know a few tncb here. If all the alternative sequences of actiVItii'S have the same> 1111t1al subsequrnce, then do that common subse'luence before making the dechion.

UTILIZE: In tim casP., all three brgm by partlllonmg a domain of elt'mf?nts.

DEFER: Temporarily, replace the task CF by the task of partitioning a domam. (Tilt' usa is infMmrd of this.) Now consider the deciSion about subJeCt-specific behavior being re·1uired.

PSYCH: ThiS mvolves penod1cally mputtmg a descnption of r he human sub JP.Ct .

CODER: That would mean adJustmg the algonthms based on a vector of parameters.

WHEN-NEXT: This would probably affe>ct the entire code.

DEFER : I can't deft>r this decision. Someone resolve it.

R ESOL Y E: Ask the user about 11.

ASK -USER: Phrase this as a yes/no question. Explain each alternative to the user.

MESSENGER: That's my job ... <t~fm on tdrtypt> User says no, don't simulate different people.

DEFER : The next decisiOn ...

Eltr·rn duisions art ultillliltdy p,.ot·osrd by PSYCH, and all l>llt ont art drfrrrt'd.

INFO-USER : I have no objections now 1f someone wants the floor .

PGM-MANAGER : Do any of the other three experts 1 mentioned earlier want to speak now?

PGM MER: Yes. I think that the top-level function CF can now be coded .

CODER: Give llll' the arguments and the body of the code.

PGM MER: There are no known argumt>nts. The body is a call on PARTITION-l>OMAIN.

CODER: Okay. I w1ll precede that wuh a call to an INITIALIZE function, and follow 11 wuh a call to a FINALIZE function, which are both delined as NIL for now. Is PARTITION-l>OMAIN s1mple enough to be composed right now and filled in here?

MATHEMATICIAN: No way. Any realizate ...

CODER: llh, thanks. There. The function CF is defined as: (LAMBDA 0 (INITIALIZE! <PARTITION-OOMAIN) (FINALIZi:)).

AN A L YST: Remind me to l'X amine the imtialization and finalization functions at the end of our task. If either function is still null. 11 w1ll be de>lt'ted.

WARNER: I have just put that note into the code for CF, as a comml'nt of type "demon"

PGM MER : Can someone aclv1se me of what else to do to fin1sh defln1ng this function'

PGM-MANAGER : Each funwon should have a proper name. Show the user the names you have picked, and Jet him choose other ones if he prefers.

MESSENGER: Okay ... The use>r at~rP.es to all :l names.

INFO-USER: Somebody, please tell the group how to do partitlonmg of a space of examples.

A complete scnpt, like the .1bove, was constructed by hand . In the sequel, tillS w1ll hP rrf··rrrd to ~~ the proto;o/. In all, 87 diffe1rnt experts wt're call~d for: 17 specificly dealing wuh mductiV!' infrrrn(f' r .u~ ;. and 70 dealing with programming. managing workers, and comnnm1catmg with the ust'r. Near the end of thl' protocol, the user is asked wh1ch of the thr~e t)'pP.s of concq>t fonnat1011 CF IS supposed to do. He responds "CL.~SSIFICATORl' on/·(, and the experts diSCOVer that they are fuushed . A II thl' newly created codP. is dumprd out onto a frrsh nit': After hundreds of pagP.s, a conct:'pt formation prog· ;un meeting the user's spt>c1ficat1ons had bt>en wntten. The next section Will clescribP. that pn·gram in detail.

Clnf' of rhe ··xprrls at the sumrlated rnrftiug must have re~d P. Wmsrnn's rlm·'1Htlon[7). bec~me CF, the synthesized concept fonnat1on program, was rrm;u kably similar to the one therrrn dE'scribrrl. CF has ~ much simpltr graph­ matciHIIf: alf:orlthm, ami rtbtrons on relations art stored in a diltNent way rh~n sunplr rrl~tro11 s on ob jtcts. Since CF was latt'r syntlwsrzt>rl lty PUP6. the programmed pool of Beings. it i~ worth drlarhng hrrr.

CF rrpr:l!f.·dly sc.1m a scene .1 nd tnr.s to name it. As a first ""P· 1111' <r t.'lll' 1s brokf'n 11110 :1 set of obJects and a set of featun·s (rrl .·llom on those ob )t'c15). CF mamtams a model for ··ach clifl··ll·lllfy.n:mlt.'d >CCIII.' It has encountered. A model conr~ms a clr>enptlou of the oh jeers one PXpects in such a structuH', a so:-1 of fea11nes wlmh must be present in any scrnr havmg thiS name, a set of features which must not be prrsrnt if the w~nr IS to have rhas name, and a set of features whach may be present or absent . Thus a model is an archetypical <<: rnr plus a name. For example, part of a scene maght be drstnbed :os:

OR.JF.CTS ~.b.cd

RELATIONS (�a·~en a) (Blur c) (Touches c d)

(Suppom a c) (Supports b c)

CF's currenr model fur an arch maght bt:

NAMF.

Arch

OBJECTS a,b,c

M liST

(Supports .1 c) (Supports b c)

MllSTNOT (Toudws :o h)

MAY

(GrcPn a) (WE'dgr c) (Pmm a) (Blocl:. b)

(Parallt'l a b) (Rrd a) (Red b)

Each ruw· It is ronfrontt'd IJy a new scrne, CF must ;can its models 1111t1l 11 hnds one wh1ch matches 11 . A model is said to match a S(f'llf' if all the MUST frarmes associated with that modo~ l art obs('I'Vt'd in rht sctnE', and all the MUSTN<Yr featlll'f'S are absrnt from the scene. CF informs tht' us~·r of elm [:uess, :t11d accPpls the proper name. If it gur<srd mconrrtly. CF modaties its models. The wrollf:· f:Ue~s model may have fea1111es added to Its MUST or MUSTNOT ~er~ . Tim i~ suflicacnt to prevent CF from making the samf' we ong gues~ twice in succession. The correct-name modf'l may have to be modafied or (if it's a new namP.) crratrd and ansen~d 11110 the hst of models, to ensure that CF wall r.vent11:1lly learn that concept. A concept herE' simply means a modr.l; i.l'., all scents havmg a given name.

Suppose that the targP.t program reads in the above scene fragment and tnt's to march It to the above ARCH model. The MUST relations should all be present. Yes, the scene does contain (SUPPORTS a c) and (SUPPORTS b c). Next, the MUSTNOT relations must be absent from the scene. Sure tnough. (TOUCHES a b) isn't there. So the model and ~cent arP. conmtent, and the program announces that its guess is ARCH. If the user venf1es this guess, then the MAY set of the ARCH model is augmtnted with the relations (I~LUE c) and (TOUCHES c rl), and the OBJECTS set is augmrntl·d with "ct ."

If the 11sr.r dt'nirs char the <cen~ IS an arch, CF sees if thf.'re are any relations 111 the ARCH model's MAY set which do not occur in the scene. If so. ont of thf.'m (e.g., (PARALLEL a b)) wall ht tramfrrrcd f1om thE' MAY to the MUST ~et . If no mch featmr 1'\lstrrl. thE' program would look for a featurE' prl'~l'nt 111 lht' ~cene uut not mentioned in :~ny st't of tht' ARCH modrl (r.g . (TOllCIIES c d)), and l!IH' I t il mto thE' M lJSTNOT set. In rlthcr case. the user would be ;oskfd what thr IIIII' namr was, and that model would havr lis M A\' St'l .lut:nwur.·d lty any new features in thr ~ct'nt' :md by any fl'aiUi l'S on tht' true-namP. model's M liST or M USTNOT ~ets whach <"Ontradacted the scene.

~.ApajOJJlY_..9L.Syn_~reeti_c_Coop_~[af[qn

CumidP.r thf' b1rth of one ~ mall rdea llf'CI'S>ary 111 thE' writmg ol CF (r.g . rh .11 of cl .ns1fymg ~ modd's features mto tlnee r.a t··t:"lr··s (Mt JST , MU~TNOT, ~lAY)) No single ~prCiah<t at rhr lllf'f'llll f!. (OUlcl havr had tim acll'a by himself. How do lllt t:> llecrs mf'sh. rffP.r. llvP.ly comrm11ucare. and unite !hear powers~ II tf'ntauve mrc hana~m. whach harely scratches the surf ace nf rhas mystery, will l·e hYJ'Oiht"SIZE'd. The Bemgs in PUP6 f'mbody rim concept. and ~rE' able to rtproduce both the rxpem' dmus51on and the final CF program.

Viewing lhP. group of experts as a smgle entity, what mal:.es at producu ve) The membeas must be very difff.'rtnt in abilitiP.s, in order to handle such a complex rasl:. , yet similar in basac cognitiVE' structure (in tlw anatomy of thP.II' minds) to permit facile communacataons to flow. For rxample, each speCialist knows how to darect a prog1 ammer to do some of thE' things hP. ca n do, but the ~pecifrc facts rach f'xpert has under thas ca lf'[:ory must be qu11e 11naqur. S11nllarly, each mP.mber may havr a set of stratf'glrs for rP.cogna1.mg his own relt'vanc · ~ to a propo~t'd q11est ion. but the contn1ts of that knowledge vanl's from mdivadual to mdav1dual. The hypotll('sis as that all the experts nn be said to consist of cattgorized mfor ma11on, where lht' set of catP.gonrs as fairly standard. and mdrcares rhe tyJ>o of ques11om :my expert can be expected to answPr. An exp!'rt is conSJdeaed rquivalrnt to his answPrs to ~evtral standard quesr aons. Each expert has the same mental "parts". 11 as only the va lues stored in these parts, thP.ir conrr.nrs. which distinguish him as an individual.

Armed with rhas dubious v1ew of mttlligtnce, let us return to the desagn of Beings. Each r.eang shall have many parts, tach possPssmg a n~mP. (~ qu<'staon 11 rltals with) and a value (a proct·dure capable of answenng that question). Henceforth, "pc11t" wall be used 111 thas rrchnrcal sense. When a Being asks a question, at is rtally JUSI one part who is asl:.ing. In fact . it must be that thl" Mlllt subpart of some part can't answer hiJ quest1on wllhout further ~ssistance . He may not know t'nough to call on specific otht'r Bt'ings (so he lets anyonE' n~spond who fP.els relevant). bur hP should crlways specify what GPmg part thE' quC'Stion should bt' answertd by. By analogy with the experts, each Being wall have the same "umv!"rsal" set of types of parts (wall :ulSwrr the sam!" l:.inds of qutnC's), and this umformaty should permit pa·inless mtl"rcommunacation. Smce the parada~~m of thE' ml"eting is quP.stionmg ~nd answering, the nanws of the parts should cover all the types of questioi1s one rxpt'rt wants to ask anoth<'r. F.ach part of each Being will have amphcll access to thas hst : tt may ask only these typts of qutst ao11s . Each Bemg should nM have accP.ss to the list of all Bem(;s m the system: requests should be phrased in terms of what as wanted; rarely is the name of the answerer specified in advance. (By analogy: the human speaker as not awarE' of precisely who is in the room; when he feels inadt>quatt, ht asks for help and hopes someone rE'sponds). A nothP.r po1111 as that Beings are not a recursave concept (like ACTORs[~) are): a part of a Being is a brit'f collection of knowledge (usually procedural), not another Bemg; a collection of Beings (also called a community, a pool, the system. or a group) is also not itself a Being. Thtre are no Jtr' II<'II/T(<f clusters or B<'mgs.

Once again: thE' concept of a pool of Gf'mgs as that many t'ntitif's cof'xist, each havmg a complex structlln·. but that struc!lll't' does not vary from Beanf~ to r.emr: . Thas idta has analogur.s in many fif'lds: tnmaction .l l ~ n a l yqs 111 psychology, anatomy 111 mtdacllrE', modular desat:n 111 archll t'dl!Ure.

How can we tPSI our thas rdea ) We must IJuald a pool of Bemgs. a modular pror,ram wh1ch wall rnter.rct wtth a human user and grnrr;He lhr CF program Rtcastmg the idea into operational IE'rms, we arrave at th is proctdurP. for writing a pool of Beings:

• (I) Srudy thr ta~k which the pool is to do. See what kinds of qur~tiom arr a~ked by ~imulatrd experts.
• (~) D1 ~t1ll 1111~ mto a CQr~ of ~imple questions. q, in such a way that "~' h uHrr.rxpNt 'luest1011 or tr a n .<f~r of control can br r rphr :H·~rl 111 term< of (!_: The qze nf f .~ ll very important. If (~ ll Inn 1:11'):.''· .uid111on of nrw H<·mgs w1ll demand either t·.lr;ot ,.ftoll or f·.rrat lllt r lll!!,rnce (an rxample of a ~ystem like tlu< "ACTOR~) If(~ IS roo small, all rhr. IIOII ·IIIHformity is simply push·~d down mto the vahlt'S of one or two gem·ral catch~ll qursttom (~II first ·order log1cal languages do this).
• (~) l.ist all the fipmg< who Will be presrnt 111 the pool, and fill in thr.ir part<. The time to t'ncode knowledge into many s1mplr. rqnr<entat1on schemes 1s proportional to the square of (occastonally exponential in) the ~mount of interrelated knowll"df~" (!>.g .· comrder the frame problem). The filling in of a new lk111g is i>llftJ>t'1tcimt of the number of Beings alre.1dy 111 the pool , because P.emgs can communicate via nondf'termilmtlc goalmechan1sms, and not have to know the namf's of the Bemgs who w1ll answer therr queries. This filhng in is lintnl in the number of Being parts listed in Qj all pat ts of all Bemgs must be (at least, should be) filled in.
• The human user interacts with the completed Being comnmntty, unt1l thl" rlesirrd task is completf'.

Settron r, clarafie< the rffects of constrammg that Q. be comtant (ovf'r ~II the Bf'ings in the system). Theoretical asprcts of r.emg ~ystf'm< follow, 111 section G. Next comes an evaluation of PUPG's brhavior. The mes and the problems .with Beings are summrd up in thr ftnalsection .

A H't of ~9 ubiquitous questions were chosen, reprrsrnt111g evt·rythiug one rxpert 1111ght want to ask anothrr. At least . they naturally encompass those questions wh1ch Wl'l'f~ asked during the simulated meet1ng. hence should be sufficient for generatmg CF. 1{. th1s umversal set of Being parts, is hsted in A pprndtx I The reader is urged to glance at th1s now, and refer to it whenever a Being part is specifically mentioned.

Each of the 100 Beings in PUPG should have had a value for Pach part (m reality, only 401. of these 2900 slots Wt'rl' ftllrd in; only ~(11. were ~ctu~lly n~cess~ry to generate CF). A value for a pall is s1mply a LISP prc>g1 ~Ill which can answN th~t <JUl'~tlon . oftrn by asktnt; questtons of the same Brlltt),. of otlll'r r.emgs, and of the mer. A part may also assert somr fact , rreate or mod1fy some structllre (including demons, Hr.mgs. ~nd pam of Bemgs). Appendix I shows the values storrrl under each part for the typical Being named

"INFO-OBT AINER".

The sf'l of p~rts bre~ks into three rough categories: (I) those parts which are useful in deciding which Bemg gets control, (?.) those whrch are used oncr the Being gains control, and (:1) those meful only to answer the user's qur.~llom ~net krrp hun onentcd. The nrxt section describes cate[:ones I and ~; the section after that rxpltcates the third catrr:ory of Brmg pam.

At the humans' met'tmg, only one expert spoke at a time; in thr lkmgs communlly. only one Brmg has control at any g1vPn momr nt. 1-11' uses his parts to do things (ask, create, mod1fy), and yirlds control rither voluntarily or through intP.ITIIfJIIon

In shghtly more procedural terms, the scenario is as follows. One part of a Remg sensrs Its teiPv~nce (often the IDEN or EFFECTS parts, wh1ch ar!' unttrd with all such part .~ to form a large production ~y<tl"m[5]) . If more than one Bt'tng wants control at any tunl", a ~pec1al Bemg. CHOOSER, seizes control mometlt~nly . He asks each competing Bemg to evalu~te tts WHEN part. to see how seriously it nPeds to go 1111111rdtatrly. If somP. Bemgs are still tied for hrst place, he asks them to evaluate their COMPLEXITY pam, to ~ee wh1ch IS the s1mplrst. If any still tte for top, one IS randomly clwsen. In any case, the winnrr IS chen pas~ed control. 0ncr 111 control, a Bemg arrang·es snme of its 11arts 111 somr. o1d1'1' :111d r.valuates them. For exampk, the A RGS part mt (:ht b,· hrst; 1f It asks for some arguments which no Brmg h:·~ " 'I'Pir('d, then the whole Being might decide to fall . Somr. parts, when evaluatrd, might create a new Be1ng. m1ght ask questions wh1ch require th1s whole proc('ss to rt·peat rewrsively. etc. This "asking" really means broadcastmg a rr.quest to one or two parts of every Being; for ex~mple "Is there a known fast w~y of gronking tovr.s?" would bP asked as a search for a Bemg whose COMPLEX lTV part 111d1cated speed, and whosr EFFECTS part contamPd a production with a template matchmg "gronking toves" A list of the responders would be rr.turned . (Incidentally, GERUND would recognize this, but later give up when no one could recognize "gronk roves".) The questioner m1ght pose some new questions directly to these Beings. might turn control over to them directly, etc. One way or another, the Being eventually relinquishes control. If it had no d1rect succrssor in mind, all the Beings are ~skeet if they want to take over. Thert· will always be some Being who w1ll take over; the general management types of Bemgs are always able -- but reluctant --to do so.

How does t'ach Berng clec1de which parts to evaluate, and in which order, once it gaim control? The answer might seem to be difficult or tedious for whoever writes Beings, smce it might vary from Bemg to Cemg. In fact, it doesn't· The commitment to a universal set of Bemg parts is inenicient in some ways (each r.emg nadf'd only a third of all the parts) but allow~ for some ~1mplrncat1om nght here. What parts should be evaluated. :mel m what order, when a Bemg gains control? Th1s dem1on deprnds pnmarily on the tvpn of parts present in the Bemg. not on the1r ~>aluts . But every Being has the same anatomy. so one smgle algorithm can assemble any Being's parts into an exrwtable LISP function . Moreover, this assemby can be done when the systrm is first loaded (or when a new Bemg is first created), and need only be redone for a Being when the values of its parts change. Such changes are rare: experts are not often open-minded. The prec1se algorllhm is sketched in the box below. Thl' parts useful here mcludr. ARCS, DEMONS, META-CODE, COMMENTS. ARC-CHECK, and R Eq_UISITES

A .~~t')IIJ!l!!H~ -:0J~iii)! .JI!J.!'_,1!1J':'(g(IH.1_bl~ Jttttr!ion When a Bctnt< B fir$! f,ain!. control, it~ EXPI.ICIT -ARGS are bound. The IMPLICIT -ARG5 arP initialized, the name B is pu$hf'd onto the Be>ng cot~lrol slack, and any newly­ activated DEMONS are so tar.~rd. The Beinr, who called B !.hould have c·plamed hie. rcac.ons b>' a~sir,ning some phr a5c to I he variable BEC.A.USE. Thi~ r ea$On is now ~lored a·. a ··rerial sub-part of the WHY pari of B. BECAUSE is rpbou»d periodic ally in the MET A-CODE and COMMENTS part ,. , to kpep currcnl lhc e xpl~nalion of each call thai B makes. Each ARG -CHECK predicate is evalua!Pd. If any returns NIL, lh<' r t~li r <' BPmg reports that it has failed; othNw!!.c, lhC' PRE -REQUISITES are e·amincd. Effort IS c·pcndcd lo ma~,c ll1t·m lruP, if lhPy are c urrenlly not $ali !. fiPd. Each COMMENT ir. PvaluatPd, then the CO-REQUISITES, MET.II -CODE, and the current demons are executed in pseudo-parallel. Each POST­ REQUISITE is then e·amined, and an effort made to satisfy it . The newly-act ivated demons are e·orcized, B is poppPct from the £lemp. <Onlrol ola<k, and the value <Omputcd by the META-COO[ io returned. Some heuri ~.li< s werf' devi~ed to take ~dvM1tage of the fact that the Beine~- often didn't need many of the , tandard parts. For c~ample, INFO-OOTAINER ha, no new demono or co­ requi~.i te , , c.o no p<trallel prO<e·.si ng need be simulated.

In the ~arlier conversatron r.xceqm. tht' ~imulatt'd human ustr had no trouble whattvo:r unciP.manding what the simulattd expem a~ked hrm. In tht' actual programmed PUPG sy~trm. the human who was ~itting at the teletype quite rrnrl"' undentood what was wanted by the Beings. He frtqurntly had to interrupt thrm and a~k them qutstions about whco wa~ in control, why, what he was trying to do, what had 1 rcC'ntly trampued. rtc. These ideally can be phra~C'd ~~ <unl'lt· rrtno:vals and F. VA Ls of active Beings' parts. The 1\rmg par rs mmt ntrrn call~d for by the user are the ~rmpl,. 11no:-hno:o "nrwntAtron" tl'tllpbte~ . These include WHAT. HOW. WilY. and AFFECTS. For theorettcal reasons rxplauwoJ l.lto:r. the syntlwsr1o:·d pro~ram, CF, was writen a~ a pool of 1:\elll f,~ mo:lf (by PUPS. but not during the protocol. Actually. A fortu1tcous "bug" in PUPG created thts mtngum~ .<ttualtfJn.) A It hough 1ts question-answering ability is infnror to PUP6. the fact that it has lln'J such power was smprmng to the ~uthor. In other words, one can interrupt the tat[~er prog1am a~ It is running and ask questtom. Any Gem[: on the control stack wrll provide fully instantiatrd amw<'rs to ~ny of its ~9 allowable queries (its parts); all other Be1np wrll prov1de only hypothetical answers. As an example, cons1de1 thrs actual excerpt of a human using the CF program ~ynthemed by PUPS. (Some liberty has bC'en taken with the English; e.g .· tht' user really ~ypes W H .4T', not W Ira/ arr _you doing~) "???" simply means guess the name of tht' scene wuh these objects and rtlations". CF types in italicJ, the user in boldface.

C F: R((u/-y to aar j·t brand nrw scmt.

User:(??? (A B) (81n,,~ A) (Wrdg<· B) (Touchr$ A B)) CF: N(l/ an A1ch. Not a Town . Miglot /or a Roru.

M~ guru is R(IW. IV hill is it Rrally'

U$er: Nothing

CF: Trllnsftl from lllf May I (I tlot Must ut of tht

Roru rtwdd. thr frntwr: ( 8/oclt B)

CF: Rtady to aarpt b11111d nrw sano·.

Here is the samt excrrpt. but with the user interrupting occasionally. "ll:" srgmhes he has interrupted. and "OK." signifies "Go bade to work now. CF."

ll: What art you doing?

CF: llividt a d(llllclin into wbclomains,

using spuialiud 1·mion of PARTITION-DOMAIN.

How?

OK.

CF: By building 11 p tht partiliMI gradually.

by adding onr <sanr, namr> J·ail . CF: Rtady to acapt bmnd 11rru s.-rllf.

User:(??? (A R) (Riod A) (Wedgr B) (Touch!'$ A B))

ll: What art you doing?

• CF: Drtllk. ODJ ECTS pi,·,-.- ·:0 inf·u: s.-o1.- t.> ·· -~cmtillt . What <"ndr i1 thr <"Urn·nt Dring gnin~; to t'Xecutt?
• CF: Tilt lltl'ltlo'rcll' is (CAl>R o11g/J. E1·als to ( .4 8). OK.

CF .· Not an Ar,-lo .

U: Why?

CF: Thr ARC/-1 MUST-1dation (SUPrOras A 8) is contraclio'fo·ol in thr SCENE. OK.

• CF: Not a Trwa. Migl,t l·r a 1\ow. M~ i:II<'H iJ R(lw. What is it uclll"'' ll: Why art' you asking?

CF: I mustlrsOil·r it now. but mn't. 10 I ask Usa.

OK . What you wanted i1: Nothing

ll : What are you doing now?

C.F: Go through Jf'aa of con.-rf·l nallli'J, anolm11kt !Urr

awcnr rf cloangn.

CF. MESS!I(,f iJ pM;i/ol-y callrd: SOIIII' oosi011 of TEST is f>MsiN-y ra/lt·.t. OK .

CF: Transfa jrQm thl' Ma-y to tlrr A·luJt )(/of thr

Roru >ll{ldr/, tlor fral!nr : (Block 8)

ll: Why?

CF: Ch11ngr modd of ROIV until it c'r'ltmolictJ

tlrt prtl·iouJ inpullnl Sanr.

OK.

CF: Rtady to acco'f>l brand nnu sano·.

6. Theory of Pure S.~iDgLSyst~_ms

We now dtswss the constr~mts rach nemg, and each group of Bemgs, must conform to. Hopefully, ideas will be separatl'd from implementation detarls, prt>judict's from plausible featurt's.

It would be aesthetically pltasmg to restmt all tntities in the system to be Beings. However, this would cause an inf1nile rtgress, as each part of tach Sting would havt puts which had parts ... To stop this. ont can asstrt that at some finite level. all comtructs arco pnnutivt'. ACTORs, for example, sPt this lev<'l to zero; Ikmgs set it to one. ACTORs thPnw:IHs are pnmurvP. but only J·artJ of Remgs can be. For this rP.~sun. Bemg~ can not be vrewrd as a convergent recur~rv<' drfm1t1on, as can ACTORs.

Suppose 11 werr d!'crred that thl' only ~utonomous entities po~st'ssing control abrlitrP.s were Bemgs. In particular. we forbrd any plam f!tllc'lic>ns to Pxrst. In the case of an automatic programming task. thP Bern(!_s would have to write new Bemg~. not new LISP functrons . Tht> target program would thus itself bt a community of B<'tn> : ~ In order to fill in all the parts.~ va~t amount of superfluou; mformatron would bt' collectl'd. Thl'se supplementary facts can he vrewed as a standardizl'd, org~nized body of dN!I.·IIt'n/ation. a formatted systt'lll of comments tackect onto each Bemg produced.

Which Bemgs would wrrte the new Berngs? Looking back at our interdrscrphnary expem, Wt' ste that each expert is responsible for distilling his own rssenttal contribution, which IS then encodt:>d by a programmer. Perhaps tach Being should be able to du·rct constnrct1on of new, specrahzP.d Bemgs whrch rtlate to 11. If no Bemg relatt's to a task , then rt can't be coded; 1f ~f'VN~I respond. they should coopP.rate. This abrhty rs 111 reality the ~PECIA LIZA TIONS part of rach r,erng (sre Appendrx I). The Btmg which aclllally doP.s the creation (CODER) 111 the t>xpenmental system is almost trivial, gettmg very precise rnmucttons from other Bemgs.

Since the pool must communrclte wtth tht' ustr. some Btrngs must translate quasr-English phrasl's into calls on B('mg~ . Drawmg ~gam on our exprns analogy, we rtquire that each Gemg recognrze his own rrlevanc<'. So translation is mt'rl'ly the act of askmg tht wholl' pool "Who can recognize this .. . ", collectmg the responden, havmg th.-m decidt' who should takl' control, and letting the wmner do the translation. Most communrcation is dont' as if lt. too, wtre such a translation activity.

One bras is the rejection of debugging as a fundamtntal programmmg tool. It is felt to be worth the extra tffort to make thl' sy~tP.m\ mternal model of the cun<'nt partial targtt program cMrflt . Debuggmg demands detr.ctrvt work, txamrng one's t'arlrer rtforts for fl.tws. for detarl~ which have b!'l'll overlook Pd . Any !ll'eiC'S~ systt'"' should not rgnore dttarl~. but ratl,,.r defC'r thcom . . u~,., tm~. :1 1varning to this effect whl'n it dci('S so. Procrasttnatru11 ·~ qullr valu.lble; in PUP6, much ~ffort rs ~pent dt:>fC'tTIIl?; .1ny unresolvable dtcision. Undefl'nabiP. unrl'~ol v abiC' rlrcmom must cause a bac~track pornt to be reluctantly set up. Another preJUdice is that most carelesme~s bugs can be chmmated by this deferral. feed -forward . and prtcrse recorcl -keeprng. Humans depl'rarl on 1lw1r adaptability to comiH'IISate for linuta!lons in th"ll brain hardware. but th~rl? i~ no nrrcl for an automatic IHU((I ammnrg sy~tc·n1 to do so. These brasses are not inht>rent 111 tht' F\rrng~ formulation, but oraly 111 the destgn of the PUPG systf'lll (and 1t1 the mind ol thr author).

To danfy what B·~mgs :..-r :tnrl :..-P. not , they art' contr~~trrl with ~nmr othrr rdeas. Fl~ II~~ F:'-[·1) arr mfficiently .1morphou ~ 10 ~ ~~b~um·' lk111p. In plult:o~('J'hY. fRII M ES art> nwant lo mudd percrplron. ~nd urtrnllun .<lly 1rly Clll implicit rlrf ault valur'; Brm~s lntPntiOII ;olly "vorrl makmg decisions by ddauh . Th1s is also the dtffr.lt'llCt' bctwrrn HACKER and PUI'6. SincP. PUPG wntes strucltlrt?d programs. it should bt> diSIIIlf_';UIShl'd from macro expansion. Macro prnc!'rhrars rxpanrl mf'chamcally: rxpand(~rqnrnct> m1 m 2 ) · (.\equrncr 1'xpand(m1) t>xpand(m 2 ))). Brmgs could use informa11on glf'anf'd dunng rxp;uHrun of 111 1 10 improve the way m7 was handlrd . ACTORs[?.], ranhkr Brmgs, have no f1x·.·d stnu tiii'P 1mpmed, and do raut lnoadcast !herr mtossages (thry ~prc1ly who gets each messagr. IJy name, to a bur,.auuat y).

Bl"mgs subsume (metlioently) many popular A I featurt>s; thP drmonm.1t1on will be bnt>f: A oltmon could be replaced by a Bf"mg whose A RG-CHECK predrcatt> was the trigg,ering prPdicatt', whose WHEN part was h1gh enough to t'llllll'f' frf"qurnt attf'ntron, and whos·~ MET A -CODE part wa~ the hody ol thl' tiPmon. An oiSJt>liMI 111 an associative data m·twr.nl could bl' a F\emg wilh only an !DEN part filled m; whrn rt 1t'CO)·.n1zes 1ts relt'v~nct' . a fully mst~ntiated as<r1t1on ·~ rrtuni~d . A funaioll 11 equi i' ~!Pnt to a Being with only .1 META -CODE, ARCS, and EVAL-ARGS parts; onf' know~ almost nothmg ~bout 11 bf'fOrt' eHCIItlng it. The lllf'niut>mlf'S should be clear: whenevt>r a BPmg throws a qurMron opr.n to the floor, "Who can .. .", it takt's an amount of trmP. IHCIJ'Oition~l to tht> number of Beings 111 the system. Onf' woulrl 1ntroducP this huge time factor by replacing any or thl' abOVP lllt'Chatmms by Beings.

Th~ 1111.111/oa ol Bf'mg parts set>m~ to indrcatt' the balance betwrl'n unrlolnHty .md structurf' Ill the community. This was tuuclwd nn a< pornt (2) or S~ctron -1 . A small univPrul H'l ol r.,.mg parts 1s necessary to llft'~rrve some of the advantagrs ol uniformity (rasy ~ddition of knowledge to the system. Pasy intN-Being communrcat1on). This demands that th~ numht'r of parts of each Bemg be, say, under 100. But it is the complex structurP. of a Being which makes complex behavror~ !Pasahlr, includmg lll'xrl.·lr communrcatron as well as vrablf' fmal products. So each Bemg should havt> many part<, qy .11 lraM ten. Tim rangr. 10 ~ 11011 ~ 100, is widt> for lhP. clumam uf alllomatlc pro[:ramming. In other domains, 11 m:~y hr nanow or rlrsappr~r ~ltngNhr.r; th1s would indicate that Brmg< multi 11N l.·e llll'cl P.lft'CIIvely for those tasks.

Two of the most srgnrflcant ljUt'~tions for automatic programmurg systf'm~ ~re what lli'O(;r~ms art> synthesized, and what kinds of tlungs tht> mer must trll the system.

?J . __ qu r.~~· .rrr _nf....!_l)_!' QJ11J.!'~!£.t II'!'<'JLJ l_~f _,1!i!!J'JJJ~-~

By lumpmr: all the parts ol the PUP6 ~ystem together concP.ptually. thr mtrr;tctron IS sren as a di11lrgzu bt'lween a hunMn IIIN ~ncl an au1omat1C programmurg system The level of cll·taJ!mamtalllo.·d Ill the l.':lrher polylo[:Ur (discussions among thr experts) obscurrd what the human actually saw and rP.sponded. Below 11 the same t'XCl'rpt as was presented in Srction ~. hill as the usn sittmg ~~ a tdrtypr actually saw 11. Th"~" Wf'rr tht' 111111al lew IIIIP~ of an actual ~00- pagt> long draloguf'. In srctron ::. th1s f'XCNpt was prt'sP.nted the way f'XJ't:'ll~ (th!' s~nw way the PUP6 Be111p) d1mmed it PUP: 1 want ~ny task. USER : Wntl' ~ program whiCh rlors corlCI'J'I formatron PUP: I am about to writr a progr ~m for thl" task: 5pecialized kind of CONC[ PT -r ORMATION. PUP: Givf' me a propt>r namf' for 1h1s program (I suggtost CF or CONCEPT) USER : CF PUP: Must CF m1m1c differPnt hum~n mbJPCts~ USER NO PUP: I am temporarily replacmg lhe task '\pectalized kind of CONCEPT -FORMATION" by thr srmpiP.r task "5pecialized kind of PARTITION-A-DOMAIN".

From thP. abovt>. one gets the true Impression that the dialoguE' was la1rly tedrous: chon<mg namrs and resolving desrgn drcisrons """ tht> m~r·s 111~111 rule. Th~rf' wt'rt', in sum, abm,lt ~00 such respnmr.s mvnlvrd 111 r.:rnrratmr, CF. I~ crucral rP.sponsP.s wflrP. also nrcr~s.u \'. IVhf'ro' thf' mrr supph!'s needrd mlonnauon that w~s nm "'Jihlllly 1 rq11r.srrd hy the Bemgs. A lew of thf"Sl' kry hnrs arr. ll'1ilt ol t·rog111m which dots conapt fonnation; An "dnrrnzl rf tlrr dom11i11 of slim~tli" is a. sratic ur1u; Tlrt g1uHing f'rNrH is Mit of stalo'lring, not cCJmpwing: Ttrminalt tAl' I~CJ/' iff 11ny m~cfd ftaiiLrt is incompatiblt' with the So'tn/s ftollllrts .

The translation mPchanrsm IS 11111ply the !DEN parts of all the Bemgs. Each such part contams a few productions, which art> united with thosl" ol tht' other BPmgs into one large procluctron system. Tht> left mle of a production is a template which rs matched agarnst the given phrasP.. The rrght side IS a small program to he l'Xecuted in . cast> the phrast> is recognized. Generally, that program simply says to translatP. somt> subphrasl" of the phra~e. and then (probably) pass control to thP. Btomg whrch tim 11 111 the lDF.N part of. Whilt' not up to thr "statt' of thf' art" in natural language processinf.. tlm 11 both adequare and faithful to tht> spirit of distriburmg probkms ovrr all thr. Be1ngs. by m.1king them P·nls. so 11 11 e~ch Bemg's duty to know a lrttk about tht>m.

Durmg the count' of the d1alot;ue. PUP6 ongmates the idea of a MUST/MUSTNOT/MA Y mucturmg of each modPI's lt'atures. Ht>re is how the user sees that por~tlon of the syntht'srs. Nollct' that only the first user commt>nt is otht>r than a simplt' choict>.

PUP: How do we know when to tt'rminate this loop?

USER : Tt>rminatt> iff any fpature 111 model-features is incompatible with scrne-features

PUP: PUP wants USER to type in name for specialized vt>rs1on of CONTRADICTS

USER Call it IMPOSS

• PUP: MovP. cursor to IMPOSS type of CONTRADICTS. I can no longP.r dt>fl"r this dew ion: II : Contradiction ansP.s from fpaturrs who have probabrllly· l of occurring. B: Conti adlctrCin arises from features who havt> probabrlity·O of occurrmg. C: Contrad1ctron arises from ll"aturPs who havl" probahrhtpO&< 1 of occurring Pltoase type some cof: II.B.C: or typt>: DP.Ier. '·or Deta1ls.

USER : A. 1\ . and Carr. allrrlf'vant.

• PUP: I recommr.nd that each model's fe,1tUrTS be structured (along 1 dimr1mon) mto thnl' ~ prrcr.s: PRESENT, which w1ll hold features whos ·~ occulwncc should have probabrhty- l; II BSENT, wlud1 wrll hold fcaturn whose oCC1111rncr. slroulcl havt' prub.lhillly·O; .1nd EITHER. wh1ch wrll hold fpatllres whosr nccurrf'mt· should h:we any othP.r probabrhty. Pl·?:iSP IY(ll' back YES, NO, UNSURE. DETAILS. and/nr ~new namr , .
• \.JSF.R : YE~. Call thrm MUST-l\E-PRESF.NT, MUSTNOT-GE-PR ESENT. Mil \'-HE-PRESENT.

PUP: Too long Nrckn.1mf'd Must, 1\lmtnnt. May.

• PUP: Locatt>d :1 references to mod,·l's ft.·atures in code generated so f~r. In each cas!'. the rr.fcrrnct> has been replact>d by "(APPEND Must Mmtnot May)".

Tim ~~ PUI'ii :.t m be~t m.<l.mt: Jml thP. "nght" mf"t"n'r. at thl' "nr.hr" tunr.. Till' hunrhwls of mter-Btmg tr~n<fr·n ~n· m~~l.r.d : thP. spt<'tn .~l'l''~ars to type out JUSt wh:tt rs nr.cessary. The ur.xt few par;op·apln dispel! this falst illuwrn; thP.H' is no mystrry to PUP6's domg the nght things, and any r-vJ·irrll rh~logue rxcPrpt would be bonngly vtrbme.

Bl"came of liS ~. etH'sts from a ~ingle "experts mttting" protocol, thr PUPG pool of Brmt;< was (t) rasrly able to reproduct.' that "proper" dialo('.Uf', !Jut (u) mcapable of widely vattrd dtalogu!'s wnh the USP.r. Two amunpttom implicit in usmg thr. <tllllllatrd r·xpP.tts' dtscusston as a hter~l model turnl'd out to be senous: tht abrhttn of any actual user of PUPG must comctdl' wnh thosr~ of thl' user who was stmulated tn thl' protocol, and the order of and wordtng of the actualml't-'s comm~nts must closdy adhr.re to those of the user m tht protocol. Such dtfficulttes must be ovtrcoml' in any systl'm dt!signPd for wide ml'rship, but were considt>rl'd ignorable 111 the spenfic autom~ttc code gtntratton task at hand.

Also as a rr.sult of tim ~ppt o~ch to systt.'m sptcilication, each Btm!! had nnly those pat ts <pt·ctft·~d which it actually would ntr.d 111 the Pnsumg chalngue. P.ut of tht difficulty with ntw dralugues stemmed from thts mmtnHI complttion. In the protocol. when a dectsron was made by txptrts, the knowledgr necP.ssary to follow thP. Mltn alttrnatrvt branch was not ~tsP.d, nor wtrr sttch superfluous facts supphtd to the Btmgs in PUP6. Thus thP. user nf PUP6 must almost always rtsolvl' tach chotct thr way tht sunubtrd (protocol) ustr dtd. It is felt that rf all tht pans of all thP. Bemgs had bttn farthfully filltd m. tim problem would havt subsrded. Basrcally, tht dttliculty rs ont c·f modrlling ~II tht posstbly relevant knowledgl' an expt>rt has. ratht>r than (as was donl') just capturmg P.nough of Ius knowledge to do a few givl'n tasks.

Whilt all thr Bemgs' lllltracttons were mvisibll' to tht ustr, tht system still swampP.d him with data about what was ~omg on. FCtr txample. most of the enllltts ht was asked to name Wl'H' nr.ver tdl'nrd to agam hy name. The converst probll'm exr~tr.d as w~ll: il w~s nect·ssary to mclud~ a B~ing whrch stmulatr.d forg:r.tfuhlPss. to prrvrnt, r..g .. anaphora ~pannrng mmutrs of teal llml'. Om·u11ug the us~r wa~ not solved ~attsfactorally . Pornters 11110 a graph of generated code werr simul~trd, but oflf"n a user wrshed to refer to a piece of code not by nam~ or by porntmg. but by somt britf mtanin~ful (to him only') phrase.

Tht ~yst~m. PUP6, did eventually synthtsize CF, tht tarr:et conct'pt furm:ttton program. PUP6 was 200 pagts of INTER LISP[6]. CF was ~0 pa~. r.s long (G page~ whtn codtd by hand durmg the protocol). CF was gP.nerated in 60 cpu minutes (comprled, PDP-10 TENE:'\). Tht dralogue consisted of 300K characters typed by PUPG, and iK by the ustr. It occupitd ~00 pagts, and five hours of rtaltime.

Dt~pitr the lack of dialogut' n.~xtbtltty, it was ftlt that mo~t of thf' Bt!mgs could he ust.>ful 111 gtnerating othtr pro~:rarm . For tim tra~un, two .lddiltcttul target programs wrrf' ~pf'cifu·r'l . Thr.y wr.r r. ~yntlu;mrd With lillie chang~ to PUPG, hut nnly hy ~omrcmf' fanult~r wllh the system.

The ~l'conrl taq_:l'l prop. r:om, Gl. ts a grammattcal mfrr··n((' ptngr.1m, whiCh accqll~ mmg~ lahr.llr.d LECA L, II.LEGA I., or ~~- In the laner casr:. Cl mmt gutss tht lr·t:altty. lntrtnally, potrnllal ~rts nf 1 ulr.s are maintarnl'd. Of the orr~~111.1l pool, ·HI out of the S7 Bemg~ w~re u~td in synthe~rzmr. both tart(·'ts. Four totally n~w Bemgs had to be add rei, rf'lated ro for nul grammars ami rults. Unfortunately, lht! additron of any ntw Bemgs drmands that tht user be acqu~intrd with rhf' format convr·nllons of PUP6. Tht Cl pro~_ rarn g··m·t '''"'-' was ~0 pagr1 long: ,, hand .codP.d version was nnr-ftfrh that <ll<'

Pl.. was thr> fmal IMf',PI prtJ(: r;o·n .11lr.mptPd, a srmple )JI('f'' 'IIY lt ~ t tn:onrpul.ltor. It r<?l"':rt·?dl ·,· "''"l'ls rr.quests from 1 he mr>r to tmrll , mspt·ct, or dl'l··t·· ~omr> 1 r>cord(s). Any umpf'Ciflf'd hr.lds are trP.~tr.d it S don't-cares. so a ~implt pall~;rn . matdl"r h:od 10 bl' s~· nthc·med . Two 1\emgs had to br arldrrlto PUP6. Thr nnponant ptr.ce of d.lla 1~ that about half of the on~:mal PUPG pool of Betnp, s Wt'rt' actually used in r1// rt.ru target syuthesrzmg dralogur.·s.

As propo1rd rn St'ction 6, tht' Brrngs grneratl' other Brrnp, s. nP.VP.r plam funCIIons Tim explarns th~ huge inrreas~;~ 111 rarg~'t code lengths rn the PUP6 . versions compared to the vr.rsrons produced by h;ond whl'n srmulatang the <'Xpr.rts (who wrot" lht t~rgPt programs as functions). CF was a pool of '·G brand n~w Br>mp. Cl 37, and PL 2i. As with PIJPG. one can mterrupt the target programs as thty are runnmg and ask quP.strons. Any B~mg on the control stack will provide fully rnstanttated answr.rs to any of its 29 allowabiP. querrrs (ns part<); all other Btmgs wrll provide only hypothr>ttcal answrrs. Recall the t'XCP.rpt from CF itself runnmg. found in section ~ - 2 -

Somf? of thr> dtffkulll~s stf?m from th~ natlltf? of thP. task . In any Jon(: cltaiO!',Uf?, thf? mer often forgr.'IS, changes his mind. rns. r:-rc. A vNy ~opht.sllcated mr.r mod(') would be nP.cr:~ s ~t y to :occomodalr. tim ·~rrorfttl process rn a non. drbttegmg ~y~trm _ Wtthour such .rbthllr:s. thl' system itself may be led 11110 "'rror. Whrle most IJttgs arr avordable by carr.f11l record-l.r>rptng·. 11 provr>r1 tmrr:·<tltsllc to makt no provr~ion for debuggmg a n~w thtrty·page program. When a few errors did occur 111 CF, PUPG IIS(')f had to bl' alterl'd.

8. ConclusiQ.!l.!

What havf' WE' learned from this r.xpr>tlllll'tl!al study? Tht> ov~rall feasabrll!y of Btrngs was demonstrated, but the difficulties of commllntcatmg with the user madt> tht systtm almost rmpossrble to work with. The srt of qu('s!lons tht user was I'Xpt>ctt>d to want to ask is tht same as the SE't that ont Btrng can ask another: the Btrng parts. When the "nict" ustr in ten upts. l11s qur.s11ons are translatt>d trivtally into a ~imp It retneval. Rt>al users are seldom nice; tht Bemgs gentrally mmrndrr~toocl wh~t 11sers askrd .

To morlrfy PUP6 10 syntlwsiZl' nrw programs, it was ntceHary to add a few general-purpose proy,r.llnmrng and communtcallon Bemgs. plus add sr>veral F.r.tngs spl'crfic to tht new program's domam, plus r:enrrahze a f~w exrstrng 'Btings' parts. ThP. dralog11e to producr. the nrw program may bt poorly suited to that domam, smce most of the rt>cogmztd phrases Mem from a smgle (CF-producrng) protocoL

To tmpt ove PUPG's ptrformanc~. onr could add some dtbugging speci~hst Brrngs. some dialogue specrahm, some sophtsticated user psychology experts (why rs tht ustr asking me that quPstron, what nt>tdn't I tell hrm, how should I direct his attr>ntron). somr Berngs whose task ts to ard the untrainl'd usr.r in insrrtmg new domarn-sprctfic Bt>tngs. and perhaps a whole library of vaned spt>ctalt~t Gtmr,s.

~--'-~-~.bnut _[leinl:~

Tht perfot mance of the Crmr:s 1 P.pn·~rnt.Hron ttstlf in PUPii ~~mixed . Two advantag"s 1vo·n· hopr·d for by usm& a unrfonn ~et of Bemt: p.uts. Addlttou c·f nrw r.rrngs to tht pool was not rasy (for untrarnrd IISNS) h111 fommunica!lon amon~ r.~llr~;s nt<IS tasy (fast , natural). Two .ltlv.mta;;Ps wtrt hoprrl for by ktrpmg the Bernp hrghly structut;d_ The intf'l ~ct1011~ ("~fl"ll~lly with thl.' ml.'r) wrrl.' lmttle, but the compiP.x t a~k ~ put to thl' pool wrrr ~uccP.ssfully compll.'ted.

Th" 'rlpl'l"' ~~· problPIIIS arr. sr.rn to he with user-system cornlnllllH .1111111 , nnt with thP. l\rmp 1clca~ thl.'mselves. Soph1<t1c;o1o ·d. l"·~ · .. fro·,. progr .1m~ Wfl'<' gr.nr.r~trd, aftl.'r hours of f.111ly h1 i'.h I··VI'I tlt.ol"<'·"o' with an actll'l' usrr, after tens of tholl ' "'"' "' llll'~<:o : ·· ·< l'il» f'd :nnong tht· 11P.mp. Part of thl~ <11ro o'" I'· oll1 do111o d 111 di~ttlhllttn:~ tloo: ""~POII<ibihty for Wllllll!'. "'"'' .o11d '"" lo'CUi::IIIZIII)', ~o: Joov :owo.', to a hundred Plltllll'<. 1 ;otlw· 1h.111 h;lVIIl!', a r .. w cl'nlral monitors worry a bot II t'Vt'l \'I h111 :·:. Tho.' < Llllo.l:lrdtl~IIUII uf I'~''~ made filling in '"" lklll )'.<' t o.onto · nl~ f:urly patnlc~s .

What one r.r.uog~ ~ood for? For whtch tasks won't the problr·m~ ··nwullt·'lrd in PUPG rr.cm? Thl.' idea of a fixed set of l'atts (wlmh dtstlllt: lll~hl's them from ACTORs) is useful 1f rllf· mass oof knowlo·dge IS too hugr. for one mdlvidual to kr.ep "on tnp" of. It then should be orgamzcd 10 a very untfm m way (to s11nplify prrparmg it for storage), yet it must also lof' lughly struc!llred (to spePd up retnrval).

For thf's" reasons. the author is currl.'ntly invl.'stlgating, as a pntl'ntnl ra<k rlomarn, "rese~rch in !.'lementary number thl'ur y" Thrs has thP. addPd benefot of 1solatmg the problems 111 '"f'l'l'<r.llrarroon ri'SI'.ll'f.h from thr. srag;gf'ring complexities of na1011 al l.oll t·. ll af'." handling. Beinp arl.' big and slow, but valuahll' loor llrr: :·nlnng knowlrdt:r 111 ways meaningful to how It will lw 11<1'<1 . In the futun· Automated Mathl.'matician syqt·m, l'.t'lll('.< will I>·: nne ·· but not the only .. mternal mPlhani<m fot r~prr<Pntm~; and manipulatrng knowledge.

Reference_~

• [I] Crrr11, Waltlmgn, £la1stow, Ehchlagt·r, L!.'nat, McCune, Shaw, ~11d Srr.mbrrg, Progrrss Ref>ort on Program­ Undt'l stnndi11g S~stl'ms, Memo AIM -210, Stanford A r!lhual lntelltgr.ncc Laboratory, Au~;ust, 197i.
• Hempel. C~rl C., Fundnmrntals of Concrpt Formation in EmJ>iri<al Sci(ll((, Chtcago: U. Chicago, 1952.
• [:3] HP.witt, Carl, A U11iz,crsal Modular ACTOR Formalism for Artificial /ntdligCiur, Third International Joint ConfP.rP.ncP. on ArllficlallntelligP.nce, 1973, pp. 2~5-215.
• [i) Minsky, Marvm, Frnmt's, m (P. Winston, ed.) Psycholog-y of Comf·utcr Vision, New York: McCraw Hill, 1975.
• [5) Nl'wl'il, A., Prod11<fion S"iSII'ms: Models of Control Stm.-tu1n , 111 (W. Chasl.': ed.), l'imal Information Proas .< i11g, NPw York: Academic Press, 1973.
• Tr.Hrhn:.n, Wano·n, INTERLISP Rcjarncc Manual, X ER<.lX PA RC, Palo A Ito, Ca., 197i.
• Wimton, Patmk, Lnm1i11g S/luctu.ral Descriptions from Examf·ICJ, MIT PrOJP.Ct MAC, TR-231, September, 1970.
• (8] Wood~. W.A, and Makhoul, J.. Muhrmical lnfrrcnct Problems in Colltillli<'IIS Sprl'(h Ur1drrstanding, Third I.JCAI , 19i'·. pp. ~00- 207.

Many hours of crt?atrve diScussions wt'rc quite important. In particular, the author acknowledges C. Green, R. Waldinger, D. Shaw, and E. S~crrdot1. Computer time was generously providl.'d hy thP A rtifiliallntrlligence Center of SRI.

rum~ndix 1: A Typical BeiQg

WP. considf'r INFO·OBTAINER, a BP.mg whrch is independent of task rlom~in . P.dow is hsted, for t:'ach part, its abbreviated name (in bold), an English qu!.'st1on that 11 might (try to) answP.r, ~nd lhr. ~torP.d program whrch should try to answer It (oftP.n a simpiP. template or ~ constant). The percentages p:ivP.n indiCate how many of the (ultrm~tely 100) Beings in PI I P6 actu~lly IISI'd that part during the syntht>SIS of one of thP threP. targP.t programs

(.5 .5 ,') .5 .1)

A vector of utility mea~urrs . Tht' fir~~ compon~nt says that INFO-OBTAINER IS of averagr dtfliculty to call. Next, there exists a .5 chance that somr. desw1dant wtll call it again. Next: this activity almost always sucw:ds. The time/space usf'd rn allowrng tillS BP.rng to try IS ryp1cal. Fmally, there is no good reason for rnh1brtrn!?,' 11 I.'Vt'l'. In r;eneral, each component can be a progroJ>II, 1101 JUSt a constant. These weights, like the contents of all the parts of all the Beings initially in thP. f'Xpr.nmental PUPG system, were decided upon and inserted by hand.