Prolog DCG:找到最后一个元素

Question

我想更好地了解DCG的使用.为了做到这一点,我尝试将LearnPrologNow书中的一些练习翻译成DCG表示法.但是,我失败了.

我试图编写一个程序,只列出列表中的最后一个元素.就这样.我只是想不出正确的DCG语法来做到这一点.我想我找出了应该是的"基本案例":

最后 - > [X | []].

其中X是最后一个元素.如何让Prolog以递归的方式进入列表？或者我是否以错误的方式思考DCG？

Answer 1

... --> [] | [_], ... .

list_last(Xs, X) :-
   phrase((...,[X]), Xs).

这显然是最"图形化"的定义.你可以描述很多模式... //0.

语法是描述语言的一种方式.所以你关于如何让Prolog失败的问题是不好的.语法不做任何事情.如果你坚持"生成"句子,他们.

对于程序细节,您需要了解终止,但仅限于此.

编辑:如果你真的关心性能,那么先测量它.通过SWI,我获得以下内容.请注意使用额外的库来删除调用开销phrase/2.

?- use_module(library(apply_macros)).
%   library(pairs) compiled into pairs 0.00 sec, 22 clauses
%  library(lists) compiled into lists 0.01 sec, 122 clauses
%  library(occurs) compiled into occurs 0.00 sec, 14 clauses
% library(apply_macros) compiled into apply_macros 0.01 sec, 168 clauses
true.

?- [user].
**omitted**
?- listing.

dcg_last(B, A) :-
        last(A, B, []).

list_last(A, C) :-
        ...(A, B),
        B=[C].

...(A, B) :-
        (   A=B
        ;   A=[_|C],
            ...(C, B)
        ).

last(A, [_|B], C) :-
        last(A, B, C).
last(A, [A|B], B).

:- thread_local thread_message_hook/3.
:- dynamic thread_message_hook/3.
:- volatile thread_message_hook/3.

true.

?- length(L,100000), time(list_last(L,E)).
% 100,000 inferences, 0.018 CPU in 0.030 seconds (60% CPU, 5482960 Lips)
L = [_G351, _G354, _G357, _G360, _G363, _G366, _G369, _G372, _G375|...] ;
% 5 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 294066 Lips)
false.

?- length(L,100000), time(dcg_last(L,E)).
% 100,001 inferences, 0.033 CPU in 0.057 seconds (58% CPU, 3061609 Lips)
L = [_G19, _G22, _G25, _G28, _G31, _G34, _G37, _G40, _G43|...] ;
% 2 inferences, 0.011 CPU in 0.023 seconds (49% CPU, 175 Lips)
false.

所以两者都执行大致相同数量的推断,但dcg_last/2速度较慢,因为它必须堆积所有那些无用的选择点.list_last/2创建相同数量的选择点,然而,它们几乎立即被删除.所以我们有0.018s对0.033s + 0.011s.