Prolog what are Accumulators and the \+member function

Question

I've been searching around for tutorials on what accumulators are and what they do, however all the explainations seems to be very overcomplicated and don't really give me a clear enough picture of how they work so that I can make use of it. I seem to understand that accumulators hold onto something such as a number which can then be called upon by other pieces of code and changed. The problem is although I understand what a accumulator is and know when I need one, I'm not too sure how to actually use it.

I mean from the tutorials that I've seen, sometimes the accumulator seems to be a empty list, while other times it seems to be '0' leaving me wondering what exactly can be considered a accumulator and what can not. Can someone please explain to me in simple terms how exactly a accumulator can be used?

Also for the second part of my question, I seem to have noticed people using this a lot in their prolog codes:

\+member

I've managed to deduce that it has something to do with lists since I always see it being used inside a line of code that does something to a list, however after searching around I found that what +member actually means is "Negation as failure - not provable" though I don't really understand what this means or even if that person was correct. Again, can someone please explain to me what exactly +member does and what it can be used for whilst trying to keep your explanation simple, big words confuse me xD.

Thanks a lot for any help regarding these two matters.

Answer 1

First, \+ is the negation of a goal. It succeeds, when the goal following it fails. For example:

?- member(3, [1,2,3]). # 3 is a member of the List
true.

?- member(4, [1,2,3]). # 4 is not a member
false.

?- \+member(4, [1,2,3]). # succeeds, because 'member' fails
true.

?- \+member(3, [1,2,3]).
false.

?- atom_chars('hi', C).
C = [h, i].

?- atom_chars('hi', [h, i]).
true.

?- atom_chars('hello', [h, i]).
false.

?- \+atom_chars('hello', [h, i]).
true.

Second, an accumulator is a way of threading state through a recursion, to take advantage of tail recursion optimization.

Consider these two equivalent ways of computing a factorial:

?- [user].
|: fact_simple(0, 1).
|: fact_simple(N, F) :- 
         N1 is N-1, 
         fact_simple(N1, F1), 
         F is N*F1.
|: % user://2 compiled 0.00 sec, 440 bytes
true.

?- fact_simple(6, F).
F = 720 .

[user].
|: fact_acc(N, F) :- fact_acc(N, 1, F).
|: fact_acc(0, Acc, Acc).
|: fact_acc(N, Acc0, F) :- 
         N1 is N-1, 
         Acc is Acc0 * N, 
         fact_acc(N1, Acc, F).
|: % user://4 compiled 0.00 sec, 1,912 bytes
true.

?- fact_acc(6, F).
F = 720 .

The first version just calls itself in the recursion, waits for the subcall to complete. only then it multiplies its N-value with the subcall's result.

The second version employs an accumulator instead (Acc). Note that 1 is not the accumulator, but it's initial value. After that, each call to the predicate multiplies it's N-value with the accumulator and as the recursion reaches it's base case the accumulator's value is already the final value.

The question really is not 'what can the accumulator be? (0 or the empty list or anything). It's just a way of accumulating values 'as you go' and never return to the calling predicate. This way, the Prolog system doesn't have to build up an ever-growing call stack.

Note, however, that in this example the order of the multiplications is naturally reversed. It doesn't matter for multiplication, but for other values (like lists), one has to take care of that.

fact_simple did the multiplication as 1 * 2 * 3 * 4 * 5 * 6, while fact_acc had it as 1 * 6 * 5 * 4 * 3 * 2. If that's unclear, just do a trace of both!