Esecuzione dei programmi Prolog
Liste ed operatori aritmetici
Fabio Massimo Zanzotto
University of Rome “Tor Vergata”
Algoritmo di Risoluzione
?-
path(a,d).
… by examples edge(a,d).
path(a,Z),path(Z,d).
edge(a,b).
edge(a,Z),path(Z,d).
edge(b,c).
fail
edge(a,b),path(b,d).
edge(a,e).
edge(a,b),path(b,Z),path(Z,d).
edge(c,d).
edge(a,b),edge(b,c),path(c,d).
edge(d,e).
edge(a,b),edge(b,c),edge(c,d). Success!
edge(f,e).
X=a,Y=d
path(X,Y):- edge(X,Y).
path(X,Y):- path(X,Z),path(Z,Y). X=a,Y=d
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esecuzione programma
• 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 ;
© 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”
Liste
• 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)
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Liste
• 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, []))))
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Liste
• 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)
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Operatori su liste
• member(?Elem, ?List)
– Restituisce true se Elem si trova nella lista, può essere
usato in vari modi:
•
•
•
•
© F.M.Zanzotto
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
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Operatori su liste
• member(?Elem, ?List)
• possibile implementazione:
member2(X, [X|_]).
member2(X,[_|T]):member2(X,T).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Operatori su liste
• append(?List1, ?List2, ?List1AndList2)
– List1AndList2 è la concatenazione di List1 e List2. Vari
utilizzi
•
•
•
•
© F.M.Zanzotto
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]).
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Segno 06/03/2014
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizio
• Scrivere una possibile implementazione della
append
• Scrivere la regola per invertire tutti gli elementi di
una lista, in modo da avere:
?- reversed([a,b,c,d,e,f], X).
X=[f,e,d,c,b,a]
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Operatori
• 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))
+
*
1
© F.M.Zanzotto
*
2
Logica per la Programmazione e la Dimostrazione Automatica
3
4
University of Rome “Tor Vergata”
Definire un operatore
• 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 *
*
+
a
b
© F.M.Zanzotto
+
*
c
a
c
b
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Aritmentica
• 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
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Aritmetica
• 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
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Aritmetica
• A = 3 , B is A + 4.
– A=3eB=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
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Operatori per i calcoli
• 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)
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esempio
• 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.
–
–
–
–
© F.M.Zanzotto
calcola(5+8,Y).
Y = 13
calcola(5+8+2,X).
X = 15
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizio
• 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.
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizio
/*max(L,M).
max è vera se L è una lista e M è il massimo di
questa lista
*/
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica