% these are the database entries defining the familial relations, % parent(alpha,beta) is interpreted as alpha is parent of beta. parent(ellie, bobby). parent(ellie, gary). parent(ellie, jr). parent(jock, bobby). parent(jock, gary). parent(jock, jr). parent(gary, lucy). parent(jr,johnross). parent(sueellen, johnross). parent(bobby,christopher). parent(pamella, christopher). %| ?- [dallas2]. %% consulting /amd/nfs/roc/disk/ptn013/aiugrad.97/markc/LCTG/dallas2... %% consulted /amd/nfs/roc/disk/ptn013/aiugrad.97/markc/LCTG/dallas2 in module user, 0 msec 2752 bytes %yes %| ?- parent(X,jr). %X = ellie ? %yes %| ?- parent(X, jr). %X = ellie ? ; %X = jock ? ; %no % ancestor % ancestor follows parental links to prove someone is the ancestor of someone else. ancestor(Old, Young):- parent(Old, Young). ancestor(Old, Young):- parent(Old, Middle), ancestor(Middle, Young). % We will place a spy point on ancestor so we can see it being used. % | ?- spy(ancestor). %% The debugger will first zip -- showing spypoints (zip) %% Plain spypoint for user:ancestor/2 added, BID=1 %yes %% zip % | ?- ancestor(jock,christopher). % + 1 1 Call: ancestor(jock,christopher) ? % 2 2 Call: parent(jock,christopher) ? % 2 2 Fail: parent(jock,christopher) ? % 3 2 Call: parent(jock,_1064) ? %? 3 2 Exit: parent(jock,bobby) ? % + 4 2 Call: ancestor(bobby,christopher) ? % 5 3 Call: parent(bobby,christopher) ? % 5 3 Exit: parent(bobby,christopher) ? %?+ 4 2 Exit: ancestor(bobby,christopher) ? %?+ 1 1 Exit: ancestor(jock,christopher) ? %yes %% zip %| ?- % You can also 'leap' between spy points: %| ?- ancestor(jock,christopher). % + 1 1 Call: ancestor(jock,christopher) ? l % + 4 2 Call: ancestor(bobby,christopher) ? l %?+ 4 2 Exit: ancestor(bobby,christopher) ? l %?+ 1 1 Exit: ancestor(jock,christopher) ? l %yes %% trace % here we use two different forms of ancestor to illustrate the % effect of search direction. % ancestor1 % ancestor1 proves ancestry by locating the children of the suspected % ancestor and % proving that they are ancestors of the suspected descendant. % ancestor1 descends the family tree. ancestor1(X,Y) :- parent(X,Y). ancestor1(X,Y) :- parent(X,Z), ancestor1(Z,Y). % ancestor2 % ancestor2 proves ancestry by locating the parents of the suspected % descendant and % proving that they are descendants of the suspected ancestor. % ancestor2 ascends the family tree. ancestor2(X,Y) :- parent(X,Y). ancestor2(X,Y) :- parent(Z,Y), ancestor2(X,Z). % we will now use trace to illustrate the difference between the two search % strategies. %| ?- trace. %% The debugger will first creep -- showing everything (trace) %yes %% trace % %| ?- ancestor1(Who, johnross). % 1 1 Call: ancestor1(_467,johnross) ? % 2 2 Call: parent(_467,johnross) ? %? 2 2 Exit: parent(jr,johnross) ? %? 1 1 Exit: ancestor1(jr,johnross) ? %Who = jr ? ; % 1 1 Redo: ancestor1(jr,johnross) ? % 2 2 Redo: parent(jr,johnross) ? %? 2 2 Exit: parent(sueellen,johnross) ? %? 1 1 Exit: ancestor1(sueellen,johnross) ? %Who = sueellen ? ; % 1 1 Redo: ancestor1(sueellen,johnross) ? % 2 2 Redo: parent(sueellen,johnross) ? % 2 2 Fail: parent(_467,johnross) ? % 3 2 Call: parent(_467,_1048) ? %? 3 2 Exit: parent(ellie,bobby) ? % 4 2 Call: ancestor1(bobby,johnross) ? % 5 3 Call: parent(bobby,johnross) ? % 5 3 Fail: parent(bobby,johnross) ? % 6 3 Call: parent(bobby,_2737) ? % 6 3 Exit: parent(bobby,christopher) ? % 7 3 Call: ancestor1(christopher,johnross) ? % 8 4 Call: parent(christopher,johnross) ? % 8 4 Fail: parent(christopher,johnross) ? % 9 4 Call: parent(christopher,_4417) ? % 9 4 Fail: parent(christopher,_4417) ? % 7 3 Fail: ancestor1(christopher,johnross) ? % 4 2 Fail: ancestor1(bobby,johnross) ? % 3 2 Redo: parent(ellie,bobby) ? %? 3 2 Exit: parent(ellie,gary) ? % 10 2 Call: ancestor1(gary,johnross) ? % 11 3 Call: parent(gary,johnross) ? % 11 3 Fail: parent(gary,johnross) ? % 12 3 Call: parent(gary,_2737) ? % 12 3 Exit: parent(gary,lucy) ? % 13 3 Call: ancestor1(lucy,johnross) ? % 14 4 Call: parent(lucy,johnross) ? % 14 4 Fail: parent(lucy,johnross) ? % 15 4 Call: parent(lucy,_4417) ? % 15 4 Fail: parent(lucy,_4417) ? % 13 3 Fail: ancestor1(lucy,johnross) ? % 10 2 Fail: ancestor1(gary,johnross) ? % 3 2 Redo: parent(ellie,gary) ? %? 3 2 Exit: parent(ellie,jr) ? % 16 2 Call: ancestor1(jr,johnross) ? % 17 3 Call: parent(jr,johnross) ? % 17 3 Exit: parent(jr,johnross) ? %? 16 2 Exit: ancestor1(jr,johnross) ? %? 1 1 Exit: ancestor1(ellie,johnross) ? %Who = ellie ? %yes %% trace %| ?- %| ?- ancestor2(Who, johnross). % 1 1 Call: ancestor2(_467,johnross) ? % 2 2 Call: parent(_467,johnross) ? %? 2 2 Exit: parent(jr,johnross) ? %? 1 1 Exit: ancestor2(jr,johnross) ? %Who = jr ? ; % 1 1 Redo: ancestor2(jr,johnross) ? % 2 2 Redo: parent(jr,johnross) ? %? 2 2 Exit: parent(sueellen,johnross) ? %? 1 1 Exit: ancestor2(sueellen,johnross) ? %Who = sueellen ? ; % 1 1 Redo: ancestor2(sueellen,johnross) ? % 2 2 Redo: parent(sueellen,johnross) ? % 2 2 Fail: parent(_467,johnross) ? % 3 2 Call: parent(_1047,johnross) ? %? 3 2 Exit: parent(jr,johnross) ? % 4 2 Call: ancestor2(_467,jr) ? % 5 3 Call: parent(_467,jr) ? %? 5 3 Exit: parent(ellie,jr) ? %? 4 2 Exit: ancestor2(ellie,jr) ? %? 1 1 Exit: ancestor2(ellie,johnross) ? %Who = ellie ? %yes %% trace % The final version of ancestor uses var(X) to % determine if X is a variable, if this is the case % then X (the ancestor) is being sought, and the % ascending version of ancestor is used. % By default, if this is not the case then the % descending case of ancestor is used to find the % descendants of the instantiated value of X. ancestor3(X,Y) :- var(X), ancestor2(X,Y). ancestor3(X,Y) :- ancestor1(X,Y).