Goal is always executed at least once, even if it's not strictly necessary. Goal may be executed in advance, even if the associated value in List has not been demanded yet. This should only be important if Goal performs side effects whose timing is important to you.
If you don't consume all of List, it's likely that a worker thread will be left hanging. This is a temporary implementation detail which we hope to resolve.
14:- meta_predicate lazy_findall( , , ), lazy_findall_search( , , ). 15lazy_findall(Template,Goal,List) :- 16 lazy_findall_flow(Template,Goal,Flow), 17 ( next(Flow,Value0) -> % eager first value (to detect instant failure) 18 finalize_value(Flow,Value0,Value), 19 List=[Value|Rest], 20 flow_to_llist(Flow,Rest) 21 ; otherwise -> 22 List=[] 23 ). 24 25lazy_findall_search(ResponseQ,Template,Goal) :- 26 call_ended(Goal,Ended), 27 ( Ended=more -> % Goal has unexplored choicepoints 28 thread_get_message(send_a_solution), 29 thread_send_message(ResponseQ,a_solution(Template)), 30 fail % explore other choicepoints 31 ; Ended=done -> % Goal found final solution 32 lazy_findall_final(ResponseQ,just(Template)) 33 ; Ended=fail -> 34 lazy_findall_final(ResponseQ,nothing) 35 ; Ended=exception(E) -> 36 lazy_findall_final(ResponseQ,exception(E)) 37 ). 38 39lazy_findall_final(ResponseQ,Solution) :- 40 thread_send_message(ResponseQ,final_solution), 41 thread_exit(Solution).
fail
- Goal faileddone
- Goal produced its final solution (no choicepoints left)more
- backtracking will produce more solutionsexception(E)
- Goal threw an exception53:- meta_predicate call_ended( , ). 54call_ended(Goal,End) :- 55 ( catch(call_cleanup(Goal,End=done),E,End=exception(E)) *-> 56 ( var(End) -> End=more ; ! ) 57 ; otherwise -> 58 End=fail, ! % Goal failed immediately 59 ). 60call_ended(_,fail). % Goal fails on backtracking 61 62 63:- meta_predicate lazy_findall_flow( , , ). 64lazy_findall_flow(Template,Goal,Flow) :- 65 gensym(lazy_findall_,ThreadAlias), % see Note_findall_alias 66 message_queue_create(ResponseQ,[max_size(1)]), 67 thread_create( 68 lazy_findall_search(ResponseQ,Template,Goal), 69 _ThreadId, 70 [alias(ThreadAlias)] 71 ), 72 Flow = findall_flow(ThreadAlias,ResponseQ). 73 74/* 75Note_findall_alias: 76 77To implement flow:at_eof/1 we must be able to recognize when a thread no longer 78exists. SWI-Prolog's default thread IDs are reused after a thread's resources 79are garbage collected. If we used the default thread IDs, we might encounter the 80following scenario: 81 82 1. we start lazy_findall/3 83 2. our worker thread exits 84 3. another thread starts 85 4. at_eof/1 thinks the worker thread still exists 86 87By using gensym/2 and a thread alias, we can be certain that our thread ID is 88never reused. 89*/ 90 91at_eof(findall_flow(Thread,_ResponseQ)) :- 92 ( thread_exists(Thread) -> 93 thread_property(Thread,status(exited(nothing))), 94 thread_join(Thread,_) 95 ; otherwise -> % worker is gone. flow is finished 96 true 97 ), 98 % invariant at this point: worker thread is gone 99 true. 100 101thread_exists(Thread) :- 102 catch(thread_property(Thread,status(_)), _, fail). 103 104 105next(findall_flow(Thread,ResponseQ),Solution) :- 106 catch(thread_send_message(Thread,send_a_solution),_,true), % maybe thread's gone 107 thread_get_message(ResponseQ,Response), 108 findall_next(Response,Thread,Solution). 109 110findall_next(a_solution(X),_,just(X)). 111findall_next(final_solution,Thread,Solution) :- 112 % final solution is waiting. join worker thread to receive it 113 thread_join(Thread,exited(MaybeSolution)), 114 ( MaybeSolution=nothing -> 115 fail % final solution was a spurious choicepoint 116 ; otherwise -> 117 Solution=MaybeSolution 118 ). 119 120 121finalize_value(findall_flow(_,_),X0,X) :- 122 lazy_findall_finalize_value(X0,X). 123 124lazy_findall_finalize_value(just(X),X). 125lazy_findall_finalize_value(exception(E),_) :- 126 throw(E)