Iterative Deepening and Cuts

Help!
1

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.

2

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

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

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 like you mentioned, that might work :slight_smile:

Cheers,
A.

4

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

1 Like
5

Jan Wielemaker 18 years ago

Permalink

Douglas,

*Post by **@users.sourceforge.net 

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

converts into:

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.

---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:

:- 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:

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

1 Like
6

Yes you correctly identified!

*Post by **@users.sourceforge.net

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!

7

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 :frowning: :frowning: :frowning:

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

… than to hoard it all to myself. :crab::crab::crab:

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.

1 Like
8

question

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

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

~~kintalken

9

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

10

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

11

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:

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.

?- 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

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

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

1 Like