在Prolog中实现"最后"

Question

我试图通过阅读Ulle Endriss的讲义来了解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带[].无论如何,我没有解释为什么切换声明的顺序应该有任何影响.

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

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

Answer 1

问题1:

Prolog系统并不总是能够在执行之前决定是否适用条款.具体情况取决于实施.也就是说,一般来说,你不能依赖这个决定.从发布到发布,系统在这里都有所改进.考虑最简单的情况:

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

一个非常聪明的Prolog可以检测到1 = 2总是失败,因此只需回答X = 1..另一方面,这种"聪明"实施起来非常昂贵,并且花费更多时间来优化更频繁的案例.

那么为什么Prologs会这么说呢？如果Prolog已经知道没有进一步的答案,主要原因是避免温顺地问另一个答案.因此,在进行此改进之前,系统会提示您为包含变量的所有查询提供另一个答案,并false在每个查询中获得" 或否",只有一个答案.这曾经是如此繁琐,许多程序员从来没有要求下一个答案,因此没有提醒意外的答案.

第二个原因是让你意识到实现的局限性:如果Prolog要求对这个一般查询提出另一个答案,这意味着它仍然会占用一些空间,这些空间可能会积累并占用你所有的计算资源.

在你的例子中last1/2遇到这种情况.你已经做了一些非常聪明的事情,BTW:你试图最小化查询以查看第一次出现的意外行为.

在您的示例查询中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|...].

事实上,它使用恒定的空间!

现在有两种方法:

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).
** 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),并将得出结论两个条款都适用.至少,我们现在有不断的开销而不是线性开销.

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

Answer 2

当SWI-Prolog可以确定没有解决方案时,它会尝试避免提示更多解决方案.我认为解释器检查内存,寻找一些choice point左,如果找不到,只需说明终止.否则它等待用户选择移动.

我会尝试以这种方式使last1确定性:

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

但我不认为这是indistinguishable从过去.潜伏在图书馆的源代码(很简单?- edit(last).)

%%  last(?List, ?Last)
%
%   Succeeds when Last  is  the  last   element  of  List.  This
%   predicate is =semidet= if List is a  list and =multi= if List is
%   a partial list.
%
%   @compat There is no de-facto standard for the argument order of
%       last/2.  Be careful when porting code or use
%       append(_, [Last], List) as a portable alternative.

last([X|Xs], Last) :-
    last_(Xs, X, Last).

last_([], Last, Last).
last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).

我们可以欣赏一个深思熟虑的实施.