此查询的SLD树是什么? [英] What's the SLD tree for this query?

问题描述

让我们考虑以下Prolog程序(来自"Prolog的艺术"):

Let's consider the following Prolog program (from "The Art of 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).有人可以帮助我了解这种行为吗?

Both SICStus and SWI produce the expected Z = s(s(s(s(0)))) answer, but query the user for the next answer (a correct no/false answer). However, I cannot understand why there is an open branch in the SLD tree after the only goal is found. I tried debugging both under SICStus and under SWI, but I am not really able to interpret the result yet. I can only say that, as far as I could understand, both backtrack to plus(s(s(s(0))), 0, _Z2). Can someone help me understanding this behavior?

推荐答案

由于Prolog，此问题与SLD树不直接相关 系统不以先行方式构建SLD树，因为 你描述它.但是某些Prolog中有一些优化 系统本质上具有这种效果并改变了盲目暴力 强制头匹配.即建立索引和消除选择点.

The problem is not directly related to SLD trees, since Prolog systems do not build SLD trees in a look-ahead manner as you describe it. But some optimizations found in certain Prolog systems essentially have this effect and change the blind brute force head matching. Namely indexing and choice point elimination.

现在存在SWI-Prolog的已知限制.虽然有 多参数索引，它不执行选择点消除 用于非第一个参数索引级联索引.方法 它只选择一个论点，但没有其他论点.有一些 执行多参数索引和级联索引的Prolog系统. 例如，在 Jekejeke Prolog 我们没有否/false:

There is now a known limitation of SWI-Prolog. Although it does multi-argument indexing, it does not do choice point elimination for non-first argument indexes cascaded indexing. Means it only picks one argument, but then no further. There are some Prolog systems that do multi argument indexing and cascaded indexing. For example in Jekejeke Prolog we do not have No/false:

再见

P.S .: Jekejeke Prolog的最新版本甚至没有 实际上是级联的，因为它检测到第一个参数索引 没有敏感性.因此，尽管它为 由于实际的呼叫方式而产生的第一个参数，它会跳过 第一个参数索引，并且不使用它，而仅使用 第二个论点.跳过可以加快速度. :-)

P.S.: The newest version of Jekejeke Prolog even does not literally cascade, since it detects that the first argument index has no sensitivity. Therefore although it builds the index for the first argument due to the actual call pattern, it skips the first argument index and does not use it, and solely uses the second argument. Skipping gives a little speed. :-)

通过

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

因此它没有下降到arg=0并构建了arg=1 在那里建立索引，而是并行构建arg=0和 arg=1索引.我们可能仍称这种启发式级联 因为单个查询会导致多个索引，但是它们 并没有真正的级联形状.

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.

这篇关于此查询的SLD树是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！