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