<div class="notebook"> <div class="nb-cell markdown" name="md1"> # Presence Problem I ## Lecture Recap (optional) </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"> trace, 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"> ## The Integers. Recall how we inductively defined the naturals in the lecture: </div> <div class="nb-cell program" data-background="true" name="p2"> nat(zero). nat(s(X)) :- nat(X). </div> <div class="nb-cell markdown" name="md16"> We are going to expand this definition to the integers. Your first task is to define a predecessor function on the naturals, much like the successor function s (hint: this function is not defined on zero. Use Prolog negation \+ and equality = to express this.). </div> <div class="nb-cell program" data-background="true" name="p8"> nat(p(X)) :- nat(X), \+(X=zero) . </div> <div class="nb-cell markdown" name="md17"> Next, define an inverse function i (Hint: use a predicate "neg" for the negative numbers, we will define it later on). </div> <div class="nb-cell program" data-background="true" name="p7"> nat(i(zero)). nat(i(X)) :- neg(X). </div> <div class="nb-cell markdown" name="md18"> Now we have all the ingredients to define the negative numbers and the integers: </div> <div class="nb-cell program" data-background="true" name="p10"> neg(p(zero)). neg(p(X)):- neg(X). neg(i(X)) :- nat(X), \+(X=zero). int(X):-nat(X). int(X):-neg(X). </div> <div class="nb-cell markdown" name="md19"> Let's try some queries (Hint: if something goes wrong you can use "trace" to start a debugger): </div> <div class="nb-cell query" name="q12"> nat(i(p(zero))), neg(p(p(zero))), int(i(s(zero))), \+nat(p(zero)). </div> <div class="nb-cell markdown" name="md20"> ## Order Dependency and Negation as Failure </div> <div class="nb-cell markdown" name="md21"> Let's try some more queries. Can you explain why the first one works but the second one does not terminate (hint: use "trace")? </div> <div class="nb-cell query" name="q13"> neg(X), int(X). </div> <div class="nb-cell query" name="q14"> int(X), neg(X). </div> <div class="nb-cell markdown" name="md22"> Say we want to find a non-negative integer. Can you come up with a query that does that for us (hint: again, be careful with the ordering)? Can you use the trace to explain why Prolog-negation is called "negation as failure?" \+(neg(X)) equals "It is not provable that there is a negative number X". When X is instantiated the truth value might change "It is not provable that there is a negative number 0" </div> <div class="nb-cell query" name="q15"> trace, int(X), \+(neg(X)). </div> <div class="nb-cell markdown" name="md23"> ## Blocking Backtracking Consider the following counter predicate: </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? Can you fix the problem using negation and equality? </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="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 negation as failure can be used to 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. 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"> 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 check out the following queries: </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="md6"> ## Negation as Failure via Cut 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="p9"> naf(). </div> <div class="nb-cell query" name="q3"> naf(nat(p(zero))). </div> <div class="nb-cell markdown" name="md4"> ## Bonus: Addition and Multiplication on the Integers First define a predicate "newplus" that implements addition. Use cut and negation as failure to make sure the predicate only returns "nice" numbers of the form s(s(s(...))) or p(p(p(...))). You can also use addition to implement a true inferse predicate (instead of just a function). Next use addition to define a predicate "mult" for multiplication. </div> <div class="nb-cell program" name="p3"> newplus(). mult(). </div> <div class="nb-cell markdown" name="md5"> You might find these queries useful for testing: </div> <div class="nb-cell query" name="q2"> newplus(s(s(zero)),p(p(zero)),X), newplus(s(s(s(zero))),p(p(zero)),Y), newplus(s(zero),p(p(zero)),Z), int(X), nat(X), int(Y), nat(Y), int(Z), neg(Z),newplus(zero,s(zero),Y), inverse(s(s(s(zero))),p(p(p(zero)))) </div> </div>