ILPS'97 Tutorial

Constraint Programming in Oz

Gert Smolka

DFKI and Universität des Saarlandes
Saarbrücken, Germany

The tutorial will introduce the constraint programming facilities of Oz 2. The audience is expected to have a passing acquaintance with finite domain constraint logic programming.

Oz 2 is a lexically scoped language with first-class procedures, cells, threads, logic variables, and a constraint store. It supports finite domain constraints and feature constraints. Oz is not based on backtracking but has a space primitive from which a variety of encapsulated search engines can be programmed. Spaces can express sequential and concurrent engines for one, incremental all, and best solution search. They can also express specialized engines for chart parsing of constraint grammars and polymorphic type inference.

The beta version of DFKI Oz 2 is available under a GNU-style licence. On a Pentium, DFKI Oz 2 finds and proves an optimal solution of the MT 10 job shop scheduling problem in less than 3 minutes. DFKI Oz 2 has a C++ interface for adding new propagators and comes with innovative tools facilitating the development of constraint programs.

The outline of the tutorial is as follows:

  1. Review of finite domain constraint programming
  2. Finite domain constraint programming in Oz
  3. Programming search engines with spaces
  4. Case study: parsersfor constraint grammars

The following papers are related to the tutorial:

  1. Gert Smolka, The Oz Programming Model.
  2. Gert Smolka, Finite Domain Constraint Programming in Oz. (Postscript , Oz Programs).
  3. Christian Schulte, Programming Constraint Inference Engines.
  4. Christian Schulte, Oz Explorer: A Visual Constraint Programming Tool.
  5. Jörg Würtz, Constraint-Based Scheduling in Oz.
  6. Tobias Müller and Jörg Würtz, Extending a Concurrent Constraint Language by Propagators.