[Indigo]<KRL>document>match-eng-old!1

This paper is a tutorial introduction to the design and goals of the KRL-1 interpreter. It develops the concepts through simple examples in an attempt to make it easy to follow along, gathering up the ideas. For a more structured summary and outline, see...

The KRL-1 interpreter is designed to take advantage of the fact that our problem space is loosely coupled and monotonic. The interpreter operates by building up a complex data structure which includes:

* A set of goals: These include goals of establishing and disproving hypotheses, as well as others such as finding a primary description (or pointer) in the long-term structures, or enumerating the members of some set or sequence.

* A set of operation instantiations (called the agenda) to be carried out: Some of these invoke primitive operations, while others create subgoals, and changing the status of existing goals (for example eliminating old a goal whose negation has been satisfied).

In addition to these structures themselves, it maintains additional cross-reference structures which make it possible to provide quick answers to questions like "Are there any mappings in the concept set whose prototype is X?" and "Are there any active goals which would be satisfied by showing that entity1 and entity2 are coreferent?"

The interpreter is heavily data-driven, with goals serving as a source for suggested operations, but not driving the control structure as they do in top-down problem solving. The basic organization of processing is:

* The call sets up an initial set of hypotheses and active goals. A typical call to Match, for example, may translate into a whole collection of hypotheses and goals, corresponding to the structure of the pattern.

* Each time a goal is set up (either initially, or as a subgoal) the interpreter checks to see what methods might be applicable to satisfying it. Instantiations of applicable methods are added to the agenda (after checking to see that they aren’t already there) if they are compatible with the limitations on what work can be done specified in the parameters to the call.

* Each time a primitive operation (an activation or inference) is done, its results are added to the data structures, and the interpreter checks to see what further actions might be suggested by the new information. One of the major things it looks for is active goals which may be satisfied by the new information. As with goal-motivated actions, these are checked both against the current agenda and the specification of what kinds of operations are allowed.

* The interpreter cycles, choosing at each step one of the items from the agenda and doing what it says. This in turn may cause new goals to be set up and items to be added to (or removed from) the agenda. The choice is based on a combination of criteria depending heavily on the specific parameters provided for the call (see below...)

In the case of resource exhaustion, the reason for stopping may be either partial or total. If it is total, the entire structure is abandoned. If it is partial, partial results may be returned based on the information available, and processing continued when more resources are applied.

This organization makes it possible to do many things which were suggested in the KRL Overview paper in its discussion of matching, but were never actually implemented in KRL-0. Sections ??? below give the details of how these features are specified in using the system. Section ??? <probably not to be included in this go-round of the writeup> discusses some problems in the implementation of the interpreter and proposes a preliminary set of units for the data structures.

There is a two-way coupling between goals and actions: As in top-down systems, subgoals are created (and added to the agenda) when needed to achieve some larger goal. However, whenever an operation is done, the system checks for all goals which might be satisfied by it, regardless of whether they explicitly set it up as a subgoal. This is important in searching a loosely coupled space. One goal (for example establishing a particular mapping) might call for the operation of activating the self description of a previously inactive unit. The descriptions found there might serve to satisfy a collection of other goals, including some which had not proposed this activation. There is no direct mechanism for a subgoal to "return its answer" to the goal which created it. Rather there is a mechanism (somewhat like Hearsay’s blackboard) which enables results to be distributed to all those goals which might need them.

Intermediate results are saved in the data structure: As new coreference relations are established, new mappings found, new members found for sets and sequences, etc. they are all added to the structure representing the state of the concept set. This has several implications:

* Contexts can be shared: The data structure can be used by several different processes, each with its own goals. Since the problem space is monotonic, there is no interference (except competition for resources). If an operation suggested as part of one process ends up satisfying a goal of another process, its results can be used. There are many places where this is useful. Some clear examples are:

* A "best-match" in which several slightly different patterns are being matched against a single datum, or several related datums are being tested with a single pattern. In general all activations and inferences made for the shared item (pattern or datum) are applicable to all of the competing candidates.

* A sequence in which a match testing whether a description fits some pattern is followed by operations accessing some of its subparts, or by an action which modifies it. This is very common in low-level functions. An obvious example is the test for obvious contradictions (a possible match) done as part of a Describe.

* Complete results are available: Once the processing has ended, the interpreter can do more than return a single value to the caller. The entire set of mappings, coreferences, hypotheses, goals, etc. is available to inspection. The parameters to the call can specify that various operations are to be done on the information represented in them. Some examples are:

* Permanently storing derived information: Inferences may have established mappings and coreferences which were not explicitly in the long term data structures, and also which were not part of the major top-level goal. Selected ones of these can be incorporated into the permanent structures, in those places where the gains in later processing speed make up for the cost of redundant storage. This can be done on a case by case basis, or on the basis of general rules.

* Returning a "residue": If a match failed (either because its negation was demonstrated or resources ran out) it is possible to collect together a description of those goals which failed, and to use this in guiding further processing.

* Partial results are available: If the processing is suspended before a final answer has been determined, the data structure is available for returning a partial result. Examples might be:

* Current best guess: If a "possible match" is being tested, then an answer of "Yes" can be returned as a partial result when the test is still not complete or exhausted. In a best match situation, the top contender can be returned.

* Parts of sets and sequences: If the goal is to find all the members of some set or sequence, then at any given point the data structures will make it possible to find the ones established so far. This means that the basic finding procedure can be used in the style of a generator.