在跟踪元解释器序言中实现 cut

问题描述

我有这个跟踪元解释器，从上一个问题 Prolog 解除绑定绑定变量改变.

I have this tracing meta interpreter, altered from previous question Prolog unbind bound variable.

我不明白如何解释cut.感谢用户@false 告诉我 cut 实现得很糟糕，我的问题是，我应该如何在这个元解释器中实现 cut?

I don't understand how to interpret cut. Thanks to user @false who told me that the cut is badly implemented, my question is, how should I implement 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.

推荐答案

让我从一个适用于许多程序但不是所有程序的简单实现开始.

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

这个方法绝对是在ISO Prolog中实现cut的最简单的方法.但是，它的效率不是很高.基本思想是 cut 简单地成功，只有在回溯时它才会失败，直到最后一次调用 mi_call/1.请注意，只有 mi_call/1 构造将能够捕捉到这些切割.因此，所有用户定义的目标都必须用 mi_call/1 包装.对于像 setof/3 这样的内置函数也是如此.

This method is definitely the simplest way to implement the cut in ISO Prolog. However, it is not very efficient. The basic idea is that cut simply succeeds, and only on backtracking it will fail up to the last invocation of mi_call/1. Note that only mi_call/1 constructs will be able to catch those cuts. As a consequence, all user defined goals have to be wrapped with mi_call/1. Same accordingly for built-ins like setof/3.

一个简单的实现是:

mi_cut.
mi_cut :- throw(cut).

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

在您的元解释器中，将两条规则交换为:

In your meta-interpreter, exchange two rules to:

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

这几乎适用于所有程序.除了那些，那些 throw(cut) 自己.或者想捕获所有异常.正是这些微小的事情使一般实现变得更加复杂.

This works for almost every program. Except those, that throw(cut) themselves. Or want to catch all exceptions. It is these tiny little things that makes a general implementation much more complex.

在你的追踪器中，你暂时没有实现call/1、catch/3、throw/1，所以这些问题不会显示 - 您只会收到这些错误.(也许待定)

In your tracer, you have not implemented call/1, catch/3, throw/1 for the moment, so these problems will not show - you simply get an error for those.(Maybe TBC)

这篇关于在跟踪元解释器序言中实现 cut的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！