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秒.关于这种情况,我有几个问题:

1. 这段代码中的效率问题在哪里？我认为它或者是trace_file_phrase//1或者nat//1这些只是预感.
2. 如果问题是列表,是否有更好的方法来处理带有DCG的列表？
3. 一般来说,如何诊断和处理DCG这样的性能问题？

Answer 1

作为一般性评论,您将在名称下找到关于它的更多信息library(pio).另外,干净利用它的方式是:

:- use_module(library(pio)).

你的例子过于复杂,所以我只考虑一个稍微简单的案例,换行符分隔的数字列表:

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

那么,你怎么能有效地测试呢？(这是你的问题3)基本点library(pio)是你可以使用常规DCG进行文件处理.但是对于小型测试,您仍然可以使用简单的phrase/2.所以我这样做:

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

你看到;提示了吗？这意味着:Prolog无法决定是否可以计算进一步的答案 - 因此它会打开一个或多个选择点.而这只是一个数字你可以想象事情会如何堆积.

让我们深入挖掘:

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

邪恶再次;!为了使这项工作,一切都必须确定.有三种方法:

使用削减(并失去你的灵魂)

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

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(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: Unknown error term: 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相比 - 我们远离interact效率方面!但没有固有的成本:

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

?- phrase_from_file((...,"searchstring",...),fichier).

和grep一样有效 - 空间方面.也就是说,它在恒定的空间中运行.所以希望将来会有更多代码运行得更好.

编辑:顺便说一句,library(pio)确实已经产生了影响效率:GC阶段得到了显着改善,与瓦德勒修复一些空间泄漏的方式非常相似 - 四分之一世纪前.事情在发展......

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)结束时commit(),因为您不需要再次重新分析输入的那部分以找到其他解决方案.