Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Ernesto Burattini » 6.Il Prolog - 2


Esecuzione di un programma in Prolog

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 .

Esecuzione di un programma in Prolog (segue)

| ?- father(albert, john).

| ?- sister(paul, X).

| ?- sister(paul, X), mother(X, Y).

Esecuzione di un programma in Prolog (segue)

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.

Controllo del backtracking

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.

Controllo del backtracking

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).

Controllo del backtracking (segue)

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, !.

Controllo del backtracking (segue)

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).

Controllo del backtracking (segue)


Controllo del backtracking (segue)


Modifica dinamica dei programmi

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).

Modifica dinamica dei programmi (segue)

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.

Modifica dinamica dei programmi (segue)

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).

Modifica dinamica dei programmi (segue)

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(_).

Modifica dinamica dei programmi (segue)

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(_).

Modifica dinamica dei programmi (segue)

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(_).

Modifica dinamica dei programmi (segue)

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(_).

Modifica dinamica dei programmi (segue)

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).

Modifica dinamica dei programmi (segue)

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.

Modifica dinamica dei programmi (segue)

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.

Findall e forall

forall(robot(_,_,_,_,Robot), muovi_robot(W,N,Robot))

findall(N,neuron(N,_,_,_,_,in),In)


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion