4

让我们考虑以下 Prolog 程序（来自“Prolog 的艺术”）：

natural_number(0).
natural_number(s(X)) :- natural_number(X).

plus(X, 0, X) :- natural_number(X).
plus(X, s(Y), s(Z)) :- plus(X, Y, Z).

和查询：

?- plus(s(s(s(0))), s(0), Z).

SICStus 和 SWI 都会产生预期的Z = s(s(s(s(0))))答案，但会向用户查询下一个答案（正确no/false答案）。但是，我无法理解为什么在找到唯一目标之后 SLD 树中有一个开放的分支。我尝试在 SICStus 和 SWI 下进行调试，但我还不能真正解释结果。我只能说，据我所知，两者都回溯到plus(s(s(s(0))), 0, _Z2). 有人可以帮助我理解这种行为吗？

4

3 回答 3

2

Many Prolog systems are not as smart as we expect them to be. This has several reasons, mostly because of a tradeoff choice of the implementer. What appears important to some might not be that important to others.

As a consequence these leftover choicepoints may accumulate in time and prevent to free auxiliary data. For example, when you want to read in a long list of text. A list that is that long that it does not fit into memory at once, but still can be processed efficiently with library(pio).

If you expect exactly one answer, you might use call_semidet/1 to make it determinate. See this answer for its definition and a use case.

?- plus(s(s(s(0))), s(0), Z).
Z = s(s(s(s(0)))) ;
false.

?- call_semidet(plus(s(s(s(0))), s(0), Z)).
Z = s(s(s(s(0)))).

But you can see it also from a more optimistic side: Modern toplevels (like the one in SWI) do show you when there are leftover choicepoints. So you can consider some countermeasures like call_semidet/1.

Here are some related answers:

于 2012-10-31T19:14:26.290 回答
1

该问题与 SLD 树没有直接关系，因为 Prolog 系统不会像您描述的那样以前瞻方式构建 SLD 树。但是在某些 Prolog 系统中发现的一些优化基本上具有这种效果并改变了盲目的蛮力头部匹配。即索引和选择点消除。

现在有一个已知的 SWI-Prolog 限制。尽管它进行多参数索引，但它不会对非第一个参数索引级联索引进行选择点消除。意味着它只选择一个论点，但没有进一步。有一些 Prolog 系统可以进行多参数索引和级联索引。例如，在Jekejeke Prolog中，我们没有 No/false：

皮亚诺级联

再见

PS：最新版本的 Jekejeke Prolog 甚至没有字面上的级联，因为它检测到第一个参数索引没有敏感性。因此，尽管由于实际调用模式，它为第一个参数构建索引，但它会跳过第一个参数索引并且不使用它，而只使用第二个参数。跳过会带来一点速度。:-)

The skipping is seen via the dump/1 command of the development environment version:

?- dump(plus/3).
-------- plus/3 ---------
length=2
arg=0
  =length=2
arg=1
  0=length=1
  s=length=1
Yes

So it has not decended into arg=0 and built an arg=1 index there, but instead built in parallel an arg=0 and an arg=1 index. We might still call this heuristic cascading since individual queries lead to multiple indexes, but they have not really the shape of a cascade.

于 2012-10-31T18:10:47.053 回答
0

对我们来说，加号的两个从句显然是“分离的”。我们可以这样说，因为我们知道0 \= s(Y)。但是（我认为）这样的分析通常是令人望而却步的，然后 Prolog 认为这样的分支仍有待证明：这里有一条踪迹表明，在找到第一个解决方案后，调用 (7) 仍然对替代方案“开放”。

在此处输入图像描述

于 2012-10-31T17:23:29.530 回答