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(Z) constraints automatically available in all your programs, since almost all Prolog programs also reason about integers.

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: