Prolog DCG:找到最后一个元素

问题描述

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

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

最后 --> [X|[]].

其中 X 是最后一个元素.如何让 Prolog 递归地在列表中?还是我对 DCG 的看法有误?

解决方案

... -->[] |[_], ... .list_last(Xs, X) :-短语((...,[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 个子句真的.?- [用户].**省略**?- 清单.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.:- 易失性 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.

I am trying to understand the use of DCGs better. In order to do this, I tried to translate some exercises in the LearnPrologNow book to DCG notation. However, I am failing miserably.

What I tried to write a program that simply names the last element in a list. That's all. I just can't think of the right DCG syntax to do this. I think I figured out the 'base case' which should be:

Where X is the last element. How do I make Prolog go down the list recursively? Or am I thinking about DCGs in a wrong way?

解决方案

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

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

This is clearly the most "graphical" definition. You can describe a lot of patterns with ... //0.

Grammars are a way to describe a language. So your question about how to make Prolog go down is malposed. Grammars don't do anything. They if you insist "generate" sentences.

For the procedural details, you need to understand termination, but no more than that.

Edit: And if you really care about performance, then measure it first. With SWI, I obtain the following. Note the usage of an extra library to remove the calling overheads for 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.

So both are performing roughly the same number of inferences, but dcg_last/2 is slower, since it has to pile up all those useless choicepoints. list_last/2 creates the same number of choice-points, however, they are almost immediately removed. So we have 0.018s vs. 0.033s+0.011s.

这篇关于Prolog DCG:找到最后一个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！