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)