During debugging, the debugger stops at various points in the execution of a goal, allowing you see what arguments the goal is called with, what arguments it returns with, and whether it succeeds or fails. As in other programming languages, key points of interest are procedure entry and return, but in Prolog there is the additional complexity of backtracking. One of the major confusions that novice Prolog programmers have to face is the question of what actually happens when a goal fails and the system suddenly begins backtracking. The procedure box model of Prolog execution views program control flow in terms of movement from clause to clause in the procedures of the program. This model provides a basis for the debugging mechanism and enables the user to view program behavior in a consistent way.
Let us look at a representative Prolog procedure:
+----------------------------------------+ Call | | Exit -------->| descendant(X, Y) :- offspring(X, Y). |-------> | | | descendant(X, Z) :- | <--------| offspring(X, Y), descendant(Y, Z). |<------- Fail | | Redo +----------------------------------------+
The first clause states that Y is a descendant of X if Y is an offspring of X, and the second clause states that Z is a descendant of X if Y is an offspring of X and if Z is a descendant of Y. In the diagram a box has been drawn around the whole procedure; labeled arrows indicate the control flow into and out of this box. There are four such arrows, which we shall describe in turn.
descendant(X,Y)must be satisfied, control passes through the Call port of the
descendant/2box with the intention of matching the head of a component clause and then satisfying any subgoals in the body of that clause. Notice that this is independent of whether such a match is possible; first the box is called, and then the attempt to match takes place. Textually we can imagine moving to the code for
descendant/2when meeting a call to
descendant/2in some other part of the code.
descendant/2box. Textually we stop following the code for
descendant/2and go back to the code we came from.
descendant/2box through the Redo port. An attempt will now be made to resatisfy one of the component subgoals in the body of the clause that last succeeded; or, if that fails, to completely rematch the original goal with an alternative clause and then try to satisfy any subgoals in the body of this new clause. Textually we follow the code backwards up the way we came looking for new ways of succeeding, possibly dropping down onto another clause and following that if necessary.
descendant/2box and the system continues to backtrack. Textually we move back to the code that called this procedure and keep moving backwards up the code looking for new ways of succeeding.
Note that the box we have drawn around the procedure should really be seen as an invocation box, rather than a procedure box. Often, there are many different Calls and Exits to a particular procedure in the control flow, but these are for different invocations. Each invocation box is given a unique integer identifier to prevent confusion.