Linguaggi di Programmazione
(AA 2002/2003)
Corso di Laurea in Informatica
Introduzione al linguaggio Prolog - parte 2
Prolog
• Lavora su strutture ad ALBERO
– anche i programmi sono strutture dati manipolabili
– utilizzo della ricorsione e non assegnamento
• Metodologia di programmazione:
– concentrarsi sulla specifica del problema rispetto alla
strategia di soluzione
Un PROGRAMMA PROLOG e’ un insieme di clausole di Horn
che rappresentano:
– FATTI riguardanti gli oggetti in esame e le relazioni che
intercorrono
– REGOLE sugli oggetti e sulle relazioni
(SE…..ALLORA)
– GOAL (clausole senza testa), sulla base della
conoscenza definita
Programmazione logica e Prolog
Clausole
Implicazio ne : B  A corrispond e a B  A
oppure A implicato da B (A se B) : A  B
Per una clausola :
A1  A 2  ...  A n  B1  B 2  ...  B m
Usando il teorema di De Morgan :
(A1  A 2  ...  A n )  ( B1  B 2  ...  B m )
A1  A 2  ...  A n  B1  B 2  ...  B m
Programmazione logica e Prolog
Una clausola di Horn ha un solo letterale positivo :
A  B1  B 2  ...  B m
A  B1  B 2  ...  B m
In particolar e :
regola
A  B1  B 2  ...  B m
fatto
goal
A
 B1  B 2  ...  B m
contraddiz ione

