序言 DCG : find last element

Question

我试图更好地理解 DCG 的使用。为了做到这一点，我尝试将 LearnPrologNow 书中的一些练习翻译成 DCG 符号。然而，我失败的很惨。

我试图编写一个简单地命名列表中最后一个元素的程序。就这样。我只是想不出正确的 DCG 语法来做到这一点。我想我想出了“基本情况”应该是:

last --> [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) 编译成对 0.00 秒，22 个子句
% library(lists) 编译成列表 0.01 秒，122 个子句
% library(occurs) 编译成发生 0.00 秒，14 个子句
% library(apply_macros) 编译成 apply_macros 0.01 秒，168 个子句
真的。

?- [用户]。
**省略**
？- list 。

dcg_last(B, A) :-
最后(A，B，[])。

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

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

最后(A, [_|B], C) :-
最后(A，B，C)。
最后(A，[A|B]，B)。

:- thread_local thread_message_hook/3。
:- 动态 thread_message_hook/3。
:- volatile thread_message_hook/3。

真的。

?- 长度(L,100000), 时间(list_last(L,E))。
% 100,000 次推理，0.030 秒内 0.018 CPU(60% CPU，5482960 唇)
L = [_G351、_G354、_G357、_G360、_G363、_G366、_G369、_G372、_G375|...]；
% 5 推理，0.000 秒内 0.000 CPU(94% CPU，294066 唇)
错误的。

?- 长度(L,100000), 时间(dcg_last(L,E))。
% 100,001 推理，0.057 秒内 0.033 CPU(58% CPU，3061609 唇)
L = [_G19, _G22, _G25, _G28, _G31, _G34, _G37, _G40, _G43|...] ;
% 2 推理，0.023 秒内 0.011 CPU(49% CPU，175 唇)
错误的。

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