Is there a program that can draw a search tree of Prolog queries?

Question

I was wondering if there exists a tool that can draw a step-by-step search tree of a Prolog program? Thanks.

Answer 1

If your Prolog system has a customizable debugger you can easily write your own runtime graph gathering code. Assume your Prolog system has a call back hook goal_tracing/2 as in Jekejeke Prolog. Then we can go on and inspect the current frame and the parent frame to create a link in the graph. Here is the code:

goal_tracing(call, F) :-
    frame_property(F, sys_call_indicator(N, A)),
    frame_property(F, sys_parent_frame(G)),
    frame_property(G, sys_call_indicator(M, B)),
    !,
    update_link(N / A, M / B).
goal_tracing(_, _).

:- dynamic link/2.
update_link(A, B) :-
    link(A, B),
    !.
update_link(A, B) :-
    assertz(link(A, B)).

As can be seen we only inspect the call port and we only look at the predicate indicator. But other approaches are also possible that collect more data. Now we need some utility to display the result. There is only a reset to be called before the collection, and a show to be called after the collection:

reset :-
    retract(link(_, _)), fail.
reset.

show :-
    write('http://yuml.me/diagram/scruffy/class/'),
    link(A, B),
    write(([B] -> [A])),
    write(', '),
    fail.
show.

We produce a link that is understood by yuml.me. Lets give it a try with the peano factorial program. The program code looks as follows:

add(n, X, X).
add(s(X), Y, Z) :-
    add(X, s(Y), Z).

mul(n, _, n).
mul(s(X), Y, Z) :-
    mul(X, Y, H),
    add(Y, H, Z).

fac(n, s(n)).
fac(s(X), Y) :-
    fac(X, H),
    mul(s(X), H, Y).

We can run the collector as follows:

?- reset.
?- trace.
?- fac(s(s(n)),X).
X = s(s(n))
?- nodebug.
?- show.
http://yuml.me/diagram/scruffy/class/[fac / 2] -> [fac / 2], [fac / 2] -> [mul / 3], [mul / 3] -> [mul / 3], [mul / 3] -> [add / 3], [add / 3] -> [add / 3], Yes

One can then paste the URL into a browser and will see the diagram. Remove the ", Yes" at the end of the URL. Here is the result:

Best Regards