1

I'm reading Programming in Prolog: Using the ISO Standard, but I'm having problems understanding the recursive definition of append introduced by the book:

append([], List, List).
append([X|List1], List2, [X|Result]) :- append(List1, List2, Result).

For example:

?- append([a, b, c], [3, 2, 1], Result).
Result = [a, b, c, 3, 2, 1]

As far as I understand, the definition says that the resulting list should contain the head of the first list as its head, so initially the resulting list is [ a ]. Then, we recursively run append() on the tail of the first and third argument, leaving the second one as it is, so the third argument (which is [ a ]), should contain the head of the new first argument as its head, so the resulting list is [ b, a ] (which is backwards, so clearly I'm not following correctly). At some point, the first list is [], and the resulting array is [ c, b, a ], so we hit the base case:

append([], List, List).

So append([], [3, 2, 1], [ c, b, a ])., which makes no sense at all. I also don't follow how the contents of the second list are taken into consideration if no manipulation is performed on it in the whole definition.

jviotti
  • 17,881
  • 26
  • 89
  • 148
  • the definition says that the resulting list should contain the head of the first list as its head, so *initially* the resulting list is `[ a | Result ]` where `Result` is not yet instantiated. Then, `Result` is instantiated as `[ b | Result2 ]`, so the whole list becomes known some more, as `[ a , b | Result2 ]`. [etc.](https://stackoverflow.com/questions/11539203/how-do-i-append-lists-in-prolog/11551001#11551001) – Will Ness Dec 20 '16 at 10:31
  • The fact that the definition of `append/3` is recursive is really beside the point. You could have traced your query and you would have seen exactly what happens at each recursion level, and maybe you would have had nothing left to ask. What is important here is the predicate defines what must hold for each of the three arguments for the predicate itself to succeed if evaluated. The answer by @mat explains this in detail, I just felt reiterating can't hurt. –  Dec 20 '16 at 11:34

2 Answers2

3

[...] the definition says that the resulting list should contain the head of the first list as its head, so initially the resulting list is [ a ].

Like you mentioned, the definition says that the head of the resulting list is a, it doesn't say that the entire list is [a]. Furthermore, this list is not passed on as argument to the recursive call.

The resulting list is defined as [X|Result], so in this case X is unified with a. We don't know anything about Result yet, but we "pass" it as third argument to the recursive call. So overall this means that the output will be a followed by the output of the recursive call.

The steps for b and c are exactly the same, so you can imagine the stack like this:

R = [a|R1]
R1 = [b|R2]
R2 = [c|R3]

Or, flattened: [a|[b|[c|R3]]]. Notice now the order is indeed correct?

Now the only remaining question is what is R3? Well, the first argument at this point is the empty list, so we reached the base case. This simply says that "if the first list is empty, the result is the second list". so R3 = [3, 2, 1]. After this the stack unwinds and gives you the appended list as output.

Steven
  • 2,437
  • 5
  • 32
  • 36
  • 2
    there's no stack to unwind since the definition is tail-recursive, [*modulo cons*](https://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons). – Will Ness Dec 20 '16 at 10:29
3

In my view, such an operational reading will lead you away from the true advantage of logic programming, since it will make it extremely tempting to think in terms of "inputs" and "outputs", like in functional programming. Such a procedural or even functional reading is too limited in that it does not do justice to the full generality of the relation.

In addition, as you also already notice, reading this definition operationally is extremely hard. The precise call flow of Prolog is complex, and in general too hard to understand for beginners as well as experts.

In my opinion, a good way to think about your definition is to consider the two clauses, and understand their meaning, leading us to a declarative reading.

First, consider:

append([], List, List).

This simply states what holds, and can be easily seen to be correct: If the first list is empty, the second list is the same as the third list.

Note the wording: We are not even mentioning a resulting list, since all arguments may be specified or not.

Next, consider the second clause:

append([X|List1], List2, [X|Result]) :- append(List1, List2, Result).

Read the :- as what it is, namely ←. So, this says:

If append(List1, List2, Result) holds, then append([X|List1], List2, [X|Result]) also holds.

Again, this can be easily seen to be correct, and allows a reading that is applicable in all directions.

In this light, you may consider whether Result is a good name for the third argument, and further, as @WillNess correctly points out, whether even append/3 is a good name altogether to describe this relation.

mat
  • 40,498
  • 3
  • 51
  • 78
  • 1
    *... or whether `append` is a good name for the relation, too* (a.o.t. e.g. "appended"; so we could read, `[A|B], C, [A|D]` are "appended", when `B,C,D` are "appended"). – Will Ness Dec 20 '16 at 10:55
  • 1
    Thank you, it is corrected! – mat Dec 20 '16 at 11:06