### 6.1.1 Defining append

Here's how `append/3` is defined:

`append([],L,L).append([H|T],L2,[H|L3]) :- append(T,L2,L3).`

This is a recursive definition. The base case simply says that appending the empty list to any list whatsoever yields that same list, which is obviously true.

But what about the recursive step? This says that when we concatenate a non-empty list `[H|T]` with a list `L2`, we end up with the list whose head is `H` and whose tail is the result of concatenating `T` with `L2`. It may be useful to think about this definition pictorially:

But what is the procedural meaning of this definition? What actually goes on when we use `append` to glue two lists together? Let's take a detailed look at what happens when we pose the query `append([a,b,c],[1,2,3],X)`.

When we pose this query, Prolog will match this query to the head of the recursive rule, generating a new internal variable (say `_G518`) in the process. If we carried out a trace on what happens next, we would get something like the following:

`append([a, b, c], [1, 2, 3], _G518)append([b, c], [1, 2, 3], _G587)append([c], [1, 2, 3], _G590)append([], [1, 2, 3], _G593)  append([], [1, 2, 3], [1, 2, 3])append([c], [1, 2, 3], [c, 1, 2, 3])append([b, c], [1, 2, 3], [b, c, 1, 2, 3])append([a, b, c], [1, 2, 3], [a, b, c, 1, 2, 3]) X = [a, b, c, 1, 2, 3]yes`

The basic pattern should be clear: in the first four lines we see that Prolog recurses its way down the list in its first argument until it can apply the base case of the recursive definition. Then, as the next four lines show, it then stepwise `fills in' the result. How is this `filling in' process carried out? By successively instantiating the variables `_G593`, `_G590`, `_G587`, and `_G518`. But while it's important to grasp this basic pattern, it doesn't tell us all we need to know about the way `append` works, so let's dig deeper. Here is the search tree for the query `append([a,b,c],[1,2,3],X)` and then we'll work carefully through the steps in the trace, making a careful note of what our goals are, and what the variables are instantiated to. Try to relate this to the search tree.

1. Goal 1: `append([a,b,c],[1,2,3],_G518)`. Prolog matches this to the head of the recursive rule (that is, `append([H|T],L2,[H|L3])`). Thus `_G518` is matched to `[a|L3]`, and Prolog has the new goal `append([b,c],[1,2,3],L3)`. It generates a new variable `_G587` for `L3`, thus we have that `_G518 = [a|_G587]`.

2. Goal 2: `append([b,c],[1,2,3],_G587)`. Prolog matches this to the head of the recursive rule, thus `_G587` is matched to `[b|L3]`, and Prolog has the new goal `append([c],[1,2,3],L3)`. It generates the internal variable `_G590` for `L3`, thus we have that `_G587 = [b|_G590]`.

3. Goal 3: `append([c],[1,2,3],_G590`). Prolog matches this to the head of the recursive rule, thus `_G590` is matched to `[c|L3]`, and Prolog has the new goal `append([],[1,2,3],L3)`. It generates the internal variable `_G593` for `L3`, thus we have that `_G590 = [c|_G593]`.

4. Goal 4: `append([],[1,2,3],_G593`). At last: Prolog can use the base clause (that is, `append([],L,L)`). And in the four successive matching steps, Prolog will obtain answers to Goal 4, Goal 3, Goal 2, and Goal 1. Here's how.

5. Answer to Goal 4: `append([],[1,2,3],[1,2,3])`. This is because when we match Goal 4 (that is, `append([],[1,2,3],_G593)` to the base clause, `_G593` is matched to `[1,2,3]`.

6. Answer to Goal 3: `append([c],[1,2,3],[c,1,2,3])`. Why? Because Goal 3 is `append([c],[1,2,3],_G590])`, and `_G590 = [c|_G593]`, and we have just matched `_G593` to `[1,2,3]`. So `_G590` is matched to `[c,1,2,3]`.

7. Answer to Goal 2: `append([b,c],[1,2,3],[b,c,1,2,3])`. Why? Because Goal 2 is `append([b,c],[1,2,3],_G587])`, and `_G587 = [b|_G590]`, and we have just matched `_G590` to `[c,1,2,3]`. So `_G587` is matched to `[b,c,1,2,3]`.

8. Answer to Goal 1: `append([a,b,c],[1,2,3],[b,c,1,2,3])`. Why? Because Goal 2 is `append([a,b,c],[1,2,3],_G518])`, `_G518 = [a|_G587]`, and we have just matched `_G587` to `[b,c,1,2,3]`. So `_G518` is matched to `[a,b,c,1,2,3]`.

9. Thus Prolog now knows how to instantiate `X`, the original query variable. It tells us that `X = [a,b,c,1,2,3]`, which is what we want.

Work through this example carefully, and make sure you fully understand the pattern of variable instantiations, namely:

`_G518 = [a|_G587]      = [a|[b|_G590]]      = [a|[b|[c|_G593]]]`

For a start, this type of pattern lies at the heart of the way `append` works. Moreover, it illustrates a more general theme: the use of matching to build structure. In a nutshell, the recursive calls to append build up this nested pattern of variables which code up the required answer. When Prolog finally instantiates the innermost variable `_G593` to `[1, 2, 3]`, the answer crystallizes out, like a snowflake forming around a grain of dust. But it is matching, not magic, that produces the result.

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