aggregating predicates in SWI-Prolog

Question

I need to count all X for which some_predicate(X) holds, and there really a lot of such X. What is the best way to do that?

First clue is to findall, accumulate to a list and return the length of the list.

countAllStuff( X ) :-
    findall( Y
           , permutation( [1,2,3,4,5,6,7,8,9,10], Y )
           , List
           ),
    length( List, X ).

(permutation/2 is only a dummy placeholder demonstrating that there are many results and that it's bad way to compute the count)

Obviously, with real data, there will be a stack overflow.

?- countAllStuff( X ).
ERROR: Out of global stack

Then, I'm trying to replace findall with setof, to no avail.

At last, I've found the [aggregate][1] (clickable) family of predicates, and trying to use aggregate/3 and aggregate/4:

?- aggregate(count, permutation([1,2,3,4], X), Y ).
X = [1, 2, 3, 4],
Y = 1 .

?- aggregate(count, [1,2,3,4], permutation([1,2,3,4], X), Y ).
X = [1, 2, 3, 4],
Y = 1 ;
X = [1, 2, 4, 3],
Y = 1 ;

It's all wrong, I think. I need to get something like this:

?- aggregate(count, permutation([1,2,3,4], X), Y ).
Y = 24 .

1. What am I doing wrong?

2. How can I declare a predicate to conpute the right answer? [1]: http://www.swi-prolog.org/pldoc/doc/home/vnc/prolog/lib/swipl/library/aggregate.pl

Chryselephantine

Answer 1

Use an existentially quantified variable, as you would with setof:

?- aggregate(count, X^permutation([1,2,3,4], X), N).
N = 24.

Calvities

What is X^permutation in that case? – Optical

@garm0nboz1a: X^ means "there exists X", so the whole formula means something like "count the number of ways that permutation([1,2,3,4],X) succeeds for some X and call that number N." – Calvities

Answer 2

In SWI-Prolog there is a much more efficient version, that also avoid locking the global store. So simply using nb_setval and nb_getval you gain at least 3 times the performance (more on multithreading). Just little time ago another question was on counting solutions. Being the base of aggregation it's an obvious stop point while learning Prolog. To evaluate the efficiency gain we get using these monothread semantically equivalent calls:

count_solutions(Goal, N) :-
assert(count_solutions_store(0)),
repeat,
(   call(Goal),
    retract(count_solutions_store(SoFar)),
    Updated is SoFar + 1,
    assert(count_solutions_store(Updated)),
    fail
;   retract(count_solutions_store(N))
), !.
:- dynamic count_solutions_store/1.

% no declaration required here
count_solutions_nb(Goal, N) :-
    nb_setval(count_solutions_store, 0),
    repeat,
    (   call(Goal),
        nb_getval(count_solutions_store, SoFar),
        Updated is SoFar + 1,
        nb_setval(count_solutions_store, Updated),
        fail
    ;   nb_getval(count_solutions_store, N)
    ), !.

parent(jane,dick).
parent(michael,dick).
parent(michael,asd).

numberofchildren(Parent, N) :-
    count_solutions_nb(parent(Parent, _), N).

many_solutions :-
    between(1, 500000, _).

time_iso :-
    time(count_solutions(many_solutions, N)),
    write(N), nl.

time_swi :-
    time(count_solutions_nb(many_solutions, N)),
    writeln(N).

On my system, i get

?- [count_sol].
% count_sol compiled 0,00 sec, 244 bytes
true.

?- time_iso.
tim% 1,000,006 inferences, 2,805 CPU in 2,805 seconds (100% CPU, 356510 Lips)
500000
true.

?- time_swi.
% 2,000,010 inferences, 0,768 CPU in 0,768 seconds (100% CPU, 2603693 Lips)
500000
true.

Vanguard

Doesn't the newest SWI-Prolog implement aggregates this way? – Beabeach

@j4nbur53: yes, the aggregate_all variants of count,sum,min,max use nb_setval – Vanguard

Answer 3

There is also aggregate_all/3:

?- aggregate_all(count, permutation([1, 2, 3, 4], _), Total).
Total = 24.

However, as far as runtime and stack overflows are concerned it seems to perform equally well to your findall+length solution:

?- N is 10^7, time(aggregate_all(count, between(1, N, _), Total)).
% 10,000,022 inferences, 5.075 CPU in 5.089 seconds (100% CPU, 1970306 Lips)
N = Total, Total = 10000000.

?- N is 10^7, time((findall(X, between(1, N, _), L), length(L, Total))).
% 10,000,013 inferences, 4.489 CPU in 4.501 seconds (100% CPU, 2227879 Lips)
N = 10000000,
L = [_G30000569, _G30000566, _G30000545|...],
Total = 10000000.

?- N is 10^8, aggregate_all(count, between(1, N, _), Total).
ERROR: Out of global stack

?- N is 10^8, findall(X, between(1, N, _), L), length(L, Total).
ERROR: Out of global stack

You can count the solutions using assert/retract, this is quite slow but does avoid the "out of stack" problem:

?- assert(counter(0)), N is 10^8, between(1, N, _),
   retract(counter(C)), C1 is C + 1, assert(counter(C1)), fail
   ; retract(counter(C)).
C = 100000000.

Shaman

Answer 4

This is an addendum to Kaarel’s post. Meanwhile some Prolog systems have updated their implementation of aggregate/3 and aggregate_all/3. So there is not anymore an "Out of global stack" error:

In SWI-Prolog:

Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.6)

?- N is 10^8, aggregate_all(count, between(1, N, _), Total).
N = Total, Total = 100000000.

In Jekejeke Prolog:

Jekejeke Prolog 3, Runtime Library 1.3.7 (May 23, 2019)

?- use_module(library(advanced/arith)).
% 1 consults and 0 unloads in 16 ms.
Yes

?- use_module(library(advanced/aggregate)).
% 3 consults and 0 unloads in 94 ms.
Yes

?- N is 10^8, aggregate_all(count, between(1, N, _), Total).
N = 100000000,
Total = 100000000

The new implementations do not first compute a list, and then count the length of the list. Rather they use some kind of global variable as a counter. This approach is also used for sum, max, etc...

Beabeach