prolog - Evaluating an algebraic expression

Question

This is a test review question that I am having trouble with. How do you write a method to evaluate an algebraic expression with the operators plus, minus and times. Here are some test queries:

simplify(Expression, Result, List)

?- simplify(plus(times(x,y),times(3 ,minus(x,y))),V,[x:4,y:2]).
          V = 14

?- simplify(times(2,plus(a,b)),Val,[a:1,b:5]).
          Val = 12

?- simplify(times(2,plus(a,b)),Val,[a:1,b:(-5)]).
          Val = -8 .

All I was given were these sample queries and no other explanation. But I am pretty sure the method is supposed to dissect the first argument, which is the algebraic expression, substituting x and y for their values in the 3rd argument (List). The second argument should be the result after evaluating the expression.

I think one of the methods should be simplify(V, Val, L) :- member(V:Val, L). Ideally there should only be 4 more methods... but I'm not sure how to go about this.

Answer 1

Start small, write down what you know.

simplify(plus(times(x,y),times(3 ,minus(x,y))),V,[x:4,y:2]):- V = 14.

is a perfectly good start: (+ (* 4 2) (* 3 (- 4 2))) = 8 + 3*2 = 14. But then, of course,

simplify(times(x,y),V,[x:4,y:2]):- V is 4*2.

is even better. Also,

simplify(minus(x,y),V,[x:4,y:2]):- V is 4-2.
simplify(plus(x,y),V,[x:4,y:2]):- V is 4+2.
simplify(x,V,[x:4,y:2]):- V is 4.

all perfectly good Prolog code. But of course what we really mean, it becomes apparent, is

simplify(A,V,L):- atom(A), getVal(A,L,V).
simplify(C,V,L):- compound(C), C =.. [F|T], 
  maplist( simp(L), T, VS),       % get the values of subterms
  calculate( F, VS, V).           % calculate the final result

simp(L,A,V):- simplify(A,V,L).    % just a different args order

etc. getVal/3 will need to retrieve the values somehow from the L list, and calculate/3 to actually perform the calculation, given a symbolic operation name and the list of calculated values.

Study maplist/3 and =../2.

(not finished, not tested).

---

OK, maplist was an overkill, as was =..: all your terms will probably be of the form op(A,B). So the definition can be simplified to

simplify(plus(A,B),V,L):-
  simplify(A,V1,L),
  simplify(B,V2,L),
  V is V1 + V2.         % we add, for plus

simplify(minus(A,B),V,L):-
  % fill in the blanks
  .....
  V is V1 - V2.         % we subtract, for minus

simplify(times(A,B),V,L):-
  % fill in the blanks
  .....
  V is .... .           % for times we ...

simplify(A,V,L):-
  number(A),
  V = .... .            % if A is a number, then the answer is ...

and the last possibility is, x or y etc., that satisfy atom/1.

simplify(A,V,L):-
  atom(A),
  retrieve(A,V,L).

So the last call from the above clause could look like retrieve(x,V,[x:4, y:3]), or it could look like retrieve(y,V,[x:4, y:3]). It should be a straightforward affair to implement.