Is there a program that can draw a Prolog query search tree?

Question

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

Answer 1

If your Prolog system has a custom debugger, you can easily write your own runtime graph collection code. Suppose a Prolog system has a call_tracing / 2 callback, as in Jekejeke Prolog . Then we can continue and check the current frame and the parent frame to create a link on the chart. 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 you can see, we only check the call port, and we look only at the predicate indicator. But other approaches that have more data are possible. Now we need a utility to display the result. Here there is only a reset, which must be called before the assembly, and the show, which is 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 create a link that is understood as yuml.me. Let's try with the peano facultative program. The program code is 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 

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

Best wishes

Answer 2

Prolog search trees are often simply too large to be explored step by step, but drawing was pretty simple and interesting. Perhaps I will try to write one using the html_write library. In this case, I will report the results.

Meanwhile, SWI-Prolog has a rather peculiar view in its debugger. There is interesting information about the Prolog program tree. It is not so easy to use, and I must admit that I have not read the documents yet. However, I often used a debugger. You can navigate through the tree and instantiated variables on different nodes. It is powerful .

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

edit I forgot to mention that XPCE has the ability to display large trees. If you already have a evidence tree, its display should be very simple. Just open the viewer. XPCE help should have some examples. You can customize the display on it.

Answer 3

Take a look at sldnfdraw for swi- prolog, it works like a charm, the only problem I encountered is that the terms cannot contain underscores, but I already sent an email to its author, informing me of this.

It creates a text file with a tree view, and then with the help of some commands bash converts 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} to make room for the tree.

Answer 4

I decided it differently ... look at: https://github.com/reahaas/prolog-trace-to-tree

I run the program in a prolog with a trace, which gives the trace output in the form of text. Each step on a separate 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 call trace tree: it builds the tree based on the first trace word: {Call, Fail, Exit, Redo}.

note: 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) 

These are the results:

To see the results, insert a text tree in notepad ++ and zoom out :)