<div class="notebook"> <div class="nb-cell markdown" name="md1"> # Tutorial I ## Lecture Recap </div> <div class="nb-cell program" data-background="true" name="p1"> human(leibniz). human(sokrates). greek(sokrates). fallible(X) :- human(X). </div> <div class="nb-cell query" name="q1"> fallible(X),greek(X). </div> <div class="nb-cell markdown" name="md2"> Explain Backchaining and Backtracking in the above example. </div> <div class="nb-cell markdown" name="md3"> ## Bonus : Order Dependency, Negation as Failure and more on Backtracking. ### The Integers. In the lecture we covered the naturals. Can we likewise define the integers? (Hint: try the negatives first, then make sure everything is correctly "connected" by building an inverse relation.) </div> <div class="nb-cell program" data-background="true" name="p2"> nat(zero). nat(s(X)) :- nat(X). p(s(zero)):-zero. p(s(X)) :- X. neg(p(zero)). %Or neg(minus1) neg(p(X)):- neg(X). inverse(zero,zero). %Inverse Relation inverse(s(X),p(Y)):- inverse(X,Y). inverse(p(X),s(Y)):- inverse(X,Y). int(X) :- nat(X). int(X) :- neg(X). </div> <div class="nb-cell query" name="q9"> trace, int(p(s(zero))). </div> <div class="nb-cell program" name="p3"> </div> <div class="nb-cell markdown" name="md15"> Challenge: Fix the implementation so that ?int(p(s(zero)) returns true (10 BBP). Define addition and multiplication for both naturals and integers (10 BBP). Hint: part of the problem is that Prolog interprets p in the argument of neg as a function as opposed to the predicate p defined above (note that p is marked red for "not called"). To remedy this you may have to look into how to define higher-order predicates or meta-predicates in Prolog. </div> <div class="nb-cell markdown" name="md5"> ## Order dependency This query works: </div> <div class="nb-cell query" name="q2"> neg(X), int(X). </div> <div class="nb-cell markdown" name="md6"> This one does not: </div> <div class="nb-cell query" name="q3"> trace, int(X), neg(X). </div> <div class="nb-cell markdown" name="md7"> Why? </div> <div class="nb-cell markdown" name="md8"> ## Negation as Failure. Syntax: not(method(X)), \+ method(X). Say we want to find a non-negative number. Why does this query not work: </div> <div class="nb-cell query" name="q4"> not(neg(X)) </div> <div class="nb-cell markdown" name="md9"> And this one does? </div> <div class="nb-cell query" name="q5"> int(X), \+neg(X) </div> <div class="nb-cell markdown" name="md10"> ## Blocking Backtracking Points Consider the following Counter method: </div> <div class="nb-cell program" data-background="true" name="p4"> count(_,[],zero). count(X,[X|R],s(Y)) :- count(X,R,Y). count(X,[_|R],Y) :- count(X,R,Y). </div> <div class="nb-cell query" name="q7"> count(1,[1,1,1,1,2,2,3,4,1,2,7],B) </div> <div class="nb-cell markdown" name="md12"> Why does this produce multiple solutions? Why does the following produce only one? </div> <div class="nb-cell program" data-background="true" name="p5"> count2(_,[],zero). count2(X,[X|R],s(Y)) :- count2(X,R,Y). count2(X,[H|R],Y) :- not(X=H), count2(X,R,Y). </div> <div class="nb-cell query" name="q8"> count2(1,[1,1,1,1,2,2,3,4,1,2,7],X) </div> <div class="nb-cell markdown" name="md13"> In this way "not" can block backtracking points. Be careful: there are many ways in which a method can block backtracking. Depending on how and for what purpose the function is called this may be desirable or not. When debugging, it can be useful to look at ways backtracking may be inadvertedly blocked in your methods. There is also a "bruteforce" method of blocking backtracking: the cut "!". E.g.: </div> <div class="nb-cell program" data-background="true" name="p6"> cutcount(_,[],zero). cutcount(X,[X|R],s(Y)) :- cutcount(X,R,Y), !. cutcount(X,[_|R],Y) :- cutcount(X,R,Y). </div> <div class="nb-cell markdown" name="md14"> Make sure to document your use of the cut as it affects how a function can be called (think about what happens if you query ?-cutcount(1,[1,1,1,1,2,2,3,4,1,2,7],s(zero)) )! </div> <div class="nb-cell markdown" name="md11"> </div> <div class="nb-cell query" name="q10"> count2(1,[1,1,1,1,2,2,3,4,1,2,7],s(zero)) </div> <div class="nb-cell query" name="q6"> cutcount(1,[1,1,1,1,2,2,3,4,1,2,7],s(zero)) </div> <div class="nb-cell markdown" name="md4"> </div> </div>