Prolog DCG语法规则中的堆栈溢出：如何高效或惰性地处理大型列表

Question

Prolog DCG语法规则中的堆栈溢出：如何高效或惰性地处理大型列表

16

我正在解析一个相当简单的文件格式，它由一系列行组成，每一行都有一些用空格分隔的字段，看起来像这样：

l 0x9823 1
s 0x1111 3
l 0x1111 12
⋮

我正在使用SWI-Prolog。这是我目前的DCG：

:- consult(library(pure_input)).

load_trace(Filename, Traces) :-
    phrase_from_file(trace_file_phrase(Traces), Filename).

trace_file_phrase([]) --> [].
trace_file_phrase([T|Ts]) --> trace_phrase(T), trace_file_phrase(Ts).

trace_phrase(access(Type, Address, SinceLast)) -->
    access_type(Type), space,
    address(Address),  space,
    nat(SinceLast),    newline.

access_type(load)  --> "l".
access_type(store) --> "s".

address(Number) --> "0x", hexnum(Number).

hexdigit(N)  --> digit(N).
hexdigit(10) --> "a". hexdigit(11) --> "b". hexdigit(12) --> "c".
hexdigit(13) --> "d". hexdigit(14) --> "e". hexdigit(15) --> "f".
hexnum(N) --> hexdigit(D), hexnum(D, N).
hexnum(N, N) --> [].
hexnum(A, N) --> hexdigit(D), { A1 is A*16 + D }, hexnum(A1, N).

newline --> "\n".
space --> " ".

%% the following two productions are courtesy of Lars Mans at
%% https://dev59.com/13A75IYBdhLWcg3weY1f
digit(0) --> "0". digit(1) --> "1". digit(2) --> "2".
digit(3) --> "3". digit(4) --> "4". digit(5) --> "5".
digit(6) --> "6". digit(7) --> "7". digit(8) --> "8".
digit(9) --> "9".

nat(N)   --> digit(D), nat(D,N).
nat(N,N) --> [].
nat(A,N) --> digit(D), { A1 is A*10 + D }, nat(A1, N).

正如评论中提到的，我从在Prolog中解析具有多个数字的数字中借鉴了数字处理。

我遇到的问题是其中一些文件很大，比如5-10 MB。 SWI-Prolog中的默认堆栈不足以处理这个问题，并且解析这些文件需要相当长的时间，大约为5-15秒。我有几个关于这种情况的问题：

这段代码的效率问题在哪里？我认为可能在trace_file_phrase//1或nat//1中，但这只是猜测。
如果问题在于列表，那么是否有比这更好的处理DCG的列表的方法？
一般来说，如何诊断和处理此类DCG的性能问题？

- Daniel Lyons

3个回答

7

我已经在一个2Mb的文件上验证了stackoverflow。然后使用库(dcg/basics)重写了语法，现在它可以工作了。

:- [library(dcg/basics)].

load_trace_0(Filename, Ls) :-
    phrase_from_file(lines(Ls), Filename).

lines([s(H,I)|R]) -->
    "s 0x", xinteger(H), " ",
    integer(I), blanks,
    !, lines(R).
lines([l(H,I)|R]) -->
    "l 0x", xinteger(H), " ",
    integer(I), blanks,
    !, lines(R).
lines([]) --> [].

但是我尝试纠正了您的语法之后，它也运行良好。因此，来自@gusbro (+1) 的答案解决了您的问题。

- CapelliC

你的代码中是否使用了 dcg/basics 中的 integer/3 和 xinteger/3？我之前没有听说过这个。 - Daniel Lyons

3

好的，我会尽力进行翻译。以下是需要翻译的内容：yes, it's handy. I routinely use it to parse mySQL backup files of about 10 MB是的，它很方便。我经常使用它来解析大约10MB的MySQL备份文件。 - CapelliC

谢谢您，这非常有帮助。我希望我能将接受答案的方式分成三个！ - Daniel Lyons

4

关于效率问题：

如果您的输入通常格式良好，则我认为您应该交换nat/4和hexnum/4的子句，使它们读起来如下：

nat(A,N) --> digit(D), { A1 is A*10 + D }, nat(A1, N).
nat(N,N) --> [].

hexnum(A, N) --> hexdigit(D), { A1 is A*16 + D }, hexnum(A1, N).
hexnum(N, N) --> [].

因为你只想在没有更多数字可消耗时停止解析数字。

如果明智使用，cut（！）可以帮助您提高性能，并且可以避免堆栈溢出，因为它修剪了前缀评估树。例如，您可以在trace_file_phrase/3的结尾（即newline之后）提交（！），因为您不需要重新解析输入的该部分以查找其他解决方案。

- gusbro

我想我只是看不到应该在哪里切割以改进事物。 - Daniel Lyons

1

@DanielLyons：例如，在trace_file_phrase/3的结尾处（也就是换行符后面），你可以使用!来提交，因为你不需要重新解析输入的这部分内容以查找其他解决方案。 - gusbro

1

只有在digit//1后添加一个剪枝，这个程序才能正常工作，否则它的效率会降低，因为每次递归都会留下一个选择点。 - false

@false：我已经说过他应该使用切片，即使他不使用切片，我们也应该测量时间来看哪种方法更有效。 - gusbro

