Meta-interpreter for calculating max recursion depth

Question

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.

Answer 1

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