PEARL - A Package for Efficient Access to Representations in LISP

I Introduction

We have developed an AI language called PEARL {Package for Efficient Access to Representations in LISP). Unlike the recent tendency toward elaborate representation languages such as KRL (1] or language generators such as RRL (2], PEARL is a more modest sys­ tem that combines a number of useful AI techniques into a very etJicienl package. Besides the usual goal of pro­ viding the user with a more meaningful interface than is available via LISP, PEARL has the following salient characteristics:

1. PEARL combines some features of predicate calculus-like data bases with those of frame-based systems like FRL [3).
2. PEARL introduces typing to user-defined knowledge structures.
3. PEARL allows the user to manipulate a forest of associative data bases.
4. Fetches from the data base return streams of answers. Retrieval is based on pattern matching.
5. PEARL is very etJicienl. PEARL uses its own internal representation for knowledge structures for both economy of storage and speed. A great deal of etJort has gone into exploitine type information not available in most AI languages to eliminate search­ ing inetJiciencies. In addition, the user may easily specify, as part of a knowledge structure definition, a great deal of information about how objects should be indexed for etJicient retrieval. Thus PEARL pro­ vides much of the power of expression of other AI languages without the usual overhead.

Perhaps most significantly, PEARL is actually being used in the c·mstruction of several AI systems. In particular, the latest version of PAM [5] a story understanding pro­ gram, has been re-programmed in PEARL. PANDORA [8] a planning program now under development at Berkeley, is also written in PEARL. Our experience has led us to conclude that PEARL is an etJective AI tool for the crea­ tion of etJicient AI pro1rams.

PEARL -A Package for Efficient Access to Representations in IJSP

Michael Deering Joseph Faletti Robert Wilensky

Computer Science Division, Department of EECS University of California, Berkeley Berkeley, California 94 720

PEARL provides the user with a set of operators for deftning, creating, and manipulating slot-tiller objects, as well as placing them into associative data bases, upon which further operations may be performed.

II Objects and Structures

PEARL has four basic types: INTEGER, SYMBOL, STRUCTURE, and LISP. Objects of type INTEGER are the usual numeric type, and objects of type LISP can be any general LISP object. Symbols ·(objects of type SYMBOL) correspond to atoms in LISP, and are simply primitive objects with unique labels. Structures are collections of slots, each of which may be tilled with objects of any (predeclared) type. There is also a meta-type, SETOF, which can be applied {recursively) to any basic type to generate a new type, which will consist of a list of the specified type of objects.

Types of structures must be predetined, with the number of slots, and their names and types specified via a user declaration. When an instance of a structure is created and its slots filled, only objects with the same type as the slot may t\11 it. In addition, new structures may build upon old ones in a hierarchical fashion by speciftng new slots to add to the old ones. This hierarchy may be used in operations upon the data base.

For example, symbols are declared as follows:

(SYMBOL John Home OtJice)

The statement:

{CREATE BASE Act (Actor SYMBOL))

will define the primitive type Act. More specific forms of Acts can now be defined in terms of this base, or in terms of other defined types: ·

(CREATE EXPANDED Act Trans

(From SYMBOL)

(To SYMBOL))

(CREATE EXPANDED Trans PTrans

{Object SYMBOL))

{CREATE EXPANDED Trans MTrans {MObjecl STRUCT))

Instances of these structures can now be created u fol­ lows:

This last structure denotes "John went borne from the office" in Conceptual Dependency [ 4].

PEARL provides functions for accessing and chang· ing the values of slots within individual structures, for automatically naming the structure created, and for defining other sorts of entities as well. Slots within a structure may also be tUled with a pattern-matching variable, in which case the structure may be viewed as a pattern. Such variables are bound as part of the match­ ing process {usually during a felch from the data base.)

III Data Base Facilities

PEARL allows for a forest of associative data bases implemented as hash tables into which structures may be placed, and later fetched via structure patterns. A common problem with most AI data base implementa­ tions is the system's lack of knowledge about how best to organize information for efficient retrieval. Since the user usually has such knowledge, PEARL encourages the user to provide it when a structure type is defined to the system in the form of labels on those slots most likely to help with hashing the structure (that is, with distinguish­ ing instances from one other).

