[Indigo]<KRL>document>str-lev-krs!3

NOTE -- THIS IS OUT OF DATE, and needs reviewing. For example, implications are beliefs, which this denies. Descriptions mention other anchors, not connect to them. Etc. Etc.

1.An Introduction to KRS
2.The Levels of KRS
2.1Level 0 and Representation
2.2 Level 1 and Meaning
2.3 Level 2 and Description
2.4 Level 3 and Language
3.The MetaDescription Layers
4.KRS, KRL, and the KRL-1 Interpreter

During the last several months I have been trying to work out a clear semantic foundation for KRL-1. My thesis is intended to be a thorough explanation of those issues, and a brief description will be included in the new verion of the Introduction to KRL-1 (the descendent of Terry’s first pass at a "manual"). However both those documents will take some time to complete, and in the meantime, in designing the interpreter, we are using numerous technical terms and concepts which derive from those semantics. This memo is meant to be a brief overview of the main ideas.

KRL is simultaneously a representation system, a theory of description, and a programming language. In formulating a semantic theory of KRL, it has turned out to be useful to separate out these various functions and to isolate four distinct levels or viewpoints from which to understand any piece of KRL structure. Each level has its own distinct uses, and various parts of the interpreter focus on understanding the structures that they are working with from one viewpoint or another.

The levels are numbered 0 through 3, and are generally referred to by number, although informally each of them is designed to deal with a certain class of issues as follows:

Although they are in some sense simultaneous viewpoints which one can have on a piece of KRL, I call them levels since there are precise relationships only between adjacent levels: for example one can understand the relationship between level 1 and level 3 only in terms of the intervening level 2.

The theory of these four levels and of the relationships between them I have called KRS, for Knowledge Representation Semantics. In general I use the word semantics in a loose way to refer to the relationship between a symbolic object and its meaning. Within KRS you can view each deeper (lower numbered) level as being the semantics of the level above it. However there is also a sense in which all of KRS can be viewed as the semantics of KRL, since any piece of KRL structure has meaning from the point of view of any of these levels. Therefore I will not in general use the words semantics alone when I want to be precise about which level I am talking at, but rather say something like "its level 1 meaning".

The discussion of KRS in this memo is cast informally in English. However, since KRS is itself a formal system, a careful exposition of it requires talking about it in a formal language -- and the obvious language to use is of course KRL-1. Hence, before we finish the interpreter I expect to have a complete set of units which are written in KRL-1 which completely describe both the KRL-1 language and the KRL-1 Interpreter in terms of KRS. Many of these units will be used both in the explanation of KRL-1 semantics, and also by the interpreter itself to guide the interpretation process.

The thing that distinguishes representation systems from other formal systems is that the formal structures which one builds in a representation system are meant to represent something. To the extent that a representation scheme is successful, it captures in its formal structure what the user thinks is the actual structure of the world being represented. Although one cannot in a formal system ever actually have the objects in the world being represented, it is useful in a model of the system (which is really what KRS is) to be able to talk about the relationships between the formal system and the "unknowable beyond" which is being represented. Therefore we have:

There is inherently nothing we can know about the structure of this level. It is interesting only in the fact that level 1 relates to it. All objects at level 0 are called things.

Level 1 is the level which most closely captures what one might think of as the "meaning" of a description system. One can think of it as the level formalizing the denotational semantics of descriptions and units etc. There are three fundamental kinds of objects at this level:

The term entity or conceptual entity we have used for some time, and is an abtract object which can represent anything at all. There is a special subset of all the possible entities called worlds, which are distinguished in the sense that they participate in a special way in the different types of belief.

Each entity at level 1 is said to represent a thing at level 0. The intuition is that for every thing of interest to the system builder, (s)he will create some entity, and then establish beliefs (see below) which relate that entity to other entities in a way which is felt to capture the structure of those things in the world being represented. Worlds therefore also represent things, but the intuition here is that they will represent the situation in which the thing participates or exists. However the actual interpretation (at level 0) of what it means to establish formally (at level 1) that an entity exists in a world is left open as a deep design choice for the person building a given system. No claim is being made that the structure of level 1 corresponds to the structure of the real world.

Beliefs are the relationships which connect entities. There are two kinds of belief, known as co-reference and mapping. Every description (see level 2 below) has a precise level 1 meaning which can be stated as some combination of co-references and mappings. These beliefs have the following structure:

A co-reference is a binary, symmetric relationship between two entities which is meant intuitively to mean that those two entities represent the same level 0 thing (the word co-representation would actually be more appropiate and we may shift to it).