Notazione PROLOG
regola
A :  B1, B 2 ,..., B m .
fatto
A.
goal
: -B1, B 2 ,..., B m .
contraddiz ione
false.
Programmazione logica e Prolog
clausole definite:
- regole
- fatti
AB1, B2,..., Bm.
A.
clausole negative: (goal)
B1, B2,..., Bm.
clausole negative:
domanda
$X1...Xn.(B1 B2... Bm)
negazione per applicare la refutazione
~$X1...Xn.(B1 B2... Bm)
"X1...Xn.(~B1 ~B2... ~Bm)
B1, B2,..., Bm.
Programmazione logica e Prolog
Un programma logico:
sum(0,X,X).
sum(s(X),Y,s(Z)) :- sum(X,Y,Z).
Possiamo interpretare s(N) come il successore del
numero N
allora 0, s(0), s(s(0)), s(s(s(0)))… rappresentano
0,1,2,3…
Questo programma definisce la somma fra due numeri
naturali.
Programmazione logica e Prolog
Domande :
$W sum(s(0),0 , W)
$W sum(s(s(0)), s(0), W)
W 1  0
W 2 1
Le negazioni sono :
: - sum(s(0),0 , W) .
W 1  0
: - sum(s(s(0)), s(0), W).
W 2  1
Programmazione logica e Prolog
ESECUZIONE DI UN PROGRAMMA
• Una computazione corrisponde al tentativo di dimostrare,
tramite la risoluzione, che una formula segue logicamente da
un programma (e’un teorema).
• Inoltre, si deve determinare una sostituzione per le variabili
del goal (detto anche “query”) per cui la query segue
logicamente dal programma.
• Dato un programma P e la query: :- p(t1,t2,…,tm).
se X1,X2,…,Xn sono le variabili che compaiono in
t1,t2,…,tm il significato della query e’: $X1, $X2,…, $Xn
p(t1,t2,…,tm)e l’obiettivo e’ quello di trovare una
sostituzione s= {X1/s1,X2/s2,…,Xn/sn}
dove si sono termini tale per cui P |= p(t1,t2,…,tm)]s
Programmazione logica e Prolog
Dato un insieme di clausole di Horn è possibile derivare la clausola
vuota solo se c`è una sola clausola senza testa e tutte le altre
clausole hanno la testa.
Quindi in un programma logico P tutte le clausole debbono avere la
testa mentre la clausola goal G0. non avrà testa.
Si deve dimostrare che da P  {G 0 }
clausola vuota.
è possibile derivare la
Come?
Se si tentassero ad ogni passo tutte le risoluzioni possibili e si
aggiungessero le clausole inferite all’ insieme di partenza si avrebbe
una esplosione combinatoria.
Si deve adottare una strategia di soluzione opportuna.
Programmazione logica e Prolog
Risoluzione ad input lineare
La risoluzione avviene sempre fra l’ultimo goal derivato
in ciascun passo e una clausola di programma, mai fra
due clausole di programma o fra una clausola di
programma ed un goal derivato in precedenza.
Sia dato un programma logico P e un goal G0. Si deve
dimostrare che da
P  {G 0 }
è possibile derivare la clausola vuota.
Programmazione logica e Prolog
Risoluzione ad input lineare (SLD)
dal goal G i
: -A1, A 2 ,..., A m .
e dalla regola
A : B1, B2 ,..., Bm .
se esiste un unificator e  tale che [A]  [ A1 ]
si ottiene un nuovo goal
G i 1 : B1, B2 ,..., Bm , A 2 ,..., A m .
La risoluzione avviene sempre fra l’ultimo goal e una clausola
di programma.
Si puo’ avere: successo (viene generata la clausola vuota)
insuccesso finito
insuccesso infinito
La sostituzione di risposta è la sequenza di unificatori usati.
Applicati alle variabili del goal iniziale danno la risposta.
Programmazione logica e Prolog
• Risoluzione Lineare per Clausole Definite con funzione di
Selezione (RISOLUZIONE SLD)
• Dato un programma logico P e una clausola goal G0, ad
ogni passo di risoluzione si ricava un nuovo risolvente Gi+1,
se esiste, dalla clausola goal ottenuta al passo precedente Gi
e da una variante di una clausola appartenente a P
• Una variante per una clausola C e’ la clausola C’ ottenuta da
C rinominando le sue variabili ( renaming)
– Esempio:
p(X):- q(X,g(Z)).
p(X1):- q(X1,g(Z1)).
Programmazione logica e Prolog
• L’unificazione è un meccanismo che permette di calcolare
una sostituzione al fine di rendere uguali due espressioni. Per
espressione intendiamo un termine, un letterale o una
congiunzione o disgiunzione di letterali.
• SOSTITUZIONE: q = [X1/T1, X2/T2,…, Xn/Tn]
insieme di legami di termini Ti a variabili Xi che rendono
uguali due espressioni.
L’applicazione di una sostituzione a un’espressione E, [E] q
produce una nuova espressione in cui vengono sostituite
tutte le variabili di E con i corrispondenti termini.
• Esempio: Espressione 1: c(X,Y) Espressione 2: c(a,K)
sostituzione unificatrice: = [X/a, Y/K]
Programmazione logica e Prolog
Strategia di risoluzione in profondità con backtracking
Possono esserci più clausole di programma utilizzabili per
applicare la risoluzione con il goal corrente.
Si possono adottare diverse strategie di ricerca:
in profondità : si sceglie una clausola e si mantiene fissa questa
scelta, finchè non si arriva alla clausola vuota o alla impossibilità di
fare nuove risoluzioni. In questo ultimo caso si riconsiderano le scelte
fatte precedentemente.
in ampiezza: si considerano in parallelo tutte le possibili alternative.
Il prolog adotta una strategia di risoluzione in profondità con
backtracking.
•Permette di risparmiare memoria.
•Non è completa per le clausole di Horn.
Programmazione logica e Prolog
• Una derivazione SLD per un goal G0 dall’insieme di clausole
definite P e’ una sequenza di clausole goal G0,…Gn, una
sequenza di varianti di clausole del programma C1, …Cn, e
una sequenza di sostituzioni q1 ,…, qn tali che Gi+1 è derivato
da Gi e da Ci+1 attraverso la sostituzione qn . La sequenza
può essere anche infinita.
• Esistono tre tipi di derivazioni;
– successo, se per n finito Gn è uguale alla clausola vuota
Gn = :– fallimento finito: se per n finito non è più possibile
derivare un nuovo risolvente da Gn e Gn non è uguale a :– fallimento infinito: se è sempre possibile derivare nuovi
risolventi tutti diversi dalla clausola vuota.
Programmazione logica e Prolog
ALBERI DI DERIVAZIONE
• Dato un programma logico P, un goal G0 e una regola di
calcolo R, un albero SLD per P {G0} via R è definito come
segue:
– ciascun nodo dell'albero è un goal (eventualmente vuoto);
– la radice dell'albero è il goal G0;
– dato il nodo :-A1,...,Am-1,Am,Am+1,...,Ak se Am è
l’atomo selezionato dalla regola di calcolo R, allora questo nodo
( genitore) ha un nodo figlio per ciascuna clausola Ci = A:B1,...,Bq di P tale che A e Am sono unificabili attraverso
una sostituzione unificatrice più generale q. Il nodo
figlio è etichettato con la clausola goal:
:-[A1,...,Am-1,B1,...,Bq,Am+1,...,Ak] qe il ramo
dal nodo padre al figlio è etichettato dalla sostituzione qe dalla
clausola selezionata Ci;
– il nodo vuoto (indicato con “:-”) non ha figli.
Programmazione logica e Prolog
(cl1)
(cl2)
(cl3)
(cl4)
p :- q,r.
p :- s,t.
q :- u.
q :- v.
(cl5)
(cl6)
(cl7)
s:- w.
t.
w.
goal :- p.
Albero di
risoluzione
:- p. (1)
(cl1)
:- q,r. (2)
(cl3)
:- u,r. (3)
fallimento
(cl2)
:- s,t. (5)
(cl4)
(cl5)
:- v,r. (4)
Strategia
di risoluzione
:- w,t. (6)
in profondità
(cl7)
con
backtracking
fallimento
:- t. (7)
(cl6)
:-
clausola vuota - successo
Programmazione logica e Prolog
REGOLA DI CALCOLO
• Ad ogni ramo di un albero SLD corrisponde una derivazione
SLD.
– Ogni ramo che termina con il nodo vuoto (“:-”) rappresenta
una derivazione SLD di successo.
• La regola di calcolo influisce sulla struttura dell’albero per
quanto riguarda sia l’ampiezza sia la profondità. Tuttavia non
influisce su correttezza e completezza. Quindi, qualunque sia
R, il numero di cammini di successo (se in numero finito) è lo
stesso in tutti gli alberi SLD costruibili per P {G0} .
• R influenza solo il numero di cammini di fallimento (finiti ed
infiniti).
Programmazione logica e Prolog
sum(0,X,X). (CL1)
sum(s(X),Y,s(Z)):- sum(X,Y,Z). (CL2)
G0= :- sum(W,0,0),sum(W,0,K).
Albero SLD con regola di calcolo “left-most”
Programmazione logica e Prolog
sum(0,X,X). (CL1)
sum(s(X),Y,s(Z)):- sum(X,Y,Z). (CL2)
G0= :- sum(W,0,0),sum(W,0,K).
Albero SLD con regola di calcolo “right-most”
Programmazione logica e Prolog
(cl1)
(cl2)
(cl3)
p:- q,r.
p.
q:- q,t.
(cl1)
:- q,r. (2)
(cl3)
:- q,t,r. (3)
(cl3)
Albero di
risoluzione
Strategia
per il goal :- p.
in profondità
:- p. (1)
con
backtracking
di risoluzione
(cl2)
:-
La clausola vuota può essere generata
ma il Prolog non è in grado di trovare
questa soluzione
fallimento :- q,t,t,r. (4)
(cl3)
:- q,t,t,t,r. (5)
(cl3)
Ramo di fallimento
infinito
Programmazione logica e Prolog
Dal programma logico:
sum(0,X,X).
(c1)
sum(s(X),Y,s(Z)) :- sum(X,Y,Z).
E dal goal
(c2)
sum(s(s(0)),s(0),W)
(g0)
risolvendo il goal g0 con c2 con {X/s(0),Y/s(0),W/s(Z1)}
:- sum(s(0),s(0),Z1)
(g1)
risolvendo il goal g1con c2 con {X/0,Y/s(0),Z1/s(Z2)}
:- sum(0,s(0),Z2)
(g2)
risolvendo il goal g1con c1 con {X/0,Y/s(0),Z2/s(0)}
:-
clausola vuota
La risposta si ottiene dalla sequenza di sostituzioni
W=s(Z1) Z1=s(Z2) Z2=s(0) quindi W=s(s(s(0))) cioè 2+1=3
Programmazione logica e Prolog
1. p(x,z)  p(y,z), q(x,y)
2. p(x,x) 
3. q(a,b) 
La query 4.  p(x,b)
Albero di ricerca
<-- p(x,b) •
1
<-- p(y,b), q(x,y)
x=a
y=b
3
<-- p(b,b)
•
2
1
•
<-- p(y,b), q(b,y)
fallimento finito
•
•
2
x=b
•
Programmazione logica e Prolog
PARENTELE
"(m, c)Madre(m, c)  Femmina(m)  Genitore(m , c)
"(p, c)Genitore (p, c)  Figlio(c, p)
"(g, c)(Nonno(g , c)  ($p)Genitore (g, p)  Genitore(p , c))
"(x, y)(Fratell o(x, y)  x  y  ($p)Genitore (p, x)  Genitore(p , y))
da :
Genitore(G iovanni, Mario)  Genitore(G iovanni, Luca)
si inferisce :
Fratello(M ario, Luca)
Programmazione logica e Prolog
PARENTELE
madre(m, c) : femmina(m) , genitore(m , c).
genitore(p , c) : figlio(c, p).
nonno(g, c) : genitore(g , p), genitore(p , c).
fratello(p , c) : diverso(p, c), genitore(g , p), genitore(g , c))
genitore(l uisa, luca).
genitore(m ario,,marco).
marco).
genitore(g iovanni, mario).
genitore(g iovanni, luca). diverso(ma rco, mario). diverso(ma rio, luca).
: - Fratello(m ario, luca).
Programmazione logica e Prolog
: - fratello(m ario, luca).
{p / mario, c / luca}
: - diverso(mario, luca), genitore(g, mario), genitore(g, luca) .
{}
: - genitore(g, mario), genitore(g , luca) .
{g / luisa}
: - genitore(l uisa, luca) .
fallimento
{g / giovanni}
: - genitore(giovanni, luca) .
:-
Programmazione logica e Prolog
:- collega(a,c). cl4
cl3
:- collega(a,Y1), collega(Y1,c).
:- collega(c,a).
cl3
cl4
cl1
cl3
cl4
collega(b,c)
:- collega(a,c).
cl4
cl3
cl4
:- collega(b,Y2), collega(Y2,c). collega(c,b)
cl3
ramo
:- collega(b,Y3),collega(Y3,Z3), collega(Z3,c). infinito
cl3 ramo infinito
(cl1) collega(a,b).
(cl2) collega(c,b).
(cl3) collega(X,Z):- collega(X,Y),collega(Y,Z).
(cl4) collega(X,Y):-collega(Y,X).
Programmazione logica e Prolog
P :- Q,R.
Interpretazione dichiarativa:
P è vero se sono veri Q e R.
Interpretazione procedurale:
Il problema P può essere scomposto nei sottoproblemi P e Q.
Modello di esecuzione:
Programma
Lista di goal
execute
Indicatore successo/fallimento
Istanza delle variabili
Un goal può essere visto come una chiamata ad una procedura.
Una regola può essere vista come la definizione di una procedura in cui la
testa è l’intestazione mentre la parte destra è il corpo.
Programmazione logica e Prolog
Per rendere il Prolog un linguaggio effettivamente utilizzabile
vengono aggiunti:
•Notazione per le liste.
•Possibilità di manipolare strutture dati.
•Operazioni aritmetiche.
•Meccanismi di controllo del backtracking.
•Trattamento della negazione.
•Predicati di input/output.
•Meccanismi per modificare/accedere alla base di conoscenza.
•Meccanismi per il caricamento del codice prolog.
Programmazione logica e Prolog
Predicati di controllo di un programma
Predicati predefiniti che consentono di influenzare e
controllare il processo di esecuzione (dimostrazione) di un
goal.
CUT e controllo del backtracking
PREDICATO CUT ( ! )
– E’ denotato dal simbolo !
– E’ uno dei più importanti e complessi predicati di controllo
forniti da Prolog
Per capire come funziona il predicato cut e’ necessario
vedere il modello run time di Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
EFFETTO DEL CUT
Si consideri la clausola:
p :- q1, q2,…, qi, !, qi+1, qi+2,…, qn.
l’effetto della valutazione del goal ! (cut) durante la
dimostrazione del goal "p" è il seguente:
– la valutazione di ! ha successo (come quasi tutti i
predicati predefiniti) e ! viene ignorato in fase di
backtracking;
– tutte le scelte fatte nella valutazione dei goal q1,
q2,..., qi e in quella del goal p vengono rese
definitive; in altri termini, tutti i punti di scelta per tali goal
(per le istanze di tali goal utilizzate) vengono rimossi dallo
stack di backtracking.
– Le alternative riguardanti i goal seguenti al cut non
vengono modificate
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Programmazione logica e Prolog
Linguaggi imperativi (C , Pascal etc.)
Si specifica come risolvere un problema
Linguaggi dichiarativi
Funzionali (Lisp puro)
Usa il concetto di funzione e di
composizione di funzioni
Logici (Prolog)
Si descrivono le relazioni che intercorrono fra i dati.
Non ci sono assegnamenti. Non determinismo.