Return to implement.ms CVS log

Up to [CSRG BSD Unix] / 42BSD / ucb / lisp / pearl

Annotation of 42BSD/ucb/lisp/pearl/implement.ms, revision 1.1

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.