CHAPTER 4    Unification and Backtracking

 

In the second part, we show you how Visual Prolog searches for solutions to a goal (through backtracking) and how to control a search. This includes techniques that make it possible for a program to carry out a task that would otherwise be impossible, either because the search would take too long (which is less likely with Visual Prolog than with other Prologs) or because the system would run out of free memory.

In the third part of this chapter, we introduce a predicate you can use to encourage backtracking, and go into more detail about how you can control backtracking. We also introduce a predicate you can use to verify that a certain constraint in your program is (or is not) met.

To shed more light on the subject, in the fourth part of this chapter we review the more important tutorial material (presented so far) from a procedural perspective. We show how you can understand the basic aspects of Prolog, a declarative language, by also looking at them as procedures.

Consider Program 1 in terms of the external goal

    written_by(X, Y).

When Visual Prolog tries to fulfill the goal written_by(X, Y)., it must test each written_by clause in the program for a match. In the attempt to match the arguments X and Y with the arguments found in each written_by clause, Visual Prolog will search from the top of the program to the bottom. When it finds a clause that matches the goal, it binds values to free variables so that the goal and the clause are identical; the goal is said to unify with the clause. This matching operation is called unification.

/* Program ch04e01.pro */

Since X and Y are free variables in the goal, and a free variable can be unified with any other argument (even another free variable), the call (goal) can be unified with the first written_by clause in the program, as shown here:

written_by(   X   ,    Y    ).
                  |         |
written_by(fleming, "DR NO").

Visual Prolog makes a match, X becomes bound to fleming, and Y becomes bound to "DR NO." At this point, Visual Prolog displays

    X=fleming, Y=DR NO

Since Visual Prolog looks for all solutions when you use an external goal, the goal is also unified with the second written_by clause

    written_by(melville,"MOBY DICK").

and Visual Prolog displays the second solution:

    X=melville, Y=MOBY DICK
    2 Solutions

If, on the other hand, you give the program the goal

    written_by(X, "MOBY DICK").

Visual Prolog will attempt a match with the first clause for written_by:

written_by(     X ,"MOBY DICK").
                    |      |
written_by(fleming,"DR NO").

Since "MOBY DICK" and "DR NO" do not match, the attempt at unification fails. Visual Prolog then tries the next fact in the program:

    written_by(melville, "MOBY DICK").

This does unify, and X becomes bound to melville.

Consider how Visual Prolog executes the following:

    long_novel(X).

When Visual Prolog tries to fulfill a goal, it investigates whether or not the call can match a fact or the head of a rule. In this case, the match is with

    long_novel(Title)

Visual Prolog looks at the clause for long_novel, trying to complete the match by unifying the arguments. Since X is not bound in the goal, the free variable X can be unified with any other argument. Title is also unbound in the head of the long_novel clause. The goal matches the head of the rule and unification is made. Visual Prolog will subsequently attempt to satisfy the subgoals to the rule.

    long_novel(Title):-
       written_by(_, Title),
       book(Title, Length),
       Length>300. 

In attempting to satisfy the body of the rule, Visual Prolog will call the first subgoal in the body of the rule, written_by(_, Title). Notice that, since who authored the book is immaterial, the anonymous variable (_) appears in the position of the author argument. The call written_by(_, Title) becomes the current subgoal, and Prolog searches for a solution to this call.

Prolog searches for a match with this subgoal from the top of the program to the bottom. In doing so, it achieves unification with the first fact for written_by as follows:

    written_by(   _,      Title),
                      |         |
    written_by(fleming,"DR NO").

The variable Title becomes bound to "DR NO" and the next subgoal, book(Title, Length), is called with this binding.

Visual Prolog now begins its next search, trying to find a match with the call to book. Since Title is bound to "DR NO", the actual call resembles book("DR NO", Length). Again, the search starts from the top of the program. Notice that the first attempt to match with the clause book("MOBY DICK", 250) will fail, and Visual Prolog will go on to the second clause of book in search of a match. Here, the book title matches the subgoal and Visual Prolog binds the variable Length with the value 310.

The third clause in the body of long_novel now becomes the current subgoal:

    Length > 300.

Visual Prolog makes the comparison and succeeds; 310 is greater than 300. At this point, all the subgoals in the body of the rule have succeeded and therefore the call long_novel(X) succeeds. Since the X in the call was unified with the variable Title in the rule, the value to which Title is bound when the rule succeeds is returned to the call and unified with the variable X. Title has the value "DR NO" when the rule succeeds, so Visual Prolog will output:

    X=DR NO
    1 Solution

In the following chapters, we will show several advanced examples of unification. However, there are still a few basics that need to be introduced first, such as complex structures. In the next section of this chapter, we'll discuss how Prolog searches for its solutions.