Page Numbers: Yes  First Page: 1
Heading:z18697l3528d2999x2e8qk72(635)
UNPUBLISHED WORKING DRAFT - DO NOT COPY OR DISTRIBUTE
November 14, 1977  3:52 PM  	  	6: Matcher   		[IFS]<KRL>specs>matcher.bravoz18697y774x2e8qck72\b25f5 29f0B
6. An overview of the matcher and the notion of aligningz18697l3528d2999x2e12ck72\f5b
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:z18697x2e6jk72
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. z18168l3528x2e6jk72
6.1 Extensions to the basic notionz18697l3528d2999x2e12k72\f5b
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.z18697x2e6jk72
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. z18697l4057d3528x2e6jk72\b8B
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.z18697l4057d3528x2e6jk72\b27B296b
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).z18697l4057d3528x2e6jk72\b22B154b
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.z18697l4057d3528x2e6jk72\b13B554i13I128b
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.z18697l4057d3528x2e6jk72\b20B64i1I233b
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.z18697l4057d3528x2e6jk72\b30B324i5I
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.z18697l4057d3528x2e6jk72\b42B
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.)z18697l4057d3528x2e6jk72\b34B605b
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.z18697l4057d3528x2e6jk72\b20B365b
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.z18697l4057d3528x2e6jk72\b46B
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.z18697l4057d3528x2e6jk72\b38B
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.z18697l4057d3528x2e6jk72\b7B165b
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.z18697l4057d3528x2e6jk72\b9B126i12I174bi34BI1b
6.2 The organization of the matching processz18697l3528d2999x2e12k72\f5b
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: z18697x2e6jk72\39i9I
1. Arguments are given, specifying a pattern, a datum, and a match table.  The pattern and datum are anchors or descriptors.z18168l3704d3352x2e6jk72
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.z18168l3704d3352x2e6jk72
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.z18168l3704d3352x2e6jk72
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.z18168l3704d3352x2e6jk72
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.z18168l3704d3352x2e6jk72
6. A value is returned, determined by a signal, potentially returning the complete bindings list.z18168l3704d3352x2e6jk72
6.3. The top-level functionsz18697l3528d2999x2e12k72\f5b
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.z18697x2e12jk72
(Align datum pattern matchTable)z18697x2e12jk72\b6B1i24bI1B
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.    z18697l3528x2e6jk72
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.z18697l3528x2e6jk72
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)z18697l3528x2e6jk72
(Seek valueType groundingPath matchTable)z18697x2e12jk72\b5B1i34bI1B
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.   z18697l3528x2e6jk72\198i26I
(SeekAll valueType groundingPath matchTable)z18697x2e12jk72\b8B1i34bI1B
Like Seek, but looks for all values as a list.  See example below   z18697l3528x2e6jk72
(SeekMy valueType slotName matchTable)z18697x2e12jk72\b7B1i29bI
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.   z18697l3528x2e6jk72\144i8I8i36I7i46I
(Describe groundingPath newDesc matchTable)z18697x2e12jk72\b9B1i32bI1B
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.   z18697l3528x2e6jk72
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.z18697x2e12jk72\542b
(Overwrite groundingPath newDesc matchTable)z18697x2e12jk72\b10B1i32bI1B
(MetaDescribe groundingPath newDesc matchTable)z18697x2e2jk72\b13B1i32bI1B
(Substitute groundingPath newAnchor matchTable)z18697x2e2jk72\b11B1i34bI1B
(AddDescriptor groundingPath newDescriptor matchTable)z18697x2e2jk72\b14B1i38bI1B
(SubstituteDescriptor groundingPath newDescriptor test count matchTable)z18697x2e2jk72\b21B1i49bI1B
(AddElement groundingPath newAnchor matchTable)z18697x2e2jk72\b11B1i34bI1B
(AddBefore groundingPath newAnchor test count matchTable)z18697x2e2jk72\b10B1i45bI1B
(AddAfter groundingPath newAnchor test count matchTable)z18697x2e2jk72\b9B1i45bI1B
(SubstituteElement groundingPath newAnchor test count matchTable)z18697x2e2jk72\b18B1i45bI1B
(SeekElement groundingPath pattern test count matchTable)z18697x2e2jk72\b12B1i43bI1B
(SeekDescriptor groundingPath pattern test count matchTable)z18697x2e2jk72\b15B1i43bI1B
6.4. Some examples of calls to the matcherz18697l3528d2999x2e12k72\f5b
Units used in the examplesz18697l3528d2999x2e12k72\f5b
# Person   father:   hometown:   firstName:   middleName:   lastName:z18697l3528d2999x2e12k72\2b6B3b7B3b9B3b10B3b11B3b9B
# Family   father:   children: SetOf(A Person)z18697l3528d2999x2e12k72\2b6B3b7B3b9B
# 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 Debbyz18697l3528d2999x2e12k72\2b11B
# Kim  self: A Person with    lastName = "Bobrow"    age = 13z18697l3528d2999x2e12k72\2b10B
# Debby  self: A Person with age = 9z18697l3528d2999x2e12k72\2b12B
# 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"
		z18697l3528d2999x2e12k72\2b14B
