Siano dati i fatti:
% file: backtracking/es1.pl persona(paolo). persona(giulio). persona(luca).
?- persona(X).
%file: backtracking/es2.pl
maschio(paolo). /* fatto 1 */
femmina(francesca). /* fatto 2 */
uomo(X) :- /* regola 1 */
persona(X).
persona(Y) :- /* regola 2 */
maschio(Y).
persona(Z) :- /* regola 3 */
femmina(Z).
Dopo avre consultato i fatti e le regole precedenti, usate il
trace
per vedere come il Prolog risponde alla domanda:
?- uomo(francesca).
N
mediante una funzione fact(N,X) che restituisce in
X il risultato. Volendo definire a parole il funzionamento
della funzione fattoriale potremmo dire:
N=0 e N>0. Occorrer quindi in Prolog scrivere
due regole in modo tale che il calcolo del fattoriale in base al
prodotto dei numeri venga effettuato solo
nel caso che N sia diverso da 0.
Il programma il seguente:
fact(0,1):-!. fact(N,X):-M is N-1,fact(M,Y),X is Y*N.In questo programma, la seconda regola , è tra l'altro, un esempio di definizione ricorsiva. Dal momento che l'interprete scorre il database dall'alto verso il basso, viene prima considerato il caso di
N=0 e poi
(solo se N>0) il caso generale codificato dalla seconda regola.
Vediamo ora qual' è il significato del cut nella prima regola.
Supponiamo che il Prolog effettui un backtracking e vada a riconsiderare
l'applicazione della regola fact nel caso
di N=0; la seconda regola risulta applicabile anche per
N=0 a meno che la sua applicazione non venga inibita
esplicitamente. Il cut nella prima regola ha proprio questo effetto, in quanto
costringe l'interprete a mantenere per le variabili le scelte fatte durante
l'applicazione della prima regola.
In queste situazioni, ovvero quando il suo
uso ha lo scopo di comunicare al sistema che stata trovata la regola giusta
e che non devono essere
effettuati altri tentativi, il cut può essere sostituito dal predicato
not.
not è un predicato
di sistema (e quindi direttamente disponibile per l'utente) tale che il
goal not(X) è verificato se X fallisce.
A titolo di esempio riscriviamo il programma per il calcolo del
fattoriale utilizzando il predicato not.
fact(0,1). fact(N,X):- not(N=0),M is N-1,fact(M,Y),X is Y*N.In generale è buona norma sostituire il cut in questo modo in quanto la leggibilità del programma diventa decisamente migliore. Alcune volte per la sostituzione può causare un aumento del carico computazionale perchè l'interprete è costretto a valutare più volte lo stesso goal, come, per esempio, nel caso delle seguenti regole:
r:-goal1,goal2. r:-not(goal1),goal3.in cui
goal1 deve essere valutato due volte.
Utilizzando il cut, invece si ha:
r:-goal1,!,goal2. r:-goal3.In questo caso
goal1 viene valutato una sola volta.
Controlla, usando l'interprete Prolog, l'equivalenza delle due versioni di
fact,
quella che usa il cut e quella che usa il not.
NotaIl Prolog usato in Prolog Lab non usa il predicato not.
Al suo posto viene usato \+.
\+ P coincide con not(P).
Spiegare perche' non si può usare semplicemente la definizione:
fact(0,1). fact(N,X):- M is N-1,fact(M,Y),X is Y*N.(cosa succede nel caso che si forzi il backtrackig del goal
?- fact(0,X))?
%file: cut/es1.pl %versione di fact che usa il cut fact1(0,1):-!. fact1(N,X):-M is N-1,fact1(M,Y),X is Y*N. %versione di fact che usa il not %osservate che not(P) viene scritto come \+ p fact2(0,1). fact2(N,X):- \+ N=0,M is N-1,fact2(M,Y),X is Y*N. %versione ingenua (ma sbagliata) di fact fact3(0,1). fact3(N,X):- M is N-1,fact3(M,Y),X is Y*N. /* Possibili goal: ?- fact1(4,X). ?- fact2(4,X). ?- fact3(4,X). Per forzare il backtracking usare "solutions=all". se il prolog non risponde perche' e caduto in un loop senza fine (quando accadra'?) usare "kill". */
fail per dire all'interprete che quando arriva
in quel particolare punto deve interrompere ogni tentativo di verificare
quel goal.
fail è un predicato di sistema privo di argomenti ed
è definito
in maniera tale che, considerato come goal, fallisce
sempre e causa pertanto l'inizio di un backtracking.
Quando il fail viene incontrato
dopo un cut, però, l'azione del backtracking viene alterata.
Illustriamo con un esempio il
significato di questo meccanismo. Supponiamo di voler codificare
una serie di requisiti per valutare l'attitudine di una persona
per un certo lavoro e che un requisito essenziale sia
un'età di almeno 30 anni.
puo_lavorare(X):-eta(X,Y),Y<30,!,fail.
puo_lavorare(X):-laureato(X),militesente(X),
eta(X,Y),Y<40.
puo_lavorare(X):-media(X),pensionato(X).
pensionato(X):-eta(X,Y),Y>65.
militesente(X):-sesso(X,f).
militesente(X):-congedato(X).
eta('Rossi',25).
eta('Bianchi',53).
...
Questo programmino codifica appunto una ricerca di personale.
Un candidato deve avere
più di 30 anni; nel caso abbia meno di 40 anni deve essere
laureato e militesente; nel caso che sia
pensionato basta la licenza media.
puo_lavorare.
Se non fosse stato introdotto il cut, il backtracking avrebbe proseguito
con le regole successive; la seconda regola ad esempio, può benissimo
essere soddisfatta anche se l'età del
candidato è 25 anni.
%file: cut/es2.pl
% se ha meno di 30 anni non puo' lavorare
puo_lavorare(X):-eta(X,Y),Y<30,!,fail.
% se e' laureato, miletesente,e l'eta' e' inferiore a 40 anni puo' lavorare
puo_lavorare(X):-laureato(X),militesente(X),
eta(X,Y),Y<40.
% se e' pensionato basta la licenza media
puo_lavorare(X):-media(X),pensionato(X).
% e' un pensionato se l'eta' e superiore a 65 anni.
pensionato(X):-eta(X,Y),Y>65.
% militesente se di sesso femminile
militesente(X):-sesso(X,f).
% militesente se congedato
militesente(X):-congedato(X).
% eta
eta('Rossi',25).
eta('Bianchi',53).
eta('Verdi',70).
eta('Gatti',72).
eta('Negri',42).
eta('Fabbri',35).
eta('Ferrari',36).
% congedato
congedato('Ferrari').
% sesso
sesso('Rossi',f).
sesso('Bianchi',m).
sesso('Verdi',m).
sesso('Gatti',f).
sesso('Negri',m).
sesso('Fabbri',f).
sesso('Ferrari',m).
% laureato
laureato('Fabbri').
laureato('Ferrari').
% media
media('Gatti').
/*
Possibili goal:
?- puo_lavorare('Rossi').
?- puo_lavorare('Bianchi').
?- puo_lavorare('Verdi').
?- puo_lavorare('Gatti').
?- puo_lavorare('Negri').
?- puo_lavorare('Fabbri').
?- puo_lavorare('Ferrari').
Se uso questo goal con "solutions=all" ottengo l'elenco delle
persone che possono lavorare.
?- eta(P,_),puo_lavorare(P).
*/
Il
not può essere definito usando la combinazione cut-fail
in questo modo:
not(P) :- call(P), !, fail. not(P).La prima clausola per prima cosa richiede l'esecuzione del goal
P
mediante il predicato predefinito call.
Se il goal P ha successo, viene invocato il cut, che ha successo,
e il fail provoca il backtracking che è però inibito dal
cut. Così se P ha successo,not(P)
fallisce. Se P fallisce, il cut della prima clausola non
viene raggiunto, e si passa alla seconda clausola che, essendo un fatto,
ha sempre successo. Cosi se P fallisce, not(P)
ha successo.
soluzione(Sol) :-
genera(Sol),
controlla(Sol).
Il predicato genenera produce una possibile soluzione
e successivamente controlla verifica che la soluzione sia
accettabile. Se controlla fallisce si innesca il backtracking,
e genera fornirà una soluzione alternativa.
Non appena controlla ha successo una soluzione è stata trovata.
Se per qualche ragione sappiamo che questa soluzione è l'unica
possibile, oppure l'unica che ci interessa, possiamo inibire
il backtracking una volta che controlla
abbia avuto successo.
soluzione(Sol) :-
genera(Sol),
controlla(Sol),
!.
Un semplice esempio illustrerà questo schema.
Supponiamo di voler scrivere un predicato che calcola il quoziente
della divisione fra due interi usando solo addizione e moltiplicazione:
% file: cut/es3.pl dividi(N1, N2, Risultato) :- intero(Risultato), Prod1 is Risultato * N2, Prod2 is (Risultato + 1) * N2, Prod1 =< N1, Prod2 > N1, !. intero(0). intero(N) :- intero(N1), N is N1 + 1.Il predicato
intero(N) funziona come un generatore
di numeri interi.
La prima volta che viene richiamato restituisce il valore 0 (per la
prima clausola). Ad ogni successiva richiesta di backtracking viene
restituito l'intero immediatamente successivo (ricorsione tramite
la seconda clausola).
dividi usa intero come generatore
di una possibile soluzione.
Le righe successive servono da controllo.
Risultato è una soluzione accettabile se il suo
prodotto per il divisore è minore del dividendo, e se moltiplicando
Risultato + 1 per il divisore
si ottiene un valore maggiore del dividendo.
Se queste condizioni sono verificate allora Risultato è l'unica
soluzione del problema.
Se non si introducesse il cut, la richiesta di ricerca di ulteriori soluzioni
farebbe generare a intero infiniti numeri nessuno dei quali
soddisferebbe le condizioni di cui sopra.
Controlla il funzionamento di dividi.
Cosa succede se si toglie il cut e si usa "solutions=all"?
Un ulteriore esempio di questo uso del cut può essere visto in connessione alla funzione membro. Nella sua versione non deterministica essa viene scritta come
/* appartenenza ad una lista */ membro(X,[X|_]). membro(X,[_|Y]) :- membro(X,Y).Se si chiede di soddisfare l'obiettivo
?- membro(X,[a,b,c]). X=a,X=b e
X=c.
Se scriviamo una versione deterministica dello stesso predicato
/* appartenenza ad una lista - deterministico*/ membro1(X,[X|_]) :- !. membro1(X,[_|C]) :- membro1(X,C).non appena viene trovata la prima soluzione, viene invocato il cut, che inibisce il backtracking e quindi la ricerca di altre soluzioni. Cosi
membro e membro1 si comportano allo stesso
modo se gli argomenti sono entrambi istanziati, ma possono comportarsi
in modo diverso quando il primo (o il secondo) argomento è
una variabile.
membro e membro1
formulando varie domande per l'interprete Prolog.
file: cut/es4.pl /* appartenenza ad una lista */ membro(X,[X|_]). membro(X,[_|Y]) :- membro(X,Y). /* appartenenza ad una lista - deterministico*/ membro1(X,[X|_]) :- !. membro1(X,[_|C]) :- membro1(X,C). /* possibili goal: ?- membro(y,[a,y,b,y]). ?- membro1(y,[a,y,b,y]). ?- membro(X,[a,b,c,d]). ?- membro1(X,[a,b,c,d]). ?- membro(a,L). % attenzione va in loop se si usa "solution=all" ?- membro1(a,L). */
Analogo discorso vale per il predicato conc che permette di
concatenare due liste. Può essere definito così
/* concatena due liste */ conc([],L,L). conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3).oppure usando il cut.
/* concatena due liste */ conc1([],L,L). conc1([X|L1],L2,[X|L3]) :- conc1(L1,L2,L3).Questa definizione si comporta come quella precedente se il primo argomento è istanziato, ma i due predicati differiscono se il primo argomento è una variabile. Provate a studiare le differenze fra
conc e conc1 formulando varie domande per l'interprete Prolog.
file: cut/es5.pl /* concatena due liste */ conc([],L,L). conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3). /* concatena due liste - usa il cut*/ conc1([],L,L):- !. conc1([X|L1],L2,[X|L3]) :- conc1(L1,L2,L3). /* possibili goal: ?- conc([a,b,c],[e,f],L). ?- conc1([a,b,c],[e,f],L). ?- conc([a,b,c],X,L). ?- conc1([a,b,c],X,L). ?- conc(X,[a,b,c],L). /* attenzione questo va in loop */ ?- conc1(X,[a,b,c],L). ?- conc(X,Y,[a,b,c]). ?- conc1(X,Y,[a,b,c]). */
% file: cut/insiemi.pl appartiene(X,[X|_]) :- !. appartiene(X,[_|Y]) :- appartiene(X,Y). incluso([],_). incluso([X|C],Y) :- appartiene(X,Y), incluso(C,Y). intersezione([],_Y,[]). intersezione([X|R],Y,[X|Z]) :- appartiene(X,Y), !, intersezione(R,Y,Z). intersezione([_X|R],Y,Z) :- intersezione(R,Y,Z). unione([],X,X). unione([X|C],Y,Z) :- appartiene(X,Y), !, unione(C,Y,Z). unione([X|C],Y,[X|Z]) :- unione(C,Y,Z). /* possibili goal appartiene(3,[2,5,6,3,1]). incluso([3,2,5],[4,1,2,7,6,3,5]). incluso([3,2,5,8],[4,1,2,7,6,3,5]). intersezione([9,2,5,8],[4,1,2,7,6,3,5],L). intersezione([9,0,10,8],[4,1,2,7,6,3,5],L). unione([9,2,5,8],[4,1,2,7,6,3,5],L). */
intersezione
e unione.
intersezione e
unione senza fare uso del cut in modo
che si comportino esattamente come i predicati originali.
?- unione([9,2,5,8],[4,1,2,7,6,3,5],L).L =[9,8,4,1,2,7,6,3,5]L compaiono proprio in quest'ordine.
a -- b -- c
\ | |
\ | |
\ | |
\ | |
d -- e
Il nostro problema e' quello di trovare il percorso
(più in generale i percorsi) che uniscono due città.
Prima di tutto dobbiamo rappresentare le strade che uniscono le città:
% le strade strada(a,d). strada(a,b). strada(b,c). strada(c,e). strada(d,b). strada(d,e).Dobbiamo tuttavia tenere conto del fatto che le strade possono essere percorse nelle due direzioni, quindi possiamo scrivere un predicato che ci dice quando due città sono connesse (direttamente).
% le citta X e Y sono connesse connesso(X,Y) :- strada(X,Y). connesso(X,Y) :- strada(Y,X).Possiamo ora cercare un percorso che porti dalla città
X
alla città Y:
% percorso(X,Y) % trova un percorso da X a Y % prima versione percorso(X,Y) :- connesso(X,Y). percorso(X,Y) :- connesso(X,Z), percorso(Z,Y).
X
a Y se c'è una connessione diretta.
Z direttamente connessa a X e successivamente di
trovare un percorso che unisca Z a Y.
La regola può essere schematizzata in questo modo:
|---connesso(X,Z)---> Z ---percorso(Z,Y)---|
| V
X ------------percorso(X,Y)--------------> Y
?- percorso(a,e).Yes.
Il prolog mediante il backtracking esplora le possibili strade alternative
finchè non ne trova una che porta alla destinazione finale.
Provate a sottomettere all'interprete i seguenti goal:
?- percorso(a,b).?- percorso(a,e).
% file: backtracking/perc1.pl
% Cerca un percorso che porta da una citta' ad un'altra
% usando il backtracking del Prolog
% Mappa delle strade che collegano alcune citta
/*
a -- b -- c
\ | |
\ | |
\ | |
\ | |
d -- e
*/
% le strade
strada(a,d).
strada(a,b).
strada(b,c).
strada(c,e).
strada(d,b).
strada(d,e).
% le citta X e Y sono connesse
connesso(X,Y) :-
strada(X,Y).
connesso(X,Y) :-
strada(Y,X).
% percorso(X,Y)
% trova un percorso da X a Y
% prima versione
percorso(X,Y) :-
connesso(X,Y).
percorso(X,Y) :-
connesso(X,Z),
percorso(Z,Y).
% ?- trace,percorso(a,b).
% ?- trace,percorso(a,e).
Il programma che abbiamo appena visto ha due difetti.
Prima di tutto non possiamo vedere
qual'è il percorso fra le due città.
In secondo luogo, esistono dei percorsi che sono ciclici. Possiamo cioè
ripercorrere più volte uno stesso cammino ciclico come ad esempio:
a-b-d-a-b-d-a-b-d-.....
Un metodo per ovviare a questo problema consiste nel mantenere una lista
delle città in cui siamo già passati e nel controllare che ogni nuova
città che aggiungiamo al percoso non sia contenuta in tale lista.
Il programma può essere così modificato:
% percorso(X,Y) % trova un percorso da X a Y % seconda versione percorso(X,Y,T) :- connesso(X,Y), write([Y|T]),nl. percorso(X,Y,T) :- connesso(X,Z), Z \= Y, \+ membro(Z,T), percorso(Z,Y,[Z|T]).Ora il terzo argomento di
percorso rappresenta la lista delle
città per cui si è già passati.
write
stampiamo il percorso trovato.
Z che non sia il punto di arrivo (questo e
gestito dalla prima regola) e che sia connessa direttamente a X.
Mediante il predicato diverso, Z \= Y si controlla che
Z non coincida con punto di arrivo Y;
con il predicato membro si controlla che la nuova città
Z non faccia parte della lista T delle
città già visitate.
?- percorso(a,c,[a]).a e
c.
% file: backtracking/perc2.pl .... .... % percorso(X,Y) % trova un percorso da X a Y % seconda versione percorso(X,Y,T) :- connesso(X,Y), write([Y|T]),nl. percorso(X,Y,T) :- connesso(X,Z), Z \= Y, \+ membro(Z,T), percorso(Z,Y,[Z|T]). % ?- percorso(a,c,[a]). membro(X,[X|_]). membro(X,[_|Y]) :- membro(X,Y).
Una ulteriore versione di percorso, con 4 argomenti, può essere scritta in questo modo:
% percorso(X,Y) % trova un percorso da X a Y % terza versione percorso(X,Y,T,[Y|T]):- connesso(X,Y). percorso(X,Y,T,L) :- connesso(X,Z), Z \= Y, \+ membro(Z,T), percorso(Z,Y,[Z|T],L).In questo caso il quarto argomento rappresenta il risultato (cioè il percorso trovato dal Prolog).
?- percorso(a,c,[a],L).L=[c, b, d, a] YesTrovare quei percorsi che connettono
a e c
passando per e.
% file: backtracking/perc3.pl .... .... % percorso(X,Y) % trova un percorso da X a Y % terza versione percorso(X,Y,T,[Y|T]):- connesso(X,Y). percorso(X,Y,T,L) :- connesso(X,Z), Z \= Y, \+ membro(Z,T), percorso(Z,Y,[Z|T],L). % ?- percorso(a,c,[a],L). membro(X,[X|_]). membro(X,[_|Y]) :- membro(X,Y).