Linguaggi di Programmazione
(AA 2002/2003)
Corso di Laurea in Informatica
Introduzione al linguaggio Prolog
Programmazione logica
La programmazione logica nasce all’inizio degli anni settanta da
studi sulla deduzione automatica: il Prolog costituisce il suo
primo prodotto
La programmazione logica NON è soltanto rappresentata dal
Prolog: essa costituisce infatti un settore molto ricco di studi che
cerca di utilizzare la logica matematica come base dei linguaggi
di programmazione. Prolog è l’esempio più noto.
Obiettivi e ragioni di successo:
- semplicità del formalismo
- linguaggio ad alto livello
- semantica chiara
Programmazione logica
la logica matematica
Logica matematica: formalizzazione del ragionamento
Con l'avvento dell'informatica:
• LM  Dimostrazione automatica di teoremi
• interpretazione procedurale di formule
• logica come linguaggio di programmazione
Utilizzata in varie applicazioni: dalle prove di correttezza dei
programmi alle specifiche, da linguaggio per la
rappresentazione della conoscenza in IA a formalismo per
DB.
Stile dichiarativo della
programmazione logica
•
orientato ad utenti non programmatori
•
grande potere espressivo
•
programma come insieme di formule
•
computazione come costruzione di una dimostrazione di una
formula (goal)
BASE FORMALE: calcolo dei predicati del primo ordine ma con
limitazione nel tipo di formule (clausole di Horn) e utilizzo di
particolari tecniche per la dimostrazione di teoremi
(unificazione e risoluzione)
Calcolo dei predicati
Linguaggio per esprimere concetti e loro relazioni e che
permette di inferire proposizioni da altre considerate vere.
SINTASSI (si prescinde dal significato)
• Alfabeto (a,b,...,A,B,...,(,),...,≤,
• Simboli:
- Costanti
di oggetti: C (a,b,casa, 23, ...
di funzione: F (+,-, padre, ...) con arità
di predicato: P (<,=,pari,...) con arità
- Variabili: V (X,Y,...)
Calcolo dei predicati
•
Termini:
i) una variabile XV è un termine
ii) una costante cC è un termine
iii) l’applicazione (f(t1,...,tn)) di un simbolo di
funzione n-ario
fF ad n termini t1,...,tn è un
termine
iv) non esistono altri termini
Termine ground - senza variabili (oggetti dell'Universo del discorso)
Es.: padre(padre(giovanni))
Calcolo dei predicati
• Atomi: {p(t1,..,tn) |p P, t1,..,tn termini}
Es.:
uomo(paolo)
maggiore(X,3)
maggiore(più(X,1),Y)
ama(giovanni,maria)
ama(padre(giovanni),giovanni)
ama(padre(padre(giovanni)),giovanni)
maggiore(più(più(1,giovanni),Y),padre(3))
Calcolo dei predicati
• Formule Ben Formate (fbf):
- Atomi
- frasi logiche: se F, F1, F2 sono fbf
- negazione ~F
- congiunzione F1 F2
- disgiunzione F1 F2
- implicazione F1 F2
- equivalenza F1 F2
- frasi quantificate: se Fè una fbf e X V
- universalmente ("X.F)
- esistenzialmente (X.F)
- non esistono altre fbf
("X)(uomo(X)  mortale(X))  uomo(socrate)  mortale(socrate)
Calcolo dei predicati: esempi di sintassi
1) un esempio filosofico
("X)(uomo(X)  mortale(X))  uomo(socrate)  mortale(socrate)
2) due degli assiomi di base dei numeri naturali
interpretare f e g come funzioni successore e predecessore la
costante
0 come zero il predicato u come uguaglianza )
("X)(Y)(u(Y,f(X))  ("Z)(u(Z,f(X))  u(Y,Z)))
("X)( ~u(X,0) 
((Y)(u(Y,g(X))  ("Z)(u(Z,g(X))  u(Y,Z)))))
3) nella formula ("X) p(X,Y), tutte le occorrenze di X sono vincolate
mentre Y è libera
Calcolo dei predicati: SEMANTICA
Dare una interpretazione alle espressioni
sintatticamente corrette. Definire se certe espressioni
sono vere o false in base al significato che si dà ai
componenti
l'espressione.
Interpretazione
(I):
-
Dominio D
funzione da C a D
funzione da F a (DnD)
funzione da P a (Dn{T,F})
assegnamento di variabili (U):
funzione da V a D
assegnamento di termini: (T)
combinazione di I ed U
Calcolo dei predicati: SEMANTICA
soddisfacimento(
): I
F[U]
vale se F è vera per I e U, cioè interpretata nel dominio D di I.
-

I
I
p(t1,..,tn)[U] iff pI(T(t1),..,T(tn)) = T
- 
I
~F[U] iff F[U] non è vera
- 
I
F1 F2[U] iff F1[U] e F2[U]
- 
I
F1 F2[U] iff F1[U] o F2[U]
- 
I
F1 F2[U] iff F1[U] o non F2[U]
- 
I
F1 F2[U] iff F1 F2[U] eF2 F1[U]
- 
I
- 
I
("X.F)[U] iff per ogni d D F[V]
con V identica ad U tranne che V(X)=d.
(X.F)[U] iff per qualche d D F[V]
con V identica ad U tranne che V(X)=d.
Calcolo dei predicati: SEMANTICA
Un’interpretazione I che soddisfa tutte le formule di un
insieme T (teoria) per tutti i possibili assegnamenti di
 I MODELLO di T:
variabile si dice un
T
F è conseguenza logica di una teoria T :
T I F
iff ogni modello di T è anche modello di F
F è valida |= F
iff F è soddisfatta per ogni I e per ogni U (ogni
interpretazione è un modello)
SOSTITUZIONE
una sostituzione Jè un insieme finito della forma
{v1  t1,…, vn  tn}
vi è una variabile
ti è un termine diverso da vi
le variabili vi, i=1,…,n sono tra loro distinte
una sostituzione è una funzione da variabili a termini
l’applicazione di J ad E è l’espressione ottenuta da E
sostituendo simultaneamente ogni occorrenza della variabile
vi, i=1,…,n con
il termine ti il risultato dell’applicazione (denotato da EJ) è
una
istanza di E.
SOSTITUZIONE: composizione
siano J = {X1  t1,…, Xn  tn} e
l= {Y1  u1,…, Ym  um} due sostituzioni
la composizione di Je l(denotata da J l) è la sostituzione
così definita
i) costruiamo l’insieme
{X1  t1l,…, Xn  tnl, Y1  u1,…, Ym  um}
ii) eliminiamo dall’insieme gli elementi
Xi  tiltali che
til = Xi
iii) eliminiamo dall’insieme gli elementi
Yj  uj tali che
Yj occorre in {X1,…, Xn}
SOSTITUZIONE: composizione
J = {X  f(Y), Y  Z}
l= {X  a, Y  b, Z  Y}
costruzione di J l
i)
ii)
iii)
{X  f(b), Y  Y, X  a, Y  b, Z  Y}
{X  f(b), X  a, Y  b, Z  Y}
{X  f(b), Z  Y}
costruzione di l J
i)
ii)
iii)
{X  a, Y  b, Z  Z, X  f(Y), Y  Z}
{X  a, Y  b, X  f(Y), Y  Z}
{X  a, Y  b}
UNIFICAZIONE
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.
sia dato un insieme di espressioni (termini, atomi, etc.)
{E1,…, Ek}
una sostituzione J è un unificatore per {E1,…, Ek}se e solo
se
un
insieme
E1J=
E2J ={E
…=
EkE
Jk} è unificabile se e solo se
1,…,
esiste una sostituzione J tale che J è un unificatore
per {E1,…, Ek}
ESEMPIO: l’insieme {p(a,Y), p(X,f(b))} è unificabile
dato che la sostituzione J= {X  a, Y  f(b)} è un
unificatore per l’insieme
• un unificatore J per l’insieme {E1,…, Ek} è
l’unificatore più generale (most general
unifier, mgu) se e solo se per ogni unificatore
l dell’insieme {E1,…, Ek} esiste una
sostituzione  tale che l = J
• esiste un algoritmo (algoritmo di
unificazione), che, dato un insieme di
espressioni E = {E1,…, Ek},
rivela la sua non unificabilità, oppure
calcola un unificatore più generale per E
Clausole
• disgiunzione di atomi o negazioni di atomi, in cui le
variabili sono
implicitamente quantificate universalmente
A1 A2 AnB1 B2 ~Bm
•
clausola vuota [] corrisponde a F
è equivalente a
(A1 A2 An) B1 B2 Bm)
(conclusione premesse) regola
•
insieme di clausole: congiunzione di clausole.
Clausole di Horn
Clausole con al più un letterale positivo
clausole definite:
- regole
A B1 B2 Bm
- fatti
A
- clausole negative: (goal) B1 B2 Bm
Un atomo o la sua negazione prende il nome di letterale
Clausole Horn sono un sottoinsieme delle clausole: non
tutte le formule del calcolo dei predicati del prim'ordine
sono esprimibili con esse.
clausole definite esprimono 'conoscenza'
programma logico = insieme di clausole definite
Clausole di Horn
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
A
goal
 B1  B 2  ...  B m (legge di De Morgan)
