Page Numbers: Yes First Page: 1
Heading:

UNPUBLISHED WORKING DRAFT - DO NOT COPY OR DISTRIBUTE
September 20, 1978 4:08 PM 4: Conversion [IFS]<KRL>specs>conversion.bravo

4. CONVERSION FROM INTERMEDIATE LEVEL STRUCTURES

The converter scans the intermediate structure, and all of these structures are converted into memory level structures, except certain pseudofunctionals which specify functional definition, category membership, further specification, and procedural attachment. The correspondences between intermediate structures and memory structures are listed in the section on data structure conversions. The pseudofunctionals used in meta descriptions are not converted into memory structures; the information they convey is stored in separate data structures by a process we call cataloging. To indicate that the meta description is not complete with respect to the original message level form, the PartialMeta flag is set in the handle to the metaAnchor for the structure which should have contained the information.

4.1 Data Structure Conversions

This section is a brief index into the conversions which go on between message level forms and memory level forms. Interpreted MapDescriptors are an internal form which are structurally very similar to MapDescriptors, but which are treated specially by Align when doing semantic (nonstructural) matching (see section 6 and 7). Two special syntactic forms and a number of pseudofunctionals are converted into these Interpreted MapDescriptors as indicated below.

Message FormMemory Form

PerspectiveMapDescriptor
SpecificationMapDescriptor
SequenceSequence
SetSet
Lisp InvocationInterpreted MapDescriptor
CaseInterpreted MapDescriptor
FunctionalMapDescriptor or Interpreted MapDescriptor (see below)

FunctionalUnit PrototypeArgument Slot Names

OrDisjunctionalternatives
NotNegationrejectedDescription
SetOfSetDescriptionelementDescription
SequenceOfSequenceDescriptionelementDescription
MemberOfElementDescriptioncollectionDescription
ContainsCollectionDescriptionelementDescription
DoImperativelispForm
DuringContingencyworldcontingentDescription
AlwaysInvariantDescriptiondescription
CurrentlyPresentDescriptiondescription
Lisp*LispValuelispForm variables bindings
Using*CaseSelectionkey matchControl patterns resultingDescriptions

* indicates a special syntactic form rather than a functional.

The user has two methods for getting access to the fields of an Interpreted MapDescriptor. One is through binding in a structural Align. The other is through a Lisp function

GetIA(imd oldHandle)Returns a handle for the anchor which is the argument for the Interpreted MapDescriptor, imd.

4.2 Functional Definitions

On any unit one can define an abbreviation for a perspective based on that unit. The pseudofunctional HasFunctional is used in the meta description of a unit to define such an abbreviation. For example, we can define a functional HusbandOf as follows:

# Family ↑11: HasFunctional(maleParent, HusbandOf, femaleParent)
self: A Group
maleParent: A Person; A Male
femaleParent:A Person; A Female
children:A Group

Using this definition, the following two descriptors are equivalent:

HusbandOf(Mary)
The maleParent from a Family with femaleParent = Mary.

The cataloging process stores the information contained in the HasFunctional declaration on an atom record on the name of the functional; e.g. on the atom HusbandOf. Since atoms are unique throughout the system, functional names are globally defined. The PartialMeta flag is set in the handle of the unit meta description indicating that a functional was defined there, but no other record is left. The conversion process uses these functional definition records to convert intermediate level functionals to their corresponding perspective forms, and then converts the perspective forms into memory level structures. No indication is placed in the memory structure to indicate that a mapping was entered from message level in a functional form.

The syntax for a functional declaration is:

functionalSpecification =
[whichForm *] "HasFunctional" * "(" focusSlotDesig "," functionalNameForm
{"," slotDesig} ")" [pairList].

functionalNameForm = [whichForm] ["Interpreted"] functionalName.

focusSlotDesig = ["MemberOf"] slotName.

slotDesig = {"Quoted" | "MemberOf" | "Optional" | "Sequence" | "Set"} slotName.

The Which and WhichIs alternatives for the functionalNameForm indicate preferred external format for instances of the functional. The keyword Interpreted indicates that that an interpreted map descriptor is to be constructed rather than a standard one. The keyword Quoted indicates that the argument will be enclosed in a KrlPointer descriptor. The keyword MemberOf indicates that a form containing a MemberOf functional should be constructed around the filler, or around the entire perspective if the MemberOf is on the focusSlotDesig. The Sequence and Set alternatives may only appear in a slotDesig in the last postion in the declaration: they specify that the functional may have arbitrarily many arguments after the last named slot which are to be collected as a sequence or set. The Optional alternative specifies that no filler pair should be constructed if the given instance argument is not present, rather than causing an error or building an empty collection.

