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

Take a look at sldnfdraw for swi-prolog it works like a charm, the only issue I found with it is that the terms cannot contain underscores, but I've already sent an email to its author reporting it.

It creates a tex file with a tree representation, then with some bash commands transform it to png for visualization.

latex file.tex
dvipdf file.dvi
pdfcrop file.pdf
pdftoppm file-crop.pdf|pnmtopng > file.png

I also recommend adding \usepackage[landscape]{geometry} give extra space to the tree.

Prolog search trees are often simply too big to be examined step by step, but drawing one could be rather simple, and interesting too. Maybe I'll try to write one using the html_write library. In that case, I will report the outcome.

In the meantime SWI-Prolog has a rather peculiar representation in its debugger. There are interesting details about the Prolog program tree. It's not that easy to use and I must confess I've still not read the docs. However I have used the debugger frequently. You can navigate the tree and the instantiated variables on the various nodes. That's powerful.

Visualizing the Prolog search space is an interesting task that is not simple!

edit I forgot to mention that XPCE has the ability to display large trees. If you already have the proof tree, displaying it should be very easy. Just open the viewer. There should be some examples in the XPCE manual help. You could base the display on that.

I solved it in a different way... take a look at: https://github.com/reahaas/prolog-trace-to-tree

I run the program in prolog with trace, that give me an output of the trace as text. Each step in a different line. Save this trace output to a file. it should look like this:

?- trace,there_is_way(telaviv,heifa).
Call: (9) there_is_way(telaviv, heifa) ? creep
Call: (10) there_is_way(telaviv, heifa, nil) ? creep
Call: (11) road_from(telaviv, heifa) ? creep
Call: (12) road(telaviv, heifa) ? creep
Fail: (12) road(telaviv, heifa) ? creep
Fail: (11) road_from(telaviv, heifa) ? creep
Redo: (10) there_is_way(telaviv, heifa, nil) ? creep
Call: (11) road_from(telaviv, _4236) ? creep
Call: (12) road(telaviv, _4236) ? creep

Then use this python code to print the calls trace tree: Its build the tree relying on the first word of the trace: {Call, Fail, Exit, Redo}.

notice: change the file path/name in the code (with open(...)).

from pptree import *
import os


def get_first_word(line):
    if line is "":
        return
    words = line.split()
    if len(words) > 0:
        first_word = words[0]
        return first_word


def add_node(current, line):
    if current is None:
        return Node("head" + line, None)
    else:
        return Node(line, current)


with open("/home/vagrant/openu/prolog/trace_monkey.txt", 'r') as trace_file:
    current = None

    while True:
        line = trace_file.readline()
        if line.strip() == "":  # run till it face an empty string.
            break
        first_word = get_first_word(line)
        if current is None:
            call_tree = add_node(current, line)
            current = call_tree
        elif first_word == "Call:":
            current = add_node(current, line)
        elif first_word == "Exit:":
            add_node(current, line)  # get_assignment(line))
            current = current.parent
        elif first_word == "Fail:":
            add_node(current, line)
            current = current.parent
        elif first_word == "Redo:":
            current = add_node(current, line)

print_tree(call_tree)

This is the results:

To see the results, paste the text tree to notepad++ and zoom out :)

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