Week 3: Notes

searching with integer constraints

Sometimes Prolog can solve a set of integer constraints directly:

?- X * 2 #= Y, Y + 5 #= 11.
X = 3,
Y = 6.

?- X #> 5, X #< 7.
X = 6.

In other situations it cannot, and just reports a list of constraints:

?- X in 1..50, X mod 3 #= 2, X mod 7 #= 3.
X in 17..38,
X mod 7#=3,
X mod 3#=2.

(It's interesting that in this example Prolog has at least managed to reduce the range of possible solutions).

When this happens, you may wish to search for solutions by trying values individually. As one possiblity, you can construct a list of possible solutions, and try every member:

?- numlist(1, 50, L), member(X, L), X mod 3 #= 2, X mod 7 #= 3.
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
X = 17 ;
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
X = 38

As another possibility, we can use the between() predicate to generate possible values:

?- between(1, 50, X), X mod 3 #= 2, X mod 7 #= 3.
X = 17 ;
X = 38

As yet another possibliity, we can call the label() method, which asks Prolog's integer solver to try all possible values in turn:

?- X in 1..50, X mod 3 #= 2, X mod 7 #= 3, label([X]).
X = 17 ;
X = 38.

floating-point numbers

Prolog supports floating-point numbers:

?- X = 14.3.
X = 14.3.

Notice that the = operator will never consider integers and floating point numbers to be equal, since they are structurally different:

?- 1 = 1.0.
false.

The old-style 'is' operator and the comparison operators <, =<, >, and >= will work with floats:

?- X is 4.5 + 2.2.
X = 6.7.

?- 4.8 < 10.0.
true.

The '/' operator performs floating-point division:

?- X is 9.0 / 2.0.
X = 4.5.

The abs(), min() and max() functions mentioned above will also work on floating-point numbers. Furthermore, in floating-point expressions we may use the constants e and pi, and the trigonometric functions sin(), cos(), and tan():

?- X is cos(pi).
X = -1.0.

?- X is e^2.
X = 7.3890560989306495.

new-style floating-point arithmetic

Because 'is' and the comparison operators such as '<', '=<' have limitations as described above, usually we will want to use new-style floating-point expressions, which are based on real constraints. To enable these, add this line to your init.pl file as described above:

:- use_module(library(clpr)).

New-style floating-point expressions use a completely different syntax from integer expressions. Instead of using operators such as #= and #<, we write floating-point expressions using ordinary operators such as '=', '<', '=<', but written inside braces. For example:

?- { X = 2 + 3 }.
X = 5.0

?- { 2 + 3 = X }.
X = 5.0

?- { X + 2 = 5 }.
X = 3.0

?- { X + 1 = X }.
false.

?- { X * 2 = 10 }.
X = 5.0

?- { X * 2 = 9 }.
X = 4.5

?- { 2^X = 128 }.
X = 7.0

?- { 2^X = 100 }.
X = 6.643856189774725

?- { X^2 = 16 }.
X = 4.0 ;
X = -4.0

Notice that the last query above reports two solutions separately, unlike the integer solver which was able to combine them into a single result.

Prolog's real solver can also work with inequalities, though it doesn't support the range syntax (e.g. "4..8") that we saw with integer constraints:

?- { 4 =< X, X =< 6 }.
{X>=4.0, X=<6.0}.

?- { 10 < X, X < 30, 20 < X, X < 40 }.
{X>20.0, X<30.0}.

?- { X^2 = 16, X > 0 }.
X = 4.0

Unlike the integer solver, the real solver can actually solve systems of linear equations:

?- { X + Y + Z = 9, X + Y - Z = -1, X + 2 * Y + 3 * Z = 22 }.
X = 1.0,
Y = 3.0,
Z = 5.0.

However it cannot solve a quadratic equation:

?- { X^2 - X - 2 = 0 }.
{-2.0-X+X^2=0.0}.

Let's write a few predicates using floating-point arithmetic:

% X, Y, Z are sides of a right triangle
triangle(X, Y, Z) :- { X > 0, Y > 0, Z > 0, X^2 + Y^2 = Z^2 }.

% C = celsius, F = fahrenheit
temperature(C, F) :- { F = 9 / 5 * C + 32 }.

% currency conversion
currency(Kc, Eur, USD) :- { 1.13 * Eur = USD, 21.7 * USD = Kc }.

They all work multidirectionally:

?- triangle(5, 12, H).
H = 13.0

?- triangle(5, X, 10).
X = 8.660254037844387

?- temperature(10, F).
F = 50.0

?- temperature(C, 50).
C = 10.0

?- currency(1000, Eur, USD).
Eur = 40.78137106969537,
USD = 46.082949308755765

?- currency(Kc, Eur, 1000).
Kc = 21700.0,
Eur = 884.9557522123895

more list predicates

select

The library predicate select(X, L, M) is true if we can remove X anywhere in L to make M. Equivalently, it's true if we can insert X anywhere in M to make L. We wrote this predicate in last week's tutorial, but it's fairly fundamental so let's review it again now.

One possible implementation of 'select' is recursive:

select(X, [X | L], L).
select(X, [Y | L], [Y | M]) :- select(X, L, M).

As another approach, we may write 'select' using 'append':

select(X, L, M) :- append(A, [X | B], L), append(A, B, M).

Unfortunately this predicate fails to terminate for some queries:

?- select(a, L, [b, c, d]).
L = [a,b,c,d] ;
L = [b,a,c,d] ;
L = [b,c,a,d] ;
L = [b,c,d,a] ;
<hang>

The problem is that the first goal 'append(A, [X | B], L)' may produce an infinite number of results:

?- X = a, append(A, [X | B], L).
X = a,
A = [],
L = [a|B] ;
X = a,
A = [_A],
L = [_A, a|B] ;
X = a,
A = [_A, _B],
L = [_A, _B, a|B]
...

If the first goal produces an infinite number of results, then Prolog's depth-first search can never terminate (at least in the pure core language that we have studied so far).

To help Prolog's search terminate, we need to add a constraint that limits the search space. Whenever select(X, L, M) is true, L must have one more element than M. Let's add a constraint that says that:

select(X, L, M) :- same_length(L, [_ | M]), append(A, [X | B], L), append(A, B, M).

Now the predicate will terminate in any direction. If the caller specifies L, then the call to same_length() will fix the length of M. If the caller specifies M, then the call to same_length() will fix the length of L. In either case, since the lengths of L and M are known, the following calls to append() will produce only a finite number of solutions, and so the predicate 'select' will terminate either as written above, or even if we swap the two calls to 'append'.

Adding a call to same_length() will help many other list-based predicates terminate as well. I call this the 'same_length trick'.

select, with 4 arguments

The library predicate select(X, L, Y, M) is true if we can replace X with Y at any single position in L to make M. We can write this predicate recursively:

select(X, [X | L], Y, [Y | L]).
select(X, [Z | L], Y, [Z | M]) :- select(X, L, Y, M).

Or we can call append() twice. Once again, we must use the same_length trick in order for the predicate to terminate in both directions:

select(X, L, Y, M) :- same_length(L, M), 
                      append(A, [X | B], L), append(A, [Y | B], M).

permutation

The library predicate permutation(L, M) is true if L is a permutation of M (or, equivalently, M is a permutation of L). Let's write it:

permutation([], []).
permutation(L, [X | M]) :- same_length(L, [X | M]),
    select(X, L, L1), permutation(L1, M).

nested lists

A list may contain sublists:

?- L = [[a, b], [c, d], [e, f]].
L = [[a, b], [c, d], [e, f]].

In Prolog, two lists are equal if they have the same structure and elements:

?- [[a, b], [c, d], [e, f]] = [[a, b], [c, d], [e, f]].
true.

To put it differently, equality is deep and recursive.

Prolog can perform unification even between nested lists:

?- [[X, Y], [A, B]] = [L, [3, 4]].
A = 3,
B = 4,
L = [X, Y].

?- [[X, Y], [A, B]] = [[3, X], [B, A]].
X = Y, Y = 3,
A = B.

As an example of a predicate that uses nested lists, let's write a predicate flatten(LL, L) that is true if L is the concatenation of all lists in LL:

flatten([], []).
flatten([L | LL], M) :- append(L, M1, M), flatten(LL, M1).

?- flatten([[a, b], [c, d], [e, f]], L).
L = [a, b, c, d, e, f].

?- flatten([[a, b], L, [e, f]], [a, b, c, d, e, f]).
L = [c, d]

As usual, placing the recursive call last helps the predicate terminate in both directions.

Actually this predicate is also built into the standard library – it's called append, with two arguments:

?- append([[a, b], [c, d], [e, f]], L).
L = [a, b, c, d, e, f].

structures

A structure is a kind of term that consists of a functor and zero or more arguments. The functor has the same syntax as an atom. The components are arbitrary terms. Here are some examples:

Two structures are equal only if they have the same functor name and the same arguments. Prolog can perform unification between arbitrary structures:

?- foo(3, 4, X) = foo(Y, 4, 5).
X = 5,
Y = 3.

?- foo(3, 4, X) = bar(Y, 4, 5).
false.

?- foo(3, 4, X) = foo(3, Y).
false.

?- a(X) = Y.
Y = a(X).

?- Y = a(X), Z = b(Y).
Y = a(X),
Z = b(a(X)).

We may define predicates that use structures. For example, here is a predicate that reverses the elements of a pair, where we represent pairs using a functor 'pair':

flip(pair(X, Y), pair(Y, X)).

Let's try it:

?- flip(pair(3, 4), P).
P = pair(4, 3).

?- flip(P, pair(4, 3)).
P = pair(3, 4).

?- flip(P, Q).
P = pair(_A, _B),
Q = pair(_B, _A).

Notice that predicates and structures have a similar syntax. Be sure to understand that in the clause above, 'flip' is a predicate and 'pair' is a functor.

As another example, suppose that we represent points (X, Y) using a structure 'point(X, Y)', and that we represent a line between two points P and Q using a structure 'line(P, Q)'. Now we may write predicates that succeed if a line is vertical or horizontal:

vertical(line(point(X, _), point(X, _))).
horizontal(line(point(_, Y), point(_, Y))).

Let's make some queries:

?- vertical(line(point(2, 4), point(2, 6))).
true.

?- vertical(line(point(1, 1), point(1, Y))).
true.

?- vertical(line(point(1, 1), point(2, Y))). 
false.

?- vertical(line(point(2, 3), P)).
P = point(2, _).

adding times

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).