A mapping on the other hand is a relationship consisting of a set of an arbitrary number of asymmetric pairs. Each pair consists of two entities, one called the instance entity and the other called the template entity. The concept of mapping is intuitively meant to capture our notion of abstraction; the fact that the relationship is a set of pairs rather than a single one is due to our perception of abstraction as being a structured rather than simple relationship, meaning that it is a relationship between concepts which connects the conceptual structure of those concepts, not simply the concepts viewed as un-structured wholes (see my thesis for more details).

Implications are the third level 1 object, and capture the fact that we see a conceptual description system as being an inherently active processor rather than being a statically declarative data base. There are implications which are "meant" by various structures in the whole system -- certain ones are implied by some of the beliefs, certain ones are inherent in the KRL-1 Interpreter, etc. Implications talk in terms of established beliefs and the appropriateness of establishing new entities and new beliefs (all the beliefs which exist in level 1, such as those which were talked about above, are said to be established).

The detailed semantics of implications is the area of KRS which still needs the most work (such as the precise meaning of appropriate) and therefore I won’t go into more depth regarding their structure. However there are two implications which are fundamental (see below for a technical defintion of this word) to KRS (actually maybe 3 -- I am not yet sure about whether mapping inheritance is fundamental):

If there are entities E1, E2, and E3, and there are co-reference beliefs connecting E1 and E2 and also connecting E2 and E3, then it would be appropriate to establish a co-reference belief connecting E1 and E3.

If there are entities E1 and E2, and there is a co-reference belief connecting E1 and E2, and furthermore there is a mapping M1 with E1 as an element of one of its pairs (either as an instance entity or as a template entity), then it would be appropriate to establish a mapping M2 which is derived from M1 by substituting E2 for E1 in all of its pairs.

In a sense, level 2 is the level which is what KRL-1 is all about: this is the level where one talks about descriptions and units and slots -- here we find the abstract objects which are pushed around by the interpreter -- and it is objects at this level that the level 1 objects are the meaning of. Level 2 is the level of the abstract objects which are primitive to KRL-1, as opposed either to their meaning (level 1) or their syntactic form (level 3). When you look at the sequence of characters "a Person with age = 10" and you say "that is a perspective", you are talking at level 2.

Because level 2 is the level at which the substance of the KRL-1 langauge has been designed, we use many words at this level, such as perspective, unit, specification, slot, etc., which are level 2 KRL-1 terms, rather than KRS terms. Section 4 (below) describes in more detail the relationship between KRS and KRL, but here I will simply present the fundamentals of level 2 as defined in KRS, and then show how the primitive level 2 KRL concepts are defined in terms of them.

An anchor is a structural position at level 2 with which is associated a level 1 entity. With every anchor is associated a unique entity, and with every entity is associated a unique anchor. An active description system will likely create new anchors during its reasoning processes -- which means that from a level 1 point of view a new entity has been created. An anchor does not itself say anything at all about the entity with which it is associated; that is, it does not itself convey any information at all -- it merely provides a structural "hook" so that you can say things about the entity using descriptions (below).

A description is a structural relationship at level 2 which connects anchors. Any given description system (like KRL-1) may specify any number of possible types of description, but each is constrained to have a unique and well-defined level 1 meaning (which is to say, it must specify exactly the co-references and mappings implied between the entities which are associated with the anchors to which it connects). Each description must also be attached to exactly one of the anchors to which it connects. The description is then said to have a referent which is the entity associated with the anchor to which the description is attached.

Anchors, descriptions, and description spaces constitute all of level 2 from the KRS point of view. KRL-1, on the other hand, defines a further set of terms for a particular set of descriptions and a particular set of anchors. For example:

A perspective (or a specification) is a description which connects to an even number of anchors (numbering at least 2). Its level 1 meaning is a mapping, with the entities associated with each of the anchors to which it connects being the elements of the mapping pairs. The anchors to which it connects are restricted in various ways (don’t worry if this doesn’t make much sense):

4. None of the anchors associated with the instance entities may be labelled, other than the one associated with the anchor to which the description is attached.

This characterization, even though virtually incomprehensible, is not even quite precise! The exact meaning of all the KRL-1 description and anchor types will be set forth, written in KRL-1, in the units for the semantics.

As well as restricting the types of possible description (except see section 3 below), KRL-1 also restricts the possible use of anchors. Specifically, it defines the notion of a labelled anchor, and also the concept of unit to be a collection of labelled anchors including one distinguished one called a unit anchor. It is also useful to define an anchor being embedded in a description when that description is connected to it but not attached to it. There are various further restrictions on anchors in KRL-1 such as:

2. No anchor may be embedded in more than one description, although it may have an arbitrary number attached to it. (Note that a system not allowing multiple description would restrict anchors to one embedded and one non-embedded.)

