Does any version of Prolog support higher order abstraction of accumulators?

Question

I was wondering about a Prolog that could include a built-in call like this:

accum(generator, filter, accumulator)
Calculates all solutions to generator.
For each one, if filter can be proved, accumulator is proved.
Backtracks to find all solutions to filter and generator.
Accumulator may backtrack internally, but multiple proofs of accumulator are 
  conjoined, not backtracked.

So, for example, to sum a list without using recursion you could write:

X is 0, accum(member(Val,List), True, X is X + Val).

Is there any Prolog with this construct or an equivalent? Bear in mind that I am a bit of a newbie at Prolog and may be missing something obvious.

Answer 1

SWI-Prolog library(aggregate) has a powerful interface, for instance

aggregate_all(sum(Val), member(Val,List), Sum)

the (apparently simple) sharing of the variables among aggregation and generation is obtained with a predicate, foreach/2, that could interest you.

In SWI-Prolog you can do ?- edit(library(aggregate)). to study the internals...

library(aggregate) is relatively inefficient, but coupled with SWI-Prolog nb_ (non backtrackable) data structures should do its job very well...

About non backtrackable data structures: here is an example of my 'self built' accumulator, implemented by means of nb_setarg/3.

Answer 2

I assume you mean without explicit recursion? If so, you can use an implementation of the high-order predicate list fold left, together with a lambda expression to avoid the need of an auxiliary predicate. Using Logtalk as an example you can write:

?- Sum0 is 0, meta::fold_left([X,Y,Z]>>(Z is Y+X), Sum0, [1,2,3], Sum).
Sum0 = 0,
Sum = 6.

Logtalk can use as a backend compiler most Prolog implementations (http://logtalk.org/). You can also use Ulrich's lambda library (http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord.html) with a supported Prolog compiler together with a Prolog library providing the fold left predicate for the same result. Using now YAP as an example:

$ yap
...
 ?- use_module(library(lambda)).
...
 ?- use_module(library(maplist)).
...
 ?- Sum0 is 0, foldl(\X^Y^Z^(Z is Y+X), [1,2,3], Sum0, Sum).
Sum = 6,
Sum0 = 0.

Briefly, the fold left predicate iterates over a list, recursively applying the closure in its first argument to a list element and the accumulator, returning the final accumulator value.

Answer 3

In Mercury's standard library the "solutions" module provides functionality like this.

Note that X is X + Val does not assign a new value to X. It is a statement that is true if Val is zero, and false if it is any other number, which is probably not what you mean. Accumulators like this are typically expressed as a relation between the initial and final value.

In Mercury, your example could be written as:

:- import_module solutions.
...
sumlist(List, Sum) :-
    Generator = (pred(Val::out) is nondet :- member(Val, List), true),
    Accumulator = (pred(X::in, Y::in, Z::out) is det :- Z = X + Y),
    aggregate(Generator, Accumulator, 0, Sum).

There is no need for a separate filter argument, as it can be included as part of the generator.