Es gibt mehrere Probleme. Hier sind die offensichtlichsten:
Typisierung. Ihr Prädikat re_contains/2
erwartet eine Liste als zweites Argument. Dass re_contains(a,a).
gelingt, ist eher Zufall als Absicht.
Monotonie. Ein weiteres Problem ist, dass re_contains([a],[a])
erfolgreich ist, aber re_contains([X],[a])
schlägt fehl. Oder, um es aus einem anderen Blickwinkel zu sehen: re_contains([X],[a])
schlägt fehl, aber X = a, re_contains([X],[a])
gelingt. Durch das Hinzufügen des Ziels X = a
haben wir die Abfrage so spezialisiert, dass die ursprünglich fehlerhafte Abfrage erneut fehlschlagen sollte.
Die Prüfung auf Identität (==/2
) sollte durch Gleichheit (=/2
) und ersetzt werden, die sicherstellen, dass wir eine Liste haben. Also:
re_contains(X, L) :-
% X == L.
X = L,
append(X,_,_).
Hinweis ist, dass append/3
hier nur verwendet, dass X, um sicherzustellen, ist eine Liste - die tatsächliche Anfügen Funktionalität nicht verwendet wird.
Effizienz. Das dritte Problem betrifft die tatsächliche Art und Weise, wie Sie die Verkettung darstellen. Schauen wir uns nur an die folgende Regel:
re_contains(seq(X, Y), L) :-
append(L1, L2, L),
re_contains(X, L1),
re_contains(Y, L2).
Es sei nun angenommen, dass wir hier eine Liste der Länge N
haben. Wie viele Antworten sind für das Ziel append(L1, L2, L)
möglich? Eigentlich N + 1
. Und dies unabhängig von den tatsächlichen Werten.Betrachten wir nun:
?- 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
Bedürfnisse hier Zeit proportional zur Länge der Liste. Aber es würde ausreichen, das erste Element zu betrachten, um zu erkennen, dass dies unmöglich ist.
Also das Problem ist die Verwendung von append/3
. Es gibt eine einfache Faustregel für Prolog: Wenn Sie zu viel append/3
verwenden, verwenden Sie dcg s — Definite Clause Grammars. Bitte schauen Sie in das Tag für weitere Details — und konsultieren Sie einen einleitenden Prolog Text. Um Ihnen einen Start zu geben, hier ist ein Teil Ihrer Definition:
re_contains(RE, L) :-
phrase(re(RE), L).
re([]) --> [].
re([E]) --> [E].
re(seq(X,Y)) -->
re(X),
re(Y).
, die nicht mehr die gesamte Liste nicht untersuchen:
?- 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 ist eine vollständige Definition.
Terminierung/Nicht-Terminierung. In Bezug auf Effizienz ist die Eigenschaft der Kündigung. Im Idealfall endet eine Abfrage, wenn die Menge der Lösungen endlich dargestellt werden kann. Das heißt, durch eine endliche Anzahl von Antworten. OK, das ist das Ideal, nach dem wir streben. Prologs einfacher aber sehr effizienter Ausführungsalgorithmus wird manchmal eine Schleife bilden, wenn eine endliche Anzahl von Antworten möglich gewesen wäre. Das Verständnis des Grundes der Nicht-Kündigung ist manchmal sehr schwierig. Die üblichen Debugging-Strategien – wie Tracen oder Durchlaufen mit einem Debugger – funktionieren nicht, da sie Ihnen viel zu viele Details zeigen. Zum Glück gibt es eine bessere Technik:
Anstatt auf Ihr gesamtes Programm zu schauen, werde ich wieder nur ein sehr kleines Fragment davon betrachten. Dieses Fragment ist ein failure slice (siehe den Link für weitere Details). Es ist viel kleiner, sagt aber eine Menge über das ursprüngliche Programm — vorausgesetzt, dass ein reines, monotones Programm war:
Wenn ein Fehler-Slice nicht beendet wird, dann wird das ursprüngliche Programm nicht beendet.
Wenn wir also eine solche Fehlerscheibe finden, können wir sofort Rückschlüsse auf das gesamte Programm ziehen. Ohne den Rest zu lesen!
Hier ist so eine interessante Ausfall Scheibe:
...
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).
...
Betrachten wir nun das Ziel re_contains(seq([],[]),L).
Idealerweise sollte es genau eine Antwort L = []
und das Ziel beenden sollte. Es koppelt jedoch, da append(L1, L2, L)
nicht beendet wird. Vergleichen Sie dies mit der obigen DCG-Lösung, die für phrase(re(seq([],[])),L)
endet.
're_contains' funktioniert mit Sequenzen. C.f. 're_contains ([a], [a])'. – false
sicher, aber das OP verwendet keine Listen, um den regulären Ausdruck darzustellen. Ich habe vorgeschlagen, solche Diskrepanzen zu beseitigen. – CapelliC
Die Tatsache, dass es "re_contains (X, L): - X == L." gibt, deutet darauf hin, dass Listen gemeint sind. – false