[Indigo]<KRL>document>match-seek!2

STATUS: rough draft -- not to be trusted. In particular, the process description stuff is missing, the method of specifying grounding will be slightly different, and the "pattern units" will become part of a more general notion of "unit constructors".

The command format in KRL-1 includes a single argument, which is a description of the process to be carried out. In principle, this description can make use of the full set of KRL-1 descriptive mechanisms, and it is the job of the command interpreter to make use of the information given. This very general flexibility must be tempered by practicality, by having a set of standardized descriptions which are recognized by the simple initial versions of the access compiler, interpreter, etc. These will be gradually augmented by more complex ones as the system is expanded.

to be filled in -- say that semantics will be given before detailed specification of commands and enumeration of the simple cases. Separation of I-O specifications of the commands from details about how the interpreter runs. References to general discussion of the family, of interpreter, of KRS,...

A simple Seek command is a search for a data structure (usually an anchor, handle, or lisp object) corresponding to an entity which is described in an input which provides an initial set of beliefs. More complex seeking activities (i.e. finding data structures for several entities) are discussed under Match. In specifying a Seek, there are five basic parts:

In the most abstract case, we could provide an arbitrary description (at the meta-layer) of a set of beliefs, along with an indication of which entity (or entities in the multiple-seek case) in that set of beliefs we are trying to find out more about. One simple way in which this can be done is by describing (usually with a quoted description -- see <KRL>datatypes.doc) a single anchor which is interpreted as follows:

1. The description in the anchor is interpreted as representing the set of beliefs which would be derived from incorporating it in a context where everything is defaulted, except for information appearing explicitly in that anchor (and its attached meta-description).

Syntactically, one way to provide an anchor is through the quotation mechanism. Thus, the form \The x from a Y with z = W is represented in memory as a handle to an anchor which (if it were provided as the belief argument to a Seek) would be interpreted as positing a mapping belief (see figure) and indicating that the entity mapping onto the x slot of Y is the one being sought.

For the purposes of the simple cases, this is the only form of the description argument which is needed. We will call it the initial description. Most of the simple cases involve further limiting the possible descriptor forms which can appear in the initial description. These limitations are intended to make sure that the system knows exactly where to look to find the information. Note that as we have stated it so far, the form \A Whatever would be a perfectly good initial description -- the system must set out to find more about an entity about which all is known at first is that it maps onto Whatever. This is reasonable in a global sense, but is not a simple case. In this first presentation, I am ignoring the LISP interface and the use of constructor forms to incorporate LISP variables. The interactions will be explained in a section below.

Simple Grounded Access: This corresponds closely to the simple record accesses of computer languages (e.g. the INTERLISP record package). We will use the term grounded anchor to describe an anchor which contains a coreference to a labelled anchor which is viewed as representing an individual. A grounded mapdescriptor is one which contains at least one filler anchor which either is grounded, or contains a grounded mapdescriptor (note the recursive definition!). A simple grounded initial description consists of a single grounded mapdescriptor which contains only one grounded anchor at any level of recursion.

The obvious example is a form like \The name from a Person thatIs Danny (grounded on Danny -- Note: in all of this document, remember that thatIs is simply an alias for self =.), or \A Person with mother = Mary (grounded on Mary). In the simplest case, these will be used in a process context in which the only accessing allowed is to look into the memory structure for the grounding anchor, making the process corrsespond to a CLISP fetch (or in the recursive case, a recursively nested set of fetches). Note that in the second case, the simplest Seek would succeed ony if the self slot of Mary contained a descriptor of the form The mother from a Person thatIs X. Some simple recursive cases would be:

The motivation behind this definition of simple grounding is to provide the base for a simple "unwinding" process in which simple accesses are made in layers working from the inside out, starting with the grounding. The access compiler can produce efficient code to do this, since no significant search or bookkeeping is involved. In the recursive cases, there will be some process descriptions which insist that the entire recursive structure appear in the initially given anchor, and other which allow access of derived anchor. For example, in the second example above, a Seek which allowed only direct access of the grounding would succeed only if the self slot of the the John unit included a description A Person with mother = the femaleParent from a Family with maleParent = x, where x contains the information being sought. If we allowed access of derived groundings, then the Seek would succeed if John contained A Person with mother = Mary and Mary contained the femaleParent from a Family with maleParent = Joseph. For more details, see the section below on the different process descriptions.

