Page Numbers: Yes First Page: 1
Heading:

UNPUBLISHED WORKING DRAFT - DO NOT COPY OR DISTRIBUTE
November 14, 1977 3:52 PM 6: Matcher [IFS]<KRL>specs>matcher.bravo

6. An overview of the matcher and the notion of aligning

In order to understand the full operation of the matcher, we will begin with the simplest version, and extend piece by piece. In the simplest version, the process can be thought of as "aligning" the two structures given as its arguments -- a pattern and a datum:

For each descriptor at the top level of the pattern structure, a corresponding descriptor must be found at the top level of the datum structure(i.e. one of the same type and with identical top-level sub-structure, such as the prototype of a map-descriptor or pointer of a coreference). If the pattern descriptor has internal structure (e.g. a map-descriptor with filler pairs, or an enumeration with descriptions of the elements) the process is done recursively, trying to align the corresponding parts of the pattern and datum descriptors. The process succeeds if every piece of the pattern has been successfully matched.

6.1 Extensions to the basic notion

There are a number of directions in which the idea of alignment has been extended. The extensions are partly orthogonal, but there are a number of interactions between them which will be discussed in detail below. As a quick overview of what is to come, the following list may be useful.

binding: The pattern can specify through meta-descriptions that some of its anchors and descriptors correspond to names which act as a kind of matcher variable. As a side-effect of the match, each of those variables is bound to a data object corresponding to the datum anchor or descriptor aligned with the anchor or descriptor to which it was attached.

structure-changing actions: The pattern can specify through meta-descriptions that some of the corresponding datum anchors and descriptors are to have modifications done to them. After the match has succeeded and all bindings made, all of these actions are carried out. They may in turn trigger other actions recursively.

multiple binding sets: More than one set of bindings can be returned for a match. Actions are taken for each set. This involves the splitting of contexts (see section below).

match tables: As in KRL-0, the alignment process is parameterized by providing a signal table which has responses used to control the different decisions made during the process. This table is a specific argument to the individual call to the matcher. It can abe built up out of standard tables (which provide a complete set of responses) and "fragments" each of which deal with one specific aspect. For example, what we have called "can match" is a combination of a match table which limits resources somehow (e.g. the SimpleMatchST) along with a response to the ValueForAlign signal which returns a successful binding set if the match was terminated for resource reasons, rather than finding a conflict.

LISP value returned: Rather than having a standard value returned, there is a signal which is probed in the match table before returning and its value used as the value to return. For each of the standard match tables there is a specific response, and there are match table fragments for standard variations on these.

following links for the datum: We think of the matcher as operating on a datum structure, but the structure used need not actually appear initially. As the Alignment proceeds, descriptors in the datum are used to derive further descriptors, subject to the limitations imposed by the particular match table. This is done by keeping a record of a set of links along with any datum description being aligned. The link specifies the place to go for further descriptors, and the context (world and substitution instance) needed for interpreting what is found there. Descriptors found by following these links are treated as through they had been in the original datum for purposes of finding information, but not for making stuctual changes.

conflict checking -- posts and categories: The category hierarchy is used to keep track of the categories associated with pattern anchors, and with the datum anchors (including those from following links) to which they are aligned. Checks are made to be sure these are consistent. Also, checks are made to discover when an anchor is described as referring to two distinct objects.

structure building for describing: Describing is treated almost exactly like matching, in that the pattern structure is aligned with the datum structure as far as possible with no actions being taken. The difference (which is specified by using the DescribeSF fragment in the match table -- see below) is that when doing a describe, when the alignment is stopped (due to resources, depth, etc.) and if values for all of the bindings have been found, then all those parts of the pattern which were not aligned with datum elements which actually appeared in the datum anchor are copied into the appropriate places (causing triggering, etc.)

resource limitation: There is a signal given for each of those aligner operations which could be thought of as using resources. The signal table can use these to modify resource counts and decide whether to continue. A binding is provided at the top level of the call to the matcher for an arbitrary description structure which the user wants to maintain for keeping track of things.

subgoal structures for satisfying the pattern: The internal structure of the aligner is based on a notion of goals and subgoals in a straightforward way. The operation includes setting up goals, probing a signal associated with a specific way of trying to achieve them, and going ahead if the signal says OK. The user is free to prevent methods from being tried (by responding SKIP), or to set up additional subgoal structures as part of the signal response. The user has access to the full data structure environment in doing his, so the goal structure manipulations can be as clever as the user wants to make them.

