<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"> fallible(X),greek(X). </div> <div class="nb-cell markdown" name="md2"> Explain Backchaining and Backtracking in the above example. *Solution:* ?fallible(X), greek(X) ?human(X), greek(X) Backchain ? greek(leibnitz) fail, backtrack. ? greek(sokrates) X=sokrates </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)) :- \+(X=zero), nat(X). </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(X)) :- X=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). neg(s(X)) :- \+(s(X)=zero), neg(X). 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)), \+neg(s(s(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")? *Solution:* Because Prolog has to try infinitely many naturals. </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?" *Solution:* One might expect the query ?- neg(X), inf(X) 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 p(zero) for example 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 query" name="q15"> </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? *Solution:* "count" allows for backtracking points choosing between the second and third clause. "count2" blocks this choice. </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"> failure :- (zero=one). naf(X):- X,!,failure. 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. *Solution:* See below. Depending on how far you get, this can be posed as a bonus problem. </div> <div class="nb-cell program" name="p3"> newplus(X,zero,X). %X+0=X newplus(p(X),s(zero),X) :- !. %p(s(X))=X. Cuts to avoid "ugly" numbers of the kind p(s(p(...))). newplus(X,s(zero),s(X)). % else prepend an s. newplus(s(X),p(zero),X) :- !. newplus(X,p(zero),p(X)). newplus(X,s(Y),s(Z)) :- newplus(X,Y,Z), \+(Z=p(_)). % X+(Y+1)=Z+1 if Z=X+Y. Negation as failure again to prevent creation of ugly numbers. newplus(X,s(Y),Z) :- newplus(X,Y,p(Z)). % s(p(X))=X. newplus(X,p(Y),p(Z)):- newplus(X,Y,Z), \+(Z=s(_)). newplus(X,p(Y),Z) :- newplus(X,Y,s(Z)). % No need to impose commutativity. % inverse inverse(X,Y) :- newplus(X,Y,zero). mult(_,zero,zero). mult(X,s(zero),X). mult(X,s(Y),Z) :- mult(X,Y,A), newplus(A,X,Z), !. %X*(Y+1)=Z if X*Y=Z-X Cuts here are not essential, just to avoid duplication of results mult(X,p(Y),Z) :- mult(X,Y,A), newplus(Z,X,A), !. </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)))), mult(s(zero),p(p(zero)),A), mult(s(s(zero)),s(s(zero)),B). </div> </div>