|
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.
|
|
| |
| count_elems/2 revisited |
We'll start with the simplest procedure that included Prolog arithmetic,
although the original version seemed quite satisfactory:
% 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).
|
|
| |
| memb/3 and position/3 revisited |
We've already commented on the apparent similarity between memb/3
and position/3. In this section, we'll rewrite them in a single, accumulator
procedure.
% 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]).
|
|
| |
| Using recursion efficiently |
It would be incorrect to think that the only use of accumulators was
to allow procedures to be "bi-directional". Recursion is potentially
a large user of main memory, because each recursive call requires
the state of the computation to be stored and a new state to be computed.
In realistically large Prolog programs, recursion is frequently used
and so memory consumption could be huge. However, there is a technique
of implementing recursion that allows memory to be used very economically.
Look at these two versions of a recursive rule:
% 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.
|
|
| |
| reverse/2: an example of efficiency |
There is a version of reverse commonly known as "naïve reverse"
and often quoted as a benchmark for measuring comparative speeds of
Prolog interpreters and compilers. "Naïve reverse" in turn uses
append (which we defined as app/3). A definition is:
% 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.
|
|
| Take time to work through the Self-Test
7 |
