prolog - Prolog DCG语法规则中的堆栈溢出:如何有效或延迟地处理大型列表

Question

我正在解析一种由一系列行组成的相当简单的文件格式，每行都有一些用空格分隔的字段，如下所示：

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://stackoverflow.com/questions/3279822/parsing-numbers-with-multiple-digits-in-prolog
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).

如评论中所述，我从Parsing numbers with multiple digits in Prolog抄袭了数字处理。

我遇到的问题是其中一些文件很大，大约5-10 MB。 SWI-Prolog中的默认堆栈不足以解决此问题，并且解析这些文件需要大量时间，大约需要5-15秒。我对此情况有几个疑问：


该代码中的效率问题在哪里？我认为它位于trace_file_phrase//1或nat//1中，但这只是预感。
如果问题是列表，有没有比DCG更好的方法来处理列表了？
一般来说，如何使用DCG诊断和处理诸如此类的性能问题？

Answer 1

通常，您可以在library(pio)名称下找到有关SO的更多信息。同样，干净地使用它的方法是：

:- use_module(library(pio)).

您的示例太复杂了，因此我将只考虑一个稍微简单一点的情况，即用换行符分隔的数字列表：

nats（[]）-> []。
nats（[N | Ns]）-> nat（N），换行符，nats（Ns）。


那么，如何才能有效地进行测试？ （这是您的问题3）library(pio)的基本要点是，您可以使用常规DCG进行文件处理。但是对于小型测试，您仍然可以使用简单的phrase/2。所以我做：

？-短语（nats（Ns），“ 1 \ n”）。
Ns = [1]；
假。


您看到;提示了吗？这意味着：Prolog无法决定是否可以计算出进一步的答案-因此它留下了一个或多个选择点。而且那仅是个位数，您可以想象事情将如何堆积。

让我们深入探讨：

？-短语（数字（D），“ 1”）。
D = 1;
假。


再次是邪恶的;！为了使这项工作，必须确定一切。有以下三种方法：

使用削减（并失去你的灵魂）

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

trace_file_phrase（[]）-> []。
trace_file_phrase（[T | Ts]）->
trace_phrase（T），
！，％ugly，but ...
trace_file_phrase（Ts）。


（这应该回答问题1）

但是，等一下！ !有什么不好的呢？只要对trace_phrase//1有一个正确的答案，事情就完美了。只有在有更多答案（或实际上是解决方案）的情况下，削减才可能删除宝贵的答案。您如何知道是否还有更多解决方案？好吧，你没有。而且您将不会看到它们，因为它们已经被切除了。

call_semidet/1

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

call_semidet（目标）：-
（call_nth（目标，2）
->抛出（错误（mode_error（塞米德，目标），_））
;一次（目标）
）。


它使用call_nth/2，如另一篇文章中所定义。 （作为一种优化，该实现可以避免在没有选择点打开的情况下避免调用Goal两次...）只是要弄清楚它是如何工作的：

？-短语（nat（N），“ 1234”）。
N = 1234；
假。

？-call_semidet（phrase（nat（N），“ 1234”））。
N = 1234。

？-call_semidet（（X = 1; X = 2））。
错误：未知错误术语：mode_error（semidet，（2 = 1; 2 = 2））


因此，它可以有效确定您的小语法！因此，无需重新构造任何内容！

现在缺少的是将其整合到语法中。您可以非常低级地执行此操作，或者可以使用library(lambda)干净地执行此操作。

statement_semidet（NT）->
call（S0 ^ S ^ call_semidet（phrase（NT，S0，S）））。


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

trace_file_phrase（[]）-> []。
trace_file_phrase（[T | Ts]）->
statement_semidet（trace_phrase（T）），
trace_file_phrase（Ts）。


利用索引

最后，一种非常费力但干净的方法是重写所有内容，以便从索引中更好地获利（也许可以总体上改善索引...），但这是一条漫长的路。刚开始：

位数（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）。


现在，您可以：

？-短语（数字（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进行比较-我们距离interact效率方面相去甚远！但是没有固有的成本：

...-> [] | [_]，...。

？-短语来自文件（（...，“搜索字符串”，...），文件）。


与grep一样高效-在空间方面。也就是说，它在恒定的空间中运行。因此，希望将来会有更多的代码运行得更好。

编辑：顺便说一句，library(pio)确实已经对影响效率产生了影响：GC阶段得到了显着改善，这与Wadler修复空间泄漏的方法非常相似-25年前就已发表。事情在发展...