triggering of procedural attachment: There are triggers and traps (e.g. ToMatch, ToEnumerate) which are associated with specific goals set up in alignment (e.g. aligning a map descriptor, binding the elements of a set). These are probed in the same way as the signals, except that they are indexed by a specific unit and slot to which they apply, and are only probed for goals involving that slot. They have the same power to manipulate the goal structure as do the signal responses.

worlds: There is a simple world-inheritance mechanism making use of a contingency descriptor form in the declarative structures, and a user-programmed CompatibleWorld test.

defaults: When descriptors are derived by a link from a prototype, and they were marked as Default in the prototype, there is a signal UsingDefault which checks to see if they should be used at all. If so, the only time their origin is noted is if a conflict occurs in doing a Describe, in which case they are ignored. Note: this needs to be implemented.

6.2 The organization of the matching process

The data structures organized around a goal tree, a both-way-linked tree of Goal datatype instances. In general, there is a goal for each anchor and descriptor (recursively) in the pattern, and this provides the basic tree structure. The goal tree contains both AND and OR nodes. Each Goal contains information about what needs to be done, what the operands are, the links which have been found and those which have been tried, and the results which have been found at that node or propagated up the goal tree. A simplified version of the process is:

1. Arguments are given, specifying a pattern, a datum, and a match table. The pattern and datum are anchors or descriptors.

2. An initial top level goal is created. It is an AlignAnchor goal or an Align(SomeKindOfDescriptor) goal for the appropriate descriptor type, depending on the pattern.

3. This goal goes through a SETUP phase, during which its internal structure (e.g. the descriptors in the pattern anchor) is used to create subgoals, and simple successes and failures are discovered. This is done recursively on the subgoals which get created. At the end of this phase, either the entire goal has succeeded or failed, or there remains a tree of all those goals which were set up and could not be immediately resolved.

4. A control loop is entered which cycles through the active goals until the top-level goal is satisfied, or resource bounds are reached. On the first cycle for a goal, the descriptors in its datum are used to find results or potential links (e.g. a coreference). If a goal goes through this first cycle without finding results, then the servants associated with that goal type are invoked before any links are followed. On subsequent cycles all of the links added in the previous cycle are followed, potentially finding results or new links. If on any cycle nothing new happens for any goal, this is signalled.

5. If the alignment was successful, all of the actions are taken. Data structures representing bindings and actions are passed up the tree and combined as the individual goals which produce them succeed. Note that no actions happen until the top level goal has succeeded. There is also a mechanism for passing partial results.

6. A value is returned, determined by a signal, potentially returning the complete bindings list.

6.3. The top-level functions

There is one basic top-level function, Align, and a number of others (Seek, SeekAll, SeekMy, AddElement, AddDescriptor, SubsituteElement, SubstituteDescriptor, Describe and Overwrite) defined in terms of it for specifying simple cases. They are all CLISP forms which treat their arguments as though they were arguments to a normal lambda -- i.e. they are evaluated before being used. We will take each of these in turn.

(Align datum pattern matchTable)

The pattern and datum must be a handles to an anchor or descriptor. Note that a nexus appearing in the code will evaluate to such a handle. The match table must be a signal table with responses for the signals generated in the matcher. If it is NIL (or absent), a default match table is used -- see section on the Standard Tables below. In order for the access compiler to recognize combinations of standard tables, the pseudo-function MatchTable (which is equivalent to append) can be used. For example, (Align x y (MatchTable DescribeSF UseServantsSF CanMatchSF)) would do an Align with a table made up of those three standard tables.

The pattern can contain meta-descriptions specifying actions to be taken and variables to be bound (see section 7.1 below). For every successful match (see section on multiple-matches below), after the match is complete, all of the actions are taken.

The value returned by Align is determined by a signal. In the simplest case, it is a list of binding sets, one for each successful match. Each binding set is an A-list of variable name and value. This means that NIL is returned if the match was not successful. If no bindings were specified in the pattern, the value is a NIL binding set for each successful match. Thus a successful simple single match produces (NIL)

(Seek valueType groundingPath matchTable)

It is often much more convenient to think about the process of Seeking as working from a single description. Instead of saying "See if Danny is a person with last name = a name with first letter = <the thing I want to bind>", it is clearer to say "Find the first letter from a name that is the last name from a Person thatIs Danny". The thing which is the datum for the alignment (Danny in this case) appears inside a nesting of map descriptors, the thing to be bound is the anchor at the top of the nesting, and the pattern to be used is a kind of "unwinding" of the nesting, in which each map descriptor is grabbed from the other end -- e.g. the descriptor "the lastName from a person thatIs ..." in the seek specification becomes "A person with lastName = ..." in the pattern to be aligned. The full definition of just what kind of nesting is allowed (and special treatment of set membership) isn’t here, partly because we want to coordinate with the cases Rich has done so far in the access compiler.

