CSC302 2006S, Class 33: Logic Programming (3): Playing with Prolog

Admin:
* Due: Exam 
* Read the first five sections (Introduction; Values, Types, and Other Goodies; Functions; Case Expressions and Pattern Matching; Type Classes and Overloading) of A Gentle Introduction to Haskell.
* Have a great weekend!
* Missing: Dimitar, Alex

Overview:
* Detour: Notation.
* Numbers.
* List Operations.
* Polynomials.

Prolog Notation:
* Case has meaning:
  * Words that start with lowercase are: predicates, function, constant]
  * Words that start with uppercase are: Variables
    silly(Sam).
    silly(sam).
* Defining predicates
  In GNU prolog, they should be in a file (at least in Sam's experience)
  consequent :- precedent1,precendent2,...,precendentn.

  silly(Sam) :- makesjokes(Sam).
  embarassing(Sam) :- makesjokes(Sam,Joke),bad(Joke).

  lauged(davis).
* Interaction with the system:
  * ask for queries to be proven (or not proven) by typing the predicate
  * load a set of definitions ['fname'].
* Lists
  [] - Empty
  [Head|Tail] - Cons
  [Car|Cdr] - Cons
  [v1,v2,v3,vn]

Let's write contains

(define contains
  (lambda (lst val)
    (cond
      ((null? lst) #f)
      ((eq? (car lst) val) #t)
      (else (contains (cdr lst) val)))))

Turn into predicate:
* Focus on positive cases, not negative cases
* Consider in terms of implication

C1: contains([Val|Rest],Val).
C2: contains([Other|Rest],Val) 
    :- contains(Rest,Val).

How does this work when it doesn't find the value?

? contains([],1)
; No predicates match, goals remain.  "NO"

? contains([2],1)
; Predicate C1 does not match
; Predicate C2 does match
;   Val = 1
;   Other = 2
;   Rest = []
? contains([],1)
; No predicates match, goals remain.  "NO"

? contains(L,1)
; C1 matches with
;  C1: contains([Val|Rest],Val).
;  Val = 1
;  L = [Val|Rest]
;  Rest can be "anything".
? 
; No goals remain "YES" L = [1|_]
; Sam rejects the answer.  Back to
? contains(L,1)
; C2 matches: contains([Other|Rest],Val) :- contains(Rest,Val).
;  L = [Other|Rest]
;  Val = 1
? contains(Rest,1)
; C1 matches with
;  C1: contains([Val|Rest],Val).
;   Val = 1
;   Rest = [Val|Rest1]
? 
; No goals remain L = [_|[1|_]] ; L = [_,1|_]

Next example: Representing non-negative integers as lists of 1's.

; Given a lsit of n 1's and a list of m 1's, build a list
; of (n+m) 1's
(define add
  (lambda (left right)
    (if (null? left) 
        right
        (add (cdr left) (cons (car left) right)))))

; Representing this as a predicate (can't return a list).
; add(Left,Right,Sum).
add([],Right,Right).
add([1|MoreLeft],Right,[1|MoreSum]) 
  :- add(MoreLeft,Right,MoreSum).

; How do we define multiply?
multiply([],Right,[]).
multiply([1|MoreLeft],Right,Product) 
  :- multiply(MoreLeft,Right,PartialProduct)
   , add(Right,PartialProduct,Product).

; (1+L)*R = P iff R+L*R = P
;   L*R = Tmp, for some Tmp
;   R+Tmp = P
; When is it the case that (1+MoreLeft)+Right = 1+MoreSum?
; When (MoreLeft+Right) = MoreSum