[Indigo]<KRL>document>str-syntax-lisp!1

Page Numbers: Yes First Page: 1
Heading:

April 25, 1979 4:17 PM[IVY]<KRL>document>str-syntax-lisp

Lisp syntax in KRL

B.3 -- Data Types in KRL-1

In KRL-0 there was a distinction between unit names and unit pointers which caused substantial confusion. In KRL-1 the situation is potentially even more confusing, because as well as the unit and slot names and the units and slots themselves, there are also the anchors in the slots to which descriptions get attached. These anchors are conceptually distinct both from the slots in which they appear and also from the descriptions attached to them (see the memo <Krl-1 Declarative Semantics> or the first chapter of the <Introduction to KRL-1> for more detailed discussion). Although we are trying to design all the standard functions to expect and return types which will be most often convenient, it will nonetheless happen that you will have a handle on one and will want to call some function which expects another. To cope with the complexity we are providing the appropriate functions and functionals described below, and also a well-constrained set of standard type-coercions to ease most of the conversion problems.

Names

Unit and slot names are LISP atoms. There are LISP functions called UnitFor and NameOf, and primitive functionals of the same name, which convert between unit pointers and unit names. Note the meaning for the KRL reader of the following character sequences:

" \Foo " means a quoted unit co-reference description,

" ’Foo " means the name Foo,

" UnitFor(’Foo) " means the unit whose name is ’Foo,

" SlotFor(’Foo, ’bar) " means the slot named bar in the Foo unit,

" \the bar fromUnit Foo " is a quoted slot co-reference description,

" NameOf(UnitFor(’Foo)) " is equivalent to " ’Foo ".

Type-coercion

All functions specify the type of the arguments that they expect. However there is a certain amount of type forcing of the following types:

pointer --> co-reference description:If a description is expected and a pointer (either to a LISP entity or a unit) is given, an appropriate co-reference descriptor will be assumed.

anchor --> description:If a description is expected and an anchor is given, the description attached to the anchor will be assumed.

units <--> atoms:If either a unit or an atom (i.e. unit name) is expected and the other is given, the appropriate conversion will be made.

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 event-driven control (system events), 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 are two basic channels though which LISP and KRL-1 communicate -- a command mechanism by which KRL-1 processes can be invoked from LISP code, and a LISP evaluation mechanism by which a piece of KRL-1 structure can describe a LISP computation (a binding environment and a form to be evaluated in it).

The form of KRL-1 commands

The basic operations carried out by the KRL-1 interpreter, scheduler, catalogue, etc. are invoked through KRL-Commands appearing in any place where a LISP expression would be evaluated (e.g. as a step in a PROG or as an argument to a function). A KRL-command is expressed as LISP form whose first element is the atom $, and whose second is an embedded KRL-1 anchor which describes a process to be carried out. Typically, this description will be a single descriptor which is a functional chosen from a standard set which has been "wired in" to the system. Some more complex combinations may be recognized, but these will be added slowly, as we see what is most useful. There is a general hook by which any other command description will be passed to a user program which can analyze it and carry out what the user wants.

The most difficult part of interfacing is the communication between the LISP context (variable bindings) and the KRL-1 interpretation of the command. Because of the multi-process nature of the system, there is no simple notion of context, and because of well-structuring dogma, we are insisting that all of the relevant LISP context be explicitly passed in the command and that results be passed back as its value, rather than through LISP side effects (i.e. free variable setting). In other words, the programmer cannot assume that the carrying out of the command will take place in the LISP environment in which it was invoked. Note: this will probably be relaxed for some set of global variables, and of course it is always possible to communicate results by modifying the KRL-1 data structures.

The passing of context into a command is carried out through the use of a constructor form. A constructor form is like a description, following the same syntax except for a set of special constructs which allow elements of the descriptor syntax to be replaced by a surrogate -- a LISP expression and a marker which indicates how it is to be converted to an actual descriptor form. The second element in a command is actually a constructor, rather than a normal description. When the command is invoked, the following steps occur:

1. All of the LISP expressions appearing in surrogates are evaluated

