0

我正在 Prolog 中重写以下函数：

V1：

f(X,Y):- X < 2, Y is X+1.
f(X,3):- 2 =< X, X < 5.
f(X,Y):- 5 =< X, Y is 8-X.

作为 V2：

f(X,Y) :-
    X < 2,
    Y is X + 1. 
f(X,Y) :-
    X >= 2,
    X < 5,
    Y is 3.
f(X,Y) :-
    X >= 5,
    Y is 8-X.

然后我想尝试削减。对于绿色切割 (V3)：

f(X,Y) :-
    X < 2, !,
    Y is X + 1.
f(X,Y) :-
    X >= 2,
    X < 5, !,
    Y is 3.
f(X,Y) :-
    X >= 5,
    Y is 8-X.

对于红色切割 (V4)：

f(X,Y) :-
    X < 2, !,
    Y is X + 1.
f(X,Y) :-
    X < 5, !,
    Y is 3.
f(X,Y) :-
    Y is 8-X.

但是，我不明白他们的优势，因为删除剪辑将允许代码的相同行为......有什么帮助吗？

4

2 回答 2

1

您的所有版本 V1..V4 在观察上都是等效的，因此您的推理是正确的。不过，还是有区别的。

避免多余的选择点

在许多实现中，V1 和 V2 的效率可能特别低，因为在内部，它们“留下了一个选择点”。之所以如此，是因为此类 Prolog 不会进一步考虑其他规则。所以每个目标都会f(1,X)消耗一些内存，只能在回溯（或使用！）时释放。这是一个自己尝试的简单方法：

loop(Goal) :-
   Goal,
   loop(Goal).

这是我在 SWI 中得到的：

?- time(loop(f1(1,2))).
% 5,991,554 inferences, 81.282 CPU in 81.443 seconds (100% CPU, 73713 Lips)
ERROR: Out of local stack
?- time(loop(f2(1,2))).
% 5,991,553 inferences, 85.032 CPU in 85.212 seconds (100% CPU, 70462 Lips)
ERROR: Out of local stack

而 V3 和 V4 似乎可以无限期地运行——至少比 85s 长得多。像这样的实验对于非常小的程序来说很有趣，但对于更大的程序来说不是很实用。幸运的是，在许多 Prolog 中，有一种简单的方法可以判断查询是否被确定地执行。要查看您的系统是否执行此操作，请输入：

?- X = 1.
X = 1.

对于您的变化：

?- f1(1,2).
true ;        % <== Prolog asked for another answer
false.        % <== only to conclude that there is none.

?- f2(1,2).
true ;        % same again
false.

?- f3(1,2).
true.         % <== Prolog knows there will be no further answer

?- f4(1,2).
true.

避免重新计算 - 使削减变为红色

V3 避免了多余的选择点，而 V4 现在甚至避免了多余的计算。所以它应该是最有效的。但这是以固定条款的顺序为代价的。

然而，V3 是唯一可能的，因为绿色削减的两个必要条件同时发生：

  1. 非重叠条件。这对你来说应该很明显。

  2. 实例化的安全测试。这远非显而易见。请注意，目标X < 2附带了正确实例化的隐式测试！它产生一个实例化错误应该X是一个未实例化的变量。正是因为这个测试，V3 中的剪辑恰好是绿色剪辑。没有那个测试，这将是一个红色的削减。

另请注意，如果第二条规则单独存在，则 V1 和 V2 将不等价！因为目标f(X,5).会在 V1 中失败，但会在 V2 中产生错误。

于 2014-06-02T00:07:59.373 回答
0

正如您所指出的，第一个版本显示绿色切割和第二个红色切割。您不必感觉到这两个版本之间的区别。

a) 一个原因可能是效率，但对于具有快速机器的玩具代码，您几乎不会注意到它。

b) 在绿色切割的情况下，改组规则不应该改变代码的行为，这对于第一个代码是正确的。但是在第二个代码中，如果将第二个子句放在第一个子句之前，则行为会发生变化： f(0,3) 为真，但最初为假。因此，如果您改组规则，您会感到不同。

改组的优点是您不关心顺序而是内容 - 这是声明式编程的要点之一。

于 2014-06-01T23:47:44.097 回答