COMPILING CONSTRAINTS IN CLP(FD)

We present the clp(FD) system: a constraint logic programming language with finite domain constraints. We detail its implementation, and pre sent 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 constraint X in r that embeds the core propagat ion mechanism. Complex user constraints such as linear equations or in equations are compiled into X in r expressions that encode the propaga tion scheme chosen to solve the constraint. The uniform treatment of a single primitive constraint leads to a better understanding of the ov erall constraint-solving process, and allows three main general optimi zations that encompass many previous particular optimizations of ''bla ck-box'' finite domain solvers. Implementation results show that this approach combines both simplicity and efficiency. Our clp(FD) system i s about four times faster than CHIP on average, with peak speedup reac hing eight. We also show that, following the ''glass-box'' approach, c lp(FD) can be naturally enhanced with various new constraints such as constructive disjunction, Boolean constraints, nonlinear constraints, and symbolic constraints.