Prolog/Funzioni ricorsive

Questa sezione riguarda l'uso di regole ricorsive.

Regole ricorsive

Considera il seguente programma.

 parent(david, john).
 parent(jim, david).
 parent(steve, jim).
 parent(nathan, steve).

 grandparent(A, B) :- parent(A, X), parent(X, B).

Esso mostra una linea maschile di discendenza e definisce con una regola quando qualcuno è parente diretto in secondo grado (cioè quando una persona è genitore di un genitore). Come si fa per definire se uno è antenato di una persona cioè genitore del genitore del genitore ecc. ? Procedendo nel modo tradizionale avremmo :

 ancestor(A,B) :- parent(A, B).
 ancestor(A,B) :- parent(A, X), parent(X, B).
 ancestor(A,B) :- parent(A, X), parent(X, Y), parent(Y, B).
 ancestor(A,B) :- parent(A, X), parent(X, Y), parent(Y, Z), parent(Z,B).

Chiaramente questo non sembra il modo migliore. Non è elegante, richiede un sacco di lavoro e cosa molto importante, non definisce cosa sia antenato e cosa no. Questo modo funziona per almeno quattro generazioni, ma per l'antenato diretto in quinto grado occorrebbe una nuova linea .Cio' di cui abbiamo bisogno è una definizione di antenato completa che permetta di stabilire se uno è antenato indipendentemente dalla lontananza fra le generazioni.

Per raggiungere questo obiettivo abbiamo bisogno di definire che cosa sia un antenato. Al primo rigo la persona P è antenato di C, se P è genitore di C. Inoltre dobbiamo dire che la persona A è antenato di C se la persona A è genitore di un antenato C. Queste due definizioni si completano bene a vicenda.

Per esempio, se ci chiedessimo se Steve è antenato di John, guarderemmo le definizioni. Steve non è di certo genitore di John, quindi la regola non si applica. Steve è genitore di un antenato di John? Steve è un genitore di Jim, quindi la domanda diventa, è Jim un antenato di John? Jim è un genitore di David, allora David è un antenato di John? A questo punto possiamo usare la prima definizione, perché David è un genitore di John.

In prolog, la definizione suonerebbe cosi':

 ancestor(A, B) :- parent(A, B).
 ancestor(A, B) :- parent(A, X), ancestor(X, B).

La seconda regola è ricorsiva ; usa l'antenato per definire un antenato. La prima regola è chiamata stop predicate perché si ferma richiamandosi.

Quando affronta la domanda ?- ancestor(steve,john). prolog tentera' la prima linea di definizione,ma non potra' unificare parent(steve, john) con altre linee in archivio. Cerchera' allora la seconda linea con i sottoobiettivi parent(steve, X) e ancestor(X, B). Puo' unificare parent(steve, X) con parent(steve, jim), cosi' prolog ha a sinistra ancestor(jim, john). Continuera' fino a ancestor(david, john) che , usando la prima linea della definizione è vera perché parent(david, john) è vera.

Prolog è comodo quando si tratta di definizioni ricorsive. Esso puo' trovare tranquillamente tutti gli antenati di John:

 ?- ancestor(X, john).

 X = david ;
 X = jim ;
 X = steve ;
 X = nathan ;
 No

O tutte e persone di cui Nathan è antenato:

 ?- ancestor(nathan, X).

 X = steve ;
 X = jim ; 
 X = david ;
 X = john ;
 No

Usare regole ricorsive

Usare regole ricorsive comporta dei pericoli, puo' portare ad ogni tipo di loop, i quali causano solitamente degli stack overflows, cioè che prolog ha esaurito la memoria. Le seguenti linee dovrebbero essere tenute a mente durante la scrittura di regole ricorsive.

• Parti con il predicato di stop.

Poni sempre all' inizio il predicato di stop prima del predicato ricorsivo.

• Evitare la ricorsione a sinistra

Scrivere sempre la regola ricorsiva sulla destra.Per esempio usare:

a :- b, a. 

invece di

a :- a, b.

Questo è lo stesso principio usato in precedenza , lascia che prolog valuti prima gli obiettivi non ricorsivi. Se fai ricorsione prima di aver valutato tutti gli obiettivi finirai in ricorsione infinita o farai un sacco di lavoro non necessario . Qualche volta è necessario porre l'elemento ricorsivo a sinistra ma fallo sapendo cio' che fai : eviterai conseguenze spiacevoli.

Esempi

• Un classico esempio di funzione ricorsiva è il fattoriale (vedi il capitolo Matematica, Funzioni e uguaglianza). In molti linguaggi di programmazione, potresti imparare la ricorsione scrivendo una funzione fact(), che prende come input un intero e rende un altro intero. In Prolog , dal momento che usiamo predicati al posto di funzioni, definiremo invece un predicato fact(X,Y) equiivalente all' affermazione "Il fattoriale di X è Y." allora, per trovare il fattoriale di 7, per esempio, useremo il simbolo query ?- fact(7,X). Prolog rispondera': X=5040.

• Una cosa che puo' essere facilmente definita come ricorsiva è una lista. In questo contesto considereremo una lista come una collezione di cose (elementi) che sono posti in un ordine ben preciso.Per definirla in modo ricorsivo, affermeremo che una lista è un singolo elemento,che è seguito da una lista. Per terminare la ricorsione abbiamo bisogno di una seconda affermazione, che sancisce una lista è qualcosa che consiste di un elemento. insieme, queste due definizioni completano una definizione di lista.

Le liste sono utilizzate comunemente in prolog e sono usate in modo ricorsivo. Il seguente capitolo spiega come.