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.

Sherilyn

In Mercury one would simply write a predicate named accum which does this. However you cannot use goals as parameters (as you have done in the question) you have to use lambdas instead. – Callicrates

@PaulBone The result depends on calculating all solutions to the generator. So, ultimately, calling something from Mercury's solutions module will still be required, unless you want to use non-logical features (in which case the adverb "simply" does not apply ;)). – Hypercorrection

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.

Corron

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.

Guardafui

The question was asking for the solutions to be generated by backtracking. Your response starts with the solutions [1,2,3] already generated, so it does not answer the question. – Hypercorrection

[1,2,3] is not the list of solutions, it's the input list, the same that you would be passing in the member(Val,List) bit in the question example. – Guardafui

You have only solved the example, not the general case. The question was clearly, I repeat, asking for the solutions to be generated by backtracking. – Hypercorrection

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.

Hypercorrection