实施“最后"在序言中 [英] Implementing "last" in Prolog

问题描述

我试图通过 Ulle Endriss 的 讲义.当我对一个练习的解决方案没有达到预期的效果时，我发现很难给出一个好的解释.我认为这与我对 Prolog 评估表达式的方式的模糊理解有关.

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

<块引用>

last1([_ | Rest], Last) :- last1(Rest, Last).最后一个([最后一个]，最后一个).

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

?- last1([1], Last).最后 = 1.?- last1([1, 2], 最后一个).最后 = 2 ;错误的.

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

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

last1([1, 2], Last).==>最后一个([2]，最后一个).==>最后一个([]，最后一个).或最后 = 2.==>假或最后 = 2.

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

问题 1:last1 的行为的正确解释是什么?

问题 2:如何实现与内置 last 无法区分的谓词 last1?

解决方案

问题一:

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

实际上，它使用常量空间！

现在有两种方法:

1. 尝试优化您的定义.是的，你可以做到这一点，但你需要非常聪明！例如，@back_dragon 的定义是不正确的.经常发生的情况是，初学者试图优化程序，而实际上他们正在破坏程序的语义.

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

问题2:

考虑:

<上一页>?- last(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) 相同的方式查看查询，并得出两个子句都适用的结论.至少，我们现在有恒定的开销而不是线性开销.

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

I am trying to get a feel for Prolog programming by going through Ulle Endriss' lecture notes. When my solution to an exercise does not behave as expected, I find it difficult to give a good explanation. I think this has to do with my shaky understanding of the way Prolog evaluates expressions.

Exercise 2.6 on page 20 calls for a recursive implementation of a predicate last1 which behaves like the built-in predicate last. My attempt is as follows:

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

It gives the correct answer, but for lists with more than one element, I have to key in the semicolon to terminate the query. This makes last1 different from the built-in last.

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

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

If I switch the order in which I declared the rule and fact, then I need to key in the semicolon in both cases.

I think I know why Prolog thinks that last1 may have one more solution (thus the semicolon). I imagine it follows the evaluation sequence

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

That seems to suggest that I should look for a way to avoid matching Rest with []. Regardless, I have no explanation why switching the order of declaration ought to have any effect at all.

Question 1: What is the correct explanation for the behavior of last1?

Question 2: How can I implement a predicate last1 which is indistinguishable from the built-in last?

解决方案

Question 1:

Prolog systems are not always able to decide whether or not a clause will apply prior to executing it. The precise circumstances are implementation dependent. That is, you cannot rely on that decision in general. Systems do improve here from release to release. Consider as the simplest case:

?- X = 1 ; 1 = 2.
X = 1 ;
false.

A very clever Prolog could detect that 1 = 2 always fails, and thus simply answer X = 1. instead. On the other hand, such "cleverness" is very costly to implement and time is better spent for optimizing more frequent cases.

So why do Prologs show this at all? The primary reason is to avoid asking meekly for another answer, if Prolog already knows that there is no further answer. So prior to this improvement, you were prompted for another answer for all queries containing variables and got the false or "no" on each and every query with exactly one answer. This used to be so cumbersome that many programmers never asked for the next answer and thus were not alerted about unintended answers.

And the secondary reason is to keep you aware of the limitations of the implementation: If Prolog asks for another answer on this general query, this means that it still uses some space which might accumulate and eat up all your computing resources.

In your example with last1/2 you encounter such a case. And you already did something very smart, BTW: You tried to minimize the query to see the first occurrence of the unexpected behavior.

In your example query last1([1,2],X) the Prolog system does not look at the entire list [1,2] but only looks at the principal functor. So for the Prolog system the query looks the same as last1([_|_],X) when it decides which clauses to apply. This goal now fits to both clauses, and this is the reason why Prolog will remember the second clause as an alternative to try out.

But, think of it: This choice is now possible for all elements but the last! Which means that you pay some memory for each element! You can actually observe this by using a very long list. This I get on my tiny 32-bit laptop — you might need to add another zero or two on a larger system:

?- length(L,10000000), last1(L,E).
ERROR: Out of local stack

On the other hand, the predefined last/2 works smoothly:

?- length(L,10000000), last(L,E).
L = [_G343, _G346, _G349, _G352, _G355, _G358, _G361, _G364, _G367|...].

In fact, it uses constant space!

There are now two ways out of this:

1. Try to optimize your definition. Yes, you can do this, but you need to be very smart! The definition by @back_dragon for example is incorrect. It often happens that beginners try to optimize a program when in fact they are destroying its semantics.

2. Ask yourself if you are actually defining the same predicate as last/2. In fact, you're not.

Question 2:

Consider:

?- last(Xs, X).
Xs = [X] ;
Xs = [_G299, X] ;
Xs = [_G299, _G302, X] ;
Xs = [_G299, _G302, _G305, X] ;
Xs = [_G299, _G302, _G305, _G308, X] 
...

and

?- last1(Xs, X).
** loops **

So your definition differs in this case with SWI's definition. Exchange the order of the clauses.

?- length(L,10000000), last2(L,E).
L = [_G343, _G346, _G349, _G352, _G355, _G358, _G361, _G364, _G367|...] ;
false.

Again, this false! But this time, the big list works. And this time, the minimal query is:

?- last2([1],E).
E = 1 ;
false.

And the situation is quite similar: Again, Prolog will look at the query in the same way as last2([_|_],E) and will conclude that both clauses apply. At least, we now have constant overhead instead of linear overhead.

There are several ways to overcome this overhead in a clean fashion - but they all very much depend on the innards of an implementation.

这篇关于实施“最后"在序言中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！