This week's topics are covered in Prolog Programming, 4th Edition (Bratko): see ch. 3 Lists, Operators, Arithmetic (3.2 Operator notation, 3.3 Arithmetic), ch. 7 Constraint Logic Programming (7.2 CLP over real numbers, 7.4 CLP over finite domains).
Note that in the 3rd edition of the Bratko text, constraint logic programming is discussed in chapter 14.
Here is a summary of the Prolog elements we discussed:
Prolog recognizes binary infix operators such as + and *. An expression containing these operators is an ordinary Prolog structure.
Prolog understands operator precedence, so 1 + 2 * 3
is the same as 1 + (2 * 3) and represents the structure
+(1, *(2, 3)).
An arithmetic expression is a number, a variable, or a compound expression built using these elements:
+ : addition- : subtraction* : multiplication/ : floating-point divisiondiv : integer division, rounding toward negative
infinitymod : modulus, i.e. remainder after integer division^ : exponentiationabs(X):
absolute valuemax(X,
Y) : maximum
of two valuesmin(X,
Y): minimum
of two valuescos(X), sin(X), tan(X):
trigonometric functionsNote that unlike most languages, Prolog does not automatically evaluate arithmetic expressions:
?- 2 + 3 = 3 + 2. false
+(2, 3) and +(3,
2) are not identical.?- X is 2 + 3. X = 5. ?- X is cos(pi). X = -1.0.
In classic Prolog, 'is' was the only way to perform arithmetic. Unfortunately, 'is' requires its right side to be a fully instantiated term, i.e. one with no variables:
?- 2 + 3 is X. ERROR: Arguments are not sufficiently instantiated ERROR: In: ERROR: [8] 2+3 is _6562 ERROR: [7] <user> ?- X is Y + 1. ERROR: Arguments are not sufficiently instantiated ERROR: In: ERROR: [8] _7580 is _7586+1 ERROR: [7] <user>
This means that 'is' is not part of the pure logical core of Prolog. Any predicate using 'is' is unlikely to work in multiple directions.
Modern Prolog includes integer constraints, which allow us to perfom arithmetic bidirectionally. In this course we will generally use integer constraints rather than 'is'.
To use these constraints in SWI-Prolog, you must import the clpfd
module:
?- use_module(library(clpfd)).
I recommend putting the preceding command into your
SWI-Prolog initialization file so that it will automatically
run at the beginning of each session. (Note that you must include the
?- prefix at the beginning of the line!) On SWI-Prolog
8.0 and earlier, this file is .swiplrc in your home
directory. If you are using SWI-Prolog 8.1 or later, it is in a
different
location.
Relational operators for
integer constraints begin with the '#' character, We have #=
(equals), #\=
(not equals), #<
(less than), #=< (less
than or equal), #> (greater
than) and #>= (greater
than or equal). Note
carefully the
unusual symbol ordering in the less than or equals operator #=<.
If you write the syntax #<= that
you might expect, you will get a syntax
error.
Prolog can combine integer constraints, and solve simple equations and systems of equations involving constraints:
?- X + 2 #= 3. X = 1 ?- X * X #= Y + 1, Y - 4 #= 20. Y = 24, X in -5\/5 ?- X #\= 10. X ininf..9\/11..sup
Above, '-5\/5' means 'either -5 or 5'. The \/
operator forms the union of two domains. Each domain is a single
integer, or a range of integers. inf ("inferior") means -∞
and sup ("superior") means +∞, so inf..9\/11..sup
means any value in the set (-∞, 9] ∪ [10, +∞), i.e. any integer
x such that x ≤ 9 or 11 ≤ x.
The in
operator states that
a variable belongs to a domain:
?- X in 1..10. X in 1..10
I recommend that you use this domain notation only when you have a fixed numeric range, since Prolog requires that the lower and upper bounds be known. The following will fail if Y is not yet known:
?- X in 1 .. Y. ERROR: Arguments are not sufficiently instantiated
In this situation, here is a better alternative:
?- X #>= 1, X #=< Y. X in 1..sup, Y#>=X, Y in 1..sup.
The ins operator is
similar in in,
but works for multiple variables at once:
?- [X, Y] ins 5..sup. X in 5..sup, Y in 5..sup ?- [X, Y] ins 0..2, Z #= X + Y, Z #= 0. X = Y, Y = Z, Z = 0
Sometimes Prolog's constraint propagation alone can find unique solutions for integer variables, as in the examples above. But sometimes it cannot:
?- X + Y #= 10, X - Y #= 2. 2+Y#=X, X+Y#=10
This system has a unique solution, but the constraint propagator
cannot find it (it is not smart enough to solve a linear system). In
this case and in more complicated examples, we will need to ask the
constraint system to search for
a solution. We can do this using the label
predicate, which finds solutions
for one or more variables. Note that in the above example, calling
label
alone is not enough:
?- X + Y #= 10, X - Y #= 2, label([X, Y]). ERROR: Arguments are not sufficiently instantiated
Every variable to label must belong to some domain that is bounded on at least one side, i.e. is not (-∞, ∞). If we add constraints stating that X and Y are positive, Prolog can find a solution:
?- X + Y #= 10, X - Y #= 2, X #> 0, Y #> 0, label([X, Y]). X = 6, Y = 4
Also note the useful predicate all_distinct that states
that a set of variables have distinct integer values:
?- [X, Y, Z] ins 1..3, X = 2, Y = 3, all_distinct([X, Y, Z]). X = 2, Y = 3, Z = 1
Modern Prolog also features real constraints, which let us
write predicates that use real (i.e. floating-point) numbers and work
bidirectionally. To use these constraints, you must import the clpr
module:
?- use_module(library(clpr)).
I recommend putting the preceding command into your SWI-Prolog initialization file (as described in the previous section).
Real constraints use a completely different syntax than integer constraints. To specify real constraints, write an expression in curly braces and use ordinary arithmetic operators (=, =\=, <, =<, >, or >=). Multiple constraints are separated by commas. For example:
?- {X + 2 = 3}.
X = 1.0
?- {X * X = Y + 1, Y - 4 = 20}.
X = 5.0,
Y = 24.0 ;
X = -5.0,
Y = 24.0Note the real constraint solver can solve linear systems:
?- { X + Y = 10, X - Y = 2}.
X = 6.0,
Y = 4.0sum([], 0). sum([I | L], J) :- sum(L, J1), I + J1 #= J. ?- sum([3, 4, 5], X). X = 12 ?- sum([3, X, 5], 12). X = 4 ?- sum([X, X, X], 12), X #> 0, label([X]). X = 4
len([], 0). len([_ | L], N) :- N #> 0, N #= K + 1, len(L, K). ?- len([a, b, c], N). N = 3. ?- len(L, 3). L = [_5424, _5610, _5796]
This predicate works and terminates in both directions. Here is some general advice for writing predicates that will terminate bidirectionally:
Constrain the arguments. In the above predicate, N
#> 0 states that N must be positive. When in doubt, it is
often better to add constraints, since redundant constraints will
not affect the results and are not especially expensive.
Make the recursive call last. This may seem counterintuitive: in the len predicate above, don't we want Prolog to first recursively compute the length of the sublist, and only afterward add 1 to produce the output value N? Prolog can remember constraints that you specify before a recursive call and combine them with other information later. Moving the constraints before a recursive call can only help termination.
Suppose the we represent a time of day using a structure such as
time(11, 26, 13), representing the time 11:26:13. We'd
like to write a predicate add(T1, N, T2), which says
that time T2 is N seconds after T1. Here is an implementation:
% Convert a time to a number of seconds after midnight.
convert(time(H, M, S), N) :-
H in 0 .. 23, [M, S] ins 0 .. 59, N #= 3600 * H + 60 * M + S.
% Add time T1 plus N seconds to form time T2.
add(T1, N, T2) :-
convert(T1, N1), convert(T2, N2), N1 + N #= N2.
Remarkably, add
will work in every
direction:
?- add(time(11, 30, 0), 75, T). T = time(11, 31, 15). ?- add(time(11, 30, 0), N, time(11, 31, 15)). N = 75. ?- add(T, 75, time(11, 31, 15)). T = time(11, 30, 0).
Write a Prolog program that can solve this cryptarithmetic puzzle:
A P P L E + G R A P E + P L U M =========== B A N A N A
Every letter stands for a different digit, and no leading digit may be zero.
rev_digits([], 0).
rev_digits([D | L], N) :- rev_digits(L, N1), N #= N1 * 10 + D.
% digits(L, N) is true if L is a list of digits (e.g. [3, 5, 2, 6]) and
% N is the corresponding decimal number (e.g. 3526).
digits(L, N) :- reverse(L, LR), rev_digits(LR, N).
solve(S1, S2, S3, R1) :-
S1 = [A, P, P, L, E],
S2 = [G, R, A, P, E],
S3 = [P, L, U, M],
R1 = [B, A, N, A, N, A],
List = [A, B, E, G, L, M, N, P, R, U],
List ins 0..9,
all_distinct(List),
[A, G, P, B] ins 1..9,
digits(S1, Apple),
digits(S2, Grape),
digits(S3, Plum),
digits(R1, Banana),
Banana #= Apple + Grape + Plum,
label(List).