How do I build an interpreter for an abstract syntax tree like this?

Question

cal(cal(1, plus, 2), minus, 3) I need to get a result from it. How could I do that? I'm pretty damaged by prolog. T.T

the AST is generated by calling:

?- calculations(Tree,[1,+,2,-,3],[]).
Tree = cal(cal(1, plus, 2), minus, 3) .

on the following DCG code:

calculations(VV) --> 
    vv(VV).

calculations(ResultTree) --> 
    vv(VV1), more_calculations(VV1,ResultTree).

more_calculations(VV1,cal(VV1,Operator,VV2)) --> 
    more_calculation(Operator,VV2).

more_calculations(VV1,ResultTree) -->
    more_calculation(Operator1,VV2),
    more_calculations(cal(VV1,Operator1,VV2),ResultTree).   

more_calculation(Operator,VV) --> 
    operator(Operator),vv(VV).

vv(Name) --> var_name(Name).
vv(Value) --> var_value(Value).

operator(plus) --> [+].
operator(minus) --> [-].

var_name(Name) -->
   [Name],{check_name(Name),\+member(Name,[write,read,begin,end,while])}.
var_value(Value) -->[Value],{number(Value)}.

check_name(N):-
    catch(atom_chars(N, L), _, fail),
    is_lower(L).

is_lower([]).
is_lower([H|T]) :-
    catch(char_type(H, lower), _, fail),
     is_lower(T).

Answer 1

There are many ways to do this, depending upon the bigger picture of what you're doing and what your goals are. But here is one possibility:

evaluate(cal(X, Op, Y), Result) :-
    evaluate(X, Xr),
    evaluate(Y, Yr),
    Exp =.. [Op, Xr, Yr, Result],
    call(Exp).
evaluate(X, X) :- number(X).

plus(X, Y, R) :- R is X + Y.
minus(X, Y, R) :- R is X - Y.

evaluate/2 assumes that you pass it something that looks like a number or a cal/3 where the parameters to cal/3 are an operand, an operator, and another operand, respectively. You write a predicate to evaluate each individual operator, and they assume the operands have been reduced to numbers.

Example:

evaluate(cal(cal(2, plus, 3), minus, 8), Result).

Gives:

Result = -3.

In the stated example:

| ?- calculations(Tree,[1,+,2,-,3],[]), evaluate(Tree, Result).

Result = 0
Tree = cal(cal(1,plus,2),minus,3) ? a

no