eyeprolog

Expression evaluator

What is (2 × 3) + (10 − 4), and how was it computed?

The expression is stored as a tree of facts. A four-clause evaluator folds the tree into a number, and the proof mirrors the tree: every node’s value rests on the values of its children.

Run it in the playground · Source

The question

Evaluating an arithmetic expression is a recursion over its syntax tree: a leaf is its own value, and an operator node combines its children’s values. Writing the evaluator as rules makes that recursion explicit, so the explanation of the result follows the shape of the expression.

The tree

number(n2, 2).
number(n3, 3).
number(n10, 10).
number(n4, 4).

expr(eMul, mul, n2, n3).
expr(eSub, sub, n10, n4).
expr(eAdd, add, eMul, eSub).
root(eAdd).

Leaves carry numbers; each expr/4 fact names an operator and its two children. The root is the addition.

The evaluator

value(Node, Value) :-
  number(Node, Value).

value(Node, Value) :-
  expr(Node, add, Left, Right),
  value(Left, Leftvalue),
  value(Right, Rightvalue),
  (Value is Leftvalue + Rightvalue).

value(Node, Value) :-
  expr(Node, mul, Left, Right),
  value(Left, Leftvalue),
  value(Right, Rightvalue),
  (Value is Leftvalue * Rightvalue).

One clause per kind of node (the sub clause is the same shape). Each recursive call is on a child, so evaluation always ends at the leaves.

The answer

eyeprolog examples/expression-eval.pl

result(root, 12).

The reason

step(value(eMul, 6),
     rule(12),
     ['Node' = eMul, 'Value' = 6, 'Left' = n2, 'Right' = n3, 'Leftvalue' = 2, 'Rightvalue' = 3],
     [expr(eMul, mul, n2, n3), value(n2, 2), value(n3, 3), 6 is 2 * 3]).
step(value(n2, 2), rule(9), ['Node' = n2, 'Value' = 2], [number(n2, 2)]).
step(6 is 2 * 3, builtin, [], []).

The multiplication node is worth 6 because its children are worth 2 and 3, and 6 is 2 * 3. The proof contains one such step for every node of the tree.

The check

condition('C1', resolution, ok, 16).
condition('C5', re_decision, ok, 3).
condition('C7', relevance, ok, 20).
verdict(checked).

The checker replays 16 rule steps and recomputes the three arithmetic steps (one per operator node). Nothing is trusted.

Try it

Change the root to a new node expr(eTop, mul, eAdd, n4) and predict the result.
Add a div operator. What should happen when the right child is worth 0?
How many value/2 steps does the proof contain for this tree, and how does that number relate to the number of nodes?

Learn more in The Art of EyeProlog, Chapter 22.

This site is open source. Improve this page.