CSC302 2006S, Class 32: Logic Programming (2): Prolog Basics.

Admin:
* Questions on the exam?
  * I'll grade four out of five.
  * Problem One:
    * Yes, you need to turn in a new semantics (and grammar and ...)
    * Why is the syntax abstract?
      * It's ambiguous: Because it doesn't provide information on precedence
  * Problem Two: 
    * You need not pass in the ALLCAPS things as params.
    * You can add params to their calls (e.g., to DONE?)
  * Problem Three:
    * Can we use == to compare pointers?  YES!
* I suppose a detailed analysis of "The Story of Mel" would make an interesting presentation.
* Reading for Friday: The Birth of Prolog.

Overview:
* Prolog: Imposing Fixed Control on Horn-Clause Logic.
* Some Examples.
* The Need for Backtracking.
* Problems with Resolution.
* Affecting Control: Cut.

Kowalski: Program = Logic + Control
Prolog: Horn-Clauses, plus top-down control
  * Top-down: Start with goals, and repeatedly expand
  * Contrast with bottom-up: Start with facts and repeatedly derive new facts
  * Two important issues in top-down control:
    * Which goal do you expand first?
      parent(X,john),parent(X,jane)
    * Which clause do you use?
      parent(X,Y) :- father(X,Y).
      parent(X,Y) :- mother(X,Y).
  * Prolog:
    * Expand the first goal first
    * Use the first matching clause
  * When you run out of goals, report the substitutions
  * When you fail to match a goal, back up a prior choice of matching clause and try a different matching clause

P1: prereq(cs301,cs302).
P2: prereq(mat218,cs301).
P3: prereq(cs151,cs152).
P4: prereq(cs201,cs211).
P5: prereq(cs201,cs213).
P6: prereq(cs211,cs362).
P7: prereq(ds,cs301).
P8: prereq(ds,cs201).

T2: took(hartdavi,cs302).
T3: took(hartdavi,cs151).
T4: took(hartdavi,cs362).

T0: took(Person,ds) :- took(Person,cs152).
T1: took(Person,ds) :- took(Person,cs153).

; If a Person takes a course, then they've taken all of the prerequisites
T5: took(Person,PreReq) :- took(Person,Course), prereq(Prereq,Course).

? took(hartdavi,cs301) // substitute hartdavi for Person and cs301 for PreReq in T5
=> took(hartdavi,Course),prereq(cs301,Course) // substitute cs302 for Course in the goals, use T2
=> prereq(cs301,cs302). // Use P0
=> YES

? took(hartdavi,cs211) // substitute hartdavi for Person and cs211 for PreReq in T5
=> took(hartdavi,Course),prereq(cs211,Course) // substitute cs302 for Course in goals, use T2
=> prereq(cs211,cs302) FAILED
=> backup
=> took(hartdavi,Course),prereq(cs211,Course) // substitute cs151 for Course in goals, use T3
=> prereq(cs211,cs151) FAILED
=> backup
=> took(hartdavi,Course),prereq(cs211,Course) // substitute cs362 for Course in goals, use T4
=> prereq(cs211,cs362) // use P6
=> YES
* The solution strategy is a tree
* Nodes in the tree are sequences of goals
* Branches are based on matching clauses
* Identical logic with different expression can have significnat impact on running time.

We've been using these clauses to say "Did Davis take X?",  But we can also ask "What courses did Davis take?" and "Did anyone take X"?

A simple representation of numbers: lists of 1's.

add([],X,X).
add([1|X],Y,[1|Z]) :- add(X,Y,Z).