Prolog Learnings: Simple Recursion

February 12, 2021 3-minute read

Using pattern matching, recursion and unificaton to copy a list.

Pattern matching, recursion, unification and the immutability of variables are core to the Prolog language and really shape how Prolog code is written. Things to keep in mind;

Prolog variables are immutable. Once a variable is unified to a value, that value cannot be changed.
When unified to a value that variable will have that value wherever it appears in scope. Taking a look at the copy_list code example, when Head in either argument is unified to the first element of the list, then immediately Head in the other argument will also have this value.
Predicate arguments can act as either an input (when unified to a value), or an output (if not unified to a value).
Both Elixir and Erlang make use of the Prolog list parsing syntax, where variable on the left of the | unifies to the first list item and the variable on the right unifies to the remaining list items.

Lets make use of these to copy a list.

1
2
3
4
%% copy_list(L1, L2).
copy_list([], []).                      % (1)
copy_list([Head|Rest], [Head|L2]) :-    % (2)
    copy_list(Rest, L2).

1	Handle the base case where we want to stop recurstion at an empty list.
2	Handle the nominal case of the non-empty list.

The above few lines of code handle these four use cases;

copy_list([a, b, c, d, e], L2). copies the list in L1 to L2.
And because predicate arguments can act as either input or output, copy_list(L1, [a, b, c, d, e]. will copy the list in L2 to L1.
If lists are passed in L1 and L2 to copy_list, return true if these lists have the same elements or false otherwise.
If L1 and L2 are unbound, then copy_list will create a list and copy this list from L1 to L2.

The interesting mechanic is that while both arguments contain the same list parsing syntax, in the first argument [Head|Rest] breaks apart the input list while [Head|L2] in the second argument creates the list as the stack unwinds. This is shown in some detail in the following examples;

List parsing examples

1
2
3
4
5
6
7
8
9
?- A = [a | [b, c, d, e]].              % (1)

   A = [a, b, c, d, e].


?- [Head | Rest] = [a, b, c, d, e].     % (2)

   Head = a,
   Rest = [b, c, d, e].

1	"a" is added to the head of the list.
2	The list is broken into Head and Rest.

The following diagram shows how recursion, pattern matching, and unification work to make a copy of a list. The arrow heading from top to bottom depicts growing the stack while recursing into copy_list. This ends at the base case, and then the new list is created as the stack is unwound.

Figure 1. "copy_list"

But the previous code is not tail call optimized. In other words, the compiler is unable to transform the recursive procedure into an iterative process. Which means that the code as written will eventually blow the stack if a list of sufficient size is copied. The modified code shown below is tail call optimized, so Prolog will forgo recursion and implement the algorithm as a loop and not grow the stack.

Prolog

1
2
3
4
5
6
7
reverse_list([], Result, Result).
reverse_list([Head|Rest], Temp, Result) :-
    reverse_list(Rest, [Head|Temp], Result).

fast_copy_list(List1, List3) :-
    reverse_list(List1, [], List2),
    reverse_list(List2, [], List3).

In this case the list is copied in reverse. To clone the list in the same order, we can reverse the reversed list which is a 2N operation — still faster than the recursive method.