Prolog Language
Begründung der Daten

Bemerkungen

Rekursion

Prolog hat keine Iteration, aber alle Iterationen können mit Rekursion neu geschrieben werden. Rekursion erscheint, wenn ein Prädikat ein Ziel enthält, das auf sich selbst verweist. Wenn Sie solche Prädikate in Prolog schreiben, besteht ein rekursives Standardmuster immer aus mindestens zwei Teilen:

• Basisklausel (nicht-rekursiv) : In der Regel stellen die Basisfallregeln die kleinstmöglichen Beispiele des Problems dar, das Sie lösen möchten - eine Liste ohne Mitglieder oder nur ein Mitglied oder, falls Sie es sind Wenn Sie mit einer Baumstruktur arbeiten, handelt es sich möglicherweise um einen leeren Baum oder um einen Baum mit nur einem Knoten usw. Es beschreibt nicht rekursiv die Basis des rekursiven Prozesses.

• Rekursive (Continuing) -Klausel : Enthält jede erforderliche Logik, einschließlich eines Aufrufs an sich selbst, Fortsetzung der Rekursion.

Als Beispiel definieren wir das bekannte Prädikat append/3 . Deklarativ betrachtet, gilt append(L1,L2,L3) wenn die Liste L3 das Ergebnis der Anfügung der Listen L1 und L2 . Wenn wir versuchen, die deklarative Bedeutung eines Prädikats herauszufinden, versuchen wir, Lösungen zu beschreiben, für die das Prädikat gilt. Die Schwierigkeit besteht hier darin, zu versuchen, schrittweise wiederkehrende Details zu vermeiden und dabei das prozessuale Verhalten des Prädikats zu berücksichtigen.

% Base case
append([],L,L).

% Recursive clause
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

Der Basisfall besagt deklarativ "jedes an die leere Liste angehängte L ist L". Beachten Sie, dass nichts darüber aussagt, dass L leer ist - oder sogar eine Liste ist (denken Sie daran, in Prolog läuft alles auf Begriffe):

?- append(X,some_term(a,b),Z).
X = [],
Z = some_term(a, b).

Um die rekursive Regel zu beschreiben, lässt Prolog zwar die Regeln von links nach rechts ausführen, wir lassen den Kopf für eine Sekunde aus und betrachten den Körper zuerst - indem wir die Regel von rechts nach links lesen:

    append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

Nun sagen wir das, wenn der Körper hält: "Vorausgesetzt, dass das append(L1,L2,L3) gilt"

    append([X|L1],L2,[X|L3]) :-  append(L1,L2,L3). 

Dann tut es auch der Kopf: "dann hängt es an append([X|L1],L2,[X|L3]) "

Im Klartext bedeutet dies einfach:

Angenommen, L3 ist die Verkettung von L1 und L2, dann ist [X, gefolgt von L3] auch die Verkettung von [X, gefolgt von L1] und L2.

In einem praktischen Beispiel:

„Angenommen, [1,2,3] ist die Verkettung von [1] und [2,3], dann ist [a, 1,2,3] auch die Verkettung von [a, 1] und [2,3]. ”

Schauen wir uns nun einige Fragen an:

Es ist immer eine gute Idee, Ihr Prädikat zunächst mit der allgemeinsten Abfrage zu testen, anstatt es mit einem bestimmten Szenario-Testfall zu versehen. Denken Sie daran: Aufgrund der Vereinigung von Prolog müssen wir keine Testdaten bereitstellen, wir geben es nur freie Variablen!

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_G1162],
L3 = [_G1162|L2] ;                          % Answer #2
L1 = [_G1162, _G1168],
L3 = [_G1162, _G1168|L2] ;                  % Answer #3
L1 = [_G1162, _G1168, _G1174],
L3 = [_G1162, _G1168, _G1174|L2] ;          % Answer #4
...

Ersetzen Sie die freie Variable _G1162 Notation durch alphabetische Buchstaben, um einen besseren Überblick zu erhalten:

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_A],
L3 = [_A|L2] ;                              % Answer #2
L1 = [_A, _B],
L3 = [_A, _B|L2] ;                          % Answer #3
L1 = [_A, _B, _C],
L3 = [_A, _B, _C|L2] ;                      % Answer #4
...

In der ersten Antwort wurde der Basisfall mit einem Muster abgeglichen, und Prolog instanziierte L1 mit der leeren Liste und vereinheitlichte L2 und L3 was beweist, dass L3 die Verkettung der leeren Liste und L2 ist.

Bei Antwort Nr. 2, durch chronologisches Backtracking, kommt die Rekursionsklausel ins Spiel und Prolog versucht zu beweisen, dass ein Element im Kopf von L1 mit L2 verkettet ist, L3 und dasselbe Element in seinem Listenkopf. Dazu wird eine neue freie Variable _A mit dem Kopf von L1 vereinheitlicht, und L3 hat sich jetzt als [_A|L2] erwiesen.

Ein neuer rekursiver Aufruf erfolgt jetzt mit L1 = [_A] . Prolog versucht noch einmal zu beweisen, dass ein Element, das sich im Kopf von L1 und mit L2 verkettet ist, L3 mit demselben Element im Kopf ist. Beachten Sie, dass _A bereits der Kopf von L1 , was perfekt mit der Regel übereinstimmt. Daher stellt Prolog nun durch Rekursion _A vor eine neue freie Variable und wir erhalten L1 = [_A,_B] und L3 = [_A,_B|L2]

Wir sehen deutlich, dass sich das rekursive Muster wiederholt, und kann leicht erkennen, dass beispielsweise das Ergebnis des 100. Schritts der Rekursion so aussehen würde:

L1 = [X1,X2,..,X99],
L3 = [X1,X2,..,X99|L2]

Anmerkung: Wie für guten Prolog-Code typisch, gibt uns die rekursive Definition von append/3 nicht nur die Möglichkeit, zu überprüfen, ob eine Liste die Verkettung von zwei anderen Listen ist, sondern generiert auch alle möglichen Antworten, die die logischen Beziehungen vollständig erfüllen oder teilweise instanziierte Listen.

Zugriff auf Listen

Mitglied

member/2 hat Unterschriftenmitglied member(?Elem, ?List) und gibt true wenn Elem Mitglied von List . Dieses Prädikat kann verwendet werden, um auf Variablen in einer Liste zuzugreifen, bei denen verschiedene Lösungen durch Backtracking abgerufen werden.

Beispielabfragen:

?- member(X, [1,2,3]).
X = 1 ;
X = 2 ;
X = 3.

?- member(X,[Y]).
X = Y.

?- member(X,Y).
Y = [X|_G969] ;
Y = [_G968, X|_G972] ;
Y = [_G968, _G971, X|_G975] ;
Y = [_G968, _G971, _G974, X|_G978]
...

Musterabgleich

Wenn die Indizes, auf die Sie zugreifen müssen, klein sind, kann der Musterabgleich eine gute Lösung sein, z.

third([_,_,X|_], X).
fourth([_,_,_,X|_], X).