Note that even a simple grounded access Seek can produce multiple results. If we seek \The name from a Person with homeTown = PaloAlto the grounding is the self slot of the PaloAlto unit. This might contain any number of descriptors each of the form The homeTown from a Person with name = .... Mechanisms for dealing with these multiple results will be discussed below.

Multiply grounded access and access with matching: In a simple grounded access as defined, the only description allowed (either as the argument, or recursively as a grounding) is a grounded mapdescriptor. Furthermore, a grounded mapdescriptor contains only the fillerpair which leads to the grounding. This case can be extended by allowing additional descriptors or filler pairs to appear at any place in the initial description. The result is more complex in two ways. First, if there is still only a single grounding, then the system still uses it to provide the candidate result, and in addition does a match using the other descriptors. In this simple case, the match can only serve as a cross check, but in the case of non-unique mapping (see below) it has a more primary role.

In this case, the simplest form of seek would look in the DGB unit for a name, and would also check to see that DGB matched the description A Person with homeTown = A Suburb. The parameters for the match are included in the process description for the Seek (see below).

In this case, the unit PaloAlto can also serve as a grounding. If in its self slot, it contained a description The homeTown from a Person with name = "Danny", then this would be relevant to answering the question. However, it might not be the right answer, since a single town can be the home town from many different people. Note that this did not come up in the previous example since by default the self slot provides a unique mapping -- only one mapping can map a given instance (DGB) onto the self slot of the Person unit, while many independent mappings can map PaloAlto onto the homeTown slot. Therefore, it is necessary to find a descriptor such as The homeTown from a Person with name = "Danny" thatIs DGB.

If the Seek is of an appropriate type, (as specified by the process description) the full power of the interpreter (to check to see which slots of which units correspond to unique mappings, and therefore be able to merge mappings, etc.) could be used in deducing the answer. For a simple case (the one handled by the access compiler), the Seek will succeed only if there exists a single mapdescriptor which contains all of the information specified. If there is more than one possible grounding in an initial description, the user can specify (with the meta-description A Grounding) those anchors to be used as groundings. The default is to try all of them. Thus, the example just above would be interpreted by looking in the DGB unit for a name, and checking to see if the description A Person with homeTown = PaloAlto matched DGB. Instead we might have specified the initial description:

In this case, for the simplest process description, the interpreter would look into the PaloAlto unit’s self slot for descriptors of the form The homeTown from a Person with name = x thatIs y, matching the description y to DGB, and if it matches, retrieving x.

Simple Set Grounded Access: A standard use of Seek-like functions is to find elements of a known set (i.e. one for which an enumeration is available) which fit a desired criterion (i.e. match a given description). The ability to have multiple descriptors makes it easy to provide the extra criteria. An anchor is set-grounded if it includes an explicit enumeration of a set or sequence, or a simple grounded map-descriptor which leads to such an enumeration. This grounding is said to be complete or incomplete, according to whether the enumeration is complete or incomplete (i.e. contains a "..."). A set-grounded initial description is like a grounded initial descriptor, except that each grounding consists of a MemberOf functional whose argument is a set-grounded anchor. It can contain other descriptors at the top level, and of course use the full generality of grounded access in the set grounding.

As we will see below, this kind of Seek can be expected to return a single element, or a series of elements in any one of a number of forms. Therefore, the simplest form of initial description (a simple MemberOf with an enumeration or grounding) is useful for doing the equivalent of the CLISP mapping functions on KRL-1 sets and sequences.

Since we allow other descriptors, they may in turn lead to other groundings. As with multiple groundings above, order will be used to determine the grounding for simple processes. Thus, the description below uses set-grounding recursively, and is grounded both on the self slot of the unit for BethYisrael and on the self slot of PaloAlto. We could imagine the processor enumerating through the congregation checking to see who lives in Palo Alto, or enumerating through the families listed as residents (in descriptors appearing in the Palo Alto unit) to find out which were members of the designated list.

As it is written, the enumeration would be done once for each unit. It is not simple to combine the results, and the simple process descriptions will not handle this. Instead it is necessary to specify one (but not both) of the possible groundings as A Grounding. If, for example, it were the anchor containing BethYisrael, then the self slot of the BethYisrael unit would be checked for a mapdescriptor describing it as Congregation and giving its familyList, which would be used for the enumeration. Note that in either case, this initial description leads to a doubly nested enumeration -- of the families, and of the children within each family.

All of the initial descriptions given as examples above are legal but atypical. They are written as though the entire description were fixed once and for all as a description stucture. In fact, most instances of Seek will appear in LISP code, where one or more of the variables in the current LISP context are to be filled in to the description. The document <KRL>interface.doc describes the mechanism of constructor form which enable LISP values to be copied into description structures. A typical case and a more extended example are:

