Accumulators
3.6. Accumulators#
The condition that the right-hand side of is should not contain variables sometimes determines the ordering of literals in the body of the clause. For instance, in the program below, which computes the length of a list, the is literal should be placed after the recursive length call, which instantiates M. This means that the resolvent first collects as many is literals as there are elements in the list, before doing the actual calculation. Each of these literals contains some ‘local’ variables that require some space in memory. The total memory requirements are thus proportional to the depth of the recursion.
naive_length([],0).
naive_length([_H|T],N):-naive_length(T,M),N is M+1.
Programs with tail recursion need less memory because they do all the work on one recursive level before proceeding to the next. There is a common trick to transform even the length predicate above into a tail recursive program, using an auxiliary argument called an accumulator.
length_acc(L,N):-length_acc(L,0,N).
length_acc([],N,N).
length_acc([_H|T],N0,N):-N1 is N0+1,length_acc(T,N1,N).
length_acc(L,N0,N) is true if N is the number of elements in L plus N0. Initialising N0 to 0 results in N returning the length of L. Note that the actual counting is done by the second argument: only when the list is empty is the third argument unified with the second argument. The main point is that, since the accumulator is given an initial value of 0, it is always instantiated, such that the is literal can be placed before the recursive call.
Accumulators can be used in very many programs. Suppose we want to reverse the order of elements in a list. We could do this by recursively reversing the tail of the list, and putting the head at the end of the result:
naive_reverse([],[]).
naive_reverse([H|T],R):-naive_reverse(T,R1),append(R1,[H],R).
append([],Y,Y).
append([H|T],Y,[H|Z]):-append(T,Y,Z).
This predicate is called ‘naive’ because a lot of unnecessary work is done by the append calls in the recursive clause.
By using an accumulator, we can get rid of the append predicate, as follows:
reverse(X,Y):- reverse(X,[],Y).
reverse([],Y,Y).
reverse([H|T],Y0,Y):- reverse(T,[H|Y0],Y).
reverse(X,Y0,Y) is true if Y consists of the reversal of X followed by Y0. Initialising Y0 to [] results in Y returning the reversal of X.
Exercise 3.12 #
Draw the proof tree for the query ?-naive_reverse([a,b,c],R).
The use of an accumulator in this more efficient program for reversing a list is closely related to another programming trick for increasing the efficiency of list handling. The idea is not to represent a list by a single term, but instead by a pair of terms L1-L2, such that the list actually represented is the difference between L1 and L2. The term L1-L2 is appropriately called a difference list; L1 is called the plus list, and L2 is called the minus list. For instance, the difference list [a,b,c,d]-[d] represents the simple list [a,b,c], as does the difference list [a,b,c,1234,5678]-[1234,5678], and even the difference list [a,b,c|X]-X. The last difference list can be seen as summarising every possible difference list representing the same simple list, by introducing a variable for the part which is not contained in the simple list.
As was remarked above, reverse(X,Y0,Y) is true if Y consists of the reversal of X followed by Y0. Another way to say the same thing is that the reversal of X is the difference between Y and Y0. That is, the reversal of X is represented by the difference list Y-Y0! We can make this explicit by a small syntactic change to reverse, resulting in the following program:
reverse_dl(X,Y):- reverse(X,Y-[]).
reverse([],Y-Y).
reverse([H|T],Y-Y0):- reverse(T,Y-[H|Y0]).
For instance, the third clause in this program says: if the reversal of T is represented by the difference list Y-[H|Y0], then adding H to the head of T is the same as removing H from the minus list in the difference list.
If the minus list is a variable, it can be used as a pointer to the end of the represented list. It is this property which makes difference lists so useful. For instance, if we unify [a,b,c|X]-X with Y-[d,e], we get Y=[a,b,c,d,e] – we have managed to append two lists together in a single unification step! In this example, the second term is not a difference list, nor is the result. If we want to append two difference lists
[a,b,c|XMinus]-XMinus
and
[d,e|YMinus]-YMinus
we must unify XMinus with [d,e|YMinus] (the plus list of the second difference list), such that the first difference list becomes
[a,b,c,d,e|YMinus]-[d,e|YMinus]
Combining the plus list of this difference list with YMinus, we get exactly what we want.
Figure 3.13 Appending two difference lists: the ‘length’ of XMinus is adjusted by unification with YPlus, the result is given by XPlus-YMinus.#
In general, given two difference lists XPlus-XMinus and YPlus-YMinus, we unify XMinus with YPlus, and the result is given by XPlus-YMinus (Figure 3.13):
append_dl(XPlus-XMinus,YPlus-YMinus,XPlus-YMinus):-
XMinus=YPlus.
or even shorter
append_dl(XPlus-YPlus,YPlus-YMinus,XPlus-YMinus).
Appending a simple list to another simple list of \(n\) elements requires \(n\) resolution steps; appending two difference lists requires no resolution at all, just one unification. Using difference lists is almost always a good idea if you have to do a lot of list processing.