Prolog Language
Verschillenlijsten
Zoeken…
Invoering
Verschillenlijsten in Prolog geven het concept aan om de structuur van een lijst tot op zekere hoogte te kennen. De rest van de lijst kan ongebonden blijven tot de volledige evaluatie van een predicaat. Een lijst waarvan het einde onbekend is, wordt een open lijst genoemd , afgesloten door een hole . Deze techniek is vooral handig om complexe syntaxis of grammatica's te valideren.
De bekende Definite Clause Grammars (DCG) gebruikt Difference Lists om onder de motorkap te werken.
Basis gebruik
Laten we het predicaat sumDif/2 , geverifieerd of de structuur van een lijst overeenkomt met verschillende beperkingen. De eerste term vertegenwoordigt de lijst die moet worden geanalyseerd en de tweede term een andere lijst met het deel van de eerste lijst dat onbekend is voor onze beperkingen.
Voor de demonstratie, sumDif/2 herkent een rekenkundige expressie som n gehele getallen.
sumDif([X, +|OpenList], Hole) :-
integer(X),
sumDif(OpenList, Hole).
We weten dat het eerste te valideren element van de lijst een geheel getal is, hier geïllustreerd door X , gevolgd door het symbool van de toevoeging ( + ). De rest van de lijst die later nog moet worden verwerkt ( OpenList ) wordt op dat niveau niet gevalideerd. Hole vertegenwoordigt het deel van de lijst dat we niet hoeven te valideren.
Laten we een andere definitie van het predicaat sumDif/2 om de validatie van de rekenkundige uitdrukking te voltooien:
sumDif([X|Hole], Hole) :-
integer(X).
We verwachten een geheel getal met de naam X direct aan het begin van de open lijst. Interessant is dat de rest van de lijst Hole onbekend is gebleven en dat is het hele doel van de verschillijsten: de structuur van de lijst is tot op zekere hoogte bekend.
Ten slotte komt het ontbrekende stuk wanneer een lijst wordt geëvalueerd:
?- sumDif([1,+,2,+,3], []).
true
Dit is wanneer het predikaat wordt gebruikt dat het einde van de lijst wordt vermeld, hier [] geeft aan dat de lijst geen aanvullende elementen bevat.
Evalueer een rekenkundige uitdrukking
Laten we een grammatica definiëren waarmee we toevoegingen, vermenigvuldigingen met het gebruik van haakjes kunnen uitvoeren. Om meer waarde aan dit voorbeeld toe te voegen, gaan we het resultaat van de rekenkundige uitdrukking berekenen. Samenvatting van de grammatica:
uitdrukking → tijden
uitdrukking → tijden '+' uitdrukking
keer → element
tijden → element '*' tijden
element → "geheel getal"
element → '(' expression ')'
Alle predikaten hebben een arity van 3, omdat ze lijst, het gat en de waarde van de rekenkundige uitdrukking moeten openen.
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]).
Om het principe van gaten en hoe de waarde wordt berekend goed uit te leggen, nemen we de tweede clausule- expression :
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
De open lijst wordt aangeduid met het predicaat OpenList . Het eerste te valideren element is wat vóór het toevoegingssymbool ( + ) komt . Wanneer het eerste element is gevalideerd, wordt het direct gevolgd door het toevoegingssymbool en door de voortzetting van de lijst, Hole1 genaamd. We weten dat Hole1 is de volgende element te valideren en kan een ander zijn expression , vandaar Hole1 is dan is de term voor het predicaat expression .
De waarde wordt altijd weergegeven in de eerste term. In deze clausule wordt het gedefinieerd door de som van de Value1 (alles vóór het toevoegingssymbool) en Value2 (alles na het toevoegingssymbool).
Ten slotte kan de uitdrukking an worden geëvalueerd.
?- expression(V, [1,+,3,*,'(',5,+,5,')'], []).
V = 31