1:- module(fluent, [
2 fluent_create/3,
3 fluent_get/3,
4 fluent_destroy/1]).
81%:- debug(fluent). 82 83:- meta_predicate fluent_create( , , ).
92fluent_create(Template, Goal, fluent(Thread, ResponseQueue)) :-
93 message_queue_create(ResponseQueue),
94 thread_create(fluent_work(Template, Goal, ResponseQueue), Thread, []).
If the goal in the fluent exits, Solution is unified with a copy of the
corresponding instantiation of the template given when the fluent was
created, and Exit is unified with det
or nondet
depending on
whether the goal exited without or with open choicepoints.
If the goal in the fluent raises an exception while trying to get the
next solution, fluent_get/3
re-raises it.
After all solutions are exhausted, all subsequent calls to
fluent_get/3
on this fluent fail (until it is destroyed).
111fluent_get(fluent(Thread, ResponseQueue), Template, Exit) :- 112 thread_send_message(Thread, next), 113 thread_get_message(ResponseQueue, Message), 114 ( Message = exception(Exception) 115 -> raise_exception(Exception) 116 ; Message = solution(Template, Exit) 117 ). % fail if Message is =end=
fluent_get/3
will
raise an exception.126fluent_destroy(fluent(Thread, ResponseQueue)) :- 127 thread_send_message(Thread, done), 128 thread_join(Thread, _), 129 message_queue_destroy(ResponseQueue). 130 131fluent_work(Template, Goal, ResponseQueue) :- 132 % Decide whether to try to get the first solution: 133 thread_get_message(Message0), 134 ( Message0 == next 135 -> ( % Get and send solutions (or exceptions) as we backtrack: 136 catch( 137 ( call_cleanup(Goal, D = true), 138 ( D == true -> Exit = det ; Exit = nondet ), 139 thread_send_message(ResponseQueue, solution(Template, Exit)) 140 ), Exception, 141 ( thread_send_message(ResponseQueue, exception(Exception)) 142 ) ), % when this fails, we go into the second fluent_work/3 clause 143 % Decide whether to try to get another solution: 144 thread_get_message(Message), 145 ( Message == next 146 -> fail % backtrack into Goal 147 ; ! % fluent destroyed, succeed deterministically 148 ) 149 ) 150 ; !). % fluent destroyed before 1st solution, succeed deterministically 151fluent_work(_, _, ResponseQueue) :- 152 repeat, % allow client to keep requesting solutions, 153 thread_send_message(ResponseQueue, end), % always answer end 154 thread_get_message(Message), 155 ( Message == next 156 -> fail % backtrack to repeat 157 ; ! % make fluent_work/3 goal succeed deterministically 158 )
Access all solutions of a goal without backtracking
This module lets you turn any goal into a Fluent (Tarau 2002). A Fluent, as defined here, is a stateful object that encapsulates a Prolog goal as it is interpreted. The solutions generated by the encapsulated goal on backtracking can be accessed by the caller without backtracking.
This is useful e.g. for iterating over solutions while building up a data structure (which would be destroyed by backtracking) or to solve several goals in parallel while keeping the solutions in sync (e.g. “zipping”), while avoiding error-prone and/or inefficient tricks like non-backtrackable assignment or materializing lists of solutions.
This implementation achieves backtracking-free access by delegating the backtracking to a separate Prolog thread that sends copies of solutions back to the calling thread via message queues, on demand. This technique was described by Samer Abdallah on the SWI-Prolog mailing list. The implementation was also inspired by Michael Hendricks’
lazy_findall
implementation.Example usage: