Prolog tree traversal

Let is look at how an expression tree represented as a prefix list can be traversed in Prolog.

Here is the Prolog code.

prints([]):- nl.
prints([X|Rest]):- print(X), prints(Rest).

treeList(
["op2","or",
["op2", "and", ["var", "x"], ["var", "y"]],
["op2","and",
["op1", "not", ["var", "x"]],
["op1", "not", ["var", "y"]]
]
]
).

traverse(["var", Var]):-
	prints(['var ',Var,'\n']).

traverse(["int", Int]):-
	prints(['int ',Int,'\n']).

traverse(["op1", Op1, Right]):-
	traverse(Right),
	prints(['op1 ',Op1,'\n']).

traverse(["op2", Op2, Left, Right]):-
	traverse(Left),
	traverse(Right),
	prints(['op2 ',Op2,'\n']).

traverse(X):-
	prints(['NO\n']),
	prints([X,'\n']).

go:-
	treeList(Tree),
	traverse(Tree).

:- solve(go).

Here is the output of the Prolog code.

var x\n
var y\n
op2 and\n
var x\n
op1 not\n
var y\n
op1 not\n
op2 and\n
op2 or\n

A difference list is used to construct a list from a passed logical variable in a bottom-up manner from the processing of the leaves of the tree. This acts as a tree transform from input (inherited attributes) to output (synthesized attributes).

In the following code, a return variable is used to get a tree to print and then the predicate prints1 (modified from prints) is used to print the tree.

The cut operator "!" is used to cut off backtracking in the prints1 predicate. Otherwise extraneous output would result. One should never use the cut operator unless one knows what one is doing.

One way to get data (e.g., for test) in a program is to use multiple treeList predicates and get each in turn (on backtracking).

Notice how the call by pattern matching is used to select which traverse case is to be used.

Here is the Prolog code.

prints([]):- nl.
prints([X|Rest]):- print(X), prints(Rest).

prints1([]).
prints1(X):- atomic(X), print(X).
prints1([X|Rest]):- prints1(X), prints1(Rest), !.

treeList(["var", "x"]).

treeList(["int", 3]).

treeList(["op1", "not", ["var", "y"]]).

treeList(["op2", "and", ["var", "x"], ["var", "y"]]).

treeList(
["op2","or",
["op2", "and", ["var", "x"], ["var", "y"]],
["op2","and",
["op1", "not", ["var", "x"]],
["op1", "not", ["var", "y"]]
]
]
).

traverse(["var", Var],Var).

traverse(["int", Int],Int).

traverse(["op1", Op1, Right],["(", Op1, " ", RightResult, ")"]):-
	traverse(Right, RightResult).

traverse(["op2", Op2, Left, Right],["(", LeftResult," ", Op2," ",RightResult, ")"]):-
	traverse(Left, LeftResult),
	traverse(Right, RightResult).

go:-
	treeList(Tree1),
	prints(['\n']),

	traverse(Tree1,Tree2),

	prints1(Tree2),
	prints(['\n']),
	fail.

:- solve(go).

Here is the output of the Prolog code.

\n
x\n
\n
3\n
\n
(not y)\n
\n
(x and y)\n
\n
((x and y) or ((not x) and (not y)))\n