Alternative to tabling for transitive closures

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(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)

With 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(: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,Opts) :-
   option(end(End),Opts,inf),  % default to try infinite iterations
   ignore(option(depth_reached(Depth), Opts)),

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('% '),
   ;  true

EDIT: leave only meta-call in the code.

1 Like