|
May 10 - May 14, 2004 University of Ulm Ulm, Germany |
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
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.
14:00-15:30 Invited Talk II
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.
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
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
Slim
Abdennadher (not present)
Department of Computer Science
German University in Cairo
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.
Thom
Frühwirth
Abteilung Programmiermethodik und Compilerbau
University of Ulm
Marc
Meister
Abteilung Programmiermethodik und Compilerbau
University of Ulm