=======================z18697l3528d2999x2e12ck72
(Align \$Danny:self \A Person with father = @Do('(Bind x Primary))/ SimpleSeekSF)z18697l3528d2999x2e12k86
==> \$Jack:selfz18697l6068d5539x2k72\f1
(Seek 'Primary \The father from a Person thatIs Danny/)z18697l4798d4269x2e6k72\i55f1
==> \$Jack:selfz18697l6068d5539x2\f1i4I6i5f0
=======================z18697l3528d2999x2e12ck72
(Align \$PaloAlto:self
		\The homeTown from a Person with lastName = @Do('(Bind x Pointer))/
		MultipleSeekSf)z18697l3528d2999x2e12k72
==> ("Bobrow" "Bobrow" "Jones" "Smith" "Bobrow" )z18697l6068d5539x2k72\f1 4i45I
(SeekAll 'Pointer \The lastName from a Person with homeTown = PaloAlto/)z18697l4798d4269x2e12k72\i
==> ("Bobrow" "Bobrow" "Jones" "Smith" "Bobrow" )z18697l6068d5539x2k72\f1i
=======================z18697l3528d2999x2e12ck72
(Align \$PaloAlto:self \The homeTown from
							a Person with
								lastName = "Bobrow"
								firstName = "Danny"
								middleName = @Do('(Describe \A RussianName/))/)z18697l3528d2999x2e12k72
==> (NIL)z18697l6068d5539x2k72\f1
(Describe \The middleName from a Person with
											lastName = "Bobrow"
											firstName = "Danny"
											homeTown = PaloAlto/
			\A RussianName/)z18697l4798d4269x2e12k72\i
==> (NIL)z18697l6068d5539x2k72\f1i
=======================z18697l3528d2999x2e12ck72
(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/))/) z18697l3528d2999x2e12k72
==> (NIL)z18697l6068d5539x2k72\f1
(Describe \The middleName from
				a Person thatIs !Reference (Seek 'Primary
													  \A Person with
															lastName = "Bobrow"
															firstName = "Danny"
															homeTown = PaloAlto/)
			\A RussianName/)z18697l4798d4269x2e12k72\i
==> (NIL)z18697l6068d5539x2k72\f1 4i5I
=======================z18697l3528d2999x2e12ck72
(Align \$Danny:self \The father from a Family with
							children = @Do('(BindElement x Primary T ALL)))/)z18697l3528d2999x2e12k108
==> (((x \$Kim:self \$Debby:self \$Jordy:self))))z18697l6068d5539x2e6k72\f1
(SeekElement 'Primary \The children from a Family with father = Danny/ T ALL)z18697l4269d3740x2e12k72\i77I
==> (\$Kim:self \$Debby:self \$Jordy:self)z18697l6068d5539x2e6k72\f1
=======================z18697l3528d2999x2e12ck72
(Align \$Danny:self
		\The father from a Child thatIs @Do('(Bind x Primary)))/
		MultipleMatchSF)z18697l3528d2999x2e12k72
==> (((x . \$Kim:self)) ((x . \$Debby:self)))z18697l6068d5539x2e6k72\f1
(SeekAll 'Primary \A Child with father = Danny/)z18697l4798d4269x2e12k72\i48I
==> (\$Kim:self \$Debby:self)z18697l6068d5539x2e6k72\f1
=======================z18697l3528d2999x2e12ck72
(Align \$Danny:self
		\The father from a Child with
							self = @Do('(Bind x Primary))
							age = @Do('(Bind y Pointer))/
		MultipleMatchSF)z18697l3528d2999x2e12k72
==> (((x : \$Kim:self)(y : 13))  ((x : \$Debby:self)(y : 9)) )z18697l6068d5539x2e6k72\f1
no simplified form existsz18697l4798d4269x2e6k72\i25I
=======================z18697l3528d2999x2e12ck72
# Column
self:^1		1: Trigger(ToPrint, '(For x in '(top bottom sum)
									do (PRINT(SeekMy 'Pointer x DoAFancyMatchST))))
top: An Integer
bottom: An Integer
sum:^2 An Integer						2: Trigger(ToFill, '(LispForSum))z18697l3528d2999x2e12k72\2b12f1o4 2f0o0B2f1 57f0 1f1 47f0 1b4B12b7B12b4f1o4 2f0o0B17f1
DEFINEQ((LispForSum()
	(PROG ((top(SeekMy 'Pointer 'top)) (bottom(SeekMy 'Pointer 'bottom)))
		(RETURN(AND top bottom  (PLUS top bottom)]z18697x2e12k72
=======================z18697l3528d2999x2e12ck72
# Column^1			1: Comment("A cleaner version which also works")
top: An Integer
bottom: An Integer
sum:^2 An Integer			2: Trigger(ToFill, '(LispForSum <(SeekMy 'Pointer 'top) 
															  (SeekMy 'Pointer 'bottom)>)z18697l3528d2999x2e12k108\2b6f1o4 2f0o0B3f1 48f0 1b4B12b7B12b4f1o4 2f0o0B14f1
DEFINEQ((LispForSum
	(LAMBDA (L) (AND (EVERY L 'NUMBERP) (APPLY 'PLUS L]z18697x2e12k72
=======================z18697l3528d2999x2e12c
6.5  The World mechanismz18697l3528d2999x2e12k72\f5b
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:z18697x2e6jk72\129b7Bi9I2i10bI1B
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.z18697l4057d3528x2e6jk72
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.z18697l4057d3528x2e6jk72
A descriptor is compatible with a world description if either:z18697l4057d3528x2e6jk72
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.  z18697l4621d4092x2e6jk72
It is not a contingency, and the default world (the unmarked one) is compabtible with the world descriptionz18697l4621d4092x2e6jk72
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:z18697l4057d3528x2e6jk72
If the structural grounding is in an anchor with the same world as the pattern world, the modification is made directlyz18697l4621d4092x2e6jk72
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.z18697l4621d4092x2e6jk72
6.6. The Access Compilerz18697l3528d2999x2e9k72\f5b
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.z18697x2e6jk72
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.z18697x2e6jk72
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.z18697x2e6jk72
6.7 Details of the matcher classesz18697l3528d2999x2e12k72\f5b
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.).  z18697d3528x2e12jk40
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.z18697d3528x2e12jk40\72i4I423i4I
The class types and their messages are given in the appropriate files. probably a summary should be put in here:z18697d3528x2e12jk40\71bi40BI
6.8 Details of the matcher recordsz18697l3528d2999x2e12k72\f5b
(DATATYPE Goal (suspended goalStatus goalType resultType
				goalDesc patternContext datum datumContext
				anchorPath patCategories goalArgs
				links oldLinks
				goalNumber parent children
				results immediateResults completeBindings))z18697l4410d2999x2e12k72\10b4B
This is the basic data structure.  A goal is set up for any alignment or binding.  The fields are:z18697d3528x2e12jk40
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.z18697l4057d3528x2e6jk40\b9B
resultType: An atom, which is the name of a result type class, as explained for goalTypez18697l4057d3528x2e6jk40\b11B
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. z18697l4057d3528x2e6jk40\b11B
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.z18697l4057d3528x2e6jk40\b10B
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.  z18697l4057d3528x2e6jk40\b9B
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.z18697l4057d3528x2e6jk40\b9B
patternContext: A full context from which the pattern is derived. z18697l4057d3528x2e6jk40\b16B
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.z18697l4057d3528x2e6jk40\b14B147b
datum: A Descriptor or Anchor handle.  It is set when the goal is first created, and does not change. z18697l4057d3528x2e6jk40\b7B
datumContext: A FullContext record.z18697l4057d3528x2e6jk40\b13B
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.z18697l4057d3528x2e6jk40\b11B
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.z18697l4057d3528x2e6jk40\b6B
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.z18697l4057d3528x2e6jk40\b9B
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 goalsz18697l4057d3528x2e6jk40\b11B178b
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.z18697l4057d3528x2e6jk40\b7B
children: A list of Goals, each with this one as parent.z18697l4057d3528x2e6jk40\b9B
results: A List of Result records.z18697l4057d3528x2e6jk40\b8B
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.z18697l4057d3528x2e6jk40\b17B
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.z18697l4057d3528x2e6jk40\b17B229bi43BI
# # # # # # # # # # # # # # #z18697x2e12ck72
(RECORD Link (structure . fullContext))z18697l4410d2999x2e12k72\8b4B
This is the structure for representing complete contextual information along with a descriptor or anchor.z18697d3528x2e12jk40
structure: A Handle to the descriptor or anchor.z18697l4057d3528x2e6jk40\b10B
fullContext: A FullContext.  Describes the substitution context (template and instance) from which the structure was taken.  NIL if context is unknown or defaultz18697l4057d3528x2e6jk40\b12B
(RECORD FullContext (context . world))z18697l4410d2999x2e12k72\8b11B
context: A Context Record.  NIL if substitution context is unknown or defaultz18697l4057d3528x2e6jk40\b8B
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 defaultz18697l4057d3528x2e6jk40\b6B
(RECORD Context (linkProto . instance))z18697l4410d2999x2e12k72\8b7B
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.z18697l4057d3528x2e6jk40\119b
linkProto: A handle to a self-slot anchorz18697l4057d3528x2e6jk40\b10B
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.z18697l4057d3528x2e6jk40\b9B
# # # # # # # # # # # # # # #z18697x2e12ck72
(RECORD Result (bindings actions . resultValue))z18697l4410d2999x2e12k72\8b6B
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.  z18697d3528x2e12jk40
bindings: A list of Binding records with distinct variables (no two alike).z18697l4057d3528x2e6jk40\b9B
actions: A list of Action recordsz18697l4057d3528x2e6jk40\b7B
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.z18697l4057d3528x2e6jk40\b12B
# # # # # # # # # # # # # # #z18697x2e12ck72
(RECORD Binding (bindingVariable bindingValue . virtualFlg))z18697l4410d2999x2e12k72\8b7B
This is the structure for representing a value bound to a variable.  z18697d3528x2e12jk40
bindingVariable: A LITATOMz18697l4057d3528x2e6jk40\b16B
bindingValue: An arbitrary thing bound to the variable z18697l4057d3528x2e6jk40\b12B
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.z18697l4057d3528x2e6jk40\b12B
# # # # # # # # # # # # # # #z18697x2e12ck72
(RECORD Action (actionForm actionSpec actionBinding . actionParent))z18697l4410d2999x2e12k72\8b6B
This is the structure for representing an action to be done when a match is complete.  z18697d3528x2e12jk40
actionForm: An ActionForm record.  The actual argument to the Do which created this action.z18697l4057d3528x2e6jk40\b11B
actionSpec: An ActionForm record.  Parallels the actionForm, but with the arguments evaluated (including substituting an internal type name for the actionType) z18697l4057d3528x2e6jk40\b10B
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.z18697l4057d3528x2e6jk40\b14B
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.z18697l4057d3528x2e6jk40\b13B
# # # # # # # # # # # # # # #z18697x2e12ck72
(RECORD ActionForm (actionType actionArg actionTest actionCount)
		(RECORD ActionForm (actionType . actionArgs))z18697l4410d2999x2e12k72\8b11B
This structure is the template for the specifications of actions for Do (see section 7.1 in the specs).  z18697d3528x2e12jk40
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).z18697l4057d3528x2e6jk40\b11B
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.  z18697l4057d3528x2e6jk40\b9B
actionTest: See 7.1.z18697l4057d3528x2e6jk40\b11B
actionCount: See 7.1.z18697l4057d3528x2e6jk40\b12B
# # # # # # # # # # # # # # #z18697x2e12ck72
(RECORD BindingForm (bindingType variableSpec valueType bindingTest bindingCount))z18697l4410d2999x2e12k72\8b11B63b
This structure is the template for the specifications of bindings for Do (see section 7.1 in the specs).  z18697d3528x2e12jk40
bindingType: An atom.  One of Bind, BindElement.z18697l4057d3528x2e6jk40\b12B
variableSpec: An atom (to be used without evaluation) or something which evaluates to an atom.  See section 7.1 for details.  z18697l4057d3528x2e6jk40\b12B
valueType: An atom (to be used without evaluation) or something which evaluates to an atom.  See 7.1.z18697l4057d3528x2e6jk40\b10B
bindingTest: See 7.1.z18697l4057d3528x2e6jk40\b12B
bindingCount: See 7.1.z18697l4057d3528x2e6jk40\b13B
(RECORD TrapForm (trapType trapAnchor trapActions))z18697l4410d2999x2e12k72\8b8B
This is used for setting off demons.z18697l4057d3528x2e6jk40\36b
trapType: One of Identified, Described, Changed, Filled, EnumerationChangedz18697l4057d3528x2e6jk40\b9B
trapAnchor: An anchor for which the trap is set offz18697l4057d3528x2e6jk40\b11B
trapActions: A list of Action records -- the actions which set it off.z18697l4057d3528x2e6jk40\b12B
(RECORD TriggerForm (triggerType triggerTemplate triggerPrototype triggerInstance))z18697l4410d2999x2e12k72\8b11B
This is used for setting off demons.z18697l4057d3528x2e6jk40\36b
triggerType: One of Identified, Described, Changed, Filled, EnumerationChangedz18697l4057d3528x2e6jk40\b12B
triggerTemplate: A slot anchorz18697l4057d3528x2e6jk40\b16B
triggerPrototype: The self slot anchor for the unit in which the triggerTemplate appearsz18697l4057d3528x2e6jk40\b17B
triggerInstance: An anchorz18697l4057d3528x2e6jk40\b16B
triggerAction: A list of Action records -- the actions which set it off.z18697l4057d3528x2e6jk40\b14B
# # # # # # # # # # # # # # #z18697x2e12ck72
(RECORD Count (totalNum complete initialNum . finalNum)
			(Count (totalNum complete . sequence))z18697l4410d2999x2e12k72\8b5B
This structure is used to specify the nature of an enumeration, so that descriptors can be checked to see if they could satisfy it.  z18697d3528x2e12jk40
totalNum: An integer.  The minimum number of elements which could be in a satisfactory enumerationz18697l4057d3528x2e6jk40\b9B
complete: T or NIL, specifying whether the enumeration must be complete.  If T, it means that the enumeration must contatin exactly totalNum elements.  z18697l4057d3528x2e6jk40\b8B
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.z18697l4057d3528x2e6jk40\b11B
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.z18697l4057d3528x2e6jk40\b9B
sequence: If this is NIL (which implies that initialNum and finalNum aren't given) the enumeration is for a set, rather than sequence.z18697l4057d3528x2e6jk40\b9B
6.7 Overview of the matcher functionsz18697l3528d2999x2e12k72\f5b
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.z18697l3528d2999x2e6jk40\b9B160b14B
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.z18697l3528d2999x2e6jk40\b7B
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.z18697l3528d2999x2e6jk40\b9B6b22B387b8B
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.z18697l3528d2999x2e6jk40\b11B
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.z18697l3528d2999x2e6jk40\b13B
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.z18697l3528d2999x2e6jk40\b10B
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.z18697l3528d2999x2e6jk40\b12B317b11B