[Indigo]<KRL>document>match-full-spec!1

Page Numbers: Yes First Page: 1
Heading:

April 28, 1979 12:46 PM [IVY]<KRL>document>match-full-spec

6.7 Details of the matcher classes

The code within the matcher makes heavy use of a class/instance notion like that of SMALLTALK. There are three kinds of objects which are instances of classes: Goals, Actions, and Descriptors. The class for a descriptor is its descriptor type (i.e. what TypeD would give when applied to it). The class for an action is its action type (e.g. AddElement). The names of these are prefixed with a # to avoid convflict with their use as CLISP words. Each goal is a member of two classes. One, its GoalType, is what needs to be done (e.g. AlignAnchor, FindEnumeration, etc.). The other, its ResultType is what to do when it suceeds, fails, etc. (e.g. ConjunctiveSubgoal, EquivalentGoal, TopLevelGoal, etc.).

A class definition is a function of two arguments (the instance (called self) and the message) which has as its top level a SELECTQ on the message. For each category of classes (e.g. action classes) there is a small fixed set of recognized messages. Note that this is somewhat different from smalltalk, which expects every class definition to give its own list of acceptable messages. The function SendMessages (implemented as APPLY*) runs the code for the class, with the message recipient (the self argument) bound. Any other communication is through free variables.

The class types and their messages are given in the appropriate files. probably a summary should be put in here:

6.8 Details of the matcher records

(DATATYPE Goal (suspended goalStatus goalType resultType
goalDesc patternContext datum datumContext
anchorPath patCategories goalArgs
links oldLinks
goalNumber parent children
results immediateResults completeBindings))

This is the basic data structure. A goal is set up for any alignment or binding. The fields are:

goalType: An atom, which is the name of a goal type class. Every goal is an instance of two classes -- its goalType and resultType. The goalType determines what to do to satisfy it, and the resultType what to do with its results.

resultType: An atom, which is the name of a result type class, as explained for goalType

goalStatus: One of the atoms NOTSETUP, NEW, AFTERFIRST, WAITING, ACTIVE, SUCCEEDED, FAILED, ABORTED. A goal is initially NOTSETUP, becomes NEW after receiving SETUP, becomes AFTERFIRST when it has been started up, but initial triggers haven’t been tried, WAITING if it is still live, but has no activities to do except wait for results from its subgoals, ACTIVE if it is still looking through the datum, SUCCEEDED, FAILED, and ABORTED are obvious.

suspended: T or NIL. A goal can be suspended at any time, and no further work is done on it. It can later be resumed and continue where it left off. If this field is simply clobbered, the subgoals will be unaffected. If the functions GoalSuspended and GoalResumed are used, the sugoals are suspended or resumed as well. This field is T for all complete (ABORTED, SUCCEEDED, or FAILED) goals.

goalDesc: This is the description of the goal. For Align goals it is the pattern structure. For Find goals, it is the binding or action to be done when the thing is found.

goalArgs: This is a place to hang arbitrary information on a goal. Its contents for each goal type are described in the comments associated with that goal type class.

patternContext: A full context from which the pattern is derived.

patCategories: A List of mapDescriptors, whose focus slots are to be checked for category conflict with descriptors found in the datum or in following its links.

datum: A Descriptor or Anchor handle. It is set when the goal is first created, and does not change.

datumContext: A FullContext record.

anchorPath: A list, each element of which is a descriptor handle or anchor handle. This is non-NULL only when the datum element is a direct descendant (i.e. without followng links of any kind) of the original datum given to the FullAlign. Its CAR is always EQH to the structure of the datum, the next element is the anchor or descriptor which contained that one, etc. Actions which modify structure can only be done on datum elements which are on an anchor path.

links: A list, each element of which is a Link record. Each link represents a place to get more descriptors which apply to the datum. Links are added in two basic ways: when going into a fillerPair, a link is set up to the slot prototype; and when any descriptor is found in the datum (or in an anchor found from a link), it is checked to see if it provides a link (e.g. a coreference). They can also be used to find relevant triggers. See the description of Link for details. Although the fullDatum is a Link record, it is not in the list of links.

oldLinks: A pointer into the list of links, indicating which ones have been processessed. New links are always pushed onto the front of links, and oldLinks works its way up from the bottom.

goalNumber: an integer or NIL. It is set when a goal is printed out, and used as a unique identifier for the goal until the GoalArray is cleared. It is set to the atom FREE for free goals

