Prolog
PROgramming in LOGic
LPA Prolog
Ambiente Windows a 32-bit
.pl .exe
Interprete e non compilatore
Sintassi di Edimburgo
Dati o Termini
semplici
costanti
atomi
strutturati
variabili
numeri
Termini semplici
Costanti
Atomi
1.
3.
4.
2. Sono
Un
Una
Unacarattere
stringa
stringa
atomi anche:
di
di
minuscolo
caratteri
caratteri tra
speciali:
seguito da
! ^;< >
[]: . {}
altri+caratteri:
singole
- / virgolette:
\=
@ :#$&
'ABC'
<>
a
carloMagno
'1234'
##&&
due_luglio_2000
'a<>b'
::=
Termini semplici
Costanti
Numeri
1. Reali:
Interi:
0.5
0
-3.1416
-16
6.23e+23
33
11.0e-3
+100
-2.6e-2
Termini semplici
Costanti
Variabili
Tutte le variabili in Prolog iniziano
con una lettera maiuscola o con _
X25
List
Massimo_De_Gregorio
_234
Termini strutturati
Una termine strutturato può essere formato da diversi
componenti. Ogni componente di una struttura può
essere un termine (semplice o strutturato).
Struttura
Liste
- rappresentazione
un generale
caso particolare
reale
di termini strutturati
Unatermine
Un
lista in strutturato
Prolog è una
è sintatticamente
collezione di termini.
formato da un
sole]
•funtore
la lista
e una
vuota
lista
è rappresentata
di [mare,
argomenti.
da
In particolare:
[ ];
[mela,
• iluna
funtore
lista deve
non vuota
essere
è specificata
unpera,
atomo;uva]
scrivendo i suoi
• la
elementi
lista di argomenti
tra parentesi
è racchiusa
quadre e divisi
tra parentesi;
da ",".
.(sole,
[]))
[].(mare,
[mela,
uva] da una ",";
• ogni argomento
è[a]
separato
dalpera,
successivo
.(mela,è un
.(pera,
• ogni argomento
termine..(uva, [])))
padre(mario,carlo)
f(a,g(A,c),h(d))
per(2,3,6)
Corrispondenza tra termini e alberi
• La radice dell'albero è il funtore;
• ogni argomento della struttura è un figlio della radice;
• se un argomento è una struttura, sarà disegnato
usando quest'algoritmo ricorsivamente.
Corrispondenza tra termini e alberi
somma(2, 3, 5)
•
somma
2
3
[mela, pera, uva]
mela
5
•
•
pera
uva
[]
Componenti di un programma
• Un programma Prolog è una collezione
di predicati (o regole);
• un predicato stabilisce una relazione tra gli oggetti;
• in Prolog, l'esecuzione di un programma significa
che una query è data e il sistema cerca di stabilire
se la query segue (logicamente) dai predicati del
programma.
Predicati e Clausole
• Un predicato è composto da una o più clausole
• Un goal è un termine definito dal programmatore ed
è o un atomo o un termine strutturato
• La forma generale di una clausola è la seguente:
<left-hand-side> :- <right-hand-side>.
grand_parent(X, Y) :parent(X, Z),
parent(Z, Y).
una clausola
parent(X, Y) :- mother(X, Y).
parent(X, Y) :- father(X, Y).
due clausole
Clausole unitarie o Fatti
'Mario' è il padre di 'Alberto'
1 - father('Mario', 'Alberto') :- true.
2 - father('Mario', 'Alberto').
Queries
Chi è il padre di 'Alberto'?
?- father(X, 'Alberto').
X = 'Mario'
?-
Scrivere programmi
•
•
•
•
Un programma Prolog è un insieme di fatti e regole
Fatti e regole sono memorizzati in uno o più file
Formato libero
Commenti
% <commento>
/*
<commento1>
<commento2>
*/
• Formattazione del codice
grand_parent(X, Y) :parent(X, Z),
parent(Z, Y).
parent(X, Y) :- mother(X, Y).
parent(X, Y) :- father(X, Y).
Finestre Main e Console
La console
Comandi da console
• uso dell'<enter>
• editing dei comandi
• riscrittura dei comandi
• comandi su più linee <ctrl-enter> e <enter>
• opzione break in - <ctrl-break>
Azzeramento della console
Output sulla console
Le variabili
Prolog
C o Pascal
singolo data object
locazione di memoria
(valore mantenuto)
(diversi valori)
(fino alla fine)
(durante)
Variabili che appaiono inizialmente nel goal nella parte sinistra
della regola sono quantificate universalmente.
Variabili che appaiono nel goal solo nella parte destra della
regola sono quantificate esistenzialmente (lo stesso per
quelle che appaiono nelle query).
Semantica dei programmi Prolog
Dichiarativo
Procedurale
what
how
(quale sarà il risultato)
(come trovare il risultato)
grand_parent(X, Y) :parent(X, Z),
parent(Z, Y).
?- grand_parent(mario, Y).
?- grand_parent(mario, carlo).
Unificazione
T1 e T2 sono due termini
costanti
sono lo stesso termine
variabili
uno alias dell’altro
T1 variabile e T2 qualsiasi termine
T1 istanziato a T2
T1 e T2 termini strutturati
stesso funtore
stessa arità
tutti gli argomenti corrispondenti
essere unificati
Esecuzione di un programma in Prolog
Verifica di una collezione di goal rispetto a un dato
programma
La verifica è fatta in accordo all'Algoritmo di Risoluzione
(Prolog engine o Resolution mechanism)
L'input a questo algoritmo è un programma (collezione di
predicati) e una query (uno o più goal)
L'output sarà successo o fallimento a seconda se la
validità della query iniziale potrà essere verificata o meno
Nel caso la query contenga delle variabili e possa essere
verificata, l'algoritmo mostrerà particolari valori delle
variabili che rendono la query valida
Esecuzione di un programma in Prolog
| ?- father(albert, john).
| ?- sister(paul, X).
| ?- sister(paul, X), mother(X, Y).
Esecuzione di un programma in Prolog
Possiamo vedere l'esecuzione di un programma Prolog
come un problema di ricerca e la rappresentazione del
trace come un albero. L'obiettivo, quindi, dell'algoritmo
è di trovare una soluzione (se esiste) nello spazio di
ricerca.
Depth-first e backtracking
Poiché i predicati possono essere ricorsivi, una ricerca
breadth-first avrebbe il vantaggio di trovare sempre una
soluzione se esiste. D'altro canto, una ricerca depth-first
dello stesso albero potrebbe non terminare quando, per
esempio, le clausole ricorsive sono provate per prime.
Controllo del backtracking
Il backtracking agisce automaticamente sul fallimento
per soddisfare un goal. Sebbene questa operazione è
essenziale per la procedura di ricerca usata dal Prolog,
essa può anche portare a delle inefficienze (ad esempio,
trovare soluzioni alternative a un goal che può essere
soddisfatto solo una volta). In questi casi, sarebbe
molto utile ai programmatori indicare che il
backtracking non deve agire.
Il Prolog rende disponibile un meccanismo per il
controllo del backtracking: il cut.
Controllo del backtracking
Il cut è un goal. Esso ha successo immediatamente
appena si incontra in una clausola. Però, facendo ciò,
rimuove tutti i punti di backtracking tra l'inizio del
predicato e se stesso.
q(X, Y) :- a(X), b(Y).
q(X, Y) :- c(X), !, d(Y).
q(X, Y) :- e(X, Y).
| ?- …, p(A), q(A, B), r(B), …
Controllo del backtracking
Green cut
Predicati definiti da più clausole in cui
esattamente una sola clausola può avere
successo (mutuamente esclusive).
Dopo
Prima
max(A,
max(A,B,B,A)A):-:-A A>=>=B,B.!.
max(A,
max(A,B,B,A)A):-:-B B>=>=A,A.!.
Controllo del backtracking
Red cut
Quando il cut è introdotto per evitare o
saltare la verifica di un goal. La semantica
del programma è alterata (non produce lo
stesso risultato con e senza cut).
Prima
Dopo
add(X,L,L) :member(X,L). !.
member(X,L),
add(X,L,[X|L]).
|
L
L
?- add(a,[a,b,c],L).
= [a,b,c] ;
= [a,a,b,c]
Controllo del backtracking
q(X, Y) :- a(X), b(Y).
q(X, Y) :- c(X), !, fail.
Controllo del backtracking
Un altro predicato di controllo
IF-Then-Else
Modifica dinamica dei programmi
Programmi che aggiungono e rimuovono
clausole
in questo
modo
introducono
effetti
I programmi,
una volta
caricati
- consult
- in
collaterali:
la astatici.
loro Una
esecuzione
causa
Prolog,
volta
che
un
Il
Prolog sono
mette
disposizione
predicati
il cui
cambiamenti
chee possono
future
insieme
fatti
regole
è modificare
stato caricato
in
scopo è di aggiungere
o rimuovere
clausole.
esecuzioni
(chiamate
che
hanno
successo
Prolog,
questo
insieme
non
può
essere
Una volta
modificato
in questo
modo,
la
in
un originale
determinato
punto
possono,
in
modificato
durante
l'esecuzione
forma
del predicato
è persa edel
la
seguito,
fallire
aver
successo
un
numero
programma
(l'unica
eccezione,
nuova forma
èo mantenuta
finoovviamente,
a ulteriori
differente
di volte).
è un nuovo
caricamento del programma modifiche.
Programmi
reconsult). che adottano queste tecniche
sono estremamente difficili da seguire,
modificare e da inspezionare (debug).
Modifica dinamica dei programmi
assert(Clause)
aggiunge una clausola
clausole di un predicato
alla
fine
delle
assert( (p(X) :- q(X, Y), r(Y)) ).
assert( p(pippo) ).
assert( p(_) ).
p(X) :- q(X, Y), r(Y).
p(pippo).
p(_).
Modifica dinamica dei programmi
asserta(Clause)
aggiunge una clausola
clausole di un predicato
all'inizio
delle
assert( (p(X) :- q(X, Y), r(Y)) ).
asserta( p(pippo) ).
assert( p(_) ).
p(pippo).
p(X) :- q(X, Y), r(Y).
p(_).
Modifica dinamica dei programmi
assertz(Clause)
aggiunge una clausola
clausole di un predicato
alla
fine
delle
assert( (p(X) :- q(X, Y), r(Y)) ).
assertz( p(pippo) ).
assert( p(_) ).
p(X) :- q(X, Y), r(Y).
p(pippo).
p(_).
Modifica dinamica dei programmi
retract(Clause)
rimuove una clausola di un predicato
assert( (p(X) :- q(X, Y), r(Y)) ).
assert( p(pippo) ).
assert( p(_), 2 ) .
retract( p(pippo) ).
p(X) :- q(X, Y), r(Y).
p(_).
Modifica dinamica dei programmi
retractall(Head)
rimuove tutte le clausole la cui testa è Head
assert( (p(X) :assert( p(pippo)
retractall( p(_)
assert( p(pluto)
p(pluto).
q(X, Y), r(Y)) ).
).
).
).
Modifica dinamica dei programmi
Per poter manipolare i predicati usando
assert e retract i predicati devono essere
dinamici.
I predicati creati a runtime sono dinamici.
Quando i predicati sono consultati da un
file, per poterli modificare devono essere
resi dinamici esplicitamente.
:- dynamic fratello/2, append/3.
Modifica dinamica dei programmi
Cosa succede se eseguiamo la seguente
query?
| ?- retract(X), fail.
La query ovviamente
fallisce
ma
l'effetto
collaterale è quello di
rimuovere
tutte
le
clausole dinamiche dal
programma.
findall e forall
forall(robot(_,_,_,_,Robot), muovi_robot(W,N,Robot))
findall(N,neuron(N,_,_,_,_,in),In)
Ricorsione
write_list([]).
write_list([A|L]) :write(A), nl,
write_list(L).
somma([],0).
somma([A|L],S) :somma(L,S1),
S is A+S1.
Robot spazzino
:- dynamic robot/3,
sporco/2.
sporco(5,5).
sporco(2,8).
sporco(3,7).
sporco(7,1).
sporco(1,1).
sporco(4,9).
sporco(9,2).
robot(0,0,0).
cestino(0,0).
vai :sporco(X,Y),
robot(X,Y,0),
raccogli,
vai.
vai :sporco(X,Y),
robot(X1,Y1,0),
verso(X,Y),
vai.
vai :cestino(X,Y),
robot(X,Y,1),
svuota,
vai.
vai :cestino(X,Y),
robot(X1,Y1,1),
verso(X,Y),
vai.
vai.
Robot spazzino
raccogli :robot(X,Y,0),
retract(sporco(X,Y)),
retractall(robot(_,_,_)),
write('Immodizia raccolta!'), nl,
assert(robot(X,Y,1)).
svuota :robot(X,Y,1),
retractall(robot(_,_,_)),
write('Serbatoio svuotato!'), nl,
assert(robot(X,Y,0)).
Robot spazzino
verso(X,Y) :robot(X1,Y1,S),
Dx is X-X1,
Dy is Y-Y1,
muoviti(Dx,Dy,DX,DY),
retract(robot(X1,Y1,S)),
X2 is X1+DX,
Y2 is Y1+DY,
write('Robot in: '), write(X2),
write(', '), write(Y2), nl,
assert(robot(X2,Y2,S)).
muoviti(0,Dy,0,DY) :DY is Dy/abs(Dy).
muoviti(Dx,0,DX,0) :DX is Dx/abs(Dx).
muoviti(Dx,Dy,DX,DY) :DY is Dy/abs(Dy),
DX is Dx/abs(Dx).