Declarative predicates by limiting resources

Help!
21

As yet, no. There is nothing special to recursive calls, which makes this a little hard. And then we have mutual recursive calls, etc. I doubt this is a fruitful direction :frowning:

term_expansion can do all this stuf, but the expansion gets rather nasty as well as you have to analyse the bodies for recursive calls. I think the meta-predicate approach is more practical …

22

I think I found a solution, it’s a little hacky (:sweat_smile:) but the proof of concept works:

wrap_test(Pred/Arity,Depth) :-
   atom(Pred), integer(Arity), Arity>=0,
   functor(Head,Pred,Arity),
   set_flag(outside_recursion,0),  % should be named inside_recursion
   wrap_predicate(Head, ideepen, OrigPred,
      (
	 format('inside wrapper~n'),
	 (  get_flag(outside_recursion,IR),
	    IR == 0
	 -> set_flag(outside_recursion,1),
	    format('limit   call',[]), call_with_depth_limit(OrigPred, Depth, RD),
	    (  RD == depth_limit_exceeded
	    -> set_flag(outside_recursion,0)
	    ;  true
	    )
	 ;  format('regular call',[]), call(OrigPred)
	 )
      )
   ).


leaf(l(_)).

btree(bt(A,B)) :-
   (  leaf(A); btree(A) ),
   (  leaf(B); btree(B) ).

Query

5 ?- call_with_depth_limit(btree(T),3,_).
T = bt(l(_8988), l(_8992)) ;
T = bt(l(_8988), bt(l(_8998), l(_9002))) ;
T = bt(bt(l(_8994), l(_8998)), l(_9002)) ;
T = bt(bt(l(_8994), l(_8998)), bt(l(_9008), l(_9012))) ;
true.

6 ?- wrap_test(btree/1,7).
true.

7 ?- btree(T).
inside wrapper
limit   call
T = bt(l(_8592), l(_8596)) ;
inside wrapper
regular call
T = bt(l(_8592), bt(l(_8616), l(_8620))) ;
inside wrapper
regular call
T = bt(bt(l(_8612), l(_8616)), l(_8620)) ;
inside wrapper
regular call
T = bt(bt(l(_8612), l(_8616)), bt(l(_8640), l(_8644))) ;
true.

8 ?-

So it works fine, but with a strange change:
The depth of 3 in the top level corresponds to the depth of 7 inside the wrapper. I think it is because of the strange way in which call_with_depth_limit/3 counts the recursions. It took me ages to figure this one out.

Of course in the real implementation I will change the flag name to a generated ID based on the head.

Do you see any problem with this approach?
(I used flags because they are atomic, and probably faster than anything else).

EDIT: the name of the flag is wrong, it comes from a previous iteration. Should be called inside_recursion but it doesn’t matter, because it needs to be generated anyway.

23

Flags are shared between threads. That is not what you want. Another problem with global state are possible exceptions that leave the value. Using setup_call_cleanup/3 can often solve that.

You can also use prolog_current_frame/1 and prolog_frame_attribute/3 to detect the recursion. With a lot of intermediate frames that will be slower, but with not too many it is probably faster and doesn’t suffer from all the issues related with global state.

24

Thanks! I’ll try that. I really didn’t like the global state.

25

Much cleaner now! :

wrap_test(Pred/Arity,Depth) :-
   atom(Pred), integer(Arity), Arity>=0,
   functor(Head,Pred,Arity),
   wrap_predicate(Head, ideepen, OrigPred,
      (
	 prolog_current_frame(F),
	 prolog_frame_attribute(F,parent,P),
	 copy_term(Head,Head1),
	 (  prolog_frame_attribute(P,parent_goal,Head1)
	 -> writeln('regular call'), call(OrigPred)
	 ;  writeln('limit call'),   call_with_depth_limit(OrigPred, Depth, _)
	 )
      )
   ).

leaf(l(_)).

btree(bt(A,B)) :-
   (  leaf(A); btree(A) ),
   (  leaf(B); btree(B) ).

Query

40 ?- wrap_test(btree/1,6).
true.

41 ?- btree(T).
limit call
T = bt(l(_3826), l(_3830)) ;
regular call
T = bt(l(_3826), bt(l(_3854), l(_3858))) ;
regular call
T = bt(bt(l(_3850), l(_3854)), l(_3858)) ;
regular call
T = bt(bt(l(_3850), l(_3854)), bt(l(_3882), l(_3886))) ;
true.

Turns out level 6 in the wrapper, now corresponds to level 3 in the top level. Had to use copy_term/2 to get a fresh Head.

I like this solution much better. I don’t really care about recursion levels, but only about using call_with_depth_limit/3 once on first entry.

What do you think? Any problems with it?

26

This assumes the current call can unify with a parent. That may not be the case. You should use functor/3 twice to create a most general term. Watch out for the possible module qualification!

Otherwise, yes this is what I proposed.

27

Good, it is working great. Should I use something like:

 setup_call_cleanup(
        '$set_source_module'(OldModule, M),
        % [...code here...]
        '$set_source_module'(OldModule)
 )
``

to take care of the module?
28

No. That is for some low-level hacks with source manipulation.

29

OK, I’ll use meta_predicate/...