# Iterative Deepening and Cuts

**URL:** <https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030>\
**Category:** Help!\
**Created:** [October 11, 2020, 3:55pm UTC](https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030 "2020-10-11T15:55:52Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![aminemarref](https://avatars.discourse-cdn.com/v4/letter/a/7feea3/32.png) [@aminemarref](https://swi-prolog.discourse.group/u/aminemarref)\
**Post date:** [October 11, 2020, 3:55pm UTC](https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030/1 "2020-10-11T15:55:52Z")

</div>

Hello,

I am using iterative-deepening in my program and recently met a case that I want to inquire about.

I have a predicate that is written as:

> ```
> p(X):- q(X),!.
> p(X):- g(X).
> 
> ```

The solution to predicate `q/1` is deep in the search tree compared to the solution of `g/1`. When using iterative deepening, the solution to `p/1` that goes through the choice `g/1` is returned first because the choice `q/1` hits the current depth limit of the iterative-deepening depth-first search.

Is there a way I can retain my cut’s power in iterative deepening such that the choice `g/1` is only evaluated when `q/1` fails logically, not because of depth limit?

Many thanks,  
A.

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [October 11, 2020, 4:33pm UTC](https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030/2 "2020-10-11T16:33:41Z")

</div>

> [@aminemarref](#):
>
> choice `g/1` is only evaluated when `q/1` fails logically, not because of depth limit?

Why does this matter? If you fail because of depth, the next (deeper) iteration can succeed.

It’s also possible that rewriting your code this way would give you a better result (assuming it’s OK for q(X) to succeed multiple times):

```prolog
p(X) :-
    ( q(X)
    *-> true
    ; g(X)
    ).

```

---

<div class="post-metadata">

**Author:** ![aminemarref](https://avatars.discourse-cdn.com/v4/letter/a/7feea3/32.png) [@aminemarref](https://swi-prolog.discourse.group/u/aminemarref)\
**Post date:** [October 11, 2020, 4:43pm UTC](https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030/3 "2020-10-11T16:43:10Z")

</div>

Thanks for the prompt help,

The program returns solutions, some of which are “better” than others, so I have “best” answers, and “acceptable” answers. I want to return the best answer first; and return acceptable answers only when the best answer fails.

I will try using [`(*->)/2`](https://www.swi-prolog.org/pldoc/doc_for?object=(*-%3E)/2) like you mentioned, that might work 🙂

Cheers,  
A.

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [October 11, 2020, 5:01pm UTC](https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030/4 "2020-10-11T17:01:24Z")

</div>

> [@aminemarref](#):
>
> I want to return the best answer first; and return acceptable answers only when the best answer fails.

If you’re using iterative deepening, presumably the code can go into an infinite loop without returning a “best” answer. So, I don’t see a general solution.

Perhaps you need some kind of hybrid strategy, allowing potentially “good” solutions to iterate more (or to count as less than 1 when computing depth); or maybe increasing the depth by a larger number each time; or combining with breadth-first; or (maybe someone else has a better imagination than me) …

---

<div class="post-metadata">

**Author:** ![logicmoo](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/logicmoo/32/193_2.png) [@logicmoo](https://swi-prolog.discourse.group/u/logicmoo)\
**Post date:** [October 14, 2020, 10:13pm UTC](https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030/5 "2020-10-14T22:13:30Z")

</div>

Jan Wielemaker 18 years ago

[Permalink](https://narkive.com/GAgj4vwn.6)

Douglas,

[\*Post by \*\*_@users.sourceforge.net_](https://swi-prolog.iai.uni-bonn.narkive.com/GAgj4vwn/getting-how-many-prolog-frames-a-particular-variable-has-existed-in-thus-far#post5)

```prolog
:-ensure_loaded(depth_bound_varible_term_expanions).
p(X):-q(X).
q(a).
q(X):-p(X).
q(b).

```

converts into:

```prolog
p(A):-depth_of_var(A,B),B<3,q(A).
q(a).
q(A):-depth_of_var(A,B),B<3,p(A).
q(b).

```

I _think_ I understand your problem. It isn’t hard to code this at the  
C-level. Below is the implementation. Save this file in  
depth\_of\_var.c in the directory you built SWI-Prolog (you need a version  
built from source) and build it using

plld -o depth\_of\_var -shared -I. -I…/src depth\_of\_var.c

Now use ?- load\_foreign\_library(depth\_of\_var).

to get your new predicate. NOTE NOTE NOTE: unlike normal foreign code  
this code relies on details of the machinery normally not public. So,  
it may stop working and you better recompile it before using it with  
a new version of Prolog.

```prolog
---cut here -----------------------------------------------------------
#include "pl-incl.h"

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
depth_of_var(+Var, -Depth)

Dereference the term Var. If the dereferenced chain ends on the local
stack, return the call-depth difference between my parent frame and the
frame in which Var was created.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

static foreign_t
depth_of_var(term_t var, term_t depth)
	{ Word v = valTermRef(var);
	LocalFrame fr = environment_frame;
	long l0 = levelFrame(fr)-1; /* -1: Use my parent as reference */
	
	deRef(v);
	if ( onStackArea(local, v) )
	{ DEBUG(0, Sdprintf("Ok, on local stack\n"));
	while(fr && fr > (LocalFrame)v)
	fr = parentFrame(fr);
	if ( fr )
	{ l0 -= levelFrame(fr);
	return PL_unify_integer(depth, l0);
	}
	} else
DEBUG(0, Sdprintf("Not on local stack\n"));

fail;
}

install_t
install()
{ PL_register_foreign("depth_of_var", 2, depth_of_var, 0);
}
--cut here -----------------------------------------------------------

```

Here is the code I used to test:

```prolog
:- load_foreign_library(depth_of_var).

q :-
	q(X),
	writeln(X).

q(X) :-
	depth_of_var(X, D),
	format('Depth = ~w~n', [D]),
	D < 5,
	q(X),
	notail.

notail.

```

Running this says:

```prolog
1 ?- q.
Depth = 1
Depth = 2
Depth = 3
Depth = 4
Depth = 5

No

```

You can adapt the code to throw an exception if the variable does not  
origine in a local frame. The above version fails silently. The print  
statements indicate what happens.

— Jan

---

<div class="post-metadata">

**Author:** ![logicmoo](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/logicmoo/32/193_2.png) [@logicmoo](https://swi-prolog.discourse.group/u/logicmoo)\
**Post date:** [October 14, 2020, 10:22pm UTC](https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030/6 "2020-10-14T22:22:56Z")

</div>

Yes you correctly identified!

[\*Post by \*\*_@users.sourceforge.net_](https://swi-prolog.iai.uni-bonn.narkive.com/GAgj4vwn/getting-how-many-prolog-frames-a-particular-variable-has-existed-in-thus-far#post5)

But yes, hopefully others will find uses for a depth\_of\_var/2 It seems it’s not overly specific  
to just my use, people could use it for just keeping track of depth of their program (for example PTTP could see performance gains. And not keep around global depth counters

Thank you again!

---

<div class="post-metadata">

**Author:** ![logicmoo](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/logicmoo/32/193_2.png) [@logicmoo](https://swi-prolog.discourse.group/u/logicmoo)\
**Post date:** [October 14, 2020, 10:32pm UTC](https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030/7 "2020-10-14T22:32:44Z")

</div>

I just wanted to point out that this was _way_ _way_ _way_ better than iterative deepening 18 years ago… But I still haven’t had time to write and publish a journal paper about my results ☹ ☹ ☹

Anyone else is free to do so… I rather have the idea/invention “out there” to be used by science 🙂 🙂 🙂

… than to hoard it all to myself. 🦀🦀🦀

**If you want to stay out of C code** another way to do this is to add an argument that is saved in a global variable that is a b\_setval() with a list of all the variables that are old (in the head) and newly made ones in the body expression _(The reason for the global\_variable_ `b_setval()` _is it doesn’t add an argument to every predicate)_ And lets you check if the variable(s) you are _about to submit_ to middle arguments predicates are already something elses _middle arguments_… Then you may scan the constructed value `b_getval` for the position of the variable to catch its frame depth. In fact you can keep these as `statistics` per-variable as attributes in an `attvar`. Though we can assume that tracking the variable’s `depth` will be much faster when done in C code.

---

<div class="post-metadata">

**Author:** ![zhCX](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/zhcx/32/151_2.png) [@zhCX](https://swi-prolog.discourse.group/u/zhCX)\
**Post date:** [October 16, 2020, 7:19pm UTC](https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030/8 "2020-10-16T19:19:19Z")

</div>

## question

```prolog
p(X):- q(X),!.
p(X):- g(X).

```

Is there a way I can retain my cut’s power in iterative deepening such that the choice `g/1` is only evaluated when `q/1` fails logically, not because of depth limit?

## answer

```prolog
p(X) :- q(X) .
p(X) :- \+ q(X) , g(X).

```

~~kintalken

---

<div class="post-metadata">

**Author:** ![aminemarref](https://avatars.discourse-cdn.com/v4/letter/a/7feea3/32.png) [@aminemarref](https://swi-prolog.discourse.group/u/aminemarref)\
**Post date:** [October 22, 2020, 9:37am UTC](https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030/9 "2020-10-22T09:37:57Z")

</div>

Thanks a lot for the detailed answers. I will have a go at this.

---

<div class="post-metadata">

**Author:** ![aminemarref](https://avatars.discourse-cdn.com/v4/letter/a/7feea3/32.png) [@aminemarref](https://swi-prolog.discourse.group/u/aminemarref)\
**Post date:** [October 22, 2020, 12:17pm UTC](https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030/10 "2020-10-22T12:17:42Z")

</div>

Thank you.

This does not solve the issue as `q(X)` could fail at a shallower depth making `\+q(X)` true and eventually `g(X)` evaluated (potentially to true).

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [October 22, 2020, 3:41pm UTC](https://swi-prolog.discourse.group/t/iterative-deepening-and-cuts/3030/11 "2020-10-22T15:41:16Z")

</div>

I had a little look at the ancient call\_with\_depth\_limit/3. First I thought it didn’t do iterative deepening but just cut the computation when reaching the depth limit. That doesn’t appear  
to be the case. Consider:

```prolog
a(0).
a(5) :-
    a(5).
a(I) :-
    I2 is I-1,
    a(I2).

```

Now we can make the goal below, while plain Prolog doesn’t terminate due to the loop at 5.

```prolog
?- call_with_depth_limit(a(10), 11, X).
X = 12 ;
X = depth_limit_exceeded.

```

I _think_ the rule is that if the reported depth is larger (1 larger) than the requested limit, you know you’ve hit the depth limit in some branch. So, you could do some program transformation, which essentially turns your code into

```prolog
p(X) :-
    call_with_depth_limit(q(X), Limit, Reached),
    ( integer(Reached),
        Reached > Limit)
   -> <The success is due to the depth limit>
   ...

```

This requires some program transformation: wrap the part before the ! into a call\_with\_depth\_limit/3 and some additional logic. I’m not sure whether there is something to see how far you are from the limit to initialise the Limit for the guard, but if that that will fix your problem, it should be easy enough to add a predicate that can tell you.

Related to this stuff might be [Tabling restraints: bounded rationality and tripwires](https://www.swi-prolog.org/pldoc/man?section=tabling-restraints)

That however does require tabling which is also problematic together with cuts ☹