Backtracking

At this point we should go through in more detail how Prolog answers queries (and therefore runs programs). Given a query to prove (answer), Prolog goes down its list of facts and rules, from top to bottom, looking for facts or rule heads which match the query (given any existing variable bindings). When it finds one, it stores the place in the fact/rule base it had got to in its search, so if the first match it finds is no good it can carry on and look for more possibilities. So, suppose we have the facts:

    bird(type(sparrow), name(steve))).
    bird(type(penguin), name(tweety))).
    bird(type(penguin), name(percy)).

and give the query ?- bird(type(penguin), name(X)). Prolog will first try matching the query with the first fact, but fail because sparrow doesn't match penguin. It will then try matching with the second fact, and succeed with X = tweety. However, it will put a pointer to the place it got to, so if it turns out that a later query/subgoal fails, it will go back to the saved position, and look for more solutions (ie, X = percy).

So, if we had a fact/rule base such as:

    animal(leo).
    animal(tweety).
    animal(percy).
    animal(peter).
    has_feathers(percy).
    has_feathers(peter).
    tame(peter).
 
    bird(X) :- animal(X), has_feathers(X).
    tame_bird(X) :- bird(X), tame(X).

and gave the query bird(Bird), then Prolog would go down the facts and rules until it reached the first rule, and would match bird(Bird) against bird(X). The variable Bird would then be instantiated to the variable X. Prolog then tries to prove the body of the rule. The subgoal animal(X) succeeds with X=leo. Prolog keeps a pointer of how far its got in checking for animal(X), and tries has_feathers(leo). It goes down the facts/rules looking for one that matches, but doesn't find anything. It therefore goes back to the last thing it tried to match (animal(X)), starts from where it left off, and matches with animal(tweety). But has_feathers(tweety) still doesn't match. So it goes back again and finds animal(percy). has_feathers(percy) matches, so the whole thing succeeds, with final bindings Bird = percy.

Now, if we give the query tame_bird(B), things get a little more complex. Prolog first tries to satisfy bird(X) as above. But then tame(percy) fails. It therefore has to try to resatisfy bird(X). It will do this by first trying to resatisfy has_feathers(percy) as that was the last goal it tried. But there is no other way of satisfying it. So it goes back yet again to animal(X), finding X = peter. has_feathers(peter) succeeds, so bird(X) can succeed a second way with X = peter. tame(peter) succeeds, so tame_bird(B) succeeds with B = peter.

In the above example, prolog is just bactracking through facts. But in general there may be more than one rule which prolog could try, for example:

    animal(percy).       % fact1
    has_feathers(percy). % fact2
    penguin(tweety).     % fact3
    penguin(peter).      % fact4
    tame(peter).         % fact5
 
    bird(X) :-           % rule1
       penguin(X).               
    bird(X) :-           % rule2
       animal(X), 
       has_feathers(X).
    tame_bird(X) :-      % rule3
       bird(X), 
       tame(X).

Given a query bird(B) prolog would first use the first rule (and third fact) and get B=tweety. If it then had to backtrack it would match penguin(X) with the fourth fact to get B = peter. If it bactracks again it will run out of penguin clauses so have to try the second bird rule, and (using the first and second fact) get B = percy. So, remembering that you can type a ``;'' (or click on ``next'') to force backtracking, we get:

   ?- bird(B).
   B = tweety ;
   B = peter ;   
   B = percy ;
   no

This may (or may not) be clearer if we draw some trees. Prolog goal/subgoal structure may be represented as an ``and-or'' tree, as in the following example (figure 1):

This illustrates the basic and-or structure, annotated with the variable bindings as it starts trying to prove the query tame_bird(X). We could further trace on the tree the order in which Prolog tries subgoals. However, diagrams such as this quickly get very messy. You should probably just start with the basic goal/subgoal structure representing the prolog program and work out for yourself the order in which prolog tries different subgoals for different queries. If this proves helpful, great. If not, go back to thinking of it in terms of going through the fact/rule base matching rules and facts, and going back to the last goal tried when something fails.