10

Say I want to find sum of all solutions to a predicate, I just can use

findall(L, find(L), Sols),

and just sum members of Sols.

But what if find(L) has a huge number (infinitely, maybe) of solutions, and I just want to get only first 10 of them?

I'd want this to be usable in B-Prolog and ECLiPSe CLP.

9 Answers 9

7

There are many similar uses, so maybe consider to define some abstractions in between. E.g. call_firstn(Goal_0,N) which succeeds for at most the firstN many answers of Goal_0. This in turn can be implemented using call_nth(Goal_0, Nth).

findfirstn(N, Template, Goal_0, Instances) :-
   findall(Template, call_firstn(Goal_0, N), Instances).

call_firstn(Goal_0, N) :-
   N + N mod 1 >= 0, % ensures that N >=0 and N is an integer
   call_nth(Goal_0, Nth),
   ( Nth == N -> ! ; true ).

A full implementation of call_nth/2 that does not leak and still is reentrant cannot be defined in ISO Prolog directly. You need to resort to all kinds of low-level operations with often incomplete semantics that are better hidden from the regular programmer.

4

This is how you would do it in ECLiPSe:

find_n(N, Term, Goal, Solutions) :-
    ( N < 1 ->
        Solutions = []
    ;
        record_create(Bag),
        shelf_create(count(N), Counter),
        ( 
            once((
                call(Goal),
                recordz(Bag, Term),
                \+shelf_dec(Counter, 1)   % succeed if enough
            )),
            fail
        ;
            recorded_list(Bag, Solutions)
        )
    ).

This is reentrant and does not leak memory (both are problems with global variable or dynamic predicate based solutions). Small additions are needed if you want it to deal correctly with modules.

You could of course use the same code structure with the assert/retract primitives that Paulo used.

1
  • 1
    I also looked into ECLiPSe built-in predicates to avoid using dynamic predicates but the the answer does specify that "I'd want this to be usable in B-Prolog and ECLiPSe CLP." Dec 31, 2013 at 14:06
4

A portable solution in ISO Prolog:

:- dynamic(find_n_solution/1).
:- dynamic(find_n_counter/1).

find_n(N, Term, Goal, Solutions) :-
    (   set_find_n_counter(N),
        retractall(find_n_solution(_)),
        once((
            call(Goal),
            assertz(find_n_solution(Term)),
            dec_find_n_counter(M),
            M =:= 0
        )),
        fail
    ;   findall(Solution, retract(find_n_solution(Solution)), Solutions)
    ).

set_find_n_counter(N) :-
    retractall(find_n_counter(_)),
    assertz(find_n_counter(N)).

dec_find_n_counter(M) :-
    retract(find_n_counter(N)),
    M is N - 1,
    assertz(find_n_counter(M)).

Using the sample predicate find/1 @ChristianF answer:

| ?- find_n(10, X, find(X), L).
L = [0,1,2,3,4,5,6,7,8,9]
yes

Note that this solution will still return a list of solutions even if there are less than the required number of solutions. Some Prolog compilers, including B-Prolog and ECLiPSe provide non-logical global variables that can be used to implement the counter but that would make the solution non-portable.

2
  • 1
    Using copy_term/2 is not necessary, you can simply fail across the call of Goal and collect the solutions afterwards. Using copying will also prevent your code from working correctly with constraints.
    – jschimpf
    Dec 31, 2013 at 13:22
  • 1
    This solution is not reentrant.
    – false
    Jul 13, 2014 at 16:16
3

SWI-Prolog offers the built-in predicates findnsols/4 and findnsols/5

?- findnsols(5, I, between(1, 12, I), L).
L = [1, 2, 3, 4, 5] ;
L = [6, 7, 8, 9, 10] ;
L = [11, 12].

You may want to wrap the whole call in once/1 to prevent backtracking for further solution groups (e.g. if in the example above you want the 1-5 list to be your ONLY solution).

?- once( findnsols(5, I, between(1, 12, I), L) ).
L = [1, 2, 3, 4, 5].
0
2

I've just realized that in B-Prolog it's trivial to do via tabling:

%% an example predicate with infinite solutions
%% from ChristianF answer.
find(0).
find(X) :- find(X1), X is X1+1.

:- table find(-).

