Prolog 在目标重新排序后不会终止
Prolog doesn't terminate after goal reordering
我目前正在学习 Learn Prolog Now 示例，对于 exercise 我有一个知识库，如果我只是对一个规则进行微小的更改，就会用完本地堆栈。这是知识库文章：
byCar(auckland,hamilton).
byCar(hamilton,raglan).
byCar(valmont,saarbruecken).
byCar(valmont,metz).
byTrain(metz,frankfurt).
byTrain(saarbruecken,frankfurt).
byTrain(metz,paris).
byTrain(saarbruecken,paris).
byPlane(frankfurt,bangkok).
byPlane(frankfurt,singapore).
byPlane(paris,losAngeles).
byPlane(bangkok,auckland).
byPlane(singapore,auckland).
byPlane(losAngeles,auckland).
travel(X,Y) :- byCar(X,Y).
travel(X,Y) :- byTrain(X,Y).
travel(X,Y) :- byPlane(X,Y).
和相关规则：
travel(X,Y) :- travel(X,Z), travel(Z,Y).
这是用完堆栈的有问题的查询：
?- travel(valmont,losAngeles).
但是如果我将规则更改为
travel(X,Y) :- travel(Z,Y), travel(X,Z).
然后就可以了。
如果我跟踪查询，我很快就会像这样卡住：
Redo: (17) travel(raglan, _6896) ? creep
Call: (18) byPlane(raglan, _6896) ? creep
Fail: (18) byPlane(raglan, _6896) ? creep
Redo: (17) travel(raglan, _6896) ? creep
Call: (18) travel(raglan, _6896) ? creep
Call: (19) byCar(raglan, _6896) ? creep
Fail: (19) byCar(raglan, _6896) ? creep
Redo: (18) travel(raglan, _6896) ? creep
Call: (19) byTrain(raglan, _6896) ? creep
Fail: (19) byTrain(raglan, _6896) ? creep
Redo: (18) travel(raglan, _6896) ? creep
Call: (19) byPlane(raglan, _6896) ? creep
Fail: (19) byPlane(raglan, _6896) ? creep
Redo: (18) travel(raglan, _6896) ? creep
...
但我不明白为什么。难道它不应该只知道 raglan 是一个终端站，因此它必须再回溯一级吗？
谢谢！
编辑：我使用 SWI Prolog
编辑： 一步步过后发现了问题。
就插肩而言，任何地方都没有规则。因此，在尝试 byPlane, byTrain, byCar 之后，它会再次尝试 travel(raglan, X) （最后一条规则的第一个目标），从而循环。
但是我看不出其他规则有什么更好的。
显然，目标排序在这种情况下非常重要。如您所想，您的第一个公式允许通过假设的另一个城市 Z 找到从插肩到任何地方的另一个假设连接，其 none 存在从未得到证实，因为您一直在无限递归地寻找它。真的，痕迹是你最好的朋友，但这并不是一件容易的事。您还必须考虑其中一个、两个或 none 个参数被绑定的所有情况。
你的第二个公式一点也不好，它只是碰巧在不同的情况下失败了：
travel(losAngeles, valmont).
ERROR: Out of local stack
我建议通过区分直接连接和多站旅程来使您的逻辑更安全：
connection(X,Y) :- byCar(X,Y).
connection(X,Y) :- byTrain(X,Y).
connection(X,Y) :- byPlane(X,Y).
travel(X,Y) :- connection(X,Y).
travel(X,Y) :- connection(X,Z), travel(Z,Y).
目标顺序现在不重要，因为 travel 总是需要存在一些物理连接（而不是递归）才能继续。
这也让记录旅程变得更容易，这是您无论如何都想要的（对吧？）：
connection(X,Y, car(X,Y)) :- byCar(X,Y).
connection(X,Y, train(X,Y)) :- byTrain(X,Y).
connection(X,Y, plane(X,Y)) :- byPlane(X,Y).
travel(X,Y,[Part]) :- connection(X,Y,Part).
travel(X,Y,[Part|Parts]) :- connection(X,Z,Part), travel(Z,Y,Parts).
?- travel(valmont, losAngeles, Journey).
Journey = [car(valmont, saarbruecken), train(saarbruecken, paris), plane(paris, losAngeles)]
对于没有有效行程的情况：
travel(losAngeles, valmont, Journey).
false.
您需要澄清 "it works" 的意思。事实上，谓词 travel/2 的两个版本都没有终止。但是碰巧找到了针对高度特定查询的解决方案。
现在问 ?- travel(hamilton, losAngeles). 这两个循环。
因此您的修复仅适用于某些查询，但不适用于其他查询。有没有更靠谱的出路？
一般来说，Prolog 生成的非常精确的答案替换序列很难预测。您将不得不模拟 Prolog 采取的每一个微小步骤。
另一方面，有一个非常相关的概念称为（通用）终止，它更容易预测，因为它独立于程序中的许多细节，例如顺序您的事实出现在其中。查询通用终止的最简单方法是在查询末尾添加目标 false。
但是您可以进一步添加目标 false 到任何您想要的地方1。这种修改后的程序称为failure-slice。无论您如何插入 false，以下内容都成立：
If the failure-slice does not terminate, then also your original program does not terminate.
现在考虑 travel/2 的两个变体的故障切片：
travel(X,Y) :- false, byCar(X,Y).
travel(X,Y) :- false, byTrain(X,Y).
travel(X,Y) :- false, byPlane(X,Y).
travel(X,Y) :- travel(X,Z), false, travel(Z,Y).
你的其他版本：
travel(X,Y) :- false, byCar(X,Y).
travel(X,Y) :- false, byTrain(X,Y).
travel(X,Y) :- false, byPlane(X,Y).
travel(X,Y) :- travel(Z,Y), false, travel(X,Z).
两者都没有考虑X和Y！所以这两个参数不影响终止。因此两个版本都不会终止。也就是说，它们从不终止。
现在将此结论与查看轨迹的更传统方法进行比较。虽然失败切片允许我们做出一般性结论（“...永不终止”），但特定跟踪只能向您显示一次特定执行的详细信息。
为了解决这个问题，您需要在可见部分进行一些更改。我的建议是使用 closure/3。即：
travel(X, Y) :-
closure(connexion, X, Y).
connexion(X,Y) :- byCar(X,Y).
connexion(X,Y) :- byTrain(X,Y).
connexion(X,Y) :- byPlane(X,Y).
或者使用更通用的path/4。
1 实际上，这只适用于纯单调程序。你的程序就是其中之一
我目前正在学习 Learn Prolog Now 示例，对于 exercise 我有一个知识库，如果我只是对一个规则进行微小的更改，就会用完本地堆栈。这是知识库文章：
byCar(auckland,hamilton).
byCar(hamilton,raglan).
byCar(valmont,saarbruecken).
byCar(valmont,metz).
byTrain(metz,frankfurt).
byTrain(saarbruecken,frankfurt).
byTrain(metz,paris).
byTrain(saarbruecken,paris).
byPlane(frankfurt,bangkok).
byPlane(frankfurt,singapore).
byPlane(paris,losAngeles).
byPlane(bangkok,auckland).
byPlane(singapore,auckland).
byPlane(losAngeles,auckland).
travel(X,Y) :- byCar(X,Y).
travel(X,Y) :- byTrain(X,Y).
travel(X,Y) :- byPlane(X,Y).
和相关规则：
travel(X,Y) :- travel(X,Z), travel(Z,Y).
这是用完堆栈的有问题的查询：
?- travel(valmont,losAngeles).
但是如果我将规则更改为
travel(X,Y) :- travel(Z,Y), travel(X,Z).
然后就可以了。
如果我跟踪查询，我很快就会像这样卡住：
Redo: (17) travel(raglan, _6896) ? creep
Call: (18) byPlane(raglan, _6896) ? creep
Fail: (18) byPlane(raglan, _6896) ? creep
Redo: (17) travel(raglan, _6896) ? creep
Call: (18) travel(raglan, _6896) ? creep
Call: (19) byCar(raglan, _6896) ? creep
Fail: (19) byCar(raglan, _6896) ? creep
Redo: (18) travel(raglan, _6896) ? creep
Call: (19) byTrain(raglan, _6896) ? creep
Fail: (19) byTrain(raglan, _6896) ? creep
Redo: (18) travel(raglan, _6896) ? creep
Call: (19) byPlane(raglan, _6896) ? creep
Fail: (19) byPlane(raglan, _6896) ? creep
Redo: (18) travel(raglan, _6896) ? creep
...
但我不明白为什么。难道它不应该只知道 raglan 是一个终端站，因此它必须再回溯一级吗？
谢谢！
编辑：我使用 SWI Prolog
编辑： 一步步过后发现了问题。
就插肩而言，任何地方都没有规则。因此，在尝试 byPlane, byTrain, byCar 之后，它会再次尝试 travel(raglan, X) （最后一条规则的第一个目标），从而循环。
但是我看不出其他规则有什么更好的。
显然，目标排序在这种情况下非常重要。如您所想，您的第一个公式允许通过假设的另一个城市 Z 找到从插肩到任何地方的另一个假设连接，其 none 存在从未得到证实，因为您一直在无限递归地寻找它。真的，痕迹是你最好的朋友，但这并不是一件容易的事。您还必须考虑其中一个、两个或 none 个参数被绑定的所有情况。
你的第二个公式一点也不好，它只是碰巧在不同的情况下失败了：
travel(losAngeles, valmont).
ERROR: Out of local stack
我建议通过区分直接连接和多站旅程来使您的逻辑更安全：
connection(X,Y) :- byCar(X,Y).
connection(X,Y) :- byTrain(X,Y).
connection(X,Y) :- byPlane(X,Y).
travel(X,Y) :- connection(X,Y).
travel(X,Y) :- connection(X,Z), travel(Z,Y).
目标顺序现在不重要，因为 travel 总是需要存在一些物理连接（而不是递归）才能继续。
这也让记录旅程变得更容易，这是您无论如何都想要的（对吧？）：
connection(X,Y, car(X,Y)) :- byCar(X,Y).
connection(X,Y, train(X,Y)) :- byTrain(X,Y).
connection(X,Y, plane(X,Y)) :- byPlane(X,Y).
travel(X,Y,[Part]) :- connection(X,Y,Part).
travel(X,Y,[Part|Parts]) :- connection(X,Z,Part), travel(Z,Y,Parts).
?- travel(valmont, losAngeles, Journey).
Journey = [car(valmont, saarbruecken), train(saarbruecken, paris), plane(paris, losAngeles)]
对于没有有效行程的情况：
travel(losAngeles, valmont, Journey).
false.
您需要澄清 "it works" 的意思。事实上，谓词 travel/2 的两个版本都没有终止。但是碰巧找到了针对高度特定查询的解决方案。
现在问 ?- travel(hamilton, losAngeles). 这两个循环。
因此您的修复仅适用于某些查询，但不适用于其他查询。有没有更靠谱的出路？
一般来说，Prolog 生成的非常精确的答案替换序列很难预测。您将不得不模拟 Prolog 采取的每一个微小步骤。
另一方面，有一个非常相关的概念称为（通用）终止，它更容易预测，因为它独立于程序中的许多细节，例如顺序您的事实出现在其中。查询通用终止的最简单方法是在查询末尾添加目标 false。
但是您可以进一步添加目标 false 到任何您想要的地方1。这种修改后的程序称为failure-slice。无论您如何插入 false，以下内容都成立：
If the failure-slice does not terminate, then also your original program does not terminate.
现在考虑 travel/2 的两个变体的故障切片：
travel(X,Y) :- false, byCar(X,Y).travel(X,Y) :- false, byTrain(X,Y).travel(X,Y) :- false, byPlane(X,Y). travel(X,Y) :- travel(X,Z), false,travel(Z,Y).
你的其他版本：
travel(X,Y) :- false, byCar(X,Y).travel(X,Y) :- false, byTrain(X,Y).travel(X,Y) :- false, byPlane(X,Y). travel(X,Y) :- travel(Z,Y), false,travel(X,Z).
两者都没有考虑X和Y！所以这两个参数不影响终止。因此两个版本都不会终止。也就是说，它们从不终止。
现在将此结论与查看轨迹的更传统方法进行比较。虽然失败切片允许我们做出一般性结论（“...永不终止”），但特定跟踪只能向您显示一次特定执行的详细信息。
为了解决这个问题，您需要在可见部分进行一些更改。我的建议是使用 closure/3。即：
travel(X, Y) :-
closure(connexion, X, Y).
connexion(X,Y) :- byCar(X,Y).
connexion(X,Y) :- byTrain(X,Y).
connexion(X,Y) :- byPlane(X,Y).
或者使用更通用的path/4。
1 实际上，这只适用于纯单调程序。你的程序就是其中之一