Prolog/Funzioni ricorsive
Questa sezione riguarda l'uso di regole ricorsive.
Regole ricorsive
modificaConsidera 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
modificaUsare 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
modifica- 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.
Esercizi
modifica