Engines can be used to reason about solutions produced by a goal
through backtracking. In this scenario we create an engine with the goal
we wish to backtrack over and we enumerate all its solution using engine_next/2.
This usage scenario competes with the all solution predicates (findall/3, bagof/3,
etc.) and the predicates from library
library(aggregate). Below we implement findall/3
using engines.
findall(Templ, Goal, List) :-
setup_call_cleanup(
engine_create(Templ, Goal, E),
get_answers(E, List),
engine_destroy(E)).
get_answers(E, [H|T]) :-
engine_next(E, H), !,
get_answers(E, T).
get_answers(_, []).
The above is not a particularly attractive alternative for the
built-in
findall/3.
It is mostly slower due to time required to create and destroy the
engine as well as the (currently210The
current implementation of engines is built on top of primitives that are
not optimal for the engine use case. There is considerable opportunity
to reduce the overhead.) higher overhead of copying terms
between engines than the overhead required by the dedicated
representation used by
findall/3.
It gets more interesting if we wish to combine answers from multiple
backtracking predicates. Assume we have two predicates that, on
backtracking, return ordered solutions and we wish to merge the two
answer streams into a single ordered stream of answers. The solution in
classical Prolog is below. It collects both answer sets, merges them
using ordered set merging and extract the answers. The code is clean and
short, but it doesn't produce any answers before both generators are
fully enumerated and it uses memory that is proportional to the combined
set of answers.
:- meta_predicate merge(?,0, ?,0, -).
merge_answers(T1,G1, T2,G2, A) :-
findall(T1, G1, L1),
findall(T2, G2, L2),
ord_union(L1, L2, Ordered),
member(A, Ordered).
We can achieve the same using engines. We create two engines to
generate the solutions to both our generators. Now, we can ask both for
an answer, put the smallest in the answer set and ask the engine that
created the smallest for its next answer, etc. This way we can create an
ordered list of answers as above, but now without creating intermediate
lists. We can avoid creating the intermediate list by introducing a
third engine that controls the two generators and yields the
answers rather than putting them in a list. This is a general example of
turning a predicate that builds a set of terms into a non-deterministic
predicate that produces the results on backtracking. The full code is
below. Merging the answers of two generators, each generating a set of
10,000 integers is currently about 20% slower than the code above, but
the engine-based solution runs in constant space and generates the first
solution immediately after both our generators have produced their first
solution.
:- meta_predicate merge(?,0, ?,0, -).
merge(T1,G1, T2,G2, A) :-
engine_create(A, merge(T1,G1, T2,G2), E),
repeat,
( engine_next(E, A)
-> true
; !, fail
).
merge(T1,G1, T2,G2) :-
engine_create(T1, G1, E1),
engine_create(T2, G2, E2),
( engine_next(E1, S1)
-> ( engine_next(E2, S2)
-> order_solutions(S1, S2, E1, E2)
; yield_remaining(S1, E1)
)
; engine_next(E2, S2),
yield_remaining(S2, E2)
).
order_solutions(S1, S2, E1, E2) :- !,
( S1 @=< S2
-> engine_yield(S1),
( engine_next(E1, S11)
-> order_solutions(S11, S2, E1, E2)
; yield_remaining(S2, E2)
)
; engine_yield(S2),
( engine_next(E2, S21)
-> order_solutions(S1, S21, E1, E2)
; yield_remaining(S1, E1)
)
).
yield_remaining(S, E) :-
engine_yield(S),
engine_next(E, S1),
yield_remaining(S1, E).
