The Procedure Box Control Flow Model

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.

Call

This arrow represents an initial invocation of the procedure. When a goal of the form descendant(X,Y) must be satisfied, control passes through the Call port of the descendant/2 box 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/2 when meeting a call to descendant/2 in some other part of the code.

Exit

This arrow represents a successful return from the procedure. This occurs when the initial goal has been unified with the head of one of the component clauses and all subgoals have been satisfied. Control now passes out of the Exit port of the descendant/2 box. Textually we stop following the code for descendant/2 and go back to the code we came from.

Redo

This arrow indicates that a subsequent goal has failed and that the system is backtracking in an attempt to find alternatives to previous solutions. Control passes into the descendant/2 box 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.

Fail

This arrow represents a failure of the initial goal, which might occur if no clause is matched, or if subgoals are never satisfied, or if all solutions produced are always rejected by later processing. Control now passes out of the Fail port of the descendant/2 box 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.