Would a lazy findall be desirable?

[dougransom]

Does findall need to be greedy be be ISO compliant?

?- $( (findall(a(X),a(X),L), [_,C]=L)).
call:(findall(a(A),user:a(A),B),[C,D]=B).
exit:(findall(a(A),user:a(A),[a(1),a(2)]),[a(1),a(2)]=[a(1),a(2)]).
   L = [a(1),a(2)], C = a(2).
?- 

I used the trace $ just to show the whole list is generated currently before further unifications ocurr.

Would a version of findall that produces a lazy list be desirable or ISO compliant?

I would expect a lazy findall to work like this:

?- findall(a(X),a(X),L).
   L = [a(1)|Ls].
?- 

Would the implementation be through using cont:shift and cont:reset?

[UWN]

Would a version of findall that produces a lazy list be desirable or ISO compliant?

I would expect a lazy findall to work like this:

?- findall(a(X),a(X),L).
   L = [a(1)|Ls], unexpected.

This would be non-conforming behavior. A minimal example is

?- findall(t, ( true ; throw(exception) ), Ts).
   throw(exception).

So effectively it is necessary to explore all leaf answers.

But experimenting with another form of findall might make sense. Just do not call it findall/3.

[dougransom]

I have been experimenting and having a lot of trouble creating something like a generator in Scyrer prolog that returns one solution at a time.

% lazy_list(+Pred, -List-Tail)
% Pred must be a predicate of arity 1, e.g. a(X)
lazy_list(Pred, List-Tail) :-
    lazy_step(Pred, List-Tail).


lazy_step(Pred, [X|Rest]-Tail) :-
    call(Pred, X),
    format("Lazy step ~w X:~w ~n", [Pred, X]),
    lazy_list(Pred, Rest-Tail).

lazy_step(Pred, List-Tail) :-
    \+ call(Pred, _),
    List = Tail.

a(2).
a(9).
a(7).

I also tried a solution using shift and reset.

Here is an explanation from copilot:

"Scryer does NOT preserve choice points across recursive calls.
This is different from SWI, SICStus, YAP, and most other Prologs.
...
Scryer uses a different WAM model:

It aggressively trims environments

It aggressively discards choice points when entering new predicates

It does not keep generator choice points alive across recursion

This is why your continuation experiments also failed earlier — Scryer’s execution model is not designed for multi‑resume generators.
"

Is that correct that Scryer handles recursion differently than other Prologs? How might I proceed with a lazy list implementation?

[dougransom]

Here is another approach that also failed:

:- use_module(library(freeze)).
:- use_module(library(cont)).

lazy_gen(Template, Generator) :-
    call(Generator),
    shift(Template),
    fail.
lazy_gen(_, _).

findall_lazy(Template, Generator, Stream) :-
    once(reset(lazy_gen(Template, Generator), Ball, Cont)),
    build_stream(Ball, Cont, Stream).

build_stream(done, _, []).
build_stream(Value, Cont, [Value|Tail]) :-
    freeze(Tail, (
        cont:call_continuation(Cont),
        reset(true, Ball2, Cont2),
        build_stream(Ball2, Cont2, Tail)
    )).


a(115).
a(7).
a(9).
 
 ?- G=a(_), findall_lazy(G,G,L), [X1|Xs]=L.
   G = a(115), L = [a(115)|Xs], X1 = a(115), freeze:freeze(Xs,(cont:call_continuation(cont(cont:call_continuation([cont_chunk(dir_entry(89361),a(115))]))),user:reset(true,_A,_B),user:build_stream(_A,_B,Xs))).
?- G=a(_), findall_lazy(G,G,L), [X1,X2|Xs]=L.
   error(type_error(list,cont(cont:call_continuation([cont_chunk(dir_entry(89361),a(115))]))),call_continuation/1).
?- 

[bakaq]

This is something I have been trying to do for a long time. I'm pretty sure this either needs support for doing continuations "between choicepoints" (which I'm not sure what the semantics should be), or built-in language support. I believe this would be a really important building block for interlacing IO with pure Prolog, something that is awkward to do even with library(pio) today. As an example, this would make it possible to implement the toplevel in significantly purer code than what is used right now.

The interface for this that I imagine is something like this:

% Generates an iterator for a given goal. 
call_leaf_answer_iter(Goal_0, Iter).

% Gets the next leaf answer out of that iterator.
% To be useful for things such as the top level, this probably needs
% to represent if the goal is pending or not. So, using the
% same encoding that I did at the toplevel implementation,
% `LeafAnswer` here would be either `pending/1` or `final/1`.
% If you get a `final/1`, then the iteration ended.
% The arguments to `pending/1` and `final/1` can be something like:
% - `leaf_answer(BindingsPairList, ResidualGoals, VarNames)`
% - `true` (alternatively, just use `leaf_answer([],[],[])`)
% - `false` (only makes sense with `final/1`)
% - `exception(E)` (only makes sense with `final/1`)
leaf_answer_iter_next(Iter0, Iter, LeafAnswer).

You could also imagine an interface which hides non-determinism ("tail false"), bubbles exceptions, etc... The important part here is that you could step through the leaf answers gradually, even if the predicate never terminates. You can't do this with findall/3.

Like I said, I think it's impossible to implement this interface without adding more features to the engine. The closest I ever got was what I did in the toplevel, using "choicepoint anchors" with callbacks, but that obviously makes the program have a completely different, and in my opinion much less elegant, shape.

[dougransom]

I shall give up my attempts.

I think it would be pretty cool though, since you could have a rule with a lot of matches but only the match currently considered needs to be accessible by the program. And possibly efficient in memory use.

I was also thinking the all solutions predicates could have the number of matches.

findall_count(G,L,N).

Lazy or not, if you want to know the number of elements it could be useful to know the number of matches.