The typical transitive closure problem can also easily be solved (in addition to tabling) by successive deepening of the recursion depth. If we have the typical path problem:
path(a,b). path(b,c). path(c,d). path(X,Y) :- path(X,Z), path(Z,Y).
With regular prolog we get a stack overflow:
18 ?- findall((A,B), path(A,B),Sols). ERROR: Stack limit (1.0Gb) exceeded ERROR: Stack sizes: local: 1.0Gb, global: 26Kb, trail: 1Kb ERROR: Stack depth: 12,197,269, last-call: 0%, Choice points: 8 ERROR: Probable infinite recursion (cycle): ERROR: [12,197,269] user:path(d, _6788) ERROR: [12,197,268] user:path(d, _6808)
call_iterating_depth/1 we get solutions:
22 ?- findall((A,B), call_iterating_depth(path(A,B)), Sols). Sols = [(a, b), (b, c), (c, d), (a, c), (a, d), (b, d), (a, d)].
call_iterating_depth/1 has a default start depth of 3, which is enough to find all the solutions for
path(A,B); but since it stops at the first depth for which there is a solution, we can also reduce the number of solutions (for example, if we had a very large set and we just cared about some solutions):
% Gives us only 5 solutions instead of 6 23 ?- findall((A,B), call_iterating_depth(path(A,B),[start(2)]), Sols). Sols = [(a, b), (b, c), (c, d), (a, c), (b, d)].
Increasing the start depth further has no effect, because we already found all solutions:
% Does not use more resources 24 ?- findall((A,B), call_iterating_depth(path(A,B),[start(20)]), Sols). Sols = [(a, b), (b, c), (c, d), (a, c), (a, d), (b, d), (a, d)].
I find this usage of successively deepening recursion depth (A.K.A iterative deepening) extremely useful.
If you want to try using
call_iterating_depth/[1,2] here is the code:
:- meta_predicate call_iterating_depth(0), call_iterating_depth(0,?). %! call_iterating_depth(:Goal, Options). % % Call Goal with increasingly recursive depths until at least one % solution is found. % % % This is useful when we have a recursive goal. This predicate allows % termination for goals with infinite recursion, something not % normally possible with regular prolog. % % Goal is tried with deeper recursion depths, stepped by Step, until % End depth is reached. % % Succeeds (and stops trying further depths) if the original goal % succeeds at least once. It fails silently if no solutions are % found, or if it reaches the End depth. It provides all backtracking % solutions as the original goal, but limited by the recursion depth. % % If you have a goal that backtracks witth increasing number of % solutions as you increase the depth, you can set the Start % parameter to a higher number to get more solutions. % % End can be `inf` to keep trying new depths until a solution % is found (if no solution is found, and End is `inf`, then % `iterate_depth` will not terminate). % % call_iterating_depth(Goal) :- call_iterating_depth(Goal,). call_iterating_depth(Goal,Opts) :- option(start(Start),Opts,3), option(step(Step),Opts,1), option(end(End),Opts,inf), % default to try infinite iterations ignore(option(depth_reached(Depth), Opts)), iterate_depth_(Goal,Start,Step,End,Depth). iterate_depth_(Goal,Start,Step,End, Result) :- Start =< End, ( try_depth(Goal,Start,Result) *-> true ; Start1 is Start + Step, iterate_depth_(Goal, Start1,Step,End,Result) ). try_depth(Goal,Depth,Result) :- dbg('Trying depth ~w',[Depth]), call_with_depth_limit(Goal, Depth, Result), Result \== depth_limit_exceeded. dbg(Fmt,Args) :- ( debugging(iterate_depth) -> write('% '), format(Fmt,Args), nl ; true ).
EDIT: leave only meta-call in the code.