page 1  (12 pages)
2to next section

Expanding the text here will generate a large amount of data for your browser to display

Interfacing Propagators with a Concurrent

Constraint Language

Tobias M?uller
Programming Systems Lab
University of the Saarland
Geb. 45, Postf. 15 11 50
66041 Saarbr?ucken
tmueller@ps.uni-sb.de

J?org W?urtz
Programming Systems Lab
German Research Center for AI
Geb. 45, Postf. 15 11 50
66041 Saarbr?ucken
wuertz@ps.uni-sb.de

This paper describes a C++ interface for the concurrent constraint language Oz to implement non-basic constraints as propagators. The programmer benefits from the advantages of a high-level language, like elegant and concise coding, in conjunction with efficiency. For the user it is transparent whether a constraint is implemented by an Oz procedure or through the interface. The interface is completely separated from the underlying Oz implementation. Moreover, it frees the user from tedious tasks like suspending and waking up constraints.

The overall efficiency of the resulting system is comparable to existing finite domain systems. For scheduling applications we demonstrate how algorithms from Operations Research can be incorporated, which allows to obtain results comparable to commercially available systems.

Keywords. Concurrent Constraint Language, Finite Domain Constraints, Efficient Implementation

1. Introduction

A concurrent constraint language provides for a well-suited platform to implement a finite domain constraint system over natural numbers. The concepts of a constraint store and of concurrent computation give the appropriate metaphors needed to understand and implement constraint programs. For the language Oz, we have shown in [SSW94] that the minimal requirements to enable finite domain programming are primitives to constrain a variable to a finite domain and to reflect the current domain of a variable in conjunction with encapsulated search. Desired constraints can be expressed in the language itself in an elegant way.

But finite domain systems must be efficient in order to tackle practical problems, like scheduling, placement or configuration [DVS+88]. Consequently, we decided to reimplement more complex constraints, so-called propagators, which were implemented as Oz procedures by corresponding C++ code. The resulting system provided the required efficiency and still allowed the user to invent new constraints by combining propagators with Oz language constructs like conditionals or disjunctions [ST95, MW96]. Nevertheless, users were not able to implement C++ propagators themselves to meet their individual needs of efficiency.
Hence, we wanted to design an interface to C++ propagators that can easily be used by programmers. The main design goals were as follows: