[Indigo]<KRL>document>proc-pat!2

KRL-1 provides a general production-system mechanism which unifies several KRL-0 concepts, as well as providing new facilities. It is very close in spirit to the Newell version of production systems, but the KRL context puts it in a very different light. In the Newell formulation, a production system is a model for the entire computation. In KRL-1, we have a whole world of other declarative and procedural concepts, and the production system is seen as providing one particular piece of control structure. It is intended to work with, rather than replace, the other notions of agendas, matching, description, etc. This means that we can take a very pure notion of what the productions can do, since they don’t have to do all the work by themselves.

As with the rest of KRL-1, we are initially implementing only the simpler cases, but are specifying things in a way which will lead to expandability. I will first describe the motivations and general design of the production mechanism, then give the details.

3. A single cycle of the system consists of finding a production or set of productions whose conditions are satisfied by some subset of the contents of the recognition set, and carrying out the actions associated with those productions.

Nearly every word in these definitions needs further elaboration -- What is a condition and how is it "satisfied"? what can be done in an "action", how do we decide on a particular production if more than one is satisfied?, etc. etc. Rather than try to enumerate all of the different variations in the literature, I will describe (in a progressive deepening style) the choices made in KRL-1. Note: See McDermott and Forgy (1976) for an overview and summary of standard architectures.

A production contains a prototype for a production instantiation, which must specify two things: a description of a subset of the working set to be matched, and a description of the action to be carried out by the KRL-1 interpeter. Each time the production system is invoked, the system will (at least conceptually -- the usual caveats about short circuits apply) try to match the given pattern against the beliefs in the recognition set. If it succeeds (and is active -- see below), then an action will be carried out as described in the prototype.

A major issue in the architecture of production systems is the way of dealing with situations in which the patterns from more than one production are satisifed by the working set, or in which a single production could be satisfied in more than one way. In KRL-1, there is already a concept of agendas and schedulers which is ideally suited for managing conflicts. If on any invocation of the production mechanism there is only one production satisfied, then its action is carried. If there are none, then no action is carried out. If there are more than one, the following steps are taken:

This scheduler process can be specified with the command invoking the production mechanism, or if none is given it defaults to one specified for the production set, or if there is none there it defaults to a very general system-wide one described below. Once this scheduler has been set up, the work of the production mechanism has been completed, and it is up to the details of invoked scheduler to deal with the items in the conflict set.

This scheduler process is treated like any other process -- the fact that it is a scheduler is relevant only in that its inputs are set up to include the agenda of possible invocations. Whatever it does in running is considered to be the action associated with that call to the production mechanism. This might include running some of the things on the agenda, but need not. The agenda which it is given includes descriptions of the instantiations, including the production which was satisfied and the process which would be run. Thererefore, the scheduler can do things such as: choosing one thing to run on the basis of comparing descriptions of the productions (e.g. taking the most specific one); or recognizing that some set of the firings are non-interacting and can be done in arbitrary order (this might be stated in the process descriptions), etc.

So far, we have talked only about a single cycle of the production mechanism, in which a fixed working set is matched against a set of productions, and an action taken. In the general formulation of production systems, there is a repeated cycle, with the working set at each cycle being the previous working set, as changed by the actions. In KRL-1, we begin with a more primitive notion. Each call to the production mechanism is thought of separately -- a working set is specified, an action taken, and we’re done. Of course, we might use the same working set (as modified by the actions) for another invocation. The standard production system architecture would be implemented as a loop which repeatedly called the production mechanism with the same production set and the same working set (which might get internally changed).

In using repeated cycles of production activation on the same working set, there is an important problem of circularity. If we have a production which fires when A is present in the working set, then once an A is put there that production will continue to fire on every cycle until either the A is removed, or a higher-priority production (given the scheduler) is found. Although it is possible to live with this (by writing productions which carefully modify the working set so they are no longer applicable after firing), it leads to awkwardness and kludgery. The solution in some more recent architectures (See the McDermott and Forgy paper) has been to adopt the convention that a production is allowed to fire only once with a particular set of bindings in the working set. If on one cycle, the production fires because of matching an item A, it cannot fire again on the next or subsequent cycles, unless a new A is added.

