There is an obvious relation between C(L)P languages and Operations Research: results and algorithms from O.R. are vital, and are found at the heart of C(L)P languages, because the solving methods for constraint systems are most times taken from O.R. But there is also a good deal of implementation techniques (which we have not even mentioned, and which we will not study) which come from Computer Science, and do not make sense in a setting of static equations: incremental addition of constraints, propagation of values, and different solving heuristics based on the problem under consideration.

The use of a programming language offers many advantages: explicit algorithms can be programmed if needed, equations can be set up (and changed) dynamically, the solvability of the constraints forces backtracking (and, thus, the removal of some constraints and the addition of some others) by failing when a non-consistent state is reached, and there is always the possibility of performing search among the possible values in the domain of the variables. This is the only way to reach a definite solution when the problem is underconstrained, or the constraint solver is too weak to solve them directly, or, simply, there is no known algorithm to work out a solution to the generated constraints.

The use of the data structures of the language favors a more modular, portable way to attack problems, and assimilating language variables to constraint variables results in a clean semantics and in clear programs. Also, the rule-based programming in CLP allow the expression of algorithms in a declarative way which is often more compact, easier to understand, debug (because of, for example, the implicit memory management), maintain, and update.

The next chapter will deal with Prolog. Prolog is a constraint language over the domain of Herbrand terms, and since most CLP languages are based on extending Prolog, they inherit lots of builtin predicates and control expressions from Prolog: we will review them. And, finally, Prolog itself is a nice language for writing many applications.

1998-12-03