Foundations of Computer Science Fall 2007 For today you should have: 1) Read from Sipser and answered the questions in notes12. 2) Finished the Harry Potter genealogy. 3) Prepared for a quiz. For next time, you should: 1) Do some pleasure reading. Start with the Wikipedia page http://en.wikipedia.org/wiki/Church-Turing_thesis And go on to read at least one additional source, as your interest leads you. There are no reading questions and no deliverables for this assignment. 2) Work on the Prolog exercises below. Parzzer solutions ----------------- A few Python tricks you might not have seen: 1) Defining new kinds of Exception objects: class Accept(Exception): "this exception is raised if a Grammar recognizes a string" def __init__(self, pda): Exception.__init__(self) self.pda = pda class Reject(Exception): "this exception is raised if a Grammar rejects a string" 2) Using raise to jump out of a stack of function calls, and return an object as part of the Exception: def process(self, string): """process the given string and print 'accept' or 'reject' """ try: self._process(string) except Accept, e: print 'accept', e.pda except Reject: print 'reject' Inside PDA.step: raise Accept(self) 3) An underscore at the beginning of a method name makes it private: def _process(self, string): """process the given string and raise Accept or Reject""" # initialize the queue with one PDA q = Queue() pda = PDA(self, string) q.push(pda) while q.not_empty(): # get the first PDA pda = q.pop() # process it and add the results to the queue for new in pda.step(): q.push(new) # if the queue is empty, that means we ran out of # viable PDAs, so we reject raise Reject Harry solutions --------------- 1) I represented "many generations" with non-person atoms. This will mess up the ability to check some relationships. 2) To establish siblings, I found it better to provide dummy parents than to denote the sibling relationship directly. 3) That made "cousins" and "related" easy (I think). 4) Which version of ancestor is faster, bottom up or top down? More Prolog ----------- declarative reading vs. operational reading Here's a (modified) example from Programming in Prolog, by Clocksin and Mellish. boy(harry). boy(ron). boy(neville). boy(draco). girl(hermione). girl(ginny). girl(fleur). pair(X,Y) :- boy(X), girl(Y). What's the declarative reading of pair? (Apologies for the heterosexism of this example.) What's the operational reading? What's going to happen when we ask pair(X,Y). How to run Prolog in your head: 1) For a given predicate, start with the first rule/fact and work your way down. 2) Try to satisfy the first clause. a) If you find a match, instantiate one or more variables, and move on to the next clause. b) If the clause fails (doesn't find a match), backtrack to the previous clause and try to re-satisfy the goal. The cut ------- The cut is a special predicate, spelled !, that 1) succeeds immediately and moves on to the next clause, but 2) if you backtrack and hit a cut, it fails immediately and does _not_ try to resatisfy the previous goal. What effect does this have on the previous example: pair(X,Y) :- boy(X), !, girl(Y). What about pair(X,Y) :- !, boy(X), girl(Y). What about pair(X,Y) :- boy(X), girl(Y), !. A common use of cut is the cut-fail combination, which means "if you get this far, you lose". pair(X,Y) :- boy(X), girl(Y), !, fail. not --- Which suggests an implementation of one version of not: not(P) :- call(P), !, fail. not(P). call(P) means "try to satisfy P" What happens if it succeeds? What happens if it fails? Notice that not(girl(X)) does not enumerate all instantiations of X for which girl(X) is false, which is what you might have meant/wanted. How would you do that? Lists ----- Prolog provides lists as a basic type, with the usual syntax: [1, 2, 3] is a list of three elements. In a predicate, you can match the first element and the rest: car([X|Y],X). This means that the predicate car is true if the first argument is a list with X as the first element and Y as the rest, and if the second argument matches X. Likewise with cdr and cons. cdr([X|Y],Y). cons(X,R,[X|R]). member ------ You seldom use car and cdr explicitly. For example, here is an implementation of the built-in predicate 'member': member(X,[X|R]). member(X,[Y|R]) :- member(X,R). This checks membership (obviously): | ?- member(3, [1,2,3]). true But it also enumerates the members: yes | ?- member(X, [1,2,3]). X = 1 X = 2 X = 3 And even generates all the lists that contain a given element! | ?- member(1, X). X = [1|_] ? ; X = [_,1|_] ? ; X = [_,_,1|_] ? ; X = [_,_,_,1|_] ? and so on... Write a set of rules that define a predicate "cross" on two lists that enumerates all pairs where the first element comes from the first pair and the second element comes from the second pair. Takeout ------- Type in these rules: takeout(X,[X|R],R). takeout(X,[F|R],[F|S]) :- takeout(X,R,S). And try these examples: 1) takeout(2,[1,2,3],L). 2) takeout(X,[1,2,3],L). 3) takeout(3, W, [a,b,c]). What's a better name for "takeout" in example 3? Append ------ Here's a definition of append (which is a built-in predicate): append([],X,X). append([X|R],Y,[X|S]) :- append(R,Y,S). Try these examples: 1) append([1,2,3],[4,5],A). 2) append([1,2,3],W,[1,2,3,4,5]). 3) append(A,[5],[1,2,3,4,5]). 4) append(X, Y, [1,2,3,4,5]). Can you write a definition for reverse? It's built in, so you can't test it :( DFA/NFA/PDA ----------- This web page has an interesting implementation of a DFA: http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_14.html Try reading it declaratively and then operationally. parse(L) :- start(S), trans(S, L). trans(X, [A|B]) :- delta(X, A, Y), write(X), write(' '), write([A|B]), nl, trans(Y, B). trans(X, []) :- final(X), write(X), write(' '), write([]), nl. delta(0,a,1). delta(0,b,0). delta(1,a,1). delta(1,b,2). delta(2,_,2). start(0). final(2). 1) Write a file called nfa2.pl that implements N2 on page 51 of Sipser. How do you handle more than one delta from the same state on the same symbol? 2) Write a file called nfa4.pl that implements N4 on page 53. How do you handle null transitions? 3) Write a file called pda1.pl that implements M1 on page 113. How do you handle push and pop?