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.

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].
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].
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].
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.
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].
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].
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].
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].
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.