These Pages are maintained by
Dr Peter Hancox
Last updated October 1998
This section first looks at how to write accumulators, re-working examples seen in earlier sections, and then examines why accumulators can be more efficient.
% 1 terminating condition
count_elems([], 0).
% 2 recursive
count_elems([Head|Tail], Count) :-
count_elems(Tail, Sum),
Count is Sum + 1.
This uses a variable called Count which acts as a counter of the number of elements in the list. In an accumulator, we add another argument to help the counting. This is the new terminating condition:
% 1 terminating condition
count_elems_acc([], Total, Total).
This simply says that when the list is empty, then the other two arguments are the same.
The recursive condition is a rearrangement of the old version:
% 2 recursive
count_elems_acc([Head|Tail], Sum, Total) :-
Count is Sum + 1,
count_elems_acc(Tail, Count, Total).
This simply adds one to the counter, while recursing on the Tail of the list and passing the Total on. We can see how the variables are instantiated as recursion deepens by following the output of demo_count_elems_acc/3. Look especially at how Count is incremented and how Total is only instantiated when the terminating condition is reached:
| ?- demo_count_elems_acc([a,b,c], 0, Total).
Before recursion at depth 1
List is: [a,b,c]
Count is: 0
Total is: _425
Before recursion at depth 2
List is: [b,c]
Count is: 1
Total is: _425
Before recursion at depth 3
List is: [c]
Count is: 2
Total is: _425
At the termination condition
List is: []
Count is: 3
Total is: 3
After recursion at depth 3
List is: [c]
Count is: 2
Total is: 3
After recursion at depth 2
List is: [b,c]
Count is: 1
Total is: 3
After recursion at depth 1
List is: [a,b,c]
Count is: 0
Total is: 3
Total = 3 ;
no
To call the procedure, we can try various versions:
| ?- count_elems_acc([a,b,c], 0, Total).
Total = 3 ? ;
no
| ?- count_elems_acc([a,b,c], 0, 4).
no
| ?- count_elems_acc([], 0, Total).
Total = 0 ? ;
no
| ?- count_elems_acc(List, 0, 3).
List = [_191,_197,_203]
yes
It is inconvenient to remember to add the literal '0' every time count_elems_acc/3 is called, so we write another rule, count_elems_acc/2, which calls count_elems_acc/3 with the literal:
% 1
count_elems_acc(List, Total) :-
count_elems_acc(List, 0, Total).
% 1 terminating
pos_memb_acc(Pos, Pos, Elem, [Elem|_]).
% 2 recursive
pos_memb_acc(Cnt, Pos, Elem, [_|Tail]) :-
Cnt1 is Cnt + 1,
pos_memb_acc(Cnt1, Pos, Elem, Tail).
Like count_elems_acc/3, this uses a counter (called Cnt and Cnt1) and a total (called Pos) to keep track on the position of the element. The recursive condition is true when the counter is incremented and the recursive call is true. The terminating condition is true when the head of the list is unifiable with Elem and the counter and Pos can be unified.
Again, we'll provide a more convenient calling rule:
pos_memb_acc(Pos, Elem, List) :-
pos_memb_acc(1, Pos, Elem, List).
Try these procedures with the following two queries:
| ?- pos_memb_acc(3, Elem, [a,b,c,d,e]).
| ?- pos_memb_acc(Pos, c, [a,b,c,d,e]).
% 2 recursive
count_elems([Head|Tail], Count) :-
count_elems(Tail, Sum),
Count is Sum + 1.
% 2 recursive
count_elems_acc([Head|Tail], Sum, Total) :-
Count is Sum + 1,
count_elems_acc(Tail, Count, Total).
In the first version, the first sub-goal (count_elems(Tail, Sum)) is non-deterministic: that is to say that there could be more than one alternative matching clause in the Prolog program; the second sub-goal is deterministic, because there is only one possible solution to Count is Sum + 1.
In the second version, the first sub-goal (Count is Sum + 1) is deterministic; the second sub-goal (count_elems(Tail, Sum, Total)) is non-deterministic.
In Prolog, the efficient use of memory hinges on determinism and non-determinism. Look again at the second version. As the first sub-goal (Count is Sum + 1) is deterministic, when the second, recursive sub-goal (count_elems(Tail, Sum, Total)) is reached, the Prolog interpreter/compiler has no need to "remember" anything about the previous sub-goals. This means that the recursive call can use the memory being used by the current call and so, as recursion deepens, there is no increase in memory used.
With the first version, it may be that some sub-goal following the recursive sub-goal may be non-deterministic, and so Prolog cannot over-write the memory used for the current recursive call and so requiring the consumption of more main memory.
This technique of economising on the use of memory during recursion is part of a technique called Tail Recursion Optimisation. Its name refers to the position of the recursive sub-goal at the tail-end of the recursive rule. Experienced Prolog programmers are identifiable by their wide-spread use of tail-recursion.
% 1 terminating condition
reverse_naive([], []).
% 2 recursive
reverse_naive([Head|Tail1], Reversed) :-
reverse_naive(Tail1, Tail2),
app(Tail2, [Head], Reversed).
This seems a harmless piece of code, but look at the recursive rule. This recursively reverses Tail1 to obtain Tail2 and then appends Head to Tail2. This means that reverse_naive/2 recurses through to the empty list and, at each level of recursion, app/3 also recurses through to the end of the list. If you want an illustration of what this means, simply copy reverse_naive/2 and app/3 into a file and trace a query like:
| ?- reverse_naive([a,b,c,d,e,f], Rev).
When I did this, I counted no less than twenty-eight separate calls to procedures, of which, seven were calls to reverse_naive/2 and twenty-one were to app/3. By rewriting reverse_naive/2 as an accumulator, we can drastically reduce the amount of processing:
% 1
reverse_acc(List, Tsil) :-
reverse_acc(List, [], Tsil).
% 1 terminating condition
reverse_acc([], Reversed, Reversed).
% 2 recursive
reverse_acc([Head|Tail], Rest, Reversed) :-
reverse_acc(Tail, [Head|Rest], Reversed).
This version starts the second argument of reverse_acc/3 as an empty list and then uses the list constructor to add Head to the second argument at each stage of recursion. The terminating condition specifies that the second and third arguments should be unified.
When I traced this version, there were only eight procedure calls. Obviously the accumulator version does far less work and it has the advantage of being tail-recursive, whereas the naïve version isn't, with a corresponding lack of efficiency.
Beginners at Prolog find it easy to write procedures that aren't tail recursive and don't use accumulators where they should. However, with practise and experience, better habits prevail.
These Pages are maintained by
Dr Peter Hancox
Last updated October 1998