SWI-Prolog Did You Know Did you know? ETALIS Event Processing runs on SWI-Prolog Search Documentation:
Predicate call_with_depth_limit/3
Availability:built-in
Sourcecall_with_depth_limit(:Goal, +Limit, -Result)
If Goal can be proven without recursion deeper than Limit levels, call_with_depth_limit/3 succeeds, binding Result to the deepest recursion level used during the proof. Otherwise, Result is unified with depth_limit_exceeded if the limit was exceeded during the proof, or the entire predicate fails if Goal fails without exceeding Limit.

The depth limit is guarded by the internal machinery. This may differ from the depth computed based on a theoretical model. For example, true/0 is translated into an inline virtual machine instruction. Also, repeat/0 is not implemented as below, but as a non-deterministic foreign predicate. 

repeat.
repeat :-
        repeat.

As a result, call_with_depth_limit/3 may still loop infinitely on programs that should theoretically finish in finite time. This problem can be cured by using Prolog equivalents to such built-in predicates.

This predicate may be used for theorem provers to realise techniques like iterative deepening. See also call_with_inference_limit/3. It was implemented after discussion with Steve Moyle smoyle@ermine.ox.ac.uk.

Tags are associated to your profile if you are logged in
Tags:
LogicalCaptain said (2020-12-23T10:47:38):0 upvotes 0 0 downvotes
Picture of user LogicalCaptain.

Examples

true/0 needs depth 1:

?- call_with_depth_limit(true,0,R).
R = depth_limit_exceeded.

?-
call_with_depth_limit(true,1,R).
R = 1.

So does false/0:

?- call_with_depth_limit(false,0,R).
R = depth_limit_exceeded.

?- call_with_depth_limit(false,1,R).
false.

So does is_list/1

?- call_with_depth_limit(is_list([a,b,c]),1,R).
R = 1.

random_between/3 needs depth 2:

?- call_with_depth_limit(=random_between=(0,100,X1),1,R).
R = depth_limit_exceeded.

?- call_with_depth_limit(random_between(0,100,X1),2,R).
X1 = 72,
R = 2.

It's stacked!

A call_with_depth_limit/3 within a call_with_depth_limit/3 does not work in a "limited by both" fashion.

Instead, while the inner call_with_depth_limit/3 is active, it's the one which counts, and the outer limit is disregarded. Once the Prolog processor backs out of the inner call_with_depth_limit/3 due to excessive depth, failure or success, the outer call_with_depth_limit/3 is in effect again.

How about tail call optimization?

Apparently the mechanism behind call_with_depth_limit continues to count up on calls that are subject to tail-call optimization.

This is what one wants.

See the test code below which can be nicely optimized but which is still properly limited.

Some code for experiments

deeper.pl