(SeekAll valueType groundingPath matchTable)

Like Seek, but looks for all values as a list. See example below

(SeekMy valueType slotName matchTable)

This can be used only in the environment of a trigger activation. It is approximately equivalent to a Seek in which the grounding path is: The slotName from a <unit in which the trigger appears> thatIs <instance for which the triggering took place>. It gets this from the free variable environment, not lexically, so a trigger can call a function which in turn uses SeekMy (unstructured, but useful). In fact, it is slightly more general since the instance for which the triggering took place may not be a labelled anchor, but may be an unlabelled anchor or an effective description.

(Describe groundingPath newDesc matchTable)

Like Seek, but with an action of adding the pattern argument as a description in the place where the sought thing was found -- see example below.

The following set of top-level forms correspond to their corresponding action forms (described in 7.1) in the same way as Seek and Describe. Those forms which take either Anchors or Descriptors (e.g. MetaDescribe) can be used in this way only when their arguments are Anchors. Those which appear either on the anchor for the enumeration as a whole, or an individual element (e.g. AddBefore) can be used only when applied to the enumeration anchor. The grounding path cannot be used to indicate a descriptor or an element of an enumeration.

(Overwrite groundingPath newDesc matchTable)

(MetaDescribe groundingPath newDesc matchTable)

(Substitute groundingPath newAnchor matchTable)

(AddDescriptor groundingPath newDescriptor matchTable)

(SubstituteDescriptor groundingPath newDescriptor test count matchTable)

(AddElement groundingPath newAnchor matchTable)

(AddBefore groundingPath newAnchor test count matchTable)

(AddAfter groundingPath newAnchor test count matchTable)

(SubstituteElement groundingPath newAnchor test count matchTable)

(SeekElement groundingPath pattern test count matchTable)

(SeekDescriptor groundingPath pattern test count matchTable)

6.4. Some examples of calls to the matcher

Units used in the examples

# Person father: hometown: firstName: middleName: lastName:

# Family father: children: SetOf(A Person)

# Danny
self: A Person with
father = Jack
firstName = "Danny"
lastName = "Bobrow"
The father from a Family with children = {Kim, Debby, Jordy}
The father from a Child thatIs Kim
The father from a Child thatIs Debby

# Kim self: A Person with lastName = "Bobrow" age = 13

# Debby self: A Person with age = 9

# PaloAlto
self: The hometown from a Person with
firstName = "Danny"
lastName = "Bobrow"
thatIs Danny
The hometown from a Person thatIs Kim
The hometown from a Person with lastName = "Jones"
The hometown from a Person with lastName = "Smith"
The hometown from a Person with lastName = "Bobrow"

=======================

(Align \$Danny:self \A Person with father = @Do(’(Bind x Primary))/ SimpleSeekSF)

==> \$Jack:self

(Seek ’Primary \The father from a Person thatIs Danny/)

==> \$Jack:self

=======================

(Align \$PaloAlto:self
\The homeTown from a Person with lastName = @Do(’(Bind x Pointer))/
MultipleSeekSf)

==> ("Bobrow" "Bobrow" "Jones" "Smith" "Bobrow" )

(SeekAll ’Pointer \The lastName from a Person with homeTown = PaloAlto/)

==> ("Bobrow" "Bobrow" "Jones" "Smith" "Bobrow" )

=======================

(Align \$PaloAlto:self \The homeTown from
a Person with
lastName = "Bobrow"
firstName = "Danny"
middleName = @Do(’(Describe \A RussianName/))/)

==> (NIL)

(Describe \The middleName from a Person with
lastName = "Bobrow"
firstName = "Danny"
homeTown = PaloAlto/
\A RussianName/)

==> (NIL)

=======================

(Align (ValueOf ’x (Align \$PaloAlto:self
\The homeTown from
a Person with
lastName = "Bobrow"
firstName = "Danny"
self = @Do(’(Bind x Primary))/))
\A Person with middleName = @Do(’(Add \A RussianName/))/)

==> (NIL)

(Describe \The middleName from
a Person thatIs !Reference (Seek ’Primary
\A Person with
lastName = "Bobrow"
firstName = "Danny"
homeTown = PaloAlto/)
\A RussianName/)

==> (NIL)

=======================

(Align \$Danny:self \The father from a Family with
children = @Do(’(BindElement x Primary T ALL)))/)

==> (((x \$Kim:self \$Debby:self \$Jordy:self))))

(SeekElement ’Primary \The children from a Family with father = Danny/ T ALL)

==> (\$Kim:self \$Debby:self \$Jordy:self)

=======================

