控制 Prolog 变量值选择
Controlling Prolog variable value selection
受到 an earlier question 的启发，我尝试实现一些可以枚举布尔表达式可能性的东西。但是，我在变量选择方面遇到了麻烦。这是我的预期结果：
?- eval(X^Y, R).
R = 0^0;
R = 0^1;
R = 1^0;
R = 1^1;
no.
这是我的代码：
:- op(200, yfx, ^).
split(V, R) :- var(V), R = 0.
split(V, R) :- var(V), R = 1.
split(X ^ Y, XP ^ YP) :- split(X, XP), split(Y, YP).
即使对于这个简单的案例，这也没有达到我想要的效果：
?- split(Y, R).
R = 0 ;
R = 1 ;
Y = _G269^_G270,
R = 0^0 ;
Y = _G269^_G270,
R = 0^1 ;
Y = _G269^ (_G275^_G276),
R = 0^ (0^0) ;
Y = _G269^ (_G275^_G276),
R = 0^ (0^1) ;
Y = _G269^ (_G275^ (_G281^_G282)),
R = 0^ (0^ (0^0)) .
所以，我可以看出这里的问题是什么，在通过 split(Y, YP) 的过程中，Prolog 已经用完了前两个子句，所以它再次出现在 split(X^Y, ...) 中，统一了我的Y 与 X'^Y'，本质上。我只是不确定我需要做什么来关闭这条路径，除了一开始我有结构 ^/2.
我也希望它能处理嵌套结构，所以我不能只消除分支的递归处理。
编辑: 没有运算符
如果 op/3 困扰您，请考虑以下公式：
eval(and(X,Y), R).
R = and(0,0);
R = and(0,1);
R = and(1,0);
R = and(1,1);
no.
这就是这种情况下的代码：
split(V, R) :- var(V), R = 0.
split(V, R) :- var(V), R = 1.
split(and(X,Y), and(XP,YP)) :- split(X, XP), split(Y, YP).
请记住，我仍然希望它能与 and(and(X,Y),and(Y,Z)) 等递归公式一起使用
主要问题：默认表示
本例中的核心问题是您用来表示布尔表达式的默认表示。
"defaulty" 我的意思是您无法通过 模式匹配 清楚地区分这些情况：在您的情况下，变量 V 可能表示 任一个
- 其中一个命题常数
0 和 1、 或
A^B.
由于这个缺点，您无法在程序中清楚地表达形式为 "the variable X stands only for one of the two propositional constants" 的约束。
出路：干净的表现
声明式的解决方法是使用干净的表示 代替。
例如，假设我们任意使用v/1来区分只表示命题常数的变量，那么我们有：
v(X)表示命题变量XA^B 表示 复合表达式 .
显然，由于主函子和元数不同（v/1 vs. (^)/2），我们可以仅通过模式匹配来区分情况。
有了这个 new 表示，您的代码段将变为：
split(v(V), V) :- V = 0.
split(v(V), V) :- V = 1.
split(X^Y, XP ^ YP) :-
split(X, XP),
split(Y, YP).
示例查询：
?- split(v(X)^v(Y), R).
X = Y, Y = 0,
R = 0^0 ;
X = 0,
Y = 1,
R = 0^1 ;
X = 1,
Y = 0,
R = 1^0 ;
X = Y, Y = 1,
R = 1^1.
请注意，此仍然在所有方向上都有效，在最一般的情况下也是如此:
?- split(Expr, R).
Expr = v(0),
R = 0 ;
Expr = v(1),
R = 1 ;
Expr = v(0)^v(0),
R = 0^0 ;
Expr = v(0)^v(1),
R = 0^1 ;
etc.
根据经验，一旦您必须在代码中使用像 var/1 这样的 extra-logical 谓词，保持其逻辑纯洁性和单调性的希望就很小了。以干净的表示为目标以保留这些属性。
有时，使用默认表示是不可避免的，例如，因为您想让用户更轻松地输入。在这种情况下，目标是在开始实际推理之前快速将它们转换为干净的。
在某个时候，我写了一个非常小的程序，它似乎或多或少是您要找的东西。我真的希望我没有完全误读你的问题。您可以检查整个程序的 this SWISH program。有一些差异，比如使用 f 和 t 而不是 0 和 1，或者使用 and 和 or 而不是 ^ 和 v.不过基本思路和你一样（我觉得）
如果我删除一些不必要的东西来演示，那么程序就是这样：
:- op(100, fy, ?).
:- op(500, yfx, and).
:- op(500, yfx, or).
table(F, T) :-
term_variables(F, Vs),
bagof(R-Vs, bl(F, R), T).
bl(?X, R) :-
v(X, R).
bl(X and Y, R) :-
bl(X, R0),
and_bl(R0, Y, R).
bl(X or Y, R) :-
bl(X, R0),
or_bl(R0, Y, R).
v(f, f).
v(t, t).
and_bl(f, _, f).
and_bl(t, Y, R) :- bl(Y, R).
or_bl(f, Y, R) :- bl(Y, R).
or_bl(t, _, t).
这里的要点是我有一个纯粹的关系，我的 v/2，它简单地说明 true 的值是 true 而 [=21= 的值] 是 false。然后，我使用相互递归定义来实际评估布尔表达式，最终在 v/2.
处触底
我决定自己 "tag" 布尔变量，所以你必须写 ?X 而不是 X。如果我没记错的话，当时我意识到我需要一种方法来明确说明表达式中是否有布尔变量，或者整个表达式是否仍然是 "unknown"。换句话说，这个：?X 是 t 或 f 并且这个：Expr 可以是 ?X，或 not ?X，或 ?X and ?Y，或?X or ?Y，或not (?X and ?Y)，依此类推。
用 ?X 标记变量可以避免 "defaulty representation" 是 。重要的是，如果没有显式标记，我看不到区分布尔变量和布尔表达式的方法。
以下是使用方法：
?- bl(?t and ?X, R).
X = R, R = f ;
X = R, R = t.
?- bl(?t or ?X, R).
R = t.
?- bl(?A or (?B and ?C), R).
A = B, B = R, R = f ;
A = C, C = R, R = f,
B = t ;
A = f,
B = C, C = R, R = t ;
A = R, R = t.
?- table(?A or (?B and ?A), R).
R = [f-[f, f], f-[f, t], t-[t, _7734]].
已经有两个很好的答案，一个是纯粹的答案，另一个是使用 term_variables/2 的较短的答案。我还想说一个细节：
So, I can see what the problem is here, which is that on the way through split(Y, YP) Prolog has exhausted the first two clauses, so it winds up in split(X^Y, ...) again, unifying my Y with X'^Y', essentially. I am just not sure what I need to do to close off that path except at the outset where I have the structure ^/2.
如果您不想在第一个参数是变量的情况下与 X^Y 执行 head 统一，请将统一从 head 中拉出。没有什么可以强迫您将术语 X^Y 放在那里！如果前两个条款不适用，你要做的是只考虑你的最后一个条款。前两个子句被var/1保护，所以你可以用nonvar/1保护最后一个：
split(V, R) :- var(V), R = 0.
split(V, R) :- var(V), R = 1.
split(Term, SplitTerm) :-
nonvar(Term),
Term = X ^ Y,
split(X, XP),
split(Y, YP),
SplitTerm = XP ^ YP.
这样您的示例就可以正常工作了：
?- split(Y, R).
R = 0 ;
R = 1 ;
false.
?- split(X^Y, R).
R = 0^0 ;
R = 0^1 ;
R = 1^0 ;
R = 1^1 ;
false.
编辑： 正如 mat 在评论中指出的那样，使用像 var/1 这样的测试会给你带来各种麻烦。
一个问题是您必须仔细检查不同级别的实例化：mat 的 split(1, R) 示例查询因上述代码而失败（它应该因 R = 1 而成功）。这是因为 1 属于 nonvar 的情况，但不与 _^_ 统一。如果我们这样做，我们不仅要区分 var 和 nonvar 情况，还要区分 var、ground 和 nonvar-but-not-ground。这有点乱。
另一个问题是查询 split(V, R), V = 1，它在声明上等同于上面的查询，但成功了两次，包括解决方案 R = V。这是因为 split/2 的这个定义（故意）避免在其参数之间引入共享。我们是否需要共享取决于规范。
我不会尝试通过实例化测试给出一个完全可靠的解决方案，因为我的意思并不是说这是最好的方法。
受到 an earlier question 的启发，我尝试实现一些可以枚举布尔表达式可能性的东西。但是，我在变量选择方面遇到了麻烦。这是我的预期结果：
?- eval(X^Y, R).
R = 0^0;
R = 0^1;
R = 1^0;
R = 1^1;
no.
这是我的代码：
:- op(200, yfx, ^).
split(V, R) :- var(V), R = 0.
split(V, R) :- var(V), R = 1.
split(X ^ Y, XP ^ YP) :- split(X, XP), split(Y, YP).
即使对于这个简单的案例，这也没有达到我想要的效果：
?- split(Y, R).
R = 0 ;
R = 1 ;
Y = _G269^_G270,
R = 0^0 ;
Y = _G269^_G270,
R = 0^1 ;
Y = _G269^ (_G275^_G276),
R = 0^ (0^0) ;
Y = _G269^ (_G275^_G276),
R = 0^ (0^1) ;
Y = _G269^ (_G275^ (_G281^_G282)),
R = 0^ (0^ (0^0)) .
所以，我可以看出这里的问题是什么，在通过 split(Y, YP) 的过程中，Prolog 已经用完了前两个子句，所以它再次出现在 split(X^Y, ...) 中，统一了我的Y 与 X'^Y'，本质上。我只是不确定我需要做什么来关闭这条路径，除了一开始我有结构 ^/2.
我也希望它能处理嵌套结构，所以我不能只消除分支的递归处理。
编辑: 没有运算符
如果 op/3 困扰您，请考虑以下公式：
eval(and(X,Y), R).
R = and(0,0);
R = and(0,1);
R = and(1,0);
R = and(1,1);
no.
这就是这种情况下的代码：
split(V, R) :- var(V), R = 0.
split(V, R) :- var(V), R = 1.
split(and(X,Y), and(XP,YP)) :- split(X, XP), split(Y, YP).
请记住，我仍然希望它能与 and(and(X,Y),and(Y,Z)) 等递归公式一起使用
主要问题：默认表示
本例中的核心问题是您用来表示布尔表达式的默认表示。
"defaulty" 我的意思是您无法通过 模式匹配 清楚地区分这些情况：在您的情况下，变量 V 可能表示 任一个
- 其中一个命题常数
0和1、 或 A^B. 形式的复合表达式
由于这个缺点，您无法在程序中清楚地表达形式为 "the variable X stands only for one of the two propositional constants" 的约束。
出路：干净的表现
声明式的解决方法是使用干净的表示 代替。
例如，假设我们任意使用v/1来区分只表示命题常数的变量，那么我们有：
v(X)表示命题变量XA^B表示 复合表达式 .
显然，由于主函子和元数不同（v/1 vs. (^)/2），我们可以仅通过模式匹配来区分情况。
有了这个 new 表示，您的代码段将变为：
split(v(V), V) :- V = 0.
split(v(V), V) :- V = 1.
split(X^Y, XP ^ YP) :-
split(X, XP),
split(Y, YP).
示例查询：
?- split(v(X)^v(Y), R). X = Y, Y = 0, R = 0^0 ; X = 0, Y = 1, R = 0^1 ; X = 1, Y = 0, R = 1^0 ; X = Y, Y = 1, R = 1^1.
请注意，此仍然在所有方向上都有效，在最一般的情况下也是如此:
?- split(Expr, R). Expr = v(0), R = 0 ; Expr = v(1), R = 1 ; Expr = v(0)^v(0), R = 0^0 ; Expr = v(0)^v(1), R = 0^1 ; etc.
根据经验，一旦您必须在代码中使用像 var/1 这样的 extra-logical 谓词，保持其逻辑纯洁性和单调性的希望就很小了。以干净的表示为目标以保留这些属性。
有时，使用默认表示是不可避免的，例如，因为您想让用户更轻松地输入。在这种情况下，目标是在开始实际推理之前快速将它们转换为干净的。
在某个时候，我写了一个非常小的程序，它似乎或多或少是您要找的东西。我真的希望我没有完全误读你的问题。您可以检查整个程序的 this SWISH program。有一些差异，比如使用 f 和 t 而不是 0 和 1，或者使用 and 和 or 而不是 ^ 和 v.不过基本思路和你一样（我觉得）
如果我删除一些不必要的东西来演示，那么程序就是这样：
:- op(100, fy, ?).
:- op(500, yfx, and).
:- op(500, yfx, or).
table(F, T) :-
term_variables(F, Vs),
bagof(R-Vs, bl(F, R), T).
bl(?X, R) :-
v(X, R).
bl(X and Y, R) :-
bl(X, R0),
and_bl(R0, Y, R).
bl(X or Y, R) :-
bl(X, R0),
or_bl(R0, Y, R).
v(f, f).
v(t, t).
and_bl(f, _, f).
and_bl(t, Y, R) :- bl(Y, R).
or_bl(f, Y, R) :- bl(Y, R).
or_bl(t, _, t).
这里的要点是我有一个纯粹的关系，我的 v/2，它简单地说明 true 的值是 true 而 [=21= 的值] 是 false。然后，我使用相互递归定义来实际评估布尔表达式，最终在 v/2.
我决定自己 "tag" 布尔变量，所以你必须写 ?X 而不是 X。如果我没记错的话，当时我意识到我需要一种方法来明确说明表达式中是否有布尔变量，或者整个表达式是否仍然是 "unknown"。换句话说，这个：?X 是 t 或 f 并且这个：Expr 可以是 ?X，或 not ?X，或 ?X and ?Y，或?X or ?Y，或not (?X and ?Y)，依此类推。
用 ?X 标记变量可以避免 "defaulty representation" 是
以下是使用方法：
?- bl(?t and ?X, R).
X = R, R = f ;
X = R, R = t.
?- bl(?t or ?X, R).
R = t.
?- bl(?A or (?B and ?C), R).
A = B, B = R, R = f ;
A = C, C = R, R = f,
B = t ;
A = f,
B = C, C = R, R = t ;
A = R, R = t.
?- table(?A or (?B and ?A), R).
R = [f-[f, f], f-[f, t], t-[t, _7734]].
已经有两个很好的答案，一个是纯粹的答案，另一个是使用 term_variables/2 的较短的答案。我还想说一个细节：
So, I can see what the problem is here, which is that on the way through
split(Y, YP)Prolog has exhausted the first two clauses, so it winds up insplit(X^Y, ...)again, unifying myYwithX'^Y', essentially. I am just not sure what I need to do to close off that path except at the outset where I have the structure^/2.
如果您不想在第一个参数是变量的情况下与 X^Y 执行 head 统一，请将统一从 head 中拉出。没有什么可以强迫您将术语 X^Y 放在那里！如果前两个条款不适用，你要做的是只考虑你的最后一个条款。前两个子句被var/1保护，所以你可以用nonvar/1保护最后一个：
split(V, R) :- var(V), R = 0.
split(V, R) :- var(V), R = 1.
split(Term, SplitTerm) :-
nonvar(Term),
Term = X ^ Y,
split(X, XP),
split(Y, YP),
SplitTerm = XP ^ YP.
这样您的示例就可以正常工作了：
?- split(Y, R).
R = 0 ;
R = 1 ;
false.
?- split(X^Y, R).
R = 0^0 ;
R = 0^1 ;
R = 1^0 ;
R = 1^1 ;
false.
编辑： 正如 mat 在评论中指出的那样，使用像 var/1 这样的测试会给你带来各种麻烦。
一个问题是您必须仔细检查不同级别的实例化：mat 的 split(1, R) 示例查询因上述代码而失败（它应该因 R = 1 而成功）。这是因为 1 属于 nonvar 的情况，但不与 _^_ 统一。如果我们这样做，我们不仅要区分 var 和 nonvar 情况，还要区分 var、ground 和 nonvar-but-not-ground。这有点乱。
另一个问题是查询 split(V, R), V = 1，它在声明上等同于上面的查询，但成功了两次，包括解决方案 R = V。这是因为 split/2 的这个定义（故意）避免在其参数之间引入共享。我们是否需要共享取决于规范。
我不会尝试通过实例化测试给出一个完全可靠的解决方案，因为我的意思并不是说这是最好的方法。