Programming Languages for Intelligent Systems (CM2008) Lecture on Prolog #3 Recursion & List http://www.comp.rgu.ac.uk/staff/khui/teaching/cm2008 Content A quick reminder Arithmetic Operations Some Built-in Predicates Recursion List Previously... Unification Resolution making 2 terms identical by substituting variables resolving a goal into subgoals depth-first search Backtracking at an OR node, if a branch fails, automatically try another branch Arithmetic Operations Prolog has some built-in arithmetic operators: + - * / mod to "get" a value from an expression into a variable "=" only tests for unification it does not evaluates the expression only works when the expression is already evaluated examples: ?- X=1+2. X=1+2 Yes a term structure, NOT evaluated The is/2 Predicate use is/2 to assign value to a variable variable must be uninstantiated examples: ?- is(X,1+2). X=3 Yes ?- X is 1+2. X=3 Yes evaluates 1+2 is/2 used as an infix operator Assignment or Not? is/2 is NOT an assignment it is evaluation + unification there is NO destructive assignment in Prolog you unify variables with values/terms created from other terms The ==/2 Predicate test for equality of 2 terms examples: ?- ==(X,X). X=_G123 Yes ?- X==Y. No ?- X=Y. X=_G456 Y=_G456 Yes X identical to the variable X X and Y are 2 different variables, even though they can be unified X and Y can be unified The =:=/2 Predicate evaluate expressions before comparing terms can be examples: unified ?- 1+2=1+2. Yes ?- 1+2=2+1. No ?- 1+2=:=2+1. Yes terms CANNOT be unified values are equal Recursion “something” defined on itself i.e. coming back the concept applies to predicates/ functions (e.g. in LISP) Recursive Function Example the factorial function N! = 1 × 2 × … × N e.g. OR recursively defined as 3!=1 ×2 ×3 =6 if N=0 then N!=1 if N>0 then N!=N ×(N-1)! e.g. 3!=3 ×2!=3 ×(2 × 1!)=3 ×(2 ×(1 ×0!)) =3 ×(2 ×(1 ×1))=6 The fact/2 Predicate define the factorial function as a predicate fact/2: fact(N,X) relates N with N! (i.e. X) Implementation of fact/2 fact(0,1). fact(N,Ans) :N>0, integer(N), M is N-1, fact(M,Temp), Ans is Temp*N. %0!=1 %N>0 %integer %M is N-1 %get Y=M! %N!=N*(N-1)! A Trace of fact/2 fact(3,X)? fact(2,X2)? X3=1 fact(1,X3)? X4=1 fact(0,X4)? X4=1 θ={X4=1} X2=2 X=6 The ancestor/2 Predicate logical meaning: case 1: X is the ancestor of Y if X is a parent of Y case 2: X is the ancestor of Y if X is the parent of Someone, and Someone is the ancestor of Y implementation: ancestor(X,Y) :parent(X,Y). ancestor(X,Y) :parent(X,Z), ancestor(Z,Y). The Classic Tower of Hanoi Problem 1 disc at a time no big disc above small disc must move top disc The Tower of Hanoi Problem Predicate define a predicate: hanoi(N,Start,End,Aux) a tower of N disc start from Start pole end in End pole auxiliary pole Aux gives instructions of moving a tower of N disc from Start to End with auxiliary pole Aux Implementation of hanoi/4 hanoi(1,Start,End,_) :write('move disc from '), write(Start), write(' to '), write(End), nl. logical meaning: if there is only 1 level, move disc from pole Start to End Implementation of hanoi/4 (cont’d) hanoi(N,Start,End,Aux) :N>0, M is N-1, hanoi(M,Start,Aux,End), write('move disc from '), write(Start), write(' to '), write(End),nl, hanoi(M,Aux,End,Start). logical meaning: if there are N levels & N>0, then: move N-1 levels from Start to Aux move disc from Start to End move N-1 levels back from Aux to End A Trace of hanoi/4 hanoi(3,a,b,aux) hanoi(2,a,aux,b) hanoi(1,a,b,aux) move disc from a to b hanoi(2,aux,b,a) hanoi(1,aux,a,b) move disc from a to aux hanoi(1,b,aux,a) move disc from aux to b hanoi(1,a,b,aux) General Guideline for Writing Recursive Predicates there must be at least: a special/base case: end of recursion a general case: reduce/decompose a general case into smaller cases (special case) there must be some change in arguments (values) when you make a recursive call decompose problem in each recursive call get closer to special/base case otherwise the problem (goal) is not reduced General Guidelines for Writing Recursive Predicates (cont'd) the predicate relates the arguments it works as a black-box assume that the predicate is implemented correctly if you provide these arguments, here is the effect although you haven't completed it yet state how the general case is related to simpler cases (closer to special/base case) List a linearly ordered collection of items syntactically: surrounded by square brackets list elements separated by commas e.g. [john,mary,sue,tom] e.g. [a,b,c,d] may contain any number of elements or no element [] is the empty list List (cont’d) the empty list [] has no head/tail ?- []=[_|_]. No a singleton list has only 1 element its tail is an empty list ?- [a]=[X|Y]. X=a Y=[] Yes Lists vs Arrays no fixed size each item can be of different types, even nested term structures/list e.g. [john,mary,20.0, date(10,may,2004)] e.g. [a,[1,2,3],b,[c,d]] you may not directly access an element by its index you can use unification, however Head & Tail of a List a list is a structured data each list has a: head: 1st element of the list tail: rest of the list a list can be expressed as [Head|Tail] Note: Head is an element Tail is a list List (cont’d) is a term has the functor “.” 2 arguments the head & the tail a list with >1 element can be written as a nested term List Examples ?- [a,b,c]=[X,Y,Z]. X=a Y=b Z=c Yes ?- [a,b,c]=[_,_,X]. X=c Yes ?- [a,b,c] = [X|Y]. X=a Y=[b,c] Yes ?[a,b,c]=[_|[X|Y]] . X=b Y=[c] Yes ?- [a,b,c]=[_,_|X]. X=[c] Yes A List as a Nested Term [1,2,3,4] =[1|[2,3,4]] =[1|[2|[3,4]]] =[1|[2|[3|[4]]]] =[1|[2|[3|[4|[]]]]] . 1 . . 2 3 . 4 [] List Examples (cont’d) [a,b,c,x(y,z)] =[a|[b,c,x(y,z)]] =[a|[b|[c,x(y,z)]]] =[a|[b|[c|[x(y,z)]]]] =[a|[b|[c|[x(y,z)]]]] . a . . b c . x y [] z List Examples (cont’d) [date(2,april,2004),time(9,20,32)] =[date(2,april,2004)|[time(9,20,32)]] =[date(2,april,2004)|[time(9,20,32)|[]]] . date 2 april 2004 . time 9 20 32 [] The member/2 Predicate member(X,L) is true if X is an element of list L examples: ?- member(a,[a,b,c]). Yes ?- member(c,[a,b,c]). Yes Other Ways of using member/2 ?- member(X,[a,b,c]). X=a; X=b; X=c; no ?- member(a,List). List=[a|_123]; List=[_456,a|_789]; … tell me who is an element of the list [a,b,c] tell me the list which has 'a' as an element Implementation of member/2 member(X,[X|_]). member(X,[_|Tail]) :member(X,Tail). logical meaning: X is a member of a list if it is the head. OR X is a member of a list if it is a member of the tail. A Trace of member/2 try R1 member(c,[a,b,c])? member(c,[a,b,c])=member(c,[c|_])? FAIL! try R2 member(c,[a,b,c])=member(X,[_|Tail])? Ө={X=c,_=a,Tail=[b,c]} member(c,[b,c])? try R1 member(c,[b,c])=member(c,[c|_])? FAIL! try R2 member(c,[b,c])=member(X2,[_|Tail2])? Ө={X2=c,Tail2=[c]} try R1 member(c,[c])=member(X3,[X3|_]) Ө={X3=c,_=[]} member(c,[c])? append/3 appends 2 lists together (gives a 3rd list) examples: ?- append([a,b],[x,y],Result). Result=[a,b,x,y] Yes ?- append([a,b,c],[],Result). Result=[a,b,c] Yes Implementation of append/3 append([],L,L). append([H|T],L2,[H|Rest]) :append(T,L2,Rest). logical meaning: appending an empty list to a list L gives L appending a list L1 to L2 gives a list whose head is the head of L1 and the tail is the resulting of append the tail of L1 to L2 String in Prolog double quoted single quoted is an atom a String is a list of integers (ASCII code) example: ?- S="hello". S=[104,101,108,108,111] Yes Converting between String & Atom use name/2 example: ?- S="hello",name(X,S). S=[104,101,108,108,111] X=hello Yes Summary a recursive predicate defines on itself always has a special (base) case & a general case breaks down/decomposes a problem (goal) in each recursive call a list is a structure consists of a head & a tail Readings Bratko, chapter 3

Descargar
# No Slide Title