Implementation of findall

Appeared in Volume 10/2, May 1997

Keywords: findall.

conway@cs.mu.oz.au
Thomas Charles Conway
16th January 1997

Has anyone collected statistics about how findall (and family) are actually used in programs?

We've been looking at the implementation of the Mercury equivalent: solutions/2. There are various tradeoffs in the implementation - you can do copy-once, copy-twice, bubble-in-the-heap, multiple-findall-heaps, and more variations besides. Which implementation to use intuitively depends on:

the number of solutions generated
the size of the solutions
the degree to which calls to findall are nested

tarau@clement.info.umoncton.ca
Paul Tarau
16th January 1997

Although your posting is mainly about the statistics of using findall, I'll address the implementation issue, hoping it will save some time to others :-)

BinProlog's findall is quite fast, and based on splitting the heap in two, working in the upper zone and copying back the solutions. I guess this is a copy-once technique in your terms. It is re-entrant if you are careful, and really ugly only for the people writing the GC :-).

However, if I had to do it again, I would make sure that the GC stayed simple. I would also address the "laziness" of findall from the start. The cleanest way to have this requires multiple engines (as in BinProlog), or some equivalent construct such as re-entrant multiple communicating 'interpreters'. If one engine takes the role of an 'oracle', giving goal(s) to other engine(s) and asking for answers, then we get very close to Java's Enumeration interface. This allows the answers to be viewed as a stream. Findall then becomes trivial i.e. just storing the answers in a 'list' (or other sequence).

find_all(X,Goal,Xs):-
    default_engine_params(H,S,T),
    find_all(H,S,T,X,Goal,Xs).

find_all(H,S,T,X,Goal,Xs):-
    new_engine(H,S,T,Goal,X,Handle),
    collect_answers(Handle,Xs),
    destroy_engine(Handle).

collect_answers(Handle,[X|Xs]):-
    ask_engine(Handle,A), !,
    copy_term(A,X),
    collect_answers(Handle,Xs).
collect_answers(_,[]).

new_engine(H,S,T,Goal,Answer,Handle):-
    create_engine(H,S,T,Handle),
    load_engine(Handle,Goal,Answer).

This is about twice as slow as BinProlog's built-in findall/3, but still faster than most other Prologs.

To try this out in BinProlog, type:

?-default_engine_params(200,100,100) => 
      find_all(X,member(X,[1,2,3]),Xs).

However, if I was doing it again, I would use dynamic arrays (as in Java's Vector class), despite the (small) constant price it would add.

Engines make sense even without threads, but having both gives a powerful set of implementatioin primitives for building everything else.

And finally, once you start playing with engines, there is no need for findall at all :-). You can just ask for the answers one by one, when you need them.

No Next