1.3. Structured terms#
Finally, we illustrate the way Prolog can handle more complex datastructures, such as a list of stations representing a route. Suppose we want to redefine the reachability relation, such that it also specifies the intermediate stations. We could adapt the non-recursive definition of reachable as follows:
reachable0(X,Y):-connected(X,Y,L).
reachable1(X,Y,Z):-connected(X,Z,L1),
connected(Z,Y,L2).
reachable2(X,Y,Z1,Z2):-connected(X,Z1,L1),
connected(Z1,Z2,L2),
connected(Z2,Y,L3).
The suffix of reachable indicates the number of intermediate stations; it is added to stress that relations with different number of arguments are really different relations, even if their names are the same. The problem now is that we have to know the number of intermediate stations in advance, before we can ask the right query. This is, of course, unacceptable.
We can solve this problem by means of functors. A functor looks just like a mathematical function, but the important difference is that functor expressions are never evaluated to determine a value. Instead, they provide a way to name a complex object composed of simpler objects. For instance, a route with Oxford Circus and Tottenham Court Road as intermediate stations could be represented by
route(oxford_circus,tottenham_court_road)
Note that this is not a ground fact, but rather an argument for a logical formula. The reachability relation can now be defined as follows:
reachable(X,Y,noroute):-connected(X,Y,_L).
reachable(X,Y,route(Z)):-connected(X,Z,_L1),
connected(Z,Y,_L2).
reachable(X,Y,route(Z1,Z2)):-connected(X,Z1,_L1),
connected(Z1,Z2,_L2),
connected(Z2,Y,_L3).
reachable(X,Y,noroute):-connected(X,Y,_L).
reachable(X,Y,route(Z,R)):-connected(X,Z,_L),
connected(Z,Y,R).
The query ?-reachable(oxford_circus,charing_cross,R) now has three possible answers:
{ R→route(piccadilly_circus) }
{ R→route(tottenham_court_road,leicester_square) }
{ R→route(piccadilly_circus,leicester_square) }
As argued in the previous section, we prefer the recursive definition of the reachability relation, in which case we use functors in a somewhat different way.
reachable(X,Y,noroute):-connected(X,Y,_L).
reachable(X,Y,route(Z,R)):-connected(X,Z,_L),
reachable(Z,Y,R).
At first sight, there does not seem to be a big difference between this and the use of functors in the non-recursive program. However, the query
?-reachable(oxford_circus,charing_cross,R).
now has the following answers:
{ R→route(tottenham_court_road, route(leicester_square,noroute)) }
{ R→route(piccadilly_circus,noroute) }
{ R→route(piccadilly_circus, route(leicester_square,noroute)) }
The functor route is now also recursive in nature: its first argument is a station, but its second argument is again a route. For instance, the object
route(tottenham_court_road,route(leicester_square,noroute))
can be pictured as in Figure 1.6. Such a figure is called a tree (we will have a lot more to say about trees in Chapter 4). In order to find out the route represented by this complex object, we read the leaves of this tree from left to right, until we reach the ‘terminator’ noroute. This would result in a linear notation like
[tottenham_court_road,leicester_square].
Figure 1.6 A complex object as a tree.#
For user-defined functors, such a linear notation is not available. However, Prolog provides a built-in ‘datatype’ called lists, for which both the tree-like notation and the linear notation may be used. The functor for lists is . (dot), which takes two arguments: the first element of the list (which may be any object), and the rest of the list (which must be a list). The list terminator is the special symbol [], denoting the empty list. For instance, the term
.(a,.(b,.(c,[])))
denotes the list consisting of a followed by b followed by c (Figure 1.7). Alternatively, we may use the linear notation, which uses square brackets:
[a,b,c]
To increase readability of the tree-like notation, instead of
.(First,Rest)
one can also write
[First|Rest]
Note that Rest is a list: e.g., [a,b,c] is the same list as [a|[b,c]]. a is called the head of the list, and [b,c] is called its tail. Finally, to a certain extent the two notations can be mixed: at the head of the list, you can write any number of elements in linear notation. For instance,
[First,Second,Third|Rest]
denotes a list with three or more elements.
Figure 1.7 The list [a,b,c] as a tree.#
A list is either the empty list [], or a non-empty list [First|Rest] where Rest is a list. Define a predicate list(L), which checks whether L is a list. Adapt it such that it succeeds only for lists of (1) even length and (2) odd length.
Tip
In SWISH you can render Prolog terms as trees by means of the use_rendering/1 predicate:
:-use_rendering(svgtree).
Notice that SWISH displays the tree functor as '[|]' rather than the dot ..
The recursive nature of such datastructures makes it possible to ignore the size of the objects, which is extremely useful in many situations. For instance, the definition of a route between two underground stations does not depend on the length of the route; all that matters is whether there is an intermediate station or not. For both cases, there is a clause. Expressing the route as a list, we can state the final definition of the reachability relation:
reachable(X,Y,[]):-connected(X,Y,_L).
reachable(X,Y,[Z|R]):-connected(X,Z,_L),
reachable(Z,Y,R).
The query ?-reachable(oxford_circus,charing_cross,R) now results in the following answers:
{ R→[tottenham_court_road,leicester_square] }
{ R→[piccadilly_circus] }
{ R→[piccadilly_circus,leicester_square] }
Note that Prolog writes out lists of fixed length in the linear notation.
Should we for some reason want to know from which station Charing Cross can be reached via a route with four intermediate stations, we should ask the query
?-reachable(X,charing_cross,[A,B,C,D]).
which results in two answers:
{ X→bond_street, A→green_park, B→oxford_circus,
C→tottenham_court_road, D→leicester_square }
{ X→bond_street, A→green_park, B→oxford_circus,
C→piccadilly_circus, D→leicester_square }.