Page Numbers: Yes First Page: 1
Heading:

April 26, 1979 6:31 PM [IVY]<KRL>document>str-lev-mem-comp-brian

B.2 Structural Compaction

KRL descriptive structures as data structures, there is a price paid for the flexibility of multiple description, inherited properties, procedural attachment, etc. Every time a data access (Seek) or data modification (Describe) is done, there is a high overhead in searching down lists of perspectives, lists of fillerpairs, etc. to find the right place in the structure, and in looking for triggers on the template unit, traps on the instance unit, etc. etc. For a great many of the instances built up in actual uses of KRL, the following are likely to be true:

* The instance will be described using only a single template.

* The fillers of the fillerpairs will not make use of full-fledged descriptive power, but will be of a uniform type for all instances. Most of them will be either:

* unit co-references (including the implicit ones realized by strings, numbers and LISP structures);

* explicitly enumerated sets and sequences whose members are all explicit coreferences.

* references to other explicit fixed data structures

* The triggers associated with the template will be static -- they will all be known before the program begins running, and will not change during the course of running.

* Most calls to Seek, Describe, etc. can be declared ahead of time as to what the nature of their result (e.g. Explicit unit coreference) should be.

Some systems (such as all normal computer languages and some AI systems like MDS) opt for efficiency by making these simple cases be the only ones possible. We can take advantage of the simplifications allowed in these cases, without giving up general power, by having a mixed mode in which some parts (but not all) of the descriptive structures are selectively compacted. In KRL-1, we will allow the user to declare for a particular unit that perspectives based on that unit can be stored as "compact perspectives" which are just Lisp records. These records will have a fixed structure with specified named fields. The record will be allocated all at once, and accesses to it will be made directly by access functions provided by the record package. The user will declare (using meta-descriptions and special declaration units) just what slots are to be included in the compact perspective, and the types of the entries allowed for those slots. The entry types allowed in a compacted slot are just pointers to Lisp entitities of a specified type such as number, string, atom, or unit. In general they are not descriptor forms, but are Lisp entities from which a descriptor form can be constructed. The compact perspective would include an escape field which would allow other uncompacted slots to be attached, and/or fillerpairs for compacted slots which do not agree with the declarations.

Below we show some KRL units and associated functionals which are used in for declaring some compact perspectives. This is followed by a simple set of units and declarations, and the associated Lisp record declarations which would be used by Seek, Describe, and Match.