Prolog tracing interpreter failing into infinite loop when executing recursive programs

Question

I have this tracing meta interpreter which I found in book written by Ivan Bratko called Prolog Programming For Artifical Intelligence 3rd edition and it looks like this:

trace(Goal):-
    trace(Goal, 0).

trace(true, Depth):-!.
%I added those below because I want to allow numeric operations
trace(A > B, Depth):-!.
trace(A < B, Depth):-!.
trace(A = B, Depth):-!.
trace(A is B, Depth):-!.
trace((Goal1, Goal2), Depth):-!,
    trace(Goal1, Depth),
    trace(Goal2, Depth).
trace(Goal, Depth):-
    display('Call: ', Goal, Depth),
    clause(Goal, Body),
    Depth1 is Depth + 1,
    trace(Body, Depth1),
    display('Exit: ', Goal, Depth),
    display_redo(Goal, Depth).
trace(Goal, Depth):-
    display('Fail: ', Goal, Depth),
    fail.

display(Message, Goal, Depth):-
    tab(Depth), write(Message),
    write(Goal), nl.

display_redo(Goal, Depth):-
    true
    ;
    display('Redo: ', Goal, Depth),
    fail.

Can somebody please explain why this tracing meta interpreter fails to trace recursive programs like factorial or fibonnaci number?

I use SWI-Prolog version 6.6.6.

You should also post the actual actorial or fibonnaci programs for which your meta-interpreter fails. Also, unification (`=/2`) is not a numeric operation. — Paulo Moura, Oct 21 '14 at 02:39
What should happen when a goal matches the clauses of `trace/2` that you have added yourself? — , Oct 21 '14 at 03:10

score 2 · Accepted Answer · answered Oct 21 '14 at 08:43

You have added several built-in predicates like (>)/2:

trace(A > B, Depth):-!.

But the interpretation you provide simply says: It's always true. And for this reason your programs never terminate. Instead, provide the actual interpretation:

trace(A > B, _Depth) :- !,
   A > B.

Also, be aware that you receive a lot of warnings for void variables: Use _ to remove cases as this one.

Prolog tracing interpreter failing into infinite loop when executing recursive programs

1 Answers1