[Indigo]<KRL>document>str!3

One of the major developments in KRL-1 (over KRL-0) is a formalization of the "meaning" of the syntactic forms provided by the language. In KRL-0, we provided a large collection of different forms and an intuitive guide to how and where they should be used. The functions Match, Seek and Describe were specified in terms of the possible combinations of forms which might serve as inputs and stored data. For each possible combination, at each point of the process, we either specified exactly what would be done, or provided a named signal indicating the combination, and left it up to the user what to do. In fact, by the time KRL-0 was retired, only a small fraction of the possible combinations had been handled -- only those which actually came up in the small set of programs which were debugged.

Our goal in designing KRL-1 was to provide a clear and principled framework for understanding what could and could not be done with the description forms which make up a KRL knowledge base. In doing so, we realized that part of the complexity of using KRL-0 (and most AI languages) comes from the fact that many of the mechanisms are called upon to do double or triple duty. The same syntactic device is used for a variety of different things, and the programmer needs to be constantly aware of how each thing is being used in each case.

In developing KRL-1, we concentrated on sorting out the different dimensions of structure which we found in AI representation languages. The result is an overall framework which seems quite complex at first -- it has layers and levels, descriptors, descriptions, anchors, entities, and a host of other conceptual distinctions. But this diversity arises from an attempt to be as explicit as we can in characterizing just what structures can be built and just what kinds of reasoning can be done with them. We feel that it has more than payed off in the clarity of our understanding both of our own system and of other systems which incorporate many of the same concepts (see Smith and Brachman ?? for an attempt to characterize all AI representation systems along similar lines).

Table ??.?? lists the 8 dimensions we have distnguished, with some specific issues connected with each. In this section (str-lev??) we will use a simple example (Example ??.??) to provide illustrations of each dimension. In cases where there are alternative ways of stating things, or optional descriptive structures, we have tried to illustrate the different possibilities by arbitrarily doing one part of the example one way, and one another. For an example as simple as this one, the mechanisms of KRL-1 are clearly a case of overkill. Those familiar with representation systems will see implications for larger and more complex examples, and further sections of chapter ??str?? examine each dimension in detail. The order of those sections is different from the order of the introduction here, in a way which we hope will make the connections clearer. In the more detailed discussion, whenever possible, we try to make use of and extend the initial example ??.

KRL is organized around a notion of objects with structured descriptions. This is somewhat different from the more common formal structure based on constants, variables, and predications (thought of as "nodes and links" in semantic networks, or "atoms, variables, and assertions" in Planner-like languages). In a way, it is closer to the record-based data structures of more traditional programming languages like PASCAL or INTERLISP, and it is in the spirit of "frame" representations as advocated by a number of researchers. For a general discussion of this style of representation, the reader is referred to the Overview (Section 2) and references ???(Brachman??). In Example ??.??, the definitions of Person, Pet, Act, GiveDescription and Own are prototypes used as a basis for structured descriptions in the other units.

In making the comparision with record-based data structures, it is important to recognize that KRL (unlike the standard languages) makes use of a recursive power of description. If an INTERLISP program has a record definition for Pet with a field named Owner, then any instance of Pet will have a filler for that field which is a pointer to a specific person. In KRL, on the other hand, we can have structures like that in the example:

In this case, the name field has been filled in with a value in the standard way, but the owner field has been filled with a description of the owner, rather than a pointer. This recursive use of description provides the structure for the matching process described in section ??.??. Other AI formalisms achieve the same effect by other means. In predicate calculus, an existentially quantified variable would be introduced, saying in this case: Ex Owner(x,Farley) & nSex(x,Male) & LastName(x,"Samovar"). Most semantic net and planner-like systems would require an ad hoc solution, in which an individual (node, atom, etc.) is created for the owner, and specially marked to indicate that it was not to be treated as a unique individual in reasoning. In general, the recursive structuring of KRL descriptions (along with its use of prototypes) replaces many (but not all) of the uses of variables in the predicate calculus. Section ?? discusses the advantages and disadvantages of this structure.

