.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Declarative Programming
More on Constraint Logic Programming
Geraint A. Wiggins
Professor of Computational Creativity
Department of Computer Science
Vrije Universiteit Brussel
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Propositional Constraints
▶ In the last lecture, we saw the use of propositional
constraints in the store_boxes program
▶ Syntax of propositional constraints:
not: #\ C
and: C1 #/\ C2
or: C1 #\/ C2
ex-or: C1 #\ C2
implies: C1 #==> C2
if: C1 #<== C2
iff: C1 #<==> C2
▶ For these goals to be acceptable, C, C1 and C2 must be
reifiable
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Propositional Constraints (2)
▶ We can use propositional constraints for applying different
sets of constraints in our system in different cases, eg
( X #= 1 #==> Y in 1..10 ) #/\
( X #\= 1 #==> Y in 20..30 )
is the CLP way of saying
if X = 1
then
1 ≤ Y ≤ 10
else
20 ≤ Y ≤ 30
▶ Propositional constraints allow us to delay decisions
about the structure of the constraint system itself, so we
can reduce backtracking even more than by just using
numerical constraints
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Reified Constraints
▶ Reified means “made into a thing” (Latin: res) or, better,
made concrete
▶ Here, it means associating an explicit truth value (0 or 1)
with a constraint
▶ To do this, we usually use the propositional constraint
#<==>, because that tells us the exact value of the
constraint we are reifying
▶ Constraints are reified if their definitions are given in a
certain way; the details are beyond the scope of this
course
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Reified Constraints (2)
▶ For example, in the constraint
( A #= B ) #<==> R
R is the reification of A #= B…
which means
R = 1 iff A = B
R = 0 iff A ̸= B
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Reified Constraints (3)
▶ So we can check whether or not a constraint holds, or if
it is as yet undecided – constraint meta-programming!
▶ But note that we can also force a value on R and force
the constraint to be true or false:
?- ( A #= B ) #<==> R,
A in 1..10, B in 5..15,
R #= 1.
R = 1,
B in 5..10,
A in 5..10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Reified Constraints (4)
▶ Now, we can specify a system, and demand that as many
constraints as possible are satisfied:
satisfy( W, X, Y, Z ) :-
constraint1( W ) #<==> R1,
constraint2( X ) #<==> R2,
constraint3( Y ) #<==> R3,
constraint4( Z ) #<==> R4,
R #= R1 + R2 + R3 + R4,
labeling( [max(R)], [W,X,Y,Z] ).
▶ Here we are abusing the notation; this works because we
represent truth values as numbers
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Reified Constraints (5)
▶ For example:
satisfy( X, Y, Z, R ) :-
X #= Y + 1 #<==> R1,
Y #= Z #<==> R2,
X #= Y + Z #<==> R3,
R #= R1 + R2 + R3,
labeling( [max(R)], [X,Y,Z] ).
?- domain( [X,Y,Z], -10, 10 ),
satisfy( X, Y, Z, R ).
R = 3,
X = 2,
Y = 1,
Z = 1 ?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Reified Constraints (6)
▶ For example:
satisfy( X, Y, Z, R ) :-
X #= Y + 1 #<==> R1,
Y #= Z #<==> R2,
X #= Y + Z #<==> R3,
R #= R1 + R2 + R3,
labeling( [max(R)], [X,Y,Z] ).
?- domain( [X,Y,Z], 2, 10 ),
satisfy( X, Y, Z, R ).
R = 2,
X = 3,
Y = 2,
Z = 2 ?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Combinatorial Constraints
▶ Combinatorial constraints are generally used for purposes
of efficiency, where a group of constraints may be solved
more efficiently together than separately
▶ In SWI Prolog, these constraints are implemented by
term expansion, like DCGs
▶ As a consequence, we sometimes have to postpone their
expansion until runtime (or later) using call/1 (and
possibly when/2)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Combinatorial Constraints (2)
▶ all_different/1 constrains each element of the list of
variables in its argument to be different
▶ Note that, for efficiency reasons, this predicate is
incomplete – it is a fast version which works most of the
time
▶ This means that sometimes it will fail to rule out an
inconsistent constraint system…
…but it will never rule out a consistent one
▶ If you need a complete (but slower) version, you can use
all_distinct/1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Combinatorial Constraints (3)
▶ element/3 constrains two variables, X and Y, and a
ground list, L, so that the Xth element of L is in the
domain of Y for every value in the domain of X
?- X in 2..3,
element( X, [10,20,30,40], Y ).
X in 2..3,
Y in{20}\/{30} ?
yes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Combinatorial Constraints (4)
▶ relation/3 constrains two variables, X and Y and a list
of integer/range pairs, L, so that the domain of Y is
consistent with the ranges associated with all integers in
the domain of X
?- X in 2..3,
relation( X, [1-(1..3),
2-(4..5),
3-(5..7)], Y ).
X in 2..3,
Y in 4..7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Constraints over other Domains
▶ We can make constraints over other mathematical
structures in SWI Prolog:
Booleans – a solver for simple Boolean algebra
Reals – a solver for the real numbers; note that
answers will be floating point approximations
to the reals
Rationals – a solver for the rational numbers (numbers
which can be expressed as fractions with
integer components, eg 12 ,
2005
47 )
▶ We won’t discuss Booleans here, as Boolean algebra is
possible in the FD package
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Constraints over other Domains (2)
▶ To post constraints in the reals, we use the following
notation:
?- { X < 2.0, Y > 1.0, Y = X + 1.0 }.
{Y=1.0+X},
{X>0.0},
{X<2.0}
▶ The same notation is used for rationals, except that the
numbers are represented using rat/2 terms, eg
rat(1,2), rat(2005,47)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Constraints over other Domains (3)
▶ Note that we cannot generate a labelling for the real
numbers, because there are uncountably many of them
▶ Therefore, we need access to the constraint solutions
themselves to search explicitly for a proof
▶ To do this, we use the call_residue_vars/2 predicate:
?- call_residue_vars( {X < 2.0,
Y > 1.0,
Y = X + 1.0}, R )
R = [[Y]-Y=1.0+X,[Y]-X>0.0,[X]-X<2.0] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Constraints over other Domains (4) ▶ We can mix real and rational constraints, but we cannot mix reals with rationals ▶ Prolog will work out which is which and use the appropriate definition (like polymorphic types) ▶ To use CLP(QR): :- use_module( library(clpqr), [] ). ▶ Note that some versions of Prolog have two separate modules for this.