parent: A Goal. NIL for top-level goal. Used as the link for goals on the free list, pointing to to the next free goal, or NIL if there is none.

children: A list of Goals, each with this one as parent.

results: A List of Result records.

immediateResults: A List of Result records. This is needed because the system avoids setting up full goal structures when a result can be found immediately. If an anchor has three descriptors, for example, and results from matching two of them can be found without setting up goals, the results must be stored with the AlignAnchor goal, while the third goal is running, then combined (to make sure bindings agree) with its results to produce the actual results for the AlignAnchor.

completeBindings: A List of atoms, each representing a variable for which it is known that no further binding values will be found. This is propagated up and down the tree to make use of pruning when a variable is bound in more than one place. Note: the code does not yet do any of this.

# # # # # # # # # # # # # # #

(RECORD Link (structure . fullContext))

This is the structure for representing complete contextual information along with a descriptor or anchor.

structure: A Handle to the descriptor or anchor.

fullContext: A FullContext. Describes the substitution context (template and instance) from which the structure was taken. NIL if context is unknown or default

(RECORD FullContext (context . world))

context: A Context Record. NIL if substitution context is unknown or default

world: An anchor which describes a world. Used only in calls to CompatibleWorld, SameWorld, and user-supplied world functions. NIL if world is unknown or default

(RECORD Context (linkProto . instance))

This will be NIL if the link is not to an instance of a prototype, e.g. if it is the result of following a coreference.

linkProto: A handle to a self-slot anchor

instance: A Link record for the instance associated with the mapping. The structure of that Link is either another anchor, or a map descriptor which is interpreted as describing a mapping whose SELF filler is the desired instance.

# # # # # # # # # # # # # # #

(RECORD Result (bindings actions . resultValue))

This is the structure for returning results at each level in the goal tree. Each of these records represents a coordinated set of bindings and actions -- i.e. there is only one binding for any one variable, and the actions are to use those bindings.

bindings: A list of Binding records with distinct variables (no two alike).

actions: A list of Action records

resultValue: ANY -- The returnValue field is used for deciding what to return as the value of Align, if this is a result for a top level goal. It can be set by the user to override defaults.

# # # # # # # # # # # # # # #

(RECORD Binding (bindingVariable bindingValue . virtualFlg))

This is the structure for representing a value bound to a variable.

bindingVariable: A LITATOM

bindingValue: An arbitrary thing bound to the variable

vitrtualFlg: T or NIL. T means that the value is a list which was generated internally, rather than found explicitly (e.g. by a BindElement with count = ALL). In checking for binding compatibility, if two bindings with the same variable name have this flag set, a set equality check is used which ignores order.

# # # # # # # # # # # # # # #

(RECORD Action (actionForm actionSpec actionBinding . actionParent))

This is the structure for representing an action to be done when a match is complete.

actionForm: An ActionForm record. The actual argument to the Do which created this action.

actionSpec: An ActionForm record. Parallels the actionForm, but with the arguments evaluated (including substituting an internal type name for the actionType)

actionBinding: An anchor path (list of handles as described in Goal). The action is to be taken to the CAR of the path. The path is needed to decide what triggering to do of demons.

actionParent: An Action record or NIL. In expanding an action specified by the user, the system builds new actions which carry out subparts of the job. They are linked in a tree (only upward links), in order to avoid redundant triggering.

# # # # # # # # # # # # # # #

