748 Chapter 16 Logic Programming Languages
is caused and controlled by the resolution process. As with ML and Haskell,
a pattern-matching process is used to choose, based on the actual parameter,
between two different definitions of the append process.
The first two parameters to the append operation in the following code
are the two lists to be appended, and the third parameter is the resulting list:append([], List, List).
append([Head | List_1], List_2, [Head | List_3]) :-
append(List_1, List_2, List_3).The first proposition specifies that when the empty list is appended to any
other list, that other list is the result. This statement corresponds to the
recursion-terminating step of the ML append function. Note that the ter-
minating proposition is placed before the recursion proposition. This is done
because we know that Prolog will match the two propositions in order, start-
ing with the first (because of its use of the depth-first order).
The second proposition specifies several characteristics of the new list. It
corresponds to the recursion step in the ML function. The left-side predicate
states that the first element of the new list is the same as the first element of the
first given list, because they are both named Head. Whenever Head is instanti-
ated to a value, all occurrences of Head in the goal are, in effect, simultaneously
instantiated to that value. The right side of the second statement specifies that
the tail of the first given list (List_1) has the second given list (List_2)
appended to it to form the tail (List_3) of the resulting list.
One way to read the second statement of append is as follows: Append-
ing the list [Head | List_1] to any list List_2 produces the list [Head
| List_3], but only if the list List_3 is formed by appending List_1 to
List_2. In LISP, this would be(CONS (CAR FIRST) (APPEND (CDR FIRST) SECOND))In both the Prolog and LISP versions, the resulting list is not constructed until
the recursion produces the terminating condition; in this case, the first list must
become empty. Then, the resulting list is built using the append function itself;
the elements taken from the first list are added, in reverse order, to the second
list. The reversing is done by the unraveling of the recursion.
One fundamental difference between Prolog’s append and those of LISP
and ML is that Prolog’s append is a predicate—it does not return a list, it
returns yes or no. The new list is the value of its third parameter.
To illustrate how the append process progresses, consider the following
traced example:trace.
append([bob, jo], [jake, darcie], Family).(1) 1 Call: append([bob, jo], [jake, darcie], _10)?