CSC302 2006S, Class 31: Predicate Logic Programming (I) Admin: * Handout on Class Presentations available. * Are there questions on the exam? * When searching for aliases, do we need to check protected and private fields? YES * Can we find a question on the Web for #5? YES, but cite. * Can we find the answer to that question, too? YES. * Don't count on homework getting graded. * Missing: Mark, Dave * Reminder: Math/CS lunch today! Overview: * Declarative Programming, Revisited. * Predicate Logic. * Predicate Logic Programming. * Control. Question from last class: * Why do we still program in other ways? * No time to define logic. * Too little control over efficiency of program. * Not necessarily better for all problems. * GUIs don't fit well. Declarative Programming: * Focus on the *what* rather than the *how* * Kowalski calls these the "logic" and the "control" * How do you express the "what"? (Formal system.) + SQL: Relational calculus + Often: Predicate logic + Sometimes: Other logics Focus this week: Predicate logic as a programming language Predicate logic: * Mechanisms for defining predicates * Predicate is a function whose range is True/False (in traditional Boolean Predicate Logic) * How do we define predicates? * List the elements. absentFromCSC302 = { Dave, Mark } * Using statements involving other predicates and the predicate operations * ops: and, or, not, implies * quantifiers: for all, exists * Example: for all X, if X is a man, then X is mortal there is a Y s.t. Y is a man Socrates is a man * Kowalski: We can express the logic of a program with predicates * We can even express the logic of a program with Horn-form predicates * What is this form? Predicate(params) <- Atom1,Atom2,...,Atomn Meaning "For all (variables used in this statement), if Atom1 AND Atom2 AND Atom3 ... AND Atomn THEN predicate" If no atoms on the right, then the left always holds. Dies(x) <- Mortal(x) Mortal(x) <- childof(x,y),Mortal(y) Mortal(x) <- Man(x) Mortal(x) <- Woman(x) Man(Socrates) <- Why bother writing predicates? * a: Helps us understand what we want in a program implicit "for all x, y, and l" smallest(x,l) <- [member(y,l) => (x <= y)], member(x,l) * Task: Think about how to turn this into a Horn clause. * b: Declarative programming: Predicates can be used to "answer questions"/run algorithms Is Socrates mortal? ? Mortal(Socrates) YES Are there any mortals? YES, Socrates is a mortal. Horn form predicates provide a kind of programming language * Each clause provides a partial definition of a predicate. * Predicates can be treated as functions if we can prove Pred(x,y) for some x, then we have converted x to y. ? sorted([23,1,5,3],x) Where does control come into play with predicates, when trying to answer a question like sorted([23,1,5,3],X)? * Two basic strategies: * Bottom up: Start with something you know sorted([],[]) Man(Socrates) Use that to generate something else Mortal(Socrates) * Top down: Replace a predicate with the precedents Need to prove Mortal(x) Try Man(x) Try ChildOf(x,y) AND Mortal(y) Try Woman(x) * Ordering orders * Parallel/sequential/backgracking Is bottom-up or top-down better? It depends on the problem * Fibonacci: Better bottom up even(0) <- odd(1) <- even(x) <- even(x-2) odd(x) <- odd(x-2) ? odd(3)