 | |
Sessions
take place in auditorium 4 unless otherwise indicated.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. |
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. |
| 14:00- | 15:30
| Thom
Frühwirth, U Munich, Germany
Invited
tutorial: Constraint handling rules |
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. |
Room:
DIKU |