Basi del linguaggio Prolog

Il primo passo:
I basilari del Prolog
Fabio Massimo Zanzotto
(slides realizzate da Andrea Turbati)
University of Rome “Tor Vergata”
Elementi del Prolog
• Termini
• Predicati
• Clausole (Fatti e Regole)
• Programma logico
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Termini
• Atomi: nomi che iniziano con lettera MINUSCOLA, sequenze di
caratteri tra ‘ ’, numeri preceduti da caratteri
– andrea
– ‘Corso di Prolog’
– c1p8
• Numeri
– 12345
• Variabili: nomi che iniziano con lettera MAIUSCOLA o con _
– Tizio
– _andrea
– _
• Termini composti
– somma(1, 2, X)
– 1+2
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Predicati
• Espressi tramite la notazione f(t1, …, tn )
• f è un atomo che prende il nome di funtore
• t1, …, tn sono gli argomenti e sono dei termini
(predicato f con n argomenti, ha arità n)
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Clausole
• Le clausole: fatti e regole
• I fatti sono regole senza corpo
• Fatti:
parent(ben, jim).
friend(luke, daisy).
• Regole:
grandparent(X,Y):parent(X,Z),
parent(Z,Y).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Regole
• Head :- Body . significa che affinché la Head sia
vera deve essere vero il Body (e quindi i predicati
che lo compongono)
• Nel Body ci sono 1 o più predicati separati da ,
(and) o da ; (or)
• Ogni regola termina con .
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Fatti
• Un fatto è un predicato seguito da .
• Un fatto può essere composto da più termini
– amico(fratello(alice, X), bob).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Programma logico
• Insieme di regole/fatti
• Risponde alle query con o true o false e assegna
dei valori alle variabili
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esempio: Famiglia
parent(anne, bill).
parent(anne, charlie).
parent(bill, donnie).
grandparent(X,Y):parent(X,Z),
parent(Z,Y).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esempio: Famiglia
• Query:
?- parent(anne, bill).
• Risposta:
true
• Query
?- parent(anne, X).
• Risposta:
X=bill
(premo ; )
X = charlie
(premo ; )
false
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esempio: Famiglia
• Query:
?- parent(X, Y).
• Risposta:
X=anne, Y=bill
(premo ; )
X=anne, Y=charlie
(premo ; )
X=bill, Y=donnie
(premo ; )
false
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esecuzione del programma
• Prolog cerca nel proprio database di regole e fatti,
quelli che soddisfano la nostra query, istanziando
le variabili
• Ogni variabile, una volta istanziata (unificata), non
può assumere un secondo valore (a differenza dei
linguaggi classici di programmazione, come Java,
C, C++, ecc)
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esempio
• Dati i fatti:
© F.M.Zanzotto
–
–
–
–
parent( pam, bob).
parent( bob, tom).
parent( tom, ann).
parent( bob, jerry).
–
–
–
–
–
female(pam).
male(bob).
male(tom).
female(ann).
male(jerry).
E le regole
father(X,Y):male(X),
parent(X,Y).
mother(X,Y):female(X),
parent(X,Y).
?- mother(ann,X).
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esempio
• E le regole
father(X,Y):male(X),
parent(X,Y).
mother(X,Y):female(X),
parent(X,Y).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esempio
• Che risposta ho alle seguenti interrogazioni?
– ?- mother(X,Y).
– ?- father(X,Y).
– ?- mother(X,ann).
– ?- father(X,ann).
– ?- mother(ann,X).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
L’interprete Prolog
• SWI-Prolog
– http://www.swi-prolog.org/
– ha la licenza Lesser GNU Public License
– contiene un basilare editor di sviluppo (poco più che un
semplice editor di test)
– Funziona su windows, linux e mac
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Comandi utili
• edit.
– apre l’editor per modificare/aggiungere fatti e regole al
file in esame
• consult('nome_file').
– carica un file con i suoi dati
• reconsult(‘nome_file’) .
– ricarica il file con i suoi dati
• trace / notrace .
– abilita / disabilita la stampa di tutti i passaggi intermedi
(molto utile per seguire lo svolgersi del programma)
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Ordine dei predicati nelle regole
• Vedere l’esempio contenuto in prolog-1.pl
• Provare le query ( * è 1,2,3 e 4):
– pred*(pam, ann).
– pred*(pam, andrea).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Documentazione sul prolog
• Nel sito http://www.swi-prolog.org/pldoc/ c’è la
documentazione sulle varie regole già presenti in
prolog
• Simboli usati:
– + termine che deve essere già istanziato
– - termine che viene istanziato dalla regola
– ? termine che può o meno essere già istanziato
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esempi documentazione
• member(?Elem, ?List)
True if Elem is a member of List. The SWI-Prolog
definition differs from the classical one. Our definition
avoids unpacking each list element twice and provides
determinism on the last element
• get(+Stream, -Char)
Read the next non-blank character from Stream.
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizio
• Scrivere un programma Prolog che rappresenta un
grafo tramite il fatto edge(A,B) per indicare che A
e B sono connessi
b
a
c
d
e
f
• Interrogare il programma realizzato per avere tutti
i nodi raggiungibili partendo da b:
– ?- path(b, X).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Prolog
• È un linguaggio di programmazione logica
• È un linguaggio dichiarativo
• Si basa su una restrizione delle logica del primo
ordine (Horn Clauses)
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Linguaggio dichiarativo
• Indica “cosa” serve per arrivare alla soluzione
desiderata, ma non il “come”, cioè
l’implementazione utilizzata
• Si contrappone ai linguaggi imperativi e
procedurali (Java, C, C++, ecc)
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica