Integration of Finite Domain Constraints in KiCS2

by Michael Hanus, Björn Peemöller, Jan Rasmus Tikovsky

Proc. of the 7th Working Conference on Programming Languages (ATPS 2014), Software Engineering 2014, CEUR Workshop Proceedings 1129, pp. 151-170, 2014

A constraint programming system usually consists of two main components: a modelling language used to describe a constraint satisfaction problem and a constraint solver searching for solutions to the given problem by applying specific algorithms. As constraint programming and functional logic languages share some common features, like computing with logic variables or the use of backtracking for non-deterministic search, it is reasonable to embed a modelling language for finite domain constraints in a functional logic language like Curry. Due to the absence of side effects or global state over non-deterministic computations in Curry, the implementation of a stateful constraint solver is rather difficult. In this paper we consider KiCS2, a Curry compiler translating Curry programs into Haskell programs. In order to embed finite domain constraints in KiCS2, we propose a new implementation technique compatible with the purely functional nature of its back end. Our implementation collects finite domain constraints occurring during a program run and passes them to a constraint solver available in Haskell whenever solutions are requested.

Preprint (PDF) BibTeX-Entry Online