Declarative Logic Programming. Michael Kifer
Читать онлайн книгу.
contrast, the object-logic approach, or OLOG, aims to extend the very logical foundations of logic programming to incorporate the notions of complex objects and classes not only at the level of syntax but also to make them first-class citizens in the semantics of the logic. A great number of approaches to OLOG have been proposed [Abiteboul and Grumbach 1987, Abiteboul and Kanellakis 1989, Aït-Kaci and Nasr 1986, Aït-Kaci and Podelski 1993, Beeri et al. 1991, Beeri et al. 1988, Chen and Warren 1989, Heuer and Sander 1989, Kifer and Wu 1989, Maier 1986a, McCabe 1992], where F-logic [Kifer and Lausen 1989, Kifer et al. 1995] is the best known and most developed—both in terms of theory and systems.
In OOP systems, an object is typically a container for data (facts) and rules. Some of the predicates may be exported to the outside world and can be invoked by other objects. Here is an example from Logtalk’s manual, which illustrates the idea.
The snippet above defines two classes, bird and penguin, where the latter is a subclass of the former. Bird exports the mode-predicate, which represents the modalities of birds’ movements. In general, this class would have many more predicates to represent the various properties of birds, but here we ignore those for the sake of clarity. The second class, penguin, modifies the transportation modalities for penguins by adding the mode swims, inheriting the mode walks, and blocking the inheritance of flies. The latter is achieved via the construct ^^mode(…), which calls the predicate mode in the immediate superclass of penguin (i.e., bird in our case).
In contrast to OOP approaches, OLOG approaches build on the idea of a complex object, which is mainly influenced by database practice. The theory of complex objects underwent rapid development in the 1980s, starting with the idea of Non-First-Normal-Form and Nested Relation data models and ending with a general and elegant data model for complex objects [Abiteboul and Beeri 1995, Bancilhon and Khoshafian 1989, Beeri 1989]. RDF [Lassila and Swick 1999] and JSON13 are largely reinventions of this earlier work and of the subsequent work on semi-structured data [Abiteboul et al. 2000]. Extending these theories to include logic rules proved harder, however, and some doubted that this goal was even possible given that object-oriented systems are inherently “pointer-based” and therefore non-logical [Ullman 1987].
One of the first important developments was the LOGIN language by Aït-Kaci and Nasr [1986]—later extended to LIFE [Aït-Kaci and Podelski 1993]—which included elements of functional programming. LOGIN gave the basic idea of how a simple logical syntax for logic object-oriented databases could be constructed, but both LOGIN and LIFE were largely constraint languages with semantics that was at odds with database query languages. This limitation led Maier [1986a] to propose elements of a semantics that was “right for databases,” and this semantics, in turn, inspired the work on O-logic by Kifer and Wu [1989], Kifer and Wu [1993]—the first coherent exposition of an OLOG approach that was completely logical and fully compatible with the logical foundations of both databases and logic programming. F-logic, which culminated this line of work, was developed shortly thereafter [Kifer and Lausen 1989, Kifer et al. 1995].
The first F-logic system was FLORID [Frohn et al. 1998], but it is no longer being maintained. The open-source Flora-2 system [Kifer 2015, Yang et al. 2003] is both well maintained and has a community of users. There also are two commercial versions: Ontobroker from Semafora, GmbH [1999] and Ergo from [Coherent Knowledge LLC 2017]. The latter is based on Flora-2, but includes many additional language constructs, connectivity to the outside world, optimizations, a development environment, and knowledge-acquisition tools.
The basic language constructs in F-logic are the subclass and membership relations as well as the frame representation (whence the “F” in F-logic). For instance, bird123:Penguin means that an object with the particular Id bird123 belongs to class Penguin. The statement Penguin::Bird means that the class Penguin is a subclass of the class Bird and Bird is a superclass of Penguin. (F-logic-based systems treat upper-case symbols just like the lower-case ones—as constants; variables are prefixed with the “?” sign instead.) Frames14 specify properties of objects, as in
This example extends the earlier one used to illustrate Logtalk, using Flora-2 syntax rather than the original F-logic syntax [Kifer et al. 1995].
The Bird[|…|] construct (and the like) is a frame that represents the default values attached to classes and inherited by subclasses and the members of the classes. (The symbol -> means “has value” and [|…|] means the value is a default one. Thus, the first statement above means that, in any object in class Bird, the default value for the attributes limb(wing) and limb(leg) is 2 and the default values for mode are flies and walks.) These default values can be overwritten. In terms of Java, these properties correspond to instance methods. Thus, the first statement above says that normally birds have two legs and wings, and their modalities of movement are flying and walking. Note that limb is a parameterized property, which can be thought of as a method that takes arguments. We already discussed the second statement, which says that penguins are birds, and the third statement explicitly says that penguins swim. This explicit statement overrides the inheritance of the movement modality from Bird. However, we do not want to completely discard the information about birds’ movement modalities—we just want to drop the flying modality. The fourth rule does so, stating that, in addition to swimming, any movement mode of a bird—except flying—is also a valid modality for a penguin.
The fifth statement is another frame: one that provides information about a particular bird with object ID bird123. First, it says that this object is a penguin. In addition, it says that this bird is (apparently a pet) named “Tweety”, and it is a one-legged creature. To indicate this situation, we use the bird123[…] construct, which provides information about a particular object instance, rather than default information about all objects in a class.15 Tweety will inherit some of the information from Bird, some from Penguin, and some of that information will be overridden. Specifically, the mode information for birds will be overridden by the more specific Penguin information, so bird123 will get the modalities of walking and swimming, but not flying. Tweety will also inherit the property of being biwinged, but the property of having two legs is overridden by the explicit statement that this bird has only one leg.
There is more to the story, however. The last rule brings in an aspect of defeasibility, which is much more flexible and powerful than inheritance overriding. It says that birds with fewer than two legs do not walk. Thus there will be two contradictory inferred facts: that Tweety both walks and does not, and the result is that each of these facts defeats the other, so none of these conflicting derived facts will hold. We refer the reader to Wan et al. [2009] and the Flora-2 manual for the details of the logical semantics for defeasible reasoning in that system.
In conclusion, we note that Flora-2 and Ergo go well beyond F-logic. Besides defeasibility, they support other important aspects of Datalog discussed in this chapter, including HiLog (Section 1.4.7), Transaction Logic (Section 1.4.8), modularity, some aspects of functional programming, and more. We should also mention that F-logic frames are closely related to semi-structured data [Abiteboul et al. 2000]. This relationship was gainfully employed in FLORID [Frohn et al. 1998], which uses F-logic to query semi-structured data, and WebLog [Lakshmanan et al. 1996], which uses an F-logic-like language for querying Web data.
1.4.7 Higher-Order Extensions
Since the early days of Prolog, users felt constrained by the inability to query the meta-structure of logic programs. Since Datalog is a subset