intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Lập trình trí tuệ nhân tạo Prolog

Chia sẻ: Nguyễn Văn Phong | Ngày: | Loại File: PDF | Số trang:103

Thêm vào BST
Báo xấu
696
lượt xem 204
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đối với Prolog, một chương trình có thể hiểu như là các tri thức được người lập trình cung cấp cho hệ thống Prolog. Nhờ vào các kiến thức được cung cấp, hệ thống có thể trả lời được các câu hỏi được đặt ra, và câu trả lời có thể đạt được nhờ cơ chế suy luận của hệ thống dựa trên những kiến thức được cung cấp ban đầu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lập trình trí tuệ nhân tạo Prolog

  1. BK ĐẠI HỌC BÁCH KHOA TPHCM TP.HCM KHOA CÔNG NGHỆ THÔNG TIN THỰC HÀNH NGÔN NGỮ LẬP TRÌNH TPHCM, Tháng 12 – 2005
  2. Mục lục PHẦN I. PROLOG _______________________________________________________ 1 Chương I. Vị từ (predicate) - Tư duy lập trình và định nghĩa vấn đề trên Prolog ______ 2 Chương II. Các clause, cách giải thích các vấn đề trên Prolog _______________________ 5 Chương III. Môi trường lập trình B-Prolog _______________________________________ 7 III.1 Giới thiệu sơ nét về B-Prolog ____________________________________________________ 7 III.2 Cài đặt và làm việc với B-Prolog__________________________________________________ 7 III.3 Gỡ rối chương trình (debugging)__________________________________________________ 8 III.4 Các thuật ngữ cơ bản trong B-Prolog ______________________________________________ 9 III.5 Các kiểu dữ liệu và các vị từ xây dựng sẵn (built-in) cơ bản trong B-Prolog _______________ 10 Chương IV. Thực thi chương trình. - Đặt câu hỏi và nhận câu trả lời_________________ 12 Chương V. IV. Phép hợp nhất - Cơ chế tìm câu trả lời của Prolog. __________________ 15 V.1 Phép hợp nhất _______________________________________________________________ 15 V.2 Cơ chế tìm câu trả lời của Prolog ________________________________________________ 16 Chương VI. Sự quay lui - Khống chế số lượng lời giải -Vị từ nhát cắt và fail ___________ 19 VI.1 Sự quay lui (back-tracing) trên Prolog_____________________________________________ 19 VI.2 Khống chế số lượng lời giải_____________________________________________________ 20 Chương VII. Lập trình đệ quy với Prolog ______________________________________ 22 Chương VIII. Danh sách trên Prolog ___________________________________________ 24 VIII.1 Cấu trúc của danh sách _____________________________________________________ 24 Chương IX. Lập trình đệ quy với danh sách trên Prolog ___________________________ 26 Chương X. Danh sách hai chiều _______________________________________________ 29 PHẦN II. LISP ________________________________________________________ 30 Chương I. Giới thiệu ________________________________________________________ 31 I.1 Lịch sử phát triển _______________________________________________________________ 31 I.2 Đặc điểm của gcLisp ____________________________________________________________ 31 1. Các đặc điểm của ngôn ngữ_____________________________________________________ 31 2. Kiểu dữ liệu _________________________________________________________________ 32 Chương II. Lập trình với gcLisp _______________________________________________ 33 II.1 Các khái niệm cơ bản _________________________________________________________ 33 1. Bắt đầu với LISP _____________________________________________________________ 33 2. Hàm và dữ liệu trong LISP _____________________________________________________ 34 3. Đánh giá____________________________________________________________________ 34 II.2 Các hàm xử lý trên danh sách ___________________________________________________ 34 1. FIRST và REST – CAR và CDR_________________________________________________ 34 2. CONS, APPEND, LIST________________________________________________________ 35 i
  3. 3. NTHCDR, BUTLAST và LAST _________________________________________________ 36 4. LENGTH và REVERSE _______________________________________________________ 37 II.3 Thao tác trên Integer, Ratio, Floating-Point Numbers, ... ______________________________ 37 II.4 Lập trình hướng dữ liệu ________________________________________________________ 38 1. ASSOC ____________________________________________________________________ 38 2. ACONS ____________________________________________________________________ 38 Chương III. Hàm và Biến cục bộ _______________________________________________ 40 III.1 Định nghĩa hàm – Chương trình đệ quy trong Lisp ___________________________________ 40 III.2 Biến cục bộ _________________________________________________________________ 41 1. LET _______________________________________________________________________ 41 2. LET* ______________________________________________________________________ 42 Chương IV. Các vị từ và biểu thức điều kiện _____________________________________ 43 IV.1 Vị từ_______________________________________________________________________ 43 IV.2 Các phép so sánh: EQUAL, EQ, EQL và =_________________________________________ 43 IV.3 Vị từ MEMBER______________________________________________________________ 44 IV.4 Vị từ NULL và ENDP _________________________________________________________ 45 IV.5 Các vị từ xác định kiểu dữ liệu __________________________________________________ 45 IV.6 Các vị từ trên số______________________________________________________________ 47 IV.7 Các toán tử logic _____________________________________________________________ 48 1. AND ______________________________________________________________________ 48 2. OR ________________________________________________________________________ 49 3. NOT_______________________________________________________________________ 49 IV.8 Các dạng điều kiện ___________________________________________________________ 50 1. IF, WHEN và UNLESS________________________________________________________ 50 2. COND _____________________________________________________________________ 51 3. CASE______________________________________________________________________ 51 Chương V. Trừu tượng hóa dữ liệu ____________________________________________ 53 V.1 Các trường của một ký hiệu_____________________________________________________ 53 V.2 Doublets____________________________________________________________________ 53 1. Doublets____________________________________________________________________ 53 2. Pointed pair _________________________________________________________________ 54 3. Ký hiệu pointed pair __________________________________________________________ 54 4. Doublets trong LISP __________________________________________________________ 54 V.3 Lời gọi hàm tính toán _________________________________________________________ 55 1. Apply ______________________________________________________________________ 55 2. Funcall _____________________________________________________________________ 55 V.4 Hàm vô danh ________________________________________________________________ 56 1. Lambda expression ___________________________________________________________ 56 2. Hàm vô danh và biến cục bộ ____________________________________________________ 56 Chương VI. Lặp trên số và trên danh sách _______________________________________ 57 VI.1 Các cấu trúc lặp ______________________________________________________________ 57 1. DOTIMES __________________________________________________________________ 57 ii
  4. 2. DOLIST Hỗ trợ lặp trên danh sách _______________________________________________ 57 3. DO tổng quát hơn DOLIST và DOTIMES _________________________________________ 59 VI.2 Các dạng đặc biệt_____________________________________________________________ 59 1. progn ______________________________________________________________________ 59 2. prog1 ______________________________________________________________________ 59 Chương VII. Các thao tác với tập tin __________________________________________ 61 VII.1 Lưu lại tập tin chương trình và dữ liệu ____________________________________________ 61 VII.2 Biên dịch tập tin______________________________________________________________ 61 VII.3 Debugging __________________________________________________________________ 61 Chương VIII. Cài đặt và sử dụng gcLisp ________________________________________ 63 VIII.1 Cài đặt___________________________________________________________________ 63 VIII.2 Startup Gclisp _____________________________________________________________ 63 VIII.3 Phím nóng________________________________________________________________ 63 VIII.4 Dòng lệnh ________________________________________________________________ 64 VIII.5 Lệnh tiền tố (Prefix command) ________________________________________________ 64 VIII.6 Cửa sổ soạn thảo GMAC ____________________________________________________ 64 VIII.7 Load file vào gclisp_________________________________________________________ 64 PHẦN III. SMALLTALK_________________________________________________ 66 Chương I. LÝ THUYẾT VỀ OOP VÀ NGÔN NGỮ SMALLTALK ________________ 67 I.1 Lập trình hướng đối tượng (Object Oriented Programming) với Smalltalk ___________________ 67 1. Đối tượng (Object) - Các thành phần (member) của đối tượng: Các thuộc tính (properties) và các phương thức (methods) - Sự bao đóng (encapsulation). ____________________________________ 67 2. Khái niệm class - Mối quan hệ giữa object và class - Khái niệm instance. _________________ 67 3. Phương thức - Thông điệp (message) - Đối tượng nhận thông điệp (receiver). Đối số của thông điệp (argument) ___________________________________________________________________ 68 4. Các loại thông điệp: unary, binary và keyword. Độ ưu tiên giữa các thông điệp. ____________ 69 5. Câu lệnh (statement) - kịch bản (script)____________________________________________ 70 6. Che giấu thông tin (hiding information) ___________________________________________ 71 7. Sự thừa kế (inheritance) - Che phủ (override) - Sự dẩn xuất (derivation) - Mối quan hệ giữa các đối tượng: cây các lớp. _____________________________________________________________ 71 8. Tính đa hình (polymorphism) - Sự ràng buộc muộn (late - binding)______________________ 72 I.2 Ngôn ngữ Smalltalk _____________________________________________________________ 72 1. Object trên Smalltalk. Thuộc tính thường và thuộc tính indexed. Các thành phần cho đối tượng và thành phần cho lớp ________________________________________________________________ 72 2. Các literal - object: Integer, Float, Character, Boolean, Array, String, Context _____________ 73 3. Khai báo biến - Ràng buộc về kiểu trên ngôn ngữ Smalltalk - Phát biểu gán - Phát biểu trả về _ 74 4. Định nghĩa một object mới. Các phương thức new và new: ____________________________ 75 5. Định nghĩa một class mới và phương thức mới - Sự biên dịch offline và online một phương thức 76 6. Bên trong phương thức - Các từ khóa self và super___________________________________ 76 7. Các phương thức primitive _____________________________________________________ 78 8. Khái niệm về MetaClass - Sử dụng MetaClass - Lập trình OOP động (dynamic) với Smalltalk 78 iii
  5. 9. Các lớp đặc biệt: Compiler, Window, ViewManager, Prompter... _______________________ 79 I.3 Một số kỹ thuật lập trình căn bản trên Smalltalk _______________________________________ 79 1. Sự mô phỏng các cấu trúc điều khiển. _____________________________________________ 79 2. Thao tác trên tập hợp (collection). Một số kỹ thuật xử lý trên tập hợp.____________________ 80 Chương II. HƯỚNG DẪN SỬ DỤNG VWIN VERSION 2.0 _______________________ 83 II.1 Hướng dẫn sử dụng chương trình VWIN: __________________________________________ 83 1. Thao tác trên hệ thống lớp ______________________________________________________ 83 2. Lập trình ___________________________________________________________________ 85 3. Load và Save file. ____________________________________________________________ 88 4. Gỡ rối______________________________________________________________________ 88 II.2 Giới thiệu về một số lớp có sẳn của VWIN _________________________________________ 90 1. Lớp Object__________________________________________________________________ 90 2. Lớp Magnitude ______________________________________________________________ 91 3. Lớp Number, Integer, Float, Character ____________________________________________ 91 4. Lớp IndexedCollection: ________________________________________________________ 91 5. Lớp Context: ________________________________________________________________ 94 Chương III. MỘT SỐ KỸ THUẬT LẬP TRÌNH CĂN BẢN VỚI LỚP COLLECTION TRÊN SMALLTALK - VÍ DỤ VÀ BÀI TẬP _______________________________________ 96 III.1 Sử dụng phương thức do: ______________________________________________________ 96 1. Ví dụ:______________________________________________________________________ 96 2. Bài tập đề nghị: ______________________________________________________________ 96 III.2 Sử dụng phương thức select: hoặc reject: __________________________________________ 97 1. Ví dụ:______________________________________________________________________ 97 2. Bài tập đề nghị_______________________________________________________________ 97 III.3 Sử dụng phương thức collect: ___________________________________________________ 97 1. Ví dụ:______________________________________________________________________ 97 2. Bài tập đề nghị: ______________________________________________________________ 98 III.4 Bài tập tổng hợp: _____________________________________________________________ 98 1. Ví dụ:______________________________________________________________________ 98 2. Bài tập đề nghị_______________________________________________________________ 98 iv
  6. PHẦN I. PROLOG
  7. Hướng dẫn sử dụng BProlog Chương I. Vị từ (predicate) - Tư duy lập trình và định nghĩa vấn đề trên Prolog Đối với Prolog, một chương trình có thể hiểu như là các tri thức được người lập trình cung cấp cho hệ thống Prolog. Nhờ vào các kiến thức được cung cấp, hệ thống có thể trả lời được các câu hỏi được đặt ra, và câu trả lời có thể đạt được nhờ cơ chế suy luận của hệ thống dựa trên những kiến thức được cung cấp ban đầu. Đơn vị kiến thức mà người lập trình cung cấp cho Prolog gọi là các vị từ (predicate). Các vị từ dùng để biểu diễn các khái niệm mà người lập trình muốn hệ thống dùng để suy luận để đạt được các kiến thức khác mà mình mong muốn. Về mặt kỹ thuật, các predicate có thể được xem như các hàm, nhưng giá trị trả về chỉ có thể là các giá trị luận lý - đúng hoặc sai. Và giá trị trả về này chỉ có thể sử dụng để suy luận, Prolog không có cơ thế chồng chất hàm như các ngôn ngữ thủ tục khác, chính điều này sẽ làm những người quen với việc lập trình thủ tục gặp khó khăn khi bước đầu lập trình với Prolog. Công việc đầu tiên khi lập trình trên Prolog là định nghĩa các vị từ - các khái niệm mà mình cần cung cấp cho chương trình. Xét các ví dụ sau: VD1: Dữ kiện ban đầu: Mọi người đều phải chết. Socrates là người. Yêu cầu: Chúng ta muốn hệ thống phải có khả năng suy luận và trả lời được các vấn đề liên quan đến các khái niệm trên: ai là người, ai không là người, ai phải chết, ai không phải chết. Ở đây chúng ta có một sự suy luận thông minh đặc trưng cho sức mạnh của Prolog: hệ thống sẽ tự động suy luận rằng Socrates phải chết (điều không được cung cấp ban đầu). Để biểu diễn các vấn đề trên bằng ngôn ngữ Prolog, chúng ta cần phải xác định cần phải biểu diễn những khái niệm gì. Trong vấn đề này chúng ta có hai khái niệm cần biểu diễn: một thực thể nào đó có thể là người (hoặc không), và một thực thể nào đó có thể chết. Như vậy chúng ta biểu diễn vấn đề đầu tiên bằng ngôn ngữ Prolog như sau: nguoi(symbol) Symbol là một kiểu dữ liệu đặc biệt của Prolog, dùng để biểu diễn cho một thực thể, một khái niệm tổng quát. Như vậy chúng ta vừa định nghĩa một khái niệm: một symbol nào đó có thể là người, một symbol nào khác thì không. Hiểu như một sự định nghĩa hàm, chúng ta có thể xem như định nghĩa một hàm mang tên nguoi, hàm này có thông số một biến thuộc kiểu dữ liệu symbol, và kết quả của hàm này, 2
  8. Hướng dẫn sử dụng BProlog không cần phải khai báo thuộc về kiểu gì, vì chỉ có thể thuộc kiểu boolean, chỉ có thể đúng hoặc sai. Nhiệm vụ của Prolog là phải trả lời được với giá trị symbol nhập vào, thì hàm này cho ra kết quả đúng hoặc sai, tức symbol ấy có phải là người hay không. Prolog chỉ có thể làm được điều này nếu như nếu như chúng ta cung cấp cho hệ thống một cơ chế suy luận đúng đắn, tức là giải thích được cho Prolog hiểu như thế nào là người? Tương tự như vậy, chúng ta định nghĩa về vấn đề một thực thể nào đó phải chết bằng vị từ sau chet(symbol) Như vậy với bài toán đã nêu, chúng ta sẽ đặt ra hai vị từ nguoi(symbol) chet(symbol) VD2: Yêu cầu: tính giá trị giai thừa của một số nguyên bất kỳ. Bài toán trên không cho biết dữ kiện ban đầu. Chúng ta phải cung cấp các dữ kiện ban đầu, để Prolog có thể dựa vào đó để suy luận, để từ đó hệ thống có thể giải quyết được yêu cầu của chúng ta. Việc cung cấp dữ kiện ban đầu cho hệ thống là rất quan trọng quyết định vấn đề giải quyết yêu cầu của chúng ta. Một trong những cách giải quyết có thể được lựa chọn là chúng ta sẽ cho hệ thống biết giá trị giai thừa của toàn bộ số nguyên: giai thừa của 0 là 1, giai thừa của 1 là 1, giai thừa của 2 là 2, giai thừa của 3 là 6, giai thừa của 4 là 24… Dễ dàng nhận thấy rằng cách này là không khả thi, và trong thực tế, con người cũng không tiếp thu tri thức theo cách này. Chúng ta có thể cung cấp dữ kiện cho hệ thống theo cách khác: giai thừa của một số là tích các số từ 1 đến số đó. Như vậy với cách giải quyết này, chúng ta có hai khái niệm cần phải cung cấp: giai thừa của một số là gì, và tích của các số nguyên tính từ 1 đến một số là gì? Cách đặt vấn đề này có thể giải quyết được bài toán, tuy nhiên chúng ta có thể đặt vấn đề theo một cách khác đơn giản, và hợp với tinh thần của Prolog hơn: giai thừa của 0 là 1, và giai thừa của một số lớn hơn 0 là giai thừa của số liền trước nó nhân với chính nó. Với cách đặt vấn đề này, chúng ta chỉ có một khái niệm phải biểu diễn: giai thừa của một số là gì? (thật ra chúng ta còn một số khái niệm phải đưa ra: một số đứng trước một số là gì, nhân hai số nghĩa là gì, tuy nhiên Prolog đã cung cấp các toán tử để giải quyết vấn đề này. Hiểu theo một nghĩa nào đó, các vấn đề trên là các tiên đề, không cần phải giải thích với hệ thống.) Nếu quen với ngôn ngữ lập trình thủ tục, chúng ta có khuynh hướng diễn tả khái niệm giai thừa như sau: giaithua(integer) Ở đây cách đặt vấn đề như vậy là không thích hợp với ngôn ngữ Prolog, vì 3
  9. Hướng dẫn sử dụng BProlog . Một vị từ chỉ có thể trả lời là đúng hoặc sai, trong khi chúng ta đang mong muốn kết quả trả về theo cách khai báo này một số . Ngôn ngữ Prolog không có sự chồng chất hàm, nghĩa là kết quả của hàm (vị từ) không thể dùng như một thông số cho một vị từ khác, trong khi chúng ta đang định dùng kết quả của hàm này để tính tiếp giá trị cho một hàm khác.(Chúng ta định dùng hàm này để tính giai thừa của n -1 , rồi nhân tiếp cho n để ra kết quả cuối cùng). Vị từ thích hợp sẽ như sau: giaithua(integer,integer) Điều này, hiểu theo ngôn ngữ thủ tục, nghĩa là chúng ta khai báo một hàm có thông số là hai số nguyên, và kết quả trả về sẽ là đúng hoặc sai. Điều chúng ta muốn diễn tả có nghĩa là: giai thừa của một số nguyên (integer) sẽ là một số nguyên khác. Nếu chúng ta giải thích được cho Prolog hiểu giai thừa của một số nguyên sẽ được tính như thế nào, hệ thống sẽ có khả năng trả lời cho cả câu hỏi thuận (giai thừa của một số nguyên là gì), câu hỏi nghịch (số nguyên nào có giai thừa bằng số nguyên này), và nghi vấn (giai thừa của một số nguyên X có phải là số nguyên Y hay không). Tuy nhiên mục đích của chúng ta chỉ cung cấp các dữ kiện để hệ thống có thể trả lời câu hỏi thuận (và có thể trả lời thêm câu hỏi nghi vấn) mà thôi. Tóm tắt: . Lập trình trên Prolog là cung cấp cho hệ thống các khái niệm và diễn giải các khái niệm đó. . Các khái niệm được cung cấp qua các vị từ. . Các vị từ có thể xem như các hàm như chỉ trả về giá trị đúng hoặc sai. . Việc hệ thống có thể trả lời được những câu hỏi nào liên quan đến khái niệm đã cung cấp phụ thuộc vào việc chúng ta diễn giải các khái niệm trên cho hệ thống 4
  10. Hướng dẫn sử dụng BProlog Chương II. Các clause, cách giải thích các vấn đề trên Prolog Sau khi đã cung cấp cho hệ thống các khái niệm cần thiết, chúng ta cần phải giải thích các khái niệm mình đã cung cấp, Prolog sẽ dùng các lời giải thích này để thực hiện việc suy luận và trả lời câu hỏi của chúng ta. Các lời giải thích này được gọi là các mệnh đề (clauses). Có hai dạng mệnh đề: sự kiện (fact), và luật ( rule) Các sự kiện là những điều mà chúng ta công nhận là đúng. Luật là những quy tắc mà chúng ta xác định điều kiện đúng cho chúng. VD3: hãy viết phần clause cho vị từ nguoi đã định nghĩa trong VD1 Dữ kiện ban đầu chỉ cung cấp cho chúng ta một vấn đề liên quan đến người: Socrates là người. Theo như cách tư duy trong không gian của bài toán, chỉ có một con người duy nhất: Socrates. Không ai khác là người. Như vậy chúng ta sẽ viết phần clause cho vị từ này như sau: nguoi(socrates). Chúng ta vừa viết một sự kiện: socrates là người là điều chắc chắn đúng. Bất kỳ symbol nào có tên là socrates là người là chắc chắn đúng, không cần phải có một điều kiện ràng buộc nào kèm theo. Lưu ý: i/ Có hai cách viết dạng hằng (literal) cho symbol trên Prolog: Một danh hiệu mở đầu bằng ký tự thường (socrates, sOCRATES…) Một chuỗi ký hiệu đặt trong cặp ký hiệu ‘’ (‘socrates’,’SOCRATES’,’ sOCRATES’, ‘Socrates’…) ii/ Một mệnh đề luôn kết thúc bằng ký tự '.' VD4: hãy viết phần clause cho vị từ chet trong VD1. Dữ kiện ban đầu chỉ cung cấp cho chúng ta một sự kiện liên quan đến vấn đề này: symbol sẽ phải chết nếu (và chỉ nếu) đó là người. Điều này sẽ xác định một quy tắc: symbol sẽ chỉ phải chết, tức vị từ sẽ trả về kết quả true, nếu symbol đó là người. Vấn đề symbol nào là người và symbol nào không là người chúng ta đã đưa ra khái niệm và giải thích cho Prolog trong các ví dụ 1 và 3. Như vậy phần mệnh đề sẽ được viết như sau; chet(X):-nguoi(X). Mệnh đề dạng rule sẽ bao gồm hai phần, nằm ở hai bên cặp ký hiệu ":-". Phần bên trái cho biết vị từ đang được đề cập và các thông số tương ứng. Phần bên phải, xác định điều kiện trả lời đúng cho luật trên, bao gồm các lời gọi các vị từ khác, được ngăn cách bởi ký hiệu ',', gọi 5
  11. Hướng dẫn sử dụng BProlog là các mệnh đề con (sub-clause). Trong ví dụ trên, chỉ có một sub-clause. Một luật chỉ trả lời đúng nếu tất cả các sub-clause bên vế phải đều trả lời đúng. Trong ví dụ trên, chúng ta có một biến X. Tất cả các thông số mở đầu bằng ký tự hoa đều được Prolog hiểu là biến. Biến này là thông số của vị từ chet. Do đã khai báo ở phần vị từ, X sẽ được hiểu là một biến thuộc kiểu symbol. Kết quả sẽ trả về đúng nếu tất cả sub-clause bên vế phải đều trả lời là đúng. Trong trường hợp này, chỉ có một sub-clause xác định xem X có phải là người không. Như vậy chúng ta đã biểu diễn được khái niệm một symbol sẽ phải chết nếu symbol đó là người, tức là tất cả những dữ kiện ban đầu được cung cấp. VD5: Hãy viết phần clause cho vị từ giaithua ở VD2. Từ các dữ kiện được cung cấp (do chúng ta tự cung cấp cho mình để giải bài toán), chúng ta thấy có một sự kiện chắc chắn đúng: giai thừa của 0 là 1, và có một luật suy diễn: giai thừa của n là (n-1)!*n. Chúng ta sẽ viết phần mệnh đề cho vị từ này như sau: giaithua(0,1). giaithua(X,Y) -: X1 is X -1, giaithua(X1,Y1), Y is Y1*X. Trước khi hiểu những điều được mô tả trong các ví dụ trên, chúng ta sẽ có một số nhận xét như sau: i./Trước tiên, chúng ta thấy vị từ giaithua được biểu diễn bằng hai mệnh đề: một sự kiện và một luật. Khi viết nhiều mệnh đề cho một vị từ, các mệnh đề phải được viết liên tiếp nhau (không được xen mệnh đề của vị từ khác vào). ii./ Chúng ta sẽ hiểu hai mệnh đề con đầu tiên X1 is X -1, giaithua(X1,Y1) biểu diễn cho công việc tính giai thừa của X-1. Tuy nhiên chúng ta không được viết giaithua(X-1, Y1). Thông số của các mệnh đề con phải là biến, không được phép là biểu thức. iii./ Chúng ta thấy sự xuất hiện của phép quan hệ 'is' và sẽ hiểu như mệnh đề con X1 is X- 1 là phép gán. Thực tế, với phép quan hệ 'is' có dạng exp1 is exp2, nếu exp1 là một biến thì phép toán này sẽ ràng buộc biến này với kết quả của biểu thức exp2. Nếu exp1 không phải là một biến mà là một biểu thức bình thường thì phép quan hệ này tương đương với phép so sánh 2 biểu thức số học exp1 =:= exp2. iv./ Phần vị từ trên biểu diễn cho việc sử dụng kỹ thuật lập trình đệ quy, sẽ là sức mạnh lập trình chủ yếu của Prolog. Xem thêm về phần lập trình đệ quy trên Prolog trong các phần sau. Tóm tắt . Các khái niệm được mô tả qua các vị từ sẽ được giải thích bằng các mệnh đề. . Có hai loại mệnh đề: sự kiện và luật. . Thông số được truyền trong lời gọi các mệnh đề con phải là biến. . Các kỹ thuật chủ yếu để lập trình trên Prolog là hợp nhất và đệ quy. 6
  12. Hướng dẫn sử dụng BProlog Chương III. Môi trường lập trình B-Prolog Trước khi thực thi các chương trình viết bằng ngôn ngữ Prolog ở trên, chúng ta cần phải chọn một môi trường lập trình cụ thể. Trong môn học này, chúng ta sẽ sử dụng phần mềm lập trình B-Prolog (http://www.cad.mse.kyutech.ac.jp/people/zhou/bprolog.html) của Neng-Fa Zhou làm công cụ lập trình cho ngôn ngữ Prolog. Phần này đầu tiên sẽ giới thiệu sơ lược về B-Prolog: cách cài đặt, một phiên làm việc trên nó, các kiểu dữ liệu và một số vị từ có sẵn. Phần tiếp theo sẽ trình bày cách sử dụng B-Prolog để viết các chương trình ví dụ đơn giản. III.1 Giới thiệu sơ nét về B-Prolog B-Prolog ngoài việc hỗ trợ viết các chương trình bằng ngôn ngữ Prolog chuẩn còn cung cấp một môi trường cho phép người sử dụng có thể nạp (consult, load), dịch (compile), debug và thực thi chương trình. Đặc biệt là môi trường này cho phép sử dụng lại các lệnh đã gọi trước đó thông qua phím mũi tên lên và xuống. Ngoài ra, B-Prolog còn có thể liên kết với ngôn ngữ C, C++, Java; hỗ trợ lập trình đồ họa cũng như cho phép lập trình ràng buộc (Constraint Logic Programming) trên nó. Trong B-Prolog, chúng ta không cần phải khai báo tường minh các vị từ như Turbo Prolog mà chúng ta chỉ cần viết các mệnh đề để giải thích về vấn đề quan tâm. III.2 Cài đặt và làm việc với B-Prolog Tải chương trình B-Prolog từ địa chỉ và giải nén nó vào một thư mục bất kỳ. Thư mục mặc định để giải nén của B-Prolog là C:\Bprolog. Nếu chúng ta giải nén ngay trong thư mục mặc định này thì chúng ta chỉ cần chạy file C:\Bprolog\bp.bat để vào môi trường làm việc của B-Prolog. Nếu chúng ta giải nén vào một thư mục khác thì chúng ta phải sửa lại đường dẫn (mục BPDIR) trong file bp.bat này đến nơi mà chúng ta đã giải nén. Ngoài ra, nếu chúng ta muốn sử dụng các gói trong đồ họa thì chúng ta phải chạy file bpp.bat. Sau khi hoàn tất giai đoạn cài đặt, màn hình khi chạy file bp.bat sẽ như sau: 7
  13. Hướng dẫn sử dụng BProlog Khi đã vào được môi trường B-Prolog, chúng ta sẽ thấy một dấu nhắc | ?-. Đây sẽ là nơi mà chúng ta nhập các lệnh vào. Nếu muốn biết các lệnh mà hệ thống B-Prolog này hỗ trợ chúng ta gõ lệnh help ở dấu nhắc này. Để thoát khỏi B-Prolog chúng ta sử dụng lệnh halt hoặc nhấn tổ hợp phím Ctrl-D. Các chương trình Prolog của chúng ta thường được viết dưới dạng một file văn bản bằng một chương trình soạn thảo bất kỳ (EditPlus, Notepad...). Phần mở rộng mặc định của các file chương trình đối với B-Prolog là .pl. Để dịch một chương trình Prolog trong môi trường B-Prolog thì chúng ta dùng lệnh compile(file-name) với file-name là tên chương trình cần dịch. Nếu tên file này có phần mở rộng là .pl thì có thể không cần gõ vào phần mở rộng đó. File được dịch sẽ có cùng tên file- name với file dịch nhưng có phần mở rộng là .out. Để thực thi một file trong B-Prolog chúng ta phải nạp các file đã được dịch này vào bộ nhớ bằng lệnh load(file-name). Một cách để kết hợp cả giai đoạn dịch và nạp này là sử dụng lệnh consult(file-name) hoặc đơn giản là gõ [file- name] ở dấu nhắc lệnh. Sau khi nạp chương trình, chúng ta có thể thực thi chương trình thông qua các câu hỏi (query). Với mỗi câu hỏi hệ thống sẽ thực thi chương trình và trả kết quả về là yes nếu thành công và no nếu việc thực thi chương trình thất bại. Nếu trong câu hỏi có chứa biến và việc thực thi thành công thì chương trình sẽ thông báo cho chúng ta giá trị ràng buộc với các biến đó. Chúng ta có thể yêu cầu hệ thống tìm thêm lời giải khác bằng cách gõ dấu ; và enter sau lời giải đã biết. III.3 Gỡ rối chương trình (debugging) 8
  14. Hướng dẫn sử dụng BProlog Để gỡ rối cho một chương trình Prolog cũng như để hiểu rõ hơn cơ chế hoạt động của Prolog, chúng ta sẽ sử dụng lệnh trace. Khi gõ lệnh trace ở dấu nhắc, hệ thống sẽ chuyển sang chế độ gỡ rối. Khi đang ở chế độ gỡ rối, tất cả các lệnh, câu hỏi nhập vào cho hệ thống sẽ được thực hiện theo từng bước. Để thoát khỏi chế độ gỡ rối, chúng ta sử dụng lệnh notrace. III.4 Các thuật ngữ cơ bản trong B-Prolog Toán hạng (term) trong B-Prolog là các hằng, biến hoặc các toán hạng tổ hợp (compound term). Có 2 loại hằng: atom và số. Atom là chuỗi các ký tự, số hoặc dấu gạch dưới có ký tự bắt đầu ở dạng chữ thường. Bất kỳ chuỗi nào nằm giữa cặp dấu nháy đơn đều là atom. Đây chính là kiểu litteral mà ở phần trước chúng ta đã đề cập đến. Một dấu nháy đơn cũng được dùng để biểu diễn ký tự escape. Ví dụ: chuỗi ‘a’’b’ chứa 3 ký tự là a, ’ và b. Số có thể là số nguyên hoặc số thực dấu chấm động. Số nguyên thập phân có thể là số có dấu hoặc không dấu và có tầm trị từ -227 + 1 đến 227 -1. Có thể biểu diễn 1 số nguyên ở dạng cơ số khác 10 theo dạng tổng quát sau: ’ với base là cơ số và digits là dãy số biểu diễn của số nguyên đó. Ví dụ: 2’100 là biểu diễn nhị phân của số 4. Số thực dấu chấm động bao gồm một số nguyên để biểu diễn phần nguyên, một dấu chấm để phân cách giữa phần thập phân và phần nguyên và một số nguyên khác để biểu diễn phần thập phân. Hiện nay, B-Prolog không hỗ trợ dạng số mũ. Biến, như đã đề cập ở phần trên, giống như atom nhưng bắt đầu bằng một chữ hoa. Toán hạng tổ hợp có dạng f(t1, t2,..., tn), trong đó n được gọi là arity, f được gọi là functor và t1, t2,..., tn là các toán hạng được gọi là component. Danh sách, được đề cập trong các phần sau, là một cấu trúc đặt biệt có functor là dấu chấm ‘.’. Danh sách [H|T] tương đương với cấu trúc ‘.’[H,T]. Atom đặc biệt ‘[]’ biểu diễn danh sách rỗng. 9
  15. Hướng dẫn sử dụng BProlog Term Atom Integer Number Floating-point Variable Structure Compound Term List Array Hashtable III.5 Các kiểu dữ liệu và các vị từ xây dựng sẵn (built-in) cơ bản trong B- Prolog Các kiểu dữ liệu, đối với B-Prolog được định nghĩa là một tập các giá trị và các vị từ trên các giá trị đó. Các vị từ này không thể được định nghĩa lại. Các vị từ kiểm tra kiểu: • atom(X): trả về đúng nếu toán hạng X là một atom • atomic(X): trả về đúng nếu X là một atom hoặc một number • real(X), float(X): kiểm tra xem X có là một số thực dấu chấm động hay không • var(X): kiểm tra X có là một biến hay không • compound(X): X là một toán hạng tổ hợp. Vị từ này trả về đúng nếu X là một cấu trúc hay là một danh sách Các vị từ hợp nhất (sẽ được trình bày chi tiết về phép hợp nhất ở phần sau): • X = Y: hợp nhất giữa X và Y • X \= Y : 2 toán hạng X và Y không thể hợp nhất Các vị từ so sánh và thao tác trên các toán hạng : • Term1 == Term2: hai toán hạng Term1 và Term2 là đồng nhất (strictly identical) • Term1 \== Term2: hai toán hạng Term1 và Term2 không đồng nhất Các vị từ trên số: • Exp1 is Exp2: đã trình bày ở phần trước • X =:= Y: hai biểu thức số X và Y bằng nhau (numerically) • X =\= Y: hai biểu thức số X và Y khác nhau • X=Y : là các phép toán so sánh giữa các biểu thức số khác Các phép toán số học: • X + Y, X – Y, X * Y, X / Y : các phép toán cộng trừ nhân chia đơn giản • X // Y : phép chia nguyên 10
  16. Hướng dẫn sử dụng BProlog • X mod Y : phép chia dư • X ** Y : phép mũ • abs(X) : trị tuyệt đối của X • sqrt(X) : lấy căn bậc hai của X 11
  17. Hướng dẫn sử dụng BProlog Chương IV. Thực thi chương trình. - Đặt câu hỏi và nhận câu trả lời Đến đây chúng ta đã có thể sử dụng B-Prolog để viết và thực thi các chương trình đơn giản viết bằng ngôn ngữ Prolog.. VD6: Viết chương trình hoàn chỉnh cho VD1. Sử dụng một công cụ soạn thảo văn bản đơn giản (không có định dạng) bất kỳ, nhập vào nội dung chương trình hoàn chỉnh cho VD1 như sau: nguoi(‘Socrates’). chet(X):-nguoi(X). Giả sử chúng ta đặt tên cho chương trình này là vd1.txt và đặt trong thư mục C:\BaitapBP thì để thực thi chương trình, chúng ta sẽ gõ ở [‘C:\BaitapBP\vd1.txt’] tại dấu nhắc của môi trường B-Prolog (xem hình dưới). Sau khi nạp chương trình vào hệ thống B-Prolog, để thực thi chương trình, người sử dụng nhập yêu cầu (goal) của mình cho hệ thống. Câu hỏi chúng ta đặt ra cho hệ thống chỉ được dựa vào các tri thức mà chúng ta đã cung cấp cho hệ thống hoặc các kiến thức có sẵn của hệ thống. Chúng ta đã cung cấp cho hệ thống các khái niệm nguoi và chet, như vậy chúng ta chỉ có thể đặt các câu hỏi liên quan đến hai khái niệm này. Với ví dụ 1 bên trên, chúng ta có thể nhập câu hỏi như sau: nguoi(‘Socrates’) 12
  18. Hướng dẫn sử dụng BProlog Dựa trên tinh thần của của khái niệm, câu phát biểu của chúng ta có nghĩa là "Socrates là người", hệ thống sẽ hiểu rằng chúng ta muốn đặt một câu hỏi nghi vấn "Socrates là người phải không?" Sau khi ấn Enter, chúng ta sẽ thấy hệ thống có ngay câu trả lời: yes. Thay bằng một tên khác, ví dụ: nguoi(‘Xeda’) Hệ thống sẽ trả lời no. Chúng ta thấy các câu trả lời của hệ thống dựa trên kiến thức mà chúng ta đã cung cấp. Dựa vào những gì mà chúng ta đã cung cấp, hệ thống chỉ biết có một người là Socrates, tất cả những symbol khác đều không phải là người. Tuy nhiên, với cơ chế suy luận mà chúng ta cung cấp, hệ thống có thể suy luận ra những điều chưa được cung cấp sẳn. Đây chính là điểm tạo nên sức mạnh lập trình của Prolog. Nhập vào câu hỏi như sau: chet(‘Socrates’) Câu trả lời là: Yes. Với một tên người khác: chet(‘Xeda’) Câu trả lời là: No. Hệ thống đã tự động suy luận theo nguyên lý mà chúng ta muốn nó phải "học": ai là người thì người đó phải chết. Ngoài những câu hỏi dạng Yes/No, Prolog có thể trả lời các câu hỏi yêu cầu tìm đáp số. Chúng ta nhập vào một câu hỏi như sau: chet(X) Đến đây, trong câu hỏi của chúng ta có một biến: X (nhắc lại: mọi danh hiệu mở đầu là ký tự hoa đều là biến). Khi trong câu hỏi của chúng ta chứa một (hoặc nhiều) biến, hệ thống sẽ tìm các giá trị có thể có của biến để cho câu phát biểu của ta là đúng. Hiểu ở mức ý niệm, câu hỏi của chúng ta là: ai là người? Kết quả trả lời của câu hỏi (ai) sẽ được chứa trong biến X. Câu trả lời sẽ là: X = Socrates Tương tự như trên, hệ thống sẽ dựa vào cơ chế suy luận đã được cung cấp để tìm ra lời giải với những câu hỏi dành cho các vị từ có các mệnh đề tương ứng là các luật. Nhập vào câu hỏi như sau: chet(X) Hệ thống sẽ trả lời như sau: X = Socrates. 13
  19. Hướng dẫn sử dụng BProlog VD7: Hoàn chỉnh và thực thi chương trình cho VD2 Chương trình hoàn chỉnh cho ví dụ 2 như sau: giaithua(0,1):-!. giaithua(X,Y):- X1 is X -1, giaithua(X1,Y1), Y is X*Y1. Chúng ta lưu ý là khi kết thúc mỗi mệnh đề đều có ký hiệu '.' và trong mệnh đề đầu tiên có một ký hiệu đặt biệt ‘!’. Đây chính là vị từ nhát cắt và sẽ được trình bày ở phần sau. Sau khi nạp chương trình vào hệ thống, chúng ta có thể đặt cho hệ thống câu hỏi dạng nghi vấn như sau: giaithua(3,6) Hiểu theo ngôn ngữ tự nhiên sẽ là: có phải giai thừa của 3 là 6 hay không? Câu trả lời là: Yes Hoặc chúng ta có thể đặt câu hỏi: giaithua(3,8) Câu trả lời sẽ là: No. Chúng ta sẽ đặt câu hỏi theo dạng tìm lời giải: giaithua(3,X) Câu trả lời sẽ là X = 6 Chúng ta cũng có thể đặt câu hỏi ngược: giaithua(X,6) Ý tưởng của câu hỏi sẽ là: giai thừa của số nào sẽ bằng 6. Tuy nhiên chúng ta không cung cấp cho hệ thống cơ chế suy luận để trả lời câu hỏi này nên hệ thống sẽ báo lỗi. Tất nhiên chúng ta cũng có thể đặt câu hỏi như sau: giaithua(X,Y) Cả hai thông số đều là biến. Như vậy câu hỏi có thể hiểu là: số nào (X) giai thừa thì thành một số khác (Y). Câu hỏi gần như vô nghĩa và những câu trả lời của hệ thống cũng sẽ chẳng mang một ý nghĩa thực sự có nghĩa nào. Tóm tắt: . Chương trình Prolog sẽ hoạt động theo cơ chế tương tác. Người sử dụng sẽ cung cấp yêu cầu và hệ thống sẽ trả lời các yêu cầu này. . Nếu câu hỏi không chứa biến thì hệ thống sẽ kiểm tra phát biểu của chúng ta là đúng hoặc sai, ngược lại, hệ thống sẽ tìm các giá trị của các biến làm cho phát biểu của ta là đúng. 14
  20. Hướng dẫn sử dụng BProlog Chương V. IV. Phép hợp nhất - Cơ chế tìm câu trả lời của Prolog. V.1 Phép hợp nhất Công việc quan trọng nhất của Prolog trong việc tìm câu trả lời là thực hiện việc hợp nhất. Để tiện cho việc theo dõi, phép hợp nhất được ở đây sẽ được biểu diễn bởi dấu =. Nó có hai thành phần, tạm gọi là vế trái vế phải. Phép hợp nhất sẽ trả về kết quả true (thành công) hoặc false (thất bại). Có các trường hợp hợp nhất sau: a) Cả hai vế đều là hằng hoặc biểu thức chứa toàn hằng. Nếu giá trị của hai vế là bằng nhau thì phép hợp nhất thành công (đáp số là true), ngược lại phép hợp nhất sẽ thất bại (kết quả là false) 7=7 true 7=8 false ‘abc’ = ‘abc’ true ‘abcd’ = ‘abc’ false 2 = 1 +1 false 1+1 = 1+1 true Một trong hai vế là hằng hoặc trong biểu thức chứa toàn hằng, vế kia là biến hoặc biểu thức có chứa biến. Trường hợp 1: Nếu tất cả các biến đều có giá trị (gọi là các biến ở tình trạng bound), chúng ta quay về trường hợp a 7=X false nếu X đã có giá trị là 6 7 = X +1 true nếu X đã có giá trị là 6 Y = ‘Socrates’ true nếy Y đã có giá trị là ‘Socrates’ Trường hợp 2: Nếu có biến chưa có giá trị (gọi là biến ở tình trạng unbound), Prolog sẽ gán giá trị cho biến sao cho hai vế có giá trị như nhau và trả về kết quả là true. Nếu không tìm giá trị như vậy, phép hợp nhất sẽ cho kết quả là false. 7=X true nếu X chưa có giá trị, sau phép hợp nhất này, X sẽ có giá trị là 7 -1 = X*X false vì không thể tìm cho X giá trị nào làm cho giá trị hai vế là như nhau. b) Cả hai vế đều là biến hoặc các biểu thức có chứa biến . Trường hợp 1: tất cả các biến đều có chứa giá trị, chúng ta sẽ quay về trường hợp a 15
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2