Prolog Language
Afleiding bomen
Zoeken…
Bewijs boom
De proefboom (ook zoekboom of afleidingsboom) is een boom die de uitvoering van een Prolog-programma toont. Deze boom helpt bij het visualiseren van het chronologische terugtrackingsproces dat aanwezig is in Prolog. De root van de boom vertegenwoordigt de initiële query en takken worden gemaakt wanneer keuzepunten voorkomen. Elke knoop in de boom vertegenwoordigt dus een doel. Takken worden pas bladeren als waar / onwaar is bewezen voor de vereiste (set van) doelen en zoeken in Prolog wordt uitgevoerd op een diepte-van-links-naar-rechts manier.
Overweeg het volgende voorbeeld:
% Facts
father_child(paul,chris). % Paul is the father of Chris and Ellen
father_child(paul,ellen).
mother_child(ellen,angie). % Ellen is the mother of Angie and Peter
mother_child(ellen,peter).
% Rules
grandfather_grandchild(X,Y) :-
father_child(X,Z),
father_child(Z,Y).
grandfather_grandchild(X,Y) :-
father_child(X,Z),
mother_child(Z,Y).
Wanneer we nu vragen:
?- grandfather_grandchild(paul,peter).
volgende proefboom visualiseert het diepte-eerste zoekproces:
?- grandfather_grandchild(paul,peter).
/ \
/ \
?- father_child(paul,Z1),father_child(Z1,peter). ?- father_child(paul,Z2),mother_child(Z2,peter).
/ \ / \
{Z1=chris} {Z1=ellen} {Z2=chris} {Z2=ellen}
/ \ / \
?- father_child(chris,peter). ?- father_child(ellen,peter). ?- mother_child(chris,peter). ?- mother_child(ellen,peter).
| | | / \
fail fail fail fail(*) success
(*) mislukt voor mother_child(ellen,angie)
waar 'angie' niet overeenkomt met 'peter'