programacion - prolog ejemplos sencillos

Desbordamiento de pila en la regla de gramática de Prolog DCG: cómo manejar grandes listas de manera eficiente o perezosa

Question

Estoy analizando un formato de archivo bastante simple que consiste en una serie de líneas, cada línea tiene algunos campos separados por espacios, que se ve así:

l 0x9823 1
s 0x1111 3
l 0x1111 12
⋮

Estoy usando SWI-Prolog. Este es el DCG que tengo hasta ahora:

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

Como mencioné en el comentario, comprimí el manejo de números de los números de análisis con múltiples dígitos en Prolog .

El problema con el que me estoy metiendo es que algunos de estos archivos son grandes, del orden de 5-10 MB. La pila predeterminada en SWI-Prolog es insuficiente para esto, y el análisis de estos archivos lleva bastante tiempo, del orden de 5-15 segundos. Tengo varias preguntas sobre esta situación:

1. ¿Dónde está el problema de eficiencia en este código? Creo que está en trace_file_phrase//1 o nat//1 pero estos son solo corazonadas.
2. Si el problema son las listas, ¿hay una mejor manera de manejar listas con los DCG que con esto?
3. ¿Cómo puede uno, en general, diagnosticar y tratar los problemas de rendimiento con los DCG como este?

Answer 1

Sobre el problema de eficiencia:

Si su entrada normalmente está bien formada, entonces creo que debería cambiar las cláusulas de nat/4 y hexnum/4 , para que lean:

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

porque solo quiere dejar de analizar un número cuando no hay más dígitos para consumir.

Si se usa con prudencia, el corte ( ! ) Puede ayudarlo en el rendimiento y también en relación con el desbordamiento de la pila, ya que poda el árbol de evaluación de prólogos. Por ejemplo, puede confirmar ( ! ) Al final de trace_file_phrase/3 (es decir, después de la newline ) porque no necesita volver a analizar esa parte de la entrada para encontrar otras soluciones.

Answer 2

Verifiqué el en un archivo de 2Mb. Luego reescribí la gramática usando la biblioteca (dcg / basics), y ahora está funcionando.

:- [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([]) --> [].

Pero luego traté de ponerle un límite a tu gramática y también estoy trabajando. Entonces, la respuesta de @gusbro (+1) resuelve tu problema.

Answer 3

Como observación general, encontrará más información al respecto en la library(pio) nombres library(pio) . También la forma de usarlo limpiamente es más bien:

:- use_module(library(pio)).

Su ejemplo es demasiado complejo, por lo que solo consideraré un caso un poco más simple, una lista de números separada por una nueva línea:

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

Entonces, ¿cómo puedes probar esto de manera efectiva? (Esa es su pregunta 3) El punto básico de la library(pio) es que puede usar DCG regulares para el procesamiento de archivos. Pero para probar en pequeño, puede usar la phrase/2 simple phrase/2 . Así que hago:

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

Viste el ; ¿rápido? Eso significa que: Prolog no pudo decidir si se pueden calcular más respuestas, por lo que deja uno o más puntos de elección abiertos. Y eso solo por un solo dígito. Puedes imaginar cómo se acumularán las cosas.

Profundicemos:

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

Otra vez el mal ; ! Para hacer que esto funcione, todo debería ser determinado. Hay tres formas de esto:

Usa cortes (y pierde tu alma)

Te deseo suerte: lo mejor parece ser justo después del elemento repetitivo:

trace_file_phrase([]) --> []. trace_file_phrase([T|Ts]) --> trace_phrase(T), !, % ugly, but... trace_file_phrase(Ts).

(Esto debería responder a la Pregunta 1)

Pero, espera un minuto! ¿Qué tiene de malo esto ! ? Siempre y cuando haya exactamente una respuesta para trace_phrase//1 cosas son perfectas. Solo si hay más respuestas (o soluciones reales), es posible que el corte elimine respuestas valiosas. ¿Cómo sabes si hay más soluciones? Bueno, tu no. Y no los verás ya que ya han sido cortados.

call_semidet/1

Aquí hay una manera de asegurarse de que esto no suceda. Esto funciona solo para objetivos libres de efectos secundarios que pueden invocarse dos veces sin ningún efecto:

call_semidet(Goal) :- ( call_nth(Goal, 2) -> throw(error(mode_error(semidet,Goal),_)) ; once(Goal) ).

Esto usa call_nth/2 , como se define en otra publicación. (Como una optimización, la implementación podría evitar llamar a Goal dos veces cuando no hay un punto de elección abierto ...) Solo para aclarar cómo funciona:

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

¡De modo que hace que tu pequeña gramática esté efectivamente determinada! ¡Por lo tanto, no hay necesidad de reformular nada!

Lo que falta ahora es alguna integración de esto en la gramática. Puedes hacer esto de muy bajo nivel, o más bien usando limpiamente la library(lambda) .

phrase_semidet(NT) --> call(S0^S^call_semidet(phrase(NT,S0,S))).

Tenga en cuenta que en este caso tan particular no usamos el / para cambiar el nombre.

trace_file_phrase([]) --> []. trace_file_phrase([T|Ts]) --> phrase_semidet(trace_phrase(T)), trace_file_phrase(Ts).

Exploit indexación

Finalmente, una forma muy laboriosa pero limpia sería reescribir todo para sacar provecho de la indexación (y tal vez ayudar a mejorar la indexación en general ...) Pero este es un largo camino. Solo para comenzar:

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

Esto te da ahora:

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

Pero tienes otra fuente de no determinismo que se debe más bien a la forma en que defines la gramática. En nat//2 lo ves:

nat(N,N) --> []. nat(A,N) --> digit(D), ... .

La primera regla siempre se aplica, es decir, "1234/n" se analizará como "1" "12" "123" "1234" solo la siguiente newline//0 da cuenta de que sería suficiente para el último - y luego se pegará lo.

Puedes reescribir cosas para eso, pero luego, el código ya no es la pequeña especificación pura que te gusta, ¿no? Bueno, tal vez las cosas podrían mejorar en el futuro.

Por ejemplo, la indexación es mucho mejor en SWI de lo que solía ser, tal vez también las cosas evolucionen aquí también ...

La intención de la library(pio) era iniciar este proceso. Compare esto con Haskell: ¡estamos muy lejos de interact eficientemente! Pero no hay un costo inherente :

... --> [] | [_], ... . ?- phrase_from_file((...,"searchstring",...),fichier).

es tan eficiente como grep - en cuanto al espacio. Es decir, se ejecuta en un espacio constante. Así que espero que más código funcione mejor en el futuro.

Edit: BTW, library(pio) ya tenía un impacto en términos de eficiencia: las fases de GC se mejoraron significativamente, en gran medida de la misma manera que Widler''s Fixing, una fuga de espacio, hace un cuarto de siglo. Las cosas evolucionan ...