ESERCIZI PROLOG
Esercizio 1 (un po' complesso)
Fare in PROLOG l'esercizio 12 di Programmazione Haskell
Esercizio 2
Si consideri il seguente programma PROLOG. Esso determina se,
dato un grafo orientato ed aciclico
(rappresentato tramite un predicato myGraph tra nodi) e
due nodi, esiste un cammino tra i due.
path(X,X).
path(X,Y) :- myGraph(X,Z), path(Z,Y).
Modificare il programma in modo tale che si possa sapere, non solo
se esiste un cammino tra due nodi, ma anche quali sono i possibili cammini.
Soluzione.
Esercizio 3
Definire la funzione fattoriale come predicato PROLOG.
Soluzione.
Esercizio 4
Esiste un grado di parentela tra due persone se queste
sono discendenti di una stessa persona.
Il grado di parentela di due persone e' la somma delle distanze
(nell'albero genealogico)
tra le due persone e la prima di cui sono entrambe discendenti.
Scrivere un programma Prolog che calcoli, se esiste, il grado di parentela
di due persone (supponendo di avere una base di dati di fatti del tipo
"parent(tizio,caio)." che indicano che tizio e' figlio di caio).
Soluzione.
Esercizio 5
Si supponga di avere una base di dati composta
da asserzioni del tipo
parent(tizio, caio).
che indicano che tizio e' figlio di caio.
Scrivere un programmino Prolog per controllare
se due persone sono cugini.
Scrivere una query la cui valutazione permetta di
ricavare tutti i cugini di Roberto, eventualmente anche
con ripetizioni. Se il programma potrebbe produrre delle ripetizioni,
indicare quali potrebbero essere le cause di output ripetuti.
Soluzione.
Esercizio 6
Uno dei meccanismi fondamentali di un interprete Prolog
e' l'utilizzo dell'algoritmo di unificazione.
Tale algoritmo non e' niente altro che la generalizzazione
a termini prolog dell'algoritmo Unify utilizzato
nell'algoritmo di Principal Pair (pp) per il lambda
calcolo tipato a' la Curry.
Estendere l'algoritmo Unify ai termini Prolog.
Esercizio 7
Definire in Haskell i tipi di dato "termine Prolog"
e "sostituzione". Implementare poi l'algoritmo sviluppato
nell'esercizio 6.
Esercizio 8
Si consideri il seguente programma Prolog per calcolare
l'altezza di un albero binario etichettato con etichette
che sono atomi:
max(N1,N2,N1):- N1>N2.
max(_,N2,N2).
altezza(X,1):- atom(X).
altezza(node(_,Subtree1,Subtree2),N):- altezza(Subtree1,N1),
altezza(Subtree2,N2),
max(N1,N2,M),
N is M+1.
Se ora calcoliamo l'altezza dell'albero
node(a,node(a,a,a),node(a,node(a,a,a),a))
attraverso la query
?- altezza(node(a,node(a,a,a),node(a,node(a,a,a),a)),X).
otteniamo non uno, ma ben due valori per l'altezza:
X = 4 ;
X = 3.
Perche'?
Modificare il programma in due modi differenti in modo che
in entrambi i casi il calcolo dell'altezza restituisca l'unico valore
corretto.
Soluzione.
Esercizio 9
Scrivere un programma Prolog che determini se esiste una soluzione
del problema del contadino che dovendo attraversare il fiume
con una barca a due posti ed avendo con se una capra, un cavolo ed un lupo,
deve evitare di lasciare da soli lupo e capra oppure capra e cavolo.
Esercizio 10
Scrivere un programma Prolog che risolva il problema dell'esercizio 9,
ma fornendo anche le sequenze di spostamenti che risolvono il problema.
Possibile soluzione.
Esercizio 11 (non banale)
Definire l'algoritmo di unificazione per i tipi del Lambda-calcolo tipato semplice. Modificare tale algoritmo per poterlo applicare ai termini del PROLOG.
Soluzione.
Esercizio 12
Supponiamo di avere i tipi del lambda calcolo a' la Church (con solo int e real come
tipi base ed i tipi freccia). Scrivere un programma PROLOG che ci dica
se un tipo e' sottotipo di un altro.
Possibilmente fare in modo che il programma,
in caso di risposta affermativa (true), produca solo questa, evitando cioe' che possa produrre anche
la risposta 'false'. Giustificare tale caratteristica.
Possibile soluzione.
Esercizio 13
Si consideri la seguente rappresentazione in PROLOG di formule ben formate
della logica proposizionale:
- con letterali p, q, etc. rappresentiamo le
variabili proposizionali;
- con neg() rappresentiamo un'implicazione;
- con implies(,) rappresentiamo un'implicazione;
- con and(,) rappresentiamo una congiunzione;
- con or(,) rappresentiamo una disgiunzione.
(esempio: la proposizione p→(p/\q) e' rappresentata
dal termine implies(p,and(p,q)) ).
Scrivere un programma PROLOG che, presa la rappresentazione di
una proposizione ed un insieme di fatti che rappresenti il valore
di verita' delle sue variabili proposizionali
(della forma truth_value(p,0) o truth_value(p,1) ), permetta di stabilirne
il valore di verita'.
Possibile soluzione.
Esercizio 14
Descrivere l'uso dell'algoritmo di unificazione nella valutazione
di programmi PROLOG.
Esercizio 15
Nel programma del corso e' descritto un programma che calcola
l'insieme dei cammini tra due nodi di un grafo non orientato.
Tale programma utilizza un argomento che contiene i nodi visitati.
Scrivere un programma prolog che non utilizzi un argomento per i nodi visitati.
Possibile soluzione.
Esercizio 16
Il seguente codice Prolog dovrebbe calcolare
i numeri di Fibonacci.
Dopo aver trovato la soluzione pero' il programma ne cerca una seconda e va in loop.
Perche'?
Modificare il programma in modo che restituisca solo la soluzione corretta,
giustificando le modifiche fatte.
fib(0,1).
fib(1,1).
fib(N,M) :- P is N-1, Q is N-2, fib(P,N1), fib(Q,N2), M is N1+N2.
Soluzione.
Esercizio 17
Si consideri il seguente insieme di fatti
e la seguente query
b(1).
b(2).
c(1).
c(2).
?- a(X).
Si dica, per ognuna delle seguenti clausole, cosa produce l'interprete Prolog
se aggiunte all'insieme dei fatti.
1. a(X) :- b(X), c(X).
2. a(X) :- b(X),!, b(_), c(X).
3. a(X) :- b(_),!, b(X), c(X).
4. a(X) :- b(_),!, b(X), c(_).
5. a(X) :- \+b(3), X is 3.
motivandone la risposta
Soluzione.
Esercizio 18
Si consideri il seguente insieme di fatti PROLOG.
c(1).
c(2).
d(1).
d(2).
e(3).
e(4).
f(3).
f(4).
Descrivere il risultato prodotto dall'interprete PROLOG (giustificando le risposte)
per il seguente goal
?- p(X,Y).
prendendo in considerazione i seguenti insiemi di fatti.
1.
p(X,Y) :- a(X),b(Y).
a(X):- c(_),!,d(X).
b(X):- e(X),!,f(X).
b(X):- f(_).
2.
p(X,Y) :- a(X),b(Y).
a(X):- c(_),!,d(X).
b(X):- e(X),f(X).
3.
p(X,Y) :- a(X),!,b(Y).
a(X):- c(_),d(X).
b(X):- e(X),f(X).
Possibile soluzione.
Esercizio 19
Le seguenti clausole Prolog sono parte del codice
Map Coloring II presente sulla pagina
del programma del corso.
La query
?- find_regions(listaDiAdiacenza,[],R)
restituisce la lista dei nodi del grafo descritto tramite una "listaDiAdiacenza".
(Notare come per questo problema non si sfrutti in alcun modo il meccanismo del Backtracking,
e come praticamente sia molto simile ad un programma funzionale.)
find_regions([],R,R).
find_regions([[X,Y]|S], R,A) :-
(member(X,R) ->
(member(Y,R) -> find_regions(S,R,A) ; find_regions(S,[Y|R],A)) ;
(member(Y,R) -> find_regions(S,[X|R],A) ; find_regions(S,[X,Y|R],A) ) ).
E' un classico esempio di programma Prolog che utilizza un argomento come accumulatore,
simulando cosi' una variabile imperativa che viene modificata durante il programma.
Questo modo di programmare, come la ricorsione di coda in programmazione funzionale,
permette di avere programmi piu' efficienti (ma meno chiari).
Scrivere la versione Haskell, utilizzando ricorsione di coda, del codice Prolog
descritto sopra
e farne poi una versione con ricorsione non di coda.
Fare poi di quest'ultima una versione in Prolog.
Possibile soluzione.
Esercizio 20
Si consideri il seguente insieme di fatti e le seguenti clausole
Prolog che definiscono le relazioni di genitore, nonno, fratello e cugino
genitore(roberto,gianni).
genitore(paola,gianni).
genitore(gianni,melo).
genitore(francesco,melo).
genitore(luigi,melo).
genitore(meloJun,roberto).
genitore(giacomo,francesco).
genitore(mario,francesco).
genitore(anna,paola).
genitore(foleman,luigi).
nonno(X,Y):-genitore(Z,X),genitore(Y,Z).
fratello(X,Y):- genitore(X,Z),genitore(Y,Z),X\==Y.
cugino(X,Y):- nonno(Z,X),nonno(Z,Y),not(fratello(X,Y)),X\==Y.
Alla query
?- cugino(roberto,Y).
l'interprete Prolog risponde, correttamente:
Y = giacomo ;
Y = mario ;
Y = foleman ;
false.
Se invece cambiamo la clausola che definisce la relazione cugino,
semplicemente permutando i suoi subgoal nel modo seguente
cugino(X,Y):- not(fratello(X,Y)),X\==Y,nonno(Z,X),nonno(Z,Y).
alla stessa query
?- cugino(roberto,Y).
l'interprete Prolog risponde invece solo:
false.
Perche'?
Possibile soluzione.
Esercizio 21
Scrivere un programma PROLOG che riconosca o rifiuti stringhe appartenenti al linguaggio
regolare, sull'alfabeto {a,b,c}, associato alla seguente espressione regolare
abc*b + aa(bb)*c*
Per semplicita' rappresentiamo una stringa con una lista di atomi (aacb verra' rappresentata dalla lista [a,a,c,b]).
Possibile soluzione.
Esercizio 22
Si considerino le seguenti definizioni Haskell
data Yunz = Yor | Frunz Int Int Yunz Yunz
usable Yor = False
usable (Frunz n m y1 y2) = (n==276)||(m==276)||(usable y1)||(usable y2)
Scrivere un programma PROLOG che definisca il predicato usable.
(Fare in modo possibilmente che il predicato restituisca solo un valore di verita'
anche nel caso un elemento contenga il numero 276 piu' di una volta, giustificando
la soluzione proposta).
Possibile soluzione.(by alex180788)
Esercizio 23
Supponendo di voler implementare in Prolog il type checker di FJ,
scrivere la clusole Prolog relative alla parte di programma corrispondente
alla seguente regola FJ:
Per semplicita' si supponga di avere gia' delle clausole per mtype e per
controllare se una classe e' definita nella Class Table attraverso l'uso di extends
Si assuma inoltre che tutti i metodi siano unari.
Possibile soluzione.
Esercizio 24
animal(lion).
animal(sparrow).
animal(X) :- bird(X).
has_feathers(sparrow).
bird(eagle).
bird(X) :-
animal(X),
has_feathers(X).
Il programma prolog appena definito, sulla query
?-bird(X).
entra in loop, restituendo infinite volte il valore sparrow.
Perche'?
Modificare il programma, mantenendo gli stessi fatti, in modo che
cio' non accada.
Possibile soluzione.
Esercizio XX
Possibile soluzione.