<div class="notebook"> <div class="nb-cell markdown" name="md3"> # Tutorial I ## Lecture Recap </div> <div class="nb-cell program" data-background="true" name="p2"> 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="md1"> Explain Backchaining and Backtracking in the above example. ?fallible(X), greek(X) ?human(X), greek(X) Backchain ? greek(leibnitz) fail, backtrack. ? greek(sokrates) X=sokrates </div> <div class="nb-cell markdown" name="md6"> ## 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") </div> <div class="nb-cell program" data-background="true" name="p3"> nat(zero). nat(s(X)) :- nat(X). neg(minus1). neg(p(X)) :- neg(X). i(zero,zero). i(s(zero),minus1). i(minus1,s(zero)). i(s(s(X)),p(Y)) :- i(s(X),Y). int(X) :- nat(X). int(X) :- neg(X). </div> <div class="nb-cell markdown" name="md5"> Challenge: Define addition and multiplication for both naturals and integers. </div> <div class="nb-cell markdown" name="md4"> ## Order dependency This query works: </div> <div class="nb-cell query" name="q2"> neg(X), int(X). </div> <div class="nb-cell markdown" name="md7"> This one does not: </div> <div class="nb-cell query" name="q3"> int(X), neg(X). </div> <div class="nb-cell markdown" name="md8"> Why? Because Prolog has to try infinitely many naturals. </div> <div class="nb-cell markdown" name="md9"> ## Negation as Failure. Syntax: not(method(X)), \+ method(X). Why does this query not work: </div> <div class="nb-cell query" name="q4"> \+(neg(X)) </div> <div class="nb-cell markdown" name="md2"> And this one does? </div> <div class="nb-cell query" name="q5"> int(X), \+neg(X) </div> <div class="nb-cell markdown" name="md10"> One might expect the first query to succeed under the semantic "Is there an X that is not a negative number?". However, Prolog treats negation as failure to obtain a proof. In other words ?- \+(neg(X)) means "It is not provable that there is a negative number X". This is of course false as the number minus1 we defined above is negative. Hence "false" is returned. To obtain the first semantic we have to instantiate X: The query :-?int(X), \+neg(X) can be read as "Is there an integer that cannot be proven to be a negative number". Prolog will first solve the first goal and instantiate X with an integer - zero. Then it will check whether zero is a negative number and fail, therefore returning zero as an answer. </div> <div class="nb-cell markdown" name="md11"> ## Blocking Backtracking Points Consider the following Counter method: </div> <div class="nb-cell program" 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="q6"> 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) :- \+(X=H), count2(X,R,Y). </div> <div class="nb-cell query" name="q7"> count2(1,[1,1,1,1,2,2,3,4,1,2,7],X) </div> <div class="nb-cell markdown" name="md13"> "count" allows for backtracking points choosing between the second and third clause. "count2" blocks this choice. </div> <div class="nb-cell markdown" name="md14"> 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="md15"> Cuts that merely prune the search tree and thus make a program more efficient are called "green". On the other hand "red" cuts change the semantics of the program. Make sure you know exactly whether your use of a cut is red or green and document it. Otherwise, bugs galore! For example 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 query" name="q8"> count2(1,[1,1,1,1,2,2,3,4,1,2,7],s(zero)) </div> <div class="nb-cell query" name="q9"> cutcount(1,[1,1,1,1,2,2,3,4,1,2,7],s(zero)) </div> <div class="nb-cell markdown" name="md16"> ## Cut and Negation as Failure Can you define your own negation as failure "naf"? Hint: first define a predicate "failure" that is always false. Then use cut to define "naf". </div> <div class="nb-cell program" name="p1"> failure :- a = b. naf(X) :- X, !, failure. naf(X). </div> </div>