@gusbro：在digit//1之后没有切割，你的定义会为每个数字使用一个选择点。这是不允许的。Daniel Lyons的原始定义在这方面要好得多。每个数字只有一个表面上的选择点。 - false

谢谢您，仅使用换行符后的剪切操作就解决了基本问题。如果可以的话，我会接受所有三个答案！ - Daniel Lyons

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- false · Accepted Answer

作为一般性的评论，您可以在SO上找到更多关于它的内容，名称为library(pio)。此外，使用它的干净方式是：

:- use_module(library(pio)).

您的示例过于复杂，因此我只考虑一个稍微简单一些的情况，即一个由换行符分隔的数字列表：

nats([]) --> [].
nats([N|Ns]) --> nat(N), newline, nats(Ns).

那么，你如何有效地测试呢？（这是你的第三个问题）library(pio) 的基本点是，您可以使用常规的 DCG 用于文件处理。但是对于小型测试，您仍然可以使用简单的 phrase/2。所以我做了以下操作：

?- phrase(nats(Ns),"1\n").
   Ns = [1]
;  false.

你看到了 ; 提示吗？这意味着：Prolog 无法确定是否可以计算出更多答案 - 因此它留下一个或多个选择点。 只有一个数字 您可以想象事情将如何堆积。

让我们深入探讨：

?- phrase(digit(D),"1").
   D = 1
;  false.

再次出现了恶魔般的 ; false！为了使其正常工作，必须确定所有内容。有三种方法可以做到这一点：

使用 cut（失去灵魂）

祝你好运 - 最好的情况似乎是在重复元素之后：

trace_file_phrase([]) --> [].
trace_file_phrase([T|Ts]) -->
   trace_phrase(T),
   !, % 丑陋，但是……
   trace_file_phrase(Ts).

（这应该回答了问题1）

但是，请等一下！这个 ! 到底有什么问题？只要 trace_phrase//1 只有一个答案，一切都很完美。只有当有更多的答案（或实际上是解决方案）时，割掉可能会删除宝贵的答案。你怎么知道是否还有更多的解决方案？好吧，你不知道。因为它们已经被割掉了，所以你看不到它们。

`call_semidet/1`

这里有一种方法可以确保不会发生这种情况。这仅适用于无副作用的目标，可以调用两次而没有任何效果：

call_semidet(Goal) :-
   (  call_nth(Goal, 2)
   -> throw(error(mode_error(semidet,Goal),_))
   ;  once(Goal)
   ).

这里使用了call_nth/2，在另一篇文章中定义了该谓词。(作为优化，当没有选择点打开时，实现可以避免调用两次Goal...)为了清楚起见，它的工作原理如下:

?- phrase(nat(N),"1234").
   N = 1234
;  false.
?- call_semidet(phrase(nat(N),"1234")).
   N = 1234.
?- call_semidet((X=1;X=2)).
   error(mode_error(semidet, (2=1;2=2)), _).

所以它使你的小语法有效地是确定性的! 因此，没有必要重新构造任何东西!

现在缺少的是将它集成到语法中。您可以使用 library(lambda) 进行非常低水平或相当干净的集成。

phrase_semidet(NT) -->
   call(S0^S^call_semidet(phrase(NT,S0,S))).

请注意，在这种非常特殊的情况下，我们不使用 \ 进行重命名。

trace_file_phrase([]) --> [].
trace_file_phrase([T|Ts]) -->
   phrase_semidet(trace_phrase(T)),
   trace_file_phrase(Ts).

利用索引

最后，一种非常费力但干净的方法是重新编写所有内容以更好地从索引中获益（也许有助于改进索引...）但这是一条漫长的路。仅作为开始：

digit(D) --> [C],
   {c_digit(C,D)}.
c_digit(0'0,0).
c_digit(0'1,1).
c_digit(0'2,2).
c_digit(0'3,3).
c_digit(0'4,4).
c_digit(0'5,5).
c_digit(0'6,6).
c_digit(0'7,7).
c_digit(0'8,8).
c_digit(0'9,9).

这样现在就可以这样使用:

?- phrase(digit(D),"1").
   D = 1.

但是您还有另一个非确定性来源，这更多是由于您定义语法的方式。在 nat//2 中可以看到:

nat(N,N) --> [].
nat(A,N) --> digit(D), ... .

第一条规则始终适用，也就是说，"1234\n" 将被解析为 "1" "12" "123" "1234" 只有以下的 newline//0 才会意识到只需要选择最后一个 - 然后坚持选择它。

您可以对此进行重写，但是这样一来，代码就不再是您喜欢的那个纯净小规范了，是吗？嗯，也许未来会有所改善。例如，在SWI中索引要好得多，也许这里的事情也会发展...... library(pio)的意图是启动这个过程。与Haskell相比，我们在效率方面还有很长的路要走！但是没有固有成本：... -> [] | [_]，...。phrase_from_file((...，“searchstring”，...), fichier)与grep一样高效-在空间上。也就是说，它在恒定的空间内运行。因此，希望将来更多的代码能够更好地运行。编辑：顺便说一句，library(pio)已经在效率方面产生了影响：GC阶段得到了显着改进，非常类似于Wadler Fixing some space leak——一个季度前的论文。事情在发展...... 编辑近10年后：相关答案。