Grammatiche in Prolog Fabio Massimo Zanzotto (slides di Andrea Turbati con aggiunte)
Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.
-
Upload
gaspare-olivieri -
Category
Documents
-
view
216 -
download
0
Transcript of Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.
Esecuzione dei programmi PrologListe ed operatori aritmetici
Fabio Massimo Zanzotto
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Algoritmo di Risoluzione
… by examples
edge(a,b).
edge(b,c).
edge(a,e).
edge(c,d).
edge(d,e).
edge(f,e).
path(X,Y):- edge(X,Y).
path(X,Y):- path(X,Z),path(Z,Y).
path(a,d).?-
edge(a,d).
X=a,Y=d
fail
X=a,Y=d
path(a,Z),path(Z,d).
edge(a,Z),path(Z,d).
edge(a,b),path(b,d).
edge(a,b),path(b,Z),path(Z,d).
edge(a,b),edge(b,c),path(c,d).
edge(a,b),edge(b,c),edge(c,d). Success!
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Analizza i fatti/regole dall’alto verso il basso (quindi è importante l’ordine con cui vengono scritti)
• Utilizzo del BACKTRACKING per tornare indietro a prima che una variabile fosse unificata o che una certa regola fosse esplorata
• Utilizzo della ricorsione per chiamare le altre regole
• Per avere altre risposte, e quindi forzare il backtracking anche se il programma ne ha già trovata una che funziona, basta premere ;
Esecuzione programma
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
«Letture» dei programmi Prolog
• Il mondo dei se può essere letto in maniera:
– Dichiarativa
I problemi sono risolubili attraverso la scrittura di un insieme di regole – Procedurale
I problemi sono risolubili attraverso la scrittura sequenze di istruzioni
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
«Lettura» Dichiarativa del Prolog
È la lettura classica (e più corretta):• Una clausola con variabili come
grandparent(X,Y):-
parent(X,Z),
parent(Z,Y).• viene letta:Per ogni X e Y e Z,
grandparent(X,Y) è vero se
parent(X,Z) è vero e
parent(Z,Y) è vero
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
«Lettura» Dichiarativa del Prolog
È la lettura classica (e più corretta):
Una query come:
?- grandparent(X,mario).
viene letta come:
esiste un X che tale che grandparent(X,mario) è vero?
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
«Lettura» Procedurale del Prolog
È una lettura necessaria:• Una clausola con variabili come
grandparent(X,Y):-
parent(X,Z),
parent(Z,Y).• Può essere anche letta:Per qualsiasi valore delle variabili X e Y e Z,
per soddisfare il goal grandparent(X,Y) soddisfa prima il goal parent(X,Z) e poi il parent(Z,Y).
ATTENZIONE: le variabili NON variano valore durante il soddisfamento del goal
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
«Lettura» Procedurale del Prolog
È una lettura necessaria:
Una query come:
?- grandparent(X,mario).
viene letta come:
Soddisfare il goal grandparent(X,mario) trovando il valore della variabile X?
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Osservazioni
• Importanza dell’ordine delle clausole e nelle clausole.
path(X,Y):- path(X,Z),path(Z,Y).
path(X,Y):- edge(X,Y).
Genera un loop infinito!!!
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• In Prolog le liste sono molto utilizzate
• Lista: sequenza di vari elementi (anche ripetuti), che possono essere a loro volta delle liste
• Es: [primo, secondo, [primo2, secondo2]].– Lista composta da tre elementi– Il terzo elemento è a sa volta una lista
• La lista può essere vuota (caso molto importante e utilizzato)
Liste
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Ogni lista è composta da due parti:– Head: è il primo elemento– Tail: è il resto della lista (a sua volta una lista)
• Le liste possono essere rappresentati in due modi:– [a,b,c,d]– .(a, .(b, .(c, .(d, []))))
Liste
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Per estrarre la Testa di una lista si usa la notazione:– [H | T ], dove H è la testa e T è la lista rimanente senza
il primo elemento
• Si possono estrarre più elementi contemporaneamente:– [H1, H2 | T]– H1 e H2 sono il primo e il secondo elemento– T è la lista rimanente (la lista di partenza meno i primi
due elementi)
Liste
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• member(?Elem, ?List)– Restituisce true se Elem si trova nella lista, può essere
usato in vari modi:• member(b, [a, b, c, d]). -> true• member(e, [a, b, c, d]). -> false• member(X,[a, b, c, d]). -> X = a ; X=b ; … • member(c, [a, b, X, d]). -> X = c
Operatori su liste
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• member(?Elem, ?List)
• possibile implementazione:member2(X, [X|_]).
member2(X,[_|T]):-
member2(X,T).
Operatori su liste
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• append(?List1, ?List2, ?List1AndList2) – List1AndList2 è la concatenazione di List1 e List2. Vari
utilizzi• append([a,b],[c,d], X). -> X = [a,b,c,d]• append([a,b],X, [a,b,c,d]). -> X = [c,d]• append([a,b],[X,d], [a,b,c,d]). -> X = c• append(X, Y, [a,b,c,d]).
Operatori su liste
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Scrivere una possibile implementazione della append
• Scrivere la regola per invertire tutti gli elementi di una lista, in modo da avere:
?- inverti([a,b,c,d,e,f], X).
X=[f,e,d,c,b,a]
Esercizio
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• In Prolog è possibile definire nuovi operatori, ma ne esistono già alcuni definiti (esempio gli operatori aritmetici)
• 1*2+3*4 ha i due operatori + e *• la scrittura in Prolog sarebbe:
– +(*(1,2), *(3,4))
Operatori
1 2 3 4
*
+
*
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Ogni operatore ha una sua priorità• a + b*c come deve essere letto?
– +(a, *(b,c) ?– *( +(a,b), c) ?
• In matematica * lega di più di +, e quindi + ha priorità più alta di *
Definire un operatore
b c
*
+
a
a b
c
*
+
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• :- op(Priorità, Tipo, Operatore).
• Priorità è un numero tra 0 e 1200
• Tipo:– infisso : xfx, xfy, yfx– prefisso: fx, fy– postfisso: xf, fy
• Operatore: il nome/simbolo dell’operatore
Definire un operatore
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Il tipo serve ad indicare anche la precedenza degli operatori:– x : la sua priorità deve essere minore di quella
dell’operatore– y: la sua priorità deve essere minore o uguale a quella
dell’operatore
• :- op(700, yfx, somma).• Qual è l’albero risultante di
– 9 somma 5 somma 7 ?
Definire un operatore
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• :- op(700, yfx, somma).• 9 somma 5 somma 7
• Quello a sinistra è corretto, perché?
Definire un operatore
a b
c
somma
somma
b c
somma
somma
a
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Prolog può essere usato anche per fare dei calcoli, con alcune limitazioni
• Come detto gli operatori aritmetici sono già definiti
• A = B + C assegna ad A non il risultato della somma ma assegna proprio B + C
• per eseguire l’operazione bisogna usare is
Aritmentica
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• A is 5 + 6 fa sì che in A venga messo il valore 11
• B is 8 + 2 * 3 mette in B 14 (rispetta la priorità)
• A destra di is non possono esserci variabile non ancora istanziate
Aritmetica
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• A = 3 , B is A + 4.– A = 3 e B = 7
• A = 3, B = A + C.– A = 3 e B = 3+C
• A = 3, B is A+C, C=4.– ERROR: is/2: Arguments are not sufficiently
instantiated
Aritmetica
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Gli operatori direttamente utilizzabili sono:– +– -– *– /– ** (elevamento a potenza)– // (divisione intera)– mod (modulo, resto della divisione)– <, >, >=, =<, =, \= (sono confronti booleani utili come
predicati, ma non utilizzabili a sinistra di is)– number(X) (vero se X è un numero, falso negli altri casi)
Operatori per i calcoli
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Vedere il file prolog-2.pl per avere un esempio di regole che usano gli operatori per i calcoli
• calcola(X + Y, Z):-
Z is X+Y.
– calcola(5+8,Y).– Y = 13– calcola(5+8+2,X).– X = 15
Esempio
© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Implementare l’operatore div in modo tale che– A is 12 div 6 div 2– A = 4
• Definire la regola max(A, B, Max) in modo che in Max ci vada il massimo tra A e B
• Pensare anche al caso:– max(A, 5, 9)– A = 9.
Esercizio