Approfondimemti: come il Prolog tratta la ricorsione

Supponiamo ora di voler sapere se l'atomo new_york appartiene o meno alla lista: [boston, chicago, filadelfia, san_francisco, los_angeles, denver].
Interroghiamo perciò l'interprete Prolog così : ?-membro(new_york,[boston,chicago,filadelfia, san_francisco, los_angeles,denver]).
  1. Inizialmente la prima regola fallisce perchè new_york è diverso da boston; viene quindi applicata la seconda regola che dice di considerare la coda della lista. X rimane quindi associata a new_york, mentre Y diventa invece la lista [chicago, filadelfia, san_francisco, los_angeles, denver].
  2. La prima regola fallisce di nuovo perchè new_york è diverso da chicago; viene applicata la seconda regola, e così via fino all'ultimo passo in cui la variabile y è associata a [denver].
  3. Viene applicata la seconda regola (la prima ovviamente fallisce ancora) estraendo la coda di [denver]; ma la coda di [denver] , come sappiamo, è la lista vuota.
  4. Ci troviamo quindi a dover valutare: membro(new_york,[]). Nel database però non esiste nessuna regola che preveda questo caso e quindi la ricerca fallisce: l'interprete risponderà no.
Usando il comando trace provare ad eseguire il goal precedente e confrontare quanto scritto nel testo con il trace prodotto dall'interprete Prolog. Sempre usando il comando trace. provare il seguente goal:
?-membro(los_angeles,[boston,chicago,filadelfia, san_francisco, los_angeles,denver]).
In questo caso il goal non fallisce. A che punto terminerà la ricorsione ?

 

Approfondimenti: pericoli insiti nella ricorsione

 Si detto che l'uso della ricorsione è molto utile e frequente; occorre però fare attenzione a non generare dei cicli infiniti come nell'esempio seguente: 
                golosa(X,Y):-piace(Y,X).
                piace(Y,X):-golosa(X,Y).
Queste regole dicono che X è golosa di Y se Y piace ad X; d'altra parte Y piace ad X se X è golosa di Y. Nel tentativo di soddisfare la regola golosa si instaura un meccanismo che fa ripetere le due regole alternativamente all'infinito. Anche le ricorsioni sinistre generano cicli infiniti. Si consideri il caso delle relazioni di parentela descritti dai seguenti fatti genitore: 

     genitore(tom,bob).  
     genitore(bob,pat).   
     genitore(pat,jim).
e si voglia definire una regola antenato. La regola antenato può essere scritta come
  1. X è antenato di Y se X è antenato di Z e Z a sua volta è genitore di Y .
  2. X è antenato di Y se X è genitore di Y.
In Prolog: 
         antenato(X,Y) :- antenato(X,Z), genitore(Z,Y).
         antenato(X,Y) :- genitore(X,Y).
In questo caso il goal
?- antenato(tom,Discendente).
genera, usando la prima regola, il nuovo goal
?- antenato(tom,Discendente').
che a sua volta genera il nuovo goal
?- antenato(tom,Discendente'').
Viene generato sempre lo stesso goal senza che ci sia mai terminazione. Per risolvere il problema Dobbiamo tenere conto che l'interprete Prolog soddisfa i goal scandendoli da sinistra verso destra. Quindi avremo una terminazione corretta riformulando la regola per antenato nel seguente modo: 
         antenato(X,Y) :- genitore(X,Z),antenato(Z,Y).
         antenato(X,Y) :- genitore(X,Y).
Questa volta il goal
?- antenato(tom,Discendente).
genera, usando la prima regola, il nuovo goal
?- genitore((tom,Z),antenato(Z,Discendente).
e poichè il goal
?- genitore((tom,Z),
ha come soluzione:
Z=bob
e rimane da provare che
?- antenato(bob,Discendente).
un goal diverso da quello originale.
Inoltre, tenendo presente che l'interprete Prolog scandisce il database alla ricerca delle regole, dall'alto verso il basso, risulta più conveniente scrivere prima il fatto e poi la regola. 
         antenato(X,Y) :- genitore(X,Y).
         antenato(X,Y) :- genitore(X,Z),antenato(Z,Y).
Caricate il fatto genitore e le varie versioni della regola per antenato nel database del Prolog. Attenzione la prima regola non funziona e bloccherà il prolog. Confrontate, aiutandovi con il comando trace, la seconda e la terza versione. 

% file: liste/es4.pl 

% fatti genitore
     genitore(tom,bob).  
     genitore(bob,pat).   
     genitore(pat,jim). 

%regola per antenato - ricorsione sbagliata
  antenato1(X,Y) :- antenato1(X,Z), genitore(Z,Y).
  antenato1(X,Y) :- genitore(X,Y).

% regola per antenato - ricorsione corretta 
%                       la regola e' scritta per prima
 antenato2(X,Y) :- genitore(X,Z),antenato2(Z,Y).
 antenato2(X,Y) :- genitore(X,Y).

% regola per antenato - ricorsione corretta
%                       il fatto e' scritto per primo
 antenato3(X,Y) :- genitore(X,Y).
 antenato3(X,Y) :- genitore(X,Z),antenato3(Z,Y).

p1 :- antenato1(tom,jim). % Ricorsione sbagliata, NON usare !!!!!!!!!
p2 :- antenato2(tom,jim). % Questa funziona. 
p3 :- antenato3(tom,jim). % Questa funziona.

In generale bisogna evitare le ricorsioni sinistre ed è più conveniente scrivere prima i fatti e poi le regole. Tuttavia l'ordinamento delle clausole, necessario a far terminare un goal, può dipendere da come si è posto il goal stesso (quali argomenti sono variabili e quali no).