Programmazione Logica -- Lezione 4: Alberi di ricerca SLD
Introduzione
Abbiamo visto che alcune caratteristiche della programmazione logica,
che la distinguono da quella imperativa, sono:
- manipolazione simbolica
- computazione di vincoli fra variabili
- invertibilita' degli argomenti
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:
- la scelta dell'atomo nel goal (atomo selezionato)
- la scelta della clausola fra quelle la cui testa unifica con
l'atomo selezionato
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:
- I nodi di T sono goals, e la radice e'
il goal iniziale
- Ogni nodo G ha come figli tutti i goal
che si ottengono con un passo di derivazione da
G, avendo fissato l'atomo selezionato
secondo R. Tali figli sono ordinati da
sinistra a destra secondo l'ordine in cui sono scritte, in
P, le clausole utilizzate nei passi di
derivazione.
- Ogni foglia e' un goal vuoto (successo) o un goal di fallimento.
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):
- Regola leftmost, che sceglie sempre l'atomo piu' a
sinistra nel goal. Con tale regola, si ottiene un albero SLD che
ha un ramo di successo con cas {x/f(a,b)}, e un ramo infinito.
- Regola rightmost, che sceglie sempre l'atomo piu' a
destra. Con tale regola, si ottiene un albero SLD che
ha un solo ramo, di successo, con cas {x/f(a,b)}.
- Regola alternante, che sceglie prima l'atomo piu' a
sinistra, poi il secondo piu' a sinistra, eccetera, fino ad
arrivare a quello piu' a destra, poi di nuovo quello piu' a
sinistra, eccetera. Con tale regola, si ottiene un albero SLD che
ha due rami: uno di successo, con cas {x/f(a,b)}, e uno di fallimento.
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
-
- Siano T1 e T2
due alberi SLD per lo stesso programma e goal iniziale, con
regole di selezione diverse, ma entrambe fair.
Si ha che T1 e' finitamente fallito se e solo
se T2 lo e'.
- Se per un certo programma e goal iniziale
esiste un albero SLD finitamente fallito, allora tutti gli alberi con
regola fair lo sono.
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.