Prolog Language
Differenzlisten
Suche…
Einführung
Differenzlisten in Prolog bezeichnet das Konzept, um die Struktur einer Liste bis zu einem bestimmten Punkt zu kennen . Der Rest der Liste kann bis zur vollständigen Bewertung eines Prädikats ungebunden bleiben. Eine Liste, deren Ende unbekannt ist, wird als offene Liste bezeichnet , die durch ein Loch beendet wird. Diese Technik ist besonders nützlich, um komplexe Syntaxen oder Grammatiken zu überprüfen.
Die bekannten Definite-Clause-Grammatiken (DCG) verwenden Differenzlisten, um unter der Haube zu arbeiten.
Grundlegende Verwendung
Betrachten wir das Prädikat sumDif/2 , das überprüft wurde, wenn die Struktur einer Liste mehreren Einschränkungen entspricht. Der erste Begriff stellt die zu analysierende Liste dar und der zweite Begriff eine andere Liste, die den Teil der ersten Liste enthält, der unseren Einschränkungen nicht bekannt ist.
Für die Demonstration erkennt sumDif/2 einen arithmetischen Ausdruck, um n Ganzzahlen zu summieren.
sumDif([X, +|OpenList], Hole) :-
integer(X),
sumDif(OpenList, Hole).
Wir wissen, dass das erste zu validierende Element der Liste eine Ganzzahl ist, hier dargestellt durch X , gefolgt vom Symbol der Addition ( + ). Der Rest der Liste, der später noch verarbeitet werden muss ( OpenList ), bleibt auf dieser Ebene ungültig. Hole stellt den Teil der Liste dar, den wir nicht überprüfen müssen.
Geben wir eine andere Definition des Prädikats sumDif/2 an, um die Überprüfung des arithmetischen Ausdrucks abzuschließen:
sumDif([X|Hole], Hole) :-
integer(X).
Wir erwarten eine Ganzzahl namens X direkt am Anfang der offenen Liste. Interessanterweise bleibt der Rest des Hole unbekannt, und das ist der ganze Zweck der Differenzlisten: Die Struktur der Liste ist bis zu einem gewissen Punkt bekannt.
Das fehlende Stück kommt schließlich, wenn eine Liste ausgewertet wird:
?- sumDif([1,+,2,+,3], []).
true
In diesem Fall wird das Prädikat verwendet, an dem das Ende der Liste erwähnt wird. Hier zeigt [] , dass die Liste keine zusätzlichen Elemente enthält.
Berechnen Sie einen arithmetischen Ausdruck
Definieren wir eine Grammatik, die es uns ermöglicht, Ergänzungen und Multiplikationen mit Hilfe von Klammern durchzuführen. Um diesem Beispiel mehr Wert zu verleihen, berechnen wir das Ergebnis des arithmetischen Ausdrucks. Zusammenfassung der Grammatik:
Ausdruck → mal
Ausdruck → mal '+' Ausdruck
mal → element
mal → Element '*' mal
Element → "Ganzzahl"
Element → '(' Ausdruck ')'
Alle Prädikate haben eine Arität von 3, da sie die Liste, die Lücke und den Wert des arithmetischen Ausdrucks öffnen müssen.
expression(Value, OpenList, FinalHole) :-
times(Value, OpenList, FinalHole).
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
times(Value, OpenList, FinalHole) :-
element(Value, OpenList, FinalHole).
times(TimesValue, OpenList, FinalHole) :-
element(Value1, OpenList, ['*'|Hole1]),
times(Value2, Hole1, FinalHole),
TimesValue is Value1 * Value2.
element(Value, [Value|FinalHole], FinalHole) :-
integer(Value).
element(Value, ['('|OpenList], FinalHole) :-
expression(Value, OpenList, [')'|FinalHole]).
Um das Prinzip der Löcher richtig zu erklären und wie der Wert berechnet wird, nehmen wir den expression der zweiten Klausel:
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
Die offene Liste wird durch das Prädikat OpenList . Das erste zu überprüfende Element ist das, was vor dem Zusatzsymbol ( + ) steht . Wenn das erste Element validiert ist, folgt direkt das Additionssymbol und die Fortsetzung der Liste mit dem Namen Hole1 . Wir wissen , dass Hole1 das nächste Element ist eine weitere Validierung und kann sein expression , daher Hole1 ist dann der Begriff auf das Prädikat gegeben expression .
Der Wert wird immer im ersten Ausdruck dargestellt. In dieser Klausel wird sie durch die Summe von Value1 (alles vor dem Additionssymbol) und Value2 (alles nach dem Additionssymbol) definiert.
Schließlich kann der Ausdruck a ausgewertet werden.
?- expression(V, [1,+,3,*,'(',5,+,5,')'], []).
V = 31