Prolog là một ngôn ngữ lập trình. Tên gọi Prolog được xuất phát từ cụm từ tiếng Pháp Programmation en logique, nghĩa là lập trình theo lô gích. Xuất hiện từ năm 1972 (do Alain Colmerauer và Robert Kowalski thiết kế), mục tiêu của Prolog là giúp người dùng mô tả lại bài toán trên ngôn ngữ của logic, dựa trên đó, máy tính sẽ tiến hành suy diễn tự động dựa vào những cơ chế suy diễn có sẵn (hợp nhất, quay lui và tìm kiếm theo chiều sâu) để tìm câu trả lời cho người dùng....
PGS.TS PHAN HUY KHÁNH Lập t rình Lơ g ích Prolog NHÀ XUẤT BẢN ĐẠI HỌC QUỐC GIA HÀ NỘI 2004 PGS.TS PHAN HUY KHÁNH L ậ p tr ìn h L ơg í ch t r ong Pr ol og Prolog ngơn ngữ lập trình lơgich (Prolog = PROgramming in LOGic) GS A Colmerauer đưa lần năm 1972 trường Đại học Marseille, nước Pháp Đến năm 1980, Prolog nhanh chóng áp dụng rộng rãi, người Nhật chọn làm ngôn ngữ phát triển máy tính hệ Prolog cài đặt hầu hết dịng máy tính Unix/Linux, Macintosh, Windows Prolog cịn gọi ngơn ngữ lập trình ký hiệu (symbolic programming) tương tự lập trình hàm (functional programming), hay lập trình phi số (non-numerical programming) Nguyên lý lập trình lơgich dựa phép suy diễn lơgích, liên quan đến khái niệm toán học phép hợp Herbrand, hợp giải Robinson, lôgich Horn, lôgich vị từ bậc (first order predicate logic), v.v Prolog thích hợp để giải tốn liên quan đến đối tượng mối quan hệ chúng Prolog ứng dụng chủ yếu lĩnh vực trí tuệ nhân tạo (Artificial Intelligence) cơng nghệ xử lý tri thức, hệ chuyên gia, máy học, xử lý ngơn ngữ, trị chơi, v.v Nội dung sách tập trung trình bày sở lý thuyết kỹ thuật lập trình Prolog, thích hợp cho sinh viên ngành tin học bạn đọc muốn tìm hiểu kỹ thuật lập trình ứng dụng lĩnh vực trí tuệ nhân tạo VỀ TÁC GIẢ : Tốt nghiệp ngành Tốn Máy tính năm 1979 trường Đại học Bách khoa Hà Nội Từ 1979 đến giảng dạy khoa Công nghệ Thông tin, trường Đại học Bách khoa, Đại học Đà Nẵng Bảo vệ tiến sĩ năm 1991 Pháp Giữ chức chủ nhiệm khoa Công nghệ Thông tin 1995-2000 Hướng nghiên cứu : xử lý ngơn ngữ, xử lý đa ngữ, lý thuyết tính tốn E-mail: khanhph@vnn.vn LỜI NĨI ĐẦU Cuốn sách nhằm cung cấp sở lý thuyết phương pháp lập trình mơn học «Lập trình lơgich» (Programming in Logic) Người đọc làm quen với số kỹ thuật lập trình lơgich ứng dụng tương đối phổ biến chủ yếu lĩnh vực trí tuệ nhân tạo (Artificial Intelligence) công nghệ xử lý tri thức, máy học, hệ chuyên gia, xử lý ngôn ngữ tự nhiên, trò chơi, v.v Cuốn sách gồm năm chương, chương, tác giả cố gắng đưa vào nhiều ví dụ minh họa Nội dung chương sau : − Chương giới thiệu ngơn ngữ lập trình Prolog dựa lôgich Horn (Horn logic) Người đọc làm quen với kiểu liệu Prolog, khái niệm luật, kiện viết chương trình Prolog đơn giản − Chương trình bày mức nghĩa khác chương trình Prolog : nghĩa lôgich, nghĩa khai báo nghĩa thủ tục, cách Prolog trả lời câu hỏi, cách Prolog làm thoả mãn đích − Chương trình bày phép tốn số học, phép so sánh đối tượng định nghĩa hàm sử dụng phép đệ quy Prolog − Chương trình bày cấu trúc danh sách phép xử lý danh sách Prolog − Chương trình bày kỹ thuật lập trình nâng cao với Prolog − Phần phụ lục giới thiệu ngơn ngữ lập trình SWI-Prolog, hướng dẫn cách cài đặt sử dụng phần mềm số chương trình ví dụ tiêu biểu viết SWI Prolog chạy có kết Cuốn sách dùng làm giáo trình cho sinh viên ngành Tin học bạn đọc muốn tìm hiểu thêm kỹ thuật lập trình cho lĩnh vực trí tuệ nhân tạo Trong q trình biên soạn, tác giả nhận từ bạn đồng nghiệp nhiều đóng góp bổ ích mặt chun mơn, động viên khích lệ mặt tinh thần, giúp đỡ biên tập để sách đời Tác giả xin bày tỏ lòng biết ơn sâu sắc Tác giả chân thành cảm ơn ý kiến phê bình đóng góp bạn đọc gần xa nội dung sách Đà Nẵng, ngày 27/05/2004 Tác giả MỤC LỤC CHƯƠNG MỞ ĐẦU VỀ NGÔN NGỮ PROLOG I GIỚI THIỆU NGÔN NGỮ PROLOG I.1 Prolog ngơn ngữ lập trình lơgich I.2 Cú pháp Prolog I.2.1 Các thuật ngữ I.2.2 Các kiểu liệu Prolog I.2.3 Chú thích II CÁC KIỂU DỮ LIỆU SƠ CẤP CỦA PROLOG II.1 Các kiểu (trực kiện) II.1.1 Kiểu số II.1.2 Kiểu lôgich II.1.3 Kiểu chuỗi ký tự II.1.4 Kiểu nguyên tử II.2 Biến III SỰ KIỆN VÀ LUẬT TRONG PROLOG III.1 Xây dựng kiện III.2 Xây dựng luật 10 III.2.1 Định nghĩa luật 10 III.2.2 Định nghĩa luật đệ quy 16 III.2.3 Sử dụng biến Prolog 18 IV KIỂU DỮ LIỆU CẤU TRÚC CỦA PROLOG 20 IV.1 Định nghĩa kiểu cấu trúc Prolog 20 IV.2 So sánh hợp hạng 23 CHƯƠNG I II II.1 II.2 II.3 II.4 II.5 NGỮ NGHĨA CỦA CHƯƠNG TRÌNH PROLOG 31 QUAN HỆ GIỮA PROLOG VÀ LƠGICH TỐN HỌC 31 CÁC MỨC NGHĨA CỦA CHƯƠNG TRÌNH PROLOG 32 Nghĩa khai báo chương trình Prolog 33 Khái niệm gói mệnh đề 34 Nghĩa lôgich mệnh đề 35 Nghĩa thủ tục Prolog 37 Tổ hợp yếu tố khai báo thủ tục 47 i III III.1 III.2 III.3 III.3.1 III.3.2 VÍ DỤ : CON KHỈ VÀ QUẢ CHUỐI 48 Phát biểu toán 48 Giải toán với Prolog 49 Sắp đặt thứ tự mệnh đề đích 54 Nguy gặp vịng lặp vơ hạn 54 Thay đổi thứ tự mệnh đề đích chương trình 56 CHƯƠNG I I.1 I.2 I.3 II II.1 II.2 II.3 II.4 III III.1 III.2 III.3 III.3.1 III.3.2 III.3.3 CÁC PHÉP TOÁN VÀ SỐ HỌC 65 SỐ HỌC 65 Các phép toán số học 65 Biểu thức số học 65 Định nghĩa phép toán Prolog 68 CÁC PHÉP SO SÁNH CỦA PROLOG 73 Các phép so sánh số học 73 Các phép so sánh hạng 75 Vị từ xác định kiểu 77 Một số vị từ xử lý hạng 77 ĐỊNH NGHĨA HÀM 79 Định nghĩa hàm sử dụng đệ quy 79 Tối ưu phép đệ quy 87 Một số ví dụ khác đệ quy 88 Tìm đường đồ thị có định hướng 88 Tính độ dài đường đồ thị 89 Tính gần chuỗi 90 CHƯƠNG I II III III.1 III.1.1 III.1.2 III.1.3 III.1.4 III.1.5 III.1.6 III.2 CẤU TRÚC DANH SÁCH 95 BIỂU DIỄN CẤU TRÚC DANH SÁCH 95 MỘT SỐ VỊ TỪ XỬ LÝ DANH SÁCH CỦA PROLOG 98 CÁC THAO TÁC CƠ BẢN TRÊN DANH SÁCH 99 Xây dựng lại số vị từ có sẵn 99 Kiểm tra phần tử có mặt danh sách 99 Ghép hai danh sách 100 Bổ sung phần tử vào danh sách 104 Loại bỏ phần tử khỏi danh sách 104 Nghịch đảo danh sách 105 Danh sách 106 Hoán vị 107 III.3 III.3.1 III.3.2 III.3.3 Một số ví dụ danh sách 109 Sắp xếp phần tử danh sách 109 Tính độ dài danh sách 109 Tạo sinh số tự nhiên 111 CHƯƠNG I I.1 I.2 I.2.1 I.2.2 I.2.3 I.3 I.3.1 I.3.2 II II.1 II.2 II.3 II.3.1 II.3.2 II.4 II.5 II.5.1 II.5.2 II.5.3 II.5.4 II.5.5 III III.1 III.2 III.2.1 III.2.2 III.2.3 III.3 III.3.1 III.3.2 III.3.3 III.3.4 III.3.5 KỸ THUẬT LẬP TRÌNH PROLOG 117 NHÁT CẮT 117 Khái niệm nhát cắt 117 Kỹ thuật sử dụng nhát cắt 118 Tạo đích giả nhát cắt 118 Dùng nhát cắt loại bỏ hoàn toàn quay lui 119 Ví dụ sử dụng kỹ thuật nhát cắt 122 Phép phủ định 126 Phủ định thất bại 126 Sử dụng kỹ thuật nhát cắt phủ định 128 SỬ DỤNG CÁC CẤU TRÚC 131 Truy cập thông tin cấu trúc từ sở liệu 132 Trừu tượng hoá liệu 136 Mô ôtômat hữu hạn 138 Mô ôtômat hữu hạn không đơn định 138 Mô ôtômat hữu hạn đơn định 143 Ví dụ : lập kế hoạch du lịch máy bay 144 Bài toán tám quân hậu 150 Sử dụng danh sách toạ độ theo hàng cột 151 Sử dụng danh sách toạ độ theo cột 155 Sử dụng toạ độ theo hàng, cột đường CHÉO 158 Kết luận 161 Bộ diễn dịch Prolog 162 QUÁ TRÌNH VÀO-RA VÀ LÀM VIỆC VỚI TỆP 163 Khái niệm 163 Làm việc với tệp 164 Đọc ghi lên tệp 164 Một số ví dụ đọc ghi lên tệp 167 Nạp chương trình Prolog vào nhớ 171 Ứng dụng chế độ làm việc với tệp 172 Định dạng hạng 172 Sử dụng tệp xử lý hạng 173 Thao tác ký tự 175 Thao tác nguyên tử 177 Một số vị từ xử lý sở liệu 180 iii PHỤ LỤC A MỘT SỐ CHƯƠNG TRÌNH PROLOG 187 PHỤ LỤC B I II II.1 II.2 II.3 II.4 II.5 III HƯỚNG DẪN SỬ DỤNG SWI-PROLOG 200 GIỚI THIÊUU SWI-PROLOG 194 LAIM VIÊUC VỚI SWI-PROLOG 195 Đặt câu hỏi 195 Chạy trình demo 196 Chạy trình demo XPCE 197 Các lệnh đơn (Menu commands) 198 Soạn thảo chương trình 200 MỘT SỐ LỆNH SWI-PROLOG THÔNG DỤNG 201 TÀI LIỆU THAM KHẢO 203 CHƯƠNG Mở đầu ngôn ngữ Prolog « A program is a theory (in some logic) and computation is deduction from the theory » J A Robinson « Program = data structure + algorithm » N Wirth « Algorithm = logic + control » R Kowalski I Giới thiệu ngôn ngữ Prolog I.1 Prolog ngơn ngữ lập trình lơgich rolog ngơn ngữ sử dụng phổ biến dịng ngơn ngữ lập trình lơgich (Prolog có nghĩa PROgramming in LOGic) Ngôn ngữ Prolog giáo sư người Pháp Alain Colmerauer nhóm nghiên cứu ơng đề xuất lần trường Đại học Marseille đầu năm 1970 Đến năm 1980, Prolog nhanh chóng áp dụng rộng rãi châu Âu, người Nhật chọn làm ngôn ngữ phát triển dịng máy tính hệ Prolog cài đặt máy vi tính Apple II, IBM-PC, Macintosh Prolog cịn gọi ngơn ngữ lập trình ký hiệu (symbolic programming) tương tự ngơn ngữ lập trình hàm (functional programming), hay lập trình phi số (nonnumerical programming) Prolog thích hợp để giải toán liên quan đến đối tượng (object) mối quan hệ (relation) chúng Prolog sử dụng phổ biến lĩnh vực trí tuệ nhân tạo Ngun lý lập trình lơgich dựa mệnh đề Horn (Horn logíc) Một mệnh đề Horn biễu diễn kiện hay việc khơng đúng, xảy khơng xảy (có khơng có, v.v ) Ví dụ I.1 : Sau số mệnh đề Horn : Nếu người già mà (và) khơn ngoan người hạnh phúc Jim người hạnh phúc Nếu X cha mẹ Y Y cha mẹ Z X ơng Z Tom ơng Sue P Lập trình lôgic Prolog Tất người chết (hoặc Nếu người phải chết) Socrat người Trong mệnh đề Horn trên, mệnh đề 1, 3, gọi luật (rule), mệnh đề lại gọi kiện (fact) Một chương trình lơgich xem sở liệu gồm mệnh đề Horn, dạng luật, dạng kiện, chẳng hạn tất kiện luật từ đến Người sử dụng (NSD) gọi chạy chương trình lơgich cách đặt câu hỏi (query/ question) truy vấn sở liệu này, chẳng hạn câu hỏi : Socrat có chết không ? (tương đương khẳng định Socrat chết hay sai ?) Một hệ thống lôgich thực chương trình theo cách «suy luận»-tìm kiếm dựa vốn «hiểu biết» có chương trình - sở liệu, để minh chứng câu hỏi khẳng định, (Yes) sai (No) Với câu hỏi trên, hệ thống tìm kiếm sở liệu khẳng định Socrat chết «tìm thấy» luật thoả mãn (vế thì) Vận dụng luật 5, hệ thống nhận Socrat người (vế nếu) kiện Từ đó, câu trả lời : Yes có nghĩa kiện Socrat chết I.2 Cú pháp Prolog I.2.1 Các thuật ngữ Một chương trình Prolog sở liệu gồm mệnh đề (clause) Mỗi mệnh đề xây dựng từ vị từ (predicat) Một vị từ phát biểu đối tượng có giá trị chân (true) sai (fail) Một vị từ có đối nguyên lôgich (logic atom) Mỗi nguyên tử (nói gọn) biểu diễn quan hệ hạng (term) Như vậy, hạng quan hệ hạng tạo thành mệnh đề Hạng xem đối tượng “dữ liệu” trình Prolog Hạng hạng sơ cấp (elementary term) gồm (constant), biến (variable) hạng phức hợp (compound term) Các hạng phức hợp biểu diễn đối tượng phức tạp toán cần giải thuộc lĩnh vực xét Hạng phức hợp hàm tử (functor) có chứa đối (argument), có dạng Tên_hàm_tử(Đối_1, , Đối_n) Tên hàm tử chuỗi chữ và/hoặc chũ số bắt đầu chữ thường Các đối biến, hạng sơ cấp, hạng phức hợp Trong Prolog, Các phép toán số học 77 a(X) :- b(X) b(X) :- X1 is X - 2, write(X), write(' '), a(X1) Chương trình khơng gọi « đệ quy » even_succ_nat Kết sau lời gọi a(20) dãy số giảm dần 20 18 16 14 12 10 Ví dụ III.2 : Xây dựng số tự nhiên (Peano) phép cộng số tự nhiên /* Định nghĩa số tự nhiên */ nat(0) % số tự nhiên nat(s(N)) :% s(X) số tự nhiên nat(N) % N số tự nhiên Chẳng hạn số viết : s(s(s(s(s(zero))))) /* Định nghĩa phép cộng */ addi(0, X, X) % luật : + X = X /* addi(X, 0, X) sử dụng them luật : X + = X addi(s(X), Y, s(Z)) :- % luật : X + Y = Z (X+1) + Y = (Z+1) addi(X, Y, Z) Hoặc định nghĩa theo nat(X) sau : addi(0, X, X) :- nat(X) ?- addi(X, Y, s(s(s(s(0))))) X = 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ụ III.3 : Tìm ước số chung lớn (GCD: Greatest Common Divisor) Cho trước hai số nguyên X Y, ta cần tính ước số D USCLN dựa ba quy tắc sau : Nếu X = Y, D X Nếu X < Y, D USCLN X Y - X Nếu X > Y, thực tương tự bước 2, cách hốn vị vai trị X Y 78 Lập trình lơgic Prolog Có thể dễ dàng tìm ví dụ minh hoạ hoạt động ba quy tắc trước Với X =20 Y =25, ta nhận D =5 sau dãy phép trừ Chương trình Prolog xây dựng sau : gcd( X, X, X gcd( X, Y, D X < Y, Y1 is Y gcd( X, ) ) :– X, Y1, D ) gcd( X, Y, D ) :X > Y, gcd( Y, X, D ) Đích cuối mệnh đề thứ ba thay : X1 is X – Y, gcd( X1, Y, D ) Kết chạy Prolog sau : ?- gcd( 20, 55, D ) D = Ví dụ III.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 : N > 0, M = N - 1, Fm is (N-1)!, F = N * Fm, F N! Phép tốn is giống phép gán ngơn ngữ lập trình mệnh lệnh Prolog, is khơng gán giá trị cho biến Về mặt lôgich, thứ tự mệnh đề vế phải luật vai trị gì, lại có ý nghĩa thực chương trình M khơng phải biến lời gọi thủ tục đệ quy gây vịng lặp vơ hạn Các định nghĩa hàm Prolog thường rắc rối hàm quan hệ mà biểu thức Các quan hệ định nghĩa sử dụng nhiều luật thứ tự luật xác định kết trả hàm Ví dụ III.5 : Tính số Fibonacci /* Fibonacci function */ Các phép toán số học 79 fib(0, 0) % fib0 = fib(1, 1) % fib1 = 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 tốn tính số Fibonacci sử dụng hai lần gọi đệ quy nhanh chóng làm đầy nhớ với N=21, SWI-prolog phải dừng lại để thơng báo lỗi Ví dụ III.6 : Tính hàm Ackerman /* Ackerman's function */ ack(0, N, A) :- % Ack(0, n) = n + A is N + 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, ack(M1, N, A1), ack(M, A1, A) Ví dụ III.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ụ III.8 : Thuật tốn hợp 80 Lập trình lơgic Prolog Sau thuật toán hợp đơn giản cho phép xử lý trường hợp biến thay (hợp nhất) hạng mà hạng lại có chứa tên biến Chẳng hạn phép hợp X = f(X) không hợp lệ % unify(T1, T2) unify(X, Y) :% trường hợp biến var(X), var(Y), X = Y unify(X, Y) :% trường hợp biến = biến var(X), nonvar(Y), X = Y unify(X, Y) :% trường hợp 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 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 N tham đối X 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 tham đối có bậc N arg(N, X, ArgX), arg(N, Y, ArgY), unify(ArgX, ArgY) Ví dụ III.9 : Lý thuyết số Ta tiếp tục xây dựng hàm số tự nhiên định nghĩa ví dụ Ta xây dựng phép so sánh hai số tự nhiên dựa phép cộng sau : egal(+(X, 0), X) % phép cộng có tính giao hốn egal(+(0, X), X) egal(+(X, s(Y)), s(Z)) :egal(X+s(Y), s(Z)) % X YZ.egal(X+Y, Z) → Các phép toán số học egal(+(X, Y), Z) Sau số kết : ?- 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 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) ; 81 82 Lập trình lơgic Prolog X = _G299+s(s(0)) Y = s(s(_G299)) ; 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 83 Các phép toán số học III.2 Tối ưu phép đệ quy Lời giải toán sử dụng đệ quy ngơn ngữ lập trình nói chung thường ngắn gọn, dễ hiểu dễ quản lý chương trình Tuy nhiên, số trường hợp, sử dụng đệ quy lại xảy vấn đề độ phức tạp tính tốn, khơng tốn nhớ mà cịn tốn thời gian Trong ngơn ngữ mệnh lệnh, phép tính n! sử dụng đệ quy cần sử dụng nhớ có cỡ 0(n) thời gian tính tốn có cỡ 0(n), thay 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ụ tính số Fibonacci 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 Để ý lần gọi hàm fib(n) với n>1 dẫn tới hai lần gọi khác, nghĩa số lần gọi tăng theo luỹ thừa Với n lớn, chương trình gọi đệ quy dễ gây tràn nhớ Ví dụ sau tất lời gọi cho trường hợp n=5 fib5 3 1 2 1 Hình III.1 Biểu diễn 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 tính lại giá trị Chương trình Pascal dùng hai biến phụ x=fib(i) y=fib(i+1) : { tính fib(n) với n > } i:= 1; x:= 1; y:= 0; while i < n begin x:= x + y; y:= x – y end; Ta viết lại chương trình Prolog sau : fibo(0, 0) fibo(N, F) :N >= 1, fib1(N, 1, 0, F) fib1(1, F, _, F) fib1(N, F2, F1, FN) :- 84 Lập trình lơgic Prolog N > 1, N1 is N - 1, F3 is F1 + F2, fib1(N1, F3, F2, FN) ?- fibo(21, F) F = 10946 Yes ?- fibo(200, F) F = 2.80571e+041 Yes III.3 Một số ví dụ khác đệ quy III.3.1 Tìm đường đồ thị có định hướng Cho đồ thị có định hướng sau : A B C D E Hình III.2 Tìm đường đồ thị có định hướng Ta xét tốn tìm đường hai đỉnh đồ thị Mỗi cung nối hai đỉnh đồ thị biểu diễn quan hệ hai đỉnh Từ đồ thị trên, ta viết mệnh đề Prolog biểu diễn kiện : arc(a, arc(b, arc(c, arc(c, arc(a, b) c) e) d) e) Giả sử cần kiểm tra có tồn đường hai nút a d (không tồn đường hai nút mô tả), ta viết mệnh đề : path(a, d) Để định nghĩa này, ta nhận xét sau : • Tồn đường hai nút có cung nối chúng Các phép tốn số học 85 • Tồn đường hai nút X Y tồn nút thứ ba Z cho tồn đường X Z đường Z Y Ta viết chương trì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 hai người dòng họ ancestor(X, Y) xét trước ?- path(X, Y) X = a Y = b ; X = b Y = c ; III.3.2 Tính độ dài đường đồ thị Ta xét tốn tính độ dài đường hai nút, từ nút đầu đến nút cuối đồ thị số cung chúng Chẳng hạn độ dài đường hai nút a d ví dụ Ta lập luận sau : • Nếu hai nút có cung nối chúng độ dài đường • Gọi L độ dài đường hai nút X Y, L1 độ dài đường nút thứ ba Z Y tồn giả sử có cung nối X Z, L = L1 + Chương trình viết sau : trajectory(X, Y, 1) :- arc(X, Y) trajectory(X, Y, L) :arc(X, Z), trajectory(Z, Y, L1), L is L1 + trajectory(a, d, L) L = Yes III.3.3 Tính gần chuỗi Trong Tốn học thường gặp tốn tính gần giá trị hàm số với độ 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 độ xác 10-6 nhờ khai triển chuỗi Max Loren : 86 Lập trình lơgic Prolog ex = + x + x x3 + + 2! 3! Gọi expower(X, S) hàm tính giá trị hàm mũ theo X, biến S kết gần với độ xác e=10-6 Từ cơng thức khai triển Max Loren đây, ta nhận thấy giá trị hàm mũ ex tổng vơ hạn có dạng : sum(0) = 1, t0 = tương ứng với x = ex = sum(i+1) = sum(i) + ti+1, với ti+1 = ti * x /( i+1), i = 0, 1, Để thực phép lặp, ta cần xây dựng hàm đệ quy tính tổng sum(X, S, I, T) sử dụng biến trung gian I bước lặp thứ i T số hạng ti Theo cách xây dựng này, hàm tính tổng sum(X, S, I, T) tổng số hạng thứ I trở chuỗi Quá trình tính tổng dừng lại ti< e, nghĩa đạt độ xác e Tại thời điểm này, giá trị tổng số hạng ti Điều kiện khởi động trình lặp 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 T=1 Ta có chương trình đệ quy 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 ?- expower(1, S) S = 2.71828 Yes ?- expower(10, S) S = 22026.5 Yes Tóm tắt chương • Các phép tốn số học thực nhờ thủ tục thường trú Prolog Các phép toán số học 87 • Vai trị phép tốn tương tự vai trị hàm tử, để nhóm thành phần cấu trúc mà thơi • Mỗi NLT tự định nghĩa phép tốn riêng Mỗi phép tốn định nghĩa tên, độ ưu tiên kiểu gọi tham đối • Các phép toán cho phép NLT vận dụng cú pháp linh hoạt cho nhu cầu riêng họ Sử dụng phép tốn làm cho chương trình trở nên dễ đọc (readability) • Để tính biểu thức số học, tham đối có mặt biểu thức phải ràng buộc giá trị số • Chỉ dẫn op dùng để định nghĩa phép toán mới, gồm yếu tố : tên, kiểu độ ưu tiên phép tốn • Sử dụng phép tốn trung tố, tiền tố, hậu tố làm tăng cường tính dễ đọc chương trình Prolog • Độ ưu tiên số nguyên nằm khoảng giá trị cho trước, thông thường nằm 1200 Hàm tử biểu thức phép tốn có độ ưu tiên cao Các phép tốn có độ ưu tiên thấp ưu tiên • Kiểu phép toán phụ thuộc vào hai yếu tố : vị trí phép tốn so với tham đối, độ ưu tiên tham đối so sánh với độ ưu tiên phép toán Đối với ký hiệu đặc tả xfy, tham đối x có độ ưu tiên bé hẳn độ ưu tiên phép tốn, cịn tham đối y có độ ưu tiên bé độ ưu tiên phép toán Bài tập chương Cho biết kết câu hỏi sau : ?- X=Y ?- X is Y ?- X=Y, Y=Z, Z=1 ?- X=1, Z=Y, X=Y ?- X is 1+1, Y is X ?- Y is X, X is 1+1 ?- 1+2 == 1+2 ?- X == Y ?- X == X 88 Lập trình lơgic Prolog ?- =:= 2-1 ?- X =:= Y Cho biết kết câu hỏi sau : ?- 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)) Từ định nghĩa số tự nhiên (nat) phép cộng (addi) cho ví dụ mục định nghĩa hàm, viết tiếp hàm trừ (subt), nhân (multi), chia (divi), luỹ thừa (power), giai thừa (fact), so sánh nhỏ (less) tìm ước số chung lớn (pdg) sử dụng hàm có (chẳng hạn less, subt ) Viết hàm Prolog để kiểm tra số nguyên tuỳ ý N : a N số chẵn (even number) sử dụng đệ quy trực tiếp Hướng dẫn : N chẵn N±2 số chẵn b N số lẻ (odd number) sử dụng đệ quy trực tiếp Hướng dẫn : N lẻ N±2 số lẻ c N chẵn sử dụng hàm kiểm tra số lẻ câu d (N chẵn N±1 số lẻ) d N số lẻ sử dụng hàm kiểm tra số chẵn câu c (N lẻ N±1 chẵn) Viết hàm Prolog để làm duyệt (tracking/traverse) nhị phân theo thứ tự trước (reorder), sau (post-order) (in-order) Giả sử nhị phân tương ứng với biểu thức số học (5+6)*(3-(2/2)) mệnh đề Prolog sau : tree(’*’, tree(’+’, leaf(5), leaf(6)), tree(’-’, leaf(3), tree(’/’, leaf(2), leaf(2))) Kết duyệt sau : theo thứ tự trước : [*, +, 5, 6, -, 3, /, 2, 2] thứ tự : [5, +, 6, *, 3, -, 2, /, 2] thứ tự sau : [5, 6, +, 3, 2, 2, /, -, *] Viết lại hàm tạo 10 số tự nhiên chẵn (đã cho phần đệ quy) cho kết trả dãy số tăng dần Lập bảng nhân table(R, N) có số bị nhân (multiplicator) từ trở với số nhân N (multiplier) dừng lại gặp số bị nhân R (kết R * N) 89 Các phép toán số học Viết hàm tính gần giá trị hàm sau với độ xác e = 10-5 : 1 = − + − + π 1+ x2 x4 x6 + × + × × +