Sumar
Multe relații au o formă tranzitivă: dacă R(a, b) și R(b, c), atunci R(a, c). În Prolog, scriem două clauze:
% caz direct
ancestor_of(X, Y) :- parent_of(X, Y).
% caz recursiv (închiderea tranzitivă)
ancestor_of(X, Y) :-
parent_of(X, Z),
ancestor_of(Z, Y).
Exemplu — arborele de familie (Lab 1)
Baza de cunoștințe are doar parent_of/2. Vrem ancestor_of/2 peste oricâte generații:
?- ancestor_of(olivia, sam).
true.
olivia -> roger -> ben -> sam — trei pași, dar predicatul se închide tranzitiv.
Exemplu — predecessor în Dutch Royal Family (model)
Când avem două relații (parent, ruler) care se compun:
predecessor(X, Y) :- ruler(X), ruler(Y), parent(Y, X).
predecessor(X, Y) :-
ruler(X),
parent(Z, X),
ruler(Z),
predecessor(Z, Y).
Ordinea conjuncțiilor contează pentru eficiență: punem întâi constrângerile care filtrează mult (ruler(X)) înainte de recursie.
Exemplu — path/2 pe graf (Lab 4)
path(X, Y) :- connected(X, Y).
path(X, Y) :-
path(X, Z),
connected(Z, Y).
Funcționează pe grafuri aciclice. Pe grafuri cu cicluri, programul poate să nu termine — vezi Căutare și drumuri pentru varianta cu acumulator de noduri vizitate.
Atenție — ordinea clauzelor
Cazul direct trebuie să fie primul. Altfel Prolog se adâncește în recursie înainte să găsească răspunsul imediat:
% GREȘIT — poate intra în buclă
ancestor_of(X, Y) :-
parent_of(X, Z),
ancestor_of(Z, Y).
ancestor_of(X, Y) :- parent_of(X, Y).
Atenție — recursia stângă vs dreaptă
% bună — „left recursion” cu cunoștințe deja existente
ancestor_of(X, Y) :-
parent_of(X, Z),
ancestor_of(Z, Y).
% și asta merge, dar explorează altfel graful
ancestor_of(X, Y) :-
ancestor_of(X, Z),
parent_of(Z, Y).
Ambele sunt corecte logic. Pe materiale alegem prima — apelează mai întâi un fapt concret (nu un predicat care se apelează singur).