SWI-Prolog 7.4.2 Reference Manual

# 7 Constraint Logic Programming

This chapter describes the extensions primarily designed to support constraint logic programming (CLP), an important declarative programming paradigm with countless practical applications.

CLP(X) stands for constraint logic programming over the domain X. Plain Prolog can be regarded as CLP(H), where H stands for Herbrand terms. Over this domain, =/2 and dif/2 are the most important constraints that express, respectively, equality and disequality of terms. Constraint logic programming is thus a natural generalization of plain Prolog.

There are dedicated constraint solvers for several important domains:

- CLP(FD) for integers (section A.8)
- CLP(B) for Boolean variables (section A.7)
- CLP(Q) for rational numbers (section A.9)
- CLP(R) for floating point numbers (section A.9).

In addition, CHR (chapter 8) provides a general purpose constraint handling language to reason over user-defined constraints.

A key advantage of constraints is their ability to combine all available information that is stated about the entities you reason about, independent of the order in which you state it, and before the actual search for solutions even begins. Using the available information to prune parts of the search space is called constraint propagation, and it is performed automatically by the available constraint solvers for their respective domains.

Among the most important and typical instances is CLP(FD), constraint logic programming over integers. For example, using constraints, you can state in the most general way that a variable X is an integer greater than 0. If, later, X is bound to a concrete integer, the constraint solver automatically ensures this. If you in addition constrain X to integers less than 3, the constraint solver combines the existing knowledge to infer that X is either 1 or 2 (see below). To obtain concrete values for X, you can ask the solver to label X and produce 1 and 2 on backtracking. See section A.8.

    ?- use_module(library(clpfd)).
    ...
    true.

    ?- X #> 0, X #< 3.
    X in 1..2.

    ?- X #> 0, X #< 3, indomain(X).
    X = 1 ;
    X = 2.

Contrast this with plain Prolog, which has no efficient means to deal with (integer) X > 0 and X < 3. At best it could translate X > 0 to `between(1, infinite, X)` and a similar primitive for X < 3. If the two are combined it has no choice but to generate and test over this infinite two-dimensional space.

Using constraints therefore makes your program more declarative in that it frees you from some procedural aspects and limitations of Prolog.

When working with constraints, keep in mind the following:

- As with plain Prolog, !/0 also destroys the declarative semantics of constraints. A cut after a goal that is delayed may prematurely prune the search space, because the truth of delayed goals is not yet established. There are several ways to avoid cuts in constraint logic programs, retaining both generality and determinism of your programs. See for example zcompare/3.
- Term-copying operations ( assertz/1, retract/1, findall/3, copy_term/2, etc.) generally also copy constraints. The effect varies from ok, silent copying of huge constraint networks to violations of the internal consistency of constraint networks. As a rule of thumb, copying terms holding attributes must be deprecated. If you need to reason about a term that is involved in constraints, use copy_term/3 to obtain the constraints as Prolog goals, and use these goals for further processing.

All of the mentioned constraint solvers are implemented using the attributed variables interface described in section 7.1. These are lower-level predicates that are mainly intended for library authors, not for typical Prolog programmers.

## Section Index