Module 4, part 1

Breaking the network

In the previous Module, the network was deterministic in the sense that it was always possible to reach node b from any starting node: there are no paths that do not lead to the final goal. However, if we introduce a break in the network we can observe Prolog's method of searching in more detail.

We will remove one arc from the simple network. The one chosen is that between nodes 5 and 8. (This can be done in the Prolog program either by deleting the fact path(5, 8). or (better) by inserting a single line comment ('%') before it.)

We will use the two rules in the procedure route/2 that we developed in the previous Module:

     % 1
     route(Start, End) :-
          path(Start, End).
     % 2
     route(Start, End) :-
          path(Start, Via),
          route(Via, End).

We will start with the query:

     | ?- route(a, b).

Let's look at how this query works through the network using the path/2 procedure ordered in exactly the same way as in the previous Module. Given a query such as the above, Prolog looks through its database of procedures to find the one that matches. It will then look at each clause in the procedure until it finds one that matches. Our query matches the head of the first rule. If you are not certain of a matching, simply try it out with the Prolog interpreter as you did in the first Module, ie:

     | ?- route(a, b) = route(Start, End).

     End = b,
     Start = a ?

     yes

The first rule tries to find a procedure: path(a,b). This doesn't occur in the database, so this route/2 %1 doesn't succeed. Prolog doesn't give up, but looks for an alternative clause in the procedure. The head of route/2 %2 matches, and so Prolog tries the goals in the body of the rule. The variable Start has been instantiated to a and the variable Via doesn't have a value. There is a fact in the database that will match with this. Try the following query:

     | ?- path(a, Via).

     Via = 1 ? 

     yes

Prolog has found the very first instance of a path/2 rules whose first argument is "a".

Summary: Prolog's search through the database

If you want a computer analogy for Prolog's method of finding a clause to unify with a query, think of the Prolog program as a sequential file. For each new query or for each new goal, Prolog starts at the beginning of the file and reads sequentially through the file until it finds something that will match with what it is looking for.

If you want an everyday analogy for Prolog's method of finding a clause to unify with a query, think of the Prolog program as a list written on a sheet of paper. For each new query or for each new goal, Prolog starts at the top of the list and reads down through the list (line by line) until it finds something that will match with what it is looking for.

The second goal in route/2 %2 is (with the variables instantiated):

          route(1, b).

(It is true that there is a path from a to 1 and now the task is to establish that there is a route from 1 to b.)

We could draw a tree of how far we have got:

We have now got into the situation of calling route/2 from within route/2. This is recursion and is a very neat trick in computing.[+]

How does Prolog handle a recursive call?

There are several processes.

it "remembers" the current values of the variables. In this example, it would remember that Start=a, Via=1 and End=b.
it "remembers" which clause in the procedure it is currently using. In this example, it is using route/2 %2.
it looks for the procedure which is being recursively called. In this example, it looks for the procedure route/2. It searches for the recursive call from the beginning of the database.
having found a new clause that matches, it unifies the recursive call with the head of the clause that has been found. In this example, the recursive call is route(1, b) and it first finds route(Start, End) :- ... It unifies as follows:

          Start = 1
          End = b

In step 1, Start had the value of a; now a variable called Start has the value 1. It is essential to realise that Prolog treats the two instances of Start as unrelated. When a new clause is matched, all variables names are treated as unique to the new clause, even if they have names that are used elsewhere in the program.
Prolog continues using the recursive call until it terminates, at which point processing drops back into the rule from which the recursive call was made.

The query progresses as shown in the following search tree, which represents the search as far as the search for a route from node 5.

There is no path from 5 to another node. If Prolog was deterministic, it would get thus far and halt. A deterministic machine is one that is committed to the choices it makes in its computation and which does not have the capability to undo its choices and find alternative computations. A non-deterministic machine can recover from local failures like this one and find an alternative computation.

We can see with a glance at the diagram of the network that the nearest alternative route starts right back at the first node, node a. Prolog has to work methodically back through the network, node by node, looking for alternatives. The key point is that Prolog undoes each successful node in the search tree, one by one, and attempts to find alternative solutions for that node. In this example, it has blocked at path(5, Via). It therefore undoes the immediately preceding node in the search tree (route(5, b)) and looks for an alternative at this point. It has already tried both clauses in the route/2 procedure, so it has to go back to the next previous node: path(2, 5). When it has undone this node of the search tree, it tries to find an alternative path/2 clause with 2 as the first argument. There are none, so it has to progress back to the next previous node of the search tree: (route(2, b)). Again there are no untried alternatives, so it backtracks to the previous node of the search tree: path(1, 2).

With path(1, 2) we come to the first alternative. The goal in the %2 clause of the route/2 procedure is path(Start, Via). Prolog undoes the instantiation of Via to 2 and searches for an alternative instantiation. The next path/2 fact in the database will match with the instantiation of Via = 4. And so Prolog starts to search forward through the network from this point until it again blocks at node 5.

Again, having blocked at node 5 of the network, the process of methodically undoing each step in the computation and searching for an alternative is repeated. The next alternative is back at node a, with the path to node 3. Again the route via 4 to 5 is taken and undone before the path from 3 to 7 is found, and from 7 to b.

Take time to work through Self-Test 1.

[+] Recursion is a common element in children's stories, for instance:

"Once upon a time, there was a little girl who sat on her daddy's knee and said 'Daddy please will you tell me a story and he said:

The problem with this example is that there is no obvious terminating condition, ie the point at which the story naturally finishes. In this case the child is most likely to go off in a fit of (understandable) temper at being so teased.

Navigation Menu