An obvious consequence of basing the structure on objects with attached descriptions is that any description (including one used recursively) can contain an arbitrary number of separate "descriptors", each adding something to the overall description of the thing to which it corresponds. There is a vocabulary of different descriptor types, (enumerated in section ?? below) any of which can be used in any place where a description is given. This leads to a combinatorial matching process, as discussed in Section ??. In this sense, it is unlike the simple pattern-matchers of AI languages, and more like the general problem of "unification" faced in a predicate calculus system, in which the appearance of a particular constant or variable in more than one proposition can be thought of as "multiple description" of the object it represents.

Finally, the example illustrates that the user of KRL works with a mixture of things he or she defines (such as Person and GiveDescription) and things which are built in as part of the underlying system (such as String and HasFunctional). As in LISP, there is no syntactic barrier between system-defined and user-defined objects. The only way to tell that something is part of the basic system is that it is not defined elsewhere. This makes it easy to build an "onion" in which each layer is viewed as a user-program by the person who builds it, but as part of the system by those who later build around it. Section ?? summarizes the central core of built-in objects and names.

In sorting out the dimensions of structure in KRL we came to realize that our previous discussion of "units" had combined three quite different aspects of structuring: object identity, name scoping and memory chunking. Each has an important place in a representation language, and we have (after much discussion) left them combined as before. However the structure of levels (see Section ??) below provides a way of identifying the different aspects and separating them when necessary. The following rough characterizations are expanded in sections ??.

Object identity: A unit is like a node (a predicate or constant). In general, a unit is used to represent an individual object (such as Farley), or a particular prototype (such as Person). Semantic networks and planner-like systems have a similar standard use of nodes or atoms. The recursive descriptive structure of KRL means that descriptions will appear within units which describe other objects. For example, the description A Person with lastName = "Samovar" appears inside the unit for Farley. In general, it can be assumed that units refer to unique individuals (i.e. no two units refer to the same object), while embedded descriptions may be "co-referential" with other embedded descriptions or with some unit. This is a very useful approximation, but needs to be overridden in some cases, as discussed in Section ??.

Name scoping: A unit is like a program block. In most programming languages there is some notion of "name scope". The written form of a program includes identifiers whose "binding" is determined according to where they appear. Thus, for example, the variable "x" can have different referents if it appears in two different blocks of an ALGOL program, each of which declares it. AI formalisms such as semantic nets have generally eliminated this kind of structure, providing a single global name space. In predicate calculus, there are well-defined scope rules for variable names. In KRL, the unit provides a level of scoping for local (slot) names. Thus, for example, the descriptor My owner appearing in the unit for Pet and the names owner and owned appearing in the definitions associated with Own get their meaning from the fact that corresponding slots are declared for the units in which they appear. There are a number of issues regarding the locality of names (including the desire for non-hierarchical scoping structures) which are discussed in Section ??.

Memory chunking: A unit is like a page of memory. The third aspect of units (the one given prominence in the Overview) is that they provide a way of imposing an accessing-distance structure on memory. From the point of view of pure deduction, this additional organization is redundant or irrelevant, since it does not affect the set of deductions which can be made. From the point of view of building effective systems, it can be critical in providing heuristic guidance in the reasoning process. A number of mechanisms ("packets", "vistas", "length of path") have been proposed in various AI systems, and the particular choices in KRL are discussed at some length in the Overview (Section 2.6). We can think of access modules as being like pages in a system using paged secondary memory. Accesses within a page are "fast" while those across pages can be "slow". This difference can determine the course of reasoning in the case of resource-limited matching We see this issue as central to the design of systems which do reasoning on the basis of "plausible inference", rather than pure deduction. Winograd (1979??) presents this view in the context of past AI systems and the kinds of "extended inference modes" they allow.

The access structure could be completely orthogonal to the logical structure represented by units, but we have chosen to combine them. We have not yet had enough experience with resource-limited reasoning to come up with a better scheme. As a simple example in the Example ??.??, the information that Farley is a Poodle does not appear in the Farley unit, but in the unit for SallySamovar, where the descriptors A Poodle and Farley appear together. This means that the matcher would need to find the SallySamovar unit before being able to determine Farley’s breed. Section ?? discusses the matching process as combining the two processes of finding relevant descriptions and making inferences from them.