operator syntax

Prolog includes various predefined operators, which are actually functors. Most operators consist of punctuaction symbols (e.g. +, *, /), but some contain letters (e.g. div, mod). Operators may either be binary operators, which take two arguments, or unary operators, which take only one.

An operator may be followed by a parenthesized argument list just like with ordinary functors, but usually we will write binary operators with infix syntax. The same structure will be produced in either case:

?- X = +(3, 2).
X = 3+2.

?- X = 3 + 2.
X = 3+2.

Most unary operators use prefix syntax, meaning that they precede their argument:

?- X = + a.
X = +a.

?- X = + + a.
X = + +a.

As we can see above, there is a binary operator '+' and also a separate unary operator '+'.

Here is a table listing some of Prolog's predefined operators. The table lists operators from lowest to highest precedence; operators on the same line have equal precedence. All operators are binary unless otherwise specified.

As we have seen, some of these operators have specific meanings in arithmetic expressions. However, these operators do not all have an arithmetic meaning. And actually we can use any of these operators to hold any data that we like, and may use them even in non-arithmetic contexts.

For example, suppose that we use the operator / for representing pairs of values:

?- X = a / b.
X = a/b.

Let's write a predicate zip() that will zip two lists of items into a list of pairs:

zip([], [], []).
zip([X | L], [Y | M], [X / Y | N]) :- zip(L, M, N).