(RECORD ActionForm (actionType actionArg actionTest actionCount)
(RECORD ActionForm (actionType . actionArgs))

This structure is the template for the specifications of actions for Do (see section 7.1 in the specs).

actionType: An atom. For ActionForms typed by the user, it will be one of Describe, OverWrite, Substitute, SubstituteDescriptor, AddDescriptor, AddElement, AddBefore, AddAfter, SubstituteElement. For internally created ones (e.g. the ones which appear as the actionSpec of an Action), it will be the name of an action type class (see classes.bravo for a list of the ones currently implemented).

actionArg: A handle or Lisp pointer. This is the argument specifying the change to be made -- the new thing, or thing to be substituted, etc. See section 7.1 for details.

actionTest: See 7.1.

actionCount: See 7.1.

# # # # # # # # # # # # # # #

(RECORD BindingForm (bindingType variableSpec valueType bindingTest bindingCount))

This structure is the template for the specifications of bindings for Do (see section 7.1 in the specs).

bindingType: An atom. One of Bind, BindElement.

variableSpec: An atom (to be used without evaluation) or something which evaluates to an atom. See section 7.1 for details.

valueType: An atom (to be used without evaluation) or something which evaluates to an atom. See 7.1.

bindingTest: See 7.1.

bindingCount: See 7.1.

(RECORD TrapForm (trapType trapAnchor trapActions))

This is used for setting off demons.

trapType: One of Identified, Described, Changed, Filled, EnumerationChanged

trapAnchor: An anchor for which the trap is set off

trapActions: A list of Action records -- the actions which set it off.

(RECORD TriggerForm (triggerType triggerTemplate triggerPrototype triggerInstance))

This is used for setting off demons.

triggerType: One of Identified, Described, Changed, Filled, EnumerationChanged

triggerTemplate: A slot anchor

triggerPrototype: The self slot anchor for the unit in which the triggerTemplate appears

triggerInstance: An anchor

triggerAction: A list of Action records -- the actions which set it off.

# # # # # # # # # # # # # # #

(RECORD Count (totalNum complete initialNum . finalNum)
(Count (totalNum complete . sequence))

This structure is used to specify the nature of an enumeration, so that descriptors can be checked to see if they could satisfy it.

totalNum: An integer. The minimum number of elements which could be in a satisfactory enumeration

complete: T or NIL, specifying whether the enumeration must be complete. If T, it means that the enumeration must contatin exactly totalNum elements.

initialNum: The number of elements at the front of a sequence which must be explicitly given (i.e. not ellipsis) in order to be able to determine a match with the pattern which set up this count.

finalNum: The number of elements at the end of a sequence which must be explicitly given (i.e. not ellipsis) in order to be able to determine a match with the pattern which set up this count.

sequence: If this is NIL (which implies that initialNum and finalNum aren’t given) the enumeration is for a set, rather than sequence.

6.7 Overview of the matcher functions

FullAlign: the top level. Creates a top level goal and calls RunGoal. Most of the code in the entire matcher includes exits for success, abort, or failure by calling AlignCompleted, which in turn does a RETFROM FullAlign after releasing the storage space for the goals and signalling for a return value.

RunGoal. Sets up lists of activeGoals and oldGoals. Cycles through the active goals in a depth first way, doing one round of link following each time. It has signals if it runs out of things to do, but usually it is jumped out of by an abort, or a success or failure of the top level goal.

SetUpGoal (and SetUpGoalForDescriptor) -- Sends the message SETUP to the relevant descriptor or goal type, along with an initial Goal Record with all the relevant information. The response to SETUP does the initial check for quick match, recursively setting up the goals needed for a more careful match in the meantime. Value returned is not used, since side effects are used to cause result propagation. In particular, GoalDone is used to terminate a goal and propagate its results (both actions/bindings and success/failure) up and down the tree.

StartUpGoal: Sends the goal the message STARTUP, then tries each of descriptors in the original datum, then the message AFTERFIRST, then puts the goal on activeGoals if it hasn’t finished. It is written in a style which copes with the possibility that actions done by one of the messages may change the status of the goal, and make the rest of them unneccesary.

TryDescriptor: does the work for each descriptor found in trying to satisfy a goal. First sends the descriptor the message TRY, which allows it to replace itself (e.g. a contingency being equivalent to its embedded anchor, or a reflexive being replaced by the corresponding map descriptor). Then the goal is sent the message NEWDESCRIPTOR, then the descriptor is sent ADDLINK, and for each link it adds, the goal is sent NEWLINK.

DoActions: When a match succeeds, all the associated actions are done in a breadth-first batched kind of way. They each receive a sequence of messages -- EXPAND which they respond to by creating sets of primitive subgoals (recursively), BEFORE which triggers before-demons, DO which actually carries out the action, WHEN which triggers when-demons. During all of this, any of the actions or demons can add new actions to be done on the next loop of the DoActions.

SendMessage: The primitive for calling classes. Currently the way things are set up, it is an equivalence for APPLY*. To send a message to an object, you use both the object and a sub-categorization. E.g. every goal has both a goalType and a resulType, which are classes which accept different messages. I have put all of the SendMessage’s in bold face, since that is the access path to all the stuff in the file classes.bravo, and is where much of the action takes place.