The first (which is probably the 90% case for all seeks) is the standard case where the variable x is bound to some individual (actually to the labelled anchor for that individual), which is to serve as the grounding for a simple access. The second is more complex --it assumes that y will be bound to the name of one of the slots in the Family unit (e.g. children, maleChildren, etc.), that z will be bound to a LISP list of anchors which correspond to a complete enumeration of the relevant set of families, and that w will be bound to the handle for a descriptor which is to be used as a check (using a Match) on the candidate people before actually accessing the names.

In the example given here, there is no problem determining the grounding, since the system knows that a !Coreference surrogate must be replaced by a coreference descriptor which could serve as a grounding. In other cases, this would not be clear, as in: \The name from a Person thatIs !Descriptor x. In this case, there is no way of determining before runtime whether the descriptor bound to x will in fact be useable as a grounding (i.e. a coreference descriptor) or some other arbitrary descriptor. If the process description associated with the Seek states that a simple grounded access is to be used, the system (i.e. the access compiler) will assume that the variable will have the necessary type of value, and do a run-time check which leads to an error event if the assumption was wrong.

Thinking in the full interpreter semantics, the Seek process can be characterized by assuming that as the result of incorporating the initial description, an entity (a box) is created to represent the entity being sought. We will call this the target entity As a result of further processing, anchors are found in the memory structures which can be identified with the target entity (through processes of merging and coalescing). Note: This is not really right, but will be refined in the following section. The goal of the seek is to find one of the following:

1. An anchor corresponding to the target entity, where the anchor has a specified (arbitrary) property. Most often the property of interest will be that the anchor is a labelled anchor. However, it can be an arbitrary description of an anchor.

2. A LISP object which corresponds to the target entity. Often this will be the result of finding an anchor corresponding to the target entity which contains a simple LISP pointer descriptor. At other times, it may be the result of an inference within the interpreter (e.g. evaluating a LispInvocation, possibly as the result of a trigger)

In the simplest case of Seek, we would expect a single answer (or failure) to be returned. However, as I pointed out above, even if there are no explicit mentions of sets (and almost always if there are) there is the potential of finding more than one object matching the given initial description. The characterization in the previous paragraph assumes that a single entity is set up as the initial place for attaching anchors. A more accurate characterization is to think of Seek as operating more like a match. The initial description provides a pattern, and the matcher sets out trying to find a corresponding set of beliefs in the memory structure. In doing so, it will set some entity derived from incorporation into correspondence with the target entity in the pattern. However, a single pattern can fit a set of memory structures in more than one way, and each of these can correspond to a potential answer to the Seek. In order to organize the process properly, the sytem makes one of several assumptions (specified by the caller of the specific process, or by defaults):

1. The Seek is either single or multiple. If single, then as soon as the characterization of the sought-after information is satisfied, the process is done. If the Seek ismultiple, there may be more than one. If a single Seek fails to find an object, a failure is signalled. A multiple Seek can be satisfied by finding a collection with no members (i.e. an empty set).

2. If it is single, then it is either unique or arbitrary. If unique, then it is a failure if more than one answer could be found. The degree of checking for this depends on the process description If arbitrary, then the user is willing to accept an answer without regard to whether there might be others, and the one returned will be the first one found acording to the given process description.

3. If it is multiple, then it is either complete or incomplete. If complete, then it is a failure if the system cannot establish that all possible values have been found. If incomplete, then after the process terminates (due to resource limitations or access restructions) the existing enumeration is considered sufficient (even if it has no members).

Since a Seeking process is usually carried out as the result of a KRL-1 command, its results must be passed back as a LISP value. note: section ??? will discuss the invocation of KRL processes such as Seeking in a KRL context which enables the results to be returned as part of the description of the process. As with other parts of the LISP/KRL-1 interface, the goal is to provide a variety of forms to make it convenient and efficient to use KRL-1 commands as a part of LISP programs. There are three basic things to be spcified: what to do with individual values; what to do with collections; and how to deal with failure.

Anchor: The value to be returned is an anchor handle. If the goal was to find an anchor fitting a given description, that anchor is obviously returned. If the goal was to find a LISP pointer, handle, or enumeration, then the result is a newly created unlabelled anchor containing a single descriptor of the appropriate type.

Descriptor: Like anchor for all the cases except that in which an anchor is decribed as the goal, except the appropriate single descriptor handle is returned without being embedded in an anchor. Doesn’t make sense for the case in which an anchor is specified.

