Programmazione Logica -- Lezione 4: Alberi di ricerca SLD

Introduzione

Abbiamo visto che alcune caratteristiche della programmazione logica, che la distinguono da quella imperativa, sono: C'e' un'altra caratteristica che uno dovrebbe aver notato in quanto visto fin'ora: il nondeterminismo. La computazione di un goal, infatti, puo' avere molte refutazioni, ognuna associata ad una diversa risposta, e tutte valide ai fini della risoluzione del problema.

Il nondeterminismo e' dovuto alle varie possibilita' di scelta che si hanno durante il passo di computazione, e precisamente:

Ci sarebbe anche la scelta dell'mgu, visto che ce ne possono essere piu' d'uno. Pero' abbiamo visto che in realta' gli mgu sono tutti equivalenti, per cui non e' rilevante quale mgu scegliamo.

Vedremo che in realta', da un certo punto di vista, nemmeno la scelta dell'atomo e' rilevante. La vera sorgente di nondeterminismo e' la presenza di clausole alternative.

Alberi SLD

L'albero di ricerca per un goal, o SLD tree, e' un albero che esplora tutte le possibili derivazioni per una fissata regola di selezione degli atomi nel passo di derivazione.
Definizione
Una regola di selezione e' una regola che, in ogni goal di una derivazione, indica qual'e' l'atomo selezionato. Cioe' e' una funzione che associa ad ogni goal (in una derivazione), un certo atomo fra quelli che vi compaiono.
Definizione
Siano dati un programma P, un goal iniziale G0, ed una regola di selezione R. L'albero di ricerca per G0 in P, rispetto ad R, e' un albero T cosi' definito:
Gli alberi di ricerca si dicono anche alberi SLD, che vuol dire: "Linear resolution for Definite clauses with Selection rule".

Notare che un albero SLD puo' essere anche infinito, cioe' puo' avere rami infiniti. Essi corrispondono a derivazioni infinite. I percorsi radice-foglia corrispondono invece a derivazioni di successo o di fallimento.

Diremo che un albero e' finitamente fallito se e' finito e tutte le foglie rappresentano fallimenti.

Esempio
Consideriamo il programma
p(x) <- q(x), r(x)
q(f(a,y))
q(g(z)) <- q(z)
r(f(w,b))
Consideriamo varie regole di selezione, e vediamo come sono fatti gli alberi corrispondenti per il goal <- p(x):
La seguente proposizione esprime l'indipendenza dalla regola di selezione, almeno per quanto riguarda i successi:
Proposizione (Indipendenza dalla regola di selezione per i successi)
Siano T1 e T2 due alberi SLD per lo stesso programma e goal iniziale, ma con regole di selezione diverse. Si ha che ogni ramo di successo in T1 corrisponde and un ramo di successo in T2, con la stessa cas (a meno di renaming), e viceversa.
Per quanto riguarda i fallimenti, invece, non si ha una corrispondenza cosi' precisa. Addirittura puo' succedere che una regola generi un albero finitamente fallito, mentre un'altra ne generi uno infinito, come si puo' vedere nel seguente esempio:
Esempio
Consideriamo il programma
p(x) <- q(x), r(x)
q(a) <- q(a)
r(b)
La regola leftmost per il goal <- p(x) genera un albero infinito, mentre la regola rightmost genera un albero finitamente fallito.
Vale comunque che, se ci restringiamo alle regole fair, cioe' alle regole che selezionano, prima o poi, tutti gli atomi di una derivazione, allora gli alberi SLD sono tutti equivalenti anche dal punto di vista dei fallimenti:
Proposizione
I fallimenti finiti sono molto importanti per la definizione della negazione in programmazione logica, che e' un argomento che vedremo in seguito.

Strategia di ricerca dell'interprete Prolog

L'interprete Prolog adotta la regola di selezione leftmost, che non e' una regola fair.

Come abbiamo visto, ogni albero SLD genera le stesse soluzioni, ma alcuni rami possono essere infiniti. Per trovar tutte le soluzioni, quindi, occorrerebbe visitare l'albero per livelli.

L'interprete Prolog non effettua la visita per livelli, ma bensi effettua la cosiddetta visita depth first, cioe' visita prima il ramo sinistro, in profondita', poi riconsidera l'ultima scelta e segue la diramazione immediatamente a destra, eccetera. Se uno dei rami e' infinito l'interprete diverge seguendo quel ramo, e le eventuali soluzioni piu' a destra non vengono mai trovate. La strategia del Prolog e' quindi incompleta, cioe' non trova necessariamente tutte le cas.

La ragione per cui il Prolog adotta una regola unfair e una strategia depth first e' essenzialmente per motivi di efficienza: un programmatore esperto riesce a sfruttare queste caratteristiche dell'interprete per rendere la ricerca piu' veloce. Inoltre la strategia depth first permette di definire il cut, che e' un meccanismo che vedremo in seguito, per controllare la ricerca della soluzioni.

E' chiaro che queste caratteristiche allontano il Prolog da quello che era l'ideale di Kowalski di liberare totalmente il programmatore dal doversi preoccupare del controllo.

Esempio
Consideriamo il programma della lezione scorsa che definisce un albero genealogico, e consideriamo tre modi alternativi di definire il predicato antenato
P1
antenato(x,y) <- genitore(x,y)
antenato(x,y) <- genitore(x,z), antenato(z,y)
P2
antenato(x,y) <- genitore(x,y)
antenato(x,y) <- antenato(x,z), genitore(z,y)
P3
antenato(x,y) <- antenato(x,z), genitore(z,y)
antenato(x,y) <- genitore(x,y)
Si ha che con P1 l'albero e' finito e quindi l'interprete Prolog trova tutte le soluzioni in tempo finito. Con P2 si ha un albero che contiene un ramo infinito, ma per fortuna e' quello piu' a destra. Quindi l'interprete Prolog trova tutte le soluzioni (in tempo finito) e poi diverge. Con P3, invece, si ha un albero il cui ramo piu' a sinistra e' infinito. Quindi l'interprete Prolog diverge subito e non trova nessuna soluzione.