Переполнение стека в правиле грамматики Prolog DCG: как эффективно или лениво обрабатывать большие списки

Ответ 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 понимает, что достаточно будет для last — и затем придерживаться его.

Вы можете переписать что-то для этого, но тогда код больше не является чистым маленьким спектром, который вам понравился, не так ли? Возможно, в будущем это может измениться.

например. индексирование в SWI намного лучше, чем раньше, возможно, здесь тоже развиваются вещи....

Цель library(pio) заключалась в том, чтобы запустить этот процесс. Сравните это с Haskell — мы далеки от interact эффективности! Но нет присущей стоимости:

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

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

так же эффективен, как grep — пространство-накрест. То есть, он работает в постоянном пространстве. Поэтому, надеюсь, в будущем будет больше работать код.

Edit: BTW, library(pio) уже имеет эффективность воздействия: фазы GC были значительно улучшены, очень точно так же, как Wadler. Устранение некоторых утечек пространства; ndash; бумага четверть века назад. Вещи развиваются...

Ответ 2

Я проверил stackoverflow в файле 2Mb. Затем я переписал грамматику с помощью библиотеки (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) решает вашу проблему.

Ответ 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) --> [].

потому что вы хотите прекратить синтаксический анализ числа, когда больше нет цифр.

Если использовать разумно, разрез (!) может помочь вам с точки зрения производительности, а также в отношении, поскольку он обрезает дерево оценки пролога. Например, вы можете зафиксировать (!) в конце trace_file_phrase/3 (то есть, после newline), потому что вам не нужно снова повторять эту часть ввода, чтобы найти другие решения.