Verifica di una collezione di goal rispetto a un dato programma.
La verifica è fatta in accordo all’Algoritmo di Risoluzione (Prolog engine o Resolution mechanism).
L’input a questo algoritmo è un programma (collezione di predicati) e una query (uno o più goal).
L’output sarà successo o fallimento a seconda se la validità della query iniziale potrà essere verificata o meno
Nel caso la query contenga delle variabili e possa essere verificata, l’algoritmo mostrerà particolari valori delle variabili che rendono la query valida.
La lezione è stata curata in collaborazione con il Prof. Massimo De Gregorio .
| ?- father(albert, john).
| ?- sister(paul, X).
| ?- sister(paul, X), mother(X, Y).
Possiamo vedere l’esecuzione di un programma Prolog come un problema di ricerca e la rappresentazione del trace come un albero. L’obiettivo, quindi, dell’algoritmo è di trovare una soluzione (se esiste) nello spazio di ricerca.
Depth-first e backtracking
Poiché i predicati possono essere ricorsivi, una ricerca breadth-first avrebbe il vantaggio di trovare sempre una soluzione se esiste. D’altro canto, una ricerca depth-first dello stesso albero potrebbe non terminare quando, per esempio, le clausole ricorsive sono provate per prime.
Il backtracking agisce automaticamente sul fallimento per soddisfare un goal. Sebbene questa operazione è essenziale per la procedura di ricerca usata dal Prolog, essa può anche portare a delle inefficienze (ad esempio, trovare soluzioni alternative a un goal che può essere soddisfatto solo una volta). In questi casi, sarebbe molto utile ai programmatori indicare che il backtracking non deve agire.
Il Prolog rende disponibile un meccanismo per il controllo del backtracking: il cut.
Il cut è un goal. Esso ha successo immediatamente appena si incontra in una clausola. Però, facendo ciò, rimuove tutti i punti di backtracking tra l’inizio del predicato e se stesso.
q(X, Y) :- a(X), b(Y).
q(X, Y) :- c(X), !, d(Y).
q(X, Y) :- e(X, Y).
Green cut
Predicati definiti da più clausole in cui esattamente una sola clausola può avere successo (mutuamente esclusive).
Prima
max(A, B, A) :- A >= B.
max(A, B, A) :- B >= A.
Dopo
max(A, B, A) :- A >= B, !.
max(A, B, A) :- B >= A, !.
Red cut
Quando il cut è introdotto per evitare o saltare la verifica di un goal. La semantica del programma è alterata (non produce lo stesso risultato con e senza cut).
I programmi, una volta caricati – consult – in Prolog, sono statici. Una volta che un insieme di fatti e regole è stato caricato in Prolog, questo insieme non può essere modificato durante l’esecuzione del programma (l’unica eccezione, ovviamente, è un nuovo caricamento del programma – reconsult).
Il Prolog mette a disposizione predicati il cui scopo è di aggiungere o rimuovere clausole. Una volta modificato in questo modo, la forma originale del predicato è persa e la nuova forma è mantenuta fino a ulteriori modifiche.
Programmi che aggiungono e rimuovono clausole in questo modo introducono effetti collaterali: la loro esecuzione causa cambiamenti che possono modificare future esecuzioni (chiamate che hanno successo in un determinato punto possono, in seguito, fallire o aver successo un numero differente di volte).
Programmi che adottano queste tecniche sono estremamente difficili da seguire, modificare e da inspezionare (debug).
assert(Clause)
aggiunge una clausola alla fine delle clausole di un predicato
assert( (p(X) :- q(X, Y), r(Y)) ).
assert( p(pippo) ).
assert( p(_) ).
p(X) :- q(X, Y), r(Y).
p(pippo).
p(_).
asserta(Clause)
aggiunge una clausola all’inizio delle clausole di un predicato
assert( (p(X) :- q(X, Y), r(Y)) ).
asserta( p(pippo) ).
assert( p(_) ).
p(pippo).
p(X) :- q(X, Y), r(Y).
p(_).
assertz(Clause)
aggiunge una clausola alla fine delle clausole di un predicato
assert( (p(X) :- q(X, Y), r(Y)) ).
assertz( p(pippo) ).
assert( p(_) ).
p(X) :- q(X, Y), r(Y).
p(pippo).
p(_).
retract(Clause)
rimuove una clausola di un predicato
assert( (p(X) :- q(X, Y), r(Y)) ).
assert( p(pippo) ).
assert( p(_), 2 ) .
retract( p(pippo) ).
p(X) :- q(X, Y), r(Y).
p(_).
retractall(Head)
rimuove tutte le clausole la cui testa è Head
assert( (p(X) :- q(X, Y), r(Y)) ).
assert( p(pippo) ).
retractall( p(_) ).
assert( p(pluto) ).
p(pluto).
Per poter manipolare i predicati usando assert e retract i predicati devono essere dinamici.
I predicati creati a runtime sono dinamici.
Quando i predicati sono consultati da un file, per poterli modificare devono essere resi dinamici esplicitamente.
:- dynamic fratello/2, append/3.
Cosa succede se eseguiamo la seguente query?
| ?- retract(X), fail.
La query ovviamente fallisce ma l’effetto collaterale è quello di rimuovere tutte le clausole dinamiche dal programma.
1. Introduzione
4. Esempi di applicazione del paradigma gerarchico
11. Schema Theory
13. Architetture Reattive a Sussunzione
14. Architetture a Campi di Potenziale
15. Architetture a Campi di Potenziale e Sussunzione
16. Progettazione di un sistema Reattivo - 1
17. Progettazione di un sistema Reattivo - 2
18. Progettazione di un sistema Reattivo - 3