Previous | Table of Contents | Next |
Prolog was sometimes originally touted as a language in which you could write executable specifications, text that was so obviously correct that it did not need to be debugged. Alas, as people wrote longer and more complex Prolog code, they found that it needed as much debugging support as any other programming language.
The debugging system of Edinburgh Prolog interpreters was developed originally by Lawrence Byrd. It is referred to as the four-port debugger or the Byrd box debugger because of the way in which it views predicate calls as boxes having four main input/output ports.
The execution of a Prolog goal can be difficult to follow because of the backtracking pattern of computation. An interactive debugger is therefore a useful tool. In Prolog debugging, it is not sufficient merely to have breakpoints on the entry and exit of a predicate; we must also be able to see when a predicate is being retried for this call due to backtracking and whether a predicate call has succeeded or failed.
The four-port debugger provides us with this information. There are four types of events associated with each predicate call that is processed by the interpreter: a call event, which occurs when the predicate is first called; a redo event, which occurs when backtracking causes other clauses to be retried; an exit event, which occurs whenever a solution has been returned by the predicate call (either on the first try or future retries); and a fail event, which occurs when the predicate has exhausted the clauses defining it. A call or redo event happens only when the predicate call has been successfully matched with a clause head; clauses that dont match the call are ignored by the debugger.
6.3.8.1. Creeping Through a Computation
Here is an example of a simple use of the debugger to creep through a computation. Consider again the standard definition of member:
member([X|Xs], X). member([X|Xs], Y) :- member(Xs, Y).
We enter the Prolog interpreter, consult a file containing this definition, and enter the query trace. This predicate is a directive to the interpreter to begin tracing goals thoroughly; the query notrace turns this facility off. We then type the goal member([a,b], X), member([b,c], X). Prologs first task is to evaluate the predicate call member([a,b], X). The first line returned from the debugger is something like
1 1 Call: member([a,b],_77) ?
This prompt is a debugging prompt, giving information on the current state of computation and asking us what we want to do next. The first number is the unique invocation identifier, which is different for every individual call to a predicate. The second number is the depth of the callthat is, how many times we have expanded a predicate call into its body from the top level in order to get to this call. Call indicates that we are at the call port of the predicate. The last thing displayed is the internal representation of the predicate call. _77 is a machine-generated identifier that is Prologs internal name for the variable X; this is different on every run of Prolog.
At this point, if we keep pressing Enter at the debugging prompts, Prolog keeps generating lines like this until we reach the last failure of the predicate. The next few lines, for example, are
1 1 Exit: member([a,b],a) ? 2 1 Call: member([b,c],a) ? 3 2 Call: member([c],a) ? 4 3 Call: member([],a) ? 4 3 Fail: member([],a) ? 3 2 Fail: member([c],a) ? 2 1 Fail: member([b,c],a) ? 1 1 Redo: member([a,b],a) ? 2 2 Call: member([b],_77) ? 2 2 Exit: member([b],b) ? 1 1 Exit: member([a,b],b) ?
Here, the interpreter has returned a as a member of the first list (the first line) and has tried to find it in the second list (the next three lines). The bottommost recursive call has failed, and that failure has propagated back to the top level of the second subgoal (the next three lines). The first subgoal has therefore been redone, and a recursive call results in b being returned. After this point, the output looks as follows:
3 1 Call: member([b,c],b) ? 3 1 Exit: member([b,c],b) ? X = b ?
The interpreter has confirmed that b is a member of the second list and has given us a solution, with the solutions prompt. If we continue in this way, we will trace through another backtrack, which will ultimately fail, leaving us with only the one solution.
Previous | Table of Contents | Next |