对查询和回溯感到困惑

Question

我对使用一些规则进行查询时会发生什么感到有点困惑。下面是我笔记中的示例代码。

link(fortran, algol60).
link(algol60,cpl).
link(cpl, bcpl).
link(bcpl, c).
link(c, cplusplus).
link(algol60, simula67).
link(simula67, cplusplus).
link(simula67, smalltalk80).

path(L,M) :-   %first path
    link(L,M). %first link

path(L,M) :-   %second path
    link(L,X), %second link
    path(X,M). %third path



 | ?- path(X,bcpl).

当我们查询它时，我们将调用第一个路径，X将被初始化到cpl，因为link(cpl，bcpl)是数据库中第一个匹配的东西。所以现在L= cpl和M= bcpl。X= cpl？；然后继续按；

接下来会发生什么？我们称第一条路径为第一条路径还是第二条路径？如果我们失败了一条规则会发生什么，我们是从第一条路径重新开始吗？

Answer 1

按;键您需要下一个解决方案。正如您已经知道的，Prolog中的替代项是用多个子句表示的。

事实上，从上到下、从左到右的抽象解释既不会尝试第一个路径/2，也不会尝试第二个路径/2，而是会首先尝试查看是否存在另一个link(X,bcpl)。

由于索引的原因，SWI-Prolog不会尝试调用其中的任何一个(它知道没有另一个合适的链接/2)，而是会回溯并尝试下一个路径/2(第二个规则)。

这里有一个(部分)跟踪:当您看到Redo时，这意味着它正在选择下一个可用的替代方案。括号之间的数字是调用级别，但是您可以看到，对于某些实现细节，证明并不是从1开始的。

?- leash(-all), trace, path(X,bcpl).
   Call: (7) path(_G2093, bcpl)
   Call: (8) link(_G2093, bcpl)
   Exit: (8) link(cpl, bcpl)
   Exit: (7) path(cpl, bcpl)
X = cpl ;
   Redo: (7) path(_G2093, bcpl)
   Call: (8) link(_G2093, _G2262)
   Exit: (8) link(fortran, algol60)
   Call: (8) path(algol60, bcpl)
   Call: (9) link(algol60, bcpl)
   Fail: (9) link(algol60, bcpl)
   Redo: (8) path(algol60, bcpl)
   Call: (9) link(algol60, _G2262)
   Exit: (9) link(algol60, cpl)
   Call: (9) path(cpl, bcpl)
   Call: (10) link(cpl, bcpl)
   Exit: (10) link(cpl, bcpl)
   Exit: (9) path(cpl, bcpl)
   Exit: (8) path(algol60, bcpl)
   Exit: (7) path(fortran, bcpl)
X = fortran ;
   Redo: (9) path(cpl, bcpl)
...
   Fail: (8) path(cplusplus, bcpl)
   Redo: (8) link(_G2093, _G2262)
   Exit: (8) link(simula67, smalltalk80)
   Call: (8) path(smalltalk80, bcpl)
   Call: (9) link(smalltalk80, bcpl)
   Fail: (9) link(smalltalk80, bcpl)
   Redo: (8) path(smalltalk80, bcpl)
   Call: (9) link(smalltalk80, _G2262)
   Fail: (9) link(smalltalk80, _G2262)
   Fail: (8) path(smalltalk80, bcpl)
   Fail: (7) path(_G2093, bcpl)
false.