In a system in which all possible firings are done on every cycle (as opposed to one having a precedence scheme which chooses only one or some of the ones which are satisfied), this convention can be implemented without having to remember the history of previous firings. A production fires if its pattern matches, and at least one of the objects it uses in the working set to perform the match is newly present since the last cycle. This causes all possible firings to happen once and only once, since a match which includes no new elements of the working set could have (and therefore would have) been done on a previous cycle.

In the KRL-1 production mechanism, we have generalized this notion to fit within the structure of single-shot invocation. The arguments to an invocation of the production mechanism includes both the working set, and an activation set which is a subset of the working set. A production can fire only if its pattern matches the working set, and at least one of the beliefs used in the match belongs to the activation set. If we wanted to implement the new Newell-type system, we would simply have the activation set each time around the loop be those elements in the working set which have been added since the last time around.

In the standard production system architecture, all that is going on in the machine is the cycling of the production system. In KRL-1, we have a notion of multi-processing, and the invocation of the production mechanism must be integrated into a process which is being driven in a very different style. One of the main motivations for having a production-like mechanism is to mix conventional (top-down) control structure with "event-driven programming". We want to specify "demons" which sit patiently waiting as the normal flow of events go on, but which jump in and take control whenever the situation they are watching for comes up.

The notion of "signals" in KRL-0 was an attempt to provide this kind of mechanism, but because of the simplicity of implementation (a set of named objects along a signal path), it did not really achieve it. In KRL-1, this notion is replaced by the production mechanism, and its use to fire productions on the basis of recognizing a set of system events. Conceptually, system events are nothing more than one specific use (by the system programs) of the general ability to specify a set of productions and call the mechanism with a given working set and activation set whenever you want, on a single-shot basis. Several of the built-in system facilities do this on a regular basis:

The reasoner -- structure changes: Each time a change is made to the set of beliefs, a production set called the belief structure production set can be invoked with a working set made up of the entire set of beliefs, and an activation set which is the newly changed belief. The process description given in describing a Seek, Match, etc. determines whether or not it will be invoked. The belief structure production set is built up by the cataloguer from the triggers and traps associated with anchors using the standard names for demons. The user cannot manipulate it explicitly, since its operation is compiled in, rather than working through the full-fledged production invocation mechanism. See <KRL>attachment.doc for more details of triggers and traps.

The command interpreter: Each time a KRL-1 Command is invoked or completed (except a command to invoke the production mechanism), a production set called the command production set is invoked with a working set made up of the description contained in the command, and a description of the current process. The action associated with a production in this set can modify that context in specified ways (see <KRL>command.doc), which make it possible to do tracing, breaking, monitoring, simulation (as in Paul’s old match simulator) etc. Note that the user can do triggering on arbitrarily selected events, using the ExecuteCode command form (see <KRL>command.doc).

The reasoner -- internal events: We can think of the reasoner as itself being a program built up with a primitive set of commands to modify beliefs, establish goals, etc. A subset of these commands will cause production checking in the same way as the user-available commands. The system event prodution set will be checked on things such as AddDescriptorToAnchor, ConflictFound, etc. for further specification, see <KRL>systemEvents.doc

For each of these, there is a single well-specified time at which the production system is invoked, and therefore no ambiguity in how the control structure of the production action is interwoven with the control structure of the program which called the production system.

One of the fields in the interface for a production invocation is the process which gave the production system command. Through this, the action associated with the production can perform conditionally on what that process is, or can actually modify the process, the agenda on which it appears, etc. The resources used by the actions of a production system command are resources which belong to the invoker. (Of course since all resource computations are cooperative, an action can choose to decrement the resources from some other pool, rather than simply using the ones assigned to it).

