As a final example, let's see whether we can use the representation of numerals that we introduced in the previous section for doing simple arithmetic. Let's try to define addition. That is, we want to define a predicate `add/3` which when given two numerals as the first and second argument returns the result of adding them up as its third argument. E.g.

`?- add(succ(succ(0)),succ(succ(0)),succ(succ(succ(succ(0))))).yes?- add(succ(succ(0)),succ(0),Y).Y = succ(succ(succ(0)))`

There are two things which are important to notice:

1. Whenever the first argument is `0`, the third argument has to be the same as the second argument:

`?- add(0,succ(succ(0)),Y).Y = succ(succ(0))?- add(0,0,Y).Y = 0`

This is the case that we want to use for the base clause.

2. Assume that we want to add the two numerals `X` and `Y` (e.g. `succ(succ(succ(0)))` and `succ(succ(0))`) and that `X` is not `0`. Now, if `X'` is the numeral that has one `succ` functor less than `X` (i.e. `succ(succ(0))` in our example) and if we know the result -- let's call it `Z` -- of adding `X'` and `Y` (namely `succ(succ(succ(succ(0))))`), then it is very easy to compute the result of adding `X` and `Y`: we just have to add one `succ`-functor to `Z`. This is what we want to express with the recursive clause.

Here is the predicate definition that expresses exactly what we just said:

`add(0,Y,Y).add(succ(X),Y,succ(Z)) :-        add(X,Y,Z).`

So, what happens, if we give Prolog this predicate definition and then ask:

`add(succ(succ(succ(0))), succ(succ(0)), R)`

Let's go through the way Prolog processes this query step by step. The trace and the search tree are given below.

The first argument is not `0` which means that only the second clause for `add` matches. This leads to a recursive call of `add`. The outermost `succ` functor is stripped off the first argument of the original query, and the result becomes the first argument of the recursive query. The second argument is just passed on to the recursive query, and the third argument of the recursive query is a variable, the internal variable `_G648` in the trace given below. `_G648` is not instantiated, yet. However, it is related to `R` (which is the variable that we had as third argument in the original query), because `R` was instantiated to `succ(_G648)`, when the query was matched to the head of the second clause. But that means that `R` is not a completely uninstantiated variable anymore. It is now a complex term, that has a (uninstantiated) variable as its argument.

The next two steps are essentially the same. With every step the first argument becomes one level smaller. The trace and the search tree show this nicely. At the same time one `succ` functor is added to `R` with every step, but always leaving the argument of the innermost variable uninstantiated. After the first recursive call `R` is `succ(_G648)`, in the second recursive call `_G648` is instantiated with `succ(_G650)`, so that `R` is `succ(succ(_G650)`, in the third recursive call `_G650` is instantiated with `succ(_G652)` and `R` therefore becomes `succ(succ(succ(_G652)))`. The search tree shows this step by step instantiation.

At some point all `succ` functors have been stripped off the first argument and we have reached the base clause. Here, the third argument is equated with the second argument, so that "the hole" in the complex term `R` is finally filled.

This is a trace for the query `add(succ(succ(succ(0))), succ(succ(0)), R)`:

`Call: (6) add(succ(succ(succ(0))), succ(succ(0)), R) Call: (7) add(succ(succ(0)), succ(succ(0)), _G648) Call: (8) add(succ(0), succ(succ(0)), _G650) Call: (9) add(0, succ(succ(0)), _G652) Exit: (9) add(0, succ(succ(0)), succ(succ(0))) Exit: (8) add(succ(0), succ(succ(0)), succ(succ(succ(0)))) Exit: (7) add(succ(succ(0)), succ(succ(0)), succ(succ(succ(succ(0))))) Exit: (6) add(succ(succ(succ(0))), succ(succ(0)), succ(succ(succ(succ(succ(0))))))`

And here is the search tree for this query:

Patrick Blackburn, Johan Bos and Kristina Striegnitz
Version 1.2.5 (20030212)