| CICLOPS 2006 | Colloquium on Implementation of Constraint Logic Programming Systems Seattle, August 21, 2006 |
CICLOPS on Monday, August 21st
Invited Tutorial (09:30‑10:30)
| 09:30‑10:30 | Neng-Fa Zhou
(City Univerity of New York at Brooklyn College and Graduate Center) AR (Action Rules): The Language, Implementation, and Applications [ppt] AR is a rule-based event-driven language designed for programming interactions needed in such applications as propagation-based constraint solvers and graphical user interfaces. AR is a result of evolution from delay constructs in early logic programming systems and it supports events on domain variables available in several constraint programming systems for programming constraint propagators. AR is compiled into a spaghetti-stack machine which facilitates fast switching of subgoals between suspended and active states. This architecture has been shown to be vital for the high performance of the finite-domain constraint solver and the CHR (Constraint Handling Rules) compiler in B-Prolog. This tutorial is based on the following papers: 1. Neng-Fa Zhou: Programming Finite-Domain Constraint Propagators in Action Rules, 25 pages, to appear in Theory and Practice of Logic Programming, 2006. 2. Neng-Fa Zhou, Mark.Wallace, and Peter J. Stuckey: The dom Event and its Use in Implementing Constraint Propagators, 18 pages, Technical Report, CUNY Compuer Science, 2006. 3. Tom Schrijvers, Neng-Fa Zhou, and Bart Demoen: Translating Constraint Handling Rules into Action Rules, 15 pages, CHR'06. 4. Neng-Fa Zhou: A Constraint-based Graphics Library for B-Prolog, Software - Practice and Experience, Vol. 33, No.13, pp.1199-1216, 2003. |
Break (10:30‑11:00)
Session 1 (11:00‑12:30)
| 11:00‑11:30 | Ricardo Rocha
(DCC-FC & LIACC, University of Porto) Efficient Support for Incomplete and Complete Tables in the YapTab Tabling System Most of the recent proposals in tabling technology were designed as a means to improve some practical deficiencies of current tabling execution models. The discussion we address in this paper was also motivated by practical deficiencies we encountered, in particular, when dealing with incomplete and complete tables. Incomplete tables became a problem when, as a result of a pruning operation, the computational state of a tabled subgoal is removed from the execution stacks before being completed. On the other hand, complete tables became a problem when the system runs out of memory. To handle incomplete tables, we propose an approach that avoids re-computation when the already stored answers are enough to evaluate a repeated call. To handle complete tables, we propose a memory management strategy that automatically recovers space from the tables when the system runs out of memory. To validate our proposals, we have implemented them in the YapTab tabling system as an elegant extension of the original design. |
| 11:30‑12:00 | Remko Troncon
(K.U.Leuven -- Dept. of Computer Science) Bart Demoen Gerda Janssens When tabling does not work Tabled execution has been successfully applied in various domains such as program analysis, model checking, parsing, ... A recent target of tabling is the optimization of Inductive Logic Programming. Due to the iterative nature of ILP algorithms, queries evaluated by these algorithms typically show a lot of similarity. To avoid repeated execution of identical parts of queries, answers to the queries can be tabled and reused in later steps of the algorithm, thus avoiding redundancy. In this paper, we make a qualitative evaluation of this application of tabling, and compare it with query packs, a special execution mechanism for sets of similar queries. We show that the memory overhead introduced by tabling not only scales poorly in this context, but that query pack execution also avoids more predicate calls for more complex problems. |
| 12:00‑12:30 | Hai-Feng Guo
(University of Nebraska at Omaha) Miao Liu (University of Nebraska at Omaha) Embedding Solution Preferences via Transformation Preference logic programming (PLP) is an extension of constraint logic programming for declaratively specifying problems requiring optimization or comparison and selection among alternative solutions to a query. PLP essentially separates the programming of a problem itself from the criteria specification of its optimal solution. The main challenge to implement a PLP system is that how the defined solution preferences take effects automatically on pruning suboptimal solutions and their dependents during the computation. The solution preferences are specified at the Prolog programming level, whereas the answer collection is implemented at the system level. In this paper, we present a novel strategy to bridge the programming gap by introducing a new built-in predicate, which serves as the interface between the specification and the actual application of solution criteria. With this interface predicate, we can easily transform a preference logic program into an executable program, where solution preferences can be propagated into recursion so that selecting an optimal solution to a problem only depends on the optimal solutions to its subproblems. The strategy has been successfully implemented on a tabled Prolog system; and experimental results are also presented. |
Lunch break (12:30‑14:00)
Session 2 (14:00‑15:30)
| 14:00‑14:30 | Bart Demoen
(K.U.Leuven) Phuong-Lan Nguyen (UCO, Angers) Delay and events in the TOAM and the WAM B-Prolog uses the TOAM abstract machine. Its implementation of delayed goals is by means of suspension frames on the execution stack. The traditional WAM approach - partly established by {\mbox SICStus} Prolog implementors - is to put suspension terms on the heap. % Ten years ago, published experiments comparing the two {\mbox approaches/systems} indicated a clear edge for B-Prolog, but it has never been clear whether the TOAM really offers a fundamental advantage over the WAM. We first redo the old experiments. We show to what extent the ten year old conclusions still hold. We offer a better explanation of the benchmark results. % We use hProlog (a WAM-based Prolog implementation) to show that the traditional WAM approach to freeze/2 can be competitive to the TOAM approach. We do the same for the event mechanism of B-Prolog. |
| 14:30‑15:00 | Tiago Soares
(DCC-FC & LIACC, University of Porto) Michel Ferreira (DCC-FC & LIACC, University of Porto) Ricardo Rocha (DCC-FC & LIACC, University of Porto) Nuno Fonseca (DCC-FC & LIACC, University of Porto) On Applying Deductive Databases to Inductive Logic Programming: a Performance Study Inductive Logic Programming (ILP) tries to derive an intensional representation of data (a theory) from its extensional one, which includes positive and negative examples, as well as facts from a background knowledge. This data is primarily available from relational databases, and has to be converted to Prolog facts in order to be used by most ILP systems. Because of the dimension of these datasets and the associated search space that the ILP system has to explore, these system can take hours or days to derive a theory. Furthermore, the operations involved in ILP execution are also very database oriented, including selections, joins and aggregations. We thus argue that the Prolog implementation of ILP systems can profit from a hybrid execution between a logic system a relational database system, that can be obtained by using a coupled deductive database system. This hybrid execution is completely transparent for the Prolog programmer, with the deductive database system abstracting all the Prolog to relational algebra translation. In this paper we propose several approaches of coding ILP algorithms using deductive databases technology, with different distributions of work between the logic system and the database system. We perform an in-depth evaluation of the different approaches on a set of real-size problems. For large problems we are able to obtain speedups of more than 100 times. The size of the problems that can be approached by the ILP system is also significantly improved, thanks to a non-memory storage of datasets. |
| 15:00‑15:30 | Quan Phan
(DTAI group, Computer Science Dept., Katholieke Universiteit Leuven) Gerda Janssens (DTAI group, Computer Science Dept., Katholieke Universiteit Leuven) Towards Region-based Memory Management for Mercury Programs Region-based memory management is a form of compile-time memory management, well-known from the functional programming world. This paper describes region-based memory management for the Mercury language using a points-to graph that models regions and distributes values of program variables over regions. First, a region analysis determines the different regions in the program. Second, the liveness of the regions is computed. Finally, a program transformation adds region annotations to the program for region support. Our approach obtains good results for a restricted set of deterministic Mercury programs and is a valid starting point to make region-based memory management work with general Mercury programs. Our method can be extended with region instructions to support programs with modules. |
Break (15:30‑16:00)
Session 3 (16:00‑17:00)
