实施“最后"操作.在序言中 [英] Implementing "last" in Prolog
问题1:
Prolog系统并不总是能够在执行子句之前决定是否使用该子句.确切的情况取决于实现方式.也就是说，您通常不能依赖该决定.系统在各个发行版之间确实有所改进.考虑最简单的情况:
?- X = 1 ; 1 = 2. X = 1 ; false.
非常聪明的Prolog可以检测到1 = 2始终失败，因此只需回答X = 1..另一方面，这种灵巧"的实现成本很高，并且在优化更常见的案例上花费了更多的时间.
那么，为什么Prologs完全显示了这一点?首要原因是，如果Prolog已经知道没有其他答案，则避免轻率地询问其他答案.因此，在进行此改进之前，系统会提示您为所有包含变量的查询提供另一个答案，并且在每个查询中都给出一个正确答案的false或否".过去如此繁琐，以至于许多程序员从来没有要求下一个答案，因此也没有对意想不到的答案保持警惕.
第二个原因是让您了解实现的局限性:如果Prolog在此一般查询中要求另一个答案，这意味着它仍然占用一些空间，这些空间可能会累积并耗尽您的所有计算资源. /p>
在使用last1/2的示例中，您遇到了这种情况.而且，您已经做了一些非常聪明的事情，顺便说一句:您试图最小化查询以查看意外行为的首次出现.
在示例查询last1([1,2],X)中，Prolog系统不会查看整个列表[1,2]，而只会查看主体函子.因此，对于Prolog系统，查询决定要应用哪个子句时，其外观与last1([_|_],X)相同.现在，这个目标适合这两个子句，这就是Prolog会记住第二个子句作为尝试的替代项的原因.
但是，请考虑一下:现在，除了最后一个元素，所有元素都可以进行此选择！这意味着您需要为每个元素支付一些内存！实际上，您可以通过使用很长的列表来观察此情况.这是我在我的小型32位笔记本电脑上看到的—您可能需要在较大的系统上添加另一个零或两个:
?- length(L,10000000), last1(L,E). ERROR: Out of local stack
另一方面，预定义的last/2可以正常运行:
?- length(L,10000000), last(L,E). L = [_G343, _G346, _G349, _G352, _G355, _G358, _G361, _G364, _G367|...].
实际上，它使用恒定空间！
现在有两种解决方法:
-
尝试优化您的定义.是的，您可以这样做，但是您必须非常聪明！例如，@ back_dragon的定义不正确.实际上，初学者实际上在破坏程序的语义时会尝试优化程序.
-
请问一下您是否实际上在定义与
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). ** loops **
因此，在这种情况下，您的定义与SWI的定义不同.交换子句的顺序.
?- length(L,10000000), last2(L,E). L = [_G343, _G346, _G349, _G352, _G355, _G358, _G361, _G364, _G367|...] ; false.
再次，这个false！但这一次，大清单起作用了.这次，最小的查询是:
?- last2([1],E). E = 1 ; false.
情况非常相似:同样，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:
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.
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屋！
