Prolog Accumulators. Are they really a "different" concept?

Asked 13/11, 2013 at 3:55 Answered 13/11, 2013 at 10:39

Solved recursion prolog tail-recursion accumulator

I am learning Prolog under my Artificial Intelligence Lab, from the source Learn Prolog Now!.

In the 5th Chapter we come to learn about Accumulators. And as an example, these two code snippets are given. To Find the Length of a List

without accumulators:

len([],0).
len([_|T],N) :- len(T,X), N is X+1.

with accumulators:

accLen([_|T],A,L) :- Anew is A+1, accLen(T,Anew,L).
accLen([],A,A).

I am unable to understand, how the two snippets are conceptually different? What exactly an accumulator is doing different? And what are the benefits?

Accumulators sound like intermediate variables. (Correct me if I am wrong.) And I had already used them in my programs up till now, so is it really that big a concept?

Bedspring answered 13/11, 2013 at 3:55 Comment(2)

As others have indicated in various ways, use of the accumulator gives you a solution which uses tail recursion which has optimization benefits. See, for example, the discussion here: #14097156. – Discrown 13/11, 2013 at 11:52

@false As I was quoting a literature, I let it be. Personally, I too would write facts before rules... – Bedspring 13/11, 2013 at 13:34

accumulators are intermediate variables, and are an important (read basic) topic in Prolog because allow reversing the information flow of some fundamental algorithm, with important consequences for the efficiency of the program.

Take reversing a list as example

nrev([],[]).
nrev([H|T], R) :- nrev(T, S), append(S, [H], R).

rev(L, R) :- rev(L, [], R).
rev([], R, R).
rev([H|T], C, R) :- rev(T, [H|C], R).

nrev/2 (naive reverse) it's O(N^2), where N is list length, while rev/2 it's O(N).

Falmouth answered 13/11, 2013 at 7:27 Comment(0)

When you give something a name, it suddenly becomes more real than it used to be. Discussing something can now be done by simply using the name of the concept. Without getting any more philosophical, no, there is nothing special about accumulators, but they are useful.

In practice, going through a list without an accumulator:

foo([]).
foo([H|T]) :-
    foo(T).

The head of the list is left behind, and cannot be accessed by the recursive call. At each level of recursion you only see what is left of the list.

Using an accumulator:

bar([], _Acc).
bar([H|T], Acc) :-
    bar(T, [H|Acc]).

At every recursive step, you have the remaining list and all the elements you have gone through. In your len/3 example, you only keep the count, not the actual elements, as this is all you need.

Some predicates (like len/3) can be made tail-recursive with accumulators: you don't need to wait for the end of your input (exhaust all elements of the list) to do the actual work, instead doing it incrementally as you get the input. Prolog doesn't have to leave values on the stack and can do tail-call optimization for you.

Search algorithms that need to know the "path so far" (or any algorithm that needs to have a state) use a more general form of the same technique, by providing an "intermediate result" to the recursive call. A run-length encoder, for example, could be defined as:

rle([], []).
rle([First|Rest],Encoded):- 
    rle_1(Rest, First, 1, Encoded).               

rle_1([], Last, N, [Last-N]).
rle_1([H|T], Prev, N, Encoded) :-
    (   dif(H, Prev) 
    ->  Encoded = [Prev-N|Rest],
        rle_1(T, H, 1, Rest)
    ;   succ(N, N1),
        rle_1(T, H, N1, Encoded)
    ).

Hope that helps.

Pinnati answered 13/11, 2013 at 6:27 Comment(2)

The accepted answer is good, but I think this one is much better. – Aramenta 6/6, 2017 at 15:22

another great answer by user @boris. – Seftton 7/8, 2018 at 18:20

TL;DR: yes, they are.

Imagine you are to go from a city A on the left to a city B on the right, and you want to know the distance between the two in advance. How are you to achieve this?

A mathematician in such a position employs magic known as structural recursion. He says to himself, what if I'll send my own copy one step closer towards the city B, and ask it of its distance to the city? I will then add 1 to its result, after receiving it from my copy, since I have sent it one step closer towards the city, and will know my answer without having moved an inch! Of course if I am already at the city gates, I won't send any copies of me anywhere since I'll know that the distance is 0 - without having moved an inch!

And how do I know that my copy-of-me will succeed? Simply because he will follow the same exact rules, while starting from a point closer to our destination. Whatever value my answer will be, his will be one less, and only a finite number of copies of us will be called into action - because the distance between the cities is finite. So the total operation is certain to complete in a finite amount of time and I will get my answer. Because getting your answer after an infinite time has passed, is not getting it at all - ever.

And now, having found out his answer in advance, our cautious magician mathematician is ready to embark on his safe (now!) journey.

But that of course wasn't magic at all - it's all being a dirty trick! He didn't find out the answer in advance out of thin air - he has sent out the whole stack of others to find it for him. The grueling work had to be done after all, he just pretended not to be aware of it. The distance was traveled. Moreover, the distance back had to be traveled too, for each copy to tell their result to their master, the result being actually created on the way back from the destination. All this before our fake magician had ever started walking himself. How's that for a team effort. For him it could seem like a sweet deal. But overall...

So that's how the magician mathematician thinks. But his dual the brave traveler just goes on a journey, and counts his steps along the way, adding 1 to the current steps counter on each step, before the rest of his actual journey. There's no pretense anymore. The journey may be finite, or it may be infinite - he has no way of knowing upfront. But at each point along his route, and hence when ⁄ if he arrives at the city B gates too, he will know his distance traveled so far. And he certainly won't have to go back all the way to the beginning of the road to tell himself the result.

And that's the difference between the structural recursion of the first, and tail recursion with accumulator ⁄ tail recursion modulo cons ⁄ corecursion employed by the second. The knowledge of the first is built on the way back from the goal; of the second - on the way forth from the starting point, towards the goal. The journey is the destination.

Recommended topics

Hot tags