Corrispondenza delle espressioni regolari Prolog

Question

Sto tentando di eseguire la corrispondenza delle espressioni regolari. Ho tutte le funzioni scritte, ma non funzionano come dovrebbero. Da quello che posso dire, ha un problema quando provo a confrontare una lista.
Ad esempio, "re_taintains (a, a)." dà vero (ovviamente), così come "re_contenitori (unione (a, b), a)."

Ma non appena ne faccio una lista, fallisce. "re_taintains (seq (a, b), [a, b])." restituisce falso. Append dovrebbe passare attraverso tutte le combinazioni possibili per trovare la corrispondenza, ma nessuna di queste funzioni funziona correttamente. Questo mi rende cosa che forse mi manca un caso base. Ma penso "re_contains (X, L): - X == L." dovrebbe prendersene cura Devo essere sopra guardando qualcosa di importante qui.

Ecco il mio codice:

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 si dividerà L, ed entrambi L1 e L2 saranno liste.

vorrei provare a sostituire re_contains(X, L) :- X == L. con re_contains(X, [X]).

Dopo il cambio, re_contains(a,a). avrà esito negativo.

Si sta rappresentando la sequenza in diversi modi, e il tuo matcher non prevede per entrambi. In realtà, gli unici casi "funzionanti" sono le sequenze non.

Answer 2

Ci sono diversi problemi. Ecco le più ovvie:

Digitazione. Il predicato re_contains/2 prevede un secondo argomento come elenco. Il successo di re_contains(a,a). è piuttosto una coincidenza che l'intenzione.

Monotonicità. Un altro problema è che re_contains([a],[a]) ha esito positivo, ma l'errore re_contains([X],[a]) non riesce. Oppure, per vederlo da un'altra angolazione: re_contains([X],[a]) non riesce, ma X = a, re_contains([X],[a]) ha esito positivo. Aggiungendo l'obiettivo X = a abbiamo specializzato la query, quindi la query originariamente fallita dovrebbe fallire di nuovo.

Il test per l'identità (==/2) dovrebbero essere sostituiti da uguaglianza (=/2) e garantire che abbiamo qualche lista. Quindi:

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

nota, che append/3 è qui utilizzato solo per garantire che X è una lista - l'effettiva funzionalità apposizione non viene utilizzato.

Efficienza. Il terzo problema riguarda il modo effettivo di rappresentare la concatenazione. Diciamo solo un'occhiata alla seguente regola:

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

Ora, pensare che abbiamo qui una lista di lunghezza N. Quante risposte sono possibili per l'obiettivo append(L1, L2, L)? In realtà N + 1. E questo, indipendentemente dai valori reali coinvolti.Consideriamo ora:

?- 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 esigenze Qui il tempo proporzionale alla lunghezza della lista. Ma sarebbe sufficiente guardare il primo elemento per capire che questo è impossibile.

Quindi il problema è l'uso di append/3. Per Prolog esiste una semplice regola empirica: se si utilizza troppo append/3, è consigliabile utilizzare dcg s Grammars clausole definite —. Si prega di guardare nel tag per ulteriori dettagli — e consultare un testo introduttivo Prolog. Per darvi un inizio, qui è un sottoinsieme della definizione:

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

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

Il che non più indagare l'intero elenco:

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

BTW, here è una definizione completa.

Terminazione/non-terminazione. In relazione all'efficienza è la proprietà della risoluzione. Idealmente, una query termina se l'insieme di soluzioni può essere rappresentato in modo preciso. Cioè, da un numero finito di risposte. OK, questo è l'ideale per cui ci stiamo battendo. L'algoritmo di esecuzione semplice ma molto efficiente di Prolog a volte si interrompe, quando sarebbe stato possibile un numero finito di risposte. Capire la vera ragione della non-terminazione è a volte molto difficile. Le solite strategie di debug – come la traccia o l'esecuzione di un debugger – non funzionano poiché mostrano troppi dettagli. Fortunatamente, c'è una tecnica migliore:

Invece di guardare l'intero programma, guarderò di nuovo solo un frammento molto piccolo di esso. Questo frammento è un failure slice (vedi il link per maggiori dettagli). È molto più piccolo ma parla molto del programma originale — purché fosse un programma puro e monotono:

Se una sezione di errore non termina, il programma originale non termina.

Quindi, se troviamo una tale fetta di fallimento, possiamo trarre conclusioni immediate sull'intero programma. Senza nemmeno leggere il resto!

Ecco un così interessante fetta di fallimento:

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

consideri ora l'obiettivo re_contains(seq([],[]),L). Idealmente, ci dovrebbe essere esattamente una risposta L = [] e l'obiettivo dovrebbe terminare. Tuttavia, lo loop, dal momento che append(L1, L2, L) non termina. Confrontalo con la soluzione DCG sopra la quale termina per phrase(re(seq([],[])),L).