![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to implement.ms CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / ucb / lisp / pearl|
Return to implement.ms CVS log | Up to [CSRG BSD Unix] / 43BSD / ucb / lisp / pearl |
1.1 root 1: .so /usr/lib/vlpmacs
2: .ND
3: .ds CH
4: .ds CF - % -
5: .po 1.00i
6: .nr LL 6.25i
7: .RP
8: .TL
9: .LG
10: The Implementation of PEARL
11: .SM
12: .sp 1
13: A Package for Efficient Access to
14: Representations in Lisp*
15: .FS
16: * This research was sponsored in part by the Office of Naval Research
17: under contract N00014-80-C-0732 and the National Science Foundation
18: under grant MCS79-06543.
19: .FE
20: .AU
21: Joseph Faletti
22: Robert Wilensky
23: .AI
24: Computer Science Division
25: Department of EECS
26: University of California, Berkeley
27: Berkeley, California 94720
28: .sp 1
29: March 1982
30: .AB
31: PEARL is an AI language developed with space and
32: time efficiencies in mind.
33: In addition to providing the usual facilities such as
34: slot-filler objects, demons and associative data bases,
35: PEARL introduces stronger typing on slots,
36: user-assisted hashing mechanisms, and a forest of data bases.
37: The resulting product is a simple but powerful and efficient
38: tool for AI research.
39: .AE
40: .NH
41: Introduction
42: .sp 3
43: .PP
44: We have developed an AI language called PEARL (Package for Efficient
45: Access to Representations in Lisp).
46: Unlike the recent tendency toward
47: elaborate representation languages such as KRL [1]
48: or language generators such as RRL [5], PEARL is
49: a more modest system that combines a number of useful
50: AI techniques into a very efficient package.
51: PEARL provides the user with a set of operators for defining, creating,
52: and manipulating slot-filler objects, as well as placing them into
53: associative data bases, upon which further operations may be performed.
54: Besides the usual goal of providing the user with a more meaningful
55: interface than is available via Lisp, PEARL has the following salient
56: characteristics:
57: .IP 1)
58: PEARL combines some features of predicate calculus-like data bases with
59: those of frame-based systems like FRL [9].
60: .IP 2)
61: PEARL introduces typing to user-defined knowledge structures.
62: .IP 3)
63: PEARL allows the user to manipulate a forest of associative
64: data bases implemented as hash tables.
65: .IP 4)
66: Fetches from the data base return streams of answers.
67: Retrieval is based on pattern matching.
68: .IP 5)
69: PEARL is very efficient.
70: PEARL uses its own internal representation
71: for knowledge structures for both economy of storage and speed.
72: A great deal of effort has gone into exploiting type information
73: not available in most AI languages to eliminate searching inefficiencies.
74: In addition, the user may easily specify, as part of a knowledge
75: structure definition, a great deal of information about how
76: objects should be indexed for efficient retrieval.
77: Thus PEARL provides much of the power
78: of expression of other AI languages without the usual overhead.
79: .LP
80: Perhaps most significantly, PEARL is actually being used in the
81: construction of several AI systems.
82: In particular, the latest version of PAM [12],
83: a story understanding program, has been re-programmed in PEARL.
84: PANDORA [13], a planning program now under development at Berkeley,
85: is also written in PEARL.
86: Our experience has led us to conclude that PEARL
87: is an effective AI tool for the creation of efficient AI programs.
88: .sp 3
89: .PP
90: The following is a quick overview of the paper:
91: First we present an overview of PEARL by discussing a sample session
92: which demonstrates the primary functions provided.
93: Next we present some measurements as evidence that PEARL is
94: indeed efficient.
95: The bulk of the paper then describes the details of each of PEARL's
96: main functions -- creating structures, the form of the data bases,
97: indicating indexing methods, fetching from the data bases, predicates
98: and matching, matching variables, and demons.
99: This is followed by descriptions of the various implementations of
100: PEARL and their relative speeds plus evidence that PEARL's hashing
101: mechanism does in fact speed up fetching.
102: Finally, we compare PEARL to its nearest cousins, FRL and KRL.
103: .NH
104: An Overview and Sample Application Of PEARL
105: .sp 3
106: .PP
107: In the section we give an overview of PEARL by presenting an
108: extended example of PEARL's use.
109: The example we will use to demonstrate the various features of
110: PEARL before going into each in more detail is a \fIvery simple\fR
111: inference mechanism based on forward and backward inferences rules.
112: In order to explain and motivate the various pieces of PEARL (and
113: Lisp) code, we present them in the order that one would most likely
114: design them, rather than the order that they must be entered
115: into PEARL. Afterwards, they would have to be moved around so
116: that things are defined before being referenced.
117: .sp 3
118: .PP
119: To implement the inference mechanism, we will want to ensure that
120: we perform forward inferences whenever we insert a concept into
121: the data base and backward inference whenever we fetch a concept
122: from the data base. The easiest way to accomplish this is to
123: create two demons, one for forward inference and one for backward
124: inference which will be run when insert and fetching respectively
125: happens. These will need to be attached to all concepts which we
126: want to make inferences from, so we need a \fIstructure\fR (PEARL's
127: name for a slot/filler object) which we will call \fIConcept\fR.
128: It will have no slots but will be used as the root of our
129: conceptual hierarchy so that all concepts can inherit the
130: inference demons from it.
131: (We will add these later when we know what their names are).
132: We do this in PEARL by declaring a \fIbase\fR structure called \fIConcept\fR:
133: .DS
134: (create base Concept)
135: .DE
136: .sp 3
137: .PP
138: We will then want to describe some of the concepts that we
139: wish to make inferences about.
140: For the purposes of this example, we will present only enough
141: information to use backward inference to determine that Samuel is
142: probably poor from the fact that he is a professor.
143: So we will want structures which describe a person, a professor,
144: a salary level, and being poor.
145: \fIPerson\fR is an expanded \fIConcept\fR;
146: that is, it should inherit everything not otherwise specified from
147: the structure \fIConcept\fR.
148: It will have one slot (for our current purposes) containing the
149: person's name which we will represent as a \fIsymbol\fR which is
150: used in PEARL for creating literals (that it, something with no
151: conceptual content):
152: .DS
153: .Ls
154: (create \kAexpanded Concept Person
155: \h'|\nAu'(* Name symbol))
156: .Le
157: .DE
158: .LP
159: Included in our definition is a special hashing mark (*) on the
160: Name slot which says that the value in this slot should be
161: helpful in indexing \fIPerson\fR structures.
162: This is true because we are likely to be asking questions of the
163: data base like "Is Samuel the name of a person?".
164: For example, suppose we have declared the symbol Samuel:
165: .DS
166: (symbol Samuel)
167: .DE
168: .LP
169: and asserted into the data base the fact that there is a person named
170: \fISamuel\fR by creating an individual instance of a \fIPerson\fR
171: with the \fIName\fR slot filled with the symbol \fISamuel\fR and
172: inserting it into the data base:
173: .DS
174: .Ls
175: (insertdb (create \kAindividual Person Sam
176: \h'|\nAu'(Name Samuel)))
177: .Le
178: .DE
179: .LP
180: (As a side effect of the above, the individual structure instance
181: \fI(Person (Name Samuel))\fR is stored in the Lisp atom \fISam\fR
182: for future use.)
183: The function \fIinsertdb\fR uses the hashing information we gave
184: for \fIPerson\fR to insert this structure in the data base in
185: two places: under the fact that it is a \fIPerson\fR which is
186: automatic for all structures and under the combination of
187: \fIPerson\fR and \fISamuel\fR because we bothered to provide
188: the extra information in our definition of \fIPerson\fR.
189: .sp 3
190: .PP
191: Now we can "phrase" the question "Is Samuel the name
192: of a person?" as:
193: .DS
194: .Ls
195: (setq Stream (fetch (create \kAindividual Person
196: \h'|\nAu'(Name Samuel)))
197: .Le
198: .DE
199: .LP
200: that is, by creating an individual \fIPerson\fR with name \fISamuel\fR,
201: and fetching it from the data base.
202: This returns a hash bucket from the data base which is chosen
203: based on two parts of our pattern: the fact that it is a
204: \fIPerson\fR structure (because this is always available)
205: plus the value in the Name slot (because we labelled this slot
206: in our definition of \fIPerson\fR.
207: Given this stream (virtual list) of possible matches, we ask
208: whether there is in fact something there which matches our pattern:
209: .DS
210: (setq Result (nextitem Stream))
211: .DE
212: .LP
213: If Result is \fInil\fR then the fact that Sam is a Person is not
214: in the data base.
215: If it is, then Result will contain the structure in the data base.
216: .sp 3
217: .PP
218: Similarly, we declare the structure \fIProfessor\fR,
219: a predicate about a (structure of type) \fIPerson\fR and
220: assert that Sam is a \fIProfessor\fR using the structure
221: value we stored in \fISam\fR before:
222: .DS
223: .Ls
224: (create \kAexpanded Concept Professor
225: \h'|\nAu'(* > Person Person))
226: (insertdb (create \kAindividual Professor
227: \h'|\nAu'(Person Sam)))
228: .Le
229: .DE
230: .sp 3
231: .PP
232: In choosing a way to index this structure, we consider the fact
233: that Person slot of \fIProfessor\fR will always contain a
234: \fIPerson\fR structure and thus the combination of \fIProfessor\fR
235: and \fIPerson\fR will not help to spread these out in our data base.
236: However, the value of the first marked slot \fIName\fR of Person will
237: contain widely varying information so the combination of
238: \fIProfessor\fR and this value will work well.
239: The hashing mark ">" instructs PEARL to do precisely this.
240: We also define \fISalary\fR, a relation between an \fIEmployee\fR
241: and a salary level:
242: .DS
243: .Ls
244: (create \kBexpanded Concept Salary
245: \h'|\nBu'\kA(* > Employee Person)
246: \h'|\nAu'( Level symbol))
247: .Le
248: .DE
249: .LP
250: Here the first slot is starred because we are likely to ask for
251: the salary of Sam.
252: If we were also likely to ask for all people with Low salaries,
253: then we would star the second slot also.
254: Finally, we define \fIPoor\fR, a predicate about a \fIPerson\fR:
255: .DS
256: .Ls
257: (create \kAexpanded Concept Poor
258: \h'|\nAu'(* > Person Person))
259: .Le
260: .DE
261: .LP
262: Having defined the types of objects we know about and the few
263: actual facts we know, we are ready to describe the inference
264: rules.
265: Forward rules say that if the value in the Fact slot is true then
266: the value in the Implies slot is true also.
267: We are likely to fetch them using Fact as a key, so we mark that
268: slot as useful in hashing:
269: .DS
270: .Ls
271: (create \kBbase ForwardRule
272: \h'|\nBu'\kA(* Fact Concept)
273: \h'|\nAu'( Implies Concept))
274: .Le
275: .DE
276: .LP
277: Backward rules say that if you want to know if the value in the Need
278: slot is true then check to see if the value in the LookFor slot is true:
279: .DS
280: .Ls
281: (create \kBbase BackwardRule
282: \h'|\nBu'\kA(* Need Concept)
283: \h'|\nAu'( LookFor Concept))
284: .Le
285: .DE
286: .LP
287: Finally, we need to add some rules to our data base.
288: Since we are likely to know a lot of inference rules and to want
289: to access them often, it would help to keep them in a different
290: data base separate from other facts to speed up access.
291: So we build a special data base just for inference rules:
292: .DS
293: (builddb *Rules*)
294: .DE
295: .LP
296: Then we insert some rules into it:
297: .DS
298: (symbol Low)
299: .DE
300: .DS
301: .Ls
302: \fI; If you want to know if someone is poor, check for a low pay level.\fP
303: (insertdb \kA(create \kBindividual BackwardRule
304: \h'|\nBu'\kC(Need (Poor (Person ?Person)))
305: \h'|\nCu'(LookFor (Salary \kB(Employee ?Person)
306: \h'|\nBu'(Level Low))))
307: \h'|\nAu'*Rules*)
308: .Le
309: .DE
310: .DS
311: .Ls
312: \fI; If you want to know if someone's pay level is low, check to\fP
313: \fI; see if they are a professor.\fP
314: (insertdb \kA(create \kDindividual BackwardRule
315: \h'|\nDu'\kB(Need (Salary \kC(Employee ?Person)
316: \h'|\nCu'(Level Low)))
317: \h'|\nBu'(LookFor (Professor (Person ?Person))))
318: \h'|\nAu'*Rules*)
319: .Le
320: .DE
321: .LP
322: Note in our rules that we use the pattern matching variable \fI?Person\fR.
323: In the first rule this ties together the person who is poor with the
324: person whose is paid at a low level.
325: In the second rule it ties together the person with low pay
326: to the professor.
327: Although these two rules have variables with the same name, no
328: naming conflict arises because most variables in PEARL are local
329: to the structure they are used in.
330: .sp 3
331: .PP
332: Next we are in a position to say how to make forward inferences:
333: .DS
334: .Ls
335: \fI; MakeForwardInference is a demon, triggered by insertions into the\fP
336: \fI; data base, which fetches forward inference rules predicated upon\fP
337: \fI; the Fact being inserted and inserts the implications from the\fP
338: \fI; rule into the data base.\fP
339: (de \kDMakeForwardInference (Fact)
340: \h'|\nDu'(prog \kC(Rules Rule)
341: \h'|\nCu'\kB(setq \kDRules
342: \h'|\nDu'(fetch \kA(create \kCpattern ForwardRule
343: \h'|\nCu'(Fact Fact))
344: \h'|\nAu'*Rules*))
345: \h'|\nBu'(while \kA(setq Rule (nextitem Rules))
346: \h'|\nAu'(insertdb (path get Rule 'Implies)))))
347: .Le
348: .DE
349: .LP
350: This says to fetch all forward inference rules with the new fact
351: in the Fact slot and assert each of their associated Implies slots.
352: .sp 3
353: .PP
354: Making backward inferences is similar but a bit more complex
355: because we want it to stop right away if it succeeds:
356: .DS
357: .Ls
358: \fI; MakeBackwardInference is a demon, triggered by fetches from the\fP
359: \fI; data base which fetches backward inference rules whose Need\fP
360: \fI; slot contains the Fact being inserted and fetches the value\fP
361: \fI; of the rule's LookFor slot from the data base until one succeeds.\fP
362: (de \kBMakeBackwardInference (Fact)
363: \h'|\nBu'(prog \kA(Rules Rule Found Try)
364: \h'|\nAu'\kC(setq Rules (fetch \kD(create \kBpattern BackwardRule
365: \h'|\nBu'(Need Fact))
366: \h'|\nDu'*Rules*))
367: \h'|\nCu'\kD(setq Found nil)
368: \h'|\nDu'\kA(while \kB(and \kC(not Found)
369: \h'|\nCu'(setq Rule (nextitem Rules)))
370: \h'|\nBu'\kC\fI; Get the LookFor slot's value.\fP
371: \h'|\nCu'\kB(setq Try (path get Rule 'LookFor))
372: \h'|\nBu'(cond (\kC(nextitem (fetch Try))
373: \h'|\nCu'\kB(insertdb Fact)
374: \h'|\nBu'(setq Found t))))
375: \h'|\nAu'(return Found)))
376: .Le
377: .DE
378: .LP
379: Finally, we can finish our description of \fIConcept\fR by saying
380: that all concepts inserted into the data base should run the demon
381: MakeForwardInference after the insertion has been performed (">insertdb").
382: All concepts fetched from the data base should run MakeBackwardInference
383: \fIbefore\fR the fetch has been performed ("<fetch"):
384: .DS
385: .Ls
386: (create \kBbase Concept
387: \h'|\nBu'(if \kA>insertdb MakeForwardInference
388: \h'|\nAu'<fetch MakeBackwardInference))
389: .Le
390: .DE
391: .LP
392: Now we "phrase" our question "Is Sam poor?" as a pattern:
393: .DS
394: .Ls
395: (create \kApattern Poor NeededFact
396: \h'|\nAu'(Person Sam))
397: .Le
398: .DE
399: .LP
400: This fact is not in the data base.
401: However, upon fetching it:
402: .DS
403: (nextitem (fetch NeededFact))
404: .DE
405: .LP
406: Our two backward inference rules will be used by our backward
407: inference demon and the desired fact will have been inserted into
408: the data base before the fetch does its job.
409: .sp 3
410: .PP
411: This example demonstrates a good deal of what PEARL can do and
412: gives the flavor of its use.
413: After presenting some measurements of its speed, we will discuss
414: each of its features in more detail and describe their
415: implementations.
416: .sp 3
417: .PP
418: The above example was described as a user would design and enter
419: code into a file to be read into PEARL.
420: This is the normal mode for experienced users of PEARL, just as it
421: is for Lisp programmers.
422: PEARL can also be used interactively since it is
423: built on top of Lisp.
424: However, PEARL constructs objects which Lisp does not know how
425: to print intelligibly.
426: To remedy this, the read-eval-print loop of Lisp has been modified
427: to deal with PEARL objects and uses PEARL's print function to
428: print a readable representation of them.
429: To help demonstrate what it is like to use PEARL interactively,
430: the examples in later sections use italics to indicate those things
431: typed by PEARL during an interactive session and bold face to
432: indicate those things typed by the user.
433: To remind the users that they are using PEARL
434: rather than Lisp, the prompt has been changed to \fIpearl>\fR.
435: .NH
436: How Fast Is PEARL?
437: .sp 3
438: .PP
439: PEARL achieves its space efficiency and some of its time efficiency
440: by requesting a block of memory from Lisp for each structure
441: instance or definition.
442: The contents or defining information are then packed within
443: this block.
444: Since much of the defining information is Boolean,
445: this provides substantial savings in space for definitions.
446: Data bases are managed similarly.
447: .sp 3
448: .PP
449: As a rough measure of PEARL's execution speed on the PDP-10,
450: we created a test data base of 4000 structures, in which the
451: average unsuccessful query took 0.0042 CPU seconds (237 per
452: second) and the average successful query took 0.0073 CPU seconds
453: (136 per second).
454: Note that PEARL's hashing mechanism results in particularly fast
455: determination of failure.
456: As another measure of PEARL's execution speed, we
457: compared the original implementation of PAM [12] written purely in Lisp
458: (with no special consideration for efficiency)
459: with the current implementation which uses PEARL.
460: The average time required by the original to process a single
461: sentence in a 5-sentence story was 5.6 CPU seconds.
462: The new version, which builds a more complete representation of
463: the overall structure of the story and uses a significantly
464: larger collection of knowledge, requires an average of only
465: 0.56 CPU seconds per sentence in a 23-sentence story.
466: .sp 3
467: .PP
468: For measurements demonstrating the effectiveness of the hashing,
469: and comparisons between various implementations, see the section
470: below on performance.
471: .NH
472: Objects and Structures
473: .sp 3
474: .PP
475: PEARL has four basic types: \fIinteger\fR, \fIsymbol\fR, \fIstructure\fR,
476: and \fIlisp\fR.
477: Objects of type \fBinteger\fR are the usual numeric type, and objects
478: of type \fBlisp\fR can be any non-atomic Lisp object.
479: \fBSymbols\fR (objects of type \fIsymbol\fR) correspond to atoms in Lisp,
480: and are simply primitive objects with predeclared unique labels.
481: There is a special built-in symbol \fBnilsym\fR
482: (corresponding to \fInil\fR when considered as an atom)
483: which denotes a value of type symbol carrying no special conceptual
484: information, that is, devoid of meaning.
485: \fBStructures\fR are collections of slots.
486: Each slot of a structure
487: may be filled with an object of one of the four types.
488: There is also a meta-type for slots, \fBsetof\fR,
489: which can be applied (recursively) to any basic type to generate a new type,
490: which will consist of a list of the specified type of objects.
491: There is a special built-in structure \fBnilstruct\fR respresenting
492: the standard empty structure (similar to \fInil\fR when considered
493: as the empty list).
494: .sp 3
495: .PP
496: Types of structures must be predefined, with the number of slots, and
497: their names and types specified via a user declaration.
498: When an instance
499: of a structure is created and its slots filled, only objects with the
500: same type as the slot may fill it.
501: In addition, new structures may
502: build upon old ones in a hierarchical fashion by specifying new slots
503: to add to the old ones.
504: This hierarchy may be used in operations upon the data base.
505: .sp 3
506: .PP
507: Since the data bases are hash tables (to be described in
508: more detail later), each symbol and type of structure is assigned
509: a unique integer at definition time to be used by the hash function
510: to compute a location in the hash table.
511: This contributes significantly to the speed of data base operations
512: in PEARL since it allows the hash function
513: to be a simple computation based on these numbers rather than
514: depending on the spelling of the names.
515: It also helps to prevent
516: structures with similar names from being hashed in similar ways.
517: In particular, the unique numbers 0 and 1 are automatically
518: assigned to \fInilsym\fR and \fInilstruct\fR.
519: .sp 3
520: .PP
521: For example, symbols are declared as follows:
522: .DS
523: \fIpearl>\fB(symbol John Home Here)
524: \fI(John Home Here)\fR
525: .DE
526: .LP
527: This call to \fIsymbol\fR sets up three unique objects whose print
528: names are "John", "Home", and "Here" and associates with
529: them the next three unique integers (2, 3, and 4).
530: Note that the value returned is a \fIlist of the symbols created\fR,
531: not a list of Lisp atoms and PEARL's print function prints this
532: value out as \fI(John Home Here)\fR.
533: .sp 3
534: .PP
535: The internal structure built by \fIsymbol\fR is a hunk of memory
536: big enough for two pointers pointing to the name and unique number.
537: .DS
538: Internal representat\kaion of the symbol John:
539:
540: s:John ---> \h'|\nau'Unique Number \kb---|---> 2
541: \h'|\nau'Print Name \h'|\nbu'---|---> John
542:
543: .DE
544: .LP
545: Although we generally chose to use hunks of memory where possible
546: to save space (as demonstrated below), this representation
547: saves no space since it is equivalent to a cons-cell.
548: However, we chose to build it as a hunk and not a cons-cell since
549: in this way, PEARL can more easily distinguish it as a symbol
550: rather than a list cell.
551: The atom \fIs:John\fR is created with its value
552: set to the symbol John so that this unique symbol can be
553: generated at a later time, leaving the atom \fIJohn\fR available for
554: use by the user.
555: .sp 3
556: .PP
557: New types of structures and instances of previously defined
558: types of structures are all created with the function \fBcreate\fR.
559: The statement
560: .DS
561: \fIpearl>\fB(create base Act
562: (Actor symbol) )
563: \fI(Act (Actor nilsym))\fR
564: .DE
565: .LP
566: will define the primitive type \fIAct\fR with one slot named
567: \fIActor\fR and containing any single object of type symbol.
568: At the same time, \fIcreate\fR produces and returns an individual
569: instance known as the \fBdefault-instance\fR which contains the
570: standard default values for each slot.
571: PEARL also provides a
572: mechanism for changing these default values at definition time.
573: In this case, the slot Actor contains the default symbol \fInilsym\fR.
574: The other defaults are \fInilstruct\fR for structures, zero for integers
575: and \fInil\fR for slots of type \fIlisp\fR or \fIsetof\fR.
576: Again, the object returned by \fIcreate\fR is an internally represented
577: structure, not a list.
578: The representation of the definition and default-instance structures
579: internally as hunks of memory is as follows:
580: .DS
581: \klStructure definition for\km Act Default-instance for Act
582:
583: \h'|\nmu' <--------\kn|
584: \h'|\nlu'Unique Number \h'|\nmu'---|---> 5 \h'|\nnu'|----|---\koDefinition
585: \h'|\nlu'Length \h'|\nmu'---|---> 1 \h'|\nou'Var-List \kp---|---> nil
586: \h'|\nlu'Default Instance\h'|\nmu'---|---------->\h'|\nou'Var-List Copy \h'|\npu'---|---> nil
587: \h'|\nlu'Isa \h'|\nmu'---|---> nil
588: \h'|\nlu'Print Name \h'|\nmu'---|---> Act \h'|\nou'Value or Var Name \h'|\npu'---|---> nilsym
589: \h'|\nlu'Hash Alias \h'|\nmu'---|---> 0 \h'|\nou'Var-Value Pair \h'|\npu'---|---> nil
590: \h'|\nlu'Expansion List \h'|\nmu'---|---> nil \h'|\nou'Predicate List \h'|\npu'---|---> nil
591: \h'|\nlu'Base Ifs \h'|\nmu'---|---> nil \h'|\nou'Slot If List \h'|\npu'---|---> nil
592:
593: \h'|\nlu'Hash Information\h'|\nmu'---|---> 0 \h'|\nou' ^
594: \h'|\nlu'Type Number \h'|\nmu'---|---> 0 \h'|\nou' |
595: \h'|\nlu'Slot Print Name\h'|\nmu'---|---> Actor \h'|\nou'i:Act
596: \h'|\nlu'PP Set Info \h'|\nmu'---|---> nil
597: \h'|\nmu' ^
598: \h'|\nmu' |
599: \h'|\nmu'd:Act
600: .DE
601: .LP
602: There are many values in the above structure which are not yet
603: important to our discussion and which will be explained later.
604: The key values so far in the definition information are the unique
605: number, length of the structure (number of slots), the default
606: instance, and the print names of the structure itself and of its slot(s).
607: In the default instance note that a pointer to the definition is
608: kept in each instance to allow quick access to the unique number,
609: and other information during hashing and matching.
610: This means that the only time that a definition must be
611: accessed through its special atom (\fId:Act\fR in this case)
612: is when a new instance is created.
613: .sp 3
614: .PP
615: The most important feature of this representation however, is the
616: speed gained by the use of hunks.
617: In order to represent this
618: information as an S-expression, we would need one cons-cell (space
619: for two pointers) per piece of information with half of this space
620: wasted on the pointer to the next cons-cell.
621: Accessing a particular piece of information would require
622: \fIcdr\fRing down the list an appropriate number of times
623: which is potentially quite slow with a larger number of slots.
624: Also, since this definition information is pointed to by all
625: instances, the uniqueness of at least its header
626: cell must be maintained requiring some extra effort on the
627: part of the programmer in Lisp.
628: However, given the cost of a cons-cell in terms of garbage
629: collection time, it would be best to maintain the uniqueness
630: of all of its parts.
631: .sp 3
632: .PP
633: By using a hunk, we can
634: .IP 1)
635: easily guarantee the uniqueness of a definition or instance,
636: .IP 2)
637: save the space used by list pointers, thus using half the space,
638: .IP 3)
639: use no new cons-cells after a structure is created,
640: .IP 4)
641: access any piece of a structure in constant time
642: (essentially two adds and a multiply at the worst), and
643: .IP 5)
644: compile all access operations relatively efficiently.
645: .LP
646: Thus, the use of hunks rather than lists contributes significantly
647: to the speed of PEARL.
648: .sp 3
649: .PP
650: Once we have defined the \fIbase\fR structure Act,
651: we can define more specific forms of Acts in terms of
652: it, using the \fBexpanded\fR argument to \fIcreate\fR in
653: place of \fIbase\fR:
654: .DS
655: \fIpearl>\fB(create expanded Act Trans
656: (From symbol)
657: (To symbol))
658: \fI(Trans (Actor nilsym)
659: (From nilsym)
660: (To nilsym))\fR
661: .DE
662: .LP
663: Here, we are declaring that Transes (transfers) are Acts with
664: two additional slots for the initial location From and the final
665: location To which are both symbols.
666: In addition to the information
667: diagrammed above, the structure definitions for Act and Trans are now
668: connected via their Isa and Expansion List fields (that is, the Isa
669: field of Trans points to Act and Trans is an element of the
670: Expansion List field of Act.
671: In this way, a complete tree of the
672: concept hierarchy rooted at a base structure is accessible from any
673: element in that hierarchy.
674: .sp 3
675: .PP
676: This hierarchy can be expanded to any depth.
677: Thus, we can now further
678: differentiate between various kinds of transfers, defining mental
679: transfers (MTrans) and physical transfers (PTrans).
680: In MTrans, the
681: mental object MObject slot will contain another concept and is thus
682: of type structure:
683: .DS
684: \fIpearl>\fB(create expanded Trans MTrans
685: (MObject struct))
686: \fI(MTrans (Actor nilsym)
687: (From nilsym)
688: (To nilsym)
689: (MObject (nilstruct)))\fR
690: .DE
691: .DS
692: \fIpearl>\fB(create expanded Trans PTrans
693: (From Here)
694: (Object symbol))
695: \fI(PTrans (Actor nilsym)
696: (From Here)
697: (To nilsym)
698: (Object nilsym))\fR
699: .DE
700: .LP
701: Slots which are not filled by the user when creating
702: an individual are filled in automatically with the default value
703: from the default instance.
704: Note in the definition of PTrans that we give the
705: default value of \fIHere\fR for the previously defined slot
706: \fIFrom\fR by simply including the slot and its new value.
707: This means that whenever we create an \fIindividual\fR instance
708: of PTrans but do not specify a value for the From slot, it will
709: be filled in with the value Here:
710: .DS
711: \fIpearl>\fB(create individual PTrans
712: (Actor John)
713: (Object John)
714: (To Home))
715: \fI(PTrans (Actor John)
716: (From Here)
717: (To Home)
718: (Object John))\fR
719: .DE
720: .LP
721: This last structure denotes "John went home (from here)" in Schank's
722: Conceptual Dependency [11] theory of representation.
723: These representations are used in the rest of the paper simply
724: as an example of PEARL's use.
725: However, PEARL makes no commitment to any
726: particular set of predicates or primitives and can be used equally
727: well with any type of slot-filler structure.
728: .sp 3
729: .PP
730: Slots within a structure may also be filled with a
731: pattern-matching variable, in which case the structure may
732: be viewed as a pattern.
733: The simplest form of pattern is one in which any unspecified
734: slots are filled with the \fImatch-anything\fR variable \fI?*any*\fR.
735: For example, a pattern matching any PTranses performed by John
736: could be defined as follows:
737: .DS
738: \fIpearl>\fB(create pattern PTrans
739: (Actor John))
740: \fI(PTrans (Actor John)
741: (From ?*any*)
742: (To ?*any*)
743: (Object ?*any*))\fR
744: .DE
745: .LP
746: However, \fBany\fR individual PEARL structure, including one with
747: all of its slots filled with actual values, can be used as a
748: pattern.
749: Thus, the first individual PTrans created above is
750: a pattern which matches only instances of John Ptransing home
751: from Here.
752: The sole purpose of using the \fIpattern\fR option to
753: \fIcreate\fR rather than \fIindividual\fR is
754: to change the default value for all types of slots to \fI?*any*\fR.
755: Variables are indicated by preceding them with a question mark
756: as in ?X for the variable X and, other than \fI?*any*\fR, they are
757: bound as part of the matching process (usually during a
758: fetch from the data base) which is discussed further below.
759: PEARL also provides functions for accessing and changing the
760: values of slots within individual structures
761: and for automatically naming the structure created.
762: .sp 3
763: .PP
764: Variables come in two other flavors in PEARL and are discussed in more
765: detail in the sections on matching and variables.
766: .NH
767: Data Base Facilities
768: .sp 3
769: .PP
770: PEARL allows for a forest of associative data bases
771: into which structures may be placed, and later fetched
772: via structure patterns.
773: Since many AI programs spend a significant part of their time
774: searching for knowledge in growing data bases, this needs to
775: be as efficient as possible.
776: .sp 3
777: .PP
778: Hashing is the usual programming solution to accessing a particular
779: element from within a large set.
780: However, traditionally, hashing has two prerequisites that are seldom
781: easy for an AI programmer to meet:
782: .IP 1)
783: The hash function must be carefully chosen in
784: advance to do a good job of spreading out the items to be inserted
785: with a minimum of computation.
786: In traditional applications of hash tables, this meant finding
787: a function which converts a (set of) string(s) into an index.
788: .IP 2)
789: Only completely specified items can be searched for.
790: That is, one may
791: not ask of a hash table "Find the closest one to X".
792: .LP
793: Unfortunately, since the knowledge structures used in AI are
794: much more complex than simple strings, finding a good hash
795: function is very difficult.
796: Also, in AI programming, normal hashing would only handle fetching
797: a particular fact from the data base, which would make the fetching
798: mean "Is this (completely specified) fact true?"
799: But it is much more likely that what is wanted is the (set of) thing(s)
800: which match a much more general pattern.
801: .sp 3
802: .PP
803: For these reasons, hashing in the normal sense is
804: inappropriate for AI data bases.
805: As a result, the traditional solution to the need for efficient
806: indexing into an AI data base is the discrimination net.
807: Or, in some cases, the data base is reduced to a linear list with
808: its inefficiency ignored (or tolerated).
809: With a discrimination net, the user often must carefully determine
810: the structure of the net and the nature of the tests to be made at
811: each level.
812: This is necessary to reduce the breadth of the net at each level,
813: since a discrimination net usually implies a linear search through
814: the possible values at each branch point.
815: As the knowledge changes, the representation hierarchy must change
816: to avoid this breadth problem, drawing the programmer away from the
817: problem at hand into worrying about indexing every step of the way
818: and forcing the representation into unnatural distinctions.
819: Generalized pattern matching is also difficult, making questions
820: like "What in the data base is close to X?" hard to ask.
821: .sp 3
822: .PP
823: Thus, a common problem with most AI data base implementations
824: is the system's lack of knowledge about how best to automatically
825: organize information for efficient and flexible retrieval.
826: The user usually has such knowledge, but needs to be able to provide
827: it in an easy way.
828: Moreover, if possible, this knowledge should be used to build a
829: hash table with its attendant speed, rather than a discrimination net.
830: The system must then provide a hash function which is
831: flexible enough to handle a large range of objects.
832: Such a hash table must also be organized in such a way that items may
833: be found which match a general pattern.
834: .sp 3
835: .PP
836: PEARL provides such a hash table and hash function, designed in such a
837: way that the user gets a significant speed up with only the effort
838: required to define objects as already been described above.
839: In addition, PEARL encourages the user to provide as much extra
840: knowledge as possible when a structure type is defined.
841: The choice of a particular structure hierarchy does not affect the
842: efficiency of the hashing so the representations are not twisted
843: to achieve efficiency.
844: Since the purpose of a hash function is to scatter
845: similar items, the required information consists of
846: indicating those slots whose values are most likely
847: to distinguish two similar structures.
848: .sp 3
849: .PP
850: This information is provided in the form of labels on
851: these slots in the definition of the structure.
852: Since only symbols and structures are assigned a unique integer at
853: definition time, slots of type \fIsymbol\fR, \fIstructure\fR
854: and \fIinteger\fR may contain such hashing information but slots
855: of type \fIlisp\fR may not.
856: These labels specify ways in which the unique number of the item being
857: hashed may be combined with the unique numbers associated with the
858: values of the labelled slots to provide a set of one, two, or three
859: numbers to be combined into an index into the hash table.
860: The particular ways of specifying these slots and the
861: ways of grouping them is described below,
862: but first we describe the form of a single data base and
863: the organization of a forest of data bases.
864: .sp 3
865: .PP
866: Each data base is implemented as a pair of hash tables in which
867: each bucket is a list of the objects hashing to that spot.
868: The possible sizes of the data bases are chosen from the set of primes
869: which are just barely smaller than the powers of two,
870: (that is, 1, 3, 7, 13, 29, 61, 127, ...).
871: The two hash tables are chosen to be off by a factor of four,
872: (that is, 1+7, 3+13, ... 29+127, ...).
873: The two data bases are chosen to be of different sizes because
874: it was hard to find a hash function to provide a good spread
875: in a large table for single small integers like the unique numbers
876: associated with structures.
877: The currently-used hash functions can be described as follows:
878: .DS
879: Let Size1 and Size2 be the sizes of the two hash tables.
880: Then the hash functions are:
881:
882: For indexes based on one number X:
883: X mod Size1
884: For indexes based on two numbers X and Y:
885: (4096 * Y + X ) mod Size2
886: For indexes based on three numbers X, Y and Z:
887: ( (4096 * 4096 * Z) + (4096 * Y) + X ) mod Size2
888: .DE
889: .LP
890: Thus the smaller of the two hash tables is used to enter
891: items indexed under only one unique number.
892: The larger is used for items indexed under combinations of
893: two or three numbers.
894: The sizes for hash tables can be chosen by the user to match the
895: number and variety of objects, the number of data bases being used
896: and the size of their machine's memory.
897: .sp 3
898: .PP
899: In order to allow flexible fetching using a pattern which is only
900: partly specified, and since the place we look must be determined based
901: upon the information that \fIis\fR provided in the pattern,
902: an item must be placed everywhere we are likely to be able to
903: look for it.
904: Thus, PEARL will index all individual instances of a structure type
905: which are inserted into the data base
906: under as many different hashing strategies as it can,
907: using the information provided by the user in the
908: definition of that type of structure.
909: Then to fetch with a particular pattern, PEARL need only use one of
910: the hashing strategies which uses slots from the pattern whose
911: values are considered hashable.
912: .sp 3
913: .PP
914: Whether there is hashing information or not, all individuals are
915: indexed in the smaller data base under (the unique integer
916: assigned to) their structure type.
917: Thus, with no effort, the user automatically gets one level
918: of distinction which provides a significant improvement
919: in efficiency over the often-used linked list.
920: This minimal use of hashing in PEARL is also an
921: improvement over discrimination nets since nets usually
922: imply a linear search through the possible values at each
923: branch point of the net instead of random access.
924: Of course, if the number of types of structures is
925: larger than the size of the data base, then after this random access,
926: there is still potentially a list of items to be searched linearly.
927: .sp 3
928: .PP
929: At this point, the speed with which the matching process
930: eliminates structures of the wrong type becomes important.
931: But the easily available unique number in each item provides a quick
932: test to eliminate items of the wrong type.
933: (For a complete description of the matching process, see the section on
934: predicates and matching.)
935: .sp 3
936: .PP
937: However, no amount of speed-up of the matching process can help as
938: much as a greater degree of discrimination by the hash function.
939: So to improve upon this automatic type of hashing, PEARL
940: needs to know which slots or collections of slots of a structure
941: are likely to help split up objects of the same type.
942: We will now describe each of the available hashing methods and the
943: circumstances in which you would want to use them.
944: .sp 3
945: .PP
946: The simplest case of adding hashing information is to label slots
947: whose values, in combination with the type of structure, would provide
948: a good distinction.
949: To indicate that a particular slot is useful in this way,
950: the user puts an asterisk (*) in that slot in the declaration.
951: Thus
952: .DS
953: \fIpearl>\fB(create base PlanFor
954: (* Goal struct)
955: ( Plan struct))
956: \fI(PlanFor (Goal (nilstruct))
957: (Plan (nilstruct)))\fR
958: .DE
959: .LP
960: defines a type PlanFor with slots for a goal and a plan, and indicates that
961: PlanFors should be indexed to be retrieved by the content of
962: their Goal slot plus the fact that they are PlanFors.
963: PEARL then uses the unique integers associated with the PlanFor
964: type and with whatever type of value is in the Goal slot.
965: .sp 3
966: .PP
967: Since the object filling the Goal slot of a PlanFor will always be
968: a structure of type Goal, using an asterisk in the Goal slot will not
969: actually distinguish PlanFors from one another.
970: In this case, we may
971: also wish to specify that the value that fills the Goal slot is to be
972: used to in a slightly different way to create the index.
973: For example, if the Objective of the Goal
974: is deemed more significant for such purposes than the fact that it
975: is a Goal, we can indicate this as follows:
976: .DS
977: \fIpearl>\fB(create base Goal
978: ( Planner symbol)
979: (& Objective struct))
980: \fI(Goal (Planner nilsym)
981: (Objective (nilstruct)))\fR
982: .DE
983: .LP
984: This will inform PEARL that structures that indexing on slots
985: in other structures which are filled with Goal-type structures
986: should instead use the Objective slot for further discriminations.
987: Thus, Goals change the way in which other structures use them to
988: index but the way in which Goals themselves are indexed
989: will not be affected.
990: This hash labelling of Goal is called \fBhash aliasing\fR and
991: will cause all PlanFors to be indexed
992: under the number for the PlanFor type plus the number for the type of value in
993: the Objective slot of the Goal, and thus all PlanFor's for Goals for a
994: particular type of Objective will be indexed in the same bucket.
995: As a short hand, the phrase "indexed under the number for the PlanFor
996: type plus the number for the type of value in the Objective slot of
997: Goal" is abbreviated as "PlanFor + Objective(Goal)"
998: .sp 3
999: .PP
1000: It might be the case that PlanFor was the only structure
1001: indexed based on Goals which would benefit from this and that
1002: some structures would actually be hurt by this because they
1003: expected Goals to be only one of many types of values.
1004: In this case, putting the control of how Goals get used by
1005: other structures into the definition of Goal is a bad idea.
1006: Instead, the control can be moved up into only the
1007: problematic structures.
1008: These structures can simply add the ">" hash label to
1009: a starred slot, causing PEARL to use the first starred slot of
1010: the slot-filling structure instead of its type.
1011: .DS
1012: \fIpearl>\fB(create base Goal
1013: (Planner symbol)
1014: (* Objective struct))
1015: \fI(Goal (Planner nilsym)
1016: (Objective (nilstruct)))\fR
1017: .DE
1018: .DS
1019: \fIpearl>\fB(create base PlanFor
1020: (* > Goal struct)
1021: (Plan struct))
1022: \fI(PlanFor (Goal (nilstruct))
1023: (Plan (nilstruct)))\fR
1024: .DE
1025: .LP
1026: If the user wanted to also star the Planner slot of Goal,
1027: but wanted the Objective slot to be used in cases where the
1028: containing structure had a ">",
1029: then the use of an "^" on the Objective slot will allow that:
1030: .DS
1031: \fIpearl>\fB(create base Goal
1032: (* Planner symbol)
1033: (* ^ Objective struct))
1034: \fI(Goal (Planner nilsym)
1035: (Objective (nilstruct)))\fR
1036: .DE
1037: .LP
1038: thus allowing Goals inserted directly into the data base to be
1039: indexed by the combinations (Goal + Planner(Goal)) and
1040: (Goal + Objective(Goal)) while objects containing Goals would
1041: use the Objective slot rather than Goal (Object + Objective(Goal)).
1042: If most structures containing Goals would benefit from the use of
1043: the hash aliasing label & in Goal, but only one or two are hurt by it,
1044: the use of "&" in Goal can be overridden by the structures
1045: which will contain Goals by adding the "<" hash label to the starred
1046: slot, thus giving the controlling structure the last word over how
1047: it is hashed.
1048: .DS
1049: \fIpearl>\fB(create base Goal
1050: ( Planner symbol)
1051: (& Objective struct))
1052: \fI(Goal (Planner nilsym)
1053: (Objective (nilstruct)))\fR
1054: .DE
1055: .DS
1056: \fIpearl>\fB(create base OffendedStructure
1057: (* < Slot struct))
1058: \fI(OffendedStructure (Slot nilstruct)))\fR
1059: .DE
1060: .sp 3
1061: .PP
1062: The above methods are all designed to allow the indexing of a
1063: structure to be based upon the type of structure and the type of the
1064: value of one slot.
1065: There are sometimes cases where one slot is not
1066: enough to distinguish items sufficiently but two slots would do a much
1067: better job.
1068: For example, a program which dealt with a large number of
1069: Goals of several planners might want to be able to ask whether a
1070: particular planner had a particular objective.
1071: Putting an asterisk in each of the slots of Goal would allow
1072: hashing by one or the other, but it would be even faster to use the
1073: fact it was a Goal, plus the values of both the Planner and Objective
1074: slots.
1075: Labelling this pair of slots with "**" causes their values
1076: plus the structure type to be combined into an index.
1077: .DS
1078: \fIpearl>\fB(create base Goal
1079: (* ** Planner symbol)
1080: (* ** Objective struct) )
1081: \fI(Goal (Planner nilsym)
1082: (Objective (nilstruct) ) )\fR
1083: .DE
1084: .LP
1085: This is also useful whenever the range of types of values in
1086: each slot is limited but the combinations of the two
1087: have a wider range.
1088: .sp 3
1089: .PP
1090: On the other hand, it may sometimes be useful to know all
1091: structures containing a particular type of value in any prominent
1092: slots.
1093: Thus for example, if a program has many kinds of structures all
1094: containing references to individual planners, it might be useful
1095: to be able to efficiently ask the question "What do I know about
1096: John?".
1097: In this case, the use of a ":" hash label on those slots of relevant
1098: structures which contain Planners causes all those
1099: structure to be indexed by that slot's value only, without
1100: regard to the structure type.
1101: This would result in some bucket in the smaller data base to contain
1102: all structures which refer to John in such a labelled slot,
1103: because they would all be indexed under that single value.
1104: Note that this is similar to the "&" type of hashing,
1105: but affects the structure itself instead of containing structures.
1106: .sp 3
1107: .PP
1108: Finally, there is a hash labelling which is the combination
1109: of these last two ideas.
1110: It may sometimes be useful to know all structures containing a two
1111: particular types of values in prominent slots.
1112: Thus for example, if a program has many kinds of acts and states
1113: all containing references to individual person/object and the time
1114: of occurrence, it might be useful to be able to efficiently ask
1115: the question "What did John do at 8 o'clock?".
1116: Thus, the use of a single pair of slots (in each structure) labelled
1117: with "::" causes the value of those two slots to be combined
1118: into an index.
1119: .DS
1120: \fIpearl>\fB(create base Act
1121: (:: Actor struct)
1122: (:: Time int) )
1123: \fI(Act (Actor (nilstruct))
1124: (Time 0) )\fR
1125: \fIpearl>\fB(create base State
1126: (:: Object struct)
1127: (:: Time int) )
1128: \fI(State (Object (nilstruct))
1129: (Time 0) )\fR
1130: .DE
1131: In this case, all states of John or acts by John would be indexed
1132: under John plus the time, thus ending up in the same hash bucket.
1133: .sp 3
1134: .PP
1135: The hashing mechanism was designed to give the user benefit in
1136: proportion to the effort expended in determining hash labels.
1137: With no effort, the structure type provides some help.
1138: With the addition of each label or pair of labels,
1139: an item to be inserted into the data base is indexed into
1140: another location in the hash table.
1141: Thus the cost of extra labels is simply the time to find
1142: another hash bucket (a few adds and multiplies), and add
1143: the item to the front of the list implying the time and
1144: space incurred by one cons-cell.
1145: The benefit at fetching time is the ability to use this
1146: extra information to narrow in on a small subset of
1147: the items in the data base which are most likely to
1148: be what is desired.
1149: .sp 3
1150: .PP
1151: It is often the case that a program needs to build several
1152: data bases where one or more are extensions of another.
1153: For example, consider a planner which is trying to choose
1154: between two alternative plans.
1155: One way to do this is to simulate carrying each one out to
1156: determine its likely effects (good or bad) to help in the
1157: decision.
1158: Thus the program might want to build a data base for each
1159: into which it could assert the various facts determined by
1160: the simulation.
1161: Both of these new data bases would be considered extensions of the
1162: usual data base with the added feature that anything stored in
1163: them was simply expected to be true in the future.
1164: Thus, after the simulation, it might be desireable to delete the
1165: data base of the plan not chosen and the program would certainly
1166: not want to assert the effects of the simulation into its regular
1167: data base since they are not in fact true.
1168: .PP
1169: PEARL provides both these abilities by providing facilities for
1170: building a forest of data bases.
1171: The regular data base which is built automatically is called
1172: \fI*maindb*\fR.
1173: To build two extensions from this, one uses the function
1174: \fIbuilddb\fR: to build a tree of data bases:
1175: .DS
1176: \fIpearl>\fB(builddb Test1 *maindb*)
1177: \fI(database: Test1)\fR
1178: \fIpearl>\fB(builddb Test2 *maindb*)
1179: \fI(database: Test2)\fR
1180: .DE
1181: .LP
1182: We can then assert various facts from the simulation into each of
1183: these new data bases.
1184: If we subsequently fetch from Test1, we will get back all facts
1185: which were asserted into either \fITest1 \fBor \fI*maindb*\fR.
1186: When we have decided which to use, we can then free up the one
1187: that is no longer needed.
1188: .NH
1189: Fetching
1190: .sp 3
1191: .PP
1192: To fetch an object from a data base, the user invokes the
1193: fetcher with a structure to be used as a pattern.
1194: For efficiency,
1195: PEARL tries to narrow down the possible choices without
1196: actually matching this pattern against any knowledge in the
1197: data base.
1198: Thus, narrowing down the possibilities and avoiding
1199: matching as long has possible are the two driving goals of the
1200: fetching algorithm.
1201: In order to narrow down the choices,
1202: information in the pattern is examined to determine
1203: which of the hashing indices is most likely to narrow
1204: down the choices.
1205: This determination is made based on the ways in which PEARL has been
1206: instructed to hash structures of the same type as the pattern and also
1207: based on which slots of the pattern actually have a useful value for
1208: hashing.
1209: \fINilsym\fR, \fInilstruct\fR, \fInil\fR and \fIunbound\fR values
1210: are not considered useful.
1211: Given the values which are considered useful and the hashing
1212: information for the type of structure, the hierarchy of buckets to be
1213: chosen is as follows:
1214: .DS
1215: ** hashing
1216: :: hashing
1217: * hashing
1218: : hashing
1219: .DE
1220: .LP
1221: All the other hashing labels are modifiers on these four
1222: methods and affect what values are used to compute the index.
1223: .sp 3
1224: .PP
1225: The resulting hash index is used to choose a bucket from the hash
1226: table which is returned to the user as a result stream.
1227: No matching between the pattern and objects
1228: in the data base occurs at this point and the
1229: stream simply contains pointers to all data base items
1230: in the same hash bucket, regardless of whether they actually
1231: match the pattern.
1232: PEARL appends the pattern to the front of this
1233: stream for subsequent use.
1234: For example, to fetch all PlanFors involving Goals whose Objective
1235: is a PTrans, we create a pattern for this type of object:
1236: .DS
1237: \fIpearl>\fB(setq PTransGoals (create pattern PlanFor
1238: (Goal (Goal (Objective (PTrans))))
1239: (Plan ?Plan)))
1240: \fI(PlanFor (Goal (Goal (Planner ?*any*)
1241: (Objective (PTrans (Actor ?*any*)
1242: (Object ?*any*)
1243: (From ?*any*)
1244: (To ?*any*)))))
1245: (Plan ?Plan))\fR
1246: .DE
1247: .LP
1248: and then call the function \fBfetch\fR with this pattern as an
1249: argument:
1250: .DS
1251: (setq PTransGoalStream (fetch PTransGoals))
1252: .DE
1253: .sp 3
1254: .PP
1255: The user may then extract items from
1256: the stream one at a time by successive requests to \fBnextitem\fR:
1257: .DS
1258: (setq Result (nextitem PTransGoalStream))
1259: .DE
1260: .LP
1261: At each request, the pattern is matched against successive
1262: items from the hash bucket until one matches,
1263: in which case it is returned,
1264: or until the potential items run out,
1265: in which case \fInil\fR is returned.
1266: .NH
1267: Predicates and Matching
1268: .sp 3
1269: .PP
1270: Predicates may also be attached to a slot specifying constraints on
1271: the values of pattern-matching variables.
1272: Each time a match is made between the slots of two structures
1273: (described in detail below), the predicates of each slot are run to
1274: determine whether the match should succeed or fail.
1275: Two types of predicates are provided by PEARL.
1276: The first type are Lisp functions or expressions to be evaluated.
1277: If a predicate is simply the name of a function, that function is
1278: applied to the slot value from the opposing structure.
1279: If it is an S-expression, it is processed for special forms
1280: which indicate where to get the arguments and then evaluated.
1281: For example, the following pattern will require that the variable in
1282: its first slot be bound to a positive integer value with the predicate
1283: \fIplusp\fR.
1284: It also requires that the variable in its third slot be bound
1285: to a value which is a member of its second slot (\fB"*"\fR refers
1286: to the value in the current slot of the opposing structure and
1287: \fI"=Two"\fR refers to the value in the slot named Two of the
1288: opposing structure):
1289: .DS
1290: \fIpearl>\fB(create individual Example
1291: (One ?One plusp)
1292: (Two ?*any*)
1293: (Three ?Three (member * =Two) ) )
1294: \fI(Example (One ?One)
1295: (Two ?*any*)
1296: (Three ?Three) )\fR
1297: .DE
1298: .sp 3
1299: .PP
1300: The second type of predicate is called a \fBstructure predicate\fR and
1301: consists of the name of a structure type.
1302: Its effect is to restrict the value in a structure slot to being a
1303: structure of the specified type.
1304: Thus another way to restrict the value of the Objective of the Goal in
1305: the Goal slot of the PlanFor which was fetched above, is to put a variable
1306: in the slot and add a PTrans predicate:
1307: .DS
1308: \fIpearl>\fB(setq PTransGoals (create pattern PlanFor
1309: (Goal (Goal (Objective ?O PTrans)))
1310: (Plan ?Plan)))
1311: \fI(PlanFor (Goal (Goal (Planner ?*any*)
1312: (Objective ?O)))
1313: (Plan ?Plan))\fR
1314: .DE
1315: .LP
1316: The effect is the same but testing the type of the value is much more
1317: efficient than doing the matching process on the two PTranses slot by
1318: slot.
1319: .sp 3
1320: .PP
1321: For efficiency, the semantics of the matching have been
1322: constrained to avoid the usual variable naming problems.
1323: Two structures match if they can be unified.
1324: However, no attempt is made to detect circularities,
1325: nor are variables ever bound to other variables.
1326: Circularities have never actually occurred in our experience and
1327: most variables are local to the pattern they appear in,
1328: so naming conflicts do not arise.
1329: Of course it would be straightforward to add checks for
1330: these problems if one was willing to incur the expense.
1331: .sp 3
1332: .PP
1333: The variables in a structure are implemented as an assoc-list attached
1334: to the structure so that a list of the variables of a structure can be
1335: located quickly.
1336: However, \fIassoc\fR is only used for external lookup of a variable.
1337: Once the structure has been created, each slot containing a variable
1338: has a pointer to the special cons-cell associated with it in the
1339: assoc-list so that it has immediate access to its value.
1340: In particular, the name of the variable is not even accessed during
1341: the matching process, since its value is all that is needed.
1342: .sp 3
1343: .PP
1344: In general, the matching procedure takes two structures
1345: which each may contain variables.
1346: If the structures are not definitionally the same type
1347: then the match fails automatically.
1348: This quickly eliminates items which happen to hash to the same slot.
1349: Otherwise, each structure is viewed as a sequence of slots
1350: which are successively matched between the two structures.
1351: Two structures of the same type match if and only if each of their
1352: slots matches the corresponding slot of the other structure.
1353: Each slot is filled in one of three ways:
1354: .IP 1)
1355: The slot may contain an actual value of its type (for example,
1356: a slot of type \fIstructure\fR may contain a PTrans).
1357: .IP 2)
1358: The slot may contain a user-defined variable.
1359: .IP 3)
1360: The slot may contain the special match-anything variable \fI?*any*\fR.
1361: .LP
1362: If the slot contains a variable (other than \fI?*any*\fR) which has not
1363: been bound then it may become bound as a side effect of the
1364: matching process.
1365: Once a variable is bound to a real value during the
1366: matching process, for the purposes of matching, it will
1367: be treated as if the slot were filled with that value.
1368: .sp 3
1369: .PP
1370: We now examine each of the pairings of slot values which may
1371: occur and how they are matched.
1372: If either of the two slots being matched contains the special
1373: variable \fI?*any*\fR, then the slots match by definition,
1374: regardless of the contents of the other slot.
1375: If both slots contain variables that are unbound, the slots do not
1376: match.
1377: (This is true even if the two variables are textually
1378: the same name, since they are each considered local to their
1379: particular structures.)
1380: If one slot contains an unbound variable (and the other
1381: a bound variable or a value), then any predicates on the
1382: slot with the unbound variable are tested to see if the
1383: unbound variable should be bound to the bound value.
1384: If so, then the unbound variable is bound to the value
1385: of the other slot, and the two slots match.
1386: If any of the predicates return \fInil\fR, the two slots do not
1387: match, the variable is not bound, and the entire match fails.
1388: .sp 3
1389: .PP
1390: If both slots contain either bound variables or values,
1391: then the values of the two slots are compared.
1392: If the slot is of type \fIstructure\fR, then the entire matching
1393: algorithm is recursively applied.
1394: If the slot is of types \fIinteger\fR or \fIlisp\fR, then \fIequal\fR is used.
1395: If the type is \fIsymbol\fR, than the two values must be the same symbol.
1396: Regardless of the type, any predicates associated with the
1397: slot are run and all must succeed.
1398: .sp 3
1399: .PP
1400: For example, if we create two structures, one representing Sam
1401: and one with a variable in the \fIName\fR slot:
1402: .DS
1403: \fIpearl>\fB(create individual Person Sam
1404: (Name Samuel))
1405: \fI(Person (Name Samuel))\fR
1406: \fIpearl>\fB(create individual Person PersonPattern
1407: (Name ?FirstName))
1408: \fI(Person (Name ?FirstName))\fR
1409: .DE
1410: .LP
1411: then match them and look at the result in \fIPersonPattern\fR:
1412: .DS
1413: \fIpearl>\fB(match Sam PersonPattern)
1414: \fIt\fR
1415: \fIpearl>\fBPersonPattern
1416: \fI(Person (Name ?FirstName = Samuel))\fR
1417: .DE
1418: .LP
1419: we find that they do match and the variable \fI?FirstName\fR in
1420: \fIPersonPattern\fR has been bound to the symbol \fISamuel\fR.
1421: .PP
1422: We now take a slightly more complicated example.
1423: In PEARL's matching algorithm there is no sense that one of its
1424: arguments is the pattern and one the thing to be matched to, so
1425: both may have variables.
1426: As long as the variables are in different slots so that \fImatch\fR
1427: will never try to match two unbound variables to each other, the
1428: matching will work fine.
1429: Thus, if we want our backward inference mechanism from the extended
1430: example in section 2 to not only tell us \fIthat\fR Sam has a low
1431: salary but in fact \fIwhat level\fR of salary he had, we could
1432: fetch the following structure:
1433: .DS
1434: .Ls
1435: (create \kBindividual Salary SamsSalary
1436: \h'|\nBu'\kA(Employee Sam)
1437: \h'|\nAu'(Level ?Level))
1438: .Le
1439: .DE
1440: .LP
1441: This would result in the backward inference demon using the
1442: following pattern to fetch rules that might tell it about
1443: finding a person's salary:
1444: .DS
1445: \fIpearl> \fB(create pattern BackwardRule Wanted
1446: (Need (Salary (Employee Sam)
1447: (Level ?Level))))
1448: \fI(BackwardRule (Need (Salary (Employee (Person (Name Sam)))
1449: (Level ?Level)))
1450: (LookFor ?*any*))\fR
1451: .DE
1452: .LP
1453: In processing the resulting stream, the matcher would be called
1454: upon to match the above pattern \fIWanted\fR to the following
1455: rule (which is in the data base but which we recreate for
1456: this example):
1457: .DS
1458: \fIpearl> \fB(create individual BackwardRule Known
1459: (Need (Salary (Employee ?Person)
1460: (Level Low)))
1461: (LookFor (Professor (Person ?Person))))
1462: \fI(BackwardRule (Need (Salary (Employee ?Person)
1463: (Level Low)))
1464: (LookFor (Professor (Person ?Person))))\fR
1465: .DE
1466: Matching these will succeed and in the process the variables
1467: \fI?Level\fR in \fIWanted\fR and \fI?Person\fR in \fIKnown\fR
1468: will be bound:
1469: .DS
1470: \fIpearl> \fB(match Wanted Known)
1471: \fIt\fR
1472: \fIpearl> \fBWanted
1473: \fI(BackwardRule (Need (Salary (Employee (Person (Name Sam)))
1474: (Level ?Level = Low)))
1475: (LookFor ?*any*))\fR
1476: \fIpearl> \fBKnown
1477: \fI(BackwardRule (Need (Salary (Employee ?Person = (Person (Name Sam)))
1478: (Level Low)))
1479: (LookFor (Professor (Person ?Person
1480: = (Person (Name Sam))))))\fR
1481: .DE
1482: .NH
1483: Variables
1484: .sp 3
1485: .PP
1486: There are three types of pattern matching variables in PEARL.
1487: Global variables (which are just Lisp variables) must be declared
1488: and are never unbound by PEARL.
1489: All undeclared variables are local to the individual structure in
1490: which they are mentioned.
1491: Local variables are dummy variables, local to a particular
1492: structure and any of its components which were created
1493: in the same instant.
1494: They are all unbound by PEARL before every match on that structure.
1495: The examples given of variables in the previous section were of local
1496: variables which require no declaration.
1497: The third, intermediate, type of variable provides lexical
1498: scoping within groups of structures.
1499: Lexically scoped variables are like local variables in that they
1500: are unbound by PEARL before a match is made, but have their
1501: scope extended across several structures as indicated by the user.
1502: .sp 3
1503: .PP
1504: Consider the following examples of the three types of variables.
1505: For our first example, suppose that in a data base representing the
1506: planning knowledge of a particular person is an Ego structure which
1507: records the identity of that person.
1508: The program wishes to determine this and to remember it in a variable
1509: called Planner.
1510: Planner is declared to be global and then used to fetch the
1511: appropriate knowledge structure from the data base:
1512: .DS
1513: .Ls
1514: (global Planner)
1515: (nextitem (fetch (create \kAindividual Ego
1516: \h'|\nAu'(Identity ?Planner))))
1517: .Le
1518: .DE
1519: .LP
1520: At this point, the Lisp atom Planner is bound to the
1521: identity of the planner.
1522: We can now ask for all PTranses in the data base involving the planner
1523: as the Actor and Object:
1524: .DS
1525: .Ls
1526: (setq Pat (create \kBindividual Ptrans
1527: \h'|\nBu'\kA(Actor ?Planner)
1528: \h'|\nAu'\kB(Object ?Planner)
1529: \h'|\nBu'\kA(From ?Start)
1530: \h'|\nAu'(To ?Dest)))
1531: (setq Stream (fetch Pat))
1532: .Le
1533: .DE
1534: .LP
1535: At this point the pattern in Pat has two local variables,
1536: \fI?Start\fR and \fI?Dest\fR which will be unbound before each match and
1537: may be bound to a new value during each match.
1538: \fI?Planner\fR on the other hand is global and will continue to have the
1539: value it received during the original fetch it was used in.
1540: .sp 3
1541: .PP
1542: With a global variable, a group of structures are allowed to share a
1543: variable whose value is constant once it is set the first time.
1544: Furthermore, all structures are thereafter required to share this same
1545: variable and are precluded from having their own variable with the
1546: same name.
1547: However, it is sometimes useful to group a set of structures together
1548: via a set of variables which we wish to behave like local variables in
1549: every other way.
1550: Furthermore we might wish to have several such groups which can each
1551: have a variable with this same name.
1552: For example, a body of PEARL structures conceptually composing a
1553: single frame should be made to share the same variables but it should
1554: be possible to have several instances of such a frame with the same
1555: variable names tying each group together without interfering with the
1556: others.
1557: Each instance of this group of variables is then local to that frame.
1558: However, the results of matching any particular component
1559: of the frame will be detectable in the variables associated
1560: with the other components.
1561: This is done in PEARL by dynamically declaring a scope with local
1562: variables which are imposed upon all structures created until that
1563: scope is closed.
1564: For example, consider the following sequence:
1565: .DS
1566: .Ls
1567: (block Plan1 (Planner Goal))
1568: (create \kBindividual PlanFor
1569: \h'|\nBu'\kA(Goal ?Goal)
1570: \h'|\nAu'(Plan ?Plan))
1571: (create \kBindividual Goal
1572: \h'|\nBu'\kA(Planner ?Planner)
1573: \h'|\nAu'(Objective ?Objective))
1574: (create \kAindividual Plan
1575: \h'|\nAu'\kB(Planner ?Planner)
1576: \h'|\nBu'\kA(Goal ?Goal)
1577: \h'|\nAu'(Steps ?Steps))
1578: (endblock Plan1)
1579: .Le
1580: .DE
1581: .LP
1582: This sequence creates three structures which are intimately tied
1583: together via the variables \fI?Planner\fR and \fI?Goal\fR which
1584: are declared in the enclosing block.
1585: After this code executes, if any of the structures is fetched from
1586: the data base, any binding of these two variables would have an
1587: immediate effect in all of them.
1588: In addition, the values of these variables are available simply by
1589: knowing the name of the block, so that one can ask for the value of
1590: the Planner variable in Plan1 directly.
1591: However, now that the block has been closed, other structures are
1592: free to have variables with the same names.
1593: .NH
1594: Demons
1595: .sp 3
1596: .PP
1597: A common AI mechanism provided by AI languages is one of
1598: "if-added" functions or demons.
1599: PEARL has a general ability to attach functions called \fIhooks\fR
1600: to base structures (\fIbase hooks\fR) or to slots of individual
1601: structures (\fIslot hooks\fR).
1602: Base hooks are run whenever the particular PEARL function that the
1603: hook is labelled with accesses an individual of that type.
1604: Slot hooks are put into individual and are run whenever the particular
1605: PEARL function that the hook is labelled with accesses that slot
1606: of the individual.
1607: In order to allow these hooks to tailor the operation of the
1608: various PEARL functions on particular structures or types of
1609: structures, these demons may be invoked either before or after
1610: the PEARL function they are labelled with does its work.
1611: If they run before, they are allowed to short-circuit the function's
1612: action or perform it themselves and specify a value to return.
1613: If they run after, they may also modify the value to be returned.
1614: .sp 3
1615: .PP
1616: For example, in the extended example at the beginning of this
1617: paper, we presented a simple inference package which would run
1618: automatically whenever an object was fetched or inserted.
1619: To implement this, we wrote two functions MakeForwardInference
1620: and MakeBackwardInference.
1621: MakeForwardInference was designed to use rules which said if
1622: you learn X then infer Y.
1623: MakeBackwardInference was designed to use rules which said if
1624: you want to know X then check to see if you know Y.
1625: Learning something while using PEARL usually means inserting
1626: something into the data base, so we wish to have
1627: MakeForwardInference run whenever we insert some concept
1628: into the data base, after the insertion.
1629: Wanting to know something while using PEARL means fetching
1630: it from the data base, so we wish to have MakeBackwardInference
1631: run whenever we fetch some concept from the data base, before the
1632: actual fetch takes place.
1633: This was accomplished by attaching these two functions as demons
1634: to the base structure Concept as follows:
1635: .DS
1636: .Ls
1637: (create \kBbase Concept
1638: \h'|\nBu'(if \kA<insertdb MakeForwardInference
1639: \h'|\nAu'>fetch MakeBackwardInference))
1640: .Le
1641: .DE
1642: .LP
1643: A similar mechanism is available for attaching demons to individual
1644: slots of structures.
1645: Other than through matching, the principle way that slots of
1646: already created structures get changed is through the PEARL
1647: function \fIputpath\fR.
1648: For example, if Sam got a raise, making his salary level
1649: \fIMedium\fR, we might want to change the \fILevel\fR slot of
1650: his Salary structure:
1651: .DS
1652: (putpath SamsSalary 'Level (getsymbol 'Medium))
1653: .DE
1654: If there were facts in the data base (like the fact that Sam is
1655: poor) which depended on this fact, we would be interested in
1656: monitoring Sam's salary level so that we could fix this up.
1657: Of course, a general data dependency mechanism would be much
1658: better but if you did not have one, one possible way of
1659: accompishing this would be to attach a demon to the Level slot of
1660: \fISamsSalary\fR at the time of creation:
1661: .DS
1662: .Ls
1663: (create \kBindividual Salary SamsSalary
1664: \h'|\nBu'\kA(Employee Sam)
1665: \h'|\nAu'(Level ^ if >putpath (AdjustPoorness =Employee *)))
1666: .Le
1667: .DE
1668: This assumes that \fIAdjustPoorness\fR is a function expecting the
1669: name of the person and the new level.
1670: .PP
1671: Like predicates, a PEARL demon may be either the name of a function
1672: to be run with the structure or slot as its argument
1673: or it may be a general S-expression which contains any of the
1674: special forms which refer to the current structure or slot.
1675: Besides the built-in PEARL functions which automatically check for
1676: demons with their names on them attached to slots that they touch,
1677: there is a facility for user-defined functions to explicitly
1678: request that demons on structures or slots that they touch be run.
1679: However, this action is not automatic;
1680: the involved functions must explicitly run the demons.
1681: .NH
1682: Implementations
1683: .sp 3
1684: .PP
1685: The main emphasis of efficiency considerations within PEARL was
1686: to allow the user to avoid inefficient algorithms.
1687: We also tried to make the code itself as efficient as possible.
1688: To make the user interface as friendly as possible,
1689: error checking is done whenever it can be done efficiently.
1690: As a result of these two principles, PEARL is fast and
1691: friendly enough for use as a serious programming language.
1692: .sp 3
1693: .PP
1694: PEARL was also intended to be portable.
1695: It was originally developed on a DEC 20 and moved with no
1696: modification to a DEC PDP-10 under UCI Lisp.
1697: It was then moved to a VAX-11/780 under Franz Lisp [3] [4]
1698: which at that time did not provide a facility for allocating
1699: hunks of memory and thus required the lowest level of the
1700: implementation to be rewritten using arrays.
1701: Since the lowest level of the UCI Lisp version was written in
1702: Lisp assembler (LAP) operating on blocks of memory, this new
1703: Franz Lisp version was somewhat less efficient.
1704: When "hunks" were added to Franz Lisp, we attempted to modify
1705: the VAX version to use them.
1706: However, since Franz Lisp hunks behave significantly differently
1707: in several ways from blocks of memory in UCI Lisp, this was
1708: abandoned temporarily.
1709: Instead, we used what we learned to redesign the lowest level of
1710: the UCI Lisp version of PEARL so that it could be easily moved
1711: between UCI Lisp and Franz Lisp and then moved it back to the VAX.
1712: .PP
1713: We now believe that PEARL could be moved to another Lisp by
1714: rewriting about a dozen functions and adding the macros
1715: needed to convert from UCI Lisp to the target Lisp.
1716: (Only one of these is now machine coded on the PDP-10,
1717: a routine for doing address arithmetic.
1718: The Franz Lisp version is completely in Lisp.)
1719: The primary functions which must be rewritten pertain to creating
1720: and accessing hunks of memory and modifying the top level
1721: read-eval-print loop.
1722: We are currently verifying PEARL's portability by moving it to
1723: both MACLisp and Lisp Machine Lisp.
1724: .NH
1725: Performance
1726: .sp 3
1727: .PP
1728: As mentioned, PEARL gains much of its speed during fetches from the
1729: data base by using a user-assisted hashing mechanism.
1730: Here we present some evidence that this mechanism does in
1731: fact speed up access to the data base.
1732: To test this, we timed the running of a recent version of PAM,
1733: a story understanding program [12], which was written using PEARL.
1734: For these timings, we used the Franz Lisp version of PEARL.
1735: Since the size of PEARL data bases is user-settable, we compared
1736: two runs of PAM on a large (23 sentence) story, one using the
1737: largest available hash table (see below for details of sizes)
1738: and one using the smallest available hash table which is logically
1739: equivalent to a linear list.
1740: .sp 3
1741: .PP
1742: For each run we read in the initial knowledge and program
1743: once and then processed the story three times to test the effects
1744: of the data base getting fuller.
1745: The results are as follows:
1746: .DS
1747: \h'|\nau'
1748: \kaSmall Table \kbLarge Table
1749:
1750: Load \h'|\nau'68 + 13 \h'|\nbu'30 + 5
1751:
1752: Run 1 \h'|\nau'96 + 10 \h'|\nbu'65 + 10
1753:
1754: Run 2 \h'|\nau'113 + 11 \h'|\nbu'66 + 9
1755:
1756: Run 3 \h'|\nau'129 + 9 \h'|\nbu'65 + 10
1757: .DE
1758: .LP
1759: Note that while the large hash table was quite stable as the
1760: amount of information in it approximately tripled, the small
1761: hash table causes the execution times to increase substantially
1762: as the data base fills up.
1763: .sp 3
1764: .PP
1765: In similar comparisons with UCI Lisp on the PDP 10, the results
1766: were even more dramatic.
1767: Times for the large data base were flat but using a small data base,
1768: each run's time was bigger than the previous run by 50% of the first
1769: run's time and each run's garbage collection time was bigger
1770: than the previous by 100% of the first run's garbage collection time.
1771: .DS
1772: \kaSmall Table \kbLarge Table
1773:
1774: Load \h'|\nau'17 + 2 \h'|\nbu'16 + 2
1775:
1776: Run 1 \h'|\nau'64 + 13 \h'|\nbu'24 + 2
1777:
1778: Run 2 \h'|\nau'92 + 22 \h'|\nbu'24 + 1
1779:
1780: Run 3 \h'|\nau'125 + 33 \h'|\nbu'26 + 2
1781: .DE
1782: .LP
1783: This indicates that PEARL could make large programs running on
1784: the PDP10 must faster.
1785: It also indicates that although the VAX is a slower machine,
1786: with its virtual memory it behaves quite well under what a load
1787: that taxes the PDP 10.
1788: .sp 3
1789: .PP
1790: Another piece of timing we performed is also interesting to those
1791: considering moving to VAXes from PDP 10s.
1792: All of the above timings were of compiled versions of PEARL on
1793: both machines.
1794: (The PAM code was not compiled.)
1795: Thus, Franz Lisp on the VAX seems to run the same program
1796: with 2-2.5 times the CPU time of UCI Lisp on the PDP 10.
1797: Since the ratio between the speeds of the processors is estimated
1798: at 2.5, compiled Franz Lisp code competes favorably (modulo the
1799: processor speed) with compiled UCI Lisp code.
1800: However, we also tried running PAM with uncompiled versions
1801: of PEARL on both machines.
1802: In this case, we found that the Franz Lisp version ran 10 times
1803: slower, while the UCI Lisp version ran only 3 times slower.
1804: This would seem to imply that either the Franz Lisp interpreter
1805: is abnormally slow or that the UCI Lisp interpreter is
1806: unusually fast.
1807: When the MAC Lisp and Lisp Machine Lisp versions are running, we
1808: will explore this further.
1809: .sp 3
1810: .PP
1811: Although we have not done any extensive profiling of PAM to
1812: determine where all the time is spent, we have tried disabling the
1813: printing functions while running PAM.
1814: Doing this, we discovered that PAM spends about 55% of its time
1815: doing input and output.
1816: This breaks down to 5% for input, 10% for conversion to list
1817: structure from internal PEARL structures and 40% for actual
1818: (pretty-)printing by Lisp.
1819: .NH
1820: Comparison to FRL
1821: .sp 3
1822: .PP
1823: Of the existing AI languages, PEARL has the most in common with FRL.
1824: This is true partly because both languages use several good ideas
1825: which have been around in AI for some time.
1826: It is also partly true because some of PEARL's features were added
1827: in imitation of the example representation language XRL presented
1828: in Charniak[2] (which the authors admit is partly in imitation of
1829: FRL and KRL).
1830: In this section, we discuss some of the ways that PEARL differs
1831: from FRL.
1832: .sp 3
1833: .PP
1834: Like PEARL, FRL is designed for representing slot-filler objects.
1835: However, in FRL these objects are modelled more after frames as
1836: described by Minsky [7] whereas PEARL's structures lean more
1837: toward logical predicates.
1838: In particular, frames become \fIactivated\fR or
1839: \fItriggered\fR by being instantiated and the data base
1840: is simply all the activated frames;
1841: there seems to be no distinction between instantiating a
1842: frame and adding it to the data base.
1843: In contrast to PEARL, frames are not encoded internally but
1844: represented as multiple depth association lists and the FRL
1845: data base is not hash coded.
1846: The FRL manual [10] seems to imply that it is in fact a linked list
1847: subject to a sequential search.
1848: The idea of separating frames into groups like PEARL's multiple
1849: data bases has been recently added as "domains" [6].
1850: .sp 3
1851: .PP
1852: Whereas PEARL requires type information on its slots and uses this
1853: information to advantage, FRL requires no information on the type
1854: or even number of values which will be allowed.
1855: This of course allows the user more flexibility but makes it more
1856: difficult for FRL to deal efficiently with each slot.
1857: .sp 3
1858: .PP
1859: In addition to the slot/filler features, FRL uses 6 primary
1860: representation techniques to improve the flexibility of frames.
1861: These are comments on slots, abstraction through slot inheritance,
1862: inherited default values for slots, constraints on slot values,
1863: indirection through values in other frames and attached procedures.
1864: We look briefly now at each of these.
1865: .IP 1)
1866: Comments in FRL are attached to slots and are generally used to
1867: remember where the value in a slot came from although they could
1868: be used for anything.
1869: This is a useful feature which in PEARL must be
1870: implemented as a separate set of predicates inserted into the data
1871: base or as dynamically-added attached procedures.
1872: We have not added them to PEARL because we are unsure whether such
1873: information should rightly be distinguished from predications
1874: about where other pieces of knowledge came from.
1875: .IP 2)
1876: The notion of inheritance of slots from more abstract objects is
1877: quite similar in FRL and PEARL, since this is one of the features
1878: PEARL inherited through XRL.
1879: The principle difference is that while in PEARL all slots must be
1880: predeclared (because of the internal mode of storage), FRL allows
1881: the addition of slots at a later time.
1882: .IP 3)
1883: The notion of default values was similarly inheritted from FRL by PEARL.
1884: However, in designing PEARL we wished to more clearly separate the
1885: idea of a general piece of knowledge represented by the definition
1886: of a type of structure along with its set of defaults from an instance
1887: of such a structure.
1888: As a result PEARL stores the default values for slots in the special
1889: instance of each type of structure called the \fIdefault instance\fR.
1890: In contrast, FRL does not make this distinction clear and provides
1891: for both a default and a value in a slot of a frame.
1892: Apparently a frame may be both an instance and a generalization
1893: at the same time.
1894: .IP 4)
1895: FRL's notion of constraints is significantly stronger and more
1896: complex than PEARL's.
1897: PEARL provides for predicates on slots but these are only enforced
1898: during matching on slots containing variables.
1899: FRL on the other hand provides three flavors of constraint with
1900: different degrees of restriction.
1901: A \fIrequirement\fR is a strong predicate on a slot which must be
1902: true of the value in that slot.
1903: A \fIpreference\fR is a weaker predicate which may be relaxed.
1904: A weaker special case of a preference is a default which simply
1905: suggests a specific value which can be easily overridden.
1906: .IP 5)
1907: A feature of FRL which goes hand-in-hand with the idea of triggered
1908: frames (and is thus lacking in PEARL) is that of indirection.
1909: This allows a frame to specify constraints on slots of other
1910: frames that are currently active when it is triggered.
1911: Thus indirection provides what might be considered a "horizontal"
1912: version of the vertical notion of default inheritance.
1913: .IP 6)
1914: Demons and attached procedures are old ideas in AI but FRL
1915: introduced a new twist on them which PEARL then took one step
1916: further.
1917: FRL provides for if-added, if-needed, and if-removed procedures which
1918: are attached to slots and rather than being triggered by arbitrary
1919: conditions are instead run only in the case of adding, requesting
1920: or removing the value of a slot.
1921: These attached procedures are enforced by the functions that
1922: perform these types of access, thus providing for idiosyncratic
1923: forms of inheritance or finding a slot value.
1924: In PEARL we extend this idea so that there are a large variety of
1925: access functions which may trigger attached procedures (hooks).
1926: In addition, these procedures are allowed to affect the actions
1927: of the access functions, thus allowing a particular class of
1928: objects to tailor the behavior of most of PEARL's functions.
1929: Similarly, procedures to tailor the performance of printing and
1930: other functions on objects (rather than their slots) are provided
1931: by both FRL (via the SELF slot) and by PEARL (via base hooks)
1932: In addition, a form of detached procedures ("sentinels") have
1933: recently been added to FRL [6] in which the triggering condition
1934: is the activation of a group of frames.
1935: .sp 3
1936: .PP
1937: In contrast to more ambitious knowledge representation languages,
1938: FRL and PEARL are similar in their fairly restricted matching
1939: procedures which are essentially slot-by-slot matches with no
1940: provision for matching to a degree or forcing a match via mapping
1941: as in MERLIN [8].
1942: .sp 3
1943: .PP
1944: Finally, there are two features of hierarchical representations
1945: which FRL provides but which are not yet provided by PEARL.
1946: The principal one is the ability to store multiple views of an object
1947: thus allowing a frame to inherit slots from several other frames.
1948: The second one is the ability to move an object down the hierarchy,
1949: thus providing the dynamic ability to further specify a previously
1950: general frame based on new information.
1951: Both of these are in the works since we have encountered a need for them.
1952: .NH
1953: Comparison to KRL
1954: .sp 3
1955: .PP
1956: .bp
1957: .NH
1958: References
1959: .sp 2
1960: .IP [1]
1961: Bobrow, D. G., and Winograd, T. "An Overview of KRL, a Knowledge
1962: Representation Language."
1963: \fICognitive Science\fR 1:1 (1977).
1964: .IP [2]
1965: Charniak, E., Riesbeck, C. K., and McDermott, D. V.
1966: \fIArtificial Intelligence Programming\fR. Hilldale, New Jersey:
1967: Lawrence Erlbaum Associates, 1980.
1968: .IP [3]
1969: Fateman, R., "Views on Transportability of Lisp and Lisp-based Systems",
1970: in \fIProc. of the 1981 ACM Symposium on Symbolic and Algebraic
1971: Computation\fR p 137-141, (ACM order no 505810), 1981.
1972: .IP [4]
1973: Foderaro, J. K., and Sklower, K. L.
1974: \fIThe Franz Lisp Manual\fR in \fIBerkeley UNIX Reference Manual\fR,
1975: Vol. 2c., Computer Systems Research Group, Computer Science Div.
1976: EECS Dept., University of California, September, 1981
1977: .IP [5]
1978: Greiner, R., and Lenat, D. "A Representation Language Language."
1979: In \fIProc. First NCAI\fR. Stanford, CA, August, 1980,
1980: 165-169.
1981: .IP [6]
1982: ?????, ?. "Extended Features of FRL" ?????, reproduced in forthcoming
1983: edition of [4], 1982.
1984: .IP [7]
1985: Minsky, M. "A Framework for Representing Knowledge" in P. H.
1986: WInston (Ed.) \fIThe Psychology of Computer Vision\fR,
1987: New York: McGraw-Hill, 1975.
1988: .IP [8]
1989: Moore, J., and Newell, A. "How Can MERLIN Understand?" in L. Gregg
1990: (Ed.), \fIKnowledge and Cognition\fR, Lawrence Erlbaum Associates, 1973.
1991: .IP [9]
1992: Roberts, R. B., and Goldstein, I. P.
1993: "NUDGE, A Knowledge-Based Scheduling Program."
1994: In \fIProc. IJCAI-77\fR. Cambridge, MA, August, 1977, 257-263.
1995: .IP [10]
1996: Roberts R. B., and Goldstein, I. P.
1997: \fIThe FRL Manual\fR, MIT AI Memo, September, 1977, reproduced in
1998: forthcoming edition of [4], 1982.
1999: .IP [11]
2000: Schank, R. \fIConceptual Information Processing\fR. Amsterdam: North Holland,
2001: 1975.
2002: .IP [12]
2003: Wilensky, R. "Understanding Goal-Based Stories",
2004: Technical Report 140, Computer Science Department,
2005: Yale University, New Haven, CT, September 1978.
2006: .IP [13]
2007: Wilensky, R.
2008: "Meta-Planning: Representing and Using Knowledge about Planning in Problem
2009: Solving and Natural Language Understanding."
2010: \fICognitive Science\fR 5:3 (1981).
2011: .rm CF
2012: .bp 0
2013: .sp 14
2014: .B
2015: .LG
2016: .ce
2017: Table Of Contents
2018: .SM
2019: .sp 2
2020: .DS
2021: 1. Introduction \ka 1
2022: 2. An Overview and Sample Application Of PEARL \h'|\nau' 2
2023: 3. How Fast Is PEARL? \h'|\nau' 6
2024: 4. Objects and Structures \h'|\nau' 7
2025: 5. Data Base Facilities \h'|\nau'11
2026: 6. Fetching \h'|\nau'17
2027: 7. Predicates and Matching \h'|\nau'18
2028: 8. Variables \h'|\nau'21
2029: 9. Demons \h'|\nau'23
2030: 10. Implementations \h'|\nau'24
2031: 11. Performance \h'|\nau'25
2032: 12. Comparison to FRL \h'|\nau'26
2033: 13. Comparison to KRL \h'|\nau'29
2034: 14. References \h'|\nau'31
2035: .DE
2036: .bp 0
2037: .sp 14
2038: .SH
2039: Acknowledgements
2040: .PP
2041: PEARL was originally a joint project of Joe Faletti and Mike
2042: Deering (now at the Fairchild AI Lab in Palo Alto) aimed at
2043: redesigning, extending and completely rewriting an earlier
2044: package designed and written by Mike.
2045: PEARL owes many ideas and much of its success to Mike who
2046: has been involved in all design decisions.
2047: In particular, the hashing scheme which is responsible for
2048: much of PEARL's efficiency was originally his idea.
2049: .PP
2050: The initial move of PEARL to the VAX from which we learned enough
2051: to make the second one easier was accomplished by Mike Deering
2052: and Doug Lanam (now at the Hewlett Packard AI Lab in Palo Alto).
2053: The move was made significantly easier by Doug's UCI Lisp
2054: compatibility package for Franz Lisp.
2055: .PP
2056: The authors wish to thank Mike and Doug for their contributions.
2057: We also wish to thank the members of the Berkeley AI Research
2058: group (BAIR) who have used PEARL during its development and made
2059: many valuable suggestions based on active experience in its use.
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.