implementation of findall 
Author Message
 implementation of findall

Hi

Has anyone collected statistics about how findall (and family) are
actually used in *real* programs (whatever *real* programs are supposed
to be)?

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:
        (i)     the number of solutions generated
        (ii)    the size of the solutions
        (iii)   the degree to which calls to findall are nested

Has anyone collected actual data on any of these things, or does everyone
just guess?

Thomas
--
Thomas Conway                                           MAKE BIGNUMS FAST!!!!
AD DEUM ET VINUM                                        Use G\"odel encoding.



Mon, 05 Jul 1999 03:00:00 GMT  
 implementation of findall



Quote:
>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:
>        (i)     the number of solutions generated
>        (ii)    the size of the solutions
>        (iii)   the degree to which calls to findall are nested

Although the main issue in the posting is a question about
statistics of using findall, I will 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 those who write a GC for
such a system :-).

However, if I would have to do it again, from scratch, I would make it
sure that GC can stay quite simple, first. I would also address the
issue of "laziness" of findall, from start. The cleanest way to have
this, requires multiple engines (as in BinProlog, see
library/engines.pl) or some equivalent construct i.e. some form of
re-entrant multiple communicating `interpreters'. If one engine takes
the role of an `oracle' giving to the other engine(s) goal(s) and then
asking for as many answers as it needs, we get very close to Java's
Enumeration interface (also used in other OO languages).  This allows
seeing the answers as a stream.  Findall then becomes trivial i.e. just
collecting the answers to a `list' (actually any form of abstract
sequence will do, even another enumeration or a stream of Linda out/1
operations to a server over the net):

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 slower than BinProlog's built-in findall/3,
see benchmarks eperms.pl vs. allperms.pl in the BinProlog
distribution at:
  http://clement.info.umoncton.ca/BinProlog/UNCOMPRESSED/progs,
but still faster than in most other Prologs around.

To try this out in BinProlog, just type:

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

However, if I would do it again, I would use dynamic arrays (like in
Java's Vector class), despite the (small) constant price it would add.
The only excuse for default_engine_params(200,100,100) is resource
control (important for security over the net), but this should
be a unique parameter for the whole system.

Note that engines make sense even without threads, but of course,
combining the too really makes you fly :-)

And finally, once you start playing with engines, no need for
findall at all :-). Actually you can just ask the answers one by one
when and as far as you need them, most of the time.

Paul Tarau



Mon, 05 Jul 1999 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. findall implementation possible?

2. patch for string.findall (why not, theres an re.findall)

3. Where is /pat/g (Perl) and findall() (Python )?

4. Where is /pat/g (Perl) and findall() (Python)?

5. Regular Expression: Bug in findall?

6. AttributeError in re.findAll ?

7. Bug in re.findall()?

8. Way to return a dictionary from re.findall?

9. re findall mod for issue of side effects

10. Alex Martinelli's solution to regular expression/findall problem

11. Problem with re.findall?????!!!!!!!!!!

12. HELP findall please???

 

 
Powered by phpBB® Forum Software