Giáo trình Lập trình hàm và Lập trình Logic - Chương 3: Ngôn ngữ Prolog - Phan Huy Khánh

ụ VII.1 : Định nghĩa hàm số học cộng hai số bất kỳ plus(X, Y, Z) :- % trường hợp tính Z = X + Y nonvar(X), nonvar(Y), Z is X + Y. plus(X, Y, Z) :- % trường hợp tính X = Z - Y nonvar(Y), nonvar(Z), X is Z - Y. plus(X, Y, Z) :- % trường hợp tính Y - Z - X nonvar(X), nonvar(Z), Y is Z - X. ?- add1(2, 3, X). X = 5 Yes add1(7, X, 3). X = -4 Yes add1(X, 2, 6). X = 4 Yes VII.1. Định nghĩa hàm sử dụng đệ quy Trong chương 1, ta đã trình bày cách định nghĩa các luật (mệnh đề) đệ quy. Sau đây, ta tiếp tục ứng dụng phép đệ quy để xây dựng các hàm. Tương tự các ngôn ngữ lập trình mệnh lệnh, một thủ tục đệ quy của Prolog phải chứa các mệnh đề thoả mãn 3 điều kiện : • Một khởi động quá trình lặp. LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 173 • Một sơ đồ lặp lại chính nó. • Một điều kiện dừng. Ví dụ thủ tục đệ quy tạo dãy 10 số tự nhiên chẵn đầu tiên như sau : đầu tiên lấy giá trị 0 để khởi động quá trình. Sau đó lấy 0 là giá trị hiện hành để tạo số tiếp theo nhờ sơ đồ lặp : even_succ_nat = even_succ_nat + 2. Quá trình cứ tiếp tục như vậy cho đến khi đã có đủ 10 số 0 2 4 6 8 10 12 14 16 18 thì dừng lại. Trong Prolog, một mệnh đề đệ quy (để tạo sơ đồ lặp ) là mệnh đề có chứa trong thân (vế phải) ít nhất một lần lời gọi lại chính mệnh đề đó (vế trái) : a(X) :- b(X, Y), a(Y). Mệnh đề a gọi lại chính nó ngay trong vế phải. Dạng sơ đồ lặp như vậy được gọi là đệ quy trực tiếp. Để không xảy ra lời gọi vô hạn, cần có một mệnh đề làm điều kiện dừng đặt trước mệnh đề. Mỗi lần vào lặp mới, điều kiện dừng sẽ được kiểm tra để quyết định xem có thể tiếp tục gọi a hay không ? Ta xây dựng thủ tục even_succ_nat(Num, Count) tạo lần lượt các số tự nhiên chẵn Num, biến Count để đếm số bước lặp. Điều kiện dừng là Count=10, ta có : even_succ_nat(Num, 10). Mệnh đề lặp được xây dựng như sau : even_succ_nat(Num, Count) :- write(Num), write(' '), Count1 is Count + 1, Num1 is Num + 2, even_succ_nat(Num1, Count1). Như vậy, lời gọi tạo 10 số tự nhiên chẵn đầu tiên sẽ là : ?- even_succ_nat(0, 0). 0 2 4 6 8 10 12 14 16 18 Yes Một cách khác để xây dựng sơ đồ lặp được gọi là đệ quy không trực tiếp có dạng như sau : a(X) :- b(X). b(X) :- c(Y...), a(Z). Trong sơ đồ lặp này, mệnh đề đệ quy a không gọi gọi trực tiếp đến a, mà gọi đến một mệnh đề b khác, mà trong b này lại có lời gọi đến a. Để không xảy ra lời gọi luẩn quẩn vô hạn, trong b cần thực hiện các tính toán làm giảm dần quá trình lặp trước khi gọi lại mệnh đề a (ví dụ mệnh đề c). Ví dụ sơ đồ dưới đây sẽ gây ra vòng luẩn quẩn vô hạn : a(X) :- b(X, Y). b(X, Y) :- a(Z). Bài toán tạo 10 số tự nhiên chẵn đầu tiên được viết lại theo sơ đồ đệ quy không trực tiếp như sau : a(0). a(X) :- b(X). b(X) :- X1 is X - 2, write(X), write(' '), a(X1). Chương trình này không gọi « đệ quy » như even_succ_nat. Kết quả sau lời gọi a(20) là dãy số giảm dần 20 18 16 14 12 10 8 6 4 2. Ví dụ VII.2 : Xây dựng số tự nhiên (Peano) và phép cộng trên các số tự nhiên /* Định nghĩa số tự nhiên */ nat(0). % 0 là một số tự nhiên LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 174 nat(s(N)) :- % s(X) cũng là một số tự nhiên nat(N). % nếu N là một số tự nhiên Chẳng hạn số 5 được viết : s(s(s(s(s(zero))))) /* Định nghĩa phép cộng */ addi(0, X, X). % luật 1 : 0 + X = X /* addi(X, 0, X). có thể sử dụng them luật 2 : X + 0 = X addi(s(X), Y, s(Z)) :- % luật 3 : nếu X + Y = Z thì (X+1) + Y = (Z+1) addi(X, Y, Z). Hoặc định nghĩa theo nat(X) như sau : addi(0, X, X) :- nat(X). ?- addi(X, Y, s(s(s(s(0))))). X = 0 Y = s(s(s(s(0)))) Yes ?- addi(X, s(s(0)), s(s(s(s(s(0)))))). X = s(s(s(0))) Yes ?- THREE = s(s(s(0))), FIVE = s(s(s(s(s(0))))), addi(THREE, FIVE, EIGHT). THREE = s(s(s(0))) FIVE = s(s(s(s(s(0))))) EIGHT = s(s(s(s(s(s(s(s(0)))))))) Yes Ví dụ VII.3 : Tìm ước số chung lớn nhất (GCD: Greatest Common Divisor) Cho trước hai số nguyên X và Y, ta cần tính ước số D và USCLN dựa trên ba quy tắc như sau : 1. Nếu X = Y, thì D bằng X. 2. Nếu X < Y, thì D bằng USCLN của X và của Y - X. 3. Nếu X > Y, thì thực hiện tương tự bước 2, bằng cách hoán vị vai trò X và Y. Có thể dễ dàng tìm được các ví dụ minh hoạ sự hoạt động của ba quy tắc trước đây. Với X =20 và Y =25, thì ta nhận được D =5 sau một dãy các phép trừ. Chương trình Prolog được xây dựng như sau : gcd( X, X, X ). gcd( X, Y, D ) :- X < Y, Y1 is Y – X, gcd( X, Y1, D ). gcd( X, Y, D ) :- X > Y, gcd( Y, X, D ). Đích cuối cùng trong mệnh đề thứ ba trên đây có thể được thay thế bởi : X1 is X – Y, gcd( X1, Y, D ). Kết quả chạy Prolog như sau : LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 175 ?- gcd( 20, 55, D ). D = 5 Ví dụ VII.4 : Tính giai thừa fac(0, 1). fac(N, F) :- N > 0, M is N - 1, fac(M, Fm), F is N * Fm. Mệnh đề thứ hai có nghĩa rằng nếu lần lượt : N > 0, M = N - 1, Fm is (N-1)!, và F = N * Fm, thì F là N!. Phép toán is giống phép gán trong các ngôn ngữ lập trình mệnh lệnh nhưng trong Prolog, is không gán giá trị mới cho biến. Về mặt lôgich, thứ tự các mệnh đề trong vế phải của một luật không có vai trò gì, nhưng lại có ý nghĩa thực hiện chương trình. M không phải là biến trong lời gọi thủ tục đệ quy vì sẽ gây ra một vòng lặp vô hạn. Các định nghĩa hàm trong Prolog thường rắc rối do hàm là quan hệ mà không phải là biểu thức. Các quan hệ được định nghĩa sử dụng nhiều luật và thứ tự các luật xác định kết quả trả về của hàm... Ví dụ VII.5 : Tính số Fibonacci /* Fibonacci function */ fib(0, 0). % fib0 = 0 fib(1, 1). % fib1 = 1 fib(N, F) :- % fibn+2 = fibn+1 + fibn N > 1, N1 is N - 1, fib(N1, F1), N2 is N - 2, fib(N2, F2), F is F1 + F2. ?- fib(20, F). F = 10946 Yes ?- fib(21, F). ERROR: Out of local stack Ta nhận thấy thuật toán tính số Fibonacci trên đây sử dụng hai lần gọi đệ quy đã nhanh chóng làm đầy bộ nhớ và chỉ với N=21, SWI-prolog phải dừng lại để thông báo lỗi. Ví dụ VII.6 : Tính hàm Ackerman /* Ackerman's function */ ack(0, N, A) :- % Ack(0, n) = n + 1 A is N + 1. ack(M1, 0, A) :- % Ack(m, n) = Ack(m-1, 1) M > 0, M is M - 1, ack(M, 1, A). ack(M1, N1, A) :- % Ack(m, n) = Ack(m-1, Ack(m, n-1)) M1 > 0, N1 > 0, M is M - 1, N is N - 1, LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 176 ack(M1, N, A1), ack(M, A1, A). Ví dụ VII.7 : Hàm tính tổng plus(X, Y, Z) :- nonvar(X), nonvar(Y), Z is X + Y. plus(X, Y, Z) :- nonvar(Y), nonvar(Z), X is Z - Y. plus(X, Y, Z) :- nonvar(X), nonvar(Z), Y is Z - X. Ví dụ VII.8 : Thuật toán hợp nhất Sau đây là một thuật toán hợp nhất đơn giản cho phép xử lý trường hợp một biến nào đó được thay thế (hợp nhất) bởi một hạng mà hạng này lại có chứa đúng tên biến đó. Chẳng hạn phép hợp nhất X = f(X) là không hợp lệ. % unify(T1, T2). unify(X, Y) :- % trường hợp 2 biến var(X), var(Y), X = Y. unify(X, Y) :- % trường hợp biến = không phải biến var(X), nonvar(Y), X = Y. unify(X, Y) :- % trường hợp không phải biến = biến nonvar(X), var(Y), Y = X. unify(X, Y) :- % nguyên tử hay số = nguyên tử hay số nonvar(X), nonvar(Y), atomic(X), atomic(Y), X = Y. unify(X, Y) :- % trường hợp cấu trúc = cấu trúc nonvar(X), nonvar(Y), compound(X), compound(Y), termUnify(X, Y). termUnify(X, Y) :- % hợp nhất hạng với hạng chứa cấu trúc functor(X, F, N), functor(Y, F, N), argUnify(N, X, Y). argUnify(N, X, Y) :- % hợp nhất N tham đối của X và Y N>0, argUnify1(N, X, Y), Ns is N - 1, argUnify(Ns, X, Y). argUnify(0, X, Y). argUnify1(N, X, Y) :- % hợp nhất các tham đối có bậc N arg(N, X, ArgX), arg(N, Y, ArgY), unify(ArgX, ArgY). Ví dụ VII.9 : Lý thuyết số Ta tiếp tục xây dựng hàm mới trên các số tự nhiên đã được định nghĩa trong ví dụ 1. Ta xây dựng phép so sánh hai số tự nhiên dựa trên phép cộng như sau : LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 177 egal(+(X, 0), X). % phép cộng có tính giao hoán egal(+(0, X), X). egal(+(X, s(Y)), s(Z)) :- % X YZ.egal(X+Y, Z) → egal(X+s(Y), s(Z)) egal(+(X, Y), Z). Sau đây là một số kết quả : ?- egal(s(s(0))+s(s(s(0))), s(s(s(s(s(0)))))). Yes ?- egal(+(s(s(0)), s(s(0))), X). X = s(s(s(s(0)))) ?- egal(+(X, s(s(0))), s(s(s(s(s(0)))))). X = s(s(s(0))) Yes ?- egal(+(X, s(s(0))), s(s(s(s(s(0)))))). X = s(s(s(0))) Yes ?- egal(X, s(s(s(s(0))))). X = s(s(s(s(0))))+0 ; X = 0+s(s(s(s(0)))) ; X = s(s(s(0)))+s(0) ; X = 0+s(s(s(s(0)))) ; X = s(s(0))+s(s(0)) ; X = 0+s(s(s(s(0)))) ; X = s(0)+s(s(s(0))) ; X = 0+s(s(s(s(0)))) ; X = 0+s(s(s(s(0)))) ; X = 0+s(s(s(s(0)))) ; No Với đích egal(X, Y) sau đây, câu trả lời là vô hạn : ?- egal(X, Y). X = _G235+0 Y = _G235 ; X = 0+_G235 Y = _G235 ; X = _G299+s(0) Y = s(_G299) ; X = 0+s(_G302) Y = s(_G302) ; X = _G299+s(s(0)) Y = s(s(_G299)) ; LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 178 X = 0+s(s(_G309)) Y = s(s(_G309)) ; X = _G299+s(s(s(0))) Y = s(s(s(_G299))) ; X = 0+s(s(s(_G316))) Y = s(s(s(_G316))) ; X = _G299+s(s(s(s(0)))) Y = s(s(s(s(_G299)))) ; X = 0+s(s(s(s(_G323)))) Y = s(s(s(s(_G323)))) ; X = _G299+s(s(s(s(s(0))))) Y = s(s(s(s(s(_G299))))) ; ... X = 0+s(s(s(s(s(s(_G337)))))) Y = s(s(s(s(s(s(_G337)))))) ; X = _G299+s(s(s(s(s(s(s(0))))))) Y = s(s(s(s(s(s(s(_G299))))))) v.v... LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 179 VII.2. Tối ưu phép đệ quy Lời giải các bài toán sử dụng đệ quy trong các ngôn ngữ lập trình nói chung thường ngắn gọn, dễ hiểu và dễ quản lý được chương trình. Tuy nhiên, trong một số trường hợp, sử dụng đệ quy lại xảy ra vấn đề về độ phức tạp tính toán, không những tốn kém bộ nhớ mà còn tốn kém thời gian. Trong các ngôn ngữ mệnh lệnh, phép tính n! sử dụng đệ quy cần sử dụng bộ nhớ có cỡ 0(n) và thời gian tính toán cũng có cỡ 0(n), thay vì gọi đệ quy, người ta thường sử dụng phép lặp fac=fac*i, i=1..n. Ta xét lại ví dụ 4 tính số Fibonacci trên đây với lời gọi đệ quy : fib(N, F) :- N > 1, N1 is N - 1, fib(N1, F1), N2 is N - 2, fib(N2, F2), F is F1 + F2. Để ý rằng mỗi lần gọi hàm fib(n) với n>1 sẽ dẫn tới hai lần gọi khác, nghĩa là số lần gọi sẽ tăng theo luỹ thừa 2. Với n lớn, chương trình gọi đệ quy như vậy dễ gây tràn bộ nhớ. Ví dụ sau đây là tất cả các lời gọi có thể cho trường hợp n=5. Hình VII.1. Biểu diễn cây các lời gọi đệ quy tìm số Fibonacci Một số ngôn ngữ mệnh lệnh tính số Fibonacci sử dụng cấu trúc lặp để tránh tính đi tính lại cùng một giá trị. Chương trình Pascal dưới đây dùng hai biến phụ x=fib(i) và y=fib(i+1) : { tính fib(n) với n > 0 } i:= 1; x:= 1; y:= 0; while i < n do begin x:= x + y; y:= x – y end; Ta viết lại chương trình Prolog như sau : fibo(0, 0). fibo(N, F) :- N >= 1, fib1(N, 1, 0, F). fib1(1, F, _, F). fib1(N, F2, F1, FN) :- N > 1, N1 is N - 1, F3 is F1 + F2, fib1(N1, F3, F2, FN). ?- fibo(21, F). F = 10946 Yes fib5 4 3 3 2 2 1 2 1 1 0 1 0 1 0 LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 180 ?- fibo(200, F). F = 2.80571e+041 Yes VII.3. Một số ví dụ khác về đệ quy VII.3.1. Tìm đường đi trong một đồ thị có định hướng Cho một đồ thị có định hướng như sau : Hình VII.2. Tìm đường đi trong một đồ thị có định hướng. Ta xét bài toán tìm đường đi giữa hai đỉnh của đồ thị. Mỗi cung nối hai đỉnh của đồ thị biểu diễn một quan hệ giữa hai đỉnh này. Từ đồ thị trên, ta có thể viết các mệnh đề Prolog biểu diễn các sự kiện : arc(a, b). arc(b, c). arc(c, e). arc(c, d). arc(a, e). Giả sử cần kiểm tra có tồn tại một đường đi giữa hai nút a và d (không tồn tại đường đi giữa hai nút này như đã mô tả), ta viết mệnh đề : path(a, d). Để định nghĩa này, ta nhận xét như sau : • Tồn tại một đường đi giữa hai nút có cung nối chúng. • Tồn tại một đường đi giữa hai nút X và Y nếu tồn tại một nút thứ ba Z sao cho tồn tại một đường đi giữa X và Z và một đường đi giữa Z và Y. Ta viết chương trình như sau : path(X, Y) :- arc(X, Y). path(X, Y) :- arc(X, Z), path(Z, Y). Ta thấy định nghĩa thủ tục path(X, Y) tương tự thủ tục tìm tổ tiên gián tiếp giữa hai người trong cùng dòng họ ancestor(X, Y) đã xét trước đây. ?- path(X, Y). X = a Y = b ; X = b Y = c ; ... A B C D E LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 181 VII.3.2. Tính độ dài đường đi trong một đồ thị Ta xét bài toán tính độ dài đường đi giữa hai nút, từ nút đầu đến nút cuối trong một đồ thị là số cung giữa chúng. Chẳng hạn độ dài đường đi giữa hai nút a và d là 3 trong ví dụ trên. Ta lập luận như sau : • Nếu giữa hai nút có cung nối chúng thì độ dài đường đi là 1. • Gọi L là độ dài đường đi giữa hai nút X và Y, L1 là độ dài đường đi giữa một nút thứ ba Z và Y nếu tồn tại và giả sử có cung nối X và Z, khi đó L = L1 + 1. Chương trình được viết như sau : trajectory(X, Y, 1) :- arc(X, Y). trajectory(X, Y, L) :- arc(X, Z), trajectory(Z, Y, L1), L is L1 + 1. trajectory(a, d, L). L = 3 Yes VII.3.3. Tính gần đúng các chuỗi Trong Toán học thường gặp bài toán tính gần đúng giá trị của một hàm số với độ chính xác nhỏ tuỳ ý (e) theo phương pháp khai triển thành chuỗi Max Loren. Ví dụ tính hàm mũ ex với độ chính xác 10-6 nhờ khai triển chuỗi Max Loren : 2 3 1 ... 2! 3! x x xe x= + + + + Gọi expower(X, S) là hàm tính giá trị hàm mũ theo X, biến S là kết quả gần đúng với độ chính xác e=10-6. Từ công thức khai triển Max Loren trên đây, ta nhận thấy giá trị của hàm mũ ex là tổng vô hạn có dạng : sum(0) = 1, t0 = 1 tương ứng với x = 0 và ex = 1 sum(i+1) = sum(i) + ti+1, với ti+1 = ti * x /( i+1), i = 0, 1, 2 ... Để thực hiện phép lặp, ta cần xây dựng hàm đệ quy tính tổng sum(X, S, I, T) trong đó sử dụng các biến trung gian I là bước lặp thứ i và T là số hạng ti. Theo cách xây dựng này, hàm tính tổng sum(X, S, I, T) là tổng của các số hạng thứ I trở đi của chuỗi. Quá trình tính các tổng dừng lại khi ti< e, nghĩa là đã đạt được độ chính xác e. Tại thời điểm này, giá trị của tổng cũng chính là số hạng ti. Điều kiện khởi động quá trình lặp là chuyển vị từ expower(X, S) thành vị từ tính tổng sum(X, S, I, T) với giá trị đầu I=0 và T=1. Ta có chương trình đệ quy như sau : expower(X, S) :- sum(X, S, 0, 1). sum(_, T, _, T) :- abs(T) < 0.000001. sum(X, S, I, T) :- abs(T) > 0.000001, I1 is I + 1, T1 is T*X/I1, sum(X, S1, I1, T1), S is S1 + T. LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 182 ?- expower(1, S). S = 2.71828 Yes ?- expower(10, S) S = 22026.5 Yes VIII. Biểu diễn cấu trúc danh sách Danh sách là kiểu cấu trúc dữ liệu được sử dụng rộng rãi trong các ngôn ngữ lập trình phi số. Một danh sách là một dãy bất kỳ các đối tượng. Khác với kiểu dữ liệu tập hợp, các đối tượng của danh sách có thể trùng nhau (xuất hiện nhiều lần) và mỗi vị trí xuất hiện của đối tượng đều có ý nghĩa. Danh sách là cách diễn đạt ngắn gọn của kiểu dữ liệu hạng phức hợp trong Prolog. Hàm tử của danh sách là dấu chấm “.”. Do việc biểu diễn danh sách bởi hàm tử này có thể tạo ra những biểu thức mập mờ, nhất là khi xử lý các danh sách gồm nhiều phần tử lồng nhau, cho nên Prolog quy ước đặt dãy các phần tử của danh sách giữa các cặp móc vuông. Chẳng hạn .(a,.(b,[ ])). Là danh sách [ a, b ]. Danh sách các phần tử anne, tennis, tom, skier (tên người) được viết : [ anne, tennis, tom, skier ] chính là hàm tử : . ( anne, .( tennis, .( tom, .( skier, [ ] ) ) ) ) Cách viết dạng cặp móc vuông chỉ là xuất hiện bên ngoài của một danh sách. Như đã thấy ở mục trước, mọi đối tượng cấu trúc của Prolog đều có biểu diễn cây. Danh sách cũng không nằm ngoại lệ, cũng có cấu trúc cây. Làm cách nào để biểu diễn danh sách bởi một đối tượng Prolog chuẩn ? Có hai khả năng xảy ra là danh sách có thể rỗng hoặc không. Nếu danh sách rỗng, nó được viết dưới dạng một nguyên tử : [ ] Nếu danh sách khác rỗng, có thể xem nó được cấu trúc từ hai thành phần (pair syntax) : 1. Thành phần thứ nhất, được gọi là đầu (head) của danh sách. 2. Thành phần thứ hai, phần còn lại của danh sách (trừ ra phần đầu), được gọi là đuôi (tail) của danh sách, cũng là một danh sách. Trong ví dụ trên thì đầu là anne, còn đuôi là danh sách : [ tennis, tom, skier ] Nói chung, đầu của danh sách có thể là một đối tượng bất kỳ của Prolog, có thể là cây hoặc biến, nhưng đuôi phải là một danh sách. Hình VIII.1. Biểu diễn dạng cây của danh sách mô tả cấu trúc cây của danh sách đã cho : LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 183 Hình VIII.1. Biểu diễn dạng cây của danh sách Vì đuôi tail là một danh sách, nên tail có thể rỗng, hoặc lại có thể được tạo thành từ một đầu head và một đuôi tail khác. Chú ý rằng danh sách rỗng xuất hiện trong số các hạng, vì rằng phần tử cuối cùng có thể xem là danh sách chỉ gồm một phần tử duy nhất có phần đuôi là một danh sách rỗng: [ skier ] Ví dụ trên đây minh hoạ nguyên lý cấu trúc dữ liệu tổng quát trong Prolog áp dụng cho các danh sách có độ dài tuỳ ý. ?- L1 = [ a, b, c ]. ?- L2 = [ a, a, a ]. L1 = [ a, b, c ] L2 = [ a, a, a ] ?- Leisure1 = [ tennis, music, [ ] ]. ?- Leisure2 = [ sky, eating ], ?- L = [ anne, Leisure1, tom, Leisure2 ]. Leisure1 = [ tennis, music ] Leisure2 = [ sky, eating ] L = [ anne, [ tennis, music ], tom, [ sky, eating ] ] Như vậy, các phần tử của một danh sách có thể là các đối tượng có kiểu bất kỳ, kể cả kiểu danh sách. Thông thường, người ta xử lý đuôi của danh sách như là một danh sách. Chẳng hạn, danh sách : L = [ a, b, c ] có thể viết : tail = [ b, c ] và L = .(a, tail) Để biểu diễn một danh sách được tạo thành từ đầu (Head) và đuôi (Tail), Prolog sử dụng ký hiệu | (split) để phân cách phần đầu và phần đuôi như sau : L = [ a | Tail ] Ký hiệu | được dùng một cách rất tổng quát bằng cách viết một số phần tử tuỳ ý của danh sách trước | rồi danh sách các phần tử còn lại. Danh sách bây giờ được viết lại như sau : [ a, b, c ] = [ a | [ b, c ] ] = [ a, b | [ c ] ] = [ a, b, c | [ ] ] Sau đây là một số cách viết danh sách : Kiểu hai thành phần Kiểu liệt kê phần tử [ ] [ ] [ a | [ ] ] [ a ] [ a | b | [ ] ] [ a, b ] . anne . đuôi cũng là danh sách đầu tennis . tom . skier [ ] LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 184 [ a | X ] [ a | X ] [ a | b | X ] [ a, b | X ] [ X1 | [ ... [ Xn | [ ] ]... ] ] [ X1, ... , Xn ] Ta có thể định nghĩa danh sáchtheo kiểu đệ quy như sau : List Æ [ ] List Æ [ Element | List ] IX. Một số vị từ xử lý danh sách của Prolog SWI-Prolog có sẵn một số vị từ xử lý danh sách như sau : Vị từ Ý nghĩa append(List1, List2, List3) Ghép hai danh sách List1 và List2 thành List3. member(Elem, List) Kiểm tra Elem có là phần tử của danh sách List hay không, nghĩa là Elem hợp nhất được với một trong các phần tử của List. nextto(X, Y, List) Kiểm tra nếu phần tử Y có đứng ngay sau phần tử X trong danh sách List hay không. delete(List1, Elem, List2) Xoá khỏi danh sách List1 những phần tử hợp nhất được với Elem để trả về kết quả List2. select(Elem, List, Rest) Lấy phần tử Elem ra khỏi danh sách List để trả về những phần tử còn lại trong Rest, có thể dùng để chèn một phần tử vào danh sách. nth0(Index, List, Elem) Kiểm tra phần tử thứ Index (tính từ 0) của danh sách List có phải là Elem hay không. nth1(Index, List, Elem) Kiểm tra phần tử thứ Index (tính từ 1) của danh sách List có phải là Elem hay không. last(List, Elem) Kiểm tra phần tử đứng cuối cùng trong danh sách List có phải là Elem hay không. reverse(List1, List2) Nghịch đảo thứ tự các phần tử của danh sách List1 để trả về kết quả List2. permutation(List1, List2) Hoán vị danh sách List1 thành danh sách List2. flatten(List1, List2) Chuyển danh sách List1 chứa các phần tử bất kỳ thành danh sách phẳng List2. Ví dụ : flatten([a, [b, [c, d], e]], X). cho kết quả X = [a, b, c, d, e]. sumlist(List, Sum) Tính tổng các phần tử của danh sách List chứa toàn số để trả về kết quả Sum. numlist(Low, High, List) Nếu Low và High là các số sao cho Low =< High, thì trả về danh sách List = [Low, Low+1, ..., High]. Chú ý một số vị từ xử lý danh sách có thể sử dụng cho mọi ràng buộc, kể cả khi các tham đối đều là biến. LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 185 Trong Prolog, tập hợp được biểu diễn bởi danh sách, tuy nhiên, thứ tự các phần tử trong một tập hợp là không quan trọng, các đối tượng dù xuất hiện nhiều lần chỉ được xem là một phần tử của tập hợp. Các phép toán về danh sách có thể áp dụng cho các tập hợp. Đó là : • Kiểm tra một phần tử có mặt trong một danh sách tương tự việc kiểm tra một phần tử có thuộc về một tập hợp không ? • Ghép hai danh sách để nhận được một danh sách thứ ba tương ứng với phép hợp của hai tập hợp. • Thêm một phần tử mới, hay loại bỏ một phần tử. Prolog có sẵn một số vị từ xử lý tập hợp như sau : Vị từ Ý nghĩa is_set(Set) Kiểm tra Set có phải là một tập hợp hay không list_to_set(List, Set) Chuyển danh sách List thành tập hợp Set giữ nguyên thứ tự các phần tử của List (nếu List có các phần tử trùng nhau thì chỉ lấy phần tử gặp đầu tiên). Ví dụ : list_to_set([a,b,a], X) cho kết quả X = [a,b]. intersection(Set1, Set2, Set3) Phép giao của hai tập hợp Set1 và Set2 là Set3. subtract(Set, Delete, Result) Trả về kết quả phép hiệu của hai tập hợp Set và Delete là Result (là tập Set sau khi đã xoá hết các phần tử của Delete có mặt trong đó). union(Set1, Set2, Set3) Trả về kết quả phép hợp của hai tập hợp Set1 và Set2 là Set3. subset(Subset, Set) Kiểm tra tập hợp Subset có là tập hợp con của Set hay không. X. Các thao tác cơ bản trên danh sách X.1. Xây dựng lại một số vị từ có sẵn Sau đây ta sẽ trình bày một số thao tác cơ bản trên danh sách bằng cách xây dựng lại một số vị từ có sẵn của Prolog. X.1.1. Kiểm tra một phần tử có mặt trong danh sách Prolog kiểm tra một phần tử có mặt trong một danh sách như sau : member(X, L) trong đó, X là một phần tử và L là một danh sách. Đích member(X, L) được thoả mãn nếu X xuất hiện trong L. Ví dụ : ?- member( b, [ a, b, c ] ) Yes ?- member( b, [ a, [ b, c ] ] ) No ?- member( [ b, c], [ a, [ b, c ] ] ) LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 186 Yes Từ các kết quả trên, ta có thể giải thích quan hệ member(X, L) như sau : Phần tử X thuộc danh sách L nếu : 1. X là đầu của L, hoặc nếu 2. X là một phần tử của đuôi của L. Ta có thể viết hai điều kiện trên thành hai mệnh đề, mệnh đề thứ nhất là một sự kiện đơn giản, mệnh đề thứ hai là một luật : member( X, [ X | Tail ] ). member( X, [ Head | Tail ] ) :- member( X, Tail ). hoặc : member(X, [X|T]). member(X, [_|T]) :- member(X, T). X.1.2. Ghép hai danh sách Để ghép hai danh sách, Prolog có hàm : append( L1, L2, L3). trong đó, L1 và L2 là hai danh sách, L3 là danh sách kết quả của phép ghép L1 và L2. Ví dụ : ?- append( [ a, b ], [ c, d ], [ a, b, c, d ] ). Yes ?- append( [ a, b ], [ c, d ], [ a, b, a, c ] ). No Hình X.1. Ghép hai danh sách [ X | L1 ] và L2 thành [ X | L3 ]. Hàm append hoạt động phụ thuộc tham đối đầu tiên L1 theo cách như sau : 1. Nếu tham đối đầu tiên là danh sách rỗng, thì tham đối thứ hai và thứ ba phải là một danh sách duy nhất, gọi là L. Ta viết trong Prolog như sau : append( [ ], L, L). 2. Nếu tham đối đầu tiên của append là danh sách khác rỗng, thì nó gồm một đầu và một đuôi như sau [ X | L1 ] Kết quả phép ghép danh sách là danh sách [ X | L3 ], với L3 là phép ghép của L1 và L2. Ta viết trong Prolog như sau : append( [ X | L1 ], L2, [ X | L3 ] ) :- append( L1, L2, L3 ). Hình 4.2 minh hoạ phép ghép hai danh sách [ X | L1 ] và L2. X L3 X L1 L2 [ X | L1 ] L3 [ X | L3 ] LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 187 Ta có các ví dụ sau : ?- append( [ a, b, c ], [ 1, 2, 3 ], L ). L = [ a, b, c, 1, 2, 3 ] ?- append( [ a, [ b, c ], d ], [ a, [ ], b ], L ] ). L = [ a, [ b, c ], d, a, [ ], b ] Thủ tục append được sử dụng rất mềm dẻo theo nhiều cách khác nhau. Chẳng hạn Prolog đưa ra bốn phương án để phân tách một danh sách đã cho thành hai danh sách mới như sau : ?- append( 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 = [ ]; Yes Sử dụng append, ta cũng có thể tìm kiếm một số phần tử trong một danh sách. Chẳng hạn, từ danh sách các tháng trong năm, ta có thể tìm những tháng đứng trước một tháng đã cho, giả sử tháng năm (May) : ?- append( Before, [ May | After ] , [ jan, fev, mar, avr, may, jun, jul, aut, sep, oct, nov, dec ] ). Before = [ jan, fev, mar, avr ] After = [ jun, jul, aut, sep, oct, nov, dec ] Yes Tháng đứng ngay trước và tháng đứng ngay sau tháng năm nhận được như sau : ?- append( _, [ Month1, may, Month2 | _ ] , [ jan, fev, mar, avr, may, jun, jul, aut, sep, oct, nov, dec ] ). Month1 = avr Month2 = jun Yes Bây giờ cho trước danh sách : L1 = [ a, b, z, z, c, z, z, z, d, e ] Ta cần xóa các phần tử đứng sau ba chữ z liên tiếp, kể cả ba chữ z : ?- L1 = [ a, b, z, z, c, z, z, z, d, e ], append( L2, [ z, z, z | _ ], L1 ). L1 = [ a, b, z, z, c, z, z, z, d, e ] L2 = [ a, b, z, z, c ] LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 188 Hình X.2. Thủ tục member1 tìm tuần tự một đối tượng trong danh sách đã cho. Trước đây ta đã định nghĩa quan hệ member( X, L ) để kiểm tra một phần tử X có mặt trong một danh sách L không. Bây giờ bằng cách sử dụng append, ta có thể định nghĩa lại member như sau : member1( X, L ) :- append( L1, [ X | L2], L). Mệnh đề này có nghĩa : nếu X có mặt trong danh sách L thì L có thể được phân tách thành hai danh sách, với X là đầu của danh sách thứ hai. Định nghĩa member1 hoàn toàn tương đương với định nghĩa member. Ở đây ta sử dụng hai tên khác nhau để phân biệt hai cách cài đặt Prolog. Ta cũng có thể định nghĩa lại member1 bằng cách sử dụng biến nặc danh (anonymous variable) : member1( X, L ) :- append( _ , [ X | _ ], L). So sánh hai cách cài đặt khác nhau về quan hệ thành viên, ta nhận thấy nghĩa thủ tục trong định nghĩa member được thể hiện rất rõ : Trong member, để kiểm tra phần tử X có mặt trong một danh sách L không, 1. Trước tiên kiểm tra phần tử đầu của L là đồng nhất với X, nếu không, 2. Kiểm tra rằng X có mặt trong phần đuôi của L. Nhưng trong trường hợp định nghĩa member1, ta thấy hoàn toàn nghĩa khai báo mà không có nghĩa thủ tục. Để hiểu được cách member1hoạt động như thế nào, ta hãy xem xét quá trình Prolog thực hiện câu hỏi : ?- member1( b, [ a, b, c ] ). member1( b, [ a, b, c ] ) Mệnh đề 2 của append So khớp : L1 = [ X | L1’ ] [ b | L2 ] = L2’ [ a, b, c ] = [ X | L3’ ] Từ đó kéo theo : X = a, L3’ = [ b, c ] Mệnh đề 1 của append So khớp : L1’ = [ ] [ b | L2 ] = [ b, c ] Từ đó kéo theo : L2 = [ c ] thành công Mệnh đề 1 của append So khớp : L1 = [ ] [ b | L2 ] = [ a, b, c ] Thất bại vì b ≠ a append( L1, [ b | L2 ], [ a, b, c ] append( L1’, [ b | L2 ], [ b, c ] ) LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 189 Cách tìm của thủ tục member1 trên đây tương tự member, bằng cách duyệt từng phần tử, cho đến khi tìm thấy đối tượng cần tìm, hoặc danh sách đã cạn. X.1.3. Bổ sung một phần tử vào danh sách Phương pháp đơn giản nhất để bổ sung một phần tử vào danh sách là đặt nó ở vị trí đầu tiên, để nó trở thành đầu. Nếu X là một đối tượng mới, còn L là danh sách cần bổ sung thêm, thì danh sách kết quả sẽ là : [ X | L ] Người ta không cần viết thủ tục để bổ sung một phần tử vào danh sách. Bởi vì việc bổ sung có thể được biểu diễn dưới dạng một sự kiện nếu cần : insert( X, L, [ X | L ] ). X.1.4. Loại bỏ một phần tử khỏi danh sách Để loại bỏ một phần tử X khỏi danh sách L, người ta xây dựng quan hệ : remove( X, L, L1 ) trong đó, L1 đồng nhất với L, sau khi X bị loại bỏ khỏi L. Thủ tục remove có cấu trúc tương tự member. Ta có thể lập luận như sau 1. Nếu phần tử X là đầu của danh sách, thì kết quả là đuôi của danh sách. 2. Nếu không, tìm cách loại bỏ X khỏi phần đuôi của danh sách. remove( X, [ X | Tail ], Tail ). remove( X, [ Y | Tail ], [ Y | Tail1 ] ) :- remove( X, Tail, Tail1 ). Tương tự thủ tục member, thủ tục remove mang tính không xác định. Nếu có nhiều phần tử là X có mặt trong danh sách, thì remove có thể xoá bất kỳ phần tử nào, do quá trình quay lui. Tuy nhiên, mỗi lần thực hiện, remove chỉ xoá một phần tử là X mà không đụng đến những phần tử khác. Ví dụ : ?- remove( a, [ a, b, a, a ], L ). L = [ b, a, a ]; L = [ a, b, a ]; L = [ a, b, a ] No Thủ tục remove thất bại nếu danh sách không chứa phần tử cần xoá. Người ta có thể sử dụng remove trong một khía cạnh khác, mục đích để bổ sung một phần tử mới vào bất cứ đâu trong danh sách. Ví dụ, nếu ta muốn đặt phần tử a vào tại mọi vị trí bất kỳ trong danh sách [ 1, 2, 3 ], chỉ cần đặt câu hỏi : Cho biết danh sách L nếu sau khi xoá a, ta nhận được danh sách [ 1, 2, 3 ] ? ?- remove( a, L, [ 1, 2, 3 ] ). L = [ a, 1, 2, 3 ]; L = [ 1, a, 2, 3 ]; L = [ 1, 2, a, 3 ]; L = [ 1, 2, 3, a ] No LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 190 Một cách tổng quát, phép toán chèn insert một phần tử X vào một danh sách List được định nghĩa bởi thủ tục remove bằng cách sử dụng một danh sách lớn hơn LargerList làm tham đối thứ hai : insert( X, List, LargerList ) :- remove( X, LargerList, List ). Ta đã định nghĩa quan hệ thuộc về trong thủ tục member1 bằng cách sử dụng thủ tục append. Tuy nhiên, ta cũng có thể định nghĩa lại quan hệ thuộc về trong thủ tục mới member2 bởi thủ tục remove bằng cách xem một phần tử X thuộc về một danh sách List nếu X bị xoá khỏi List : member2( X, List ) :- remove( X, List, _ ). X.1.5. Nghịch đảo danh sách Sử dụng append, ta có thể viết thủ tục nghịch đảo một danh sách như sau : reverse ( [ ], [ ] ). reverse ( [ X | Tail ], R ) :- reverse (Tail, R1 ), append(R1, [X], R). ?- reverse( [ a, b, c , d, e, f ] , L). L = [f, e, d, c, b, a] Yes Sau đây là một thủ tục khác để nghịch đảo một danh sách nhưng có sử dụng hàm bổ trợ trong thân thủ tục : revert(List, RevList) :- rev(List, [ ], RevList). rev([ ], R, R). rev([H|T], S, R) :- rev(T, [H|S], R). ?- revert( [ a, b, c , d, e, f ] , R). R = [f, e, d, c, b, a] Yes Sử dụng reverse, ta có thể kiểm tra một danh sách có là đối xứng (palindrome) hay không : palindrome(L) :- reverse( L, L ). ?- palindrome([ a, b, c , d, c, b, a ]). Yes X.1.6. Danh sách con Ta xây dựng thủ tục sublist nhận hai tham đối là hai danh sách L và S sao cho S là danh sách con của L như sau : ?- sublist( [ c, d, e ], [ a, b, c , d, e, f ] ) Yes ?- sublist( [ c, e ], [ a, b, c , d, e, f ] ) LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 191 No Nguyên lý để xây dựng thủ tục sublist tương tự thủ tục member1, mặc dù ở đây quan hệ danh sách con tổng quát hơn. Hình X.3. Các quan hệ member và sublist. Quan hệ danh sách con được mô tả như sau : S là một danh sách con của L nếu : 1. Danh sách L có thể được phân tách thành hai danh sách L1 và L2, và nếu 2. Danh sách L2 có thể được phân tách thành hai danh sách S và L3. Như đã thấy, việc phân tách các danh sách có thể được mô tả bởi quan hệ ghép append. Do đó ta viết lại trong Prolog như sau : sublist( S, L ) :- append( L1, L2, L ), append( S, L3, L2 ). Ta thấy thủ tục sublist rất mềm dẻo và do vậy có thể sử dụng theo nhiều cách khác nhau. Chẳng hạn ta có thể liệt kê mọi danh sách con của một danh sách đã cho như sau : ?- sublist( S, [ a, b, c ] ). S = [ ]; S = [ a ]; S = [ a, b ]; S = [ a, b, c ]; S = [ b ]; ... X.1.7. Hoán vị Đôi khi, ta cần tạo ra các hoán vị của một danh sách. Ta xây dựng quan hệ permutation có hai tham biến là hai danh sách, mà một danh sách là hoán vị của danh sách kia. Ta sẽ tận dụng phép quay lui như sau : ?- permutation( [ a, b, c ], P ). P = [ a, b, c ]; P = [ a, c, b ]; P = [ b, a, c ]; ... Nguyên lý hoạt động của thủ tục swap dựa trên hai trường hợp phân biệt, tuỳ theo danh sách thứ nhất : 1. Nếu danh sách thứ nhất rỗng, thì danh sách thứ hai cũng phải rỗng. 2. Nếu danh sách thứ nhất khác rỗng, thì nó sẽ có dạng [ X | L ] và được tiến hành hoán vị như sau : trước tiên hoán vị L để nhận được L1, sau đó chèn X vào tất cả các vị trí trong L1. L X L2L1 [ X | L2 ] L L2 L1 S L3 member( X, L ) sublist( S, L ) LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 192 Hình X.4. Một cách xây dựng hoán vị permutation của danh sách [ X | L ]. Ta nhận được hai mệnh đề tương ứng với thủ tục như sau : permutation( [ ], [ ] ). permutation( [ X | L ], P ) :- permutation( L, L1 ), insert( X, L1, P ). Một phương pháp khác là loại bỏ phần tử X khỏi danh sách đầu tiên, hoán vị phần còn lại của danh sách này để nhận được danh sách P, sau đó thêm X vào phần đầu của P. Ta có chương trình khác permutation2 như sau : permutation2( [ ], [ ] ). permutation2( L, [ X | P ] ) :- remove( X, L, L1 ), permutation2( L1, P ). Từ đây, ta có thể khai thác thủ tục hoán vị, chẳng hạn (chú ý khi chạy Arity Prolog cần gõ vào một dấu chấm phẩy ; sau ->) : ?- permutation( [ red, blue, green ], P ). P = [ red, blue, green ]; P = [ red, green, blue ]; P = [ blue, red, green ]; P = [ blue, green, red ]; P = [ green, red, blue ]; P = [ green, blue, red ]; Yes Hoặc nếu sử dụng permutation theo cách khác như sau : ?- permutation( L, [ a, b, c ] ). Prolog sẽ ràng buộc liên tiếp cho L để đưa ra 6 hoán vị khác nhau có thể. Tuy nhiên, nếu NSD yêu cầu một giải pháp khác, Prolog sẽ không bao giờ trả lời “No”, mà rơi vào một vòng lặp vô hạn do phải tìm kiếm một hoán vị mới mà thực ra không tồn tại. Trong trường hợp này, thủ tục permutation2 chỉ tìm thấy một hoán vị thứ nhất, sau đó ngay lập tức rơi vào một vòng lặp vô hạn. Vì vậy, cần chú ý khi sử dụng các quan hệ hoán vị này. X.2. Một số ví dụ về danh sách X.2.1. Sắp xếp các phần tử của danh sách Xây dựng thủ tục sắp xếp các phần tử có của một danh sách bằng phương pháp chèn như sau : ins(X, [ ], [ X ]). ins(X, [H|T], [ X,H|T ]) :- X @=< H. ins(X, [ H|T ], [ H|L ]) :- L1 là một hoán vị của L Chèn X tại một vị trí để nhận được một hoán vị của [ X | L ] X L hoán vị L L1 LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 193 X @> H, ins( X, T, L ). ?- ins(8, [ 1, 2, 3, 4, 5 ], L). L = [1, 2, 3, 4, 5, 8] Yes ?- ins(1, L, [ 1, 2, 3, 4, 5 ]). L = [2, 3, 4, 5] Yes ins_sort([ ], [ ]). ins_sort([H|T], L) :- ins_sort(T, L1), ins(H, L1, L). ?- ins_sort([3, 2, 6, 4, 7, 1], L). L = [1, 2, 3, 4, 6, 7] Yes X.2.2. Tính độ dài của một danh sách Xây dựng thủ tục tính độ dài hay đếm số lượng các phần tử có mặt trong một danh sách đã cho như sau : length( L, N ). Xảy ra hai trường hợp : 1. Nếu danh sách rỗng, thì độ dài N = 0. 2. Nếu danh sách khác rỗng, thì nó được tạo thành từ danh sách có dạng : [ head | queue ] và có độ dài bằng 1 cộng với độ dài của queue. Ta có chương trình Prolog như sau : length( [ ], 0 ). length( [ _ | Queue ], N ) :- length(Queue, N1 ), N is 1 + N1. Kết quả chạy Prolog như sau : ?- length( [ a, b, c, d, e ], N ). N = 5 Yes ?- length( [ a, [ b, c ], d, e ], N ). N = 4 Yes Ta thấy rằng trong mệnh đề thứ hai, hai đích của phần thân là không thể hoán đổi cho nhau, vì rằng N1 phải được ràng buộc trước khi thực hiện đích : N is 1 + N1 Chẳng hạn, nếu gọi trace, quá trình thực hiện length( [ 1, 2, 3 ], N ) như sau : (0) gọi length([1, 2, 3], N) -> (1) gọi length([2, 3], N’) -> (2) gọi length([3], N’’) -> (3) gọi length([ ], N’’’) -> N’’’ = 0 LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 194 (4) gọi N’’ is 1 + 0 -> N’’ = 1 (5) gọi N’ is 1 + 1 -> N’ = 2 (6) gọi N is 1 + 2 -> N = 3 Với is, ta đã đưa vào một quan hệ nhạy cảm với thứ tự thực hiện các đích, và do vậy không thể bỏ qua yếu tố thủ tục trong chương trình. Điều gì sẽ xảy ra nếu ta không sử dụng is trong chương trình. Chẳng hạn : length1( [ ], 0 ). length1( [ _ | Queue ], N ) :- length1( Queue, N1 ), N = 1 + N1. Lúc này, nếu gọi : ?- length1( [ a, [ b, c ], d, e ], N ). Prolog trả lời : N = 1 + (1 + (1 + (1 + 0))) Yes Phép cộng do không được khởi động một cách tường minh nên sẽ không bao giờ được thực hiện. Tuy nhiên, ta có thể hoán đổi hai đích của mệnh đề thứ hai trong length1 : length1( [ ], 0 ). length1( [ _ | Queue ], N ) :- N = 1 + N1, length1( Queue, N1 ). Kết quả chạy chương trình sau khi hoán đổi vẫn y hệt như cũ. Bây giờ, ta lại có thể rút gọn mệnh đề về chỉ còn một đích : length1( [ ], 0 ). length2( [ _ | Queue ], 1 + N ) :- length2( Queue, N ). Kết quả chạy chương trình lần này vẫn y hệt như cũ. Prolog không đưa ra trả lời như mong muốn, mà là : ?- length1([ a, b, c, d], N). N = 1+ (1+ (1+ (1+0))) Yes X.2.3. Tạo sinh các số tự nhiên Chương trình sau đây tạo sinh và liệt kê các số tự nhiên : % Natural Numbers nat(0). nat(N) :- nat(M), N is M + 1. Khi thực hiện các đích con trong câu hỏi : ?- nat(N), write(N), nl, fail. các số tự nhiên được tạo sinh liên tiếp nhờ kỹ thuật quay lui. Sau khi số tự nhiên đầu tiên nat(N) được in ra nhờ write(N), hằng fail bắt buộc thực hiện quay lui. Khi đó, luật thứ hai được vận dụng để tạo sinh số tự nhiên tiếp theo và cứ thế tiếp tục cho đến khi NSD quyết định dừng chương trình (^C). LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 195 Bài tập chương 3 1. Tìm các đối tượng Prolog đúng đắn về mặt cú pháp trong số đối tượng được cho dưới đây. Cho biết kiểu của chúng (là nguyên tử, số, biến hay cấu trúc) ? a) Diane b) diane c) ‘Diane’ d) _diane e) ‘Diane va en vacances’ f) va( diane, vacances ) g) 45 h) 5(X , Y) i) +( nord , owest ) j) three( small( cats ) ) 2. Hãy tìm một biểu diễn dạng đối tượng cấu trúc cho các hình chữ nhật, hình vuông và hình tròn. Xem hình 2.4 để có cách giải quyết. Sử dụng các biễu diễn cho các hình cụ thể để minh họa. 3. Chương trình sau nói rằng hai người là có quan hệ dòng họ với nhau nếu : a) một là tổ tiên của người kia, hoặc, b) hai người có chung tổ tiên, hoặc, c) hai người có cùng con cháu. kindred( X, Y) :- ancestor(X , Y). kindred(X , Y) :- ancestor(X , Y). kindred(X , Y) :- % X và Y có cùng tổ tiên ancestor( Z, X), ancestor(Z , Y). kindred(X , Y) :- % X và Y có cùng con cháu ancestor (X , Z), ancestor(Y , Z). Hãy cho biết có thể làm ngắn chương trình trên bằng cách sử dụng dấu chấm phẩy ; được không ? 4. Hãy tìm hiểu một định nghĩa mới về quan hệ ancestor : ancestor(X Z) :- parent(X Z) . ancestor(X Z) :- parent(Y , Z), ancestor( X, Y). Định nghĩa này có đúng hay không ? Có thể thay đổi lại sơ đồ đã cho trong hình 1.7 để tương ứng với định nghĩa mới này ? 5. Ngoài các định nghĩa quan hệ gia đình đã có trong phần lý thuyết và bài tập, hãy định nghĩa các quan hệ khác theo tập quán Việt Nam (cô, dì, chú, bác...) ? LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 196 6. Hãy định nghĩa các quan hệ trong thế giới sinh vật (động vật, thực vật) ? 7. Cho biết các hạng Prolog hợp thức sau đây (valid Prolog terms) : 23 +(fred, jim) foo(X, bar(+(3, 4))) 1+2. Foo(x) Alison Cawsey 8. Cho quan hệ parent được định nghĩa trong phần lý thuyết cho biết kết quả của các câu hỏi sau : a) ?- parent(jim , X). b) ?- parent( X , jim). c) ?- parent(mary , X) , parent( X , part). d) ?- parent(mary , X) , parent( X , y ) , parent(y , jim). 9. Viết các mệnh đề Prolog diễn tả các câu hỏi liên quan đến quan hệ parent : a) Ai là cha mẹ của Sue ? b) Liz có con không ? c) Ai là ông bà (grandparent) của Sue ? 10. Viết trong Prolog các mệnh đề sau : a) Ai có một đứa trẻ người đó là hạnh phúc. Hướng dẫn : Xây dựng quan hệ một ngôi happy. b) Với mọi X, nếu X có một con mà người con này có một chị em gái, thì X có hai con (xây dựng quan hệ have_two_children). 11. Định nghĩa quan hệ grandchild bằng cách sử dụng quan hệ parent. Hướng dẫn : tìm hiểu quan hệ grandparent. 12. Định nghĩa quan hệ aunt( X, Y ) bằng cách sử dụng quan hệ parent. Để thuận tiện, có thể vẽ sơ đồ minh họa. 13. Các phép so khớp dưới đây có đúng không ? Nếu đúng, cho biết các ràng buộc biến tương ứng ? a) point( A , B ) = point( 1 , 2 ) b) point( A , B ) = point( X , Y, Z ) c) addition( 2 , 2 ) = 4 d) +( 2 , D ) = +( E , 2 ) e) triangle( point( -1 , 0 ) , P2, P3 ) = triangle( P1, point( 1, 0 ), point( 0, Y ) ) Các ràng buộc ở đây đã định nghĩa một lớp các tam giác. Làm cách nào để mô tả lớp này ? 14. Sử dụng mô tả các đường thẳng đã cho trong bài học, tìm một hạng biễu diễn mọi đường thẳng đứng X = 5. 15. Cho hình chữ nhật được biễu diễn bởi hạng: rectangle(P1, P2, P3, P4). Với Pi là các đỉnh của hình chữ nhật theo chiều dương, hãy định nghĩa quan hệ : regular( R ) là đúng nếu R là một hình chữ nhật có các cạnh thẳng đứng và nằm ngang (song song với các trục tọa độ). 16. Cho biết kết quả của các câu hỏi sau đây : ?- X=Y. ?- X is Y ?- X=Y, Y=Z, Z=1. ?- X=1, Z=Y, X=Y. LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 197 ?- X is 1+1, Y is X. ?- Y is X, X is 1+1. ?- 1+2 == 1+2. ?- X == Y. ?- X == X. ?- 1 =:= 2-1 ?- X =:= Y. 17. Cho biết kết quả của các câu hỏi sau đây : ?- op(X) is op(1). ?- op(X) = op(1). ?- op(op(Z), Y) = op(X, op(1)). ?- op(X, Y) = op(op(Y), op(X)). 18. Từ các định nghĩa số tự nhiên (nat) và phép cộng (addi) cho trong ví dụ 1 ở mục định nghĩa hàm, hãy viết tiếp các hàm trừ (subt), nhân (multi), chia (divi), luỹ thừa (power), giai thừa (fact), so sánh nhỏ hơn (less) và tìm ước số chung lớn nhất (pdg) sử dụng các hàm đã có (chẳng hạn less, subt...). 19. Viết hàm Prolog để kiểm tra một số nguyên tuỳ ý N : a. N là số chẵn (even number) sử dụng đệ quy trực tiếp Hướng dẫn : N chẵn thì N±2 cũng là số chẵn b. N là số lẻ (odd number) sử dụng đệ quy trực tiếp Hướng dẫn : N lẻ thì N±2 cũng là số lẻ c. N chẵn sử dụng hàm kiểm tra số lẻ câu d (N chẵn thì N±1 là số lẻ) d. N là số lẻ sử dụng hàm kiểm tra số chẵn câu c (N lẻ thì N±1 chẵn). 20. Viết hàm Prolog để làm duyệt (tracking/traverse) trên cây nhị phân theo các thứ tự trước (reorder), sau (post-order) và giữa (in-order). Giả sử cây nhị phân tương ứng với biểu thức số học (5+6)*(3-(2/2)) là các mệnh đề Prolog như sau : tree(’*’, tree(’+’, leaf(5), leaf(6)), tree(’-’, leaf(3), tree(’/’, leaf(2), leaf(2))) Kết quả duyệt cây như sau : theo thứ tự trước : [*, +, 5, 6, -, 3, /, 2, 2] thứ tự giữa : [5, +, 6, *, 3, -, 2, /, 2] thứ tự sau : [5, 6, +, 3, 2, 2, /, -, *] 21. Viết lại hàm tạo 10 số tự nhiên chẵn đầu tiên (đã cho trong phần đệ quy) sao cho kết quả trả về là dãy số tăng dần. 22. Lập bảng nhân table(R, N) có số bị nhân (multiplicator) từ 1 trở đi với số nhân N (multiplier) và dừng lại khi gặp số bị nhân R (kết quả R * N). 23. Viết các hàm tính gần đúng giá trị các hàm sau với độ chính xác e = 10-5 : π 4 1 1 3 1 5 1 7 = − + − +... cho đến khi 1 2n -1 ε< LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 198 2 4 6x 2 x 2 4 x1 + + + + ... 2 3 4 3 5 6 × × × cho đến khi phần tử thứ n < e S = 1 - x + x 2! - x 3! + ... + (-1) x n! + ... 2 3 n n cho đến khi nx n! ε< S x x x x n n = + + + + + +1 2 4 6 2 2 4 6 2 ! ! ! ... ( )! ... cho đến khi x n n2 5 2 10 ( )! < − y = x + x + ... + x có n > 1 dấu căn 24. Trình Prolog dưới đây là một trình diễn dịch (interpreter) cho một ngôn ngữ lập trình đơn giản chỉ gồm các số nguyên int(N), các biến id(X), các hàm fn(X,E), và gọi hàm app(E1,E2) : %% subst(E1, E2, X, V) %% thực hiện phép thế biến X bởi biến V trong E1 để trả về E2. subst(int(N), int(N), _, _). subst(id(X), V, X, V). subst(id(Y), id(Y), X, _) :- X \= Y. subst(fn(X, E), fn(X, E), X, _). subst(fn(Y, Ea), fn(Y, Eb), X, V) :- X \= Y, subst(Ea, Eb, X, V). subst(app(E1a, E2a), app(E1b, E2b), X, V) :- subst(E1a, E1b, X, V), subst(E2a, E2b, X, V). %% reduce(E, V) %% thực hiện phép tính giá trị của E để trả về V. reduce(int(N), int(N)). reduce(fn(X, B), fn(X, B)) reduce(app(E1, E2), V) :- reduce(E1, fn(X, B)), reduce(E2, V2), subst(B, E, X, V2), reduce(E, V). Câu hỏi : a. Cho biết cách trao đổi tham biến hợp lệ trong ngôn ngữ mô tả trên đây ? Cách trao đổi tham biến nào thì không thể thực hiện được ? b. Tìm cách thay đổi trình Prolog trên đây để có thể thực hiện được các phương pháp trao đổi tham biến khác nhau. c. Cho biết tầm vực (scope) của các biến là tĩnh hay động ? 25. Cho ví dụ một đồ thị không định hướng dưới đây : arc(a,b). arc(d,f). arc(b,c). arc(f,a). arc(c,d). arc(a,b). arc(c,e). arc(h,i). LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 199 arc(c,g). arc(i,j). arc(g,f). Hãy viết hàm tìm đường đi giữa hai đỉnh của đồ thị. 26. Viết một thủ tục sử dụng append để xóa ba phần tử cuối cùng của danh sách L, tạo ra danh sách L1. Hướng dẫn : L là phép ghép của L1 với một danh sách của ba phần tử (đã bị xóa khỏi L). 27. Viết một dãy các đích để xóa ba phần tử đầu tiên và ba phần tử cuối cùng của một danh sách L, để trả về danh sách L2. 28. Định nghĩa quan hệ : last_element( Object, List ) sao cho Object phải là phần tử cuối cùng của danh sách List. Hãy viết thành hai mệnh đề, trong đó có một mệnh đề sử dụng append, mệnh đề kia không sử dụng append. 29. Định nghĩa hai vị từ : even_length( List ) và odd_length( List ) được thõa mãn khi số các phân tử của danh sách List là chẵn hay lẻ tương ứng. Ví dụ danh sách : [ a, b, c, d ] có độ dài chẵn, [ a, b, c ] có độ dài lẽ. 30. Cho biết kết quả Prolog trả lời các câu hỏi sau : ?- [1,2,3] = [1|X]. ?- [1,2,3] = [1,2|X]. ?- [1 | [2,3]] = [1,2,X]. ?- [1 | [2,3,4]] = [1,2,X]. ?- [1 | [2,3,4]] = [1,2|X]. ?- b(o,n,j,o,u,r) =.. L. ?- bon(Y) =.. [X,jour]. ?- X(Y) =.. [bon,jour]. 31. Viết chương trình Prolog kiểm tra một danh sách có phải là một tập hợp con của một danh sách khác không ? Chương trình hoạt động như sau : ?- subset2([4,3],[2,3,5,4]). Yes 32. Viết chương trình Prolog để lấy ra các phần tử từ một danh sách. Chương trình cũng có thể chèn các phần tử vào một danh sách hoạt động như sau : ?- takeout(3,[1,2,3],[1,2]). Yes ?- takeout(X,[1,2,3],L). X = 1 L = [2, 3] ; X = 2 L = [1, 3] ; X = 3 L = [1, 2] ; No ?- takeout(4,L,[1,2,3]). 4 LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 200 L = [4, 1, 2, 3] ; L = [1, 4, 2, 3] ; L = [1, 2, 4, 3] ; L = [1, 2, 3, 4] ; No 33. Viết vị từ Prolog getEltFromList(L,N,E) cho phép lấy ra phần tử thứ N trong một danh sách. Thất bại nếu danh sách không có đủ N phần tử. Chương trình hoạt động như sau : ?- getEltFromList([a,b,c],0,X). No ?- getEltFromList([a,b,c],2,X). X = b ?- getEltFromList([a,b,c],4,X). No 34. Viết chương trình Prolog tìm phần tử lớn nhất và phần tử nhỏ nhất trong một danh sách các số. Chương trình hoạt động như sau : ?- maxmin([3,1,5,2,7,3],Max,Min). Max = 7 Min = 1 Yes ?- maxmin([2],Max,Min). Max = 2 Min = 2 Yes 35. Viết chương trình Prolog chuyển một danh sách phức hợp, là danh sách mà mỗi phần tử có thể là một danh sách con chứa các danh sách con phức hợp khác, thành một danh sách phẳng là danh sách chỉ chứa các phần tử trong tất cả các danh sách con có thể, giữ nguyên thứ tự lúc đầu. Chương trình hoạt động như sau : flatten([[1,2,3],[4,5,6]], Flatlist). Flatlist = [1,2,3,4,5,6] Yes flatten([[1,[hallo,[[aloha]]],2,[],3],[4,[],5,6]], Flatlist) Flatlist = [1, hallo, aloha, 2, 3, 4, 5, 6] Yes 36. Sử dụng vị từ forall để viết chương trình Prolog kiểm tra hai danh sách có rời nhau (disjoint) không ? Chương trình hoạt động như sau : ?- disjoint([a,b,c],[d,g,f,h]). Yes ?- disjoint([a,b,c],[f,a]). No 37. Vị từ forall(Cond, Action) thực hiện kiểm tra sự so khớp tương ứng giữa Cond, thường kết hợp với vị từ member, và Action. Ví dụ dưới đây kiểm tra việc thực hiện các phép toán số học trong danh sách L là đúng đắn. ?- forall(member(Result = Formula, [2 = 1 + 1, 4 = 2 * 2]), Result =:= Formula). LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 201 Result = _G615 Formula = _G616 Yes 38. Sử dụng vị từ forall để viết chương trình Prolog kiểm tra một danh sách có là một tập hợp con của một danh sách khác hay không ? Chương trình hoạt động như sau : ?- subset3([a,b,c],[c,d,a,b,f]). Yes ?- subset3([a,b,q,c],[d,a,c,b,f]) No 39. Sử dụng vị từ append ghép hai danh sách để viết các chương trình Prolog thực hiện các việc sau : prefixe(L1, L2) danh sách L1 đứng trước (prefixe list) danh sách L2. suffixe(L1, L2) danh sách L1 đứng sau (suffixe list) danh sách L2. isin(L1, L2) các phần tử của danh sách L1 có mặt trong danh sách L2. 40. Sử dụng phương pháp Quicksort viết chương trình Prolog sắp xếp nhanh một danh sách các số đã cho theo thứ tự tăng dần. 41. Đọc hiểu chương trình sau đây rồi dựng lại thuật toán : /* Missionarys & Cannibals */ /* Tránh vòng lặp */ lNotExist(_,[]). lNotExist(X,[T|Q]) :- X\==T, lNotExist(X,Q). /* Kiểm tra tính hợp lý của trạng thái */ valid(MG,CG,MD,CD) :- MG>=0, CG>=0, MD>=0, CD>=0, MG=0, MD>=CD. valid(MG,CG,MD,CD) :- MG>=0, CG>=0, MD>=0, CD>=0, MG>=CG, MD=0. valid(MG,CG,MD,CD) :- MG>=0, CG>=0, MD>=0, CD>=0, MG>=CG, MD>=CD. /* Xây dựng cung và kiểm tra */ sail(1,0). sail(0,1). sail(1,1). sail(2,0). sail(0,2). arc([left,MGi,CGi,MDi,CDi],[droite,MGf,CGf,MDf,CDf]) :- sail(Mis,Can), MGf is MGi-Mis, MDf is MDi+Mis, CGf is CGi-Can, CDf is CDi+Can, valid(MGf,CGf,MDf,CDf). arc([right,MGi,CGi,MDi,CDi],[left,MGf,CGf,MDf,CDf]) :- sail(Mis,Can), MGf is MGi+Mis, MDf is MDi-Mis, CGf is CGi+Can, CDf is CDi-Can, valid(MGf,CGf,MDf,CDf). /* Phép đệ quy */ cross(A,A,[A],Non). cross(X,Y,Ch,Non) :- arc(X,A), lNotExist(A,Non), cross(A,Y,ChAY,[A|Non]), Ch=[X|ChAY]. /* Đi qua */ traverse(X,Y,Ch) :- cross(X,Y,Ch,[X]).