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

Question

我正在解析一个由一系列行组成的相当简单的文件格式，每行都有一些用空格分隔的字段，看起来像这样：l 0x9823 1s 0x1111 3l 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-prologdigit(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）提交（），因为您无需再次重新解析输入的那部分来查找其他解决方案。