Page Numbers: Yes First Page: 1
Heading:
June 14, 1977 11:51 AM [IVY]<KRL>document>rep-index
Status: unfinished draft
Specification of the index and its standardized uses in KRL1
The index mechanism in KRL-1 differs from its counterpart in KRL-0 in two major ways. First, it is actually used by the system, to catalog information which the user puts into meta-descriptions for use in processing. This includes traps and triggers which correspond to servants, category information, functional definitions, etc. Second, its input is a description, rather than a set of key words, and its output is a labelled anchor. The indexing mechanism is complemented by a production mechanism (see <KRL>production.doc) which performs actions based on recognition of patterns. It is important to distinguish these two mechanisms and their uses, since there are some older notions (e.g. procedural attachment) which have been divided up between the two of them along lines different from before.
As with the rest of KRL-1, we have made a strong effort to provide a uniform semantics for indexing, rather than simply providing an ad hoc mechanism. The first section below describes this semantics, the second section gives the detailed specification of how it is used, and the third describes the indexing which is done automatically by the system.
The semantics of indexing
In the memory structures of KRL-1, there are anchors which contain descriptors which descibe entities which they represent. In order to make use of the descriptors in an anchor, the program must get access to it in one of three ways:
1. A subset of anchors are labelled anchors. There is a mechanism which provides a handle to a labelled anchor when given the label (unit and slot name).
2. Handles to anchors can appear in descriptors. This happens in two major ways: embedded anchors in descriptor forms (e.g. the filler anchors in a map descriptor); and explicit Handle descriptors (used when describing anchors at the meta-layer). Given a handle for an anchor, the program has access to its contents.
3. (The indexing mechanism): A labelled anchor can be indexed (by an explicit command) under a subset (not necessarily proper) of the beliefs represented by the descriptors in it. There is a command to retrieve all anchors which have been indexed under a specified set of beliefs.
This is a kind of content-addressability for anchors -- it is possible to get hold of an anchor without having a handle or knowing its name, but by specifying part of its contents. But only if it was previously indexed under exactly that part of its contents. There must be an exact correspondence between what was specified when indexing and what is specified for retrieval -- no omissions, inferences, inheritance, etc. This exact match is at belief level -- i.e. differences at intermediate level (e.g. use of functionals) or memory level (e.g. the means of associating beliefs with world) are ignored. In early implementations, there will be restrictions on the form in which those beliefs are described in the arguments to Index and Retrieve, in order to simplify the workings of the mechanism.
There is a system-standard notion of an Index, and the user can create any number of them. See the section below for the names of the Indices initially defined in the system. Every indexing or retrieval command specifies which index is to be used.
The specification of indexing and retrieval
The user interface with the indexing and retrieval functions is through process descriptions associated with Describe and Seek:
Indexing: Any Describe command (including those which augment or redescribe) can (as part of the process description) be specified as An Indexing with index = X where a simple strucutral Seek on X provides an identifying anchor for the index. In addition to whatever else the specified Describe would do (assuming it is successful), the anchor which was specified as the destination is indexed under the set of beliefs corresponding to the given description. (as mentioned above, these must have been stated within the limitations of what the indexer currently knows how to handle).
Retrieving: A Seek or Match command can be given whose grounding description declares it A Retrieval with index = X, where X is as above. ..fix this...The initial beliefs are used as a retrieval key, and the resulting retrieved anchors are incorporated to form the initial beliefs for the Seek process described by the rest of the specification. All parameters having to do with type of result, form of answers, multiplicity, etc. are the same as in the case without retrieval.
The system-maintained catalogue
The KRL-1 system uses an index whose name is SystemCatalogue for storing information about units, slots, etc. which needs to be accessed efficiently. This catalog will not generally be seen by a domain-level user, but is the standard source of information which is used by pieces of internal code, such as the interpreter, the access compiler, the reader, the printer, etc. The currently specified contents are listed below, with pointers to the documents in which the details are given:
Syntactic information:
Name retrieval:
Functional declarations: If a functional definition has been catalogued by the reader/converter, then the meta-unit-anchor for the unit on which it is defined will be indexed as: The functionalDeclaration from a Functional with name = X. Note that the result of the retrieval will be this entire anchor, which in turn is used to get the definition...fix this -- need to include the actual units for declarations...
Unit-based semantic information:
Compaction Declarations:
Uniqueness:
Category Chains:
Anchor-based semantic information:
Optionality:
Interpreter-process specific semantic information:
Servants: