It is rather as if the professional community had been suddenly
transported to another planet where familiar objects are seen in
a different light and are joined by unfamiliar ones
as well. (Thomas S. Kuhn, *The Structure of
Scientific Revolutions*)

The

natnum(0). natnum(s(N)) :- natnum(N).In this representation, the natural number

With this representation, we

nat_nat_sum(0, M, M). nat_nat_sum(s(N), M, s(Sum)) :- nat_nat_sum(M, N, Sum).This is a pure predicate that

Unfortunately, this representation of natural numbers suffers from several significant disadvantages:

- First, this is not really the way we
*want*to write and read numbers. We would like to use a more familiar notation—such as 1, 2 and 3—to represent natural numbers. - With some practice, we may get used to the
successor notation. However, a more fundamental problem
remains: This representation takes space that is directly
proportional to the
*magnitude*of the numbers we need to represent. Thus, the space requirement grows*exponentially*with the length of any number's decimal representation. Therefore, reasoning about larger numbers is infeasible with this representation. - More complex relations such as
*multiplication*and*exponentiation*are hard to define in such a way that they work in*all*directions and retain good termination properties. - To extend this representation to
*integers*, we also need a way to represent*negative*numbers.

Instead, we use built-in predicates to reason about

All widely used Prolog implementations provide CLP(FD) constraints. However, the exact details differ slightly between various systems. For example, in GNU Prolog, B-Prolog and other systems, CLP(FD) constraints are conveniently available right from the start. In contrast, you need to load a

If your Prolog systems provides CLP(FD) constraints as a library, adjust your initialization file so that this library is automatically available in all your programs. For example, in SICStus Prolog, you can put the following directive in your initialization file:

:- use_module(library(clpfd)).

It is highly advisable to make CLP(FD) or CLP(ℤ) constraints automatically available in all your programs, since almost all Prolog programs also reason about integers.

Video: |

In the following, we are considering CLP(FD) constraints. These are built-in predicates that enable reasoning over

The most important CLP(FD) constraints are the

Constraint |
Meaning |

A #= B |
A is equal to B |

A #< B |
A is less than B |

A #> B |
A is greater than B |

A #\= B |
A is not equal to B |

- a logical
*variable*is an expression - an
*integer*is an expression *if*`X`and`Y`are expressions,*then*`X+Y`,`X-Y`and`X*Y`are*also*expressions.

To evaluate integer expressions, we use the predicate

Here are a few examples:

?- X #= 5 + 3. X = 8. ?- 2 #= X + 9. X = -7. ?- 1 #= 1 + Y. Y = 0.Equality is one of the most important predicates when reasoning about integers. As these examples illustrate,

list_length([], 0). list_length([_|Ls], Length) :- Length #= Length0 + 1, list_length(Ls, Length0).A declarative reading of this predicate makes clear what this relation means:

- The length of the
*empty list*is 0. *If*`Length0`is the length of`Ls`*and*`Length`is`Length0`plus 1,*then*the length of`[_|Ls]`is`Length`.

?- list_length([a,b,c,d], Length).Importantly, this also works in more general cases. For example:Length = 4.

?- list_length(Ls, Length).It can also be used in a different direction. For example:Ls = [], Length = 0 ; Ls = [_1716], Length = 1 ; Ls = [_42, _150], Length = 2.

?- list_length(Ls, 3).Note though that this does not terminate:Ls = [_898, _1064, _1230].

?- list_length(Ls, 3),It takes only a single additional goal to make this queryfalse.nontermination

To avoid the accumulation of

list_length(Ls, L) :- list_length_(Ls, 0, L). list_length_([], L, L). list_length_([_|Ls], L0, L) :- L1 #= L0 + 1, list_length_(Ls, L1, L).Again, making the goal

?- V in 0..2. V in 0..2.If we place additional goals on the toplevel, the system automatically takes into account the admissible set of integers we specified for

?- V in 0..2, V #= 3.In contrast, the following query succeeds:false.

?- V in 0..2, V #= 1.Now two variablesV = 1.

?- X in 0..2, Y in 0..2. X in 0..2, Y in 0..2.Or, equivalently:

?- [X,Y] ins 0..2. X in 0..2, Y in 0..2.Thus, the predicate

?- V in 0..2, indomain(V). V = 0 ; V = 1 ; V = 2.Assigning concrete values to constrained variables is called

?- [X,Y] ins 0..1, label([X,Y]). X = Y, Y = 0 ; X = 0, Y = 1 ; X = 1, Y = 0 ; X = Y, Y = 1.If

label(Vs) :- maplist(indomain, Vs).Labeling is a form of search that

In practice, the order in which variables are bound to concrete values of their domains matters. For this reason, the predicate

For other problems, a static reordering of variables may suffice. With N-queens for example, it is worth trying to order the variables so that labeling starts from the board's center and gradually moves to the borders.

?- [X,Y] ins 0..2, Z #= X + Y. X in 0..2, X+Y#=Z, Y in 0..2,Note that the domain ofZ in 0..4.

?- [X,Y] ins 0..2, Z #= X + Y, Z #= 0. X = 0, Y = 0, Z = 0.In this case, propagation yields ground instances for all variables. In other cases, constraint propagation detects unsatisfiability of a set of constraints without any labeling:

?- X in 0..1, X #> 2.In yet other cases, domain boundaries are adjusted:false.

?- [X,Y] ins 0..2, Z #= X + Y, Z #= 1.A set of constraints and variables with associated domains is called (globally)Z = 1, X in 0..1,X+Y#=1,Y in 0..1.

For example, the

?- [X,Y,Z] ins 0..1, all_different([X,Y,Z]). X in 0..1, all_different([X, Y, Z]), Y in 0..1, Z in 0..1.The

?- [X,Y,Z] ins 0..1, all_distinct([X,Y,Z]).To guarantee that stronger form of consistency, thefalse.

Instead of arithmetic constraints like

`(is)/2`and other low-level predicates are*moded*. This means that they can only be used in a few directions, making them unsuitable for more general relations. This severe limitation also prevents*declarative debugging*.`(is)/2`and other low-level predicates intermingle reasoning about integers with reasoning about floating point numbers, and in some systems even about*rational*numbers. This means that when readers of your code see such predicates, they will wonder whether you are using them because floating point numbers may arise somewhere. In contrast,`(#=)/2`and other CLP(FD) constraints make it perfectly clear that you intend to reason about*integers*. These constraints will help you to find certain classes of mistakes in your code more easily, because they throw*type errors*instead of failing silently.`(is)/2`and other low-level predicates force beginners to understand the procedural execution of Prolog programs*in addition*to understanding the declarative semantics. This is too hard in almost all cases.`(is)/2`itself is not sufficient: You also need`(=:=)/2`. In contrast, the CLP(FD) constraint`(#=)/2`subsumes*both*`(is)/2`and`(=:=)/2`when reasoning over integers, making Prolog easier to teach.

By the way:

Several CLP(FD) examples are available from: