Prolog Language Difference Lists Evaluate an arithmetic expression

Example

Let's define a grammar enabling us to perform additions, multiplications with the usage of parenthesis. To add more value to this example, we are going to compute the result of the arithmetic expression. Summary of the grammar:

expression → times
expression → times '+' expression
times → element
times → element '*' times
element → "integer"
element → '(' expression ')'

All the predicates have an arity of 3, because they need to open list, the hole and the value of the arithmetic expression.

expression(Value, OpenList, FinalHole) :-
    times(Value, OpenList, FinalHole).

expression(SumValue, OpenList, FinalHole) :-
    times(Value1, OpenList, ['+'|Hole1]),
    expression(Value2, Hole1, FinalHole),
    plus(Value1, Value2, SumValue).

times(Value, OpenList, FinalHole) :-
    element(Value, OpenList, FinalHole).

times(TimesValue, OpenList, FinalHole) :-
    element(Value1, OpenList, ['*'|Hole1]),
    times(Value2, Hole1, FinalHole),
    TimesValue is Value1 * Value2.

element(Value, [Value|FinalHole], FinalHole) :-
    integer(Value).

element(Value, ['('|OpenList], FinalHole) :-
    expression(Value, OpenList, [')'|FinalHole]).

To properly explain the principle of holes and how the value is computed, let's take the second clause expression:

expression(SumValue, OpenList, FinalHole) :-
    times(Value1, OpenList, ['+'|Hole1]),
    expression(Value2, Hole1, FinalHole),
    plus(Value1, Value2, SumValue).

The open list is denoted by the predicate OpenList. The first element to validate is what comes before the addition symbol (+). When the first element is validated, it's directly followed by the addition symbol and by the continuation of the list, called Hole1. We know that Hole1 is the next element to validate and can be another expression, hence Hole1 is then the term given to the predicate expression.

The value is always represented in the first term. In this clause, it's defined by the sum of the Value1 (everything before the addition symbol) and Value2 (everything after the addition symbol).

Finally, the an expression can be evaluated.

?- expression(V, [1,+,3,*,'(',5,+,5,')'], []).
V = 31