Compiling constraints in clp(FD)

The clp(FD) system is a Constraint Logic Programming language with finite domain constraints based on the use of a single primitive constraint X in r that embeds the core propagation mechanism and can be naturally enhanced with various new constraints such as constructive disjunction, boolean constraints, non-linear constraints and symbolic constraints.

Abstract

We present the clp(FD) system: a constraint logic programming language with finite domain constraints. We detail its implementation, and present an abstract instruction set for the constraint solver that can be smoothly integrated into the WAM architecture. It is based on the use of a single primitive constraintX in r that embeds the core propagation mechanism. Complex user constraints such as linear equations or inequations are compiled into X in r expressions that encode the propagation scheme chosen to solve the constraint. The uniform treatment of a single primitive constraint leads to a better understanding of the overall constraint-solving process, and allows three main general optimizations that encompass many previous particular optimizations of "black-box" finite domain solvers. Implementation results show that this approach combines both simplicity and efficiency. Our clp(FD) system is about four times faster than CHIP on average, with peak speedup reaching eight. We also show that, following the "glass-box" approach, clp(FD) can be naturally enhanced with various new constraints such as constructive disjunction, Boolean constraints, nonlinear constraints, and symbolic constraints.