4/22/20081CSE 3302 Programming LanguagesLogic Programming:Chengkai LiSpring 2008Prolog (II)Lecture 22 –Prolog (II), Spring 20081CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 2008SWI-PrologSWI-PrologLecture 22 –Prolog (II), Spring 20082CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 2008Resources• Download: http://www.swi‐prolog.org/dl‐stable.html• Documentation:(You don’t necessarily need to read. But good for reference when you have questions.)http://www.swi‐prolog.org/dl‐doc.htmlMenu “Help ‐> Online Manual” (HTML files in directory “doc”)Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20083Query Prompt• query prompt?‐ (Enter goals after “?‐”)Example: ?‐ help(help).• Load a file with clauses?‐[swi(‘myprogram/example.pl’)]. or?‐[swi(‘myprogram/example’)]. (myprogram must be a subdirectory in the swi‐prolog program directory)Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20084ancestor(X,Y) :- parent(X,Y).ancestor(X,Y) :- ancestor(X,Z), ancestor(Z,Y).parent(X,Y) :- mother(X,Y).parent(X,Y) :- father(X,Y).father(bill,jill).mother(jill,sam).father(bob,sam).Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20085User Interaction?‐ parent(bob,sam). (a query must end with . )true (can be proved)?‐ parent(bob,jill).fail(cannot prove)( p)?‐ parent(bill,X),| father(X,sam)|. (user can use multiple lines to write a query ) fail?‐ parent(X, sam).X = jill ;(user typed ; to ask for more answers.)X = bobLecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200864/22/20082Debugging?- trace, parent(X, sam).Call: (8) parent(_G494, sam) ? creepCall: (9) mother(_G494, sam) ? creepExit: (9) mother(jill, sam) ? creepExit: (8) parent(jill, sam) ? creepXjill;X = jill;Redo: (8) parent(_G494, sam) ? creepCall: (9) father(_G494, sam) ? creepExit: (9) father(bob, sam) ? creepExit: (8) parent(bob, sam) ? creepX = bobMore details in section 2.9 and 4.2.8 of the manualLecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20087Graphical DebuggerLecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20088Prolog SyntaxProlog SyntaxLecture 22 –Prolog (II), Spring 20089CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 2008Basic Syntax<clause> ::= <fact> | <rule><fact> ::= <term> .<rule> ::= <term> :- <termlist> .<termlist> ::= <term> | <term> , <termlist><term> ::= <variable> | <constant> | <compound-term><constant> ::= <number> | <atom><compound-term> ::= <atom> ( <termlist> )Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200810Prolog syntax• :‐ for ←, for and• Uppercase: variableLowercase: other names (constants, atom (i.e., name of predicate))• Built‐in predicates: read, write, nl (newline)=,is,<,>,=<,>=,/,*,+,-,mod,div(Note it is =<, not <=)Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200811Arithmetic• Arithmetic operation can use prefix or infix notations.+(3,4)3+4• Value is not immediately evaluated.?‐ write(3+5).?‐ X is 3+5. (is a predicate that evaluates 3+5)x=7.?‐ 3+4 = 4+3. (these are two different terms)fail.?‐ X is 3+4, Y is 4+3, X = Y. (unification)X=7,Y=7.Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 2008124/22/20083Unification• The semantics of = is determined by unification, i.e., = forces unification.?‐ me = me.true.?‐ me = you.fail.(See unification algorithm in Page 556)1. Constant unifies only with itself.?‐ me = X.X = me.?‐ f(a,X) = f(Y,b).X = b,Y = a.?‐ f(X) = g(X).fail.Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 2008132. Variable unifies with anything, and becomes instantiated to that thing.3. Two predicates unifies if they have the same name and the same number of arguments, and their arguments unify.Unification for List Operations?- [H|T]=[1,2,3].H = 1,T = [2,3]?- [H1,H2|T]=[1,2,3].H1 = 1,H2 = 2,T = [3]?- [H1,H2,H3|T]=[1,2,3,4,5].H1 = 1,H2 = 2,H3 = 3,T = [4,5]Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200814List Operations• Concatenation:?- X = [0,1|[2,3,4]].X = [0,1,2,3,4]• Get elements, or tail :?[H1 H2|[3 4]] [0 1|[2 3 4]]?-[H1,H2|[3,4]] = [0,1|[2,3,4]]What do we get?fail.?- [H1,H2|[3,4]] = [0,[1,2],3,4]What do we get?H1=0,H2=[1,2].Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200815Define List Operation Predicates• cons(X,Y,L) :‐ L = [X|Y].?‐ cons (0,[1,2,3],A).?‐ cons (X,Y,[1,2,3]).• Rewrite cons:cons(X,Y, [X|Y]).Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200816Define List Operation Predicates• append(X,Y,Z) :‐ X = [ ], Y=Z.append(X,Y,Z) :‐ X = [A|B], Z=[A|W], append(B,Y,W).• Another definitionappend([ ],Y,Y).append([A|B], Y, [A|W]) :‐ append(B,Y,W).?‐ append(X, Y, [1,2]).Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200817• reverse([],[]).reverse([H|T], L) :‐ reverse(T,L1), append(L1, [H], L).Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 2008184/22/20084Prolog’s Search StrategyProlog s Search StrategyLecture 22 –Prolog (II), Spring 200819CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 2008Resolution and Unification• Order matter s:– The order to resolve subgoals.– The order to use clauses to resolve subgoals.• Thus programmers must know the orders used by the language implementations, in order to write efficient or even correct program. (Search Strategies)Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200820Prolog’s Strategy• Depth‐first search– The order to resolve subgoals.(left to right)– The order to use clauses to resolve subgoals.(top to bottom)• Backtrack:try another clause when it fails.Lecture 22 –Prolog (II), Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200821Example 1•
View Full Document
Unlocking...