Regular Expression Matching Prolog

Question

Estoy tratando de hacer coincidencia de expresiones regulares. Tengo todas las funciones escritas, pero no funcionan como deberían. Por lo que puedo decir, tiene un problema cuando trato de comparar una lista.
Por ejemplo, "re_contains (a, a)." da verdadero (obviamente), al igual que "re_contains (union (a, b), a)."

Pero tan pronto como lo hago una lista, falla. "re_contains (seq (a, b), [a, b])". devuelve falso. Append debería pasar por todas las combinaciones posibles para encontrar la coincidencia, pero ninguna de estas funciones funciona correctamente. Esto me hace pensar que tal vez me falta un caso base. Pero creo que "re_contains (X, L): - X == L." debería encargarse de eso Debo estar mirando algo importante aquí.

Aquí está mi código:

re_contains(empty, []). 

re_contains(X, L) :- 
    X == L. 

re_contains(seq(X, Y), L) :- 
    append(L1, L2, L), 
    re_contains(X, L1), 
    re_contains(Y, L2). 

re_contains(union(X, _), L) :- 
    re_contains(X, L). 

re_contains(union(_, Y), L) :- 
    re_contains(Y, L). 

re_contains(kleene(X), L) :- 
    append([Car|L1], L2, L), 
    re_contains(X, [Car|L1]), 
    re_contains(kleene(X), L2). 

re_contains(kleene(_),[]). 

Answer 1

append/3 dividirá L, y ambos L1 y L2 estarán listas.

me gustaría tratar de sustituir re_contains(X, L) :- X == L. con re_contains(X, [X]).

Después del cambio, re_contains(a,a). se producirá un error.

Está representando la secuencia de diferentes maneras, y su emparejador no proporciona ambas. En realidad, los únicos casos que funcionan son y no las secuencias.

Answer 2

Hay varios problemas. Aquí están los más obvios:

Escribiendo. Su predicado re_contains/2 espera una lista como segundo argumento. Que re_contains(a,a). tenga éxito es más bien una coincidencia que una intención.

Monotonicidad. Otro problema es que re_contains([a],[a]) tiene éxito, pero re_contains([X],[a]) falla. O bien, para verlo desde otro ángulo: re_contains([X],[a]) falla, pero X = a, re_contains([X],[a]) tiene éxito. Al agregar el objetivo X = a, hemos especializado la consulta, por lo que la consulta que falló originalmente debería fallar nuevamente.

La prueba de la identidad (==/2) debe sustituirse por la igualdad (=/2) y asegurar que tenemos una lista. Por lo tanto:

 
re_contains(X, L) :- 
    % X == L. 
    X = L, 
    append(X,_,_). 

Nota, que append/3 se utiliza aquí sólo para asegurar que X es una lista - Anexión de la funcionalidad real no se utiliza.

Eficiencia. El tercer problema tiene que ver con la forma real en que se representa la concatenación. Vamos a ver en la siguiente regla:

 
re_contains(seq(X, Y), L) :- 
    append(L1, L2, L), 
    re_contains(X, L1), 
    re_contains(Y, L2). 

Ahora, supongamos que tenemos aquí una lista de longitud N. ¿Cuántas respuestas son posibles para el objetivo append(L1, L2, L)? En realidad, N + 1. Y esto, independientemente de los valores reales involucrados.Consideremos ahora:

?- length(L,1000000), time(re_contains(seq([a],[]),[b|L])). 
% 2,000,005 inferences, 0.886 CPU in 0.890 seconds (100% CPU, 2258604 Lips) 
false. 

re_contains/2 necesidades Aquí el tiempo proporcional a la longitud de la lista. Pero bastaría con mirar el primer elemento para darse cuenta de que esto es imposible.

El problema detrás es el uso de append/3. Hay una regla básica simple para Prolog: si está usando demasiado append/3 considere usar dcg s — Gramática de cláusula definida. Consulte la etiqueta para obtener más detalles — y consulte un texto introductorio de Prolog. Para darle un nuevo comienzo, aquí es un subconjunto de su definición:

 
re_contains(RE, L) :- 
    phrase(re(RE), L). 

re([]) --> []. 
re([E]) --> [E]. 
re(seq(X,Y)) --> 
    re(X), 
    re(Y). 

Lo cual ya no se investigue toda la lista:

 
?- length(L,1000000), time(phrase(re(seq([a],[])),[b|L])). 
% 6 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 127313 Lips) 
false. 

Por cierto, here es una definición completa.

Terminación/no terminación. Relacionado con la eficiencia es propiedad de la terminación. Idealmente, una consulta termina, si el conjunto de soluciones puede representarse finitamente. Es decir, por un número finito de respuestas. OK, ese es el ideal por el que estamos luchando. El algoritmo de ejecución simple pero muy eficiente de Prolog algunas veces repetirá, cuando un número finito de respuestas hubiera sido posible. Comprender la verdadera razón de la no terminación es a veces muy complicado. Las estrategias habituales de depuración – como trazar o avanzar con un depurador – no funcionan, ya que muestran demasiados detalles. Afortunadamente, hay una técnica mejor:

En lugar de mirar todo el programa, volveré a mirar solo un fragmento muy pequeño. Este fragmento es failure slice (ver el enlace para más detalles). Es mucho más pequeño pero cuenta bastante sobre el programa original —, siempre que fuera un programa puro y monótono:

Si un segmento de falla no finaliza, el programa original no finaliza.

De modo que si encontramos una porción de falla de este tipo, podemos sacar conclusiones inmediatas sobre el programa completo. ¡Sin siquiera leer el resto!

Aquí es una rebanada fracaso interesante como:

 
... 
re_contains(X, L) :- false, 
    X = L 
re_contains(seq(X, Y), L) :- 
    append(L1, L2, L), false, 
    re_contains(X, L1), 
    re_contains(Y, L2). 
re_contains(union(X, _), L) :- false, 
    re_contains(X, L). 
... 

Consideremos ahora el objetivo re_contains(seq([],[]),L). Idealmente, debe haber exactamente una respuesta L = [] y el objetivo debe terminar. Sin embargo, se repite, ya que append(L1, L2, L) no finaliza. Contraste esto a la solución DCG arriba que termina para phrase(re(seq([],[])),L).