In the simple production system model, the production memory is a simple set, and the only relevant operation is that of adding a new production to it. In our contexte, we need a more structured notion of how production sets can be built up out of component production sets. The KRL-0 signal path mechanism made one form of this possible. Viewed in production terms, it allowed the user to create a new production set from two old ones, one of which had to be simple (a single table) and the other had to be complex (an existing path). In the resulting set, productions in the simple set always took precedence over those in the pre-existing complex one, and there was a special mechanism ("pass the buck") for getting access to productions other than the first one satisfied.

From our more general production-oriented viewpoint, we want to allow a production set to be built up without imposing one specific conflict resolution strategy on the resulting combination. Therefore, we have a notion of a production set which includes:

conflict resolver: a process to be run whenever on a given invocation of the production mechanism with this set as input, more than one production is satisfied. This includes the case in which one of the direct productions is satisfied along with one or more of those inherited from the included sets.

When a production is invoked, part of the available information is the complete path (through layers of production set inclusion) from the set in which it appears to the set which was given as an argument to the production mechanism. There is no enforcement of uniqueness, so a single production might be found along several different paths. If so, a separate instantiation is created for each path, and this is treated as a conflict case, since there can be information bound along the paths (as descriptions of the intermediate production sets) which might be different along the different paths, leading to different actions.

4) Every production set uses the same conflict resolver which operates as follows: Do the action for the instantiation which has the shortest path (i.e. the one nearest the front of the path). If it returns the special result "pass the buck", then repeat the scheduling process, going to the item on the agenda with the next shortest path. If it returns any other value, the scheduler process terminates.

Every time a new production is added to a production set, it is entered into a global discrimination net of productions which is based on the pattern, not on the production set. It is tagged with the identity of the production set. At invocation, this global discrimination net is used to find all potentially matching productions (down to some level -- there are some efficiency issues here), which are then checked to see if their tag is included by some path in the production set given as an argument. The bookkeeping of paths is done with the general hierarchy mechanism (see <KRL>categories.doc).

Creation of productions and creation and changes to production sets are done using the normal Describe commands. Triggers associated with the units Production and ProductionSet do the necessary bookkeeping. It is not determined yet what kind of changes to a production will be allowed without throwing it away and starting over. It depends somewhat on the sophistication of the record keeping.

# ProductionInstantiation
production: A Production
invocation: A ProductionMechanismInvocation
matchedStuff: SetOf(A Belief)
matchAnchor: An Anchor
action: A KRLProcess
path:SequenceOf (A ProductionSet)
<A ProductionSet with productions = HasMember(My production), ...>
<..., The productionSet from My invocation>

# P???
self:A ProductionInstantiation with
matchedStuff =
An AddingNewMapPair with
template = Handle frob inUnit Foo
instance = My slotFiller
mapping = A MapBelief with
pairs = {<My selfInstance, Handle self inUnit Foo>...}
action = LispEvaluation
(LISP ’(DoFrob x y z) binding
x = IdentifyingAnchorFor(My selfInstance)
y = IdentifyingAnchorFor(My slotFiller)
z = IdentifyingAnchorFor(The path from My self)
selfInstance: An IdentifiedEntity
slotFiller: An IdentifiedEntity

# ProductionMechanismInvocation↑1
1: HasFunctional(self, ProductionCycle, productionSet, Quoted workingSetAnchor)
productionSet: A ProductionSet
workingSetAnchor: An Anchor
workingSet: SetOf(A Belief)
BeliefsCorrespondingTo(My workingSetAnchor)
activationSet:
SubsetOf(My workingSet)
SetOfAll(BeliefsCorrespondingTo(EmbeddedAnchor(My workingSetAnchor)
An ActivationAnchor)
conflictResolver: A SchedulerProcess
Default(The conflictResolver from My productionSet)
caller: A Process