CSE 3302 Programming LanguagesSlide 2ResourcesQuery PromptSlide 5User InteractionDebuggingGraphical DebuggerSlide 9Basic SyntaxProlog syntaxArithmeticUnificationUnification for List OperationsList OperationsDefine List Operation PredicatesSlide 17Slide 18Slide 19Resolution and UnificationProlog’s StrategyExample 1Slide 23Slide 24Slide 25Slide 26Example 2Slide 28Example 3Slide 30Example 4CSE 3302 Programming LanguagesChengkai LiSpring 2008Logic Programming:Prolog (II)Lecture 22 – Prolog (II), Spring 20081CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 2008SWI-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)?- 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, 20086Debugging?- trace, parent(X, sam). Call: (8) parent(_G494, sam) ? creep Call: (9) mother(_G494, sam) ? creep Exit: (9) mother(jill, sam) ? creep Exit: (8) parent(jill, sam) ? creepX = jill ; Redo: (8) parent(_G494, sam) ? creep Call: (9) father(_G494, sam) ? creep Exit: (9) father(bob, sam) ? creep Exit: (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 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, 200812Unification•The semantics of = is determined by unification, i.e., = forces unification.?- me = me.true.?- me = you.fail.?- 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, 200813(See unification algorithm in Page 556)1. Constant unifies only with itself.2. 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]]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, 200818Prolog’s Search StrategyLecture 22 – Prolog (II), Spring 200819CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 2008Resolution and Unification•Order matters:–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
View Full Document
Unlocking...