**Mail folder:**Interlingua Mail**Next message:**John McCarthy: "More about contexts"**Previous message:**Michael R. Genesereth: "kif doc"**Reply:**John McCarthy: "More about contexts"

Message-id: <199209300208.AA01752@venera.isi.edu> Date: Tue, 29 Sep 92 22:03:11 EDT From: sowa@watson.ibm.com To: SRKB@ISI.EDU, INTERLINGUA@ISI.EDU, CG@CS.UMN.EDU Subject: More about contexts

During the past few months, Pat Hayes and I have been carrying on an open email debate about contexts, their formalization in logic, and their desirability in KIF and related languages. In my work on the IRDS conceptual schema, I have been using contexts as a mechanism for representing encapsulation in object-oriented programming languages. Partly as a result of that work, I have become even more firmly convinced that contexts are a valuable mechanism that should be seriously considered for the knowledge sharing effort. As Pat and I have agreed in past email notes, the notion of "context" in the literature has been rather confused, with many different ideas bundled up in a single term. There are three distinct concepts that must be distinguished: 1. A packaging mechanism for enclosing a collection of formulas and allowing them to be named and referenced as a single unit. 2. The contents of that package, which could be called anything from "quoted formula" to "microtheory". 3. The permissible operations on the formulas in the package. These operations could be defined by a set of axioms in a larger package that encloses the one under discussion. Whenever I use the word "context", I mean only the packaging mechanism. In my Conceptual Structures book, I defined a context to be a concept box that contains a collection of nested conceptual graphs in its referent field. In effect, the box behaves like a Lisp QUOTE, and the relations attached to the box determine how the nested graphs are used. According to this view, a context is a very lightweight construct with little more semantics than a Lisp QUOTE plus an assignment. The power of the construct comes from what you do inside and outside the package. Inside a context box, you can insert any number of formulas that define an arbitrarily rich theory; outside the box, you can state any number of other axioms (actually, metalanguage axioms) that make assertions about the context and how the formulas inside it can interact. In effect, the formulas outside the box define the rules of inference for the theory stated by the formulas inside the box. Besides making statements about the formulas inside a box, you must be able to attach relations to the box itself to make the following kinds of assertions: 1. "The conjunction of the formulas in this box is false." 2. "The formulas in this box describe a possible state of affairs." 3. "Mary believes the propositions stated by the formulas in this box." 4. "The formulas in this box interact according to the axioms contained in the box named S5." 5. "The formulas in this box were true during the time interval [t1,t2]." 6. "Any formula placed in this box must be in Horn-clause form." The ability to say things like this gives you an immense amount of power. If used in an undisciplined way, that power could get you into trouble by letting you say things that are inefficient, undecidable, or inconsistent. But it also gives you the power to state and enforce whatever discipline you like. For example, you could package a theory T in a context C and say that the rules of inference for T are in another package S4 or S5. If we adopt such a mechanism as a basis for knowledge sharing, there are several issues that must be addressed: 1. Can you develop a coherent model theory for such a system of nested contexts? How do you ensure that the system is consistent and the reasoning mechanisms sound? 2. Since the context mechanism itself has so little semantics, the real crux of the issue lies in what you do with the contexts. How can you keep people from getting into trouble by using contexts in weird and wonderful, but totally undisciplined ways? 3. If you want to share knowledge between different systems, it is easy to map from a more restricted theory to a more general one. But in general, it may be impossible to map backwards from a general one to a more restricted one. How can you ensure that translation is possible? Or at least determine when it is possible or impossible? To answer the first question, construct a quasi-first-order model consisting of a union of conventional models with primitive objects and metamodels whose objects correspond to the linguistic elements that talk about primitive objects. Build it up recursively: a) For any context containing only first-order formulas, a model for the universe of discourse (UoD) can be constructed in the usual way from a set S of basic objects and relations R over them. b) For any context C whose formulas talk about a universe of discourse U, construct an extended UoD for C, which consists of the union of U and the language L in which the formulas in C are stated. The language L is defined in the usual way as the set of all grammatical statements derivable by some suitable grammar. c) For any context C that contains nested contexts C1,...,Cn, let the UoD of C be the union of the extended UoD's of C1 through Cn plus the set of contexts {C1,...,Cn} themselves. Then the formulas in C can refer to the nested contexts, the languages of those contexts, the primitive objects, or the way that any of these things relate to one another. Note that the language of each context has a first-order structure. The universe of discourse of each context becomes larger and larger as you go outward, but if the primitive UoD is countable, all the extended UoD's and their unions remain countable. This structure gives you the power to state any definitions or make any metalinguistic statements you like, but none of the quantifiers in any of the metalevels range over uncountable sets, as in the usual higher-order logics. That means that at any level, you need nothing more powerful than first-order proof procedures. If you prefer, you can restrict your languages to a more efficient subset, such as Horn clauses or whatever. That is effectively what people do when they write a Prolog interpreter in Prolog, for example. In that case, Prolog becomes the metalanguage that talks about the nested language, which happens to have exactly the same syntax. Prolog programmers have found this to be a very useful technique, and the context mechanism is a generalization of that approach. Re consistency: There are two distinct issues: consistency of the framework itself vs. consistency of whatever formulas anyone might choose to insert in any context. To show consistency of the framework, it is sufficient to construct one instance (example below). Consistency of what people put in the contexts, however, is the responsibility of the user. Any practical programming language has to be powerful enough to let people get hung up in a loop, and any practical reasoning system has to be powerful enough to let people say things that are inconsistent. The responsibility of the framework designer is to ensure that the framework itself is consistent and that people who want to enforce appropriate disciplines are given mechanisms for doing so. Re discipline: Building a knowledge base is something that a domain expert should be able to do. But designing a metalanguage with rules of inference that support disciplined knowledge engineering techniques is a sophisticated task that would probably be left to professional system designers. The context mechanism provides a clean way of separating the two tasks. Following are some metalinguistic frameworks that system designers might implement for the users: 1. File system: The simplest use of contexts is for packaging formulas, naming the packages, and retrieving them upon request. The only metarule that would affect the reasoning methods would be one that says that any formula could be moved in or out of any package at any time. This rule has the effect of making the context structure transparent to the theorem prover; i.e. all the formulas interact as though they were in a single global space. Since this simple example is consistent, it shows that the framework of nested contexts by itself does not lead to inconsistencies (although people are free to put inconsistent combinations of formulas in the contexts, if they choose to do so). 2. Modality: If you divide a knowledge base K into two contexts, a set of laws L and a set of contingent facts F, you can define necessity as provability from L and possibility as consistency with L. These definitions satisfy the usual axioms for the modal operators. They also give you a convenient way of formalizing conventional database systems: the context F consists of all the data stored in the database, and the context L consists of the integrity constraints on that data. 3. Limiting expressive power: The various systems that limit expressive power for the purpose of improving efficiency can be organized in a hierarchy. Let A and B be names of contexts that define the rules of inference for two different systems. Then you can define A < B to mean that every rule of inference in A is a rule or derived rule in B and that every statement form that is supported by A is also supported by B. For example, B could be classical FOL, and A could be some terminological language or Horn-clause language. Then when two knowledge bases share knowledge, they would have to specify which rules they were operating under. You could always export from a system that operates under the rules A to a system that operates under B. You could also allow limited export from B to A, provided that any message m sent from B to A was first checked to see whether m used only the syntactic forms permissible by the rules of A. 4. Hybrid systems: Many systems have collections of knowledge of different kinds. A deductive database system, for example, might have three different collections of knowledge: a) A very large conventional database where no fact requires anything more complex than ground-level atoms. Let the rules in context GL define the subset of logic that is equivalent to the database. b) A set of integrity constraints expressed in full FOL. Note: It is possible to check any FOL constraint against a set of ground level atoms in at most polynomial time. Such checks can be stated in SQL and executed by a standard query processor. c) A deductive component that uses Prolog-like Horn clauses (context HC) to draw inferences from database in GL form. Since the expressive powers of these three versions of logic are ordered GL < HC < FOL, anything in expressible by GL could be exported to a knowledge base using HC for inference a knowledge base using FOL for integrity checks. After a deduction is performed by HC, any conclusion that uses only the ground-level GL form could be sent back to the database, even though the more general HC or FOL forms could not be stated in GL. Checking whether a conclusion can be exported in a more restricted form is a purely syntactic test that can be done in linear time. For knowledge sharing, any systems that communicate would have to agree on a standard context that contains the metalanguage that defines the subset of logic that they are using for communication. That subset could be identical to the subset that they use for reasoning, or it might be a more restricted subset. In summary, the context mechanism provides an enormous amount of power for a small investment. Furthermore, it also provides a way of enforcing any kind of discipline needed to restrict that power. And most importantly, it can simulate many different kinds of protocols within a common framework: conventional database systems, deductive databases, terminological systems, object-oriented systems, and many others. John Sowa