constraint logic programming
Springer Online Journal Archives 1860-2000
Abstract In this paper, we describe Nicolog, a language with capabilities similar to recently developed constraint logic programming (CLP) languages such as CLP(BNR), clp(FD), and cc(FD). Central to Nicolog are projection constraints (PCs), a sublanguage for compiling and optimizing constraint propagation in numeric and Boolean domains. PCs are an interesting generalization of the indexical constraints introduced in cc(FD) and also found in clp(FD). Nicolog compiles a very general class of built-in constraints into equivalent sets of PCs, allowing an arbitrary mixture of integer (easily extensible to real) and Boolean operations. Nicolog also lets the user program PCs directly, making it possible to implement new sophisticated propagation procedures. We show that PCs are a simple, efficient, and flexible way to implement most of the propagation procedures possible in other FD CLP systems. These include procedures for cardinality, constructive disjunction, implication, and mixed Boolean/numeric constraints. Empirical results with a simple prototype Nicolog implementation based on the WAM architecture show it can solve hard problems with speed comparable to the fastest existing CLP systems.
Type of Medium: