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).

正如评论中提到的那样，我在解析Prolog中具有多个数字的数字处理中总结了数字处理。

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

该代码中的效率问题在哪里？我认为它要么存在，trace_file_phrase//1要么nat//1只是预感。

如果问题是列表，那么有没有比DCG更好的方法来处理列表了？

通常，如何使用DCG诊断和处理诸如此类的性能问题？

Answer 1

通常，您可以在的名称下找到更多关于SO的信息library(pio)。同样，干净地使用它的方法是：:- 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（semidet，Goal），_））   ; 一次（目标）   ）。这使用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效率还差得远！但是没有固有的成本：...-> [] | [_]，...。？ -  phrase_from_file（（...， “搜索字符串”，...），fichier）。与grep一样高效-在空间方面。也就是说，它在恒定的空间中运行。因此，希望将来会有更多的代码运行得更好。编辑：顺便说一句，library(pio)确实已经在影响效率方面有所改进：GC阶段得到了显着改善，与25年前Wadler的“修复一些空间泄漏”的方法非常相似。事情发展...

Answer 2

我已经验证了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）的答案解决了您的问题。

Answer 3

关于效率问题：如果输入通常是良好的，那么我认为你应该换的条款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（!）可以帮助您提高性能，并可以解决堆栈溢出问题，因为它会修剪prolog评估树。例如，您可以在（!）trace_file_phrase/3之后（即，之后newline）提交（），因为您无需再次重新解析输入的那部分来查找其他解决方案。