Alternative to tabling for transitive closures

Useful Code
1

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)

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

1 Like