(Align \$Danny:self
\The father from a Child thatIs @Do(’(Bind x Primary)))/
MultipleMatchSF)

==> (((x . \$Kim:self)) ((x . \$Debby:self)))

(SeekAll ’Primary \A Child with father = Danny/)

==> (\$Kim:self \$Debby:self)

=======================

(Align \$Danny:self
\The father from a Child with
self = @Do(’(Bind x Primary))
age = @Do(’(Bind y Pointer))/
MultipleMatchSF)

==> (((x : \$Kim:self)(y : 13)) ((x : \$Debby:self)(y : 9)) )

no simplified form exists

=======================

# Column
self:↑11: Trigger(ToPrint, ’(For x in ’(top bottom sum)
do (PRINT(SeekMy ’Pointer x DoAFancyMatchST))))
top: An Integer
bottom: An Integer
sum:↑2 An Integer2: Trigger(ToFill, ’(LispForSum))

DEFINEQ((LispForSum()
(PROG ((top(SeekMy ’Pointer ’top)) (bottom(SeekMy ’Pointer ’bottom)))
(RETURN(AND top bottom (PLUS top bottom)]

=======================

# Column↑11: Comment("A cleaner version which also works")
top: An Integer
bottom: An Integer
sum:↑2 An Integer2: Trigger(ToFill, ’(LispForSum <(SeekMy ’Pointer ’top)
(SeekMy ’Pointer ’bottom)>)

DEFINEQ((LispForSum
(LAMBDA (L) (AND (EVERY L ’NUMBERP) (APPLY ’PLUS L]

=======================

6.5 The World mechanism

One of the interpreted map descriptors in KRL-1 corresponds closely to the contingency descriptor of KRL-0. The functional form During(worldDesc, objectDesc) can appear in any anchor with the following meaning:

If this descriptor appears in the pattern of an Align, then the AlignDescriptor goal associated with it is given a subgoal which is an AlignAnchor goal, in which the pattern anchor is that of the second argument (the objectDesc), and which has an associated world description of the first argument (worldDesc). World descriptions are inherited directly from their parent goals by subgoals which are not created in this way.

If an AlignAnchor goal has an associated world description, then the only descriptors used in testing for results are those "compatible" with that world. However, links which are not compatible can be followed looking for a compatible descriptor. For example, if I am matching with a non-trivial pattern world against an anchor containing a coreference (which does not appear in a contingency), then that coreference cannot be used as an answer. However, it can be followed in search of other descriptors which might themselves be apropriate contingency forms. The link mechanism keeps track of the worlds corresponding to where the link came from.

A descriptor is compatible with a world description if either:

It is a contingency, and the function (CompatibleWorld sought found) (which uses a user-catchable signal) returns Non-NIL. In this case it is the objectDesc, rather than the whole contingency that is used to check for results.

It is not a contingency, and the default world (the unmarked one) is compabtible with the world description

Actions which involve modifying structure which appear inside a contingency in the pattern are handled as with any modification (i.e. the addition of structure starts from the furthest embedded existing structural grounding) with the following addition:

If the structural grounding is in an anchor with the same world as the pattern world, the modification is made directly

If the structural grounding is an anchor for a compatible world, then the modification is made inside a contingency added to that anchor for the pattern world. In the case of set and sequence modifications, this means copying the previous structure and modifying the copy.

6.6. The Access Compiler

The basic calls to the matcher (Align, Seek, etc.) are CLISP forms. When first encountered, the access compiler is called. It checks to see if the signal table argument is of a form it recognizes and knows how to compile. If so it examines the arguments (typically each a nexus) and if it can, compiles a set of direct accesses which avoid going through the overhead of setting up the full matcher data structures. If for any reason, it cannot provide specialized code, it compiles the CLISP form into a call to the generalized matcher.

Note that this means that the environment in which a trigger or trap is run will depend on whether the call to Align which set it off is specialized by the access compiler, or is made into a general matcher call. The conventions for procedural attachment are designed so that a trigger or trap which is written to work in the simple (access-compiled) environment will have the same effect in the more complex environement provided by the full matcher. Whenever one is invoked, the variable FULLALIGN will be available to test. Triggers which do more complex things involving effective descriptions, goals, etc. need to check it before proceeding.

Detailed design of the compiler is not included here, since Rich has already done much of it and we need to coordinate. Details of the cases it handles are those of the associated signal tables. It may also turn out that for initial versions of the implementation, it will not handle the full flexibility of the binding and action Do meta-descriptions, and that the full Aligner will be run when they are used. It is possible to extend the compiler incrementally, since there is a fall back for anything it recognizes it can’t handle.

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.