One of the most active research areas in artificial intelligence today (see, for example, refs???) is the design of systems containing "meta-knowledge" -- knowledge about the system itself which can be used in the same style as knowledge about the domain in which the system operates. KRL-0 contained a collection of relatively ad hoc mechanisms for describing the structures themselves (such as "features" on descriptions). KRL-1 has a general notion of "meta-description" with a well-defined semantics. In principle, knowledge about any aspect of the system can be represented directly in the KRL knowledge base, and used in the running of the system. There are many complex issues raised by different levels of self-reference, and the integration of them into a running system. These are discussed in Section ??. There is a special syntactic device (analogous to footnotes in text) which is used for indicating meta-description in the printed form of KRL structures. In Example ??.??, there are illustrations of several kinds of meta-description: Procedural attachment (in the unit for Person), name definition (in Own and GiveDescription), structure specification (in GiveDescription), and the labelling of knowledge as to its origin (in Farley). The GiveDescription unit as a whole is included in the example in order to provide a prototype for meta-description.

Many of the complexities of representation formalisms arise because of the need to staisfy demands posed by different roles played by the notation. It must be perspicuous for those who write and read it, have a reasonable structure for parsing and machine analysis, be stored efficiently in memory, and provide a basis for a coherent reasoning algorithm. Often, decisions which aid in one direction (e.g. readability) have bad consequences in another (e.g. efficiency of storage, or consistency of reasoning). In KRL-1, following Brian Smith’s analysis of Knowledge Representation Semantics (Smith 1978???) we have formally distinguished four differnt "levels" of structure. Each level has its own well-defined syntax, and there are rules for conversion between adjacent levels. The levels are labelled: belief, memory, intermediate, and communication.

Belief Level: This is the level at which logic is done. Its basic elements correspond closely to the predicates, constants, and variables of logic, and its design is guided by a desire for uniformity and simplicity, which makes the statement of general inference procedures relatively easy. At this level, for example, there is no notion of "memory unit" which deals with accessability, or of "abbreviation" which simplifies the writing of structures.

Memory Level: This level is the way the structures are stored in the underlying machine. It is still based on abstraction (in the spirit of abstract data types in programming languages), not the bits and switches of the machine itself, but its characteristics are close to the way storage is actually manipulated. Its design is guided by the desire to provide long-term storage which makes access and modification easy. In the reasoning process, memory level structures are accessed and treated (either through actual conversion or equivalent code) in terms of the corresponding belief structures.

Intermediate Level: This is the level corresponding to a parse of the syntactic forms in the printed version. It is tree-structured, has a notion of lexical scoping, and retains all of the connections to LISP. In converting from intermediate level to memory level, a number of changes are made: abbreviations are expanded (in a manner similar to the compilation of macros); names are bound according to their scope and replaced with direct pointers; LISP "surrogates" which allow substitutions based on the current LISP context are evaluated; and some descriptors which have alternative syntactic structures are converted into canonical memory forms. In general, it is the intermediate level which is manipulated by LISP programs, since it is a standard LISP tree structure whose terminal leaves are atoms. The particular combination of choices of what appears at intermediate level and what appears at memory level is arbitrary. For example, we could have chosen a tree-structured scope-and-name form for memory, rather than converting it to a directed graph based on unique pointers. However, by having multiple levels, we are able to optimize the handling of different operations at different levels.

Communication level: Finally, there is the form seen by the user. This has two different parts: a written form, and an interactive "browser". The written form is based on a "two-and-a-half dimensional" syntax which makes use of coordinate information (i.e. indentation) to decide on syntactic groupings, and has footnotes to indicate meta-description. For example, in the unit for Farley, the indentation indicates that it is the Pet, not the Person which has the name "Farley". The syntax uses a number of special characters to indicate underlying structures (e.g. different forms of brackets to indicate argument lists, sets, and sequences). (See Section ??). All of these are converted into explicit list structures at the intermediate level. Different type fonts and faces are also used to increase the readability of printouts. The browser provides a structured graphic environment (using windows and menus with a pointing device) which enables a user to interactively edit KRL memory structures. It has a quite different organization because of its interactive style. It is described in Section ??.

It is difficult to convey the significance of the levels without going into more detail. Throughout the rest of this document, there are places where a mechanism (such as that for further-specification hierarchies) is described in terms of its realization on different levels. We have found this an extremely useful tool in keeping straight just what we are doing, and what its semantic implications are. Section ?? describes the levels in more detail.

