higher-order "solutions" predicate

Question

I am using a higher order Prolog variant that lacks findall.

There is another question on implementing our own findall here: Getting list of solutions in Prolog.

The inefficient implementation is:

parent(pam, bob). %pam is a parent of bob
parent(george, bob). %george is a parent of bob

list_parents(A, Es, [X|Xs]) :-
   parent(X, A),
   \+ member(X, Es),
   list_parents(A, [X|Es], Xs).
list_parents(A, Es, []).

The efficient one

need a "solutions" higher-order predicate:

list_parents(X, Ys) :- solutions(parent, [X, W], 1, Ys)

What is solutions? Can I implement my own solutions predicate in higher order lambda Prolog?

Answer 1

If your Prolog has some kind of non backtrackable assignment, like SWI-Prolog 'global' variables, you could implement (beware, simple minded code) in this way:

:- meta_predicate solutions(0, ?).
:- meta_predicate solutions(+, 0, ?).

solutions(G, L) :-
    solutions(G, G, L).

solutions(P, G, L) :-
    ( nb_current(solutions_depth, C) -> true ; C=1 ),
    D is C+1,
    nb_setval(solutions_depth, D),
    atom_concat(solutions_depth_, D, Store),
    nb_setval(Store, []),
    (   G,
        nb_getval(Store, T),
        nb_setval(Store, [P|T]),
        fail
    ;   nb_getval(Store, R)
    ),
    nb_delete(Store),
    nb_setval(solutions_depth, C),
    reverse(R, L).

Usage of 'global' variables results in more efficient execution WRT the dynamic database (assert/retract), and (in SWI-prolog) can be used even in multithreaded applications.

edit

Thanks to @false comment, moved the cut(s) before reverse/2, and introduced a stack for reentrant calls: for instance

?- solutions(X-Ys,(between(1,3,X),solutions(Y,between(1,5,Y),Ys)),S).
S = [1-[1, 2, 3, 4, 5], 2-[1, 2, 3, 4, 5], 3-[1, 2, 3, 4, 5]].

edit

Here is a variant of solutions/3, building the result list in order, to avoid the final reverse/2 call. Adding results to the list tail is a bit tricky...

solutions(P, G, L) :-
    ( nb_current(solutions_depth, C) -> true ; C=1 ),
    D is C+1,
    nb_setval(solutions_depth, D),
    atom_concat(solutions_depth_, D, Store),
    (   G,
        ( nb_current(Store, U/B) -> B = [P|R], Q = U/R ; Q = [P|T]/T ),
        nb_setval(Store, Q),
        fail
    ;   ( nb_current(Store, L/[]) -> true ; L = [] )
    ),
    nb_delete(Store),
    nb_setval(solutions_depth, C).

Answer 2

Yes, if findall/3 were not available, you could implement it for example via the dynamic database.

For example, for the concrete use case of parents:

list_parents(_) :-
        parent(P, _),
        assertz(parent(P)),
        false.
list_parents(Ps) :-
        phrase(retract_parents, Ps).

retract_parents -->
        (   { retract(parent(P)) } ->
            [P],
            retract_parents
        ;   []
        ).

Sample query:

?- list_parents(Ps).
Ps = [pam, george].

You can combine this with sort/2 for asymptotically optimal performance, avoiding the quadratic overhead of the "naive" solution to remove duplicates.

Beware though: First, this is not thread-safe. To make it thread-safe you need to add more information pertaining to the current thread.

Second, if you implement full-fledged findall/3 in this way, you must take care of nested findall/3 calls.

One way to do this is to assert two kinds of terms:

• solution(S), such as solution(parent(pam)), indicating a concrete solution that was found on backtracking via the most recent findall/3 call
• mark, indicating that a new findall/3 starts here

When collecting solutions, you only proceed to the most recent mark.

See Richard O'Keefe's book for a good introduction to these issues.