Declarative Logic Programming. Michael Kifer
Чтение книги онлайн.
Читать онлайн книгу Declarative Logic Programming - Michael Kifer страница 15
Название: Declarative Logic Programming
Автор: Michael Kifer
Издательство: Ingram
Жанр: Компьютеры: прочее
Серия: ACM Books
isbn: 9781970001983
isbn:
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 of Prolog, it inherits this limitation. For instance, we have already defined several binary predicates, such as advised, adjacent, and related. How can one find out in which relationships lvk and ks stand to each other? We could ask series of queries
This approach is hardly satisfactory: If additional relations are defined later on, more queries need to be added. It would be nice if we could just ask a single query
(R being a variable) and get an answer related(lvk, ks) (that is, R = related). One of the first logic programmers to pay attention to this issue was D. H. D. Warren [1982a], who proposed a programming style (or, one can say, an encoding scheme) that allows treating predicates as first-class objects. The idea is, roughly, to introduce a new predicate, say binary_property/3, and then represent information about the aforesaid predicates as
In this approach, we still cannot ask ?– R(lvk, ks), but we can write instead:
which, although awkward, does the job. This approach is essentially an adaptation of the well-known technique from formal AI, which prescribes a single predicate, true (or holds) and “downgrades” predicates to the level of data (for example, true(advised(X,Y)) or, closer to Warren’s style, true(advised,X,Y)).
The problem of awkwardness and other limitations of Warren’s proposal are overcome by HiLog [Chen et al. 1989b, Chen et al. 1989a, Chen et al. 1993], which is a full-blown logic that admits variables over predicates, function symbols and more. While HiLog has a higher-order syntax, its semantics is first-order. As a result, it provides a convenient higher-order syntax and yet computationally it is not more expensive than Prolog.
For instance, the aforesaid query ?– R(lvk, ks), which has a variable in the predicate position, is syntactically correct and has the expected semantics. More interestingly, HiLog supports parameterized predicates, which can significantly simplify working with Datalog and make rules more generic. To understand this idea, suppose we have various binary relations, such as parent, edge, and direct_flight. In all of these cases, transitive closure creates a new, meaningful, and commonly used concept. For instance, by closing parent transitively, we get the concept of an ancestor—also a binary relation. Similarly, the transitive closure of edge gives us the concept of a path in a graph; the transitive closure of direct_flight is also a meaningful concept—the ability to travel between cities by air with stops in-between. In Datalog and in Prolog, one would have to write three different rule sets to define these different closures. Here is one such a set for parent:
For edge, the rules would be similar except that the names of the predicates would change. To make such rules generic, it is not enough to just put variables in place of the predicates: one also needs to be able to construct new names for relations because if parent were replaced by edge, then ancestor would need to be changed to some other name that depends on the underlying predicate. Here is a solution to the problem in HiLog:
Here Pred is a variable that can be bound to parent, edge, or direct_flight. If, say, Pred is bound to direct_flight, then the rules above define the relation closure(direct_flight). If Pred is bound to edge then these rules define closure(edge). Details can be found in Chen et al. [1993].
HiLog is available in a number of systems. First, it is supported in XSB, but its usability there is limited because it is not integrated with XSB’s module system. HiLog is fully supported by and is extensively used in the Flora-2 system [Kifer 2015, Yang et al. 2003] and in its commercial cousin, the Ergo reasoner [Coherent Knowledge LLC 2017].
We mention another important extension in this area, Lambda Prolog [Miller and Nadathur 1986]. Like HiLog, Lambda Prolog supports second-order syntax. However, unlike HiLog, it is semantically a second-order logic. As a result, Lambda Prolog has a much greater expressive power than HiLog, but it is also more expensive computationally.
1.4.8 Datalog and Updates
The need to endow logic-based declarative languages with an ability to change the state of the underlying database has been recognized early on, and both Prolog and SQL—the two earliest and most prominent such languages—have the facilities to do so. The trouble is that neither facility was wholly satisfactory. In Prolog, database updates are performed via assert and retract, “predicates” with side effects. In SQL one uses INSERT, DELETE, and UPDATE statements. We put the term “predicates” inside the quotes because neither assert nor retract are predicates in that they do not state or test any kind of a truth-valued statement. Instead, they perform extra-logical operations of inserting or deleting information, and their semantics can be explained only procedurally and non-logically, hence not declaratively. In SQL, the situation is similar, but, realizing the theoretical difficulty of integrating update operators into a declarative language, the designers relegated these operators to a separate sublanguage. Then, to put everything together, they came up with a host of less than ideally designed procedural languages for so-called stored procedures, completely abandoning any pretense of declarativeness.
This state of affairs has been deemed unsatisfactory by a long list of researchers and practitioners leading to an equally long list of proposed fixes. Few have gained traction, however. Bonner and Kifer give a comprehensive survey of many of these proposals [Bonner and Kifer 1998a]. In this section, we review some of the approaches from that earlier survey and also cover some newer proposals. In addition, we will try to classify the different approaches along several dimensions.
The approaches to updates in logic languages can be roughly classified into two broad categories: explicit state identifiers and destructive updates. The latter are further subdivided into updates in the rule heads and updates in the rule bodies. There are also approaches based on other logics, such as dynamic logic [Harel 1979] and process logic [Harel et al. 1982], which we do not cover here, but they are covered in the survey cited above.
What features should one expect or want from integrating an update capability into a logic language, beyond the basic modification of data? The following desiderata are the most important features, in our view, and they will serve as additional classification dimensions for the different proposals.
1. Declarative semantics. This requirement roughly means that one would like the integration to be as smooth as possible and be declarative. Prolog and SQL clearly fail soundly on this score.
2. Subroutines, compositionality. Every programming СКАЧАТЬ