# Building an Expression Tree in Prolog

dcg expression-trees prolog ### Question

I'm looking for a way to build an Expression Tree in Prolog. I already did some experiments and came up with the following working code (that will only handle constants and the plus expression):

``````const(_).
plus(_, _).

eval(const(R), R).

eval(plus(A, B), R) :- number(A), number(B), R is A+B.
eval(plus(A, B), R) :- number(A), eval(B, B_R), R is A+B_R.
eval(plus(A, B), R) :- eval(A, A_R), number(B), R is A_R+B.
eval(plus(A, B), R) :- eval(A, A_R), eval(B, B_R), R is A_R+B_R.
``````

Is there any simpler alternative to this approach? Will I have to define these 4 cases for each one of the operators I plan on adding to my program?

I think this should do it, though I'm not familiar with the construct `pred1(pred2(...)...) :- ...` (my Prolog is very rusty).

``````eval(A, A) :- number(A).
eval(plus(A, B), R) :- eval(A, A_R), eval(B, B_R), R is A_R+B_R.
``````

See here another schema, exploiting DCG and (a kind of) lazy evaluation:

``````/*
File:    dcg_calculator.pl
Author:  Carlo,,,
Created: Aug 16 2011
Purpose: associativity and precedences in calculator
*/

:- module(dcg_calculator, [dcg_calculator/2, expr//1]).
%- [library(http/dcg_basics)]. obsolete
:- [library(dcg/basics)].

/* usage

?- dcg_calculator("1+(-2-2)",S),V is S.
S = 1+ (-2-2),
V = -3 ;
false.

*/
dcg_calculator(Formula, IsEvaluable) :-
phrase(expr(IsEvaluable), Formula, []).

expr(Evaluable) -->
sum(Evaluable).

sum(S) -->
product(P), sum_1(P, S).
sum_1(L, S) -->
"+", product(P), sum_1(L + P, S);
"-", product(P), sum_1(L - P, S);
{L = S}.

product(P) -->
value(V), product_1(V, P).
product_1(V, P) -->
"*", value(U), product_1(V * U, P);
"/", value(U), product_1(V / U, P);
{V = P}.

% value(V) -->
%   {var(V)} -> {V=0 /* between(0, 9, V)*/ }, "0".

value(V) -->
"(", expr(V), ")" ;
number(V).
``````

Using grammars to model data structures it's a very useful technique in Prolog. The grammar used it's an implementation of PEGs. Dependency from SWI-Prolog it's very limited, just number//1.

Prime Library

More Projects...