Graphs generated by a predicate
4.2. Graphs generated by a predicate#
In the preceding section, a tree was represented by a Prolog term. This is convenient for relatively small trees such as proof trees, that are processed and passed around as a unit. However, for bigger trees it is a better idea not to represent them explicitly by a Prolog term, but implicitly by a set of ground facts, listing the arcs in the graph. An additional advantage of this representation is the possibility of representing graphs that are not trees.
As an example of this representation, the tree in Figure 4.2 would be represented by the following facts:
arc(n1,n2).
arc(n1,n3).
arc(n2,n4).
arc(n2,n5).
arc(n2,n6).
arc(n5,n7).
arc(n3,n8).
arc(n3,n9).
arc(n9,n10).
The predicate for finding a path in a graph now needs a few minor adjustments: the graph is not passed on as an argument, and arc/2 is used rather than term_arc/2:
% path(P) <- P is a path in the graph given by arc/2
path([Node1,Node2]):-
arc(Node1,Node2).
path([Node1,Node2|Nodes]):-
arc(Node1,Node2),
path([Node2|Nodes]).
Exercise 4.4 #
Draw the SLD-tree for the query ?-path([n1|Path]).
path/2 will generate paths between any two connected nodes. When searching a graph such as an SLD-tree, we are normally only interested in paths which start at a given node (for instance, the root of a tree), and end in a leaf. The following program will do the job. Note that this program differs from the previous one in that it allows for paths consisting of one node only.
% path_leaf(N,P) <- P is a path starting at node N, ending
% in a leaf in the graph given by arc/2
path_leaf(Leaf,[Leaf]):-
leaf(Leaf).
path_leaf(Node1,[Node1|Nodes]):-
arc(Node1,Node2),
path_leaf(Node2,Nodes).
leaf(Leaf):-
not(arc(Leaf,_SomeNode)).
The query ?-path_leaf(n1,Path) will lead to the following answers:
Path = [n1,n2,n4];
Path = [n1,n2,n5,n7];
Path = [n1,n2,n6];
Path = [n1,n3,n8];
Path = [n1,n3,n9,n10];
No more solutions
Exercise 4.5 #
Draw the SLD-tree for this query.
Notice the order in which the paths to the leafs are found – the longer path [n1,n2,n5,n7] is found before the shorter path [n1,n2,n6]. This kind of search is called depth-first search,n because the deepest unvisited nodes are preferred. In contrast,n breadth-first search tries all nodes on a given level before going one level deeper; consequently,n shortest paths are found first. Of course,n the order in which nodes are visited can only be understood procedurally – logically speaking,n there is nothing in the program which prescribes such an order. It is only because Prolog itself searches the SLD-tree in a depth-first fashion,n that programs like the above perform depth-first search.
In real life, graphs are often infinite. For instance, many SLD-trees are infinite, even for very simple programs such as (br abbreviates brother):
br(X,Y):-br(X,Z),br(Z,Y).
br(paul,peter).
SLD-trees are graphs, with resolvents as nodes. Representing a resolvent by the list of its literals, we would need an infinite number of facts to represent SLD-trees, for instance:
arc([br(paul,B)],[br(paul,Z),br(Z,B)]).
arc([br(paul,B)],[]).
arc([br(paul,Z),br(Z,B)],[br(paul,Z1),br(Z1,Z),br(Z,B)]).
arc([br(paul,Z),br(Z,B)],[br(peter,B)]).
arc([br(paul,Z),br(Z,B)],[br(paul,paul)]).
...
arc([br(peter,B)],[br(peter,Z),br(Z,B)]).
...
arc([br(paul)],[br(paul,Z),br(Z,paul)]).
...
In such cases, it is a better idea to write a program which generates these facts. In other words, we need a logical definition of arc/2.
Exercise 4.6 #
Sketch the SLD-tree for the query ?-br(paul,B).
Now, arc(A,B) is true if A and B are lists of negative literals interpreted as resolvents, and one resolution step applied to A and a clause for br/2 yields B. We can write this down by means of the predicate resolve/3, which performs one resolution step, and the two clauses for br/2 in the appropriate representation. This gives the following program:
arc(A,B):- resolve(A,(br(X,Y):-[br(X,Z),br(Z,Y)]),B).
arc(A,B):- resolve(A,(br(paul,peter):-[]),B).
% resolve(G,C,NewG) <- the goal G (a list of atoms)
% resolves with the clause C (body
% is a list) to yield the goal NewG
resolve([H1|T],(H2:-Body),B):-
H1=H2, % literal in goal unifies with head of clause
append(Body,T,B).
resolve([H|T],Clause,[H|B]):-
resolve(T,Clause,B). % try next literal
The query ?-arc([br(paul,B)],N) results in the answers
B = Y
N = [br(paul,Z),br(Z,Y)];
B = peter
N = []
as expected.
Note that a query of the form ?-arc(R,[]) asks for a path from R to a success branch in the SLD-tree, thus simulating a query :-R. That is, the above program for arc/2 is simply a meta-interpreter (with the object-level program hardwired in its clauses). In Section 5.3, we encounter a similar meta-interpreter for full clausal logic.