# Non-Deterministic Tracing

We demonstrate non-deterministic tracing of the default debugger for a simple example. Non-deterministic already happens if a predicate fails. The execution at one point then does not reach an exit port but instead a fail port. We can use the debugger directive nodebug/0 to switch off tracing. Without tracing, we only see a negative answer in the top-level:

`?- nodebug.Yes?- rev([a|b], X).No`

An execution that fails or succeeds deterministically is called semi-deterministic. For semi-deterministic executions, the default debugger can deliver valuable information in that it can show the fail port where the predicate fails for the first time. We will see a sequence of call ports that are not anymore balanced by exit ports, but by fail ports instead:

`?- trace.Yes?- rev([a|b], X).    0 Call rev([a|b], X) ?     1 Call rev([a|b], [], X) ?     2 Call rev(b, [a], X) ?     2 Fail rev(b, [a], X) ?     1 Fail rev([a|b], [], X) ?     0 Fail rev([a|b], X) ? No`

We will now use a different and simpler predicate to show non-deterministic execution. The predicate will only consist of a couple of facts. Facts are a simple way to represent lists of data and we will therefore name the corresponding predicate data/1. The only argument will consist of ground lists:

`data([1,2]).data([4,3]).`

When using a variable call pattern the predicate data/1 will leave choice points. The top-level will then show the first answer substitution without a further prompt "?-". We need to enter the semicolon ";" to get further answer substitutions. The last result is deterministically returned, since the Prolog interpreter is clever enough to eliminate the choice point:

`?- nodebug.Yes?- data(X).X = [1,2] ;X = [4,3]?- `

When an execution leaves some choice points, the default debugger will show redo ports. Not only will the top-level will show that a choice point was eliminated. The default debugger will also recognize the situation. As a result, the default debugger will only show a single redo port and not two redo ports for the example:

`?- trace.Yes?- data(X).    0 Call data(X) ?     0 Exit data([1,2]) ? X = [1,2] ;    0 Redo data([1,2]) ?     0 Exit data([4,3]) ? X = [4,3]?-`

Instead of entering the semicolon ";" it is also possible to stop showing further answer substitu-tions while in debug mode. We use the recursive predicate from the previous section to gener-ate a potential infinite stream of answer substitutions. In ordinary mode, the stream can be stopped by pressing return instead of entering the semicolon ";":

`?- rev(X, Y).X = [],Y = [] ;X = [_A],Y = [_A] ;X = [_A,_B],Y = [_B,_A] ?-`

This top-level functionality is also available while in debug mode. We run the same recursive predicate again, this time in debug mode. This will also demonstrate how additional variables can become visible. In the above example, a single new variable was named "_A". Because we look behind the scene, two new variables will be named "_A" and "_B":

`?- trace.Yes?- rev(X, X).    0 Call rev(X, X) ?     1 Call rev(X, [], X) ?     1 Exit rev([], [], []) ?     0 Exit rev([], []) ? X = [] ;    0 Redo rev([], []) ?     1 Redo rev([], [], []) ?     2 Call rev(_A, [_B], [_B|_A]) ?     2 Exit rev([], [_B], [_B]) ?     1 Exit rev([_B], [], [_B]) ?     0 Exit rev([_B], [_B]) ? X = [_B] ?-`

In the above, we have just entered a semicolon ";" or pressed return to control the stream of answer substitutions. When an answer substitution without a further prompt "?-" appears the end-user can either use the mouse or the keyboard to also issue debugger directives. For more information on debugger directives, see the next chapter.