Prolog Language
Elenchi di differenze

introduzione

Utilizzo di base

Consideriamo il predicato sumDif/2 , verificato se la struttura di una lista corrisponde a diversi vincoli. Il primo termine rappresenta l'elenco da analizzare e il secondo termine un altro elenco che contiene la parte del primo elenco che è sconosciuta ai nostri vincoli.

Per la dimostrazione, sumDif/2 riconosce un'espressione aritmetica per sommare n interi.

sumDif([X, +|OpenList], Hole) :-
    integer(X),
    sumDif(OpenList, Hole).

Sappiamo che il primo elemento della lista da validare è un numero intero, qui illustrato da X , seguito dal simbolo dell'aggiunta ( + ). Il resto dell'elenco che deve ancora essere elaborato in seguito ( OpenList ) non viene OpenList a quel livello. Hole rappresenta la parte dell'elenco che non è necessario convalidare.

Diamo un'altra definizione del predicato sumDif/2 per completare la convalida dell'espressione aritmetica:

sumDif([X|Hole], Hole) :-
    integer(X).

Prevediamo un intero chiamato X direttamente all'inizio della lista aperta. È interessante notare che il resto dell'elenco Hole è rimasto sconosciuto e questo è l'intero scopo delle liste delle differenze: la struttura dell'elenco è nota fino a un certo punto.

Infine, il pezzo mancante arriva quando viene valutato un elenco:

?- sumDif([1,+,2,+,3], []).
true

Questo è quando si usa il predicato che la fine della lista è menzionata, qui [] , indica che la lista non contiene elementi aggiuntivi.

Valuta un'espressione aritmetica

Definiamo una grammatica che ci consenta di eseguire aggiunte, moltiplicazioni con l'uso di parentesi. Per aggiungere più valore a questo esempio, calcoleremo il risultato dell'espressione aritmetica. Riassunto della grammatica:

espressione → tempi
espressione → tempi '+' espressione
volte → elemento
volte → elemento '*' volte
elemento → "intero"
elemento → '(' espressione ')'

Tutti i predicati hanno un'arità di 3, perché hanno bisogno di aprire la lista, il buco e il valore dell'espressione aritmetica.

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]).

Per spiegare correttamente il principio dei buchi e come viene calcolato il valore, prendiamo la seconda expression frase:

expression(SumValue, OpenList, FinalHole) :-
    times(Value1, OpenList, ['+'|Hole1]),
    expression(Value2, Hole1, FinalHole),
    plus(Value1, Value2, SumValue).

L'elenco aperto è indicato dal predicato OpenList . Il primo elemento da convalidare è ciò che precede il simbolo di addizione ( + ) . Quando il primo elemento è convalidato, è seguito direttamente dal simbolo di addizione e dal seguito dell'elenco, chiamato Hole1 . Sappiamo che Hole1 è l'elemento successivo da convalidare e può essere un'altra expression , quindi Hole1 è quindi il termine assegnato expression del predicato.

Il valore è sempre rappresentato nel primo termine. In questa clausola, è definita dalla somma di Value1 (tutto prima del simbolo di addizione) e Value2 (tutto dopo il simbolo di addizione).

Infine, l'espressione può essere valutata.

?- expression(V, [1,+,3,*,'(',5,+,5,')'], []).
V = 31