Coroutine: A LISP coroutine handle is returned, which will return another element each time it is RESUMEd. Note that it is not much use to specify a generator or coroutine for a multiple answer which must be complete, since the sytem will have to make a list of all of the values before giving out any, in order to be sure it is done. In fact, for efficiency reasons, it is better to return a LIST whenever the nature of the process makes it possible to do all the seeking before using the values.

Failure Result: This is specified for all KRL-1 commands, but it is repeated here for the sake of bringing together things that need to be thought of together. The problem (as we all know from sad experience) is that LISP has a basic notion of returning a single value. Conventionally, processes which can fail at what they are asked to do (e.g. GETP) signal this by returning NIL. Often, this cannot be distinguished from a success in which the thing found was an empty list. In some places (e.g. ERRORSET) this is bypassed by always returning a list of the desired value, with NIL being a distinguishable failure message.

Since we are buying at least this much of the LISP process structure (argument and value passing) we must adapt. The default is that a KRL-1 command which fails returns NIL, regardless of how its values are being interpreted. Any individual command can have as an added description a specification (see details in section ?? below) of a different failure value. Thus, for example, in the standard cases for multiple seeks which return lists, empty lists will be allowed, and the default will be overridden by specifying a distinguished atom (FAIL) as the failure result. This can be further overriden by the user in any specific command.

This is the most complex and open-ended part of the specification. Much of the development of KRL-1 as it is used will center around developing appropriate strategies, heuristics, stylistic idioms, etc. etc. For the moment, we will specify only the simple cases handled by the access compiler. The set of standardly recognized process descriptions will be augmented as we go further.

Some parts of the process description are shared by all commands (e.g. the failure value discussed above), others by all reasoning commands (e.g. whether certain inference steps are allowed), and others by specific commands such as Seek (e.g. what type of grounding is allowed). Section ?? below is a list of currently defined units and functionals process description, divided up along these lines. Section ?? contains units and functionals for standard cases of Seek.

A simple Match command is a search to see if a particular set of beliefs can be found in or inferred from the memory structure. At its simplest, the answer is either ’yes" or "no". There are a number of other possibilities, which include checking for compatibility ("can match") and returning bindings, and these interact along several dimensions. In specifying a Match, there are five basic parts:

2. Specifying the criterion for satisfaction -- whether the beliefs must be all found, whether it is only necessary to see if they would be compatible with what is believed, or to provide some kind of evaluation of their plausibility with respect to what is believed.

6. Specifying the type of processing to do -- i.e. whether inferences are to be drawn, other units are to be accessed, how resources are to be considered, etc. For some types of matching, this may include passing back partial results.

In the most abstract case, we could provide an arbitrary description (at the meta-layer) of a set of beliefs. One simple way in which this can be done is by describing two anchors (called the pattern and the datum) which are interpreted as follows:

1. The pattern is interpreted as representing the set of beliefs which would be derived from incorporating it in a context where everything is defaulted, except for information appearing explicitly in that anchor (and its attached meta-description).

2. If the datum is a labelled anchor, then the sought-after beliefs are all of the pattern beliefs, along with the belief that the entity corresponding to the anchor of the pattern is the same as the entity corresponding to the labelled anchor. If the datum is an unlabelled anchor, a special labelled anchor corresponding to it (with identical descriptors) is set up for the purposes of the match, and treated as if it were in memory structure. It is then treated as though it had been given as a labelled anchor.

Danny: here is where we would say something about providing a set of pairs of pattern and datum anchors for multiple match (e.g. for checking out a world). My temptation is to make a special declarative syntax for that case (hanging a set of beliefs by its world) rather than special arguments to the match procedure. Any current thoughts?

We will see below a case in which a unit, rather than a single anchor is given as a patter, in order to have a convenient way to specify bindings. In this case, the set of beliefs to be established is the union of the beliefs corresponding to incorporating all the anchors of the unit.

Known to match or not match: In many cases, the interpreter will be able to establish with certainty that a Match succeeds (i.e. finding or deriving the set of specified beliefs) or fails (i.e. finding or deriving a set of beliefs which are incompatible with the specified set).

Process done: Due to limitations on the nature of steps to be carried out (e.g. access only) or to an initial resource bound, there is a clear ending to the process. This may occur before either all the initial beliefs or any contradictory beliefs have been found. At this point, the interpreter may (depending on the process description) have some accumulated information (e.g. an evaluation of the match, a tentative set of bindings, a residue, etc.) or it may not. For some purposes, termination without any definite answer will be considered a failure (e.g. in a "known to match") while in others it will be considered a success (e.g. a "can match").

