Returning results in recursion

Question

I am trying to solve a problem where I need to evaluate the value of a binary expression tree.

tree_calc(Tree, Eval)

where Eval should hold the final result and Tree must be in the form:

tree(LeftNode, Operator, RightNode)

If I create the tree function as per the form above, how am I supposed to pass the results of the calculations back up the recursion if there isn't an empty variable to store the results?

My understanding is that an extra variable is always needed to store the result in.

Apologies in advance as I am sure I am misunderstanding something basic.

Thanks for your help.

Answer 1

In this context, tree isn't what you are calling a function, nor is it what Prolog would refer to as a predicate. tree(LeftNode, Operator, RightNode) is just a term that is used as a structure to represent the tree. So, for example, (2 + 3) * 4 would be represented by, tree(tree(2,+,3), *, 4). You would call your predicate with tree_calc(tree(tree(2,+,3),*,4), Eval) and expect that query to yield, Eval = 20. The term, tree/3 doesn't carry results in this case.

To give an example of how to access tree/3 in a predicate, here's a simple predicate that evaluates the simplest tree (so there's no recursion to tree leaves):

tree_calc(tree(L, Op, R), E) :-
    % Neither L or R are of the form `tree/3`
    compute(Op, L, R, E).

compute(+, L, R, E) :- E is L + R.
compute(*, L, R, E) :- E is L * R.
compute(-, L, R, E) :- E is L - R.
compute(/, L, R, E) :- E is L / R.

You can generalize compute/4:

compute(Op, L, R, E) :-
    Exp =.. [Op, L, R],
    E is Exp.

And you can call it like so:

| ?- tree_calc(tree(2,+,3), Eval).

Eval = 5

yes

For your more general case, you'll need to check L and R to see if they are a tree/3 structure themselves and recursively call tree_calc recursively if so.

Prolog is good at matching term patters. So if you check unification L = tree(LL, Op, LR) and it succeeds, that means L is a tree with left branch LL, operation Op, and right branch LR. You can play with this behavior at the Prolog prompt to see how it works:

| ?- Tree = tree(2, +, 3), Tree = tree(L, Op, R).

L = 2
Op = (+)
R = 3
Tree = tree(2,+,3)

yes
| ?- Tree = tree(2,+,tree(3,*,4)), Tree = tree(L, Op, R).

L = 2
Op = (+)
R = tree(3,*,4)
Tree = tree(2,+,tree(3,*,4))

yes

| ?- Tree = tree(2,+,tree(3,*,4)), Tree = tree(L, Op, R), R = tree(LR, OpR, RR).

L = 2
LR = 3
Op = (+)
OpR = (*)
R = tree(3,*,4)
RR = 4
Tree = tree(2,+,tree(3,*,4))

yes
| ?-