?- zip([a, b, c], [d, e, f], L).
L = [a/d, b/e, c/f].

We may even run it in reverse to unzip:

?- zip(L, M, [a/d, b/e, c/f]).
L = [a, b, c],
M = [d, e, f].

disabling printing anonymous variables

I recommend that you add this line to your init.pl file:

:- set_prolog_flag(toplevel_print_anon, false).

This will disable the printing of anonymous variables in the REPL. An anonymous variable is any variable whose name begins with an underscore (_). These variables are sometimes convenient for simplifying the output that queries produce, as we will see shortly.

dictionaries

Often we may wish to map keys to values. We have already seen that we may represent such a mapping using a 2-argument predicate:

color(red, 10).
color(green, 20).
color(blue, 30).
color(green, 40).

This is called a temporal representation of the data. "temporal" means related to time. When we query this predicate, we get results one at a time:

?- color(K, V).
K = red,
V = 10 ;
K = green,
V = 20 ;
K = blue,
V = 30 ;
K = green,
V = 40.

Alternatively, we may want a spatial representation of the data, i.e. to hold all the keys and values in a single dictionary data structure. A simple dictionary representation in Prolog is an association list, which is simply a list of key/value pairs. As we saw above, it's convenient to use operator syntax for pairs. Here, let's use the ':' operator so that our dictionaries will look something like Python dictionaries.

For example, here is a dictionary:

colors(D) :- D = [ red : 10, green : 20, blue : 30, orange : 40 ].

Prolog does not have traditional global variables, but we can use a predicate such as this as a workaround. If we want access to this dictionary at any place in our program, we can simply call the predicate to assign it to a variable of our choice.

Let's now write a predicate 'lookup' that will let us look up keys in any dictionary:

lookup(D, K, V) :- member(K : V, D).

Now we may look up keys in the dictionary above. As usual, queries work in both directions, so we may even map values back to keys:

?- colors(_D), lookup(_D, blue, X).
X = 30

?- colors(_D), lookup(_D, C, 20).
C = green

?- colors(_D), lookup(_D, K, V).
K = red,
V = 10 ;
K = green,
V = 20 ;
K = blue,
V = 30 ;
K = orange,
V = 40.

Notice that _D is an anonymous variable since it begins with an underscore. If you've enabled the toplevel_print_anon flag as described in the previous section, these queries won't print _D out, which would only clutter the output.

We have seen that we can encode a key/value mapping either temporally (using a 2-argument predicate) or spatially (using a dictionary data structure). Which approach is better? Either is reasonable in Prolog, and the best approach may depend on the problem we are trying to solve. However, note that we can easily translate a spatial to a temporal representation: the last query above does exactly that. On the other hand, we cannot translate a temporal representation to a spatial representation using the subset of Prolog that we know so far.