Here are some fundamental predicates in Prolog. They all exist in the standard library, but let's see how we can implement them ourselves.
append(L,
M, N) is true if N is the concatenation of L and M.
append([], L, L). append([X | L], M, [X | N]) :- append(L, M, N).
'append' is a useful helper for writing many other predicates. For example, consider the predicate member(X, L), which is true if X is a member of L. Previously we saw how to write 'member' recursively. Alternatively, we can simply use 'append':
member(X, L) :- append(_, [X | _], L).
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. 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(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).The predicate reverse(L, M) is true if M is the list L reversed. Here is one possible implementation:
reverse([], [])
reverse([X | L], M) :- same_length([X | L], M),
reverse(L, LR), append(LR, [X], M).Unfortunately this implementation is inefficient. The call to append() will run in O(N) when there are N elements in the list LR, because it must make a copy of the the entire list in order to append X at the end. And so the running time of reverse() will be O(N2) for a list with N elements.
Later in this course we will see how to write reverse() so that it runs in O(N).
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:
point(4,5)
date(25,2,2020)
line(point(1.0,2.5), point(3.2,4.6))
box(box(a, b), c)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, _).
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.
->
=, <, >,
=<, >=
:
+, -
*, /, 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, in Prolog it is common to use the :
or -> operators to hold pairs of values:
?- X = 3 : 4. X = 3:4. ?- X = (3 -> 4). X = (3->4).
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.
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. 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.
We may represent a directed or undirected graph in Prolog using adjacency list representation. For example, consider this graph:
We will represent it using this list:
G = [ a -> [b, e], b -> [c, f], c -> [], d -> [],
e -> [d, f], f -> [a, c], g -> [d, h], h -> [f] ]This is a spatial representation. Previously, we saw how to represent graphs temporally using a 2-argument predicate. However, we will generally use a spatial representation of graphs from now on, since it is generally more convenient for implementing graph algorithms.