Page Numbers: Yes First Page: 1
Heading:

UNPUBLISHED WORKING DRAFT - DO NOT COPY OR DISTRIBUTE
November 16, 1977 2:23 PM 7: Details [IFS]<KRL>specs>details.bravo

7. Detailed specification of the matcher

7.1 Standardly recognized meta-descriptions in the pattern

Instructions to the matcher are in the form of meta-descriptions attached to anchors and descriptors in the pattern. They are all attached via the functional Do which takes a single argument, which is a Lisp expression according to the syntax below. Most of the arguments within an action form are evaluated, but at the time the action is taken, rather than the time the Alignment is initiated. The exceptions are arguments for variable name type, and count, which are evaluated only if they are not ATOMS.

Binding actions happen as the match proceeds, in order to make use of multiple bindings. All other actions are saved up and done when the entire match has succeeded. Evaluation of the arguments in the specification happens at the time they are carried out, in the environment in which Align was called. The function (ValueOf x) returns the value bound in the match for the variable x.

7.1.1. Standard Arguments

Action specifications involve carrying out some action on an object (descriptor or anchor) found in the course of the alignment. There are some standard ways of specifying what object (or objects) are to be acted on. These are shared by the different action types (Bind, Substitute, and Add) and by the different kinds of enumeration (Descriptors in an anchor, or Elements in a collection). They are designated in the forms below as the arguments test and count.

The basic form of the action specifies a set of candidates for the action. Each of these is tested, using the test, and a list made up (virtually when possible) of the successful ones. The count is then used to decide which member(s) of the list to act on.

When a test is given, it must evaluate to either a lisp predicate of one argument (e.g. the atom NLISTP or a form (LAMBDA(X)...)), a handle to a descriptor or anchor, or the distinguished atom ME. In testing candidates for an action, if a predicate is given, it will be APPLYed, if a handle is given, it will be aligned against it using the current match table if it is a collection element, or simple structural match if it is a descriptor. If the test is NIL or T, all candidates pass the test. The use of ME will be explained below.

When a count is given, it must evaluate to an integer (positive or negative), or the distinguished atoms ALL or COMPLETE. The integers are treated like those in the INTERLisp editor -- the nth element is taken from the list of candidates which pass the test. Positive integers count from the front of the list, negative from the end. ALL does the action for every element of the list. COMPLETE insists that it be known that the list is complete (e.g. that an enumeration on which it is based does not contain a ...) If no count is given, or it evaluates to NIL, it is equivalent to a count of 1 -- i.e. the first candidate passing the test is taken.

7.1.2 Bindings

These are used to bind variable names to objects encountered in the match, both for returning as values of the match, and for use in additions to structure done within a match/describe. If a the same variable name appears in multiple binding meta-descriptions, its value must be the same (EQ or EQHandle) for all for the match to succeed.

(Bind variableName type)

This can appear only in a meta-description of an anchor. The variable name is used in the bindings resulting from the match. The type must be one of:

Pointer: The effective description must include a Lisp pointer descriptor, and the variable is bound to its pointer

