Programmazione Logica -- Lezione 12: Dichiarazioni di Delay in Prolog

Abbiamo visto che l'albero di risoluzione SLD puo' essere molto diverso a seconda della regola di selezione che scegliamo. In particolare, una certa regola puo' dar luogo ad un'albero con molti piu' rami -- alcuni dei quali magari infiniti -- di quello che si otterrebbe con un'altra regola.

In generale il grado di nondeterminismismo di un certo atomo nel goal (ossia il numero di figli che si ottendgono con un passo di risoluzione se selezionamo tale atomo) dipende da quanto e' instanziato il goal.

Esempio: Consideriamo il seguente programma logico:
p(a)
p(b) <- p(b)
q(a)
e consideriamo il goal <- p(x),q(x). Se usiamo la regola di selezione leftmost, otterremo un albero con due rami, uno di successo (con cas {x/a}), ed uno infinito. Se avessimo usato la regola di selezione rightmost, invece, avremmo avuto un abero finito e addirittura con un solo ramo (ovviamente di successo e con la stessa cas). Il motivo e' che la computazione di <- p(a) e' meno nondeterministica di quella di <- p(x), in quanto per risolvere <- p(a) possiamo usare solo la prima clausola, mentre per risolvere <- p(x) possiamo usare anche la seconda, e andare in ciclo.

In generale, sarebbe conveniente avere una regola di selezione piu' flessibile di quella del Prolog. Una regola che permetta di scegliere un atomo solo quando e' "abbastanza instanziato" e che riduca cosi' il grado di nondeterminimo e quindi la complessita' della ricerca delle soluzioni.

A tale scopo, nelle versioni di Prolog piu' moderne, quali il NU-Prolog, e' stata aggiunta la possibilita' di inserire in un programma le cosiddette dichiarazioni di delay. Una dichiarazione di delay e' un'espressione della forma:

DELAY p(x1,...,xn) UNTIL Cond(x1,...,xn)

dove p e' un predicato del programma, e Cond(x1,...,xn) una certa condizione logica.

Il significato di tale dichiarazione e' quello di modificare la regola di selezione (e quindi la semantica operazionale) del Prolog nel seguente modo:

Seleziona l'atomo p(t1,...,tn) piu' a sinistra tale che per ogni dichiarazione di delay della forma DELAY p(x1,...,xn) UNTIL Cond(x1,...,xn), vale che Cond(t1,...,tn) e' verificata.

Gli atomi piu' a sinistra dell'atomo selezionato con questa nuova regola, ossia quelli per i quali le corrispondenti condizioni non erano soddisfatte, si dicono sospesi o delayed. Essi rimangono nel goal, ma potranno essere selezionati in qualche passo successivo per effetto delle istanziazioni che si sono avute nel frattempo.

Esempio: Se nel programma precedente aggiungiamo una dichiarazione di delay della forma
DELAY p(x) UNTIL nonvar(x)
allora la nuova regola di selezione da' luogo ad un albero finito e con un solo ramo, che, in questo particolare caso, e' lo stesso che si sarebbe avuto con la regola rightmost.

Notiamo che la nuova regola introduce un terzo tipo di terminazione: la sospensione, che si ha quando tutti gli atomi del goal sono delayed. Ad esempio, con il programma precedente, e la suddetta dichiarazione di delay, il goal <- p(x) termina con sospensione, e non si ottiene neppure quindi il successo corrispondente alla cas {x/a}. Si puo' avere quindi una perdita di completezza rispetto alla semantica dichiarativa del Logic Programming.

Analogamente, con le dichiarazioni di delay si puo' perdere la proprieta' di invertibilita':

Esempio: Consideriamo un predicato binario p. Come sappiamo, in programmazione logica possiamo dare in input il primo argomento ed ottenere in output il secondo, o viceversa. Se pero' diamo una dichiarazione della forma
DELAY p(x,y) UNTIL nonvar(x)
allora in generale non potremo piu' usare tale predicato con la modalita' di output sul primo argomento.

Comunque, se usate in modo oculato, in Prolog le dichiarazioni di delay permettono addirittura di recuperare parte della completezza che si perde a causa della strategia depth-first del Prolog. Consideriamo il seguente esempio:

Esempio

Il seguente programma Prolog definisce il predicato perm(L1,L2) (L2 e' una permutazione di L2) e il predicato ausiliario delete(X,L1,L2) (L2 e' la lista che si ottiene eliminando X da L1)

perm([],[]). perm([X|L1],L2) :- delete(X,L2,L3), perm(L1,L3). delete(X,[X|L],L). delete(X,[Y|L1],[Y|L2]) :- delete(X,L1,L2).

L'interprete del Prolog standard, con la query ?- perm(L,[a,b])., genera entrambe le risposte L =[a,b], L =[b,a], e poi termina.

Se diamo invece la query ?- perm([a,b],L)., allora l'interprete genera la risposta L =[a,b], e poi va in ciclo.

Il problema e' che con la seconda query si arriva ad un certo punto a valutare un goal della forma ?- delete(b,L',L"), perm([],L").. Con la regola di valutazione leftmost, si cercano prima tutte le possibili soluzioni per delete(b,L',L"), e quindi si va in ciclo sulla quarta clausola. Notare che in tale ciclo si generano infinite soluzioni, di cui solo la prima va bene, cioe' e' compatibile con le soluzioni di perm([],L").

Se avessimo usato una dichiarazione di delay del tipo

DELAY delete(X,L1,L2) UNTIL nonvar(L1) OR nonvar(L2)

allora anche con la query ?- perm([a,b],L). l'interprete avrebbe generato entrambe le risposte L =[a,b], L =[b,a], e poi avrebbe terminato.

Esercizio: Verificare quanto affermato nell'esempio precedente costruendo l'albero SLD per le due query.

Nota: Certe implementazioni di Prolog, come il NU-Prolog, forniscono un pre-interprete che, esaminando la struttura del programma, genera automaticamente certe dichiarazioni di delay. L'idea naturalmente, e' quella di analizzare quali sono gli argomenti che controllano la possibilita' di scegliere una clausola ricorsiva, e di generare delle condizioni che richiedano che tali argomenti siano abbastanza istanziati. Nel caso dell'esempio precedente, il NU-Prolog avrebbe generato le dichiarazioni:

DELAY perm(L1,L2) UNTIL nonvar(L1) OR nonvar(L2) DELAY delete(X,L1,L2) UNTIL nonvar(L1) OR nonvar(L2)