For example, to indicate that a particular slot is useful for hashing, the user puts an · in that slot in the declaration. Thus

(CREATE BASE PlanFor (· Goal STRUCT) (Plan STRUCT))

defines a type PlanFor with slots for a goal and a plan, and indicates that PlanFors should be indexed to be retrieved by their goals.

In addition, we may also wish to specify how the value that tllls the Goal slot is used to create the index. For example, if the Planner of the Goal is deemed significant for such purposes, we can indicate this as fol­ lows:

(CREATE BASE Goal {& Planner SYMBOL) (Objective STRUCT))

This will inform PEARL that structures that index on slots tllled with Goal-type structures should use the Planner slot for further discriminations; however, the way in which Goals themselves are indexed will not be affected.

IV The Matcher

To felch an object from a data base, the user invokes the fetcher with a structure to be used as a pat­ tern. This pattern is matched against likely objects in the data base, and those which match are returned to the user via a result stream (actually possibilities list) . The semantics of the matching have been constrained to avoid the usual variable naming problems for efficiency.

Two structures match if they can be unified, although no attempt is made to detect circularities (in our applications, these never occur). Also, most vari­ ables are local to the pattern they appear in, so naming conflicts do not arise {but see below for special kinds of variables). Predicates may also be attached to a slot specifying matching constraints.

There also is a general "if-added" demon mechan­ ism, in which demons can be attached either to struc­ ture definitions (that is, to all instances of a particular type of structure) or to individual slots of individual instances of structures. These demons must be labelled with the function which they wish to monitor and are only invoked by PEARL when that function is being per­ formed.

V Variables

There are three types of pattern matching variables in PEARL: global variables {which are just LISP variables), variables which are local to an individual structure and an intermediate type of variable which provides lexical scoping within groups of structures. Local variables are dummy variables, local to a particular structure and any of its components which were created in the same instant. They are all unbound before every match on that structure. Lexically scoped variables are like local variables in that they are unbound before a match is made, but have their scope extended across several structures as indicated by the user.

For example, a body of PEARL structures conceptu­ ally composing a single frame can be made to share the same variables. These variables will be local to that frame. However, the results of matching any particular component of the frame will be delectable in the vari­ ables associated with the other components.

VI Implementation Goals

While the main emphasis of efficiency considerations within PEARL was to allow the user to avoid exponential algorithms, we also tried to make the code itself as efficient as possible. To make the user interface as friendly as possible, error checking is done whenever it can be done efficiently. As a result of these two princi­ ples, PEARL is fast and friendly enough for use both as a serious programming language as well as a teaching tool for graduate Al classes. PEARL was also intended to be portable. It was developed on a DEC 20, moved with no modification to a DEC PDP-10 under UCI LISP, and currently also runs on a VAX-11/760 under Franz Lisp.

Vll Implementation and Performance

PEARL achieves its space etficiency and some of its time etficiency by requesting a block of memory from LISP for each structure instance or definition. The con­ tents or defining information are then packed within this block. Since much of the defining information is Boolean, this provides substantial savings in space for definitions . Data bases are managed similarly.

Only the lowest level functions for accessing these blocks could not be written in LISP. In the PDP-10 imple­ mentation, these functions are written in assembler; on the VAX they are written in C. The major etfort required to move PEARL to another machine is to rewrite these functions. The rest of the job entails dealing with ditferent dialects of LISP.

As a rough measure of PEARL's execution speed on the PDP-10, we created a lest data base of 4000 struc­ tures, in which the average unsuccessful query took 0.0042 CPU seconds (237 per second) and the average successful query took 0.0073 CPU seconds (136 per second) . Note that PEARL's hashing mechanism results in fast determination of failure. As another measure of PEARL's execution speed, we compared the original implementation of PAM [5] written purely in LISP with the current implementation using PEARL. The average time required by the original to process a sentence was 5.6 CPU seconds, while the new version requires an aver­ age of only 0.56 CPU seconds.