Note that level 2 is the default level at which we talk about descriptions and units: if I want to view a piece of KRL from level 3 I refer explicitly to the structure’s form; the level 1 viewpoint is usually referred to as the description’s meaning. If I want to discuss the level 0 object that corresponds to the piece of structure, I talk about the thing that the structure represents.

Level 3 is the syntactic level of language. It is here that names are meaningful, and that the legal syntactic forms of KRL-1 are defined. There are only two relevant concepts in KRS at this level:

I have not yet worked out the details of the structure of names and forms in the abstract, but the intuition is that a form is any describable lexical structure, and a name is the obvious lexical token. KRL-1 of course defines the forms of all its legal description and anchor types, as specified in the syntax document. The footnote is a KRL-1 level 3 mechanism which allows one to attach metaDescriptions to anchors and descriptions (the word "metaDescription" is itself a term from level 2 -- see section 3 below).

Note that it is only at level 3 that KRL-1 (or in fact any representation scheme) is accessible. A consequence of this is that it is really the structure of the KRL-1 syntactic forms which enables KRL-1 to implement restrictions on the possible use of anchors as described in the last section. Specifically, the syntax for units and slots uniquely determines which labels are anchors and which ones participate in units. Since there is no general facility provided for attaching metaDescriptions to unlabelled anchors, there is no way for a user to over-ride those restrictions.

Note also that functionals are purely a level 3 abbreviation mechanism. A consequence of this fact is that, since the level 2 objects are the ones in which the interpreter is in general interested, it can make no difference whatsoever in the behaviour of functions which deal with level 2 understandings of descriptions whether the description syntactically came from a functional or a full-blown specification or perspective. Functionals are a way of abbreviating descriptions: the further specification mechanism we are working on will likely be a level 3 abbreviation mechanism for anchors, and will correspondingly have a well-defined level 2 meaning which is equivalent to some longer syntactic form.

All of the discussion above has ignored perhaps one of the most interesting things about KRS/KRL-1 -- the concept of metaDescriptions. The description of level 2 of KRS above was incomplete in an important detail: with every description, anchor, or description space (i.e. with each level 2 object), one may uniquely associate another anchor called a metaAnchor. This metaAnchor is then said to be hooked to that level 2 object, and is just like any other anchor (for example it could have its own metaAnchor) except for the following restriction on the entity associated with it:

Thus the metaAnchor provides us with a fundamental way to shift the entire domain of description to the "model" or "KRS" level. By attaching descriptions to this metaAnchor we can then describe how the various levels relate, how we have described or represented various things, etc. There is of course a limit to this self-consciousness; there is no way a metaAnchor can describe the fact that it is hooked to an anchor or description without spawning another metaAnchor, leading to the obvious infinite regress.

Note that this meta-level shift is in an orthogonal direction to the sense of KRS levels. Since the metaHook is at level 2, it inherently gains primary access to the level 2 understanding of the description system it is modelling. However all of the objects which were previously part of each of the 4 KRS levels have suddenly become level 0 things at the metaLevel. (I need the obvious good picture here.) In the KRL-1 Interpreter there are standard ways to describe the various KRS levels and the ways in which they relate.

Most of this memo has dealt with the four ordered semantic levels of KRS. In section 3 I described a different orthogonal set of (possibly infinite) levels called metaDescription layers. There is one more hierarchy, complete with its set of technical terms, which needs to be explained.

In describing level 2 of KRS I distinguished terms which were defined as an inherent part of KRS from those which were part of KRL-1. This distinction can be made more precise by observing that the knowledge representation system we are building can be viewed in the following three layers:

1) KRS -- the underlying semantics, which we have just described. The adjective "fundamental" is used to describe terms, design choices, and mechanisms which are part of KRS.

2) KRL-1 -- the language. Many decisions as to which of the possible relationships etc. that could be constructed in KRS we want to make easy or possible are reflected in the design of the KRL-1 language. Included also is the syntax, including the ability to use footnotes to hook metaDescriptions. The adjective "primitive" is used to refer to concepts, design choices, and mechanisms which are inherent to the language but which are not fundamental to KRS.

3) The KRL-1 Interpreter. The particular interpreter which we are building brings along with it numerous design choices which are in no way inherent to the KRL-1 language, but which are deeply embedded within it, and which any program which uses the interpreter will make heavy use of. These include: protocols for procedural attachment; the taxonomy of system events; quantification mechanisms; the functions Seek, Match, and Describe; the notion of a primary anchor (a uniquely metaDescribed anchor for an equivalence class of co-referent entities); etc., etc. The adjective "standard" is used to refer to these mechanisms, which are not primitive to the language but upon which the interpreter is grounded.