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

问题描述

让我们考虑以下 Prolog 程序(来自The Art of Prolog"):

natural_number(0).自然数(s(X)):- 自然数(X).加(X，0，X):-自然数(X).加(X，s(Y)，s(Z)):-加(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).有人可以帮我理解这种行为吗?

解决方案

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

现在 SWI-Prolog 存在一个已知限制.虽然它确实多参数索引，它不做选择点消除对于非第一个参数索引 级联索引.方法它只选择一个论点，但没有进一步.有一些执行多参数索引和级联索引的 Prolog 系统.例如在 命令开发环境版本:

?- 转储(加/3).-------- 加/3 ---------长度=2参数=0=长度=2参数=10=长度=1s=长度=1是的

所以它并没有沦为 arg=0 并构建了一个 arg=1索引，而是并行构建 arg=0 和arg=1 索引.我们可能仍将其称为启发式级联因为单个查询会导致多个索引，但它们没有真正的级联形状.

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).

and the query:

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

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?

解决方案

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.

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:

Bye

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

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屋！