2. The corresponding descriptor forms for the surrogates are created and used in creating a copy of the constructor form, with the surrogates replaced by description elements, according to the markers.

3. The resulting (intermediate level) form is converted to a corresponding memory structure.

4. The memory structure is used by the command interpeter to carry out the command.

5. A result (whose content and form are specified by the particular command) is returned as the LISP value of the command form. For more information on how the value to be passed back is determined, see <krl>commands.doc

In fact, this process is shortcut by various subsystems. The access compiler looks at the constuctor, 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 command interpretation as stated above.

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 construction 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. 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 !. A descriptor surrogate produces a descriptor (or in one case, a list of descriptors) which appear in the description where the surrogate appeared. The indicators for descriptor surrogates are:

!Descriptor: The expression must evaluate to a descriptor handle (see <krl>handles.doc for a further description of handles), which points to a descriptor which is be copied into the constructed form.

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

!Coreference: 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.

!Handle: The expression must evaluate to a handle which is embedded in a Handle descriptor.

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

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.

Paired Tail: There are several places in the syntax (fillerPairs, inversePairs of an e.g., bindingPairs of a LispInvocation) which allow arbitrary sequences of pairs whose first elment 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) seprated 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 descriptor constructor:

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

produces:

($ \A Frob with
B = E
foo = {’B, ’C, ’D, ...}
bar = The thing inUnit E
A Frob
Which Gritches
bletch = C
Which D (Handle 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 to four arguments. The first of these is 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.

The form of KRL-1 Lisp invocations

KRL-1 has two different descriptors for embedding LISP structures into description structures. The simplest is the LispPointer descriptor which is indicated in the syntax by simply including a number or string (without further syntactic marking), or any other LISP expression preceded by a single quote. Semantically, it indicates that the entity being described is the same as the one represented by the LISP object (i.e. the description is a description of that string, number, atom, or list).

The second is the LispInovocation descriptor which is indicated in the syntax by the key word LISP followed by a description and an optional set of bindings. The description following the key word is assumed to describe a LISP expression (possibly a literal atom, number, etc.). Typically it is described using a LispPointer, but it need not be -- any valid description is legal. The bindings are a set of pairs whose left hand element is an atom representing a LISP variable, and whose right hand element describes a LISP object or KRL object (i.e. an anchor or descriptor). This, could in turn, of course, be described using a LispInvocation descriptor, or by describing it as the result of some KRL process. These right hand elements are actual descriptions, not constructor forms. They cannot contain surrogates.

The semantics of the LispInvocation form is that the descriptor as a whole describes the computation (not the value!) which would result from carrying out the following steps successfully:

1. Do a Seek, using the description following the key word LISP as the initial description, and seeking the LISP object described by it. The style and resources devoted to this Seek are determined by the style and resources of the process which chose to do the LISP invocation, typically another Seek.

2. For each pair in the bindings, Seek a LISP object described by the right hand side.

3. If all of these procedures succeeded, then set up a LISP environment in which each variable name in a binding pair is associated with the value produced by the associated Seek.

4. In this environment, evaluate the expression found in step 1.

Notice that this is all stated in terms of "if you did....the result would be...". That is, there is no commitment as to when this might actually be done. Therefore, the only free variables which can be included in the expression to be evaluated are those which are listed in the bindings, or universal global variables. Note that the semantics of this descriptor are somewhat vague, as they make no reference to the time at which the expression is evaluated. For most standard cases, it will not matter. For others, caveat emptor. Someday we’ll really integrate processes!

Typically, we are not interested in talking about the LISP computation, but about its results. To do this, we have the following unit and functional, which are recognized by the interpreter:

# LispInvocation↑11: HasFunctional(value, ValueOf, self)
self:
value: Or(A LispPointer, A Handle)

An example:

#Column
self:
top: An Integer
bottom: An Integer
sum: An Integer
ValueOf(LISP ’(PLUS x y) binding)
x = My top
y = My bottom

# Column1
self: A Column with
top = ValueOf(LISP ’(PLUS 5 2))
bottom = 5

# Column2
self: A Column with
top = ValueOf(LISP My expression)
bottom = The value from A Letter thatIs D
expression: ’(PLUS 3 4)

# D
self: A Letter with value = 5

If we invoke a Seek, looking for The sum from a Column thatIs Column1, specifying that it can only use units mentioned in the original specification:

1. It will Seek My top for Column1 viewed as a Column under the same restriction, first finding the descriptor ValueOf(LISP ’(PLUS 2 5)).

2. Since the description following the key word is already a LISP pointer, and there are no bindings, it will do the evaluation, resulting in 7.

3. Since the seek of My top has succeeded, it then seeks My bottom, trivially finding 5.

4. x is bound to 7, y to 5, and the expression evaluated resulting in 12, which is returned as the value of the overall Seek.

If we invoke a Seek, looking for The sum from a Column thatIs Column2, under the same conditions, then:

1. It will Seek My top for Column2 viewed as a Column under the same restrictions, first finding the descriptor ValueOf(LISP My expression).

2. It will Seek My expression as a slot in the unit Column2, looking for a LISP object, finding 7.

3. It will Seek My bottom looking for a LISP object, which will fail under the limitation put on seeking, since the descriptors available in the immediate units do not include a LISP object. If we had specified a more general Seek, it would have followed the map descriptor to the unit for D, found the 5, and continued as above to a successful answer.

The LispPredicate functional

Another common use of LISP in descriptions is to use a LISP predicate in a position where a descriptor is called for. This is particularly useful for matching. The LispPredicate functional makes use the LispInvocation descriptor, but associates it results in different ways. Its formal definition is slightly complex, but the notion is that the object being described gets bound to the variable given as the first argument, and the descriptor applies whenever the Lisp result is Non-NIL. It can be interpreted as saying that the following steps could be carried out.

2. For each pair in the bindings, Seek a LISP object described by the right hand side.

3. Seek a LISP object described by the anchor in which the LispPredicate descriptor appeared (or which inherited it), and bind the result to the variable name specified as an argument.

4. If all of these procedures succeed, then set up a LISP environment in which each variable name in a binding pair is associated with the value produced by the associated Seek.

5. In this environment, apply the function found in step 1 to the object found in step 3.

6. The value produced by this evaluation will be non-NIL.

Notice that again this is all stated in terms of "if you did....the result would be...". That is, there is no commitment as to when this might actually be done.

The Formal definitions (almost -- with some handwaving)

# LispPredication↑11: HasFunctional(candidate, Satisfies, variable, quoted specification)
self:
specification: A LispInvocationDescriptor
candidate: A Thing
variable: An Atom
invocation: A LispInvocation with value = Not(’NIL)
<an invocation which corresponds to the specification, but with an
extra binding pair whose identifier is my variable name and
whose binding is the result of seeking a pointer for my candidate>

# SimpleLispPredication↑11: HasFunctional(candidate, SatisfiesPredicate, function)
self:
function: An↑2 Atom2:Comment("must be the name of a one-argument LISP function")
candidate: A Thing
invocation: A LispInvocation with value = Not(’NIL)
<an invocation which corresponds to the application of the function
to the result of seeking a pointer for my candidate>

An example:

#MagnitudeRelation
self:
top: An Integer
Satisfies (’x, LISP ’(GREATERP x y) binding y = My bottom)
bottom: An Integer
SatisfiesPredicate (’NLISTP)

If we invoke a Match, with datum = 3 and pattern = The top from a MagnitudeRelation with bottom = The value from a Letter thatIs D, (which would of course be done with a functional), and if we specify a process description which enables the matcher to use evaluation of LISP predicates as one of its strategies, then it will do the obvious and end up evaluating (GREATERP 3 5) resulting in a NoMatch. Note that the other way around is not fully specified in the unit as given -- we have said that anything which is a top must satisfy the predicate, but not vice-versa. In order to do that, we need to put a Criterial footnote on the functional. This care is necessary, as illustrated by the predicate associated with the bottom. Indeed, anything which fills it will not be a list, but we cannot infer that all things passing this predicate must therefore be appropriate fillers.