list - 在 Prolog 中实现 "last"

Question

我试图通过 Ulle Endriss 的 lecture notes 来感受 Prolog 编程。 .当我对练习的解决方案没有达到预期时，我发现很难给出一个很好的解释。我认为这与我对 Prolog 评估表达式的方式的理解不稳定有关。

第 20 页的练习 2.6 要求递归实现谓词 last1其行为类似于内置谓词 last .我的尝试如下:

last1([_ | Rest], Last) :- last1(Rest, Last).
last1([Last], Last).

它给出了正确的答案，但对于包含多个元素的列表，我必须输入分号来终止查询。这使得 last1不同于内置last .

?- last1([1], Last).
Last = 1.

?- last1([1, 2], Last).
Last = 2 ;
false.

如果我切换我声明规则和事实的顺序，那么在这两种情况下我都需要输入分号。

我想我知道为什么 Prolog 认为 last1可能还有一个解决方案(因此是分号)。我想它遵循评估顺序

last1([1, 2], Last).
==>  last1([2], Last).
==>  last1([], Last).    OR    Last = 2.
==>  false    OR    Last = 2.

这似乎表明我应该寻找一种方法来避免匹配 Rest与 [] .无论如何，我无法解释为什么切换声明顺序应该有任何效果。

问题一:对 last1 行为的正确解释是什么？ ?

问题2:如何实现谓词 last1这与内置的 last 没有区别?

Answer 1

问题 1:

Prolog 系统并不总是能够在执行一个子句之前决定它是否适用。确切的情况取决于实现。也就是说，您不能完全依赖该决定。系统确实会从一个版本到另一个版本不断改进。考虑最简单的情况:

?- X = 1 ; 1 = 2。
X = 1 ;
错误的。

一个非常聪明的 Prolog 可以检测到 1 = 2总是失败，因此只需回答 X = 1.反而。另一方面，这种“聪明”的实现成本非常高，最好将时间花在优化更频繁的案例上。

那么为什么 Prologs 会显示这一点呢？主要原因是避免温顺地要求另一个答案，如果 Prolog 已经知道没有进一步的答案。因此，在此改进之前，系统会提示您为所有包含变量的查询提供另一个答案，并得到 false或“否”对每个查询都只有一个答案。这在过去非常麻烦，以至于许多程序员从不询问下一个答案，因此也没有注意到意外答案。

第二个原因是让您了解实现的局限性:如果 Prolog 要求对这个一般查询提供另一个答案，这意味着它仍然使用一些空间，这可能会累积并耗尽您的所有计算资源。

在你的例子中 last1/2你遇到这样的情况。而且您已经做了一些非常聪明的事情，顺便说一句:您尝试最小化查询以查看第一次出现的意外行为。

在您的示例查询中 last1([1,2],X) Prolog 系统不会查看整个列表 [1,2]但只看主仿函数。因此，对于 Prolog 系统，查询看起来与 last1([_|_],X) 相同。当它决定适用哪些条款时。这个目标现在适合两个子句，这就是 Prolog 将记住第二个子句作为尝试的替代方案的原因。

但是，想一想:这个选择现在是可能的所有 元素但最后!这意味着您为每个元素支付一些内存!您实际上可以通过使用很长的列表来观察这一点。这是我在我的小型 32 位笔记本电脑上得到的——你可能需要在更大的系统上再添加零或两个:

?- 长度(L,10000000), last1(L,E)。
错误:超出本地堆栈

另一方面，预定义的 last/2工作顺利:

?- 长度(L，10000000)，最后(L，E)。
L = [_G343、_G346、_G349、_G352、_G355、_G358、_G361、_G364、_G367|...]。

事实上，它使用 常数 空间!

现在有两种方法可以解决这个问题:

尝试优化您的定义。是的，你可以这样做，但你需要非常聪明!例如@back_dragon 的定义是不正确的。初学者经常尝试优化程序，但实际上他们正在破坏其语义。

问问自己是否真的定义了与 last/2 相同的谓词.事实上，你不是。

问题2:

考虑:

?- 最后(Xs，X)。
Xs = [X] ;
Xs = [_G299, X] ;
Xs = [_G299, _G302, X];
Xs = [_G299, _G302, _G305, X];
Xs = [_G299, _G302, _G305, _G308, X]
...

和

?- last1(Xs, X)。
** 循环 **

因此，在这种情况下，您的定义与 SWI 的定义不同。交换条款的顺序。

?- 长度(L,10000000), last2(L,E)。
L = [_G343、_G346、_G349、_G352、_G355、_G358、_G361、_G364、_G367|...]；
错误的。

同样，这个 false !但这一次，大名单起作用了。而这一次，最小的查询是:

?- last2([1],E)。
E = 1 ;
错误的。

情况非常相似:同样，Prolog 会以与 last2([_|_],E) 相同的方式查看查询。并将得出结论，这两个条款都适用。至少，我们现在有恒定的开销而不是线性开销。

有几种方法可以以干净的方式克服这种开销 - 但它们都非常依赖于实现的内部结构。