ICLP on Tuesday

Detailed program
Tuesday July 30th, 2002
See also the unified by-slot program

Sessions take place in auditorium 4 unless otherwise indicated.

Session 5: Constraints

Chair: Sandro Etalle

09:00-10:00  Bernard Boigelot, U Liege, Belgium
Pierre Wolper, U Liege, Belgium
Invited talk: Representing arithmetic constraints with finite automata: An overview
Linear numerical constraints and their first-order theory, whether defined over the reals or the integers, are basic tools that appear in many areas of Computer Science. This paper overviews a set of techniques based on finite automata that lead to decision procedures and other useful algorithms, as well as to a normal form, for the first-order linear theory of the integers, of the reals, and of the integers and reals combined. This approach has led to an implemented tool, which has the so far unique capability of handling the linear first-order theory of the integers and reals combined.

10:00-10:30  Michael Maher, Loyola U Chicago, USA
Propagation completeness of reactive constraints
We develop a framework for addressing correctness and timeliness-of-propagation issues for reactive constraints - global constraints or user-defined constraints that are implemented through constraint propagation. The notion of propagation completeness is introduced to capture timeliness of constraint propagation. A generalized form of arc-consistency is formulated which unifies many local consistency conditions in the literature. We show that propagation complete implementations of reactive constraints achieve this arc-consistency when propagation quiesces. Finally, we use the framework to state and prove an impossibility result: that CHR cannot implement a common relation with a desirable degree of timely constraint propagation.

Session 6: Memory Management

Chair: David S. Warren

11:00-11:30  Henning Makholm, U Copenhagen, Denmark
Kostis Sagonas, Uppsala U, Sweden
On enabling the WAM with region support
Region-based memory management is an attractive alternative to garbage collection. It relies on a compile-time analysis to annotate the program with explicit allocation and deallocation instructions, where lifetimes of memory objects are grouped together in regions. This paper investigates how to adapt the runtime part of region-based memory management to the WAM setting. We present additions to the memory architecture and instruction set of the WAM that are necessary to implement regions. We extend an optimized WAM-based Prolog implementation with a region-based memory manager which supports backtracking with instant reclamation, and cuts. The performance of region-based execution is compared with that of the baseline garbage-collected implementation on several benchmark programs. A region-enabled WAM performs competitively and often results in time and/or space improvements.

11:30-12:00  Bart Demoen, K.U. Leuven, Belgium
Phuong-Lan Nguyen, Catholic U of the West, France
Ruben Vandeginste, K.U. Leuven, Belgium
Copying garbage collection for the WAM: To mark or not to mark ?
Garbage collection by copying is becoming more and more popular for Prolog. Copying requires a marking phase in order to be safe: safeness means that the to-space is guaranteed not to overflow. However, some systems use a copying garbage collector without marking prior to copying, and instead postpone the copying of potentially unsafe cells. Such systems only collect small portions of the heap and it is not clear whether postponing works while collecting the whole heap. Moreover, it is shown here that postponing does not solve the problem in a fundamental way. Since marking takes time, it is worth studying the tradeoffs involved. These observations have prompted the experimentation with a series of garbage collectors based on copying without marking and without postponing. In particular, variants were implemented that are named dangerous, optimistic and cautious copying which exhibit various degrees of unsafeness. Versions of each have been implemented based on recursive copying as in most implementations of copy_term/2 and on the Cheney algorithm. Performance on benchmarks suggests that large performance gains can be obtained by skipping the marking phase, that dangerous copying is still relatively safe but can be costly, and that the additional effort of cautious copying over optimistic copying is not worth it. The optimistic collectors based on recursive copying perform best and slightly better than the ones based on Cheney. Cache performance measurements back up the benchmark results.

12:00-12:30  Bart Demoen, K.U. Leuven, Belgium
A different look at garbage collection for the WAM
A non-algorithmic approach to garbage collection for the WAM heap is developed. A set of garbage collections compatible with the WAM is specified in two steps: the first step makes the useful data for each continuation private and ensures that only useful terms survive garbage collection. The second step completes garbage collection by extending the intuitive notion of folding of identical structures. The role of the trail in the folding process is crucial and it is shown for the ordinary WAM trail as well as for a value trail. New and unexpected opportunities for recovering memory are discovered to be compatible with this view of garbage collection. This approach leads to better understanding of the usefulness logic in the WAM, it is a good start for the formal specification of the garbage collection process and it shows a potential for new compile time analyses that can improve run time memory management. Choice point trimming is used as a vehicle to show selective liveness of data, so its relation to the more common stack maps is established.

Session 7: Invited Tutorial

14:00-15:30  Thom Frühwirth, U Munich, Germany
Invited tutorial: Constraint handling rules

Session 8: Programming and Extensions

Chair: Henning Christiansen

16:00-16:30  Harald Ganzinger, MPI Saarbrücken, Germany
David McAllester, AT&T Labs, USA
Logical algorithms
It is widely accepted that many algorithms can be concisely and clearly expressed as logical inference rules. However, logic programming has been inappropriate for the study of the running time of algorithms because there has not been a clear and precise model of the run time of a logic program. We present a logic programming model of computation appropriate for the study of the run time of a wide variety of algorithms.

16:30-17:00  Joachim Schimpf, Imperial College, UK
Logical loops
We present a concrete proposal for enhancing Prolog and Prolog based Constraint Logic Programming languages with a new language construct, the logical loop. This is a shorthand notation for the most commonly used recursive control structure: the iteration or tail recursion. We argue that this enhancement fits well with the existing language concepts, enhances productivity and maintainability, and helps newcomers to the language by providing concepts that are familiar from many other programming languages. The language extension is implemented and has been in everyday use over several years within the ECLiPSe system.

17:00-17:30  Eric Martin, U New South Wales, Australia
Phuong Nguyen, U New South Wales, Australia
Arun Sharma, U New South Wales, Australia
Frank Stephan, U Heidelberg, Germany
Learning in logic with RichProlog
Deduction and induction are unified on the basis of a generalized notion of logical consequence, having classical first-order logic as a particular case. RichProlog is a natural extension of Prolog rooted in this generalized logic, in the same way as Prolog is rooted in classical logic. Prolog can answer Σ1 queries as a side effect of a deductive inference. RichProlog can answer Σ1 queries, Π1 queries (as a side effect of an inductive inference), and Σ2 queries (as a side effect of an inductive inference followed by a deductive inference). RichProlog can be used to learn: a learning problem is expressed as a usual logic program, supplemented with data, and solved by asking a Σ2 query. The output is correct in the limit, i.e., when sufficient data have been provided.

17:30-18:30  Association of Logic Programming general meeting

18:30-21:00  Prolog Programming Competition

Room: DIKU