?- table_cardinality_limit(find/1, 10), findall(X, find(X), L).
L = [0,1,2,3,4,5,6,7,8,9]
yes
2
  • I don't know, any use case to check? This functionality (linear tabling) implemented in the B-Prolog abstract machine. Jan 14, 2014 at 0:12
  • 1
    findfirst(3, J-Is, (between(1,5,J), findfirst(2, I,between(1,4,I),Is)), JIs).
    – false
    Jan 14, 2014 at 0:35
1

The Logtalk threaded engines API or the SWI-Prolog coroutining engines API, both added recently, provide an alternative solution. For example, using Logtalk threaded engines:

find_at_most(N, Template, Goal, List) :-
    threaded_engine_create(Template, Goal, Engine),
    collect_at_most(N, Engine, List0),
    threaded_engine_destroy(Engine),
    List = List0.

collect_at_most(N, Engine, [X| Xs]) :-
    N > 0,
    threaded_engine_next(Engine, X),
    !,
    M is N - 1,
    collect_at_most(M, Engine, Xs).
collect_at_most(_, _, []).

The threaded_engine_create/3 predicate computes the first solution and then suspends waiting for it to be retrieved by the threaded_engine_next/2 predicate. When a solution is retrieved, the engine starts computing the next solution, again suspending until it's consumed (when a call to the threaded_engine_next/2 predicate happens before a solution is ready, this predicate simply blocks waiting for it). Thus, at most N solutions are computed.

The solution using SWI-Prolog coroutining engines is almost identical but without the blocking semantics (in the threaded engines version) and expected to be more efficient unless the implicit overhead of threads is offset by exploiting concurrency (elsewhere) in the application:

find_at_most(N, Template, Goal, List) :-
    engine_create(Template, Goal, Engine),
    collect_at_most(N, Engine, List0),
    engine_destroy(Engine),
    List = List0.

collect_at_most(N, Engine, [X| Xs]) :-
    N > 0,
    engine_next(Engine, X),
    !,
    M is N - 1,
    collect_at_most(M, Engine, Xs).
collect_at_most(_, _, []).

Both APIs also support reified versions of the _next/2 predicates, and thus alternative implementations of the find_at_most/4 predicate, if you want to get rid of the cut in the auxiliary predicate.

Last, but not the least, the solution presented here originated from Paul Tarau work and papers on engines.

0

I think you will need to manually implement the uniqueness condition that is implied in findall, i.e., you will need to aggregate solutions and for each new one check that it hasn't yet been picked before.

Here is an example of how this can work:

%% an example predicate with infinite solutions
find(0).
find(X) :- find(X1), X is X1+1.

%% myfindall(+Num) holds when there are at least Num different solutions for find
myfindall(Num) :-
    length(L, Num),
    mfa_aux(L, [], All),
    %% now do something with All, e.g., sum it.
    writeln(All).

mfa_aux([], All, All).
mfa_aux([H|T], All, Rtv) :-
    find(H),
    not(member(H, All)), !,
    mfa_aux(T, [H|All], Rtv).


%% Test
%% ?- myfindall(10).
1
  • 4
    There's no "uniqueness condition" in the ISO Prolog standard findall/3 predicate. Maybe you're thinking of setof/3? Dec 31, 2013 at 11:27
0

Needing to make a thread-safe solution in SWI Prolog, I came with this:

find_n( N, Solution, Goal, Solutions ) :-
    thread_self( Thread_id ),
    atomic_list_concat( [counter, Thread_id], Counter_flag_key ),
    flag( Counter_flag_key, _, 0 ),

    findall( Solution, (

        call( Goal ),

        flag( Counter_flag_key, X, X ),
        X1 is X + 1,
        flag( Counter_flag_key, _, X1 ),

        ( X1 >= N -> !; true )

    ), Solutions ).
0
0

You can combine findall/3 with limit/2 from the library solution sequence, inspired from SQL:

limit(+Count, :Goal)
Limit the number of solutions
https://www.swi-prolog.org/pldoc/man?predicate=limit/2

Here is an example run:

?- findall(X, limit(3, (repeat, X = 1)), L).
L = [1, 1, 1].

A couple of Prolog systems have predicates like limit/2 in their repertoire.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.