Implementing Prolog Meta-Interpreter Tracking Reduction

Question

I have this trace interpreter modified from a previous Prolog unbind bound variable question.

I do not understand how to interpret the cut. Thanks to the user @false, who told me that the cut is poorly implemented, my question is, how do I cut in this meta-interpreter?

%tracer mi_trace(Goal):- mi_trace(Goal, 0). mi_trace(V, _):- var(V), !, throw(error(instantiation_error, _)). mi_trace(true, _Depth):-!, true. mi_trace(fail, _Depth):-!, fail. mi_trace(A > B, _Depth):-!, A > B. mi_trace(A < B, _Depth):-!, A < B. mi_trace(A =< B, _Depth):-!, A =< B. mi_trace(A >= B, _Depth):-!, A >= B. mi_trace(A = B, _Depth):-!, A = B. mi_trace(A is B, _Depth):-!, A is B. mi_trace(\+A, _Depth):-!, \+mi_trace(A, _Depth). mi_trace(!, _Depth):-!, fail. % <- this is wrong mi_trace((Goal1, Goal2), Depth):- !, mi_trace(Goal1, Depth), mi_trace(Goal2, Depth). mi_trace(Goal, Depth):- display('Call: ', Goal, Depth), redo_clause(Depth, Goal, Body), Depth1 is Depth + 1, mi_trace(Body, Depth1), display('Exit: ', Goal, Depth). mi_trace(Goal, Depth):- display('Fail: ', Goal, Depth), fail. redo_clause(Depth, Goal, Body) :- findall(Goal-Body, clause(Goal, Body), [First|Rest]), ( Goal-Body = First ; length(Rest, RL), length(RestC, RL), member(Goal-Body,RestC), display('Redo: ', Goal, Depth), Rest = RestC ). display(Message, Goal, Depth):- tab(Depth), write(Depth), write(': '), write(Message), write(Goal), nl. trace_query(In, Out, Query):- consult(In), tell(Out), call_with_depth_limit(findall(Query, mi_trace(Query), _Solutions), 30, _XMessage), writeln(_XMessage), writeln(_Solutions), told, unload_file(In), true. 

Answer 1

Let me start with a simple implementation that works for many programs, but not for all.

Using catch/3 and throw/1

This method is by far the easiest way to implement abbreviation in ISO Prolog. However, this is not very effective. The basic idea is that the cut simply succeeds, and only upon retreat will it fail before the last call to mi_call/1 . Note that only mi_call/1 constructs can catch these abbreviations. As a result, all user targets must be wrapped using mi_call/1 . Similarly, for built-in functions like setof/3 .

Naive implementation:

 mi_cut. mi_cut :- throw(cut). mi_call(Goal) :- catch(Goal, cut, fail). 

In your meta-interpreter, replace the two rules with:

 mi_trace(!, _Depth):-!, ( true ; throw(cut) ). ... mi_trace(Goal, Depth):- display('Call: ', Goal, Depth), Depth1 is Depth + 1, catch( ( redo_clause(Depth, Goal, Body), mi_trace(Body, Depth1) ), cut, fail), display('Exit: ', Goal, Depth). 

This works for almost every program. Except those that throw(cut) themselves. Or want to catch all the exceptions. It is these tiny little things that complicate the overall implementation.

In your tracer at the moment you have not implemented call/1 , catch/3 , throw/1 , so these problems will not be displayed - you just get an error for them. (Maybe TBC)