.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Declarative Programming
Finite Domains in Prolog
Geraint A. Wiggins
Professor of Computational Creativity
Department of Computer Science
Vrije Universiteit Brussel
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
The idea behind constraint logic programming
▶ In old-fashioned Prolog programming, programs can
spend an awful lot of time searching through impossible
solutions, because a test is applied after an entire solution
has been generated – e.g., British Museum sort
▶ We can partly overcome this problem by using delayed
calls to let predicates “lie in wait” for information, and
substantial improvements can be made – e.g., n! to ∼ n2
▶ But we can improve things still further, by reasoning with
a logical theory about our data
▶ SWI Prolog has built-in theories for integer finite
domains, booleans, real numbers, and rational numbers
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
The idea behind constraint logic programming (2)
▶ When we do this, we can think of the constraints as an
enhancement of the unification process (there are logical
ways of explaining this), instead of as part of the
execution process, like delay declarations
▶ So if we insist in advance, for example, that X is an
integer between 1 and 3, then the attempt to unify X
with 5 can be made to fail as soon as it is tried, instead
of at some time later
▶ Using constraints can cut down the search space for
solutions by many, many orders of magnitude
▶ They can even effectively change the algorithm of a
program (as with BMsort)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Finite domains in Prolog
▶ Internally, to the advanced programmer, the SWI Prolog
constraint system is very complex and powerful
▶ However, it can be used very easily to produce striking
effects
▶ We associate a set of “allowed values” with each variable,
and then any attempt to unify it with something “not
allowed” will fail
▶ We allow the specification of fixed relationships between
variables (e.g., X < Y)
▶ We could do this with delay declarations alone…
▶ In CLP(FD) we add a theory of integers so we can solve
(mostly linear) equations
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Finite domains in Prolog (2)
▶ This allows Prolog to go beyond ordinary unification, and
actually suggest values in some cases e.g.,
?- X in 1..10, X #> _Y + 8, _Y = 1.
X = 10 ?
true
▶ Like delayed goals, constraints can sometimes leave a
useful residue:
?- X in 1..10, X #> Y + 8, Y = -2.
X in 7..10 ?
true
?- X in 1..10, X \= 5.
X in(1..4)\/(6..10)
true
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Finite domains in Prolog (3)
▶ We can reason about the domains themselves, too:
?- X in 1..10, Y in 8..20, X = Y.
X = Y
X in 8..10 ?
true
▶ And we can enumerate the members of a domain, if we
need to:
?- X in 1..3, indomain( X ).
X = 1 ? ;
X = 2 ? ;
X = 3 ? ;
false
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
How Finite Domains work in Prolog
▶ First, we define domain constraints
▶ A domain constraint is of the form X::I where X is a
variable, and I is a finite set of integers
▶ A set S of domain constraints is called a store.
▶ The domain, D(X,S), of X in S is the intersection of all I
such that X::I is in S
▶ S is consistent if D(X,S) is inhabited for all X
▶ Otherwise it is contradictory
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
How Finite Domains work in Prolog (2)
▶ Now, whenever we unify a domain variable with anything,
we add any constraints produced to the store
▶ If the resulting store is consistent, unification succeeds
▶ If the resulting store is contradictory, unification fails and
we backtrack
▶ There is a further system involved with constraint
programming, called indexicals, but we will not cover that
here
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Domain Specification Syntax
▶ Domains are specified using a special kind of integer
term, which I will call an integer domain term
▶ An integer domain term is one of the following:
▶ an integer (e.g., 1)
▶ sup – positive infinity (supremum)
▶ inf – negative infinity (infimum)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Domain Specification Syntax (2)
▶ A range is one of the following:
▶ an interval (e.g., T1..T2)
▶ a set of integers (e.g., {1,20})
▶ a union of ranges
(e.g., T1..T2 \/ {1,10})
▶ an intersection of ranges
(e.g., T1..T2 /\ {2,7,8})
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Predefined constraints
▶ SWI Prolog’s finite domain package is in
library(clpfd), and contains the following predicates
(among others)
▶ For testing and setting constraints:
in/2 associates a range with a variable and checks
consistency: X in 1..10
=/2 unifies terms and checks consistency
#OP/2 where OP is one of >, >=, =, =<, <, posts an arithmetic constraint and checks consistency: X #> Y + 2
#\=/2 makes two expressions arithmetically not
equal
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
An example: B M sort again
▶ Recall the example from the last lecture:
dbmsort(X,Y) :-
when( nonvar( Y ), ord( Y )),
perm( X, Y ).
ord( [H1,H2|T] ) :-
H1 #=< H2,
when( nonvar( T ), ord( [H2|T] )).
ord( [_] ).
ord( [] ).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Executing constrained BM sort
▶ Consider the non-ground query again:
?- dbmsort( [4,V,3,1], Y ).
Y = [V,1,3,4],
V in inf..1 ? ;
Y = [1,V,3,4],
V in 1..3 ? ;
Y = [1,3,V,4],
V in 3..4 ? ;
Y = [1,3,4,V],
V in 4..sup ? ;
false
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Example: SEND MORE MONEY
▶ A well known puzzle: Find the values of the variables in
the sum
S E N D
+ M O R E
M O N E Y
where all the variables have different values
▶ We can write a constraint logic program to do this easily
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
SEND MORE MONEY (2)
▶ First, we write down a predicate which will add the
numbers appropriately:
% we need to allow a carrying slot
add( A, B, C ) :-
add( A, B, C, 0 ).
% add numbers rep'd as lists of digits
add( [], [], [], 0 ).
add( [A|As], [B|Bs], [C|Cs], Carry ) :-
A in 0..9,
B in 0..9,
C #= ( A + B + NextCarry ) mod 10,
Carry #= ( A + B + NextCarry ) / 10,
add( As, Bs, Cs, NextCarry ).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
SEND MORE MONEY (3)
▶ And we call
?- add( [0,S,E,N,D], [0,M,O,R,E],
[M,O,N,E,Y] ),
all_different( [S,E,N,D,M,O,R,Y] ),
labeling( [], [S,E,N,D,M,O,R,Y] ).
▶ all_different/1 constrains the variables in its
argument list to be different
▶ labeling/2 enumerates the values of the variables in its
second argument, as constrained by the store
▶ This version is roughly 2,800 times faster than the best
generate and test version!