CSC302 2011S, Class 08: Prolog (1)

Overview:
* Predicate Logic Programming.
* Prolog Syntax.
* Behind the Scenes: Computation in Prolog.
* Lab.

Admin:
* Missing: MD
* Reports suggest that you should be able to do the first three problems on assignment 3 in under five hours, but that problem 4 is harder.  I'll treat that one as extra credit.
* For problem 4 on assignment 3, you should use the notation from problem 3.
* EC for CS Extra Thursday (Weinman).
* EC for CS Table Friday.

Broad model: Declarative programming
* You give the computer "facts"
* You ask the computer "questions"
* The computer magically answers questions using facts
* Lots of kinds of declarative programming
  * Predicate logic programming (Prolog)
  * Pure functional programming
  * SQL

Predicate Logic Programming
* Programming using Boolean logic: True/False, And, Or, Not, Existenial 
  Quantifiers, Universal Quantifiers
* Working with predicates: Like a question
  A function with parameters that returns true or false

How do we know if two people are genetically related?
* If X and Y share a common ancestor

Optional: Clearly not necessary, but perhaps clearer
* If X is Y's biologic parent
* If Y is X's biologic parent

We'll say that you're not related to yourself
* If they are the same person (maybe)

How do you decide if X and Y share a common ancestor?
* If exists Z, s.t. Z is an ancestor of X and Z is ancestor Y.

How about ancestry?
* P is an ancestor of Q if P is Q's parent
* P is an ancestor of Q If exists a Z s.t. Z is Q's parent and P is an ancestor of Z.
  * Z is existentially quantified
  * P and Q are universally quantified.
Universal quantificatioN: For all
Existentional quantification: There exists

Prolog uses Disjunctive normal form: An OR of ANDs

Rules
* Constants - lowercase
* Variables - uppercase
* Predicates - lowercase

predicate(params) :- preconditions.

ancestor(P,Q) :- parent(P,Q).
ancestor(P,Q) :- parent(Z,Q), ancestor(P,Z).

parent(adam,cain) :- .
parent(adam,cain).

# A claim that I do not necessarily believe.
ancestor(adam,X).

How does prolog use all of this to compute.
Queries