Process interrupted: In a multi-process environment, it may often be useful to have several match processes going simultaneously, and to interrupt them occasionally (by repeatedly giving them resource quanta) to compare results. This is like the Process Done case, except that it is assumed that the matching process may be resumed with a new allocation of resources, to continue from where it left off.

In many cases, the reason a match is being done is to establish a corresponding between selected anchors in the pattern (bindings) and the objects to which they correspond in the memory structure (values). In general, as with Seek, we want is a specific kind of information about the entity matched -- e.g., a labelled anchor for it, a pointer or handle, etc. This is done by associating meta-descriptions with the selected anchors in the pattern. These meta-descriptions serve both to identify the anchors which are to be sought (i.e. the interpreter is looking for other anchors corresponding to the same entities), and the kind of information being sought about them (exactly analagous to the arguments to Seek). More than one anchor in the pattern can be identified with a particular thing to be sought (analogous to using the same variable twice in a pattern).

The syntax makes use of a unit in place of a description in the argument to a KRL-1 command, with the slots of the unit serving as the names for binding. Conceptually, one possible result of the Match is an instance of this unit, with all the fillers filled in. (In fact there are various forms for returning the binding -- see below).

($ \A Match with
pattern =
\# Pattern21
self: A Family with
children = {My juliet, ...}
A Set with cardinality = My familySize
maleParent = My oldMan
The despiser from
a Despisement with
despised = My romeo
juliet:↑1 A Girl1: Seeking(A LabelledAnchor)
romeo:↑2 A Boy; LoverOf(My juliet)2: Seeking(A LabelledAnchor)
oldMan:↑33: Seeking(A LabelledAnchor)
familySize:↑44: Seeking(A Pointer)

Note that this unit is not fundamentally different from one which might have been defined completely independently of the matcher, with a name like RomeoAndJulietTypeFamily. If this had been done, then the pattern \A RomeoAndJulietTypeFamily would have a meaning similar to the pattern given here, but with two important differences:

2. The set of beliefs which must be found in order to establish a match is precisely the full set in all the anchors of the pattern unit. This is not the case for units in general. The default case for matching a descriptor \An X, is that no assumption can be made about whether the unit contains sufficiently explicit description to identify instances, unless explicit meta-descriptions (Criterial) say so. For example, it is perfectly OK (and in fact typical) to have a unit like:

Orthogonal to the exact nature of the answer desired, there is a set of decisions (like those for Seek -- see section ??.?? above), concerning whether the user desires a single or multiple result (if there is more than one way in which the pattern could be matched to memory), and if single, whether it is unique or not, and if multiple, whether the collection of answers must be logically complete or not. Typically, there may be several different sets of binding which allow a pattern to be matched, and the user may want to have all of these available for comparison.

There are a number of different sorts of information which could be provided by a match -- the reason for returning, the bindings, an evaluation, a residue, or some combination of the above. For each of these, there are different possible forms -- e.g., full-fledged descriptions, special LISP structures (such as an A-list for the bindings, or an atom symbolizing the result), etc. This is all further complicated by the possibility of returning partial results. In order to factor the complexity, we can think of the answer-production as involving two steps. First, a full description of the state of the match is generated (conceptually -- as usual, it can be short circuited in the implementation) using a standard unit given below. Second, some recipe is followed for converting it into a LISP object containing the desired information. In a specifying a match process, the user (or system builder in the standardized cases) provides this recipe.

# MatchResult
self:
matchProcess: A Match
currentStatus: Or(Succeeded, Failed, Suspended)
residue: SetOf(A Belief)
bindings: A MapDescriptor with
prototype = The matchUnit from My matchProcess
lispResult: A LispPointer
DescribedBy(The returnValue from my Match)

\ValueOf(LISP ’(if result=’Succeeded
then <<rom jul> old <’HalfOf (TIMES 2 num)>>
else NIL)
binding
result = AtomFor(My currentStatus)
rom = BindingFor(’romeo, My bindings)
jul = BindingFor(’juliet, My bindings)
old = AtomFor(BindingFor(’oldMan, My bindings))
num = BindingFor(’familySize, My bindings))

4. The LISP value to be passed back is the anchor handle if an anchor was found, and the LISP object otherwise. Note that this convention prevents this case from being used in seeking entities which are anchor handles being treated as LISP objects, since the result would be ambiguous. This would only come up in working atthe meta-layer.