First Workshop on Constraint Handling Rules

May 10 - May 14, 2004

University of Ulm

Ulm, Germany

[Program] [Local Information] [Organization]
The Constraint Handling Rules (CHR) language has become a major specification and implementation language for constraint-based algorithms and applications. Algorithms are often specified using inference rules, rewrite rules, sequents, proof rules or logical axioms that can be directly written in CHR. Based on first order predicate logic, this clean semantics of CHR facilitates non-trivial program analysis and transformation.

Several implementations of CHR exist in Prolog, Haskell, and Java. A particular emphasis of this first workshop will be the comparison, joint development, consolidation and common extension of the various CHR implementations. We expect the main implementors of CHR to be present at the workshop.

This first workshop of CHRs called for extended abstracts describing ongoing work on all aspects of CHR, including topics such as:
- Implementations
- Program Transformation
- Program Analysis
- Algorithms
- Applications
- Critical Assessment/Comparisons

During the workshop new theoretical foundations of CHR as well as technical details of recent implementations of CHR were presented and discussed in detail. The theoretical topics mostly considered linear logics as a new candidate for CHR's declarative semantics. The implementation issues focused on source-to-source transformations, language extensions and compilers for different languages realizing differerent optimization techniques.  All these different "flavours" of CHR and their semantics raised a discussion on how to support this living evolution process.  The audience agreed in the establishment of a CHR mailing list and repository for communication and information as well as in the setup of an repository for the shared use of documents and programs.

Some issues discussed during the workshop (incomplete, unordered):
- linear logic semantics
- compiler optimizations
- analysis (termination and confluence)
- justification and constraint deletions
- debugger, visual tracer
- abduction with multiple constraint stores
- negation in CHR
- sharing implementations of multiple constraint stores
- program transformation for CHR
- using RETE/TREAT algorithms for CHR
- programming pearls in CHR (e.g. union-find algorithm)

Photos taken (by Armin) at the workshop and of Ulm city.

Selected contributions appeared in Ulmer Informatik-Berichte, Nr. 2004-01.


The Program consists of invited talks, talks on accepted papers and tutorials, as well as hands-on working sessions.

All events are in room O27/545.

Tuesday, May 11

11:00-12:30 Invited Talk I

Christian Holzbaur
Department of Medical Cybernetics and Artifical Intelligence (IMKAI)
University of Vienna

Source-to-Source Transformations and Bootstrapped Compilation of Constraint Handling Rules

The relational representation of CHR programs, initially excogitated as a means of elegant source-to-source transformations within the CHR framework, very naturally led to the construction of a fully functional bootstrapped compiler for CHR.  The use of dictionaries, common to virtually any compiler, is supported directly and very compactly by CHR, including iterations/mappings over relations.  In the talk we will present the CHR formulation of the analytical tasks required by the compilation process (functional dependency analysis, set semantics of constraints, etc.) The confluence of the ensuant incremental compiler has recently been demonstrated by semi-automatic methods.

12:30-14:00 Lunch Break

14:00-15:30 Invited Talk II

Armin Wolf

Fraunhofer Institut für Rechnerarchitektur und Softwaretechnik (FIRST)
Fraunhofer Gesellschaft e.V.

DJCHR - a Java-Based System for Dynamic Constraint Handling -- Theory, Architecture and Application --

The CHR language is an executable specification language successfully applied to implement several constraint theories. These implementations are used in various applications solving real-world as well as benchmark constraint problems. 

In this talk, an extended Java-based CHR implementation is presented. This implementation differs from all other CHR implementations in mainly two topics: All constraints - given or derived - are justified. This offers a new functionality in CHR implementations allowing arbitrary constraint additions and deletions. Thus, the handling of dynamic constraint problems as well as  the implementation of local or dependency-directed search algorithms is supported in this Java-based CHR implementation. 

The talk is organized as follows: First, the theoretical foundation for the extended functionality is introduced. Then, the architecture of the CHR implementation is presented and its usage is shown by example. Further examples give an impression of the capability of dynamic constraint handling: a CHR-based implementation of a simulated annealing approach for solving the n queens problem, a CHR-based implemention of an advanced conflict-directed search algorithm for solving SAT-problems, and others. These presentations are completed by the results of runtime examinations, esp. performed in comparison with the CHR implementation in SICStus Prolog. 

The talk is concluded with some suggestions of future work.

15:30 - 16:00 Coffee Break

16:00 Discussion CHR Implementation Issues

Wednesday, May 12

9:00 - 10:00 CHR Implementation

Tom Schrijvers and Bart Demoen
Katholieke Universiteit Leuven, Belgium

The K.U.Leuven CHR system: implementation and application  (slides)

Henning Christiansen
Roskilde University, Denmark

CHR Grammars with multiple constraint store (slides)

10:00-10:30 Coffee Break

10:30-11:00 CHR Program Transformation

Thom Frühwirth
Universität Ulm, Germany

First Examples of CHR Program Transformation

11:00-12:00 Discussion Implementation Issues

12:00-14:00 Lunch Break

14:00 - 15:00 Linear Logic 

Hariolf Betz
Universität Ulm, Germany

A linear logic semantics for CHR

Rémy Haemmerlé and Olivier Bouissou
INRIA Rocquencourt, France

The SiLCC Project

15:00-15:30 Coffee Break

15:30 Discusssion CHR Extensions/ Future Development

Slim Abdennadher (not present)
Department of Computer Science
German University in Cairo

JCK: A Java Constraint Kit
The talk will introduce a library, called JCK, providing constraint programming for the host language Java.
JCK consists of three components:

JCHR: Java Constraint Handling Rules. A high-level language to write application specific constraint solvers.

JASE: Java Abstract Search Engine. A generic search engine for JCHR to solve constraint problems.

VisualCHR. An interactive tool to visualize JCHR computations.

Martin Sulzmann (not present)
National University of Singapore

The Chameleon System

Local Information

For Information about the city of Ulm and how to get there, go to the local information section on the KI-2004 pages.

In Ulm, busses go every 10 minutes from 7am to 8pm, except Sunday mornings.
You can buy a ticket for a single ride (Euro 1.50) at the driver or at a machine at bus stops.

How to get to your hotel from the main train station (Hauptbahnhof):

In front of the train station, there is a bus and tram stop.

If you stay at Hotel Ibis, you have to take the bus going to the left. So use the undercrossing to take bus number 3 for one stop only, the stop is called "Theater".
Hotel Ibis is directly at this bus stop.

If you stay at Hotel Rathaus, you have to take the bus going to the right. Take bus number 5 or 6 for a few stops (5 mins.) to "Rathaus". At the back of the Rathaus there is a square. On the opposite side of the square, near the huge glass pyramide building, is your hotel.

How to get to the university from your hotel:

Enter bus 3 at the bus stop "Theater" at Hotel Ibis, after 5-10 mins, exit at the 6th stop called "Universität Süd" (first stop after the woods).

If you stay at another hotel in the inner city area, its best to walk to the bus stop "Theater", it will take 5-10 minutes.

Having left the bus at "Universität Süd", climb the staircase and enter the university, you are now in building O25 (chessboard like numbering system). Turn right, cross the cafeteria and  head for building O27. Our department "Programmiermethodik and Compilerbau" is located on the forth (yellow) floor. You can find the secretary in room O27/419. The lecture room O27/545 is in the same building on the fifth (orange) floor.


Workshop Organizers

Thom Frühwirth
Abteilung Programmiermethodik und Compilerbau
University of Ulm

Marc Meister
Abteilung Programmiermethodik und Compilerbau
University of Ulm