Переполнение стека в правиле грамматики Prolog DCG: как обрабатывать большие списки эффективно или лениво
Я разбираю довольно простой формат файла, состоящий из ряда строк, каждая строка имеет несколько полей, разделенных пробелами, который выглядит следующим образом:
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://stackru.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).
Как уже упоминалось в комментарии, я взяла обработку чисел из анализа паролей с несколькими цифрами в Прологе.
Проблема, с которой я сталкиваюсь, заключается в том, что некоторые из этих файлов имеют размер порядка 5-10 МБ. Стек по умолчанию в SWI-Prolog недостаточен для этого, и анализ этих файлов занимает значительное время, порядка 5-15 секунд. У меня есть несколько вопросов об этой ситуации:
- Где проблема эффективности в этом коде? Я думаю, что либо в
trace_file_phrase//1или жеnat//1но это только догадки - Если проблема заключается в списках, есть ли лучший способ обработки списков с помощью DCG, чем этот?
- Как вообще диагностировать и лечить проблемы производительности с DCG, такими как эта?
4 ответа
В качестве общего замечания вы найдете больше на 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]; ложный.
Вы видели ; незамедлительный? Это означает: Пролог не смог решить, могут ли быть рассчитаны дальнейшие ответы - поэтому он оставляет одну или несколько точек выбора открытыми. И это только для одной цифры. Вы можете представить, как все будет накапливаться.
Давайте копать глубже:
?- фраза (цифра (D),"1"). D = 1; ложный.
Опять зло ;! Чтобы сделать эту работу, все должно быть определенным. Есть три пути к этому:
Используйте порезы (и потеряйте свою душу)
Я желаю вам удачи - лучшее, кажется, только после повторяющегося элемента:
trace_file_phrase ([]) -> []. trace_file_phrase([T|Ts]) -> trace_phrase(Т),!, некрасиво, но... trace_file_phrase (Ts).
(Это должно ответить на вопрос 1)
Но подожди минутку! Что в этом плохого !? Пока есть только один ответ на trace_phrase//1 все идеально. Только, если есть больше ответов (или фактически решений), сокращение может удалить ценные ответы. Как узнать, есть ли еще решения? Ну, ты не. И вы их не увидите, так как они уже вырезаны.
call_semidet/1
Вот способ гарантировать, что этого не произойдет. Это работает только для целей без побочных эффектов, которые могут быть вызваны дважды без какого-либо эффекта:
call_semidet (цель):- ( call_nth(цель 2) -> throw(ошибка (mode_error(semidet,Goal),_)); один раз (цель)).
Это использует call_nth/2, как определено в другом посте. (В качестве оптимизации реализация может избежать вызова Goal дважды, когда нет открытой точки выбора...) Просто чтобы прояснить, как это работает:
?- фраза (nat(N),"1234"). N = 1234; ложный. ?- call_semidet (фраза (nat (N), "1234")). N = 1234. ?- call_semidet ((X = 1; X = 2)). ОШИБКА: неизвестный термин ошибки: mode_error(semidet, (2=1;2=2))
Так что это делает вашу маленькую грамматику эффективным определением! Таким образом, нет необходимости переформулировать что-либо!
Чего сейчас не хватает, так это некоторой интеграции этого в грамматику. Вы можете сделать это очень низкоуровнево, или, вернее, чисто используя library(lambda),
фраза_семид (NT) -> вызов (S0^S^call_semidet(фраза (NT,S0,S))).
Обратите внимание, что в этом конкретном случае мы не используем \ для переименования.
trace_file_phrase ([]) -> []. trace_file_phrase([T|Ts]) -> phrase_semidet(trace_phrase(Т)), trace_file_phrase (Ts).
Эксплойт индексация
Наконец, очень трудоемким, но чистым способом было бы переписать все, чтобы получить лучшую прибыль от индексации (и, возможно, помочь улучшить индексацию в целом...) Но это долгий путь. Просто для начала:
цифра (D) -> [C],
{C_digit (С, 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) -> цифра (D), ... .
Первое правило всегда применяется, то есть "1234\n" будет проанализирован как "1""12" "123""1234" только следующее newline//0 понимает, что этого было бы достаточно, пойти на последнее - и затем придерживаться его.
Вы можете переписать вещи для этого, но тогда код больше не является чистой маленькой спецификацией, которая вам понравилась, не так ли? Ну, может, в будущем все может улучшиться.
Например, индексирование в SWI намного лучше, чем раньше, может быть, здесь тоже что-то развивается...
Намерение library(pio) должен был начать этот процесс. Сравните это с Haskell - мы далеко от interact эффективность-накрест! Но нет никакой внутренней стоимости:
... -> [] | [_], ... ?- фраза_от_файла ((...,"строка поиска",...), более высокая).
так же эффективен, как grep - в пространстве. То есть он работает в постоянном пространстве. Надеемся, что в будущем больше кода будет работать лучше.
Редактировать: Кстати, library(pio) уже имел влияние на эффективность воздействия: фазы ГХ были значительно улучшены, во многом таким же образом, как и Уодлера. Устранение некоторой утечки пространства - бумага четверть века назад. Вещи развиваются...
Я проверил переполнение стека в файле 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) решает вашу проблему.
О проблеме эффективности:
Если ваш вклад обычно хорошо сформирован, то я думаю, что вы должны поменять местами 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) потому что вам не нужно повторно анализировать эту часть ввода, чтобы найти другие решения.
Стандартный совет в YACC - сделать производство рекурсивным, чтобы избежать переполнения стека.
Преобразование в Пролог, говорит
trace_file_phrase([Ts|T]) --> trace_file_phrase(Ts), trace_phrase(T).