Giáo trình Lập trình hàm và lập trình Lôgic (Phần 2)
Các thuật ngữ
Một chương trình Prolog là một cơ sở dữ liệu gồm các mệnh đề (clause). Mỗi mệnh đề
được xây dựng từ các vị từ (predicat). Một vị từ là một phát biểu nào đó về các đối tượng có
giá trị chân đúng (true) hoặc sai (fail). Một vị từ có thể có các đối là các nguyên lôgich (logic
atom).
Mỗi nguyên tử (nói gọn) biểu diễn một quan hệ giữa các hạng (term). Như vậy, hạng và
quan hệ giữa các hạng tạo thành mệnh đề.
Hạng được xem là những đối tượng “dữ liệu” trong một trình Prolog. Hạng có thể là hạng
sơ cấp (elementary term) gồm hằng (constant), biến (variable) và các hạng phức hợp
(compound term).
Các hạng phức hợp biểu diễn các đối tượng phức tạp của bài toán cần giải quyết thuộc lĩnh
vực đang xét. Hạng phức hợp là một hàm tử (functor) có chứa các đối (argument), có dạng
Tên_hàm_tử(Đối_1, ., Đối_n)
Tên hàm tử là một chuỗi chữ cái và/hoặc chũ số được bắt đầu bởi một chữ cái thường. Các
đối có thể là biến, hạng sơ cấp, hoặc hạng phức hợp. Trong Prolog, hàm tử đặc biệt “.” (dấu
chấm) biểu diễn cấu trúc danh sách (list). Kiểu dữ liệu hàm tử tương tự kiểu bản ghi (record)
và danh sách (list) tương tự kiểu mảng (array) trong các ngôn ngữ lập trình mệnh lệnh (C,
Pascal.).
Ví dụ I.2 :
f(5, a, b).
student(robert, 1975, info, 2,
address(6, 'mal juin', 'Caen')).
[a, b, c]
Mệnh đề có thể là một sự kiện, một luật (hay quy tắc), hay một câu hỏi.
Prolog quy ước viết sau mỗi mệnh đề một dấu chấm để kết thúc như sau :
• Sự kiện : < .="">.
(tương ứng với luật < .=""> :- true. )
• Luật : < .=""> :- < .="">.
• Câu hỏi ?- < .="">.
(ở chế độ tương tác có dấu nhắc lệnh)
Tóm tắt nội dung tài liệu: Giáo trình Lập trình hàm và lập trình Lôgic (Phần 2)
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 122 CHƯƠNG 3 NGÔN NGỮ PROLOG A line may take us hours, yet if it does not seem a moment's thought All our stitching and unstitching has been as nought. Yeats - Adam's Curse I. Giới thiệu ngôn ngữ Prolog I.1. Prolog là ngôn ngữ lập trình lôgich Prolog là ngôn ngữ được sử dụng phổ biến nhất trong dòng các ngôn ngữ lập trình lôgich (Prolog có nghĩa là PROgramming in LOGic). Ngôn ngữ Prolog do giáo sư người Pháp Alain Colmerauer và nhóm nghiên cứu của ông đề xuất lần đầu tiên tại trường Đại học Marseille đầu những năm 1970. Đến năm 1980, Prolog nhanh chóng được áp dụng rộng rãi ở châu Âu, được người Nhật chọn làm ngôn ngữ phát triển dòng máy tính thế hệ 5. Prolog đã được cài đặt trên các máy vi tính Apple II, IBM-PC, Macintosh. Prolog còn được gọi là ngôn ngữ lập trình ký hiệu (symbolic programming) tương tự các ngôn ngữ lập trình hàm (functional programming), hay lập trình phi số (non-numerical programming). Prolog rất thích hợp để giải quyết các bài toán liên quan đến các đối tượng (object) và mối quan hệ (relation) giữa chúng. Prolog được sử dụng phổ biến trong lĩnh vực trí tuệ nhân tạo. Nguyên lý lập trình lôgich dựa trên các mệnh đề Horn (Horn logíc). Một mệnh đề Horn biễu diễn một sự kiện hay một sự việc nào đó là đúng hoặc không đúng, xảy ra hoặc không xảy ra (có hoặc không có, v.v...). Ví dụ I.1 : Sau đây là một số mệnh đề Horn : Nếu một người già mà (và) khôn ngoan thì người đó hạnh phúc. Jim là người hạnh phúc. Nếu X là cha mẹ của Y và Y là cha mẹ của Z thì X là ông của Z. Tom là ông của Sue. Tất cả mọi người đều chết (hoặc Nếu ai là người thì ai đó phải chết). Socrat là người. Trong các mệnh đề Horn ở trên, các mệnh đề 1, 3, 5 được gọi là các luật (rule), các mệnh đề còn lại được gọi là các sự kiện (fact). Một chương trình lôgich có thể được xem như là một cơ sở dữ liệu gồm các mệnh đề Horn, hoặc dạng luật, hoặc dạng sự kiện, chẳng hạn như tất cả các sự kiện và luật từ 1 đến 6 ở trên. Người sử dụng (NSD) gọi chạy một chương trình lôgich bằng cách đặt câu hỏi (query/ question) truy vấn trên cơ sở dữ 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 đúng hay sai ?) Một hệ thống lôgich sẽ thực hiện chương trình theo cách «suy luận»-tìm kiếm dựa trên vốn «hiểu biết» đã có là chương trình - cơ sở dữ liệu, để minh chứng câu hỏi là một khẳng định, là đúng (Yes) hoặc sai (No). Với câu hỏi trên, hệ thống tìm kiếm trong cơ sở dữ liệu khẳng định Socrat chết và «tìm thấy» luật 5 thoả mãn (vế thì). Vận dụng luật 5, hệ thống nhận được Socrat là người (vế nếu) chính là sự kiện 5. LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 123 Từ đó, câu trả lời sẽ là : Yes có nghĩa sự kiện Socrat chết là đúng. I.1.1. Cú pháp Prolog I.1.2. Các thuật ngữ Một chương trình Prolog là một cơ sở dữ liệu gồm các mệnh đề (clause). Mỗi mệnh đề được xây dựng từ các vị từ (predicat). Một vị từ là một phát biểu nào đó về các đối tượng có giá trị chân đúng (true) hoặc sai (fail). Một vị từ có thể có các đối là các nguyên lôgich (logic atom). Mỗi nguyên tử (nói gọn) biểu diễn một quan hệ giữa các hạng (term). Như vậy, hạng và quan hệ giữa các hạng tạo thành mệnh đề. Hạng được xem là những đối tượng “dữ liệu” trong một trình Prolog. Hạng có thể là hạng sơ cấp (elementary term) gồm hằng (constant), biến (variable) và các hạng phức hợp (compound term). Các hạng phức hợp biểu diễn các đối tượng phức tạp của bài toán cần giải quyết thuộc lĩnh vực đang xét. Hạng phức hợp là một hàm tử (functor) có chứa các đối (argument), có dạng Tên_hàm_tử(Đối_1, ..., Đối_n) Tên hàm tử là một chuỗi chữ cái và/hoặc chũ số được bắt đầu bởi một chữ cái thường. Các đối có thể là biến, hạng sơ cấp, hoặc hạng phức hợp. Trong Prolog, hàm tử đặc biệt “.” (dấu chấm) biểu diễn cấu trúc danh sách (list). Kiểu dữ liệu hàm tử tương tự kiểu bản ghi (record) và danh sách (list) tương tự kiểu mảng (array) trong các ngôn ngữ lập trình mệnh lệnh (C, Pascal...). Ví dụ I.2 : f(5, a, b). student(robert, 1975, info, 2, address(6, 'mal juin', 'Caen')). [a, b, c] Mệnh đề có thể là một sự kiện, một luật (hay quy tắc), hay một câu hỏi. Prolog quy ước viết sau mỗi mệnh đề một dấu chấm để kết thúc như sau : • Sự kiện : . (tương ứng với luật :- true. ) • Luật : :- . • Câu hỏi ?- . (ở chế độ tương tác có dấu nhắc lệnh) I.1.3. Các kiểu dữ liệu Prolog Hình 1.1. biểu diễn một sự phân lớp các kiểu dữ liệu trong Prolog gồm kiểu dữ liệu sơ cấp và kiểu dữ liệu có cấu trúc. Sự phân lớp này nhận biết kiểu của một đối tượng nhờ bề ngoài cú pháp. Cú pháp của Prolog quy định mỗi kiểu đối tượng có một dạng khác nhau. Prolog không cần cung cấp một thông tin nào khác để nhận biết kiểu của một đối tượng. Trong Prolog, NSD không cần khai báo kiểu dữ liệu. LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 124 Hình I.1. Các kiểu dữ liệu trong Prolog Các kiểu dữ liệu Prolog được xây dựng từ các ký tự ASCII : • Các chữ cái in hoa A, B, ..., Z và chữ cái in thường a, b, ..., z. • Các chữ số 0, 1, ..., 9. • Các ký tự đặc biệt, chẳng hạn + - * / = : . & _ ~. I.1.4. Chú thích Trong một chương trình Prolog, chú thích (comment) được đặt giữa hai cặp ký hiệu /* và */ (tương tự ngôn ngữ C). Ví dụ : /*************************/ /*** Đây là một chú thích ***/ /*************************/ Trong trường hợp muốn đặt một chú thích ngắn sau mỗi phần khai báo Prolog cho đến hết dòng, có thể đặt trước một ký hiệu %. Ví dụ : %%%%%%%%%%%%%%%%%%%%% % Đây cũng là một chú thích %%%%%%%%%%%%%%%%%%%%% Prolog sẽ bỏ qua tất cả các phần chú thích trong thủ tục. I.2. Các kiểu dữ liệu sơ cấp của Prolog I.2.1. Kiểu hằng số Prolog sử dụng cả số nguyên và số thực. Cú pháp của các số nguyên và số thực rất đơn giản, chẳng hạn như các ví dụ sau : 1 1515 0 -97 3.14 -0.0035 100.2 Tuỳ theo phiên bản cài đặt, Prolog có thể xử lý các miền số nguyên và miền số thực khác nhau. Ví dụ trong phiên bản Turbo Prolog, miền số nguyên cho phép từ -32768 đến 32767, miền số thực cho phép từ ±1e-307 đến ±1e+308. Các số thực rất khi được sử dụng trong Prolog. Lý do chủ yếu ở chỗ Prolog là ngôn ngữ lập trình ký hiệu, phi số. Các số nguyên thường chỉ được sử dụng khi cần đếm số lượng các phần tử hiện diện trong một danh sách Prolog dạng [a1, a2, ..., an ]. kiểu dữ liệu kiểu sơ cấp kiểu phức hợp hằng biến số chuỗi ký tự nguyên tử LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 125 I.2.2. Kiểu hằng lôgich Prolog sử dụng hai hằng lôgich có giá trị là true và fail. Thông thường các hằng lôgich không được dùng như tham số mà được dùng như các mệnh đề. Hằng fail thường được dùng để tạo sinh lời giải bài toán. I.2.3. Kiểu hằng chuỗi ký tự Các hằng là chuỗi (string) các ký tự được đặt giữa hai dấu nháy kép. "Toto \#\{@ tata" chuỗi có tuỳ ý ký tự "" chuỗi rỗng (empty string) "\"" chuỗi chỉ có một dấu nháy kép. I.2.4. Kiểu hằng nguyên tử Các hằng nguyên tử Prolog là chuỗi ký tự ở một trong ba dạng như sau : (1) Chuỗi gồm chữ cái, chữ số và ký tự _ luôn luôn được bắt đầu bằng một chữ cái in thường. newyork a_ nil x__y x25 tom_cruise (2) Chuỗi các ký tự đặc biệt : .:. ======> ::== ... (3) chuỗi đặt giữa hai dấu nháy đơn (quote) được bắt đầu bằng chữ in hoa, dùng phân biệt với các tên biến : ’Jerry’ ’Tom SMITH’ I.2.5. Biến Tên biến là một chuỗi ký tự gồm chữ cái, chữ số, bắt đầu bởi chữ hoa hoặc dấu gạch dưới dòng : X, Y, A Result, List_of_members _x23, _X, _, ... II. Sự kiện và luật trong Prolog II.1. Xây dựng sự kiện Ví dụ II.1 : Quan hệ gia đình Để xây dựng các sự kiện trong một chương trình Prolog, ta lấy một ví dụ về. Ta xây dựng một cây gia hệ như Hình II.1. Trong cây gia hệ (a), các nút chỉ người, còn các mũi tên chỉ quan hệ cha mẹ của (parent of). Sự kiện Tom là cha mẹ của Bill được viết thành một vị từ Prolog như sau (chú ý mệnh đề được kết thúc bởi một dấu chấm) : parent(tom, bill). % Chú ý không có dấu cách trước dấu mở ngoặc LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 126 Ở đây, vị từ parent có hai đối là tom và bill. Người ta có thể biểu diễn vị từ này bởi một cây như trong Hình II.1 (b) : nút gốc là tên của vị từ, còn các nút lá là các đối. (a) (b) Hình II.1.Cây gia hệ. Từ cây gia hệ trên đây, có thể tiếp tục viết các vị từ khác để nhận được một chương trình Prolog gồm 6 vị từ như sau : parent(mary, bill). parent(tom, bill). parent(tom, liz). parent(bill, ann). parent(bill, sue). parent(sue, jim). Sau khi hệ thống Prolog nhận được chương trình này, thực chất là một cơ sở dữ liệu, người ta có thể đặt ra các câu hỏi liên quan đến quan hệ parent. Ví dụ câu hỏi Bill có phải là cha mẹ của Sue được gõ vào trong hệ thống đối thoại Prolog (dấu nhắc ?-_) như sau : ?- parent(bill, sue). Sau khi tìm thấy sự kiện này trong chương trình, Prolog trả lời : Yes Ta tiếp tục đặt câu hỏi khác : ?- parent(liz, sue). No Bởi vì Prolog không tìm thấy sự kiện Liz là người mẹ của Sue trong chương trình. Tương tự, Prolog trả lời No cho sự kiện : ?- parent(tom, ben). Vì tên ben chưa được đưa vào trong chương trình. Ta có thể tiếp tục đặt ra các câu hỏi thú vị khác. Chẳng hạn, ai là cha (hay mẹ) của Liz ? ?- parent(X, liz). Lần này, Prolog không trả lời Yes hoặc No, mà đưa ra một giá trị của X làm thoả mãn câu hỏi trên đây : X = tom Để biết được ai là con của Bill, ta chỉ cần viết : ?- parent(bill, X). Với câu hỏi này, Prolog sẽ có hai câu trả lời, đầu tiên là : X = ann ->; mar tom bil l liz ann sue jim parent tom bill LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 127 Để biết được câu trả lời tiếp theo, trong hầu hết các cài đặt của Prolog, NSD phải gõ vào một dấu chấm phẩy (;) sau -> (Arity Prolog) : X = sue Nếu đã hết phương án trả lời mà vẫn tiếp tục yêu cầu (;), Prolog trả lời No. NSD có thể đặt các câu hỏi tổng quát hơn, chẳng hạn : ai là cha mẹ của ai ? Nói cách khác, cần tìm X và Y sao cho X là cha mẹ của Y. Ta viết như sau : ?- parent(X, Y). Sau khi hiển thị câu trả lời đầu tiên, Prolog sẽ lần lượt tìm kiếm những cặp cha mẹ − con thoả mãn và lần lượt hiển thị kết quả nếu chừng nào NSD còn yêu cầu cho đến khi không còn kết quả lời giải nào nữa (kết thúc bởi Yes) : X = mary Y = bill ->; X = tom Y = bill ->; X = tom Y = liz ->; X = bill Y = ann ->; X = bill Y = sue ->; X = sue Y = jim Yes Tuỳ theo cài đặt Prolog, NSD có thể gõ vào một dấu chấm (.) hoặc Enter để chấm dứt giữa chừng luồng trả lời. Ta có thể tiếp tục đưa ra những câu hỏi phức tạp hơn khác, chẳng hạn ai là ông (bà) của Jim ? Thực tế, quan hệ ông − bà (grandparent) chưa được định nghĩa, cần phải phân tách câu hỏi này thành hai phần sơ cấp hơn : 1. Ai là cha (mẹ) của Jim ? Giả sử có tên là Y. 2. Ai là cha (mẹ) của Y ? Giả sử có tên là X. Hình II.2. Quan hệ ông bà được hợp thành từ hai quan hệ cha mẹ. Lúc này, có thể viết trong Prolog như sau : ?- parent(Y, jim), parent(X, Y). Prolog trả lời : Y = sue X = bill Yes Câu hỏi trên đây tương ứng với câu hỏi : tìm X và Y thoả mãn : Y X jim parent grandparent parent LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 128 parent(Y, jim) và parent(X, Y). Nếu thay đổi thứ tự hai thành phần câu hỏi, thì nghĩa lôgich vẫn không thay đổi và Prolog trả lời cùng kết quả (có thể thay đổi về thứ tự), nghĩa là ta có thể đặt câu hỏi như sau : ?- parent(X, Y), parent(Y, jim). X = bill Y = đường dẫn Yes Bây giờ ta đặt câu hỏi ai là cháu của Tom ? ?- parent(tom, X), parent(X, Y). X = bill Y = ann->; X = bill Y = sue ->; No Một câu hỏi khác có thể như sau : Ann và Sue có cùng người ông không ? nghĩa là ta diễn đạt thành hai giai đoạn : 1. Tìm X là cha mẹ của Ann. 2. X tìm thấy có cùng là cha mẹ của Sue không ? Câu hỏi và trả lời trong Prolog như sau : ?- parent(X, ann), parent(X, sue). X = bill Trong Prolog, câu hỏi còn được gọi là đích (goal) cần phải được thoả mãn (satisfy). Mỗi câu hỏi đặt ra đối với cơ sở dữ liệu có thể tương ứng với một hoặc nhiều đích. Chẳng hạn dãy các đích : parent(X, ann), parent(X, sue). tương ứng với câu hỏi là phép hội (conjunction) của 2 mệnh đề : X là một cha mẹ của Ann, và X là một cha mẹ của Sue. Nếu câu trả lời là Yes, thì có nghĩa đích đã được thoả mãn, hay đã thành công. Trong trường hợp ngược lại, câu trả lời là No, có nghĩa đích không được thoả mãn, hay đã thất bại. Nếu có nhiều câu trả lời cho một câu hỏi, Prolog sẽ đưa ra câu trả lời đầu tiên và chờ yêu cầu của NSD tiếp tục. II.2. Xây dựng luật II.2.1. Định nghĩa luật Từ chương trình gia hệ trên đây, ta có thể dễ dàng bổ sung các thông tin khác, chẳng hạn bổ sung các sự kiện về giới tính (nam, nữ) của những người đã nêu tên trong quan hệ parent như sau : woman(mary). man(tom). man(bill). woman(liz). LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 129 woman(sue). woman(ann). man(jim). Ta đã định nghĩa các quan hệ đơn (unary) woman và man vì chúng chỉ liên quan đến một đối tượng duy nhất. Còn quan hệ parent là nhị phân, vì liên quan đến một cặp đối tượng. Như vậy, các quan hệ đơn dùng để thiết lập một thuộc tính của một đối tượng. Mệnh đề : woman(mary). được giải thích : Mary là nữ. Tuy nhiên, ta cũng có thể sử dụng quan hệ nhị phân để định nghĩa giới tính : sex(mary, female). sex(tom, male). sex(bill, male). . . . Bây giờ ta đưa vào một quan hệ mới child, đối ngược với parent như sau : child(liz, tom). Từ đó, ta định nghĩa luật mới như sau : child(Y, X) :- parent(X, Y). Luật trên được hiểu là : Với mọi X và Y, Y là con của X nếu X là cha (hay mẹ) của Y. hay Với mọi X và Y, nếu X là cha (hay mẹ) của Y thì Y là con của X. Có sự khác nhau cơ bản giữa sự kiện và luật. Một sự kiện, chẳng hạn : parent(tom, liz). là một điều gì đó luôn đúng, không có điều kiện gì ràng buộc. Trong khi đó, các luật liên quan đến các thuộc tính chỉ được thoả mãn nếu một số điều kiện nào đó được thoả mãn. Mỗi luật bao gồm hai phần: • phần bên phải (RHS: Right Hand Side) chỉ điều kiện, còn được gọi là thân (body) của luật, và • phần bên trái (LH: Left Hand Side S) chỉ kết luận, còn được gọi là đầu (head) của luật. Nếu điều kiện parent(X, Y) là đúng, thì child(Y, X) cũng đúng và là hậu quả lôgich của phép suy luận (inference). Câu hỏi sau đây giải thích cách Prolog sử dụng các luật : Liz có phải là con của Tom không ? ?- child(liz, tom) child(Y, X) :- parent(X, Y). đầu thân LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 130 Thực tế, trong chương trình không có sự kiện nào liên quan đến con, mà ta phải tìm cách áp dụng các luật. Luật trên đây ở dạng tổng quát với các đối tượng X và Y bất kỳ, mà ta lại cần các đối tượng cụ thể liz và tom. Ta cần sử dụng phép thế (substitution) bằng cách gán giá trị liz cho biến Y và tom cho X. Người ta nói rằng các biến X và Y đã được ràng buộc (bound) : X = tom và Y = liz Lúc này, phần điều kiện có giá trị parent(tom, liz) và trở thành đích con (sub-goal) để Prolog thay thế cho đích child(liz, tom). Tuy nhiên, đích này thoả mãn và có giá trị Yes vì chính là sự kiện đã thiết lập trong chương trình. Sau đây, ta tiếp tục bổ sung các quan hệ mới. Quan hệ mẹ mother đ ... đế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]).
File đính kèm:
- giao_trinh_lap_trinh_ham_va_lap_trinh_logic_phan_2.pdf