Prolog Language
Liste de différences
Recherche…
Introduction
Les listes de différences de Prolog désignent le concept pour connaître la structure d'une liste jusqu'à un point . Le reste de la liste peut être laissé libre jusqu'à l'évaluation complète d'un prédicat. Une liste dont la fin est inconnue est appelée liste ouverte , terminée par un trou . Cette technique est particulièrement utile pour valider des syntaxes complexes ou des grammaires.
Le bien connu Grammars Clause définie (DCG) utilise des listes de différences pour fonctionner sous le capot.
Utilisation de base
Considérons le prédicat sumDif/2 , vérifié si la structure d'une liste correspond à plusieurs contraintes. Le premier terme représente la liste à analyser et le second terme une autre liste contenant la partie de la première liste inconnue de nos contraintes.
Pour la démonstration, sumDif/2 reconnaît une expression arithmétique pour résumer n entiers.
sumDif([X, +|OpenList], Hole) :-
integer(X),
sumDif(OpenList, Hole).
Nous savons que le premier élément de la liste à valider est un entier, ici illustré par X , suivi du symbole de l'addition ( + ). Le reste de la liste qui doit encore être traité ultérieurement ( OpenList ) est laissé non validé à ce niveau. Hole représente la partie de la liste que nous n'avons pas besoin de valider.
Donnons une autre définition du prédicat sumDif/2 pour compléter la validation de l'expression arithmétique:
sumDif([X|Hole], Hole) :-
integer(X).
Nous attendons un entier appelé X directement au début de la liste ouverte. Il est intéressant de noter que le reste de la liste Hole reste inconnu et que les listes de différences servent à l’objectif: la structure de la liste est connue jusqu’à un certain point.
Enfin, la pièce manquante vient quand une liste est évaluée:
?- sumDif([1,+,2,+,3], []).
true
C'est lorsque le prédicat est utilisé que la fin de la liste est mentionnée, ici [] , indique que la liste ne contient pas d'éléments supplémentaires.
Evaluer une expression arithmétique
Définissons une grammaire permettant d'effectuer des additions, des multiplications avec l'utilisation de parenthèses. Pour ajouter plus de valeur à cet exemple, nous allons calculer le résultat de l'expression arithmétique. Résumé de la grammaire:
expression → fois
expression → fois expression '+'
times → element
times → element '*' times
element → "entier"
element → '(' expression ')'
Tous les prédicats ont une arité de 3, car ils doivent ouvrir la liste, le trou et la valeur de l'expression arithmétique.
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]).
Pour bien expliquer le principe des trous et comment la valeur est calculée, prenons la deuxième expression clause:
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
La liste ouverte est désignée par le prédicat OpenList . Le premier élément à valider est ce qui précède le symbole d'addition ( + ) . Lorsque le premier élément est validé, il est directement suivi du symbole d'addition et de la suite de la liste, appelée Hole1 . Nous savons que Hole1 est l'élément suivant à valider et peut être une autre expression , donc Hole1 est alors le terme donné à l' expression prédicat.
La valeur est toujours représentée dans le premier terme. Dans cette clause, elle est définie par la somme de Value1 (tout avant le symbole de l’addition) et Value2 (tout après le symbole de l’addition).
Enfin, une expression peut être évaluée.
?- expression(V, [1,+,3,*,'(',5,+,5,')'], []).
V = 31