Prolog includes various predefined operators, which are
actually functors. Most operators consist of punctuation 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.
->
=, <,
>, =<, >=
:
+, -
*, /,
div, mod
**
^
+, -
(unary)
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].
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.
Let's represent a key/value pair as a structure K
: V.
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. So the queries above 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.
Suppose that Prolog did not include built-in arithmetic. Could we define our own numbers using structures?
Actually we could, and it would not be difficult. Consider the
natural numbers ℕ = 0, 1, 2, ..., and choose the following
representation: the atom z will represent zero, and the
structure s(X) will represent the successor of X. So we
have
z = 0
s(z) = 1
s(s(z)) = 2
...
We may write a recursive predicate add(A, B, C) that
adds two natural numbers in this representation:
add(A, z, A). add(A, s(B), s(C)) :- add(A, B, C).
It will work in any direction, so we may use it to either add or subtract:
?- Two = s(s(z)), Three = s(Two), add(Two, Three, N). Two = s(s(z)), Three = s(s(s(z))), N = s(s(s(s(s(z))))). ?- Two = s(s(z)), Three = s(Two), add(Two, N, Three). Two = s(s(z)), Three = s(s(s(z))), N = s(z). ?- Two = s(s(z)), Three = s(Two), add(Three, N, Two). false.
Now let's write a predicate le(A, B) that is true if A ≤
B, where A and B are natural numbers in this representation. Here is
a recursive implementation:
le(z, _). le(s(A), s(B)) :- le(A, B).
Alternatively, we may just call add():
le(A, B) :- add(A, _, B).
This predicate will also work bidirectionally:
?- le(s(s(z)), N). N = s(s(z)) ; N = s(s(s(z))) ; N = s(s(s(s(z)))) ; ... ?- le(N, s(s(z))). N = s(s(z)) ; N = s(z) ; N = z
The syntax s(s(s(s(s(z))))) is a bit ugly. Instead of
the s() functor, we may use a prefix operator, such as
the built-in unary operator '+'. We will have
z = 0
+ z = 1
+ + z = 2
...
Let's rewrite our add() predicate using this syntax:
add(z, I, I). add(+ I, J, + K) :- add(I, J, K).
Now our queries will look a bit nicer. For example:
?- Two = + + z, Three = + + + z, add(Two, Three, N). Two = + +z, Three = + + +z, N = + + + + +z. ?- Two = + + z, Three = + + + z, add(Two, N, Three). Two = + +z, Three = + + +z, N = +z.
It's nice that we can define our own numbers. However, internally Prolog does not store its own integers using this representation, which would be extremely inefficient for performing arithmetic on numbers that are not small. (Instead it uses machine words that it can manipulate using CPU instructions, just like other languages.)
Suppose that Prolog did not have built-in lists. Could we define them using structures?
Actually we could, very easily. Let's use the atom nil
to represent the empty list. cons(X, L) will represent
the value X prepended to the list L. So, for example, the list
containing 3, 4, and 5 will be represented as cons(3, cons(4,
cons(5, nil))).
With this list representation, let's write member()
and append():
member(X, cons(X, _)). member(X, cons(_, L)) :- member(X, L). append(nil, L, L). append(cons(X, L), M, cons(X, N)) :- append(L, M, N).
These predicates will work just as on ordinary lists, and in any direction:
?- member(5, cons(3, cons(5, cons(7, nil)))). true ?- member(5, cons(3, cons(X, cons(7, nil)))). X = 5 ?- append(cons(3, cons(5, nil)), cons(7, cons(9, nil)), L). L = cons(3, cons(5, cons(7, cons(9, nil)))).
The syntax with the cons functor is awkward when lists
have more than a couple of elements. As an alternative, let's use
operator syntax instead. We will use the built-in infix operator :
for prepending, so that X : L will represent the value X
prepended to the list L. With this syntax, our predicates will now
look like this:
member(X, X : _). member(X, _ : L) :- member(X, L). append(nil, L, L). append(X : L, M, X : N) :- append(L, M, N).
Queries are now much easier to read:
?- member(X, 3 : 5 : 7 : nil). X = 3 ; X = 5 ; X = 7 ?- append(2 : 3 : 4 : nil, 5 : 6 : nil, L). L = 2:3:4:5:6:nil.
In fact this syntax is arguably easier to read than Prolog's own list
syntax, since A : B looks simpler than [A | B].
We have seen that Prolog's structures are quite general. We can use them to implement numbers, lists, and many other useful data types as well.
Suppose that we have a predicate pos(X) that succeeds
if an integer X is positive. We may recursively write a predicate
all_pos(L) that is true if all elements of a list are
positive:
pos(X) :- X #> 0. all_pos([]). all_pos([X | L]) :- pos(X), all_pos(L).
Now suppose that we have a predicate even(X) that
succeeds if an integer X is even. Similarly, we may write a predicate
all_even(L):
even(X) :- X mod 2 #= 0. all_even([]). all_even([X | L]) :- even(X), all_even(L).
It's awkward that we have to write the same recursive pattern in each
of the examples above. Instead, we can use the built-in predicate
maplist(). We can write all_pos() and
all_even() more simply as follows:
all_pos(L) :- maplist(pos, L). all_even(L) :- maplist(even, L).
maplist(P, L) applies a predicate P to every element of
a list L, and succeeds if P succeeds on every element. It is a
higher-order predicate because its argument P is itself a
predicate.
As another example, suppose that we'd like to write a predicate
all_dif(X, L) that is true if every element of L is
different from X. We could write this predicate recursively:
all_dif(_, []). all_dif(X, [Y | L]) :- dif(X, Y), all_dif(X, L).
Alternatively, we can write it using maplist:
all_dif(X, L) :- maplist(dif(X), L).
In this rule, dif(X) is a partially applied
predicate. As we know, the dif predicate takes two
arguments; for example, dif(a, b) is true. The form
dif(X) gives dif its first argument;
maplist will pass each member of L in turn as the second
argument to dif. If all of those calls succeed, i.e.
every element of L is different from X, then maplist
itself will succeed.
We may even partially apply the built-in equality predicate '=':
?- length(L, 7), maplist(=(4), L). L = [4, 4, 4, 4, 4, 4, 4].
Sometimes when we use partially applied predicates, the order of
arguments in an existing predicate is inconvenient. For example,
suppose that we'd like to write a predicate subset(L, M)
which is true if L is a subset of M, i.e. every member of L is a
member of M. We already have the built-in predicate member(X,
L), which succeeds if X is a member of L. We might try to
write subset() like this:
subset(L, M) :- maplist(member(M), L). % WRONG
However this is wrong. The problem is that the first argument of
member() is not a list; it is the member element.
As a workaround, we can write a predicate member_of()
that is like member, but with its arguments swapped:
% member_of(L, X) - true if X is a member of L member_of(L, X) :- member(X, L).
And now we can write subset() using maplist:
subset(L, M) :- maplist(member_of(M), L).
The order of arguments may also be inconvenient if we use partially applied comparison operators. For example, consider the following query:
?- maplist(#>(5), [8, 9, 10]). false.
At first glance, the result above may be surprising, since it looks like the query is testing whether all list elements are greater than 5. However, the query is actally testing whether 5 is greater than each of the list elements! In other words, its first test will be 5 #> 8. That's because the first argument to the #> operator is 5, since it's supplied by the partial application.
When maplist() has three arguments, it applies a predicate P to
corresponding pairs of elements from two lists. For example,
maplist(P, [1, 2, 3], [4, 5, 6])
will invoke P(1, 4), P(2, 5) and P(3,
6). maplist() will succeed if all of these
invocations succeed.
You can use this form to compare list elements, for example:
less(I, J) :- I #< J. ?- maplist(less, [1, 2, 3], [4, 5, 6]). true.
The preceding query succeeds because 1 < 4, 2 < 5, and 3 < 6.
Alternatively, you can pass maplist() a predicate
representing a function that you want to apply to every element of a
list:
double(I, J) :- J #= I * 2. ?- maplist(double, [1, 2, 3], [2, 4, 6]). true. ?- maplist(double, [1, 2, 3], L). L = [2, 4, 6].
If the function works
in both directions then maplist() will too:
?- maplist(length, [[10, 11], [12, 13, 14]], L). L = [2, 3]. ?- maplist(length, L, [2, 3]). L = [[_, _], [_, _, _]].
Suppose that we have a mapping between numbers and words:
num(1, one). num(2, two). num(3, three). num(4, four).
We may use maplist() to apply the mapping to an entire list:
?- maplist(num, [2, 2, 3, 4], L). L = [two, two, three, four]. ?- maplist(num, L, [two, two, three, four]). L = [2, 2, 3, 4].
Let's write a predicate that will add an integer N to every element of a list, using a partially applied predicate:
add(I, J, K) :- I + J #= K. add_n(N, L, M) :- maplist(add(N), L, M). ?- add_n(7, [10, 20, 30], L). L = [17, 27, 37].
When maplist() has four arguments, it applies a
predicate P to triples of arguments from three lists. For
example, we may use this form to add two vectors:
add(A, B, C) :- A + B #= C. ?- maplist(add, [1, 2, 3], [10, 11, 12], L). L = [11, 13, 15].
maplist() is actually built from a more primitive
predicate call(). call() is itself a
higher-order predicate, and invokes the predicate it is given,
appending additional arguments:
add(A, B, C) :- A + B #= C. ?- call(add, 2, 3, X). X = 5. ?- call(length, [2, 4], N). N = 2. ?- call(length, L, 2). L = [_, _].
The first argument to call() can be a partially
applied predicate:
?- call(add(2), 3, N). N = 5. ?- call(add(2, 3), N). N = 5.
We can easily implement
maplist() using call(). Here is the
2-argument version:
maplist(_, []). maplist(P, [X | L]) :- call(P, X), maplist(P, L).
In Prolog we can easily represent a matrix using nested lists. For example, the matrix
1 2 3 4 5 6 7 8 9
has the representation [[1, 2, 3], [4, 5, 6], [7, 8, 9]].
maplist() is convenient for peforming
operations on matrices in this representation. For example, suppose
we'd like to write a predicate add_mm() to add two
matrices. Above, we saw that we can easily add two vectors using
maplist(). Let's write a predicate add_vv()
to do that:
add(A, B, C) :- A + B #= C. % add vectors V + W = X add_vv(V, W, X) :- maplist(add, V, W, X).
Let's try it:
?- add_vv([1, 2], [3, 4], X). X = [4, 6].
Now using add_vv() we can easily write a
predicate add_mm() to add two matrices:
% add matrices M + N = P add_mm(M, N, P) :- maplist(add_vv, M, N, P).
Let's try it:
?- add_mm([[1, 2], [3, 4]], [[5, 6], [7, 8]], M). M = [[6, 8], [10, 12]].
We can even use it to subtract matrices:
?- add_mm([[1, 2], [3, 4]], M, [[6, 8], [10, 12]]). M = [[5, 6], [7, 8]].
We will practice writing more matrix predicates in the tutorial and/or homework.
We may use graph search algorithms to search in state spaces, which allows us to solve many sorts of problems and puzzles.
As a first trivial example, consider this problem. There are three coins on a table. Initially the first two coins are heads up, and the third is tails up:
H H T
We would like to make three coin flips and end up in a state where the three coins are either all heads up or all tails up. We want to write a Prolog predicate that can determine all possible solutions.
Let's represent a state via a list of three atoms, e.g. [h,
h, t]. We can write a predicate next() that
defines how we may move from one state to the next:
flip(h, t). flip(t, h). % next(S, T) - from state S we can make a move to state T. next(S, T) :- select(X, S, Y, T), flip(X, Y).
For example:
?- next([h, h, t], T). T = [t, h, t] ; T = [h, t, t] ; T = [h, h, h]
Now let's write a predicate path() that can find all
paths from a state S to any final state:
final([h, h, h]). final([t, t, t]). % path(S, P): P is a path from S to a final state. path(S, [S]) :- final(S). path(S, [S | P]) :- next(S, U), path(U, P).
We want to make three coin flips, so any valid path will have 4 states since it includes both the initial and final states. We can now find all possible solutions:
?- length(P, 4), path([h, h, t], P). P = [[h, h, t], [t, h, t], [h, h, t], [h, h, h]] ; P = [[h, h, t], [t, h, t], [t, h, h], [h, h, h]] ; P = [[h, h, t], [h, t, t], [h, h, t], [h, h, h]] ; ...
Let's try to find any solution at all from the starting state:
?- path([h, h, t], P). <hang>
This query hangs because the depth-first search is considering an infinite path in which it flips the first coin at every step: [h, h, t], [t, h, t], [h, h, t], ... It will never find a solution.
Instead, we can use iterative deepening to find all solutions in increasing order of length:
?- length(P, _), path([h, h, t], P). P = [[h, h, t], [h, h, h]] ; P = [[h, h, t], [t, h, t], [t, t, t]] ; P = [[h, h, t], [h, t, t], [t, t, t]] ; P = [[h, h, t], [t, h, t], [h, h, t], [h, h, h]] ; P = [[h, h, t], [t, h, t], [t, h, h], [h, h, h]] ; ...
How does this work? The goal length(P, _) will generate
uninstantiated paths of increasing lengths:
?- length(P, _). P = [] ; P = [_] ; P = [_, _] ; P = [_, _, _] ; P = [_, _, _, _] ...
So the query length(P, _), path([h, h, t], P) will make
a series of calls to path. The query will first search
for a path of length 0, then a path of length 1 and so on.
Recall that a breadth-first search will find the shortest path to a goal, but in general a depth-first search will not. Iterative deepening is a useful technique because it can find a shortest path even when we are using depth-first searches. Since Prolog's own search is depth-first, it is especially appopriate in Prolog.
On the other hand, iterative deepening has some weaknesses. Our code above might visit the same state repeatedly, which could be undesirable in some searches. Furthermore, if there is no solution then an iterative deepening search in the form we've written it will search forever, even if the search space is finite.
So we might instead want to implement a classic breadth-first search with a visited in Prolog. We'll see how to do that in the next lecture.
Let's look at another classic state space search exercise in Prolog: the monkey and bananas problem.
Consider a simple world with positions A, B, and C. A monkey begins at position A. There is a box at position B. At position C there are some bananas hanging from the ceiling.
At each step, the monkey may take any of the following actions:
• go(P)
– go to position P
• push(P)
– push the box (which must be at the monkey's current position) to
position P
• climb_on
– climb onto the box (which must be at the monkey's current
position)
• climb_off
– climb off the box (only if the monkey is currently on the box)
• eat
– eat the bananas (only if the monkey is on the box under the
bananas)
How can the monkey eat the bananas?
To solve this in Prolog, we must first invent a representation for the state of the world. We can use a list with 3 elements:
the
monkey's position (either a, b, or c,
or box if the monkey is standing on the box)
the
box's position (either a, b, or c)
the
position of the bananas (either c,
or gone
if the monkey has eaten them)
The
start state is [a, b, c].
Now
let's write a predicate next(A, S, T) that is true if
the action A leads from state S to state T. We ean easily represent
actions using Prolog structures. Here is the predicate:
pos(a). pos(b). pos(c). next(go(P), [Mon, Box, Ban], [P, Box, Ban]) :- pos(P). next(push(P), [Mon, Box, Ban], [P, P, Ban]) :- pos(P), Mon = Box. next(climb_on, [Mon, Box, Ban], [box, Box, Ban]) :- Mon = Box. next(climb_off, [box, Box, Ban], [Box, Box, Ban]). next(eat, [box, Box, Ban], [box, Box, gone]) :- Box = Ban.
Next, let's write a predicate path(S, G, P) that is true if P is a series of actions leading from the start state S to the goal state G:
path(S, S, []). path(S, G, [A | P]) :- next(A, S, T), path(T, G, P).
Finally, we can use iterative deepening to find the shortest path from the start to the goal:
?- length(P, _), path([a, b, c], [_, _, gone], P). P = [go(b), push(c), climb_on, eat]
The monkey walks to position B, pushes the box to position C, climbs on the box, then eats the bananas.
Obviously this problem is not difficult, but this example shows that in Prolog we can express search problems such as this one quite naturally.