Notazione PROLOG
regola
A :  B1, B 2 ,..., B m .
fatto
goal
A.
: -B1, B 2 ,..., B m .
contraddiz ione
false.
Principio di risoluzione
siano c1 e c2 due clausole qualunque
c1 = a11  a21  …  an1
c2 = a12  a22  …  am2
tali che i letterali ai1 e aj2 sono complementari
il risolvente di c1 e c2 è la clausola
a11 …  ai-11 ai+11 …  an1
a12…  aj-12 aj+12 …  an2
disgiunzione delle clausole ottenute
eliminando i letterali complementari
Principio di risoluzione: esempi
1) c1 = p  r c2 = ~p  q
c1,2 =r  q
2) c1 = ~p  q  r c2 = ~q  s
c1,2 = ~p  r  s
3) c1 = ~p  q
c1,2 non esiste
c2 = ~p  r
Programmazione logica
Dalla Logica dei predicati del primo ordine verso un
linguaggio di programmazione;
– requisito efficienza
• Si considerano solo clausole di Horn (al più un letterale
positivo)
– il letterale positivo corrisponde alla testa della clausola
• Si adotta una strategia risolutiva particolarmente efficiente
– RISOLUZIONE SLD (la vedremo più avanti)
– Non completa per la logica a clausole, ma completa
per il sottoinsieme delle clausole di Horn.
Prolog
• PROLOG: PROgramming in LOGic, nato nel 1973
• E’ il più noto linguaggio di Programmazione Logica
ALGORITMO = LOGICA + CONTROLLO
• Si fonda sulle idee di Programmazione Logica avanzate da R.
Kowalski
• Basato sulla logica dei Predicati del Primo Ordine
• Manipolatore di SIMBOLI e non di NUMERI
Prolog: sintassi
• Nome di predicato: una sequenza di caratteri alfanumerici
ad esempio ama(.. , ..).
• Nome di funzione: una sequenza di caratteri alfanumerici
ad esempio succ(x).
• Variabili: una sequenza di caratteri alfanumerici maiuscoli.
ad esempio ama(X,susanna).
• And : per rappresentare la congiunzione di predicati
Prolog: ama(george,kate), ama(george,susie).
Italiano: George ama kate e George ama Susie.
• Or : per rappresentare la disgiunzione di predicati
Prolog: ama(george,kate); ama(george,susie).
Italiano: George ama Kate o George ama Susie.
Prolog: sintassi
• Solo se (implicazione): il simbolo :- è utilizzato per
rappresentare il predicato “solo se”
Prolog: ama(george,susie) :- ama(george,kate).
Italiano: George ama Susie se George ama Kate.
• Not: il not si utilizza per rappresentare il complemento del
predicato
Prolog: not(ama(kate,susie)).
Italiano: Kate non ama Susie.
Prolog: programmi
SINTASSI: un programma Prolog e’ costituito da un insieme di
clausole di Horn della forma
(cl1) A FATTO o ASSERZIONE
(cl2) A :- B1, B2,…, Bn REGOLA
(cl3) :- B1, B2,…, Bn GOAL
In cui A e Bi sono formule atomiche
• A : testa della clausola
• B1,B2,…,Bn : body della clausola
Il simbolo “,” indica la congiunzione; il simbolo “:-” l’implicazione
logica in cui A e’ il conseguente e B1,B2,…,Bn l’antecedente
Prolog: concetto di query
L’utente invoca l’interprete Prolog che risponde a delle domande
(queries).
Esempi:
ama(george,kate).ama(george,susie).ama(george,wine).
ama(susie,wine).ama(kate,gin).ama(kate,susie).
?- ama(george,kate).
Yes
?- ama(kate,susie).
Yes
?-ama(george,X).
X = kate;
X = susie;
X = wine;
No
Prolog: esempi
ESEMPIO: due individui sono colleghi se lavorano per la stessa
ditta
Prolog: esempi
Fatti (DB)
padre (giovanni, maria).
padre (carlo, giulio).
madre(maria, ettore).
Domande (Queries) goal
?-padre (giovanni, maria).
risposta: Yes (cons. logica del DB)
?-padre (giovanni, carlo).
risposta: No (fallimento nella
dimostrazione)
Prolog: esempi
Domande esistenziali (con variabili logiche)
?-padre (X, maria).
risposta: X=giovanni
?-padre (X, Y).
risposte: X=giovanni, Y= maria
X=carlo, Y= giulio
Prolog: sintassi
Una formula atomica (atomo) e’ una formula del tipo
p(t1,t2,…,tn)
in cui p e’ un simbolo di predicato e t1,t2,…,tn sono termini
Un termine e’ definito ricorsivamente come segue:
– le costanti (numeri interi/floating point, stringhe alfanumeriche
aventi come primo carattere una lettera minuscola) sono termini
– le variabili (stringhe alfanumeriche aventi come primo
carattere una lettera maiuscola oppure il carattere “_” ) sono
termini.
– f(t1,t2,…,tk) e’ un termine se “f” e’ un simbolo di
funzione (operatore) a k argomenti e t1,t2,…,tk sono
termini.
f(t1,t2,…,tk)viene detta struttura
NOTA: le costanti possono essere viste come simboli funzionali
a zero argomenti.
Prolog: sintassi, esempi
• COSTANTI: a, pippo, aB, 9,135,a92
• VARIABILI: X, X1, Pippo, _pippo, _x, _
– la variabile _ prende il nome di variabile anonima
• TERMINI COMPOSTI: f(a), f(g(1)), f(g(1),b(a),27)
• FORMULE ATOMICHE: p, p(a,f(X)), p(Y), q(1)
• CLAUSOLE DEFINITE:
q.
p:-q,r.
r(Z).
p(X):- q(X,g(a)).
• GOAL:
:-q,r.
Non c’e’ distinzione tra costanti, simboli funzionali e predicativi.
Prolog: interpretazione dichiarativa
Le variabili all’interno di una clausola sono quantificate
universalmente
• per ogni asserzione (fatto)
p(t1,t2,…,tm).
se X1,X2,…,Xn sono le variabili che compaiono in
t1,t2,…,tm il significato e’: "X1,"X2,…,"Xn
(p(t1,t2,…,tm))
• per ogni regola del tipo
A:- B1,B2,…,Bk.
se Y1,Y2,…,Yn sono le variabili che compaiono solo nel body
della regola e X1,X2,…,Xn sono le variabili che compaiono
nella testa e nel corpo, il significato e’:
"X1,"X2,…,"Xn,"Y1,"Y2,…,"Yn ((B1,B2,…,Bk) A)
"X1,"X2,…,"Xn,(Y1,Y2,…,Yn(B1,B2,…,Bk)) A)
Prolog: interpretazione dichiarativa
ESEMPI
padre(X,Y) “X e’ il padre di Y”
madre(X,Y) “X e’ la madre di Y”
nonno(X,Y):- padre(X,Z), padre(Z,Y).
“per ogni X e Y, X e’ il nonno di Y se esiste Z
tale che X e’ padre di Z e
Z e’ il padre di Y”
nonno(X,Y):- padre(X,Z), madre(Z,Y).
“per ogni X e Y, X e’ il nonno di Y se esiste Z
tale che X e’ padre di Z e Z e’ la madre di Y”
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
Prolog: prova di un goal
• Un goal viene provato provando i singoli letterali da sinistra
a destra
:- collega(X,Y), persona(X), persona(Y).
• Un goal atomico (ossia formato da un singolo letterale)
viene provato confrontandolo e unificandolo con le teste delle
clausole contenute nel programma
• Se esiste una sostituzione per cui il confronto ha successo
– se la clausola con cui unifica e’ un fatto, la prova termina;
– se la clausola con cui unifica e’ una regola, ne viene
provato il Body
• Se non esiste una sostituzione il goal fallisce
Schema riassuntivo
Risoluzione LSD
risoluzione Lineare con funzione di Selezione per clausole Defin
• si parte da un insieme di clausole definite (il programma P)
ed
un'unica clausola negativa (il goal G)
• ogni risolvente è sempre ottenuto da una clausola definita
ed
una negativa, ottenendo così un'altra clausola
negativa (il
nuovo goal)
• si deve selezionare a quale letterale del goal applicare la
risoluzione (regola di sel. R).
• una derivazione SLD è una sequenza massimale (finita o
no) di goal (G0G1 di clausole di P (c0 c1) e di
sostituzioni (q0 q1):
- G0 è il goal iniziale G
- ci non ha variabili a comune con G,ci,...,ci-1
- Gi+1 è ottenuto da
Gi = A1 A2 Am e ci = AB1 B2 Bn
[Aj]qi = [A]qi
Gi+1 = [A1Aj-1B1 B2 BnAj+1 Am]qi
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