In addition to the four "principled" levels, there are a number of places where specific parts of the KRL structure are converted into a specially accessible form. For example, procedural attachment can be thought of as one use of meta-description at the memory level. However, instead of storing this information in memory using the standard attachment for meta-description, it is stored in a separate hash-coded table for fast access. We have explored the possibility of uniform notions of compilation and compaction which would make it possible to take any aspect of KRL structure and put it into a special form with appropriate declarations. This is discussed in Section ??.

Hierarchies as logical implications. The simplest notion is that which has always been part of semantic net formalisms, the use of a hierarchy to represents facts such as "All poodles are dogs" and "All dogs are animals". A link in the hierarchy represents a subset relation between the classes of entities denoted by the node. In many cases (including KRL), links between individuals and categories ("Farley is a poodle") use similar mechanisms to the generalization. In KRL, this kind of structure is realized through the use of the self description of a unit.

Hierarchies as mutual exclusion. In some cases, it is useful to represent explicit partitioning relationships. This is not equivalent to the notion of implication. All dogs are animals, and all pets are animals, but we are not thereby entitled to infer that dogs are not pets. In KRL-0 we used a mechanism based on theories of category type which were not general enough (see Bobrow and Winograd, 1979 for discussion). In KRL-1 there is a general mechanism for specifying any number of independent mutual-exculsion hierarchies. There is a special syntax, as illustrated by the list at the end of Example ??.?? In that example, Cat and Dog are listed as mutually exclusive, while Pet is not mentioned at all, leaving open the possibility that it applies to any of the other categories. The mutual exclusion mechanism is described in Section ??.

Hierarchies as further specification of structure. In a system based on structured abstraction, a hierarchical relationship can provide for the inheritance of internal structure (the list of slots) as well as the overall subset relationships. This kind of relationship forms the basis for hierarchies in languages like FRL (ref??). In KRL, it is called "further specification". In the example, the fact that GiveDescription is a further specified Act indicates not only that every instance of GiveDescription is an instance of Act, but also that it must have an actor and a time. The differences between simple logical hierarchies and further specification are complex, involving the inheritance of procedural attachment, the use of names in specifying mappings and combinatorial efficiency considerations in searching for descriptions in prototypes. These are elaborated in Section ??.

One of the main features of KRL is the systematic use of procedural attachment to provide "demons" and "servants" for structuring computation. In KRL-1 the basic ideas discussed in the Overview (section 3.1) are built into a more general framework which uses meta-description. In the example above, the footnote on the Person unit sets up a demon which is called whenever a name is filled in for a person. The demon calls a LISP function guessSex which makes use of the triggering context (see details in Section ??) to try computing and filling in the sex of the person from the name. There are also special syntactic forms for describing the results of LISP computations with specified environments (not illustrated in the example). We have thought a good deal about providing a more uniform general form of procedural attachment based on a notion of "system event", as described in section ??, but this was not implemented in KRL-1.

One of the problems encountered in using almost every representation system is the double nature of abstractions. We can choose to view a unit (or node, or whatever the corresponding thing is in another system) for Poodle as representing a class (i.e. the class of all poodles), or an individual which is a member of the class called Breed. In general, we want to do reasoning which goes back and forth between treating an abstraction in these two ways. We want to reason that "Poodles are dogs and Farley is a poodle, so Farley is a dog", and also to say that "poodle is one of the breeds listed in the kennel club index". In application after application, it has become apparent that the "prototype-abstraction relationship" is complex and needs to be carefully represented. KRL-0 attempted to blur the distinction, combining the two views with no separation. The descriptors An Animal and A Breed appeared together in the self slot of the unit for Poodle. In designing KRL-1, we went though a series of alternatives (marks for the two different kinds of descriptors, separate self slots, separate but interlinked units) and were never completely satisfied. In KRL-1 we did not build in a solution, leaving it to the individual user to specify the connections. These problems were avoided in the example above, but are discussed with examples in Section ??. Brian Smith has done a careful analysis of this problem (ref??) and we consider it one of the areas where we clearly need to do further design.

One of the features of network representations is that they often allow links whose logical structure is not well specified, but which serve as some kind of "association". KRL-0 had an index facility, as described in the Overview (section 2.7), and we have not done much further exploration in this area. Some ideas for integrating the indexing mechanism with some of the special structure storage (e.g. hash tables described above) are discussed in Section ??.