8

我有这个跟踪元解释器，从上一个问题Prolog unbind bound variable改变。

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

%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.
4

1 回答 1

8

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

使用catch/3和throw/1

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

一个天真的实现是：

mi_cut.
mi_cut :- throw(cut).

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

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

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)他们自己。或者想捕获所有异常。正是这些微小的东西使一般实现变得更加复杂。

在您的跟踪器中，您暂时还没有实现call/1, catch/3，throw/1因此这些问题不会显示 - 您只会得到一个错误。（也许待定）

于 2014-12-02T17:31:09.763 回答