Prolog Language
Skillnadslistor
Sök…
Introduktion
Skillnadslistor i Prolog anger begreppet att känna strukturen på en lista upp till en punkt . Resten av listan kan lämnas obunden tills en fullständig utvärdering av ett predikat. En lista där dess slut är okänd kallas en öppen lista , avslutad med ett hål . Denna teknik är särskilt användbar för att validera komplexa syntaxer eller grammatik.
De välkända Definite Clause Grammars (DCG) använder Difference Lists för att fungera under huven.
Grundläggande användning
Låt oss överväga predikatet sumDif/2 , verifierad om strukturen i en lista matchar flera begränsningar. Den första termen representerar listan som ska analyseras och den andra termen en annan lista som innehåller den del av den första listan som är okänd för våra begränsningar.
För demonstration, sumDif/2 igenkänner ett aritmetiskt uttryck till summan n heltal.
sumDif([X, +|OpenList], Hole) :-
integer(X),
sumDif(OpenList, Hole).
Vi vet att det första elementet i listan som validerar är ett heltal, här illustrerat av X , följt av symbolen för tillägget ( + ). Resten av listan som fortfarande behöver bearbetas senare ( OpenList ) lämnas ogiltig på den nivån. Hole representerar den del av listan som vi inte behöver validera.
Låt oss ge en annan definition av predikatet sumDif/2 att slutföra valideringen av det aritmetiska uttrycket:
sumDif([X|Hole], Hole) :-
integer(X).
Vi förväntar oss ett heltal som heter X direkt i början av den öppna listan. Intressant nog är den återstående av listan Hole okänd och det är hela syftet med skillnadslistorna: listans struktur är känd upp till en punkt.
Slutligen kommer den saknade biten när en lista utvärderas:
?- sumDif([1,+,2,+,3], []).
true
Detta är när predikatet används att slutet på listan nämns, här [] , indikerar att listan inte innehåller ytterligare element.
Utvärdera ett aritmetiskt uttryck
Låt oss definiera en grammatik som gör det möjligt för oss att utföra tillägg, multiplikationer med användning av parentes. För att lägga till mer värde till detta exempel kommer vi att beräkna resultatet av det aritmetiska uttrycket. Sammanfattning av grammatiken:
uttryck → gånger
uttryck → gånger '+' uttryck
gånger → element
gånger → element '*' gånger
element → "heltal"
element → '(' uttryck ')'
Alla predikat har en arity av 3 eftersom de måste öppna listan, hålet och värdet på det aritmetiska uttrycket.
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]).
För att korrekt förklara principen av hål och hur värdet beräknas, låt oss ta den andra klausulen expression :
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
Den öppna listan betecknas av predikatet OpenList . Det första elementet som validerar är vad som kommer före tilläggssymbolen ( + ) . När det första elementet valideras följs det direkt av tilläggssymbolen och av fortsättningen av listan, kallad Hole1 . Vi vet att Hole1 är nästa element för att validera och kan vara en annan expression , därav Hole1 är då termen ges till predikat expression .
Värdet representeras alltid under den första terminen. I denna klausul definieras den av summan av Value1 (allt före tilläggssymbolen) och Value2 (allt efter tilläggssymbolen).
Slutligen kan uttrycket utvärderas.
?- expression(V, [1,+,3,*,'(',5,+,5,')'], []).
V = 31