2

I'm trying to write a meta-interpreter in prolog for prolog, which would return maximal reached recursion depth in a given prolog program.

This code actually counts number of all recursive calls in a program:

rc( true, 0) :- !.
rc( ( Goal1, Goal2), N) :- !, %we have multiple goals
  rc( Goal1, N1), %count recursive calls in Goal1
  rc( Goal2, N2), %count recursive calls in goals Goal2
  N is N1 + N2. %add both counters

rc( Goal, N) :-
  clause( Goal, Body),
  functor( Goal, F, A), %get functor and airity
  rcount( F/A, Body, NF), %count calls of that functor/airity in the body
  rc( Body, NB), %recursively process the body
  N is NF + NB. %add counters

I must somehow keep track of each individual recursion path and compare their depths, but have problems defining this in prolog. Can somebody point me into the right direction?

Thanks.

false
  • 10,264
  • 13
  • 101
  • 209
Uros K
  • 3,274
  • 4
  • 31
  • 45

1 Answers1

3

You can try something along these lines:

solve(true, 0) :- !.
solve(Head, Hdepth) :- clause(Head, Body), solve(Body, Bdepth),
    Hdepth is Bdepth + 1.
solve((Goal1, Goal2), Depth) :- solve(Goal1, Depth1), solve(Goal2, Depth2),
    Depth is max(Depth1, Depth2).
Jiri Kriz
  • 9,192
  • 3
  • 29
  • 36
  • I think you are missing cut (!) in first solve: solve(true, 0) :- !. Tnx for the solution. It's actually easier than I thought :) – Uros K Jul 07 '11 at 13:00
  • 1
    `solve(true, 0)` is a simple true fact. No cut is needed. This is pure Prolog! – Jiri Kriz Jul 07 '11 at 13:14
  • But, when backtracking, it will try to match Head with true and Hdepth with 0 and succeed (second solve/2). Which is wrong, you want it to stop when it reaches solve(true, 0). – Uros K Jul 07 '11 at 13:59
  • What? Why should it match Hdepth with 0? Hdepth will typically be a free variable when solve/2 is called and is still to be computed. – mat Jul 07 '11 at 14:47
  • 2
    I would prefer not to have the cut. However, SWI Prolog gives on backtracking "ERROR: clause/2: No permission to access private_procedure `true/0'". This can be avoided with the cut. The logical justification would be that there is surely only one solution. – Jiri Kriz Jul 07 '11 at 15:05
  • 1
    OK, avoiding this error is a different and valid reason. You can still avoid the cut by using for example catch/3 or other built-in predicates to see whether clause/2 can safely be used in the second clause. Regarding the "only one solution": A good declarative solution would be, instead of using the built-in clause/2, to represent programs that are to be interpreted in a way that is not defaulty, for example like my_clause(Head, [G1,G2,...,G_n]) ("true" then corresponds to the empty list). Then the meta-interpreter can be written nicely without cuts, and could easily interpret itself as well. – mat Jul 08 '11 at 07:53