Implementation of subset logic languages
Kyonghee Moon · 1997
The main focus of this dissertation is the design and implementation of a declarative language with powerful set processing capabilities. The underlying thesis of our work is that an efficient sequential implementation of a set-oriented declarative language is possible with static program analyses and run-time optimizations. Towards that end, we developed implementation techniques for a comprehensive paradigm embodying sets called subset-logic programming. An example of such a paradigm is the language SuRE (for Subsets, Relations, and Equations), which combines features from functional and logic programming languages, and is also well-suited to problems in deductive databases. By formulating a set-valed function through subset clauses, one gains the flexibilities of operation on the resulting set in different ways: eagerly, incrementally, or lazily. Subset clauses and, more generally, partial-order clauses help render clear and efficient formulations to problems requiring grouping operations, transitive closures, and monotonic aggregation in deductive databases. Like other logic programming languages, the implementation of SuRE is based upon and extends the Warren Abstract Machine (WAM)(War83). The presence of sets and the subset clause require a new control strategy for their implementation. Solving circular subset constraints requires monotonic memo-tables. This form of memoization goes beyond the usual form of memoization in functional and logic programming languages. When circular function calls depend upon one another through subset-monotonic functions, these calls have to be re-executed until their least/greatest fixed point is reached. This in turn requires memo-table entries to be monotonically updated. Another novel features of subset-logic programming is lazy evaluation, which, unlike that in traditional functional languages, actually involves lazy exploration of a resolution search-tree. The presence of sets requires the standard matching and unification operations to be generalized to set-matching and set-unification, which causes more branching than as in Prolog. We examined a few static analysis techniques for subset clauses in order to improve the performance of SuRE programs and their respective experimental results were presented. We showed that the overhead of memoization in subset-logic programs is minimal, and the use of monotonic memo-tables to implement dynamic programming algorithm can be a more efficient way than using pure memo-tables.