读一截!在序言中
Reading a cut ! in Prolog
我正在阅读 Learn Prolog Now! 's chapter on cuts,同时阅读 Bratko 的 Prolog Programming for Artificial Intelligence,第 5 章:控制回溯。起初,似乎 cut 是模仿其他编程语言已知的 if-else 子句的直接方式,例如
# Find the largest number
max(X,Y,Y):- X =< Y,!.
max(X,Y,X).
但是,正如下面所指出的那样,即使在我们期望 false
时所有变量都被实例化的情况下,此代码也会失败,例如
?- max(2,3,2).
true.
原因很明确:第一条规则失败,第二条规则不再有任何相关条件,所以它会成功。我明白了,但后来提出了一个解决方案(这里是swish):
max(X,Y,Z):- X =< Y,!, Y = Z.
max(X,Y,X).
我很困惑该如何阅读这篇文章。我认为 !
的意思是:'if everything that comes before this !
is true, stop termination including any other rules with the same predicate'。但是,这不对,因为这意味着 Y = Z
的实例化仅在失败的情况下发生,这对于该规则是无用的。
那么剪辑应该如何用'human'的方式来解读呢?而且,作为扩展,我应该如何阅读上面 max/3
的建议解决方案?
另见 this answer and this question。
how should I read the proposed solution for max/3 above?
max(X,Y,Z):- X =< Y, !, Y = Z.
max(X,Y,X).
您可以这样阅读:
When X =< Y
, forget the second clause of the predicate, and unify Y
and Z
.
剪辑会丢掉选择点。选择点是证明树中的标记,它告诉 Prolog 在找到解决方案后从哪里继续搜索更多解决方案。所以 cut 切掉了证明树的一部分。上面的第一个 link (here it is again) 详细讨论了削减,但该答案的很大一部分只是引用其他人在其他地方所说的关于削减的内容。
我想带回家的信息是,一旦你在 Prolog 程序中进行了剪辑,你就会强迫自己以操作方式而不是声明方式阅读它。为了理解证明树的哪些部分将被切掉,你(程序员)必须走过场,考虑子句的顺序,考虑哪些子目标可以创建选择点,考虑丢失哪些解决方案。您需要构建证明树(而不是让 Prolog 来做)。
您可以使用许多 技巧来避免创建您知道不需要的选择点。然而,这是一个有点大的话题。您应该阅读可用的 material 并提出具体问题。
您的代码的问题是在评估您的查询时从未达到切割。
尝试使用规则评估目标的第一步是模式匹配。
目标 max(2,3,2)
与模式 max(X,Y,Y)
不匹配,因为模式中的第二个和第三个参数相同,而 3 和 2 彼此不匹配。因此,这条规则在模式匹配阶段已经失败,因此评估者没有达到测试 X =< Y
,更不用说达到 !
.
但是你对裁剪的理解是非常正确的。鉴于此代码
a(X) :- b(X).
a(X) :- c(X).
b(X) :- d(X), !.
b(X) :- e(X).
c(3).
d(4).
d(5).
e(6).
和目标
?- a(X).
解释器将从第一条规则开始,尝试满足 b(X)
。在这个过程中,它发现d(4)
提供了一个解决方案,所以将值4
绑定到X
。然后切割开始,它丢弃了 b(X)
上的回溯,因此没有找到 b(X)
的进一步解决方案。但是,它不会删除 a(X)
上的回溯,因此如果您要求 Prolog 找到另一个解决方案,那么它将通过 a(X) :- c(X).
规则找到 X = 3
。如果您将第一条规则更改为 a(X) :- b(X), !.
那么它将找不到 X = 3
.
虽然剪切意味着找不到 X = 5
解决方案,但如果您的查询是
?- a(5).
然后解释器将 return 为真。这是因为 a(5)
调用 b(5)
,后者调用 d(5)
,它被定义为 true。 d(4)
事实无法进行模式匹配,因此它不会像查询 a(X)
.
时那样触发剪切
这是一个红色切割的例子(见我对 user1812457 的回答的评论)。除了破坏逻辑纯度之外,避免红色切割的一个很好的理由可能是避免由此行为导致的错误。
我正在阅读 Learn Prolog Now! 's chapter on cuts,同时阅读 Bratko 的 Prolog Programming for Artificial Intelligence,第 5 章:控制回溯。起初,似乎 cut 是模仿其他编程语言已知的 if-else 子句的直接方式,例如
# Find the largest number
max(X,Y,Y):- X =< Y,!.
max(X,Y,X).
但是,正如下面所指出的那样,即使在我们期望 false
时所有变量都被实例化的情况下,此代码也会失败,例如
?- max(2,3,2).
true.
原因很明确:第一条规则失败,第二条规则不再有任何相关条件,所以它会成功。我明白了,但后来提出了一个解决方案(这里是swish):
max(X,Y,Z):- X =< Y,!, Y = Z.
max(X,Y,X).
我很困惑该如何阅读这篇文章。我认为 !
的意思是:'if everything that comes before this !
is true, stop termination including any other rules with the same predicate'。但是,这不对,因为这意味着 Y = Z
的实例化仅在失败的情况下发生,这对于该规则是无用的。
那么剪辑应该如何用'human'的方式来解读呢?而且,作为扩展,我应该如何阅读上面 max/3
的建议解决方案?
另见 this answer and this question。
how should I read the proposed solution for max/3 above?
max(X,Y,Z):- X =< Y, !, Y = Z.
max(X,Y,X).
您可以这样阅读:
When
X =< Y
, forget the second clause of the predicate, and unifyY
andZ
.
剪辑会丢掉选择点。选择点是证明树中的标记,它告诉 Prolog 在找到解决方案后从哪里继续搜索更多解决方案。所以 cut 切掉了证明树的一部分。上面的第一个 link (here it is again) 详细讨论了削减,但该答案的很大一部分只是引用其他人在其他地方所说的关于削减的内容。
我想带回家的信息是,一旦你在 Prolog 程序中进行了剪辑,你就会强迫自己以操作方式而不是声明方式阅读它。为了理解证明树的哪些部分将被切掉,你(程序员)必须走过场,考虑子句的顺序,考虑哪些子目标可以创建选择点,考虑丢失哪些解决方案。您需要构建证明树(而不是让 Prolog 来做)。
您可以使用许多 技巧来避免创建您知道不需要的选择点。然而,这是一个有点大的话题。您应该阅读可用的 material 并提出具体问题。
您的代码的问题是在评估您的查询时从未达到切割。
尝试使用规则评估目标的第一步是模式匹配。
目标 max(2,3,2)
与模式 max(X,Y,Y)
不匹配,因为模式中的第二个和第三个参数相同,而 3 和 2 彼此不匹配。因此,这条规则在模式匹配阶段已经失败,因此评估者没有达到测试 X =< Y
,更不用说达到 !
.
但是你对裁剪的理解是非常正确的。鉴于此代码
a(X) :- b(X).
a(X) :- c(X).
b(X) :- d(X), !.
b(X) :- e(X).
c(3).
d(4).
d(5).
e(6).
和目标
?- a(X).
解释器将从第一条规则开始,尝试满足 b(X)
。在这个过程中,它发现d(4)
提供了一个解决方案,所以将值4
绑定到X
。然后切割开始,它丢弃了 b(X)
上的回溯,因此没有找到 b(X)
的进一步解决方案。但是,它不会删除 a(X)
上的回溯,因此如果您要求 Prolog 找到另一个解决方案,那么它将通过 a(X) :- c(X).
规则找到 X = 3
。如果您将第一条规则更改为 a(X) :- b(X), !.
那么它将找不到 X = 3
.
虽然剪切意味着找不到 X = 5
解决方案,但如果您的查询是
?- a(5).
然后解释器将 return 为真。这是因为 a(5)
调用 b(5)
,后者调用 d(5)
,它被定义为 true。 d(4)
事实无法进行模式匹配,因此它不会像查询 a(X)
.
这是一个红色切割的例子(见我对 user1812457 的回答的评论)。除了破坏逻辑纯度之外,避免红色切割的一个很好的理由可能是避免由此行为导致的错误。