4.3 Category Membership

KRL-1 provides a standard mechanism for inheritance from a unit, say Dog, to another unit, say Animal. In the self slot of Dog one puts a unit perspective An Animal. The category mechanism is an additional mechanism which provides a way of specifying mutual exclusion of mappings in a set of simple cases; for example, to reject quickly a match between something described as A Dog, and something described as A Cat, where both Dog and Cat may both be described as An Animal (but need not be). The category mechanism provides a way of specifying trees of mutual exclusions of mappings. The chain in the tree may sometimes be used to verify a simple mapping inheritance without going through each successively more general prototype individually.

Examples

# Dog
self:↑1 An Animal1: Category(Animal, Species)

# Cat
self:↑1 An Animal1: Category(Animal, Species)

# Vertebrate
self:↑1 An Animal1: Category(Animal, Anatomical)

# Invertebrate
self:↑1 An Animal1: Category(Animal, Anatomical)

[CategoryTree ’Species
’(AnimalCat
(Dog Poodle (Spaniel CockerSpaniel EnglishSpaniel IrishSpaniel]

Comment on Examples

The footnote on the self slot of the first two units contain the specification of the incompatibility of the descriptions A Dog, A Cat. The first argument of the functional Category is a coreference to the common tree ancestor (in this case Animal). The second argument is a Lisp atom which names the tree in which Dog and Cat should be compared. The units for Vertebrate and Invertebrate indicate why a single tree is insufficient. It is clear that the latter two units are incompatible prototypes with respect to an anatomical description of an animal. But it is plausible (perhaps even correct) to describe a single entity as both A Cat and A Vertebrate. In the above units, note that the descriptor An Animal needed to be put explicitly in the footnoted slot if such inheritance is desired, and is not implicit in the Category meta description on the slot. As mentioned earlier, the chain in the tree may sometimes be used to verify a simple mapping inheritance without going through each prototype individually.

The call to the Lisp function CategoryTree shows another way of expressing some of the same information that is expressed in the unit meta descriptions. In the tree named Species, Dog and Cat are incompatible, and Dog has two incompatible children Spaniel and Poodle, and Spaniel has three children which are incompatible. This tree could be used to verify quickly the incompatibility of CockerSpaniel and Cat.

Basic Lisp Functions for Manipulating Mutual Exclusion Trees

For each category tree, there is a Lisp list structure isomorphic to a tree like the one shown in the example. The elements of the tree are slot coreferences. For each slot in a tree, there is a Lisp list paired with a handle to that slot anchor. The pairing is done using the Handle hash link mechanism described below. The associated list is an association list indexed by tree name; each value is an ordered list of handles of slots which are on the ancestor chain starting from the indexed slot.

In the following functions, the treeName argument is a Lisp atom, and the tree members are handles to slot anchors. If an atom is given instead of such a handle, it is coerced to a handle for the self slot anchor of the unit named by that atom.

(MakeParent parent child treeName) which creates a new linkage between child and parent as described above.

(InsertParent newParent child treeName) replaces the linkage between child and its current parent in treeName with one to newParent, and creates a linkage between newParent and the former parent.

(DeleteBranch node treeName saveDescendantsFlag) deletes a portion of the tree named by treeName from node down. If saveDescendantsFlag = T then then descendants from this node are attached as children to the parent of the node in the tree.

(TreeRelation node1 node2 treeName) returns a specification of the relation between node1 (a handle to a the self slot of a unit) and node2 in tree. Its return values are

ABOVEnode1 is above node2
BELOWnode1 is below node2
SAMEnode1 is identical to node2
CONFLICTnode1 and node2 have a common parent and are not identical
NONEthere is no relation in tree between node1 and node2

If tree is not specified then all possible trees are searched, and if the two units share more than one tree, a signal is generated with the list of shared trees available.

(HasCategories node) Returns an alist keyed by the names of category trees that this node (labeled anchor) appears in; returns NIL if it appears in no category trees.

(TreePrint treeName) prints tree in the form shown above (a form using CategoryTree).

(CategoryTree treeName treeList) builds the internal data structures associated with treeName and treeList. As shown in the example, treeList is a nested list structure of unit names (LISP atoms) or handles to slot anchors.

4.4 Hash Links to Handles

In order to find items associated with certain memory structures without having a field in the memory structure itself (which would require access to the memory file), we provide a facility which is equivalent to the hash linking mechanism for pointers in Interlisp. Since pointers to the file go through the intermediary of a handle, the hash link should work off the contents of the handle rather than the address where the handle is stored. A set of functions comparable to some of those on page 7.4 of the Interlisp manual are provided which work with the contents rather than the address of handles: HPuthash, HGethash, HRehash. The array used by these functions is an ordinary array built by a call to the function ARRAY. Therefore Maphash, ClearHash, and Harray equivalents are unnecessary. The SETA part of the array is used to hold a handle which is a key, and the SETD holds the associated value. The various forms of array specifiers of ordinary hash arrays are not supported. Therefore if an array overflow error occurs, the user is responsible for HRehashing into a new array and setting the appropriate global variable to the value of the new array.

4.5 Further Specifications

At the message level, one unit (Son) is designated as a further specification of another (Father) by the following notation:

# Son↑11: FurtherSpecified(Father)

The meaning of further specification is that the Son inherits all the slots and triggering information from the father unit. At cataloging time, this footnote will cause a direct link from the self slot of the Father unit to the Son unit to be cataloged and placed in the tree called FurtherSpecified (see section 4.8 for further information about trees).

This is implemented by distributing information at the time of conversion from intermediate structure to memory structures. A given mapping to be added to an anchor is expanded into a set of mappings reflecting the further specification chain up from the son to father and so on, and attaches the filler pairs given in the initial mapping descriptor to the highest possible prototype in the FurtherSpecified chain. Thus if we have:

# Father
self:
s1:
s2: A Bar

# Son↑11: FurtherSpecified(Father)
s2: A Mumble
s3:

then a description A Son with [s1 = d1] [s2 = d2] [s3 = d3] would be converted into two mappings, one the equivalent of A Father with [s1 = d1] [s2 = d2] and the other the equivalent of A Son with [s3 = d3].

Mappings with prototypes for all the entries in the further specified chain are always added, even if no filler pair is present which necessitates this.

All relevant triggers will be activated, regardless of position in the hierarchy. Thus in the above example, WhenFilled triggers attached to either s2 in Son or s2 in Father would be activated.

The access compiler converts calls to Seek to look for a filler pair attached to the highest prototype in the tree, and if that fails then it invokes servants from the bottom up. Thus a Seek with main argument the s2 from G00354 viewedAs a Son would look first for the filler of a pair with name s2 in a mapping with prototype Father, then check for servants on the s2 slot of Son, then on the s2 slot of Father.

4.6 Procedural Attachment

Procedural attachment of triggers and traps is done in KRL-1 in a style very similar to that done in KRL-0. A user can put in the meta description of any slot a special functional which indicates the trigger or trap to be used. As in KRL-0 triggers are probed by the system when using a unit as a template, in certain well defined situations. We will list the system probed triggers below. In addition to triggers on individual slots, the user can specify triggers which will be probed if any of a set of slots in the unit are "touched" by using a special pseudofunctional on the unit meta description. The example below illustrates each of these:

# Column ↑11: TriggerOnAny({top, bottom}, WhenFilled, ’(TryToAdd))
top:↑2 A Number2: Trigger(ToFill, ’(CheckSumAndBottom))
bottom:A Number
sum:A Number

The pseudofunctional TriggerOnAny takes three arguments, a set of slotnames, a trigger name, and a Lisp form. The pseudofunctional Trigger takes two arguments, a trigger name and a Lisp form. The cataloging process indexes each trigger lisp form on the unit and slot name (the point of attachment for simple triggers, all those in the slot list for multiple triggers). The system will probe for the existence of specific types of triggers (known by trigger name) in circumstances specified in section 7. The user can of course probe slots for triggers with any name at any time. The pseudofunctionals Trigger and TriggerOnAny are not converted into memory structures, and the PartialMeta bit is set in the metaAnchor of any slot which contained a trigger form in its intermediate level version.

Traps are procedures which can be fired when the anchor they are attached to is "touched" in specific ways. A functional named Trap is provided which takes two arguments, a Lisp atom which is the trap name (eg ToFill, WhenFilled), and a Lisp form which is the expression to be evaluated when the trap is snapped.

The following are the types of triggers and traps probed by the system:
ToFind, ToEnumerate, ToMatch,
WhenFilled, WhenKnown, WhenEnumerationChanged, WhenDescribed, WhenIdentified

4.7 Other Special Functionals

NonPrimary: All labelled anchors are considered primary, that is, the default repository for standard information about an entity. Two entities represented by a primary anchors are considered distinct if their anchors are not the same. To handle what we called in KRL-0 manifestations, we need to be able to specify that a labelled anchor is nonprimary. Attaching the pseudofunctional NonPrimary() to a labelled anchor causes the anchor to be so marked, and all handles which reference that anchor to have a bit indicating that it is a nonprimary anchor. In order to allow references to labelled nonprimary anchors before they are defined in a unit, we will provide a facility to declare a set of labelled anchors to be noprimary at the beginning of a file. A memory level form is created for this pseudofunctional.

UniqueMap, NonUniqueMap: In order to know whether two mapdescriptors with the same focus can be considered to be descriptions of the same mapping, we need to specify if a mapping is unique with respect to that focus. The default is that mappings are unique with respect to the self slot (all unit perspectives can be folded), and not unique with respect to any other slot (no slot perspectives can be folded). In order to override this default, two pseudofunctionals UniqueMap() and NonUniqueMap() are provided which can be attached to a slot to indicate a change from the default. This sets a bit in the metaAnchor which is propagated to any handle which points to this anchor. To insure consistent propogation before the unit is defined, we will again provide a declaration mechanism for uniqueness.

Do: In order to cause side effects in aligning, a special pseudofunctional Do is used. The argument to Do is a single Lisp expression. The operation of Do is described in section 6 and 7.

4.8 Specification of the LISP interface in KRL-1

KRL-1 (as seen by the user, not the implementer) depends on INTERLISP in two major ways. First, it uses the low-level INTERLISP data structures, such as strings, atoms, and numbers. Second, although it has agendas and procedural attachment (traps and triggers), it has no mechanisms for ordinary control flow (sequences, conditionals, subroutines, etc.) or argument passing. For this purpose it is parasitic on INTERLISP, using all of the standard mechanisms (including CLISP constructs such as the iterative statement, generators, coroutines, etc.).

There exists a communication channel from LISP to KRL -- a conversion mechanism by which KRL structure can be created in LISP code using conversion-time values of LISP variables.

The Nexus and its evaluation

When a piece of KRL syntax is embedded in LISP structure (using \.../ or \...//), it is not a direct representation of a memory level structure, but is a representation of an intermediate level structure which can contain surrogates which are to be replaced at evaluation time. The reader creates a data object called a nexus which has file pointers to the original message-level structure, and a record structure representation of the intermediate level structure which resulted from parsing it. When a nexus is evaluated, it carries out an operation of conversion in which surrogates appearing in the intermediate level structure are evaluated and the results used to build a memory structure. The value returned is a handle to this memory structure. If the intermediate level structure contains no surrogates, the conversion is done only once and the result returned on subsequent evaluations. No copying is necessary as e.g. Describe always copies its argument. Otherwise, conversion is done each time the nexus is evaluated.

In fact, this process is shortcut by various subsystems. The access compiler looks at the nexus without first evaluating it, and compiles a piece of code which does the evaluations as needed in the execution. The interpreter, scheduler, etc. may do the same for some set of standard cases which can be easily recognized. However, any such shortcut must preserve the semantics of nexus evaluation.

The form of surrogates

A surrogate consists of an indicator followed by a LISP expression. The LISP expression is not preceded by a single quote, since it is one field of a surrogate, not an independent LispPointer descriptor. The LISP expression is evaluated when the conversion is done. There are four different kinds of syntactic elements for which surrogates exist: names, descriptors, tails, and paired tails.

Names: Anywhere in the syntax where an arbitrary literal atom could appear (i.e. the non-terminal literalAtom in the syntax document), a surrogate of the form !Name expression can appear (!Name can be abbreviated by !N). The expression must evaluate to a literal atom. In the current syntax, literal atoms can appear as the expansions of unitName, slotName, functionalName, and as the first element in a bindingPair.

Descriptors: Anwhere in the syntax where a descriptor can appear, a descriptor surrogate can appear. The indicators for descriptor surrogates are prefixed by a single !. In parentheses after the full name is a short form which can be used as an abbreviation. A descriptor surrogate produces a descriptor (or in one case, !Description, an anchor) which appear in the description where the surrogate appeared. The indicators for descriptor surrogates are:

!Descriptor: (!Dr !Descr) The expression must evaluate to a descriptor handle (see the Datatypes document for a further description of handles), which points to a descriptor which is be copied into the constructed form.

!Lisp: (!L) The expression is evaluated, and its value is made into a LispPointer descriptor.

!Coreference: (!C !Coref) The expression must evaluate to an anchor handle for a labelled anchor. The surrogate is replaced with a coreference descriptor with that anchor as its target.

!Krl: (!K) The expression must evaluate to a handle, which is then embedded in a KrlPointer descriptor.

!Description: (!Dn !Descn) The expression must evaluate to an anchor handle. The descriptors in that anchor are copied into the description containing the surrogate.

!Post: (!P) If the expression does not evaluate to a handle, its value is made into a LispPointer descriptor. If it evaluates to a labelled anchor handle, then it is placed in a coreference descriptor, otherwise it must be a handle to a KrlPointer descriptor, a copy of which is used.

Tails: Anwhere in the syntax where a descriptionSequence can appear (a sequence of descriptions separated by commas in the normal syntax), a tail surrogate can appear. The indicators for tail surrogates are identical to those for descriptor surrogates, but prefixed by a !!. A tail surrogate contains a LISP expression which must evaluate to a list, each of whose elements meets the specification of the corresponding descriptor surrogate. It produces a sequence of anchors, each containing a descriptor (or in the case of !!Description, a list of descriptors) corresponding to an element of that list. The current syntax has descriptionSequence in a setEnumeration, sequenceEnumeration, and the argSequence of a functional.

The use of tail surrogates in pseudo-functionals is not supported.

Paired Tails: There are several places in the syntax (fillerPairs, pairList following a Functional) which allow arbitrary sequences of pairs whose first element is a name and whose second is a description. In the usual syntax these are written using "=". In any of these contexts, a Paired Tail surrogate can appear. Its indicator is prefixed by !!!, and is chosen from the same basic set as the descriptor and tail indicators. It is followed by two lisp expressions (again without quotes) separated by an "=". The first expression must evaluate to a list of literal atoms, and the second to a list, each member of which fits the requirements for the corresponding descriptor indicator. The resulting form contains a set of pairs whose length is the minimum of the two list lengths, and which has the corresponding name before each = and the corresponding description following it.

An example:

Assume we have:

x bound to the list (B C D)

y bound to a handle for the self anchor from the unit:
#E
self: A Frob; Which Gritches
thing: A Whatever

w bound to the anchor for the thing slot of the unit E

z bound to a list of four descriptor handles corresponding to the descriptors:
A Frob, A Bletch, A Blivet, and A Grindle.

Then the nexus produced by reading the characters:

\A Frob with
!Name (CAR x) = !Coreference y
foo = {!!Lisp x, ...}
bar = !Coreference w
!Description y
bletch = !Name (CADR x)
Which !Name (CADDR x) (!Krl y, !!Name x)
!!!Descriptor (CDR x) = z/

produces the same memory structure as would have been produced from a message level structure as follows:

\A Frob with
B = E
foo = {’B, ’C, ’D, ...}
bar = The thing inUnit E
A Frob
Which Gritches
bletch = C
Which D (Structure self inUnit E, B, C, D)
C = A Frob
D = A Bletch/

Notes:

1. The first pair uses B as a slot name, while E is a coreference descriptor to the self slot of unit E.

2. The second pair describes a set whose members include the LISP atoms B, C, and D.

3. The third pair contains a slot coreference and a copy of the descriptors in the anchor bound by y. This is not the same as establishing a coreference to y -- all it says is that the same descriptors are to be used.

4. The fourth pair describes an entity which is coreferent with the self slot of unit C, and which is in the relationship named by the functional D applied to four arguments. The first of these is a KrlPointer to the labelled anchor handle for the self slot in E, and the other three are coreferential to units B, C, and D.

5. Unit coreferences can be produced either by giving a !Name surrogate in an appropriate context where an atom name would be parsed as a coreference, or by using a !Coreference surrogate whose expression evaluates to a handle to an anchor which is a self slot.

6. In the final pairs, even though z contained 4 descriptions, only two pairs appear, since the list of names included only 2 items.