Primary: The effective description must have a primary anchor as its structural grounding or include a coreference descriptor to a primary anchor (note, not all labelled anchors are primary -- the meta-description NotPrimary() indicates what it says. The variable is bound to a handle to the grounding anchor or to the anchor pointed to by the coreference.

Hook: The effective description must contain a Handle descriptor or StructureNamed descriptor, and the variable is bound to the handle derived from it.

Post: This is the union of Pointer, Primary, and Hook. It binds a handle for a primary, a pointer for a pointer, and a Handle descriptor for a Hook. Note that this is different from the bare handle bound if Hook is used directly, so that it can be distinguished from a Primary.

Anchor: The effective description must have a structural grounding, and its handle is bound.

(Bind variableName Descriptor test count)

This can appear in a meta-description of an anchor or descriptor. If it appears on an anchor, the effective description aligned with that anchor is searched for descriptors which pass the test (as described above). If count is an integer, the nth such one is returned, while if it is ALL, a list of all the descriptors is returned. In this case, ME is not a legal test value. If a BindDescriptor action appears as the meta-description of a descriptor, then the only legal test is ME, and it means that the action is to be done to the descriptor which achieves the match. If the count is ALL, the action is done to all descriptors found in the effective description which match the pattern descriptor.

As mentioned above, a simple structural match is used in deciding whether a datum descriptor matches a pattern descriptor.

(BindElement variableName type test count)

This must appear in the meta-description of a pattern anchor which is matched against a datum anchor containing an enumeration of a collection. It is like BindDescriptor except that it operates on the elements of an enumeration instead of the descriptors in an anchor. Type is interpreted as with a simple Bind. ME is not a valid test. This can be used to get a list from an enumeration -- e.g. (BindElement x Post NIL ALL) returns a list of posts, one for each element in the enumeration in the datum anchor.

7.1.2 Semantic Changes to descriptions

(Describe newDesc)

This is used to meta-describe a pattern anchor. The corresponding anchor must appear structurally in the datum. newDesc must evaluate to a descriptor or anchor handle or lisp pointer, and changes corresponding to it are made to the anchor in the datum. The argument is evaluated, and the result treated as follows:

An anchor handle: the descriptors in the anchor are copied

A descriptor handle: the descriptor is copied

Any Lisp pointer: a Lisp descriptor is created this is not currently implemented

Note that if the argument is a nexus (entered as a form with \.../) it will evaluate to a handle. All of the ordinary surrogate forms (the bangs) are allowed in the nexus, and the Lisp form (ValueOf atom) evaluates to the bound value, where the atom is one of the variables in the bindings of the pattern.

A Describe causes folding and triggering all the way down -- it can be thought of as a series of actions in which the specified new description is added one level at a time starting at the top. If the piece being added would be redundant, it is not added. This is distinct from Substitute and AddDescriptor, which add their argument as a whole without dealing with its internal structure.

(OverWrite newDesc)

This is used to meta-describe a pattern anchor. The corresponding anchor must appear in the datum, and a set of descriptors corresponding to the new description is put into it. Those previous descriptors in that anchor which are in conflict with the new ones (as defined by the type of match) are removed. This can be used in conjunction with bindings, as in:

(Match foo \A Something with
currentCount = @Do(’(Bind x Pointer))
@Do(’(OverWrite (Add1 (ValueOf x))))/)

(MetaDescribe newDesc)

This is used to meta-describe a pattern anchor or descriptor. The corresponding anchor or descriptor must appear in the datum, and newDesc is added to its meta-description. This addition is done using the same folding mechanisms as for any Describe.

7.1.3 Structural Changes to Descriptions

These are used to change the structures found in the course of the match. After a match has succeeded completely (all bindings are satisfied), the set of changes is made, and can refer to the values bound. A substitution is specified much like a binding, in that it must find the object for which to substitute.

(Substitute newAnchor)

This must appear in the meta-description of a pattern anchor. newAnchor must evaluate to an anchor handle or NIL. The datum anchor against which it is matched has both its descriptors and meta-descriptors removed and replaced with newAnchor, or with null handles, if newAnchor evaluates to NIL. This is a structural replacement, not a semantic describe. No triggering happens within the contents of the new anchor -- only above it in the datum. A labelled anchor cannot be substituted for anything, nor an unlabelled one for a labelled one.

(SubstituteDescriptor newDescriptor test count)

This can appear in the meta-description of a pattern descriptor if the test is ME, or an anchor otherwise. It first acts like BindDescriptor, finding the specified descriptor (or descriptors). It then replaces it (each of them) with a copy of the value of newDescriptor. If the newDescriptor value is NIL, the descriptors are removed from their anchors.

(AddDescriptor newDescriptor)

This is used to meta-describe a pattern anchor. The corresponding effective description must be structurally grounded, and a copy of the newDescriptor is added to it without checking for redundancy or folding.

7.1.4 Changes to enumerations

(AddElement newAnchor)

This is used to meta-describe a pattern anchor. The corresponding effective description must be structurally grounded, and contain an explicit set or sequence enumeration descriptor. A copy of newAnchor is put into a new anchor, which is added to the enumeration. Triggering is done as with describe. If the enumeration is a sequence, the new element is added at the end. If the enumeration was marked as complete, a signal AddingToCompleteCollection is generated.

(AddBefore newAnchor test count)

This is used to meta-describe a pattern anchor. It first operates like BindElement, finding the element (or elements) passing the test and meeting the count. It then adds a new element to the enumeration immediately before the one specified, copying the newAnchor. Note that this can be used to add an element in a specific place. the Command (AddBefore x NIL 3), for example, inserts a new element in position 3, moving the rest down. If the test is ME, the anchor must be in an enumeration in a pattern, and the new elment is inserted before the element matched by the pattern element. In this case, the top-level AddBefore form cannot be used.

(AddAfter newAnchor test count)

This is like AddBefore, but puts the new elment after the one(s) found.

(SubstituteElement newAnchor test count)

This can appear in the meta-description of a pattern anchor, which must be an element of an enumeration if the test is ME. It first acts like BindElement, finding the specified element (or elements). It then replaces it (each of them) with a copy of the value of newAnchor. If the newAnchor value is NIL, the elements are removed from their enumerations.

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

7.2 Procedural Attachment -- Triggers and traps

Triggers and traps are very much like they were in KRL-0. There is a small fixed set of names recognized by the system when attached in a trigger or trap footnote. The cataloguer (see Section ?) stores an index of triggers so they can be used without accessing the prototype unit each time. The comunication between a trigger or trap and its environment is through free variables. Some of these (e.g. the triggering unit, slot, etc.) are general to all triggers or all traps. Others are specific to individual ones.

7.2.1 Triggers

Each trigger (demon or servant) is indexed under one or more labelled anchors (unit and slot name). It is entered through a Trigger meta-description on that anchor (or by being put on dynamically with the functions for manipulating the procedural attachment index). One minor extension beyond KRL-0 is that a trigger can be simultaneously associated with a set of slots in a single unit, through a TriggerOnAny meta-description on the unit.

Whenever a trigger is invoked, the following free variables are available:

SLOT: a handle to the slot anchor for the slot under which the trigger is indexed. In the case of a TriggerOnAny, it is the slot corresponding to the actual instance of triggering

PROTOTYPE: a handle to the self slot of the unit in which the trigger is indexed.

INSTANCE: a handle to an anchor for the instance of the prototype unit in which the trigger appeared

WORLD: a handle to an anchor describing the world corresponding to the goal. If it is the default world, it will be NIL

FULLALIGN: T if the full matcher environment, NIL if called by an access-compiled Align.

As mentioned in section 1.4, the function SeekMy accesses these. I don’t think SeekMy has been written yet.

7.2.1.1 Servants

ToFind: Whenever a Find goal (e.g. FindPost) is activated on a datum which includes a mapDescriptor whose template focus slot includes a ToFind trigger, or it is in that slot of a pattern mapDescriptor, and if the goal is not immediately satisfied by the effective description, then the trigger code is executed.

Note the two cases: Assume \$Foo:bar has a ToFind trigger. Then in the first case, the pattern is:

\A Foo with bar = @Do(’(Bind x Post))/ and the datum is:

\A Foo with mumble = .../.

In the second case, the pattern is:

\A Randomness with stuff = @Do(’(Bind x Post))/ and the datum is:

\A Randomness with stuff = The bar from a Foo with mumble = .../

The variable TYPE is bound to the descriptor the type of binding sought. In a FullAlign, the variable GOAL is set to the appropriate Goal. The value returned by the trigger is treated as follows:

The atom NOTFOUND --> the servant failed to find the desired thing

Any other Lisp pointer --> if the TYPE sought was Post or Lisp, then use it. Otherwise an error (KHelp).

A handle --> if the TYPE sought was Post, and it is a primary anchor handle, use it as coreference. If it is a handle to a KRL-pointer descriptor and the type was Post, use its contents in a KRL-pointer. If the type was KRL and it was a handle, use it directly in a KRL-pointer. If the type is Primary or Anchor and it is a handle of the right kind, use it. Otherwise an error (KHelp).

Note that if the code does not end up satisfying the goal, it will not be tried again unless a new descriptor is found which has that slot as its focus slot..

ToEnumerate: Like ToFind, except for a FindEnumeration goal. Value returned must be the atom NOTFOUND, or a list of elements treated as described above. Note that finding a primary anchor for a collection is different from being able to enumerate its elements.

ToMatch: Whenever an AlignMapDescriptor goal is activated and not immediately satisfied, the system looks for a ToMatch trigger associated with the focus slot of the prototype unit, and runs the code. The variable PATTERNDESCRIPTOR will be bound to the pattern descriptor (which is a map descriptor whose unit and focus correspond to the place the trigger is indexed). DATUM is bound to the corresponding datum anchor. The variable FOCUSMATCHED is non-NIL if it is known that the map descriptor focus applies, but the fillers have not been all matched, NIL if nothing has been proved about the match. The trigger is expected to return a value like a signal:

ALLOK -> assume the goal is satisfied

OK -> assume that the focus is satisfied, but go ahead and set up subgoals for the individual fillers. Notice that if FOCUSMATCHED is non-NIL, then this answer is irrelevant.

SKIP -> the trigger didn’t satisfy it (although it may have acted through side effects on the environment) but go on trying

FAIL -> the goal fails -- no match should be sought

As with ToFind, this trigger will not be tried again unless it is provoked by a new map descriptor with appropriate focus slot.

7.2.1.2 Demons

As mentioned in section 6.2, the actions associated with a call to Align are all saved up until the match is complete (with all bindings), then done. The triggering of demons is done at this time, and the code has access to the entire list of actions. Demons for each kind of event (e.g. filled, described, etc.) are of two types -- those which are done before the action actually happens (e.g. BeforeFilled), and those that happen afterwards (e.g. WhenFilled). The process carried out for each successful result of the Align is as follows:

For each action (the result of a single Do functional or a place in a Describe where something was actually added), do the following:

Find all the potential demons which will fire.

Execute each of the Before... demons.

Do the actual structure changes corresponding to the action

Execute each of the When... demons.

The demons associated with any one action are taken in arbitrary order. If a Before.. demon wants to prevent the action from being taken, it can call modify the action by setting its actionSpec to NIL. This will prevent it from being done, and from being used as a cause for When... demon invocation. Code which depends on any fancy timing between actions and demons is taking its chances.

When a demon is invoked, the following variables are always bound:

TRIGGERFORM or TRAPFORM: One or the other will be bound, depending on whether the demon is a trap or trigger. It is bound to a record of that same type (TriggerForm or TrapForm), which is the one causing the firing.

ACTION: The top-level action (a record of type Action) which provoked this demon, possibly through its sub-actions.

ALLACTIONS: A list of all the sub-actions (including the top-level actions) provoked by ACTION

ACTIONS: A list of the sub-actions which provoked this particular demon.

PATH: An anchor path, which is the thing on which the action will be taken. The change is to the CAR of the path. The path is an alternating list of Anchors and Descriptors, such that PATH:n is a structure which is a part of PATH:(n+1).

TRIGGERS: All of the triggerforms for ACTION. This includes one for every case where either a Before.. or a When.. trigger exists, and is not modified as they are done, so it includes all those which have been and will yet be done.

TRAPS: like TRIGGERS

OLDACTIONS: Actions (siblings of ACTION) which have already been done

NEWACTIONS: Actions yet to be done. ACTION is on neither of these lists.

Demons which are triggers

The following variables are bound when a trigger demon is invoked:

PROTOTYPE: The self slot of the unit in which the trigger appears

SLOT: The slot which caused the triggering

INSTANCE: An anchor for an instance of PROTOTYPE for which the triggering occured.

WORLD: The world for the instance

MAPDESCRIPTOR: The map descriptor which caused the triggering. In the case of a *Identified, it will be the new descriptor being added. In a *Filled, *Described, or *EnumerationChanged, it will be somewhere in the PATH above the place where the change is being made.

The following are the different trigger demon types:

*Filled: This trigger is activated whenever an action is taken meeting the following criteria:

1. A CoReference to a primary anchor, LispPointer, or KRLpointer is added to an anchor which did not previously contain it

2. The anchor in which it is put is the filler anchor for a perspective of the prototype for which the trigger is indexed, in a pair for the slot on which it is indexed.

The variable FILLER is bound to the post corresponding to the descriptor added (i.e. the actual lisp pointer, KRL handle, or structure Descriptor). PATH:1 is the anchor in which it is being put, PATH:2 is the entire mapDescriptor, and path:3 the anchor in which it appears.

Note that this covers several cases in addition to the simplest one. For example, it does not insist that the mapDescriptor have SELF as its focus slot. If we had in some anchor a previous description \The bar from a Foo/ and add the description \The bar from a Foo with mumble = 3/, a WhenFilled on \$Foo:mumble would be triggered. Also, there is no condition that the mapDescriptor appear at the top level of a labelled anchor. Thus if we have a datum of \A Foo with bar = A Gritch/ and add \A Foo with bar = A Gritch with yuk = "hello"/, then a WhenFilled on \$Gritch:yuk is activated. The KRL-0 version of WhenFilled corresponds to this one when PATH:3 is a primary anchor and PATH:2 has SELF as its focus slot.

WhenEnumerationChanged: This trigger is like WhenFilled, except that the first condition is:

1. A change (addition or deletion) is made to an explicit enumeration descriptor appearing in an anchor, or a new enumeration descriptor is put into an anchor not previously containing one.

In addition to the variables for WhenFilled (except for FILLER, which it does not have), it has ENUMERATION bound to the old enumeration descriptor (or the changed version after the action).

Note that this is structure local -- if something is described as \A Foo with bar = GoodGuys/ and \$GoodGuys:self contains an enumeration, then changes to that enumeration will not trigger a WhenEnumerationChanged on \$Foo:bar.

WhenDescribed: This trigger is activated whenever an action is taken meeting the following criteria:

1. Any change is made to the contents of an anchor

2. That anchor is lexically contained at any depth inside a filler anchor for the indexed slot in a mapDescriptor for the indexed unit

3. The change was made as part of a call to Align whose datum (including that added by describe -- see below) explicitly included the path down from the mapDescriptor to the changed anchor

This is the catch-all trigger for noticing that something is being changed in a structure. Its variables are (in addition to the standard ones for all triggers):

DESCRIPTORS: A list (possibly NIL) of descriptors being added directly to a filler anchor corresponding to the trigger.

CHANGES: A list (possibly NIL) of Actions which cause changes internally to descriptors embedded below the filler anchor.

Note that there is a big difference between a call to align which includes an action on some embedded anchor, and a sequence of two operations, the first of which finds and binds that embedded anchor, and the second of which does something to it. The single call will trigger all of the relevant WhenDescribeds on the chain down to the anchor, while in the separated case, the action will be taken without triggering any demons.

WhenIdentified: This trigger is activated whenever a MapDescriptor with the index slot as focus slot and index unit as prototype is added to an anchor. It will not be triggered when one was already there, and simple folding prevented a new top-level mapDescriptor from being added. However it will be triggered if a second one is added because folding isn’t obvious (e.g. adding a second \The hometown from.../ descriptor to an anchor which has one).

Whereas all of the previous demons in this list were triggered because their attachment correspond to the structure in which changes were made, this one is triggered because it corresponds to the structure being added. Note that unlike WhenIdentified in KRL-0, it does not depend on the anchor to which it is being added being primary -- it is triggered when an appropriate descriptor is added to any anchor (including one embedded in a contingency) it is up to the trigger code to determine the nature of the place it is being added.

*** this is as far as I have gone ***

7.2.2 Traps

Each trap (demon or servant) appears in the meta-description of an anchor and is not otherwise indexed. When it is invoked, the variables available are:

ANCHOR: a handle to the anchor in which the trap appeared

WORLD: a handle to an anchor describing the world corresponding to the goal. If it is the default world, it will be NIL

FULLALIGN: T if the full matcher environment, NIL if called by an access-compiled Align.

7.2.2.1 Servants

ToFind: Whenever a FindBinding goal is activated on an effective description which includes in its procedures a ToFind trap, and if the goal is not immediately satisfied by the effective description, then the trap code is executed.

The variable TYPE is bound to the descriptor the type of binding sought. The value returned by the trap is the same as for the corresponding trigger

ToEnumerate: Like ToFind, except for a FindList goal. Note that finding a primary anchor for a collection is different from being able to enumerate its elements.

7.2.2.2 Demons

WhenFilled: This trap is activated whenever Coreference, LispPointer, or HandleDescriptor is added to the anchor on which it appears (note that it is not inherited by effective descriptions which copy its descriptors). Variable is FILLER, the object filled in (as with the trigger).

WhenEnumerationChanged: As with the trigger, mutatis mutandis

WhenKnown: When this anchor is the structural grounding of an effective description to which a Post is added

WhenDescribed: Any change is made at any level (as qualified in the description of the corresponding trigger)

7.3 The goal types

For more details on these, see the individual files. Those with stars are not yet written:

FILE: ALIGNCLASSES

AlignAnchor

AlignCoreference (align a non-Primary Coreference)

AlignPost (align a Primary Coreference, LispPointer, or HandleDescriptor)

AlignMapDescUnique (the pattern map descriptor is unique w.r.t. its focus slot)

AlignMapDescMulti (the pattern map descriptor is not unique w.r.t. its focus slot. Alos used for InterpretedMapDescriptors in structural match)

AlignMapDescOneOf (used by both Unique and Multi to match against an individual datum MapDescriptor)

AlignNot

AlignOr

AlignContingency

*AlignContains

*AlignMemberOf

*AlignUsing

*AlignSequenceAny (the pattern contains no explicit elements, so any sequence will do)

*AlignSequenceComplete (the pattern sequence contains no "...")

*AlignSequenceEmpty (the pattern is the empty sequence)

*AlignSequenceMultiGap (the pattern sequence contains more than one "...")

*AlignSequenceOf (the pattern is a SequenceOf functional)

*AlignSequenceSingleGap (the pattern sequence contains a single "...")

*AlignSequenceSingleton (the pattern sequence contains a single element and no "...")

*AlignSetAny (the pattern contains no explicit elements, so any set will do)

*AlignSetComplete (the pattern set contains no "...")

*AlignSetNull (the pattern is the empty set)

*AlignSetIncomplete (the pattern set contains one or more "...")

*AlignSetOf (the pattern is a SetOf functional)

*AlignSetSingleGap (the pattern set contains a single "...")

*AlignSetSingleton (the pattern set contains a single element and no "...")

FILE: FINDCLASSES

FindAnchor

FindDescriptors

FindElements (used within a single enumeration descriptor)

FindEnumeration (used to find the enumeration descriptor in which elements are sought)

FindPost (find a Primary, Pointer, or Hook)