Use SWI-Prolog engines to incrementally compute and memoize solutions to a goal.

memo.pl

% -*-Prolog-*-
:-module(memo, [ incremental/1 ]).

:- meta_predicate(insist(0)).
insist(G) :-
    (   G
    *-> true
    ;   assertion(G)
    ).

:- dynamic key_engine_known/3.
goal_engine_known(G, E, K) :-
    fast_term_serialized(G, Key),
    key_engine_known(Key, E, K), !.

goal_engine_known(G, E, K) :-
    fast_term_serialized(G, Key),
    copy_term(G, GG),
    engine_create(GG, GG, E),
    K = [],
    asserta(key_engine_known(Key, E, K)).

goal_completed(G) :-
    goal_engine_known(G, E, _),
    completed(E).

completed(completed).

%% incremental(Goal) should behave as call(Goal).
%  The implementation achieves a memoization for a specific usage pattern.
%  The first time incremental(Goal) is called for a specific goal, an engine
%  is created and associated with the goal (via dynamic assert). As backtracking
%  generates more solutions to Goal, these are stored as "known" solutions.
%  Backtracking may be stopped before all solutions are found. Later, if
%  incremental(Goal) is called with the same Goal, the known solutions are supplied
%  first, THEN then engine is consulted if/when more solutions are required.
%
%  Note that `fast_term_serialized(Goal, Key)` is used for keying asserted data
%  so a Goal is keyed based on it's "structure" (see =@=).
%  `incremental(foo(1,X))` and `incremental(foo(1,Y))` will share the same key
%  and solutions assuming that X and Y are both vars at the time of calling.    
:- meta_predicate(incremental(0)).
incremental(Goal) :-
    (   goal_completed(Goal)
    ->  known_(Goal)
    ;   (  known_(Goal)
        ;  remainder_(Goal)
        )
    ).

rember(X, [H|T]) :-
    (  rember(X, T)
    ;  X = H
    ).

:- meta_predicate(known_(0)).
known_(Goal) :-
    goal_engine_known(Goal, _, Known),
    rember(Goal, Known).

:- meta_predicate(remainder_(0)).
remainder_(Goal) :-
    goal_engine_known(Goal, Engine, Known),
    \+ completed(Engine),
    fast_term_serialized(Goal, Key),
    retract(key_engine_known(Key, _, _)),
    !,
    (   engine_next(Engine, Next)
    ->  NewKnown = [Next | Known],
        asserta(key_engine_known(Key, Engine, NewKnown)),
        (   Goal = Next
        ;   remainder_(Goal)
        )
    ; insist(engine_destroy(Engine)),
      insist(asserta(key_engine_known(Key, completed, Known))),
      !,
      fail
    ).