Some of this week's topics are discussed in the Bratko text (8.5.3 Last call optimizations and accumulators, 9.5 Graphs, 11.2 Depth-first search and iterative deepening).
Here's a predicate that adds numbers in a list:
% sum(L, N): N is the sum of numbers in L sum([], 0). sum([I | L], N) :- sum(L, N1), N #= N1 + I.
Given a list such as [3, 4, 5], this computes the sum 3 + (4 + (5 + 0)) = 12. The partial sums are computed from right to left.
Here's the same predicate, rewritten to use an accumulator.
sum(L, S) :- sum(L, 0, S). % accumulator is initially 0 % helper predicate: second argument is an accumulator sum([], S, S). sum([I | L], A, R) :- A1 #= A + I, sum(L, A1, R).
This computes the sum ((0 + 3) + 4) + 5 = 12. Notice that with an accumulator the partial sums are computed in a different order, i.e. from left to right. Of course, the result will be the same in either case, because addition is associative: (a + b) + c = a + (b + c).
Here's a predicate that reverses a list, naively:
reverse([], []). reverse([X | L], N) :- reverse(L, M), append(M, [X], N).
This will run in time O(N2) on a list with N elements. We can dramatically improve its efficiency using an accumulator, which lets us combine elements in the opposite direction:
reverse(L, R) :- reverse(L, [], R). % accumulator is initially [] % helper predicate: second argument is an accumulator reverse([], R, R). reverse([X | L], A, R) :- reverse(L, [X | A], R).
There's only one problem: both of these implementations of reverse
(either without or with an accumulator) will fail
to terminate when their first argument is an unbound variable:
?- reverse(L, [a, b, c]). L = [c, b, a] ; ERROR: Out of global stack ?-
As usual, the
same_length trick helps:
reverse(L, R) :- same_length(L, R), reverse(L, [], R). % helper predicate is same as before
Now queries will terminate in both directions.
In the lecture we also introduced higher-order predicates. (These are similar to higher-order functions, which we will see when we study Haskell in a few weeks.)
Higher-order predicates are not discussed in the Bratko text, so let's review them here.
The maplist predicate applies a predicate P to
elements of one or more lists, and succeeds if P always succeeds. It
is a higher-order predicate because its argument P is itself a
predicate. Let's look at a
few examples.
When maplist has two arguments, it applies a
predicate P to every element of a single list. Suppose that we have a
predicate odd:
odd(I) :- I mod 2 #= 1.
Now we can use maplist to test whether all integers in a
list are odd:
?- maplist(odd, [3, 5, 7]). true. ?- maplist(odd, [3, 4, 7]). false.
Consider the
following predicate, which states that up and down
are directions:
dir(up). dir(down).
We can use maplist to test whether all elements of a
list are directions. But we can also run maplist
backwards to generate lists
of directions:
?- maplist(dir, [up, down]). true. ?- length(L, 2), maplist(dir, L). L = [up, up] ; L = [up, down] ; L = [down, up] ; L = [down, down].
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 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 = [[_4144, _4150], [_4162, _4168, _4174]].
When maplist has four arguments, it applies a
predicate P to triples of arguments from three lists. You can
use this form if you have a three-argument predicate representing a
function of two arguments:
add(A, B, C) :- C #= A + B. ?- maplist(add, [1, 2, 3], [10, 11, 12], L). L = [11, 13, 15].
The first argument to maplist can be an atom naming a
predicate, as in the examples above. Or it can be a structure
containing a partially applied predicate, i.e. predicate name
plus one or more arguments. maplist will append any
additional arguments before applying the predicate. This is a
powerful and useful capability.
For example, we can add 5 to every element of a list like this:
?- maplist(add(5), [1, 2, 3], L). L = [6, 7, 8].
Another useful built-in higher-order function is foldl,
which can combine elements of a list using an arbitrary predicate.
Let's see foldl in action:
add(I, J, K) :- I + J #= K. ?- foldl(add, [3, 4, 5], 0, S). S = 12
The code above adds the members of the list [3, 4, 5], starting with the value 0. In other words, it computes ((0 + 3) + 4) + 5. This is called a left fold because it combines values from the left, just like the accumulators that we wrote in a section above.
In general, foldl takes four arguments: a predicate
of three arguments, a list, a starting value for the accumulator and
a final value for the accumulator. If we write
foldl(P, [a, b, c], V0, V)
then foldl will make a series of calls to P, with this effect:
P(a, V0, V1) P(b, V1, V2) P(c, V2, V)
Here are some more examples:
% Convert a list of digits (e.g. [4, 5, 6]) to an integer (e.g. 456). combine(I, J, K) :- K #= I + 10 * J. to_int(L, I) :- foldl(combine, L, 0, I). % An efficient implementation of reverse, using foldl. prepend(X, L, [X | L]). rev(L, M) :- same_length(L, M), foldl(prepend, L, [], M).
maplist and foldl are
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:
?- call(add, 2, 3, X). X = 5. ?- call(length, [2, 4], N). N = 2. ?- call(length, L, 2). L = [_9364, _9370].
As with maplist, the first argument to call
can be a partially applied
predicate:
?- call(add(2), 3, N). N = 5.
We can easily implement
maplist and foldl using call.
Here are 2- and 3-argument versions: of maplist:
maplist(_, []). maplist(P, [X | L]) :- call(P, X), maplist(P, L). maplist(_, [], []). maplist(P, [X | L], [Y | M]) :- call(P, X, Y), maplist(P, L, M).
Here is foldl:
foldl(_, [], V0, V0). foldl(P, [X | L], V0, VR) :- call(P, X, V0, V1), foldl(P, L, V1, VR).
We can represent a vector using a list of floating-point numbers,
and a matrix using a list of row vectors. maplist is
especially helpful for implementing vector and matrix operations.
Note that if we use clpr constraints, then all our predicates will
work in any direction. Some examples:
% helper predicates
add(I, J, K) :- { K = I + J }.
mul(I, J, K) :- { K = I * J }.
% multiply (scalar S) * (vector V) = (vector V1)
mul_sv(S, V, V1) :- maplist(mul(S), V, V1).
% multiply (scalar S) * (matrix M) = (matrix M1)
mul_sm(S, M, M1) :- maplist(mul_sv(S), M, M1).
% add (vector V1) + (vector V2) = (vector V)
add_vv(V1, V2, V) :- maplist(add, V1, V2, V).
% dot(V, W, X): X is the dot product of vectors V and W
dot(V, W, X) :- maplist(mul, V, W, Z), foldl(add, Z, 0, X).Here is a predicate to transpose a matrix, a slightly trickier operation:
% helper predicates elem(X, [X]). prepend(X, L, [X | L]). % base case: transpose 1 x N -> N x 1 trans([R], L) :- maplist(elem, R, L). % recursive case trans([R | M], N) :- maplist(prepend, R, N1, N), trans(M, N1).
There are various possible ways to represent a graph in Prolog. Consider this undirected graph:
We could represent the graph using a series of facts:
edge(a, c). edge(a, d). edge(a, f). edge(b, e). edge(c, b). edge(d, c). edge(d, e). edge(f, b).
This is sometimes called a temporal representation, because a query such as edge(a, V) will return a series of solutions over time.
Alternatively, we could use an adjacency list representation:
G = [a -> [c, d, f], b-> [e], c -> [b], d -> [c, d], e -> [], f -> [b]]
This is sometimes called a spatial representation, since the graph is represented using a data structure.
We can implement graph search algorithms on either sort of graph. For now, we will discuss how to search through a graph in temporal representation. That's because search algorithms on graphs in this representation will easily generalize to searching state spaces, such as searching for a solution to a Rubik's cube. We will see various examples of this soon.
Here is a
predicate dfs0(Start, Goal, Path) that searches for a
path from Start to Goal in a graph in temporal representation. If it
finds a path, it returns it in Path.
dfs0(Start, Start, [Start]).
dfs0(Start, Goal, [Start | Path]) :-
edge(Start, V), dfs0(V, Goal, Path).For example:
?- dfs0(a, e, Path). Path = [a, c, b, e]
Our undirected graph above was acyclic. Let's now consider a graph with a cycle:
Our predicate dfs0 may fail to terminate when searching for a path in this graph:
?- dfs0(a, e, Path)
(hangs)
That is because it may walk around a cycle forever. To remedy this, we must keep a visited set and avoid visiting any vertex twice. Let's enhance our depth-first search predicate to do that:
% recursive helper predicate
dfs(Start, Start, _, [Start]). % base case: start = goal
dfs(Start, Goal, Visited, [Start | Path]) :-
edge(Start, V), % find a next vertex
maplist(dif(V), Visited), % make sure not already visited
dfs(V, Goal, [V | Visited], Path). % recurse
% top-level predicate
dfs(Start, Goal, Path) :- dfs(Start, Goal, [Start], Path).Now we can find a path from a to e:
?- dfs(a, e, Path). Path = [a, c, b, e]
A major disadvantage of a depth-first search is that it is not
guaranteed to find a shortest path. For instance, in the previous
section the dfs predicate found the path [a, c, b,
e], but [a, d, e] is a shorter path from a to e.
When we are searching in an infinite state space, depth-first search
is not even complete, i.e. is not guaranteed to find a
solution at all, even if one exists. That's because it may recurse
infinitely in the wrong direction.
Another useful search algorithm is iterative deepening, which performs a series of depth-first searches, each of which has a maximum depth. The first depth-first search has depth limit 1, the second has limit 2, and so on. Iterative deepening will always find a shortest path to a goal, and is complete even in an infinite state space.
We can easily implement iterative deepening in Prolog using a simple trick, as follows:
iter_deep(Start, Goal, Path) :- length(Path, _), dfs(Start, Goal, Path).
Howe does this work? The goal length(Path, _) will
generate uninstantiated paths of increasing lengths:
?- length(Path, _). Path = [] ; Path = [_3610] ; Path = [_3610, _3616] ; Path = [_3610, _3616, _3622] ; Path = [_3610, _3616, _3622, _3628] ...
So iter_deep will make a series of calls to dfs,
each of which looks for a path of a particular length.
Iterative deepening is sometimes a useful technique. However, it
considers all possible paths of length (N - 1) before any path
of length N. In some state
spaces, this may be exponentially inefficient. For example,
suppose that our
state space has the
structure of a grid, with (0, 0) as the start state, and that we are
looking for the state (30,
30). At each step we may move up, down, left, or right. The
shortest path from (0, 0) to (30, 30) has length 60. Before we find
that, we will consider all paths of length 59. But there are an
enormous number of those. If iter_deep calls
dfs0,
then it will consider 459
paths of length 59, an
absurdly large number. If it calls dfs,
which avoids cycles, then it will not consider paths that visit the
same state twice, but there will still be an enormous number of such
paths of length 59.
To avoid this inefficiency, we must implement a breadth-first search that uses a visited set. We will see how to do that in Prolog next week.