next up previous contents
Next: The Flow of Up: The Box Model Previous: The Box Model

The Box Model

As this model is a model of Prolog execution, we can think in terms of procedures rather than predicates.

We represent each call to a procedure by a box. Note that, as a procedure may be executed thousands of times in a program, we need to distinguish between all these different invocations. In the diagram in figure 5.1 a box represents the invocation of a single procedure and which is therefore associated with a specific goal. The top level query is parent(X,Y), X=f.

We regard each box as having four ports: they are named the Call, Exit, Fail and Redo ports. The labelled arrows indicate the control flow in and out of a box via the ports.

Figure 5.1: The Byrd Box Model Illustrated

The Call port for an invocation of a procedure represents the first time the solution of the associated goal is sought. Control then `flows' into the box through the Call port.

We then seek a clause with a head that unifies with the goal. Then, we seek solutions to all the subgoals in the body of the successful clause.

If the unification fails for all clauses (or there are no clauses at all) then control would pass out of the Fail port. There are also other ways to reach the Fail port.

Control reaches the Exit port if the procedure succeeds. This can only occur if the initial goal has been unified with the head of one of the procedure's clauses and all of its subgoals have been satisfied.

The Redo port can only be reached if the procedure call has been successful and some subsequent goal has failed. This is when Prolog is backtracking to find some alternative way of solving some top-level goal.

Basically, backtracking is the way Prolog attempts to find another solution for each procedure that has contributed to the execution up to the point where some procedure fails. This is done back from the failing procedure to the first procedure that can contribute an alternative solution ---hence, backtracking.

When backtracking is taking place, control passes through the Redo port. We then, with the clause which was used when the procedure was previously successful, backtrack further back through the subgoals that were previously satisfied. We can reach the Exit port again if either one of these subgoals succeeds a different way ---and this leads to all the subgoals in the body of the clause succeeding--- or, failing that, another clause can be used successfully. Otherwise, we reach the Fail port. Note that, for this to work out, the system has to remember the clause last used for each successful predicate.

The system can throw this information away only if it can convince itself that we will never revisit a procedure that succeeds. We can always force this to happen by using the cut (!/0) (which is explained in chapter 9) ---but this is a last resort as most implementations of Prolog can do some sensible storage management. An understanding of this mechanism can help you avoid the use of cut.

We reach the Fail port

next up previous contents
Next: The Flow of Up: The Box Model Previous: The Box Model

Paul Brna
Mon May 24 20:14:48 BST 1999