Page Numbers: Yes First Page: 1
Heading:
April 26, 1979 7:56 PM[IVY]<KRL>document>rep-worlds-during
? Worlds and the contingency descriptor
In order to explain the KRL-1 worlds mechanisms, it seems useful to distinguish between two different notions of "world" which have been mixed up in many discussions of AI languages. The notion which is at the basis of the KRL-1 mechanism is different from the one which forms the basis for the AI languages such as Planner, Conniver, QA4, and as I currently understand it, the use of vistas in partitioned semantic networks. The two views can be labelled domain worlds vs. knowledge worlds, loosely defined as:
In the domain based notion, a world is something whose identity is based in the domain being talked about by the system. The world of all things which are believed to hold independent of time is a "world" which can be contrasted to the world of things whose truth is believed to change over time (e.g. The fact that someone is a person, vs. the fact that their age is 18). The world of things which must be the case if the letter E has the value 8 (in cryptarithmetic) has a well defined relationship to the world of things which must be true independently of that assignment. This notion of worlds is the closest to the "situation variables" used in logical axiomatization of changes over time (e.g. McCarthy and Hayes). The question as to whether a certain belief holds in a given world is not reducible to the question of whether it is stored in the data base.
In the knowledge based notion, a world (or vista, or context) is an explicit collection of knowledge structures (assertions, network links and nodes, etc.). There is a correspondence set up between these worlds, and some domain-based entities (e.g. moments in time), but the question of what is "in a world" is really a question about what is stored in the specific collection of knowledge strucures.
These two notions support different kinds of inheritance, and I believe that much of our confusion about worlds in KRL-0 came from the fact that we all tend to think in the knowledge-world style (due to experience with the systems that use it, and with computer science notions of context) while in fact KRL is much more suited to domain-worlds.
The domain-world version of inheritance is based on the logical connection between the worlds. If a specific memory structure represents a belief which holds in the world of "unchanging things", then it can be inherited to be used by an inference which is reasoning about the world of "things that are true today" or "things that were true yesterday". If a belief holds in the world in which hypothesis A is assumed, then it can be inherited into the world in which both hypotheses A and B are assumed. The inheritance link can be paraphrased as "anything which is believed in the parent world can be believed in the child world". Notice that this is completely independent of whether the beliefs are stored, inferred, or whatever.
The knowledge-world version of inheritance is based on control of access to knowledge structures. If an assertion appears in the context for "things that are true today", then access is not made to a matching (or contradictory) assertion in "things that were true yesterday". On the other hand, if there is no relevant assertion in the child context, then the system accesses the corresponding one in the parent context. The inheritance link can be paraphrased "anything which is believed in the parent world, and which is not explicitly over-ridden in the child world can be believed in the child world".
The knowledge-world inheritance depends heavily on being able to have a clear and consistent definition of information being "explicitly over-ridden". This involves two commitments: assuming that the system has immediate access to all the places in which the over-riding information could be stored (done through careful design of the context mechanism for this purpose), and assuming that there is a full update of the description in going from one context to the next (so that anything which hasn’t been explicitly changed can be trusted when inherited). These both go against basic design principles of KRL. The first forces a memory structuring of knowledge which forces decisions about accessibility which are completely orthogonal to all of our notions of the importance of differential accessibility, redundancy, etc. in memory structures. The second makes the system useful only to the extent that we are dealing with full (rather than partial) knowledge of the worlds being described. Systems of the knowledge-world type cannot be used to do reasoning about sequences of hypothetical events for which only partial descriptions are available. They are generally useful only for keeping track of an actual ongoing situation (or a corresponding total simulation). However, as experience shows, they are extremely convenient for those special cases.
In KRL-1, there are two components to the world mechanism, one of which is based on domain-world inheritance, which by its nature is simple, and the other of which is a zeroth-order version of knowledge-world inheritance, which we believe handles the great majority of things people want to do with it. These can be intermixed, as explained below.
?.? The domain-world mechanism
One of the interpreted descriptors in KRL-1 corresponds closely to the contingency descriptor of KRL-0. The functional form During(worldDesc, objectDesc) can appear in any anchor with the following meaning:
If this descriptor appears in the pattern of an Align, then the AlignDescriptor goal associated with it is given a subgoal which is an AlignAnchor goal, in which the pattern anchor is that of the second argument (the objectDesc), and which has an associated world description of the first argument (worldDesc). World descriptions are inherited directly by subgoals.
If an AlignAnchor goal has an associated world description, then the effective description against which it is aligned is initially created by taking only those descriptors from the structural anchor which are "compatible" with that world, and additional descriptors added by extension must also be compatible. Each entry for a descriptor brought into an effective description is marked for the world initially associated with it.
A descriptor is compatible with a world description if either:
It is not a contingency, and the default world (the unmarked one) is compabtible with the world description
It is a contingency, and the function (CompatibleWorld sought found) (which the user can define) returns Non-NIL. In this case it is the objectDesc, rather than the whole contingency that is added to the effective description.
Actions which involve modifying structure which appear inside a contingency in the pattern are handled as with any modification (i.e. the addition of structure starts from the furthest embedded existing structural grounding) with the following addition:
If the structural grounding is in an anchor with the same world as the pattern world, the modification is made directly
If the structural grounding is an anchor for a compatible world, then the modification is made inside a contingency added to that anchor for the pattern world. In the case of set and sequence modifications, this means copying the previous structure and modifying the copy.
All of this is under the control of signals. The simple forms of Align do not do them. The structural match treats contingencies like any other map descriptors -- looking for exact corresponding structures. The simple match table (and the corresponding access compiled code) ??should this be like the structural one, or simply refuse to use worlds -- note that the simple current-world stuff doesn’t use these.
In all of this, no commitment is made to how it will be determined if one world is compatible with another. It is expected that users will make use of the primitive tree mechanism as one simple way of linking worlds (along with using coReference descriptors as the world description argument of a contingency). should this be something which is checked for initially, before going to a function call?
?.? The current-world mechanism
One of the major attractions of the knowledge-world scheme is that within a single world (context), there is no need to distinguish between things which are always true and those which are just true at the moment. Both are included directly, with the expectation that those which are only true at the moment will be explicitly over-ridden in any other context which inherits from this one. The most important use of this is in maintaining a knowledge base of "current" information integrated smoothly into the base of "permanent" information. The context trees (and corresponding commitments as described above) of the AI languages are needed in cases where it is necessary to maintain more than one current state -- either for use in backtracking or for making explicit comparisons. Our feeling is that neither of these is really necessary (or necessarily good). For arguments against global backtracking, see anything Sussman has written since MicroPlanner. For comparing states, the context tree solution is good only in those cases where the knowledge of each state is complete rather than partial, and it is not at all clear that there are many useful cases of this. The current world mechanism in KRL-1 is designed to make it easy to maintain a single current state for any domain-based world (including the default one) with the expectation that more complex interdependencies will be handled with explicit cross-links (meta-descriptions).
Associated with any world (defined in the domain-based sense) there is another world called its current world. There are two interpreted descriptors, using the functionals Currently(objectDesc), and Always(objectDesc), which can appear in any anchors. They are treated like contingencies (as described above), where the world associated with the objectDesc is the current world (for Currently) or permanent one (for Always) corresonding to the world associated with the anchor in which the descriptor appeared. If this were all that was provided, then the equivalent effect could be achieved with the other mechanism, with the two worlds linked (parent being the permanent world, child the current one) and the two functionals replaced with contingencies naming the worlds. However, there are some important differences:
The matcher keeps track of whether the world associated with an anchor is current or permanent, and uses different signals for the addition of new information -- in most signal tables, for example, the response to an AddingConflictingPost in a current world would be to delete the old one, while in a non-current world, more drastic action needs to be taken.
It is possible to declare (with the meta-description A CurrentValue on a slot of a prototype unit) that all fillers of pairs for that slot are to be treated as current values. This means that in the great majority of cases, the fact that a description is current will not appear explicitly. For example, if the age slot in Person is declared a current value, then the following two descriptors are equivalent:
\A Person with lastName = "Doe" age = 17/
\A Person with lastName = "Doe" age = Currently(17)/
It would also be possible to have the descriptor:
\A Person with lastName = Currently("Doe") age = 17/
Which uses an explicit Currently in a slot not declared that way.
When aligning, it is assumed (unless marked explicitly otherwise in the pattern by Always) that current descriptors (along with permanent ones) are to be used. However in defining the Same-world test, it is possible to distinguish, so that one world can inherit the permanent descriptions from another without its current ones.
The structural match, insists on real identity of structures as usual. The simple (access compiled) match does not allow contingencies (or Currently or Always) in the pattern. In going through the datum it eliminates them -- i.e. a description embedded in a Currently or an Always is treated as through it appeared directly in the anchor where the functional appeared.