Esercizio - Prolog - fatti, regole e alberi SLD (laboratorio 4)

Punto 1: colleghi

colleague(emp1, emp2): il goal si unifica con la testa ($X = emp1$, $Y = emp2$); il corpo diventa work(emp1,Z), work(emp2,Z). work(emp1,Z) dà $Z = deepmind$ (clausola 1); work(emp2,deepmind) è un fatto: true.

colleague(emp1, emp3): work(emp1,Z) dà $Z = deepmind$; work(emp3,deepmind) non esiste (work(emp3, ibm) ha un'azienda diversa): fallimento. work(emp1,Z) non ha altre soluzioni: false.

Tutte le coppie colleague(X,Y): per ogni fatto work(X,Z) si cercano tutti gli work(Y,Z) con la stessa azienda. Output (verificato):

X = emp1, Y = emp1 ;  X = emp1, Y = emp2 ;
X = emp2, Y = emp1 ;  X = emp2, Y = emp2 ;
X = emp3, Y = emp3 ;  X = emp3, Y = emp4 ;
X = emp4, Y = emp3 ;  X = emp4, Y = emp4

Otto risposte: i $2 \cdot 2$ per deepmind e i $2 \cdot 2$ per ibm. Quattro sono le coppie banali ($X = Y$): la regola dice solo "stessa azienda", e ogni persona lavora per la propria azienda. Correzione con \= (non unificano):

colleague(X,Y) :- work(X,Z), work(Y,Z), X \= Y.

Ora colleague(X,Y) dà $4$ risposte: (emp1,emp2), (emp2,emp1), (emp3,emp4), (emp4,emp3). X \= Y va dopo work(...): con le variabili ancora libere $X$ e $Y$ unificherebbero e il controllo fallirebbe sempre.

Punto 2: mangiare

• ?- likes(john, pizza). Nessuna clausola di likes ha $john$ e $pizza$ insieme: false.
• ?- eats(john, X). Corpo: likes(john, X), food(X). likes(john, X) si unifica con likes(john, icecream), $X = icecream$ (la clausola likes(antonio, Thing) non si unifica: $john \neq antonio$); food(icecream) è un fatto: X = icecream. Nessun'altra soluzione.
• ?- eats(antonio, X). likes(antonio, X) si unifica con likes(antonio, Thing): $Thing$ è una variabile del fatto, quindi X resta libera (le due variabili sono identificate). Poi food(X) è il goal rimasto: prova food(pizza) ($X = pizza$, risposta) e al ritorno food(icecream) ($X = icecream$, altra risposta): X = pizza ; X = icecream.
• likes(antonio, Thing). è un fatto con variabile: significa $\forall Thing\ likes(antonio, Thing)$, Antonio ama qualsiasi cosa. Per questo eats(antonio, X) restituisce tutti i cibi.

Query aperta eats(P, T) (verificata): P = mary, T = pizza ; P = antonio, T = pizza ; P = antonio, T = icecream ; P = john, T = icecream.

Punto 3: grampa

?- grampa(tommaso, bianca). Unificazione con la testa: $X = tommaso$, $Y = bianca$. Corpo: parent(tommaso,Z), parent(Z,bianca).

1. parent(tommaso,Z): clausola 1, $Z = francesca$.
2. parent(francesca,bianca): non c'è nessuna clausola di parent con $francesca$ e $bianca$: fallisce. Backtracking: si disfa $Z = francesca$.
3. parent(tommaso,Z): clausola 2, $Z = vittorio$.
4. parent(vittorio,bianca): clausola 4, riesce. Risposta true.

?- grampa(tommaso, Who). Albero di ricerca (la variabile Who finisce unificata con Y):

grampa(tommaso, Who)
  | regola: {X = tommaso, Y = Who}
parent(tommaso, Z), parent(Z, Who)
  |- Z = francesca  -> parent(francesca, Who) -> Who = linda     (successo 1)
  |- Z = vittorio   -> parent(vittorio, Who)  -> Who = bianca    (successo 2)

La ricerca è in profondità: prima il ramo $Z = francesca$ fino al successo Who = linda; con ; si ritorna indietro e si prova $Z = vittorio$: Who = bianca. Il goal parent(francesca, Who) ha una sola soluzione ($linda$), quindi niente altri rami. La query grampa(X,Y) aperta dà (tommaso, linda) e (tommaso, bianca).

sibling e cousin (aggiunte nostre, nello stesso stile):

sibling(X,Y) :- parent(P,X), parent(P,Y), X \= Y.
cousin(X,Y)  :- parent(A,X), parent(B,Y), sibling(A,B).

• sibling(X,Y): due persone con lo stesso genitore e diverse. Risposte: (francesca, vittorio) e (vittorio, francesca).
• cousin(X,Y): figli di due fratelli. Risposte: (linda, bianca) e (bianca, linda), perché sibling(francesca, vittorio) e parent(francesca, linda), parent(vittorio, bianca).

Punto 4: backtracking con due sotto-obiettivi

?- likes(mary,X), likes(john,X). (si cerca ciò che piace a entrambi).

1. likes(mary,X): clausola 1, $X = food$.
2. likes(john,food): nessuna clausola (le clausole 3 e 4 hanno $beer$ e $wine$): fallisce. Ritorno indietro, si disfa $X = food$.
3. likes(mary,X): clausola 2, $X = wine$.
4. likes(john,wine): clausola 4, riesce. Risposta X = wine.

Dopo la risposta, con ;, Prolog ritorna ancora: likes(mary,X) non ha altre clausole, la ricerca finisce: false. L'unica soluzione è $X = wine$.