Prolog techniques - Chapter 2: Prolog Programming Techniques

1 Chapter 2 KỸ THUẬT LẬP TRÌNH PROLOG (Prolog Programming Techniques) 2 Nội dung  Caùch bieåu dieãn list  Soá hoïc  Caùch bieåu dieãn caáu truùc  Ñieàu khieån backtracking  Xuaát/nhaäp  Moät soá vò töø thö vieän quan troïng 3 CÁCH BIỂU DIỄN LIST  List là một cấu trúc dữ liệu đơn giản được dùng trong lập trình phi số học. Một list là một chuỗi với số lượng bất kỳ của các phân tử . Thí dụ: [ann, tennis, tom, skiing] là một list ở PROLOG  Tuy nhiên đấy chỉ là hình thức bên ngoài của list. Lưu ý rằng, mọi đối tượng có cấu trúc ở PROLOG được diễn tả bằng cấu trúc cây. list cũng vậy.  Một list rỗng được diễn tả bởi [ ]  Một list khác rỗng được coi như gồm hai thành phần:  Phần tử đầu tiên của list được gọi là đầu (head) của list  Phần con lại của list được gọi là đuôi (tail) của list Trong thí dụ trên, ann là đầu của list và [ tenmis, tom, skiing] là đuôi của list. 4  Một cách tổng quát , head và tail của một list được phối hợp lại thành ra một cấu trúc nhờ một hàm tử đặc biệt. Việc chọn hàm tử này tuỳ thuộc vào Prolog cụ thể. Ở đây giả định rằng đó là dấu chấm . .( Head, Tail)  Thí dụ: .( ann, .( tennis,. ( tom, .(skiing, [])))) ann tennis tom skiing [ ] . . . . 5  Một list mà chỉ gồm một phần tử tương đương với : [skiing] = .(skiing, [ ])  Lối ký hiệu dấu chấm không dễ dùng bằng lối ký hiệu [ , ].  Lập trình viên có thể dùng cả hai lối ký hiệu, nhưng lối ký hiệu dấu ngoặc vuông thông dụng hơn. Nhưng hãy nhớ rằng các list được diễn tả bên trong bằng các cây nhị phân.  Các phần tử của một list cũng có thể là bất kỳ loại đối tượng nào, kể cả các list. Đuôi của một list có thể được coi như là một đối tượng. Thí dụ: L = [ a,b,c ] Tail = [b, c] và L = .(a, Tail ) 6  Trong lối ký hiệu dấu ngoặc vuông, Prolog đưa vào dấu để tách biệt đầu và đuôi của list L = [ a Tail ] [ a,b,c ] = [ a [b,c] ] = [ a,b [c] ] = [ a,b,c [ ] ]  Tóm lại: Prolog cung cấp 3 cách viết : [Item1, Item2, ] [Head Tail ] [Item1, Item2, Others ] 7 CÁC THAO TÁC TRÊN LIST 2.1 Quan heä thaønh vieân: Vò töø member( X , L ) xeùt xem X coù phaûi laø moät phaàn töû cuûa list L. Thí duï: member( b, [ a,b,c ]) true member( b, [ a| [b, c] ]) false member( X, [ X _ ]). member( X, [ Head Tail ]):- member( X, Tail). 8 Ghép kề ( Concatenrtion)  Vị từ: conc(L1, L2 , L3 ): L3 là sự ghép kề L1 và L2. Thí dụ : conc( [a,b ], [c,d ], [a,b,c,d] ) true conc([], L , L ). conc([ X L1], L2, [ X, L3 ]) :- conc( L1 , L2, L3).  Ta có thể dùng conc để phân rã một list thành rã hai list : ?- conc( L1, L2, [ a,b,c] ). L1 = [ ] L2 = [ a,b,c ] L1 = [ a ] L2 = [ b,c ] L1 = [a,b ] L2 = [ c ] L1 = [ a,b,c ] L2 = [ ] 9 Thêm một phần tử vào list  Thêm một phần tử vào đầu của list, ta cần một procedure như sau : add( X, L , [ X L ] ). ( Sự kiện) 2.4 Xoá một phần tử ra khỏi list : Xoá một phần tử X ra khỏi list L, có thể được lập trình như một vị từ : del(X , L , L1 ) del( X, [ X Tail ], Tail ). del( X, [ Y Tail ] , [ Y Tail1] ) :- del( X , Tail , Tail1 ). ? - del( a, [ a,b,a,a ] , L ). L = [ b,a,a ]; L = [ a,b,a ]; L = [ a,b,a ] Ta có thể dùng vị từ del để định nghĩa thao tác thêm một phần tử vào bất kỳ chỗ nào trong một list . insert( X, List , BiggerList ) :- del( X, BiggerList, List ). 10 Sublist  Vị từ này có hai đối số : sublist( S , L )  Vị từ xét xem list S có phải là một list con của List L không. sublist( S, L ) :- conc(L1, L2, L), conc( S , L3 , L2 ). L1 S L3 L2 L 11 CÁC THAO TÁC TRÊN LIST 2.1 Quan heä thaønh vieân: Vò töø member( X , L ) xeùt xem X coù phaûi laø moät phaàn töû cuûa list L. Thí duï: member( b, [ a,b,c ]) true member( b, [ a| [b, c] ]) false  member( X, [ X _ ]).  member( X, [ Head Tail ]):- member( X, Tail). 12 Hoán vị  Công dụng: sinh ra các hoán vị của một list. Vị từ : permutation( [ ], [ ]). permutation( [X L], P ) :- permutation( L, L1), insert( X , L1, P ). Vị từ insert đã định nghĩa ở phần trước. ?- permutation( [ a,b,c ], P). p = [ a,b,c ]; p = [ a,c,b ]; 3 ! = 6 p = [ b,c,a ]; p = [b,a,c ]; p = [ c,a,b ]; p = [ c,b,a ]; 13 SỐ HỌC Các phương tiện để tính toán số ở Prolog khá đơn giản. Các toán tử có sẵn gồm: +, -, *, /, mod Lưu ý: Trong Prolog khi viết X = 1 + 2, X được dùng đồng nhất với toán hạng 1 + 2 ?- X = 1+ 2. X = 3 Toán tử is bắt buộc sự định trị của biểu thức số học đi sau nó: ?- X is 1 + 2 X = 3 Số học có liên quan đến khi so sánh các trị số học. ?- 277*39 > 10000. yes Các toán tử số học so sánh: > < > = < = =:= equal =\= not equal 14  Toán tử = ở X = Y khiến cho hai đối tượng X và Y hợp nhất với nhau (khiến cho biến trong X và Y được gán trị cụ thể).  Trái lại toán tử X =:= Y khiến cho X và Y được định trị số học với hai trị đem so sánh với nhau. ?- 1+2 =:= 2+1 yes ?- 1+2 = 2+1 no  Vài thí dụ:  Tìm ước số chung lớn nhất của 2 số nguyên, X, Y.  Nếu X = Y thì D = X  Nếu X < Y thì D là ước số chung lớn nhất của X và Y – X  Nếu Y < X thì giống như (2) những đổi vai trò Y và X gcd(X,X,X). gcd(X,Y,D):- X<Y, Y1 is Y – X, gcd(X,Y1,D). gcd(X,Y,D):- Y<X, gcd(Y,X,D). 15 SỬ DỤNG CẤU TRÚC  Trong Prolog, ngoài list, cấu trúc (structure) là một phương tiện lập trình khá mạnh để tạo cấu trúc dữ liệu.  Trong mục này, chúng ta học cách sử dụng cấu trúc qua một thí dụ lập trình: bài toán Tám Con Hậu.  Bài toán 8 con hậu: Đặt 8 con hậu trên một bàn cờ rộng ( 8  8 ô) sao cho không có con hậu nào tấn công được các con hậu khác. Lời giải sẽ được lập trình như một vị từ một đối số: solution( Pos) mà là đúng nếu Pos diễn tả một sắp xếp trong đó 8 con hậu không thể tấn công nhau. Có nhiều ý tưởng khác nhau cho bài toán này. Ta xem xét 3 chương trình khác nhau. 16 Cách giải 1  Chương trình 1:  Vấn đề diễn tả bàn cờ. Một ô trong bàn cờ được diễn tả bằng một cặp toạ độ ( X ,Y ) p(X ,Y) Như vậy bài toán là tìm 1 list cặp tọa độ có dạng [p( X1 , Y1) , p( X2 , Y2), , p( X8 , Y8)] mà thoả mãn đòi hỏi không tấn công. 17 1 2 3 4 5 6 7 8 X X X X X X X X 8 7 6 5 4 3 2 1 [p(1,4) , p(2,2), p( 3,7), p(4,3) ,.., p(7,5) , p(8,1)] laø moät lôøi giaûi 18 Cách giải 1 (tt)  Quan hệ solution được định nghĩa bằng cách xem xét 2 trường hợp:  Case1. list các con hậu rỗng: list rỗng là một lời giải vì không có sự tấn công.  Case2. List các con hậu khác rỗng: [p(X , Y)| Others] Con hậu thứ nhất ở vị trí (X , Y) và những con hậu khác ở các ô được mô tả bởi list Others. Nếu đây là một lời giải thì 3 điều kiện sau phải thoả: Bản thân Others cũng là lời giải đối với bàn cờ nhỏ hơn (n – 1)(n – 1). X và Y phải là số nguyên từ 1 đến 8. Con hậu ở ô (X,Y) không tấn công bất cứ con hậu nào ở danh sách Others. solution([p(X ,Y) I Others]):- solution(Others), member( Y, [1,2,3,4,5,6,7,8]), noattack( p(X,Y), others). 19 Cách giải 1 (tt)  Bây giờ cần phải định nghĩa điều kiện: “con hậu ở một ô không tấn công một con hậu ở một ô khác”. Tức là không cùng hàng, không cùng cột, và không cùng đường chéo.  Cái khuôn mẫu của lời giải sẽ đảm bảo các con hậu ở trên các cột khác nhau. Do đó chỉ cần:  Các toạ độ Y của con hậu phải khác nhau  Chúng không cùng trên đường chéo tức là khoảng cách giữa các ô theo trục X phải khác khoảng cách các ô theo trục Y. 20 % solution( boardposition) solution([ ]). solution([ p(X , Y) I Others]):- solution( Others), member(Y , [1,2,3,4,5,6,7,8]), noattack(p(X,Y), Others). noattack( _ , [ ]). noattack(p(X,Y), [ p(X1,Y1) I Others]):- Y =\= Y1 , Y1 – Y = \ = X1 – X , Y1 – Y =\= X – X1, noattack(p(X , Y), Others). member( I,[ I |_ ]). member(I, [_I Rest]):- member(I , Rest). ?-solution([p(1,Y1),p(2,Y2),p(3,Y3),p(4,Y4), p(5,Y5), p(6,Y6), p(7,Y7), p(8,Y8)]). 21 Chương trình 2  Trong cách biểu diễn bàn cờ ở chương trình 1, mỗi lời giải có dạng [p(1,Y1), p(2,Y2), , p(8,Y8)]  Vì các con hậu được đặt ở các cột kế tiếp nhau, ta không hề mất thông tin nếu ta bỏ qua các tọa độ X. Như vậy, một cách biểu diễn bàn cờ tiết kiệm chỗ hơn là chỉ giữ lại các toạ độ Y của con hậu: [Y1 , Y2,, Y8 ]  Để tránh tấn công nhau, 2 con hậu không ở trên cùng hàng. Điều này đặt một ràng buộc trên các toạ độ Y. Do đó lời giải được diễn tả bằng một hoán vị của list [1,2,3,4,5,6,7,8].  Một hoán vị S là lời giải nếu tất cả các con hậu là an toàn. Do đó, ta có thể viết: solution(S) :- permutation([1,2,3,4,5,6,7,8], S), safe(S). 22 Chương trình 2 (tt)  Vị từ permutation thì ta đã có, giờ cần định nghĩa vị từ safe.  Ta có tách định nghĩa của safe thành 2 trường hợp:  S : rỗng thì S safe  S : không rỗng và có dạng [ Queen I Others]. S sẽ an toàn nếu danh sách Others là an toàn và Queen không tấn công bất kì một con con hậu nào trong danh sách Others. safe([ ]) safe([Queen I Others]):- safe(Others), noattack(Queen, Others)  Quan hệ noattack được định nghĩa dựa vào nhận xét: 23 ° ° X ° X_Dist = 3 X_Dist = 1 Others 24  Nếu Others rỗng thì Queen không hề có tấn công.  Nếu Others khác rỗng thì Queen không được tấn công con hậu đầu tiên trong Others (có khoảng cách X_dist = 1 từ Queen) và các con hậu ở đuôi của Others (có khoảng cách X_dist >1 đối với Queen) solution(Queens):-permutation([1,2,3,4,5,6,7,8], Queens), safe(Queens). permutation( [ ], [ ]). permutation([ X I L], P):- permutation(L, L1), insert(X, L1, P). 25 del(X, [XI Tail], Tail). del(X,[Y I Tail], [Y I Tail1]):- del(X, Tail, Tail1). insert(X, List, Biggerlist):- del(X ,Biggerlist, List). safe([ ]). safe([Queen I Others]):- safe(Others), noattack(Queen, Others, 1). noattack( _ , [ ], _ ). noattack(Y, [Y1 I Ylist], Xdist):- Y1 – Y=\= Xdist , Y – Y1 =\= Xdist, Dist1 is Xdist +1, noattack(Y, Ylist, Dist1). 26 Chương trình 3  Trong chương trình này, mỗiô của bàn cờ được biểu diễn theo 4 toạ độ: x: hàng y: cột u: đường chéo thứ nhất v: đường chéo thứ hai. Với x, y cho trước, u và v được xác định bởi: u = x –y và v = x –y.  Các miền trị của 4 chiều là: Dx = [1, 2, 3, 4, 5, 6, 7, 8] Dy = [1, 2, 3, 4, 5, 6, 7, 8] Du = [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7] Dv = [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] 27  Bài toán được giải như sau:  Chọn 8 bộ tứ từ các miền trị Dx, Dy, Du, Dv sao cho không chọn cùng trị từ bất kỳ miền trị nào cho các bộ tứ này. Cho trước 4 miền trị, chọn vị trí cho con hậu thứ nhất, loại các trị tương ứng ra khỏi cả 4 miền trị và dùng các phần còn lại của các miền trị để gán cho các con hậu còn lại. % solution (Ylist) is true if Ylist is a list of %Y-coordinates of eight non-attacking queens solution(Ylist):- sol(Ylist, [1, 2, 3, 4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7, 8], [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7], [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]). 28 y x -7 -2 +7 u = x - y 12 14 16 2 6 v = x + y 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 29 Chương trình 3 sol([], [], _, _, _). sol( [Y|Ylist], [X|Dx1], Dy, Du, Dv):- del(Y, Dy, Dy1), U is X – Y, del(U, Du, Du1), V is X + Y, del(V, Dv, Dv1), sol(Ylist, Dx1, Dy1, Du1, Dv1). del(Item, [Item| List], List). del(Item, [First| List], [First| List1]):- del(Item, List, List1). 30 Nhận xét  Ba cách giải bài toán 8 con hậu dùng ba cách biểu diễn dữ liệu khác nhau.  Trong ba chương trình, cách giải III minh hoạ một cách tiếp cận đáng chú ý: tạo ra 8 cấu trúc bốn thành phần, mỗi thành phần từ những miền trị khác nhau sao cho thỏa mãn những ràng buộc. Trong ba chương trình, cách nào là tốt nhất?  Cách II là kém nhất vì nó phải tạo ra tất cả các hoán vị rồi mới tìm ra hoán vị hợp lệ để làm lời giải. (Phương pháp sinh và thử).  Cách I và III có thể nhận dạng và loại bỏ ngay những hoán vị “không an toàn” ngay khi chúng vừa được tạo ra chưa đầy đủ.  Cách III hữu hiệu nhất. “Thu hẹp các miền trị” theo cách “lan truyền ràng buộc”. 31 ĐIỀU KHIỂN BACKTRACKING Ngăn chặn Backtracking:  Trên lý thuyết ta có thể điều khiển quá trình thực thi một CT bằng cách sắp lại thứ tự của các mệnh đề và tiểu mục tiêu.  Ở đây ta xem xét một phương tiện điều khiển khác, được gọi là nhát cắt (cut) để ngăn chặn hồi quy.  Prolog thường tự động quay lui khi cần thiết để thoả một mục tiểu mục tiêu.  Tự động quay lui là một tính chất mà làm nhẹ gánh cho lập trình viên khỏi phải lập trình quay lui một cách tường minh.  Mặt khác, quay lui không điều khiển có thể làm cho CT không hữu hiệu. 32  Đôi khi, ta cần phải điều khiển ngăn chặn quay lui. Điều này được thực hiện bằng phương tiện “cut”.  Xét thí dụ: Qui tắc 1: nếu X < 3 thì Y = 0 Qui tắc 2: Nếu 3 ≤ X < 6 thì Y =2 Qui tắc 3: Nếu 6 ≤ X thì Y = 4  Trong Prolog, ta định nghĩa vị từ f(X,Y) như sau: f(X, 0):- X < 3 f(X , 2):- 3≤ X, X >6. f(X , 4):- 6 ≤ X.  Xem xét truy vấn ?- f(1,Y), 2<Y. Y = 0 và tiểu mục tiêu 2<0 sẽ thất bại và làm cho toàn bộ mục tiêu thất bại. Prolog sẽ hồi quy với (2), (3) một cách vô ích. 33 Ngăn chặn Backtracking (tt.)  Vì 3 mệnh đề có tính loại trừ lẫn nhau, chỉ một trong số chúng là thành công.  Chương trình được viết lại là f(X,0):- X < 3,!. f(X,2) :- 3 ≤ X, X <6,!. f(X, 4):- 6 ≤ X.  Cut ngăn chặn hồi quy ngay tại điểm mà nó xuất hiện trong chương trình.  Thực hiện lại truy vấn ?-f(1,Y), 2 < Y. các nhánh tương ứng với rule 2 và rule 3 sẽ không được thực hiện.  Tóm lại: đưa “cut” vào, chúng ta chỉ thay đổi ý nghĩa thủ tục của chương trình mà không ảnh hưởng đến ngữ nghĩa khai báo của chương trình. 34  Bây giờ, hãy xem xét truy vấn ?- f(7,Y). Y = 4. Tiểu mục tiêu 3 ≤ X gây ra một sự thử thừa. Diễn tả lại: if X < 3 then Y =0, else if X < 6 then Y = 2 else Y =4. f(X,0):- X < 3,!. f(X,2) :- X < 6,!. f(X,4).  Lần này các kí hiệu cut không chỉ thay đổi ý nghĩa thủ tục mà còn ảnh hưởng đến ý nghĩa của khai báo chương trình. 35  Định nghĩa: Tiểu mục tiêu cha (parent subgoal) là mục tiêu mà hợp nhất với đầu mệnh đề có chứa kí hiệu “cut”.  Khi gặp phải một kí hiệu cut như là một mục tiêu nó thành công ngay lập tức, nhưng nó buộc chặt hệ thống với những lựa chọn đã thực hiện từ lúc “mục tiêu cha” được gọi cho đến lúc gặp phải ký hiệu cut. Tất cả những lựa chọn khác nằm giữa tiểu mục tiêu cha và ký hiệu cut đều bị loại bỏ. G: tiểu mục tiêu cha H:- B1, B2, , Bm ,!, , Bn  Giả sử tiểu mục tiêu G đối sánh với H của mệnh đề này, thì G là tiểu mục tiêu cha. Tại lúc gặp phải kí hiệu cut, thì hệ thống đã tìm thấy lời giải nào đó cho B1, B2, , Bm . khi gặp phải kí hiệu cut, lời giải hiện hành của B1, B2, , Bm sẽ được chọn và toàn bộ những lựa chọn khác sẽ bị loại bỏ. (Tiểu mục tiêu G sẽ kết với mệnh đề này: mọi cố gắng để hợp nhất G với đầu của một vài mệnh đề khác sẽ bị ngăn chặn.) 36  Thí dụ: C:- P,Q,R,!,S,T,U. C:- V. A:- B,C,D. ?- A.  Khi hợp nhất C trong A với mệnh đề C:- P,Q,R,!,S,T,U. ta được danh sách mục tiêu: B, P,Q,R,!,S,T,U,D  Backtracking có thể áp dụng cho P,Q,R nhưng một khi đã gặp ký hiệu cut, tất cả những lựa chọn khác cho danh sách các tiểu mục tiêu P,Q,R sẽ bị ngăn chận. Mệnh đề C:- V sẽ không được chọn. 37 Một số thí dụ về cut:  Tính maximum. max(X , Y , X) :- X ≥ Y. max(X,Y,Y):- X < Y.  Hai qui taéc loaïi tröø hoã töông. Dieãn ñaït laïi if X ≥ Y then max = X else max = Y. max(X,Y,X):- X≥ Y,!. max(X,Y,Y).  Vò töø member moät lôøi giaûi: Xeùt : member(X,L) member(X,[X | _ ). member(X,[Y | L):- member(X,L).  Chöông trình naøy khoâng taát ñònh (nondeterministic) : neáu X xuaát hieän nhieàu laàn thì moãi laàn xuaát hieän ñeàu ñöôïc tìm thaáy. a vaø [a,b,c,a,d] 38 Vò töø member moät lôøi giaûi  Ta có thể chuyển member về thành một procedure tất định mà chỉ tìm thấy lần xuất hiện đầu tiên.  Chương trình thứ 2 : member(X,[X| _]):- !. member(X,[_ | L]) :- member(X,L).  Chương trình này sẽ đưa lại chỉ lời giải ?- member(X,[a,b,c]). X = a 39 Đưa một phần tử vào một danh sách mà không lặp lại.  Ta muốn đưa một phần tử X vào list L sao cho X được thêm vào chỉ khi X không thấy trong L. add(X,L, L1) Nếu X là một phần tử của L thì L1 = L. Ngược lại, L1 bằng với L có X điền thêm vào. add(X,L,L): member(X,L),!. add(X,L,[X|L]). ?- add(a,[a,b,c],L) L = [a,b,c] 40 Sự phủ định như là một thất bại (negation as failure)  Thí dụ: “ mary thích mọi thú vật trừ rắn” like(mary,X):- snake(X),!, fail. likes(mary,X):- animal(X).  fail là một subgoal đặc biệt, nó luôn luôn thất bại, nó làm cho tiểu mục tiêu cha bị thất bại.  Thí dụ 2: ta muốn định nghĩa vị từ different(X,Y) different(X,X):- !, fail. different(X,Y).  Qua hai ví dụ trên ta thấy nảy sinh nhu cầu về một vị từ not. 41 Vò töø not  Nhiều hệ thống Prolog có cung cấp vị từ này. Nếu không có thì chúng ta có thể tự định nghĩa lấy vị từ not. not(P):- P,!, fail. not(P).  Lưu ý: not được định nghĩa như là một thất bại, nó không tương ứng hoàn toàn với trong logic toán.  Ta viết lại 2 thí dụ trên, nó tự nhiên hơn và dễ đọc. likes(mary,X):- animal(X), not snake(X). different(X,Y):- not(X = Y). 42 Những vấn đề với cut và not Tóm tắt về tiện lợi và bất tiện của chương trình như sau:  Với ký hiệu cut, chúng ta có thể cải biến độ hữu hiệu của chương trình: ta bảo Prolog đừng thử những lựa chọn mà dẫn đến thất bại.  Dùng cut, ta có thể mô tả được những nguyên tắc loại trừ lẫn nhau, chúng ta có thể diễn tả những qui tắc có dạng. If condition P then coclusion Q, otherwise conclution R.  Một nhược điểm của cut xuất phát từ sự kiện là chúng ta có thể mất đi mối tương ứng quí báu giữa ý nghĩa khai báo và ý nghĩa thủ tục của chương trình. 43 Vị từ not, negation của 1 subgoal như là sự thất bại của subgoal đó.  Vì lý do sáng sủa của CT, chúng ta thích dùng not hơn là tổ hợp cut và fail.  Khi Prolog thực thi một not(G), Prolog không cố chứng minh not(G) một cách trực tiếp. Và nó tìm cách chứng minh điều ngược lại. Nếu điều ngược lại không thể chứng minh được ( = thất bại) thì Prolog giả định rằng not(G) là đúng.  Lối suy luận như vậy được gọi sự giả định thế giới đóng (close world assumption).  Một thế giới là đóng theo ý nghĩa rằng mọi cái tồn tại là trong CT, hoặc dẫn ra từ CT. Do vậy, một cái gì không tồn tại (hoặc không dẫn xuất ra) từ CT thì nó là sai và phủ định nó là đúng.  Thí dụ: Nếu ta không đưa vào chương trình mệnh đề human(mary). Thì ?- human(mary). no Bởi vì “không có đủ thông tin trong CT chứng tỏ rằng mary là human”. 44 XUẤT NHẬP Tương tác với file:  Cho đến bây giờ, tương tác giữa người sử dụng với CT chỉ là người sử dụng đặt các truy vấn với CT và CT trả lời bằng những sự gán trị cụ thể vào biến.  Phương cách tương tác này rất hạn chế. Những mở rộng sau đây là cần thiết :  Nhập dữ liệu ở dạng khác với các truy vấn – thí dụ những câu văn bản.  Xuất dữ liệu khác với khuôn mẫu mong muốn.  Xuất/nhập từ file, chứ không chỉ từ terminal của người sử dụng.  Các vị từ thư viện dùng cho I/O tuỳ thuộc vào từng hệ thống Prolog. Ta nên tham khảo sách hướng dẫn sử dụng cho hệ thống Prolog để biết chi tiết về những vị từ đó.  Trong chương này trình bày một số vị từ xuất/nhập cơ bản nhất. 45  Về nguyên tắc, CT có đọc dữ liệu từ nhiều file nhập, cũng được gọi là dòng nhập (input stream), và xuất dữ liệu ra nhiều file xuất được gọi là dòng xuất (output stream) Terminal Người sử dụng Chương trình Những dòng xuất Những dòng nhập File1 File2 File3 File4 user user Dữ liệu từ terminal của người sử dụng cũng được coi như là một dòng nhập dữ liệu được xuất ra terminal của người sử dụng cũng được coi như là một dòng xuất. Cả hai tập tin này được coi như có tên là “user”. 46 Tương tác với file  Tên của các file khác được chọn bởi người lập trình.  Tại mỗi lúc thực thi một chương trình Prolog, chỉ có hai file tham gia: một cho nhập và một cho xuất. Hai file này được gọi là dòng nhập hiện hành và dòng xuất hiện hành.  Ban đầu, hai dòng này tương ứng với terminal của người sử dụng. Ta có thể chuyển dòng nhập hiện hành sang một file khác, filename, bởi ví dụ: see(filename)  Một mục tiêu như vậy sẽ khiến việc nhập dữ liệu được chuyển từ dòng dữ liệu trước đó sang tập tin filename.  Thí dụ: see(file1), // nhập liệu từ tập tin file1// see(user), . 47 Tương tác với file (tt.)  Dòng dữ liệu xuất được chuyển hướng bằng mục tiêu có dạng: tell(Filename)  Thí dụ: tell(file3), // xuất dữ liệu ra tập tin file3// tell(user), .  Mục tiêu seen đóng file nhập hiện hành.  Mục tiêu told đóng file xuất hiện hành. 48 Xử lý các file toán hạng Read và write.  Vị từ thư viện read được dùng để đọc các toán hạng trên dòng nhập hiện hành.  Tiểu mục tiêu read(X) sẽ khiến một toán hạng T, được đọc và toán hạng này sẽ đối sánh với X. Nếu X là một biến thì X được gán giá trị T. Nếu sự đối sánh không thành công thì tiểu mục tiêu read(X) thất bại.  Vị từ read(X) là tất định, vì khi nó thất bại thì không có backtracking để lấy vào toán hạng khác.  Nếu read(X) được thực thi mà gặp điểm cuối file, thì X sẽ được gán trị đặc biệt nguyên tử end-of-file. 49  Vị từ write xuất ra một toán hạng. Như vậy, tiểu mục tiêu write(X) sẽ xuất toán hạng X tại file xuất hiện hành. Vị từ write biết cách trình bày mọi toán hạng, bất luận nó phức tạp như thế nào.  Có những vị từ thư viện giúp việc lập khuôn mẫu khi xuất.  Đó là vị từ tab(N) khiến cho N khoảng trống được xuất ra.  Vị từ nl khiến cho bắt đầu một hàng mới. ? – cube. 2. 8 5. 125 12. 1728 stop. yes Thí dụ: cube :- read(X), process(X). process(stop):- !. process(N) :- C is N*N*N, write(C), nl, cube. 50  Cải tiến thủ tục cube: cube:- write(‘ Next item, please:’),read(X),process(X). process(stop):- !. process(N) :- C is N*N*N, write(‘ Cube of’), write(N), write(‘is’), write( C), nl , cube. ?-cube. Next item, please: 5. Cube of 5 is 125 Next item, please :12. Cube of 12 is 1728 Next item, please: stop. yes 51  Trình bày list. writelist([ L ]). writelist([X | L]):- write(X), nl, writelist(L). Mỗi phần tử ở trên 1 hàng riêng.  In ra một list của list. writelist2([]) writelist2([L|LL]):- doline(L), nl , writelist2(LL). doline([ ]) doline([X|L]):- write(X), write(‘ ’), doline(L). Sẽ in ra mỗi phần tử trên một hàng. ?- writelist2([[a,b,c]),[d,e,f],[g,h]]). a b c d e f g h 52 Chế biến các ký tự  Một kí tự được đưa ra dòng xuất hiện hành bằng tiểu mục tiêu . put( C ) với C là mã ASCII của kí tự xuất.  Thí dụ: ?- put(65), put(66), put(67). sẽ gây ra dòng xuất như sau ABC  Một ký tự có thể được đọc từ dòng dữ liệu nhập từ tiểu mục tiêu: get0(C).  Điều này khiến cho một kí tự hiện hành được đọc từ dòng nhập và kí tự C được gán mã ASCII của kí tự này.  Một biến dạng của vị từ get0 là vị từ get, mà được dùng để đọc những ký tự khác khoảng trống.  Tiểu mục tiêu get(C) sẽ bỏ qua những ký tự không in được (non- printable) từ vị trí nhập hiện hành. 53  Thí dụ: squeeze :- get0(C), put(C) dorest( C ). dorest( 46 ):- !. % 46 là mã ASCII của dấu chấm. dorest( 32 ) :- !, get( C ), % 32 là mã ASCII cho khoảng trống put( C ), dorest(C ). dorest(letter):- squeeze. Đọc chương trình: ( consult ):  Để ra lệnh cho Prolog đọc một chương trình từ một file văn bản F (tên của một file chương trình), ta dùng tiểu mục tiêu : consult(F).  Hiệu ứng: tất cả các mệnh đề trong F sẽ được đọc và sẽ được dùng bởi Prolog khi trả lời những câu hỏi sau đó từ người sử dụng. ( F phải là một file văn bản đã được tạo ra) 54 MỘT SỐ VỊ TỪ THƯ VIỆN QUAN TRỌNG Thử loại toán hạng: Các vị từ var, nonvar, atom, integer, real, atomic  Toán hạng có thể thuộc nhiều loại Toán hạng  biến  Số nguyên, số thực  Nguyên tử  Nếu một toán hạng là một biến thì nó có thể được gán trị (instantiated). Tại một thời điểm thực thi nào đó, hoặc không được gán trị. Khi được gán trị, thì trị của nó có thể là một nguyên tử, cấu trúc, v.v Đôi khi rất có ích khi biết loại của trị nào: thí dụ, chúng ta có thể viết: Z is X + Y  Nếu chúng ta không chắc rằng X và Y được gán trị ( trước khi được cộng ) thì chúng ta nên thử, bằng cách dùng hàm thư viện integer ..., integer(X), integer(Y), Z is X + Y, ... 55  Các vị từ thư viện thuộc loại này gồm: var, nonvar, atom, integer, real, atomic.  var(X) : sẽ thành công khi X là một biến không gán trị  nonvar(X) : sẽ thành công nếu X là một toán hạng khác biến hoặc X là một biến đã được gán trị  atom(X) : sẽ thành công nếu X là một nguyên tử  integer(X) : sẽ thành công nếu X là một số nguyên  real(X) : sẽ thành công nếu X là một số thư thực  atomic(X) : sẽ thành công nếu X hiện là một số nguyên hoặc là một nguyên tử. 56 ? - Z = 2 , var( Z ). no ?- integer( Z ), Z = 2. % chöa gaùn trò maø thöû integer( Z ) no ? - Z = 2, integer( Z ), nonvar( Z ). Z = 2. ?- atom( 22 ). no ?- atom(==> ). yes ?- atom( p(1) ). no  Thí duï 1: Ta muoán ñeám coù bao nhieâu laàn moät nguyeân töû xuaát hieän trong moät list ñoái töôïng count( A, L , N ). count( _, [ ] , O ). count( A , [ BL ], N ) :- atom( B ), A = B, ! , count( A, L, N1 ), N is N1 + 1. count( A , [ _L ] , N ) :- count( A, L, N ) . 57 Cấu tạo và phân rã toán hạng: = .., functor, arg  Có 3 vị từ thư viện dùng để phân rã toán hạng và cấu tạo toán hạng mới: functor, arg, và = ..  Xét = .. , được viết như là một toán tử infix. Tiểu mục tiêu Term = .. L là đúng nếu L là một list bao gồm hàm tử chính của tóan hạng Term và sau đó là các đối số của nó.  Thí dụ: ? – f(a,b) = .. L L = [f,a,b] ? – T =.. [rectangle, 3,5]. T = rectangle(3,5) ?- Z = .. [p,X,f(X,Y)]. Z = p(X, f(X,Y)) 58  Tại sao ta lại cần phân rã toán hạng thành những phần : hàm tử và đôí số ? và tại sao ta muốn xây dựng 1 toán hạng mới từ một hàm tử và các toán hạng đã cho ?  Thí dụ: Bài toán xử lý ký hiệu của công thức: tác vụ thay thế những biểu thức con nào đó bằng những biểu thức con khác. Ta định nghĩa quan hệ: substitute(Subterm, Term, Subterm1, Term1)  Như sau: tất cả những sự xuất hiện của Subterm trong Term được thay thế bằng Subterm1, và rồi ta sẽ có được Term1. ?- substitute( sin(x), 2*sin(x)*f(sin(x)), t, F). F = 2*t*f(t)  Sự xuất hiện của Subterm trong Term hiểu theo nghĩa một bộ phận nào đó trong Term hợp nhất được với Subterm. ?- subtitute( a + b, f(a, A + B),v, F). sẽ cho ra : F = f(a,v) A = a B = b 59 % sutitute(subterm, term,subterm1,term1): % if all occurrences of subterm in term subtitute with subterm1 % then rise get term1 % case 1: thay toaùn haïng subtitute(Term, Term, Term1, Term1):- !. % case 2: khoâng thay gì caû neáu term laø nguyeân töû hoaëc soá subtitute( _ , Term, _ , Term) :- atomic(Term),!. % case 3: thöïc hieän thay theá treân caùc ñoái soá. subtitute(Sub, Term, Sub1, Term1) :- Term = .. [ F | Args], substlist( Sub, Args, Sub1, Args1), Term1 = .. [ F | Args1]. substlist( _ ,[], _ , []). substlist(Sub,[Term| Terms], Sub1, [Term1, Terms1]):- subtitute(Sub, Term, Sub1, Term1), substlist(Sub, Terms, Sub1, Terms1). 60 Vị từ =..  Toán hạng mà được cấu tạo bằng cách dùng vị từ “ = ..” thì cũng có thể được dùng như những mục tiêu. Tiện lợi của cách này là khi thực thi CT có thể tạo và thực thi những mục tiêu dạng thức không thể tiên đoán trước tại lúc viết CT.  Thí dụ : Đoạn chương trình với 1 chuỗi mục tiêu: obtain( Functor), compute(Arglist), Goal = .. [ Functor| Arglist], Goal.  Ở đây obtain và compute là những vị từ cấu tạo nên mục tiêu mà cần thực thi. Mục tiêu được tạo ra, rồi sẽ được gọi ra để thực thi bằng cách nêu tên nó lên, goal 61  Nhiều hệ thống Prolog đòi hỏi một mục tiêu phải được viết như là một nguyên tử hay là một cấu trúc với một nguyên tử dùng như là một hàm tử. Một biến, dù thế nào, cũng không được chấp nhận về mặt ngữ pháp như là một mục tiêu.  Vấn đề này có thể được khắc phục bằng một vị từ thư viện, call, mà đối số của nó là một tiểu mục tiêu cần thực thi. ......... Goal = ..[ Functor| Arglist], call(Goal).  Đôi khi ta cần trích ra từ một toán hạng chỉ hàm tử chính của nó hoặc là một trong những đối số của nó. 62 Các vị từ functor và arg  functor( Term, F, N) traû veà trò ñuùng neáu F laø haøm töû chính cuûa Term vaø N laø soá ñoái soá cuûa Term.  arg(N, Term,A) laø ñuùng neáu A laø ñoái soá thöù N cuûa Term.  Thí duï: ?- functor(t(f(X),X,t),Fun,Arity). Fun = t Arity = 3 ?- arg(2,f(X,t(a),t(b)),Y). Y = t(a) ?- functor(D,date,3), arg(1,D,29), arg(2,D,june), arg(3,D,1982). D = date(29, june, 1982) 63 Các loại đẳng thức khác nhau Có 3 loại đẳng thức khác nhau.  Loại thứ nhất dựa trên sự đối sánh: X = Y trả về trị đúng nếu X và Y hợp nhất được Loại thứ nhất khác được viết là: X is E trả về trị đúng nếu X đối sánh được với trị của biểu thức số học E  Loại thứ hai để so sánh 2 biểu thức số học: E1 =:= E2 trả về trị đúng nếu hai trị của hai biểu thức số học bằng nhau. E1=\= E2 trả về trị đúng nếu hai trị của hai biểu thức số học tại E1, E2 là khác nhau.  Loại thứ 3 ( một loại đẳng thức khó tính hơn) T1 = = T2 trả về trị đúng nếu hai toán hạng T1, T2 giống hệt nhau (chúng có cùng cấu trúc và tất cả các thành phần giống hệt nhau) T1 \ = = T2 T1, T2 không giống hệt nhau 64  Thí dụ: ?- f( a,b) = = f(a,b). yes ?- f(a,b) = = f(a,X). no ?- t(X,f(a,X)) = = t(X,f(a,X)). yes  Thí dụ: Đếm số lần suất hiện của một toán hạng trong một list. count( _ , [], 0). count(Term,[Head| Tail], N):- Term = = Head,!, count(Term, Tail, N1), N is N1 +1. count(Term, [ _ | Tail], N):- count(Term, Tail, N). 65 Các phương tiện điều khiển  Chúng ta đã điểm qua tất cả các phương tiện điều khiển trừ repeat. + cut: ngăn cản backtracking. + fail : mục tiêu mà luôn luôn thất bại. + true : mục tiêu mà luôn luôn thành công + not(P): một dạng của phủ định mà có nghĩa not(P) : - P,!, fail. not(P). + call(P): gọi mục tiêu P, nó thành công nếu P thành công. + repeat: là một mục tiêu luôn luôn thành công. Đặc tính đặc biệt của nó là không tất định; do đó mỗi lần nó được đạt tới do quay lui, nó sinh ra một nhánh thực thi khác. repeat làm việc như là: repeat. repeat :- repeat. 66 repeat  Thí dụ: dosquares:- repeat, read(X), dowrite(X). dowrite(X):- X = stop,!. dowrite(X):- Y is X*X, write(Y), nl, fail.  Thủ tục trên đọc vào một chuỗi con số và xuất ra những bình phương của chúng. Chuỗi thực hiện này kết thúc với nguyên tử stop. Loại vòng lặp này được gọi là failure-driven-loop. 67 Vị từ bagof and findall  Chúng ta có thể sinh ra, nhờ backtracking, tất cả những đối tượng, từng đối tượng một thỏa mãn được mục tiêu nào đó. Mỗi lần một lời giải mới được tạo ra, lời giải cũ đã biến mất và không còn có thể truy đạt đến.  Tuy nhiên, đôi khi ta cần gom tất cả các lời giải lại, thí dụ, thành một list. Vị từ thư viện bagof và findall phục vụ cho mục đích này.  Vị từ bagof(X,P,L) sinh ra một list L các đối tượng X thỏa mãn quan hệ P. Điều này có nghĩa chỉ khi X và P có những biến chung.  Ví dụ: Ta có các sự kiện age(peter,7). age(ann,5). age(pat,8). age(tom,5). Để có một danh sách tất cả những đứa trẻ 5 tuổi, ta dùng truy vấn: ?- bagof( Child, age(Child, 5), List). List = [ann, tom] 68  Nếu ta để tuổi là biến chưa gán trị, ta sẽ được, thông qua sự quay lui, ba danh sách, tuỳ theo ba độ tuổi của trẻ. ?- bagof( Child, age(Child, Age), List). Age = 7 List = [peter]; Age = 5 List = [ann, tom]; Age = 8 List = [pat] No  Một vị từ tương tự như bagof là vị từ findall. Vị từ findall(X, P,L) sinh ra một list L các đối tượng X thỏa mãn quan hệ P.  Điểm khác biệt của findall với bagof là tất cả các đối tượng X được thu gom bất kể những lời giải khác nhau cho các biến trong P mà khác với X.  Thí dụ: ?- findall( Child,age(Child, Age), List). List = [peter, ann, pat, tom]