Regole ricorsive - (Prolog) Lezione 2

In questo post aggiungeremo la relazione predecessor(antenato) al programma famiglia illustrato in precedenza. Consideriamo la relazione


predecessor(X,Y) :-
    parent(X,Y).


essa non è altro che un wrapper della regola parent e per salire nell’albero familiare è necessario riscrivere la regola in questo modo


predecessor(X,Z) :-
    parent(X,Y), parent(Y,Z).


adesso possiamo risalire l’albero familiare di un’altro grado ma per poter risalire alla radice, quindi definire qualsiasi antenato e non solo i nonni, è necessario definire la regola in termini di se stessa. L’idea base è

Per ogni X ed Y,
X è antenato di Z se esiste una Y tale che
(1) X è padre di Z e
(2) Y è a sua volta antenato di X

La traduzione in prolog è data dalle seguenti due regole

(r1)

predecessor(X,Z) :-
    parent(X, Z).

(r2)

predecessor(X , Z) :-
    parent(X, Y),
    predecessor(Y, Z).


Una regola che coinvolge se stessa nella propria definizione è detta regola ricorsiva. Nel nostro caso la prima regola è il caso banale della ricorsione, prolog per rispondere ad una query del tipo predecessor(pam,bob) tenta prima la verifica di (r1) e se quest’ultima da esito negativo viene verificata (r2) è quindi chiaro che senza (r1) si entrerebbe in un ciclo infinito nel tentativo di verificare (r2).

Ecco la nuova regola in azione:

?- predecessor(pam,X).
    X = bob;
    X = ann;
    X = pat;
    X = jim;