Prolog解析故障

Question

我的代码采用类似的表达式or(lit(true),lit(X)),X)并将其作为列表列表输出.

 tocnf(Tree, Expr) :-
    trans(Tree ,Expr, []).

 trans(lit(X)) -->bbool(X).
 trans(or(lit(X1),lit(X2))) --> bconj(X1), bdisj(X2).
 trans(and(lit(X1),lit(X2))) --> bbool(X1), bconj(X2).

 bdisj(Conj) --> bconj(Conj).

 bconj(Bool) --> bbool(Bool).

 bbool(X) --> [[X]].

这段代码应该采用类似的方式

tocnf(lit(X),X) 

输出为

[[X]]

要么

 tocnf(or(lit(true),lit(X)),X)  

并输出为

[[true],[X]].

问题是为什么当我这样做

  tocnf(or(lit(true), and(lit(X),lit(true))),X) 

它输出

 false.

Answer 1

预赛

首先,关于样式的注释:您应该始终使用该phrase/2界面来访问DCG,因此请写tocnf/2为:

tocnf(Tree, Expr) :-
        phrase(trans(Tree), Expr).

此外,tocnf/2是一个相当命令的名称,因为它暗示了使用方向("到"CNF).然而,该关系在其他方向上也是有意义的,例如以产生答案.因此,试着找到一个更好的名字,这对Prolog的这种一般性质是正义的.我将此作为练习.

声明性调试

现在,谈谈你的实际问题.应用声明性调试以查找失败的原因.

我们从您发布的查询开始:

?- tocnf(or(lit(true), and(lit(X),lit(true))), X).
false.

这意味着该程序出乎意料地过于具体:在我们期望成功的情况下失败.

现在,我们概括了查询,以找到仍然失败的更简单的情况.这是完全可以接受的,因为您的程序是使用Prolog 的单调子集编写的,因为强烈建议使用声明性调试.

为了概括查询,我使用变量而不是一些子项.例如:

?- tocnf(or(lit(_), and(lit(X),lit(true))), X).
false.

啊哈!这仍然失败,因此每个更具体的查询也将失败.

所以,我们这样做,使用变量而不是一些子项:

?- tocnf(or(lit(_), and(lit(X),lit(_))), X).
false.

?- tocnf(or(_, and(lit(X),lit(_))), X).
false.

?- tocnf(or(_, and(_,lit(_))), X).
false.

?- tocnf(or(_, and(_,_)), X).
false.

所有这些查询也都失败了.

现在,我们更进一步:

?- tocnf(or(_, _), X).
X = [[_G793], [_G795]].

啊哈!所以我们发现了一个成功的案例,一个稍微更具体的案例虽然仍然非常简单,但失败了:

?- tocnf(or(_, and(_,_)), X).
false.

这是我开始的情况:想想为什么你的关系不适用于表单的条款or(_, and(_,_)).

自动化解决方案

纯粹单调Prolog的一个主要吸引力是上面的推理可以自动化:

该机器应该找到失败的原因,让我们可以专注于更重要的任务.

Ulrich Neumerkel慷慨地提供了一种方法.

要试用它,您需要安装:

1. library(diadem) 和
2. library(lambda).

现在,概括一下:我们发现了一个意外失败的查询.它是:

?- tocnf(or(lit(true), and(lit(X),lit(true))), X).
false.

要找到原因,我们首先加载library(diadem):

?- use_module(library(diadem)).
true.

然后,我们稍微改变一下该查询的重新发布:

?- tocnf(or(lit(true), and(lit(X),lit(true))), X).?Generalization.

也就是说,我只是附加?Generalization.到上一个查询.

作为回应,我们得到:

Generalization = tocnf(or(_, and(_, _)), _) .

因此,Generalization是一种更普遍的目标是仍然失败.由于我们正在考虑的Prolog程序是完全纯粹和单调的,我们知道每个更具体的查询也将失败.因此,我建议您关注这个更简单,更一般的情况,在这种情况下会自动找到,并且是我们在几个步骤后手动找到的相同目标.

在学习Prolog时,意外故障是一个常见问题,自动声明性调试可让您快速找到原因.