›
›

Thực hành ngôn ngữ lập trình

pdf 103 trang phuongnguyen 2880
Download
Bạn đang xem 20 trang mẫu của tài liệu "Thực hành ngôn ngữ lập trình", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfthuc_hanh_ngon_ngu_lap_trinh.pdf

Nội dung text: Thực hành ngôn ngữ lập trình

  1. ĐẠI HỌC BÁCH KHOA TPHCM BK 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 ( 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,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
  21. Hướng dẫn sử dụng BProlog X = Y Æ true nếu cả X và Y đều đã có giá trị và những giá trị này bằng nhau X -1 = Y Æ false nếu X và Y đều đã có giá trị và X nhỏ hơn Y . Trường hợp 2: tất cả các biến của một vế đều đã có giá trị, chúng ta sẽ quay về về trường hợp b X = Y Æ true nếu X chưa có giá trị và Y đã có giá trị, sau phép hợp nhất, X sẽ nhận giá trị của Y X - 1 = Y Æ true nếu X chưa có giá trị, Y đã có giá trị. Sau phép hợp nhất, X sẽ có giá trị bằng Y +1 . Trường hợp 3: cả hai vế đều còn chứa biến ở tình trạng unbound Æ hợp nhất vẫn thành công và mỗi khi một biến nào đó trong vế phải hoặc vế trái có giá trị thì biến còn lại cũng sẽ được ràng buộc với giá trị đó X = Y Æ true nếu cả X và Y đều chưa gán giá trị X-1 = Y Æ true nếu cả X và Y đều chưa gán giá trị V.2 Cơ chế tìm câu trả lời của Prolog Nếu chúng ta đặt ra cho Prolog một câu hỏi, Prolog sẽ thực hiện công việc so trùng (match), tức là tìm mệnh đề đầu tiên đề cập đến khái niệm mà chúng ta muốn hỏi. Nói một cách chi tiết hơn, Prolog sẽ dùng phép hợp nhất đã trình bày ở phần trên trong quá trình so trùng cấu trúc dữ liệu một subgoal với một mệnh đề. Trở lại VD6, sau khi đã hoàn tất chương trình, chúng ta đặt ra câu hỏi như sau: nguoi(‘Socrates’) Prolog sẽ tìm mệnh đề đầu tiên có liên quan đến khái niệm nguoi. Hiển nhiên, mệnh đề đầu tiên (và duy nhất) có liên quan đến khái niệm này là: nguoi(‘Socrates’) Như vậy, khi đã có câu hỏi (nguoi(‘Socrates’)) và tìm thấy mệnh đề liên quan (nguoi(‘Socrates’)), Prolog sẽ tiến hành tìm kiếm lời giải, công việc này tiến hành bằng cách tạo mối liên kết giữa các thông số ở phần câu hỏi và các thông số ở phần mệnh đề. Sau khi đã tạo mối quan hệ giữa các thông số ở phần câu hỏi và phần mệnh đề, Prolog sẽ tiến hành các sub-clause (nếu mệnh đề này một luật). Nếu tất cả các sub-clause thành công và các biến ở phần câu hỏi đã ở tình trạng bound (tức là đã có giá trị), Prolog sẽ thông báo lời giải. Nếu là câu hỏi thuộc dạng Yes/No như ví dụ trên, tức là câu hỏi không chứa biến, Prolog sẽ trả lời Yes nếu công việc hợp nhất thành công và các sub-clause đều thành công (nếu mệnh đề so trùng là một luật). Quay trở lại với ví dụ của chúng ta, ở đây thông số của câu hỏi là một hằng (‘Socrates’), và thông số của mệnh đề tương ứng cũng là một hằng (‘Socrates’), hai hằng này hợp nhất thành công, và kết quả trả lời là Yes. 16
  22. Hướng dẫn sử dụng BProlog Nếu chúng ta đặt ra câu hỏi khác: nguoi(‘Xeda’) Prolog cũng chỉ tìm thấy một mệnh đề liên quan đến khai niệm này (nguoi(‘Socrates’)), và vì sự hợp nhất giữa hai hằng ‘Socrates’ và ‘Xeda’ thất bại, đáp số sẽ trả lời là No. Chúng ta xét trường hợp câu hỏi của chúng ta có chứa biến: nguoi(X) Hệ thống sẽ tìm thấy mệnh đề có liên quan đến vấn đề này (nguoi(‘Socrates’)) , và tiến hành hợp nhất giữa X và ‘Socrates’, và vì X chưa có giá trị (unbound) nên phép hợp nhất thành công, X có giá trị là ‘Socrates’. Vì việc hợp nhất giữa các thông số giữa phần câu hỏi và phần clause đã thành công, đây là một sự kiện nên không cần phải thực hiện phần sub-clause, và sau khi hợp nhất, tất cả các biến cần tìm đã có giá trị (ở đây chỉ có một biến là X), nên hệ thống sẽ công bố đã tìm ra lời giải và in ra giá trị của X ( X = ‘Socrates’) Chúng ta xét trường hợp khi ở câu hỏi so trùng với một luật: chet(Y) Chúng ta hoàn toàn có thể đặt câu hỏi là chet(X), nhưng chúng ta sẽ đặt tên biến khác để tiện phân biệt giữa biến trong câu hỏi và thông số cục bộ ở mệnh đề. Thực ra, B-Prolog sẽ tự tạo ra và quản lý các biến của nó trong quá trình đi tìm lời giải cho một goal nào đó. Chúng ta có thể thấy rõ điều này qua quá trình debug (dùng lệnh trace) chương trình. Các biến này được bắt đầu bằng dấu gạch dưới và một dãy 6 số hoặc ký tự tiếp theo. Để hiểu rõ cơ chế tìm câu trả lời của B-Prolog chúng ta có thể chuyển sang chế độ debug khi đặt câu hỏi. Câu hỏi được so trùng với mệnh đề sau: chet(X): - nguoi (X). Vì hai biến X (thông số của mệnh đề) và Y (thông số của câu hỏi) đều chưa chứa giá trị, hệ thống sẽ xem cả hai biến là một, tức là, khi X có được giá trị thì Y cũng có giá trị đó và ngược lại. Do đây là một luật, nên hệ thống sẽ tiến hành thực hiện các sub-clause. Hệ thống sẽ thực hiện sub-clause đầu tiên nguoi(X). Quá trình thực hiện các sub-clause ở vế phải sẽ được thực hiện như sau: • Nếu sub-clause này có thông số là biến unbound, Prolog sẽ tìm giá trị của biến này để sub-clause có giá trị Yes, nếu không tìm được giá trị như vậy, sub- clause sẽ thất bại. • Nếu sub-clause có thông số đều là biến bound (đã có giá trị) hoặc là hằng, Prolog sẽ kiểm tra xem sub-clause có trả về giá trị Yes hay không, nếu không, sub-clause sẽ thất bại. Các sub-clause sẽ được tiến hành từ trái qua phải, và nếu có một sub-clause thất bại, mệnh đề được so trùng sẽ thất bại. 17
  23. Hướng dẫn sử dụng BProlog Trong trường hợp trên, khi tiến hành sub-clause nguoi(X), do biến X là unbound, nên chúng ta rơi vào trường hợp a, hệ thống sẽ tìm giá trị của X cho sub-clause trên là đúng. Cách tìm kiếm câu trả lời cho sub-clause này hòan tòan giống như cách hệ thống tìm câu trả lời khi chúng ta đặt câu hỏi này trong phần câu hỏi, và như vậy X sẽ có giá trị là ‘Socrates’ sau khi sub-clause này thực hiện xong. Do X và Y được xem như một, nên khi X có giá trị là ‘Socrates’ thì Y cũng có giá trị này. Do tất cả các sub-clause đã thực hiện xong, và Y đã có giá trị, nên Prolog công bố là đã tìm ra lời giải và in ra giá trị của Y. Tóm tắt: . Phép hợp nhất là nền tảng của mọi hoạt động của Prolog để tìm ra lời giải . Để trả lời câu hỏi, Prolog so trùng câu hỏi với mệnh đề và tạo mối liên quan giữa các thông số. . Prolog tìm ra lời giải khi thực hiện thành công một mệnh đề và tất cả các biến nếu có trong các thông số của câu hỏi đều đã có giá trị 18
  24. Hướng dẫn sử dụng BProlog Chương VI. Sự quay lui - Khống chế số lượng lời giải -Vị từ nhát cắt và fail VI.1 Sự quay lui (back-tracing) trên Prolog Hợp nhất là hòn đá nền tảng cho cơ chế suy luận của Prolog. Tuy nhiên, để tìm ra lời giải đúng, Prolog cần phải sử dụng cơ chế quay lui, khi giá trị đầu tiên được gán cho thông số không phải là lời giải. Chúng ta xét ví dụ sau: VD9: nguoi(‘Socrates’). nguoi(‘Xeda’). vua(‘Xeda’). sungsuong(X) :- nguoi(X), vua(X). Như vậy trong ví dụ này, ngoài khái niệm về người, chúng ta đưa ra khái niệm về vua và sự sung sướng. Diễn giải những thông tin trong các dữ kiện trên thành ngôn ngữ tự nhiên, chúng ta có được các điều sau: "Thế giới mà chúng ta sống có hai người là Socrates và Xeda. Chúng ta có một vua la Xeda, và một thực thể nào đó chỉ sung sướng nếu thực thể đó vừa người vừa là vua." Lưu ý rằng trong ví dụ trên, các mệnh đề liên quan đến cùng một vị từ phải viết liên tiếp nhau. Xét khi hệ thống trả lời câu hỏi sau: sungsuong(X) Trước tiên hệ thống sẽ so trùng câu hỏi trên với mệnh đề sungsuong(X) :- nguoi(X),vua(X). Lưu ý rằng vào lúc này chúng ta có hai biến X: một biến X là thông số của câu hỏi và một biến X là thông số của mệnh đề. Về nguyên tắc, hai biến X này hòan tòan khác nhau. Tuy nhiên, khi so trùng câu hỏi với mệnh đề, do cả hai biến X lúc này đều chưa chứa giá trị, nên chúng sẽ được xem như một. Nhưng cần chú ý rằng biến X sử dụng trong các sub- clause là biến X thông số của mệnh đề. Sau đó Prolog sẽ tiến hành các sub-clause. Ở sub-clause đầu tiên, nguoi(X), tương tự như VD6, Prolog sẽ tìm được câu trả lời là X = Socrates. Khi thực hiện sub-clause thứ hai, vua(X), do X đã có giá trị (Socrates), Prolog sẽ kiểm tra xem giá trị này có làm giá trị của mệnh đề là true hay không. Như các ví dụ trên, việc tiến hành trả lời một sub-clause cũng tương tự như khi trả lời một câu hỏi, Prolog lại so trùng sub-clause với một mệnh đề cùng tên. Prolog tìm thấy một mệnh 19
  25. Hướng dẫn sử dụng BProlog đề liên quan đến vua là vua(‘Xeda’) và tiến hành hợp nhất giữa X và Xeda. Do X đã có giá trị là Socrates, việc hợp nhất thất bại. Tuy nhiên khi sub-clause này thất bại, không có nghĩa rằng Prolog sẽ vội kết luận rằng mệnh đề này thất bại. Ở đây công việc tìm kiếm câu trả lời thất bại sau khi biến X được gán giá trị và chuyển từ trạng thái bound sang unbound. Hệ thống sẽ quay lại thời điểm biến X được gán giá trị (khi trả lời sub-clause nguoi(X)), X được chuyển lại sang tình trạng unbound, và cố gắng tìm kiếm một giá trị khác của X để cho mệnh đề con này vẩn đúng. Công việc này được gọi là back-tracing. Do việc so trùng sub-clause này với mệnh đề nguoi(‘Socrates’) thất bại, hệ thống sẽ so trùng với mệnh đề khác. Nếu không còn mệnh đề nào khác liên quan đến sub-clause, việc thực hiện mệnh đề mới thật sự thất bại, tuy nhiên ở đây hệ thống tìm thấy một mệnh đề khác liên quan đến khái niệm này là nguoi(‘Xeda’). Việc hợp nhất giữa X và ‘Xeda’ lại được thực hiện, X sẽ có giá trị là Xeda và sau đó, khi lại tiếp tục thực hiện sub-clause vua(X) thì chúng ta sẽ dễ dàng thấy rằng sub-clause lần này được thực hiện thành công. Prolog đã tìm ra lời giải, tuy nhiên, ở trường hợp này, ngoài sự hợp nhất, Prolog còn sử dụng thêm một "vũ khí" mới, đó là sự quay lui. VI.2 Khống chế số lượng lời giải Để khống chế số lượng lời giải theo ý mình, chúng ta sử dụng hai vị từ đặc biệt là nhát cắt (cut) và findall, như các ví dụ sau: VD10: P(X) :-Q(X). P(3). Q(1). Q(2). Với ví dụ này, khi chúng ta đặt câu hỏi P(X) cho hệ thống thì chúng ta sẽ có được tổng cộng 3 kết quả. Ngược lại nếu chúng ta thêm một vị từ nhát cắt (!) sau vị từ Q(X) ở mệnh đề đầu tiên của ví dụ trên (P(X) :- Q(X), !.) thì chúng ta sẽ chỉ có một kết quả cho dù chúng ta có dùng dấu ‘;’ để yêu cầu B-Prolog cung cấp thêm lời giải khác. Vị từ nhát cắt được viết là !, được viết ở thân của một mệnh đề sẽ loại bỏ tất cả các khả năng lựa chọn có thể của các vị từ đứng trước (bên trái) nó trong mệnh đề. VD11: sử dụng vị từ findall để tìm tất cả các lời giải ?-findall(X, member(X,[(1,a),(2,b),(3,c)]), Xs) Xs = [(1,a),(2,b),(3,c)] Trong ví dụ trên, vị từ member là một vị từ được xây dựng sẵn (built-in) trong B-Prolog. Vị từ này có hai đối số, dùng để kiểm tra xem đối số thứ nhất có phải là phần tử của đối số thứ hai hay không. 20
  26. Hướng dẫn sử dụng BProlog Vị từ findall(Term,Goal,List) là một vị từ đặc biệt. Vị từ này thực hiện thành công nếu List chứa các giá trị của Term mà các giá trị này làm cho Goal thành công. Các vị từ tương tự với vị từ này có thể kể đến là vị từ bagof và vị từ setof. 21
  27. Hướng dẫn sử dụng BProlog Chương VII. Lập trình đệ quy với Prolog Chúng ta nhớ lại rằng với VD2, chúng ta đã cố gắng né tránh cách đặt vấn đề để giải bài toán giai thừa theo cách nhân dồn các số từ 1 đến số cần tính giá trị giai thừa. Điều này sẽ dẩn đến một điểm yếu của Prolog: không cung cấp các cấu trúc điều khiển cần thiết, dẩn đến việc khó khăn khi thực hiện phép lặp. Tuy nhiên ví dụ này cũng cho thấy một kỹ thuật lập trình tạo nên sức mạnh chủ yếu của Prolog: lập trình đệ quy. Kỹ thuật này cũng phù hợp với suy nghĩ của con người khi tiếp cận giải quyết vấn đề và khiến cho việc lập trình trên Prolog có một sự uyển chuyển và nhẹ nhàng trong việc viết mã. Tuy vậy, nó tạo ra một sự khó khăn với những người quen lập trình thủ tục. Chúng ta sẽ xem xét lại từng bước trong việc gọi đệ quy để tìm ra lời giải. VD13: Xét từng bước quá trình gọi đệ quy và hợp nhất của VD7 với goal là giaithua(2,X) Nhắc lại, chúng ta đã có đoạn chương trình như sau: giaithua(0,1):-!. giaithua(X,Y):- X1 is X -1, giaithua(X1,Y1), Y is X*Y1. Ở đây có một sự thay đổi nhỏ: chúng ta đặt nhát cắt để chuyển sự kiện đầu thành luật. Chúng ta muốn khẳng định: nếu số cần tìm giai thừa là 0 thì giai thừa của nó là 1, và kết quả này là duy nhất, không cần phải tiếp tục tìm các trường hợp khác. Ngoài ra, chúng ta cũng cần lưu ý thêm là vị từ “is” khác với phép hợp nhất “=” như trong ví dụ sau: .Với biến Y có giá trị là 1 thì trong mệnh đề “X is Y + 1” thì X có giá trị là 2 còn trong mệnh đề “X = Y + 1” thì X có giá trị là 1 + 1. Với goal là giaithua(2,X), hệ thống sẽ so trùng với mệnh đề giaithua(0,1) là mệnh đề đầu tiên tìm thấy có liên quan đến khái niệm giaithua. Hệ thống sẽ hợp nhất các thông số theo thứ tự, 2 hợp nhất với 0 và X hợp nhất với 1. Công việc hợp nhất X với 1 thành công, X có giá trị là 1, nhưng 2 hợp nhất với 0 thất bại. Hệ thống sẽ tiếp tục tìm kiếm lời giải khác bằng cách so trùng với mệnh đề khác. Lần này hệ thống so trùng goal với mệnh đề giaithua(X,Y). Khi tạo mối liên quan giữa các thông số, hệ thống hợp nhất 2 với X của mệnh đề và Y với X của goal. Chúng ta sẽ ký hiệu XG là X thông số của goal. Do Y và XG đều chưa có giá trị, Prolog sẽ xem hai biến này là một. Sau đó hệ thống bắt đầu thực hiện từng sub-clause: . X1 is X -1 X1 là biến mới, và chưa có giá trị. X đã có giá trị là 2, nên X - 1 có giá trị là 1. Hợp nhất X1 với 1 ta sẽ có giá trị của X1 là 1. . giaithua(X1,Y1) Ở đây mệnh đề giai thừa được gọi đệ quy. Lưu ý lúc này X1 đã có giá trị là 1, Y1 là biến mới chưa có giá trị, vì vậy nhiệm vụ của hệ thống là tìm giá trị của Y1 sao cho sub-clause 22
  28. Hướng dẫn sử dụng BProlog giaithua(X1,Y1) cho giá trị là đúng. Và cũng như các ví dụ trên, cách thức Prolog trả lời một sub-clause cũng tương tự như khi trả lời câu hỏi từ goal, tức là lại so trùng câu hỏi với các mệnh đề đã biết • So trùng với giaithua(0,1), Prolog tiến hành hợp nhất X1 với 0, Y1 với 1, do X1 đã có giá trị là 1, việc hợp nhất với 0 thất bại, Prolog phải so trùng với mệnh đề khác. • So trùng với giaithua(X,Y), Prolog tiến hành hợp nhất X1 với X đồng nhất Y1 với Y. Chúng ta ký hiệu X và Y ở lần gọi đệ quy này là X2 và Y2, và sử dụng cách ký hiệu tương tự như vậy cho các biến còn lại ở lần gọi đệ quy này cũng như các lần gọi đệ quy tiếp theo. Như vậy X2 sẽ có giá trị là 1 và Y1 sẽ có giá trị mà Y2 sẽ có. Tương tự ở lần gọi thứ nhất, các sub-clause của mệnh đề trên ở lần gọi thứ hai này sẽ lần lượt được gọi: - X12 is X2 - 1, hợp nhất X12 với X2 -1, ta có X12 có giá trị là 0. - giaithua(X12,Y12), X12 đã có giá trị là 0, Prolog sẽ tìm giá trị của Y12 bằng việc tiếp tục so trùng giaithua(X12,Y12) với các mệnh đề có liên quan: . So trùng giaithua(X12,Y12) với giaithua(0,1). Do X12 đã có giá trị là 0, Prolog tiến hành hợp nhất X12 với 0 và Y12 với 1. Thực hiện tiếp sub- clause !, do câu hỏi giaithua(X12,Y12) chưa tìm được câu trả lời nào, nên sub-clause này trả lời là đúng. Việc thực hiện mệnh đề giaithua(0,1) thành công, và Y12 đã có giá trị là 1 nên câu hỏi giaithua(X12,Y12) đã có đáp số. Vị từ ! sẽ ngăn chặn việc tìm các đáp số khác, vì vậy trong trường hợp này, Prolog không tiếp tục so trùng tiếp với mệnh đề giaithua(X,Y). - Y2 = X2 * Y12, lúc này Y2 chưa có giá trị, X2 và Y12 đã có giá trị là 1 và 1 nên Prolog sẽ hợp nhất Y2 và 1. Kết quả sẽ là Y2 có giá trị là 1. Như vậy đến đây các sub-clause của mệnh đề giaithua(X2,Y2) đã thực thi thành công, và Y2 đã có giá trị là 1, và vì Y1 được đồng nhất với Y2, nên Y1 cũng sẽ có giá trị la 1 . Y = X* Y1, lúc này Y chưa có giá trị, X và Y1 đã lần lượt có giá trị là 2 và 1, nên Prolog hợp nhất Y và 2*1, kết quả Y sẽ có giá trị là 2. Như vậy đến đây các sub-clause của mệnh đề giaithua(X,Y) đã thực thi thành công, và Y đã có giá trị là 2, và vì XG được đồng nhất với Y, nên XG cũng sẽ có giá trị là 2, và lời giải của bài toán đã được tìm thấy. Tóm tắt: . Đệ quy là sức mạnh lập trình chủ yếu trên Prolog . Mỗi lần gọi đệ quy, các thông số và biến cục bộ trong mỗi mệnh đề sẽ được tạo mới tương ứng với lần gọi đệ quy dó. . Có thể dùng nhát cắt để ngăn chặn các lần gọi đệ quy thừa khi đã tìm ra đáp số 23
  29. Hướng dẫn sử dụng BProlog Chương VIII. Danh sách trên Prolog Danh sách là kiểu dữ liệu cấu trúc đặc biệt trên Prolog. Có thể hiểu danh sách như một kiểu dãy một chiều, và phần tử của danh sách có thể thuộc về kiểu dữ liệu bất kỳ, tuy nhiên các phần tử trong cùng một danh sách phải cùng kiểu. VIII.1 Cấu trúc của danh sách Một danh sách trên Prolog bao gồm hai phần: phần đầu (head) là phần tử đầu tiên của danh sách và phần đuôi (tail) là danh sách các phần tử còn lại của danh sách. Một danh sách có thể mô tả theo hai cách: i. Liệt kê các phần tử của danh sách, ví dụ: [1,2,3,4,5] ii. Mô tả phần đầu và phần đuôi của danh sách, ngăn cách bởi dấu |, ví dụ [1|[2,3,4,5]] VD15: Mô tả một danh sách bao gồm 5 số nguyên là 1,2,3,4,5 Danh sách trên có thể mô tả theo các cách sau: [1,2,3,4,5] [1|[2,3,4,5]] [1|[2|[3,4,5]]] [1|[2|[3|[4,5]]]] [1|[2|[3|[4|[5]]]]] [1|[2|[3|[4|[5|[]]]]]] Lưu ý: danh sách rỗng có thể được mô tả như sau: [] VD16: Viết chương trình in ra phần đầu và phần đuôi của một danh sách. Chương trình này thực chất chỉ giúp chúng ta nhìn rõ hơn khái niệm về danh sách. Chương trình được viết như sau: indanhsach(L,H,T):- L = [H|T]. Xét khi chúng ta nhập goal vào như sau: indanhsach([1,2,3,4,5],X,Y) Prolog sẽ so trùng goal với mệnh đề indanhsach(L,H,T), L được hợp nhất với [1,2,3,4,5], X được đồng nhất với H, Y được đồng nhất với T. Khi thực hiện sub-clause L = [H|T], L được hợp nhất với [H|T], như vậy phần đầu của L sẽ hợp nhất với H, phần đuôi sẽ hợp nhất với T. Do L đã có giá trị là [1,2,3,4,5], phần đầu của L sẽ có giá trị là 1, phần đuôi sẽ có giá trị là [2,3,4,5], vậy sau khi hợp nhất, H sẽ có giá trị là 1 và L sẽ có giá trị là [2,3,4,5]. Cũng tức là X sẽ có giá trị là 1 và Y có giá trị là [2,3,4,5]. Prolog đã tìm thấy lời giải và sẽ in ra lời giải này. 24
  30. Hướng dẫn sử dụng BProlog Lưu ý: • Chương trình trên sẽ chạy sai nếu danh sách nhập vào là rỗng ([]) do lời giải của chúng ta chưa xử lý trường hợp này • Phần mệnh đề cho vị từ indanhsach có thể viết lại là indanhsach([H|T],H,T). Tóm tắt . Danh sách là kiểu dữ liệu cấu trúc đặc biệt do người dùng định nghĩa trên Prolog . Một danh sách bao gồm hai phần: phần đầu là phần tử đầu, phần đuôi là danh sách các phần tử còn lại của danh sách. . Trong trường hợp danh sách rỗng, phần đầu của danh sách sẽ không có. 25
  31. Hướng dẫn sử dụng BProlog Chương IX. Lập trình đệ quy với danh sách trên Prolog Khi xử lý danh sách trên Prolog, người lập trình phải từ bỏ phong cách dùng vòng lặp để xử lý dãy mà phải tận dụng kỹ thuật đệ quy để tìm ra lời giải. Chúng ta xét một số ví dụ sau đây: VD17: Viết vị từ đếm xem một danh sách có bao nhiêu phần tử. Đầu tiên chúng ta phải định nghĩa được công việc mà chúng ta định làm. Chúng ta sẽ viết một vị từ như sau: dem(list,integer) Chúng ta đếm trong một danh sách có bao nhiêu phần tử. Ví dụ khi gọi goal dem([1,2,3,4],X), đáp số sẽ là X = 4 Tiếp theo chúng ta phải xác định một thuật giải phù hợp với tinh thần của Prolog. Không thể dùng vòng lặp, chúng ta phải xây dựng một giải thuật đệ quy. Một giải thuật đệ quy sẽ bao gồm hai phần: điều kiện dừng và lời gọi đệ quy. Điều kiện dừng cho bài toán này rất dễ dàng: khi danh sách không có phần tử nào, thì hiển nhiên số phần tử của nó là 0. Vậy điều kiện dừng sẽ được viết như sau: dem([],0):-!. Khi trường hợp danh sách không có phần tử nào, đáp số 0 là duy nhất, vậy chúng ta có thể dùng nhát cắt để yêu cầu Prolog không tìm thêm lời giải nào khác. Phần đệ quy hơi khó đối với những ai chưa quen với danh sách trên Prolog. Prolog chỉ cung cấp cho chúng ta cơ chế chia danh sách thành hai phần: phần tử đầu và phần đuôi danh sách các phần tử còn lại. Như vậy lời giải gần như đã tự nó hiện ra: chúng ta sẽ gọi đệ quy để đếm phần đuôi có bao nhiêu phần tử rồi cộng nó với 1 (phần tử đầu) sẽ ra số phần tử trong một danh sách. Phần này sẽ được viết như sau: dem([H|T],X):- dem(T,X1), X is X1+1. Tư tưởng đệ quy đã được thể hiện rất rõ ràng: đếm phần đuôi T của danh sách để có được tổng X1, hợp nhất X với X1+1 sẽ cho đáp số cần tìm. Tuy nhiên chúng ta thấy ở đây biến H hòan tòan không cần dùng trong vế phải của mệnh đề. Prolog không coi đây là lỗi, nhưng sẽ "phàn nàn" về việc này. Xét về hiệu quả lập trình, hòan tòan không cần khai báo tên biến mới cho thành phần H trong trường hợp này. Có một nguyên tắc để nhận ra những biến "vô dụng" như vậy: đó là những biến chỉ xuất hiện 1 lần trong suốt mệnh đề. Đối với trường hợp này, ta nên dùng ký hiệu '_' thay cho tên biến để biểu diễn biến này không cần dùng trong thuật giải. 26
  32. Hướng dẫn sử dụng BProlog Vậy phần đệ quy sẽ được "tinh chế" như sau: dem([_|T],X):- dem(T,X1), X is X1+1. Như vậy toàn bộ chương trình hoàn chỉnh sẽ như sau: dem([],0):-!. dem([_|T],X):- dem(T,X1), X is X1+1. VD18: Viết vị từ tính tổng các phần tử trong một danh sách tong([],0):-!. tong([H|T],X):- tong(T,X1), X is X1+H. Tư duy đệ quy ở đây là: chúng ta tính tổng phần đuôi của danh sách, rồi cộng nó với phần tử đầu để tính tổng danh sách. VD19: Viết vị từ kiểm tra một số nguyên có nằm trong danh sách hay không (thực ra đây chính là vị từ member đã có sẵn của B-Prolog). Xác định vấn đề: chúng ta sẽ viết vị từ ptu(integer,list), khi gọi ptu(2,[1,3,5]) kết quả sẽ là No, ngược lại khi gọi ptu(3,[1,3,5]), kết quả sẽ là Yes. Ở đây chúng ta phải xác định được các trường hợp một phần tử nằm trong một danh sách. Và chúng ta phải trình bày được các khái niệm này một cách đệ quy. Sau đây là ý tưởng của thuật giải: có hai trường hợp để một số nguyên là phần tử của một danh sách: số nguyên này là phần tử đầu của danh sách hoặc nó là phần tử của phần đuôi danh sách. Sau khi xác định được ý tưởng, chúng ta có bài giải như sau: ptu(H,[H|_]):-!. ptu(H,[_|T]):- ptu(H,T). Lưu ý: i./Chúng ta đã thay thế các biến chỉ xuất hiện một lần trong một mệnh đề bằng ký hiệu '_' như đã nói ii./ Ở mệnh đề đầu đã có ký hiệu nhát cắt, nên nếu mệnh đề này đúng, bài toán đã có lời giải và không so trùng đến mệnh đề thứ hai. Như vậy mệnh đề thứ hai chỉ được so trùng khi mệnh đề thứ nhất thấy bại, và vì mệnh đề thứ nhất ứng với trường hợp số nguyên cần tìm bằng với phần tử đầu của danh sách, nên khi mệnh đề thứ nhất thất bại, tức là số nguyên cần tìm không bằng với phần tử đầu của danh sách, nên trong mệnh đề thứ hai, chúng ta không cần quan tâm đến phần tử đầu của danh sách. VD20: Xác định phần tử thứ n của danh sách Khi ta gọi ptn([1,3,5,7,9],2,X) -Æ X = 3 (phần tử thứ 2 của danh sách). Vì Prolog chỉ cho chúng ta truy xuất phần tử đầu tiên của danh sách, nên chúng ta phải xây dựng thuật giải đệ quy dựa trên cơ sở này: nếu n bằng 1 thì phần tử cần tìm là phần tử đầu của danh sách, ngược lại thì đó sẽ là phần tử thứ n -1 của phần đuôi danh sách. ptn([H|_],1,H):-!. 27
  33. Hướng dẫn sử dụng BProlog ptn([_|T],N,X):- N1 is N - 1, ptn(T,N1,X). VD 21: Tạo ra một danh sách bao gồm chỉ các phần tử lẻ của danh sách ban đầu. Goal khi gọi sẽ có dạng ptle([1,2,3,4,5,6],L) Æ L = [1,3,5] Điều kiện dừng của bài toán rất đơn giản: khi danh sách là rỗng thì danh sách được tạo ra cũng là rỗng. Và phần đệ quy của bài toán phải dựa trên việc truy xuất từ phần tử đầu tiên của danh sách và gọi đệ quy cho phần đuôi. Chúng ta phải xét các trường hợp khác nhau của phần tử đầu. ptle([],[]):-!. ptle([H|T],[H|T1]):- H mod 2 =:= 1, ptle(T,T1),!. ptle([_|T],T1):- ptle(T,T1). Ở đây chúng ta lưu ý đến mệnh đề thứ ba: do hai mệnh đề trên đều có nhát cắt, nên mệnh đề thứ ba chỉ được so trùng khi hai mệnh đề trên đều sai. Mệnh đề thứ hai đã xét trường hợp khi H lẻ, vì vậy ở mệnh đề thứ ba chắc chắn H không phải là số lẻ, và vì vậy không cần phải xét đến Tóm tắt: . Đệ quy là công cụ chủ yếu để xử lý danh sách trên Prolog . Việc gọi đệ quy trên danh sách thường dựa trên cơ sở chia danh sách thành phần đầu và phần đuôi. . Sử dụng vị từ nhát cắt hợp lý sẽ khiến các mệnh đề trở nên gọn nhẹ và logic hơn. 28
  34. Hướng dẫn sử dụng BProlog Chương X. Danh sách hai chiều Danh sách hai chiều là một trường hợp đặc biệt của danh sách. Phần tử của danh sách lúc này cũng là một danh sách. Việc lập trình với danh sách hai hay nhiều chiều, về cơ bản, hòan tòan không khác với việc lập trình danh sách một chiều, tức cũng sử dụng các giải thuật xử lý danh sách bình thường. Tuy nhiên chúng ta cần chú ý rằng phần tử của danh sách này cũng là một danh sách. VD23: Viết chương trình đếm trên một danh sách hai chiều của các số nguyên L có bao nhiêu phần tử con có tổng các phần tử là số chẳn. Với bài toán này, chúng ta phải viết thêm một vị từ phụ để có được lời giải tong([],0):-!. tong([H|T],X):-tong(T,X1), X is H+X1. dem([],0):-!. dem([H|T],X):-tong(H,N), N mod 2 =:= 0, dem(T,X1), X is X1 + 1,!. dem([_|T],X):- dem(T1,X). Tóm tắt . Danh sách nhiều chiều là một danh sách trong đó các phần tử cũng là danh sách . Về mặt tư duy, lập trình để xử lý trên danh sách nhiều chiều không khác nhiều với xử lý danh sách một chiều . Các phần tử của danh sách nhiều chiều cũng là danh sách, nên có thể áp dụng các giải thuật xử lý danh sách để xử lý các phần tử này. 29
  35. PHẦN II. LISP
  36. Hướng dẫn sử dụng Lisp Chương I. Giới thiệu I.1 Lịch sử phát triển LISP là ngôn ngữ lập trình có tên lấy từ List Processing nghĩa là xử lý trên danh sách. Vào mùa hè năm 1956, Allen Newell, J.C. Shaw, và Herbert Simon đã phát triển Lisp (Lisp processing) và tạo nên ngôn ngữ xử lý thông tin IPL (Information Processing Language) – ngôn ngữ trừu tượng thao tác trên ký hiệu và danh sách. Khi FORTRAN được xây dựng, McCarthy thiết kế một ngôn ngữ mới – LISP (Lisp Processor), lấy từ ý tưởng của IPL, FORTRAN và FLPL chạy trên IBM704. Vào thập niên 70, Guy Steele và Gerald Sussman định ra Scheme, kết hợp Algol và Lisp. Vào đầu thập niên 80, có khoảng 12 hệ Lisp khác nhau. Các hệ Lisp này không tương thích nhau. Do đó, một dự án nhằm định ra một ngôn ngữ Lisp chung nhất đã hình thành – dự án này sẽ kết hợp những đặc tính tốt nhất của các hệ Lisp thời đó vào một thể thống nhất. Điều đó đã dẫn đến sự ra đời phiên bản đầu tiên của Common Lisp chuẩn năm 1984 – kết hợp nhiều ý tưởng của ngôn ngữ lập trình như thông dịch và biên dịch hàm, dọn rác (garbage collection), gọi hàm đệ quy, theo vết và dò lỗi (tracing and debugging) và trình soạn thảo theo cú pháp. I.2 Đặc điểm của gcLisp 1. Các đặc điểm của ngôn ngữ Từ khi được John McCarthy (MIT) nghĩ ra năm 1958, LISP được tinh chế dần đến version 1.5 và được sử sụng lâu dài về sau Lisp là ngôn ngữ hướng chức năng (functional language hay applicative), dùng lối ký hiệu tiền tố (prefix) và dấu ngoặc đơn: f(x,y, z) được ký hiệu là (f x y z) Tương tự x+y ký hiệu là (+ x y) ⎛ π ⎞ Bt. sin⎜3x + ⎟ viết trong Lisp như thế nào ? (sin (+ (* 3 x) (/ pi 2))) ⎝ 2 ⎠ Lisp là ngôn ngữ thông dịch (interpreted language) (xem Error! Reference source not found.) Ngôn ngữ biên dịch Ngôn ngữ thông dịch câu lệnh (instructions) Biểu thức biên dịch đánh giá trả lời chương trình thực thi Kết quả thực thi kết quả vòng lặp top-level Ví dụ: 31
  37. Hướng dẫn sử dụng Lisp * (+ 3 4) 7 * (+ (* 3 4)(- 5 2)) 15 *4 4 2. Kiểu dữ liệu Lisp thao tác trên các loại dữ liệu: ¾ Biểu thức expression::= atom | list ¾ Danh sách list::= (expression1 expressionn) Danh sách là một chuỗi các biểu thức ngăn cách nhau bởi khoảng trắng, tất cả đặt trong dấu ngoặc đơn ¾ Atoms atom::= số | chuỗi ký tự | ký hiệu ¾ Ký hiệu (~ identifier): từ tạo bởi các ký tự bất kỳ, ngoại trừ ( ) ‘ ` “ ; và khoảng trắng ¾ Boolean: Lisp không có kiểu boolean. Trong Lisp, nil mang giá trị logic sai và tất cả các biểu thức khác có giá trị đúng. Ký hiệu t dùng để chỉ trị logic đúng theo mặc định. Các kiểu dữ liệu được xếp theo cấp bậc như sau: expression list atom symbol number list nil interger real Biến trong Lisp không có kiểu dữ liệu , cùng một biến có thể có nhiều kiểu dữ liệu khác nhau. Ví dụ: * (setq a ‘(1 2 3)) (1 2 3) * a (1 2 3) * (setq a 2) 2 * a 2 32
  38. Hướng dẫn sử dụng Lisp Chương II. Lập trình với gcLisp Bây giờ chúng ta sẽ cùng bắt đầu với LISP. Chương này sẽ giới thiệu một số hàm cơ bản nhằm thao tác trên ký hiệu trong LISP. Đầu tiên là các hàm về số, sau đó là các hàm trên danh sách. Phần này cũng sẽ giới thiệu một số thuật ngữ khi làm việc với LISP, chẳng hạn như dấu nhắc, chú thích, hàm, đối số, chương trình, giải thuật, atom, số, ký hiệu, danh sách, các phần tử trong danh sách, biểu thức, kiểu dữ liệu, dạng, đánh giá. II.1 Các khái niệm cơ bản 1. Bắt đầu với LISP Đối với phần lớn ngôn ngữ lập trình, cách tốt nhất để học là bắt đầu với một chương trình đơn giản. Trong phần này, chúng ta sẽ làm quen với một số khái niệm cơ bản trong LISP. Để bắt đầu, chúng ta tưởng tượng ta đang ngồi trước màn hình vi tính. Khi LISP không thực hiện một thao tác gì, nó ở trạng thái tĩnh. Khi đó, LISP hiển thị dấu nhắc cho biết nó đang đợi chúng ta gõ lệnh vào. Trong phần lớn các hệ COMMON LISP hiện nay, dấu nhắc chương trình là dấu sao. * Những từ đi sau dấu chấm phẩy là ghi chú chèn vào chương trình. Tất cả những từ còn lại sau dấu ; trong cùng dòng sẽ không được LISP xử lý. Chúng ta khởi đầu với một ví dụ đơn giản minh họa khả năng của LISP về xử lý số học * (+ 3.14 2.71) 5.85 Giả sử chúng ta muốn lưu trữ một số thông tin cần thiết của một người. Ví dụ, chúng ta muốn ghi nhớ danh sách bạn bè, kẻ thù, của một người nào đó. Chúng ta dùng SETF (viết tắt của set field). * (setf friends ‘(dick jane sally)) (DICK JANE SALLY) * friends (DICK JANE SALLY) * (setf enemies ‘(troll grinch ghost)) (TROLL GRINCH GHOST) * enemies (TROLL GRINCH GHOST) Hai danh sách trên là những thông tin động và có thể thay đổi. Ví dụ như ghost không còn là kẻ thù mà trở thành bạn bè. Khi đó cần cập nhật lại hai danh sách. * (setf enemies (remove ‘ghost enemies)) (TROLL GRINCH) * (setf friends (cons ‘ghost friends)) (GHOST DICK JANE SALLY) * enemies 33
  39. Hướng dẫn sử dụng Lisp (TROLL GRINCH) * friends (GHOST DICK JANE SALLY) Bây giờ chúng ta sẽ xem làm thế nào định nghĩa một hàm làm công việc tương tự. Ta định nghĩa hàm tên NEWFRIEND thực hiện công việc đổi một người từ kẻ thù thành bạn bè. (defun newfriend (name) (setf enemies (remove name enemies)) (setf friends (cons name friends)) ) Với hàm NEWFRIEND, việc đổi tình trạng của GHOST từ kẻ thù thành bạn bè có thể thực hiện bằng một dòng lệnh đơn giản. * (newfriend ‘ghost) 2. Hàm và dữ liệu trong LISP Lisp là ngôn ngữ đặc trưng cho việc xử lý danh sách Chương trình được biểu diễn bằng các danh sách và có thể thao tác trên đó như dữ liệu (+ (* 3 4) (- 5 2)) chương trình: hàm + áp dụng vào hai đối số dữ liệu: danh sách gồm ba thành phần Ở top-level, khi đóng vai trò là đối số của một hàm, một danh sách luôn được xem như là sự áp dụng một hàm. 3. Đánh giá ‘Exp là cách viết tắt của (quote Exp) *‘a A *‘‘a (QUOTE A) QUOTE không đánh giá đối số Ngược lại với quote là hàm eval đánh giá giá trị của đối số * (setq l ‘(a b c)) (A B C) * (eval (list ‘car ‘l)) A * (eval (list ‘* (1+ 3) 2)) 6 Giá trị của (eval ‘Exp) là Exp II.2 Các hàm xử lý trên danh sách 1. FIRST và REST – CAR và CDR ¾ FIRST trả về phần tử đầu tiên của danh sách 34
  40. Hướng dẫn sử dụng Lisp ¾ REST trả về danh sách theo sau phần tử đầu tiên Cho đến gần đây, phần lớn lập trình viên LISP vẫn dùng CAR và CDR thay cho FIRST và REST. Ngoài chức năng tương tự, CAR và CDR có thể kết hợp với nhau.thành dạng phức hợp CxxR, CxxxR hay CxxxxR. Mỗi x tượng trưng cho A – CAR hay D – CDR. Quy ước: * (car nil) NIL * (cdr nil) NIL Bài tập: 1. Lấy phần tử thứ ba của danh sách (car (cdr (cdr l))) có thể viết: (caddr l) CAR và CDR có thể kết hợp với nhau đến mức độ 4 Ví dụ: (caadr l) = (car (car (cdr l))) (cadar l) = (car (cdr (car l))) 2. Làm thế nào trích ra chuỗi example trong danh sách: L=((this) is (an (example)) more complex) L=((this) is (an (example)) more complex) (cdr l) = (is (an (example)) more complex) (cdr (cdr l)) = ((an (example)) more complex) (car (cdr (cdr l))) = (an (example)) (cdr (car (cdr (cdr l)))) = ((example)) (car (cdr (car (cdr (cdr l))))) = (example) (car (car (cdr (car (cdr (cdr l)))))) = example 2. CONS, APPEND, LIST ¾ LIST trả về danh sách các đối số * (list ‘a (+ 3 1) ‘c) (a 4 c) * (list ‘(a b) ‘(c d)) ((a b) (c d)) * (list ‘a nil) (a nil) ¾ CONS thêm một phần tử vào đầu danh sách (cons ‘a ‘(2 3)) (a 2 3) (cons `(a b) ‘(c d)) ((ab) c d) (list `a nil) 35
  41. Hướng dẫn sử dụng Lisp (a) (CAR (CONS a l)) = a (CDR (CONS a l)) = l Bt. Cho biết giá trị của các biểu thức sau: 1. (cons ‘a (cons ‘b (cons ‘c nil))) (cons ‘a (cons ‘b (cons ‘c nil))) = (cons ‘a (cons ‘b ‘(c))) = (cons ‘a ‘(b c)) = (a b c) 2. (list (car ‘(car ((1) (2)))) (cdr (cdr ‘((1) (2))))) (list (car ‘(car ((1) (2)))) (cdr (cdr ‘((1) (2))))) = (list ‘car (cdr (cdr ‘((1) (2))))) = (list ‘car (cdr ((2)))) = (list ‘car nil) = (list ‘car nil) = (car nil) ¾ APPEND kết hợp các phần tử của mọi danh sách đã cho (setq l1 ‘(a b) l2 ‘(x y)) = (x y) (append l1 l2) = (a b x y) (append l1 ‘() l2 ‘()) = (a b x y) 3. NTHCDR, BUTLAST và LAST ¾ NTHCDR cắt n phần tử đầu danh sách, với thông số đầu chỉ số phần tử cần cắt * (setq l ‘(a b c d e)) (a b c d e) * (nthcdr 2 l) (c d e) ¾ BUTLAST cắt n phần tử cuối danh sách, với thông số đầu là danh sách, thông số thứ hai chỉ số phần tử cần cắt * (setq l ‘(a b c d e)) (a b c d e) * (butlast l 2) (a b c) * (butlast l 10) NIL ¾ LAST trả về danh sách tất cả phần tử trừ phần tử cuối cùng đã bị loại ra * (setq l ‘(a b c d e) l1 ‘((a b) (c d))) 36
  42. Hướng dẫn sử dụng Lisp ((a b) (c d)) * (last l) (e) * (last l1) ((c d)) 4. LENGTH và REVERSE ¾ LENGTH trả về chiều dài của chuỗi * (setq l ‘(a b c d e)) (a b c d e) * (length l) 5 ¾ REVERSE trả về chuỗi nghịch đảo * (setq l ‘(a b c d e)) (a b c d e) * (reverse l) (e d c b a) II.3 Thao tác trên Integer, Ratio, Floating-Point Numbers, * (/ 1.234321 1.111) 1.111 * (/ 27 9) 3 * (\\ 10 4) 2 Tuy nhiên với trường hợp chia không chẵn, kết quả là một phân số: * (/ 22 7) 22/7 Dùng FLOAT nếu muốn kết quả trả về là số thực có dấu phẩy động: (float (/ 22 7)) 3.14286 Dùng ROUND để làm tròn kết quả: * (round (/ 22 7)) 3 ;Thương – số nguyên gần nhất 1/7 ;Phần dư * (+ round (/ 22 7)) (round (7/3))) 5 * (round (/ 5 2)) 2 Một số hàm tính toán học: * (MAX 2 4 3) 4 * (MIN 2 4 3) 2 37
  43. Hướng dẫn sử dụng Lisp * (expt 2 3) 8 * (expt 3 2) 9 * (expt 3.3 2.2) 13.827085 * (sqrt 9) 3 * (abs -5) 5 II.4 Lập trình hướng dữ liệu 1. ASSOC ¾ ASSOC gắn với một danh sách – association list hay còn gọi a-list Key Key (setf sarah ‘((height .54) (weight 4.4))) Value Value height và weight là khóa trong danh sách được gán cho SARAH; .54 và 4.4 là các giá trị biểu thị bằng met và kilograms. ¾ Có thể lấy các thành phần từ một danh sách dùng ASSOC với các đối số là một khóa và danh sách liên kết: (ASSOC ) Ví dụ: * (setf Andrew ‘((height .74) (weight 6.4))) ((HEIGHT 0.74) (WEIGHT 6.4)) * (assoc ‘height Andrew) (HEIGHT 0.74) Lưu ý ASSOC luôn trả về toàn bộ danh sách con tương ứng với khóa. Trong trường hợp có nhiều danh sách con cùng khóa, danh sách đầu tiên sẽ được trả về. 2. ACONS ¾ ACONS để thêm một thành phần mới vào danh sách (ACONS ) Ví dụ: * (acons ‘nick ‘Bobby Andrew) ((NICK . BOBBY) (HEIGHT 0.74) (WEIGHT 6.4)) 38
  44. Hướng dẫn sử dụng Lisp ¾ Ví dụ: Chúng ta muốn dùng cùng một hàm thực hiện việc cộng hai số và nối hai chuỗi ¾ Giải pháp 1 (defun add(x y) (cond ((numberp x) (+ x y)) ((listp x) (append x y) ) ) ) ¾ Giải pháp 2 * (setf add ‘((FIXNUM +) (CONS append))) ((FIXNUM +) (CONS APPEND)) * (defun add(x y) (funcall (cadr (assoc (type-of x) add)) x y) ) funcall cho phép gọi các hàm tính toán 39
  45. Hướng dẫn sử dụng Lisp Chương III. Hàm và Biến cục bộ Trong chương trước, chúng ta đã tìm hiểu về các hàm cơ bản cũng như một số thuật ngữ trên LISP. Chương này sẽ giúp chúng ta trong việc viết các chương trình riêng cho mình và định nghĩa một hàm mới dựa trên các hàm cơ bản. Các thuật ngữ mới cũng được thêm vào như biến, tham số, thân chương trình. III.1 Định nghĩa hàm – Chương trình đệ quy trong Lisp Trong Lisp, chúng ta định nghĩa hàm bằng từ khóa defun: (defun ) ký hiệu đại diện cho các biến biểu thức Ví dụ: * (defun square (x) (* x x)) SQUARE * (square 3) 9 * (defun abs(x) (if (>= x 0) x (* -1 x) ) ) ABS Vòng lặp trong Lisp được thực hiện chủ yếu nhờ vào đệ quy Ví dụ: Tính giai thừa n!=1*2* *n 0!=1 Trong Pascal, hàm n! được viết bằng vòng lặp: function fac(integer:n):integer; var i:integer begin fac:=1; for i:=1 to n do fac:=fac*i; end Định nghĩa đệ quy của giai thừa: n! = 1*2* *n-1 *n n!=n* (n-1) nếu n≥2 0!=1 (n-1)! 40
  46. Hướng dẫn sử dụng Lisp Trong Lisp: (defun fac(n) (if (= n 0) 1 (* n fac (1- n)) ) ) Bài tập: 3. Viết hàm in ra phần tử thứ n trong danh sách (defun nth (n l) (if (= n 1) (car l) (nth (1- n) (cdr l)) ) ) 4. Ví dụ đệ quy chéo hay lời gọi đệ quy: (defun pair (n) (or (= n 0) (impair (1- n)) ) ) (defun impair (n) (and (<> n 0) (pair (1- n)) ) ) III.2 Biến cục bộ 1. LET (let ((var1 exp1) (varm expm)) expm+1 expn) Chúng ta gán cho mỗi biến giá trị của biểu thức tương ứng, sau đó ta đánh giá (progn expm+1 expn) Ví dụ: * (let ((x (fac 4))) (* x x)) = 576 ¾ Các biến cục bộ che phủ các biến toàn cục * (setq x 5) 5 * (let ((x 1)) x) = 1 * x 5 * (let ((x 1)) (setq x 2) x) 2 *x 5 ¾ Các biến cục bộ che phủ các đối số của một hàm * (defun foo(x) (let ((x 1)) x ) ) FOO * (foo 4) 41
  47. Hướng dẫn sử dụng Lisp 1 ¾ Các liên kết được thực hiện song song * (defun bar(x) (let ((x 1) (y (1+ x))) y) ) BAR * (bar 4) 5 2. LET* ¾ Dạng let* thực hiện một liên kết tuần tự các đối số * (defun bar(x) (let ((x 1) (y (1- x))) y) ) BAR * (defun bar1(x) (let* ((x 1) (y (1- x))) y) ) BAR * (bar 3) 2 * (bar1 3) 0 ¾ let* tương ứng với let lồng nhau * (defun bar(x) (let ((x 1)) (let ((y (1+ x))) y) ) ) BAR 42
  48. Hướng dẫn sử dụng Lisp Chương IV. Các vị từ và biểu thức điều kiện Mục đích chính của chương này là giải thích một số từ mà chúng ta gọi là vị từ. Những từ này, khi kết hợp với các biểu thức điều kiện sẽ cho phép chúng ta biến đổi những gì xảy ra trong một số tình huống, và nhờ vào đó, chúng ta có thể định ra các hàm phức tạp hơn. Một số vị từ còn cho phép thay đổi cách xử lý của các đối số. IV.1 Vị từ Một vị từ là một hàm trả về giá trị true hay false. FALSE trong LISP luôn được biểu diễn bằng NIL. True được biểu diễn bằng ký hiệu T, bất kỳ cái gì khác NIL đều được xem là có giá trị true. Lưu ý là ở đây, T và NIL là các ký hiệu đặc biệt trong đó giá trị của chúng đã được thiết lập sẵn cho T và NIL. Điều đó có nghĩa là giá trị của T là T và giá trị của NIL là NIL. Ví dụ: * t T ; Giá trị của T là T * nil NIL ; Giá trị của NIL là NIL IV.2 Các phép so sánh: EQUAL, EQ, EQL và = EQUAL kiểm tra xem hai đối số và xem giá trị của chúng có cùng một biểu thức biểu diễn hay không. EQUAL dùng cho cả atom và danh sách. * (equal (+ 2 2) 4) T * (equal (+ 2 3) 3) NIL * (equal ‘(this is a list) (setf l ‘(this is a list))) T * (equal ‘(this is a list) l) T * (equal ‘(this is a list) (setf reverse-of-l ‘(list a is this))) NIL * (equal l (reverse reverse-of-l)) T Các vị từ EQUAL, EQ, EQL và = đều có hai đối số và đều dùng để so sánh hai đối số. Nếu hai đối số là bằng nhau, vị từ sẽ trả về giá trị T; ngược lại vị từ trả về giá trị NIL. Tuy nhiên chúng có một số khác biệt trong cách thức so sánh. Nếu như EQUAL được xem là vị từ chung dùng để so sánh, thì EQ và = được sử dụng với những mục đích khác hơn: Vị từ Mục đích equal Giá trị của hai đối số có cùng là một biểu thức hay không ? 43
  49. Hướng dẫn sử dụng Lisp eql Giá trị của hai đối số có cùng là một ký hiệu hay một số hay không ? eq Giá trị của hai đối số có cùng là một ký hiệu hay không ? = Giá trị của hai đối số có cùng là một số hay không ? Bây giờ, chúng ta xem xét một cách chi tiết hơn về liên hệ giữa các vị từ: ¾ EQUAL đầu tiên kiểm tra xem hai đối số có thỏa mãn EQL. Nếu không thỏa, nó sẽ xem chúng là các danh sách và kiểm tra từng phần tử trong nó có thỏa EQUAL không. ¾ EQL đầu tiên kiểm tra hai đối số có thỏa mãn EQ. Nếu không thỏa, nó sẽ xem chúng có cùng là số với cùng kiểu và giá trị. ¾ EQ kiểm tra hai đối số được lưu trữ cùng vùng nhớ trong máy tính hay không. ¾ = kiểm tra hai đối số biểu diễn cùng một số, ngay cả khi chúng không cùng kiểu. Lưu ý rằng các số được so sánh phải là cùng kiểu để thỏa mãn EQL. Nhưng với = thì có thể không cùng kiểu. * (eql 4 4.0) ; Các số khác kiểu NIL * (eql 4 4) ; Các số có cùng kiểu T Các số không cùng kiểu thỏa =: * (= 4 4.0) T Các đối số cho = phải có kiểu số. Bất kỳ một kiểu nào khác sẽ dẫn đến sinh ra lỗi. IV.3 Vị từ MEMBER Vị từ MEMBER kiểm tra xem đối số thứ nhất có phải là một phần tử của đối số thứ hai hay không. Lưu ý là MEMBER trả về những gì còn lại trong danh sách khi tìm thấy phần tử trùng hợp với đối số thứ nhất. * (setf sentence ‘(tell me more about your mother please)) (TELL ME MORE ABOUT YOUR MOTHER PLEASE) * (member ‘mother sentence) (MOTHER PLEASE) Một lưu ý nữa là MEMBER thông thường trả về NIL trừ khi đối số thứ nhất là một phần tử trực tiếp của đối số thứ hai; còn nếu chỉ là phần tử nằm trong một danh sách thì không đủ. * (setf pairs ‘((father son) (mother daughter))) (TELL ME MORE ABOUT YOUR MOTHER PLEASE) * (member ‘mother pairs) NIL Thay đổi cách xử lý các đối số Thông thường, MEMBER thực hiện việc kiểm tra với vị từ EQL – vị từ chỉ hoạt động với ký hiệu và số có cùng kiểu. Bây giờ chúng ta muốn MEMBER tìm một phần tử xuất hiện trong danh sách, chúng ta phải chỉ ra là chúng ta cần kiểm tra tính thành viên dùng vị từ EQUAL thay vì EQL. 44
  50. Hướng dẫn sử dụng Lisp * (setf pairs ‘((mapple shade) (apple fruit))) ((MAPPLE SHADE) (APPLE FRUIT)) * (member ‘(mapple shade) pairs) NIL * (member ‘(mapple shade) pairs :test #’equal) ((MAPPLE SHADE) (APPLE FRUIT)) IV.4 Vị từ NULL và ENDP Ngoài vị từ LISTP, các vị từ quan trọng nhất trên danh sách là: Vị từ Mục đích null Đối số của vị từ là một danh sách rỗng ? endp Đối số của vị từ (phải là danh sách) là một danh sách rỗng ? Ví dụ: * (null ‘(this is not empty)) NIL * (endp ‘(this is not empty)) NIL * (null ‘()) T * (endp ‘()) T * (null ‘this-is-a-symbol) NIL * (endp ‘this-is-a-symbol) ERROR: ENDP: wrong type argument: THIS-IS-A-SYMBOL A CONS or NIL was expected Thông thường ENDP được dùng để kiểm tra danh sách rỗng, và NULL cũng vậy. Tuy nhiên ENDP dùng với một đối tượng không phải danh sách sẽ sinh ra lỗi. Vì vậy, nên dùng NULL cho việc kiểm tra dữ liệu nói chung có phải là NIL hay không, hơn là cho việc kiểm tra danh sách rỗng. IV.5 Các vị từ xác định kiểu dữ liệu Trong LISP, kiểu được gán cho dữ liệu chứ không phải cho biến. Ta có thể biết kiểu dữ liệu của biến nhờ vào các vị từ (prédicat) Vị từ Mục đích atom Đối số có phải là một atom ? numberp Đối số có phải là một số ? symbolp Đối số có phải là một ký hiệu ? 45
  51. Hướng dẫn sử dụng Lisp stringp Đối số có phải là một chuỗi ? listp Đối số có phải là một danh sách ? Ví dụ: * (atom ‘pi) T * (atom pi) T * (numberp ‘pi) NIL * (numberp pi) T * (symbolp ‘pi) T * (symbolp pi) NIL * (listp ‘pi) NIL * (listp pi) NIL * (listp ‘(this is a list with pi in it)) T NIL tương đương với danh sách rỗng NIL và danh sách rỗng, ( ), hoàn toàn tương đương và thỏa mãn tất cả các vị từ EQ, EQL, và EQUAL. * (eq nil ‘()) T * (eql nil ‘()) T * (equal nil ‘()) T Cả NIL và danh sách rỗng đều được in là NIL. * nil NIL * () NIL Chính sự tương đương giữa NIL và () đã gây rắc rối, bởi vì NIL và () đều là ký hiệu và danh sách. Vì thế, cả (SYMBOLP ‘()) và (LISTP NIL) đều trả về T. * (atom nil) T * (atom ()) 46
  52. Hướng dẫn sử dụng Lisp T * (symbolp nil) T * (symbolp ()) T * (listp nil) T * (listp ()) T IV.6 Các vị từ trên số Các vị từ trên số mang ý nghĩa khá rõ ràng: Vị từ Mục đích numberp Đối số có phải là một số ? zerop Đối số có phải là zero ? plusp Đối số có phải là một số dương ? minusp Đối số có phải là một số âm ? evenp Đối số là số chẵn ? oddp Đối số là số lẻ ? > Các đối số theo thứ tự giảm dần ? < Các đối số theo thứ tự tăng dần ? Ví dụ: * (setf zero 0 one 1 two 2 three 3 four 4) 4 * (setf digits (list zero on0e two three four)) (0 1 2 3 4) Dùng những giá trị trên, chúng ta có thể xem các vị từ số. NUMBERP kiểm tra xem đối số của nó có phải là một số hay không. * (numberp 4) T * (numberp four) T * (numberp ‘four) NIL * (numberp digits) NIL * (numberp ‘digits) NIL 47
  53. Hướng dẫn sử dụng Lisp ZEROP nhận đối số là một số và kiểm tra nó có phải là zero hay không. ZEROP sẽ phát sinh lỗi nếu đối số không có kiểu số. * (zerop zero) T * (zerop ‘zero) ERROR: ZEROP: wrong type argument: ZERO A NUMBER was expected. * (zerop four) NIL PLUSP kiểm tra một số có phải là số dương hay không. * (plusp one) T * (plusp (- one)) NIL * (plusp zero) NIL EVENP kiểm tra một số có phải là số chẵn hay không. * (evenp two) T * (evenp (* 9 7 5 3 1)) NIL * (evenp (* 10 8 6 4 2)) T Các vị từ > và kiểm tra xem các đối số có giảm ngặt và four two) T * (>two four) NIL * (> three two one) T * (> three one two) NIL IV.7 Các toán tử logic 1. AND (and E1 E2 En) là sai nếu ít nhất một Ei sai AND đánh giá các đối số từ trái sang phải và chỉ dừng khi gặp một đối số sai Nếu mọi thông số đều đúng, AND trả về thông số cuối cùng 48
  54. Hướng dẫn sử dụng Lisp Ví dụ: * (setq x ‘a) A *x A * (and (numberp x) (> x 1) ) NIL * (and (symbolp x) (list x) ) (A) 2. OR (or E1 E2 En) là sai nếu ít nhất một Ei sai OR đánh giá các đối số từ trái sang phải và chỉ dừng khi gặp một đối số đúng Ví dụ: * (setq x ‘a) A *x A * (or (numberp x) (> x 1) ) error > A is not a number * (or (symbolp x) (list x) ) T 3. NOT NOT đổi giá trị không NIL thành NIL và NIL thành T. Ví dụ: * (not nil) T * (not t) NIL * (not ‘dog) NIL * (setf pets ‘(dog cat)) (DOG CAT) * (member ‘dog pets) (DOG CAT) * (not (member ‘dog pets)) NIL * (member ‘dingo pets) NIL * (not (member ‘dingo pets)) 49
  55. Hướng dẫn sử dụng Lisp T * (and (member ‘dog pets) (member ‘tiger pets)) NIL * (and (member ‘dog pets) (not (member ‘tiger pets))) T Chúng ta nhận thấy rằng NIL và danh sách rỗng – () là hoàn toàn tương đương nhau. Do đó NOT thật sự làm cùng một công việc như NULL: cả hai đều trả về T nếu đối số là NIL, và cả hai đều trả về NIL khi đối số là không NIL. IV.8 Các dạng điều kiện 1. IF, WHEN và UNLESS (if E1 E2 E3) Nếu E1 đúng, trả về giá trị E2 nếu không trả về giá trị E3 Ví dụ: * (if (numberp 1) ‘(a number) ‘(not a number)) (A NUMBER) * (if (numberp ‘a) ‘(a number) ‘(not a number)) (NOT A NUMBER) Ở đây, chỉ có một trong hai đối số – đối số thứ hai hoặc thứ ba được đánh giá. IF được gọi là có điều kiện vì IF phụ thuộc vào giá trị đối số của nó. Có nhiều dạng điều kiện khác phổ biến IF hơn khi người dùng không cần lắm tính tổng quát của IF. Chi tiết hơn, WHEN được dùng thay cho IF khi mệnh đề kết quả sai trong IF (biểu thức E3 ở trên) là NIL. (if E1 E2 nil) ≡ (when E1 E2) Tương tự như vậy, UNLESS được dùng thay cho IF khi mệnh đề kết quả đúng trong IF (biểu thức E2 ở trên) là NIL. (if E1 nil E3) ≡ (when E1 E3) Thật sự, cả WHEN và UNLESS có số lượng không giới hạn các đối số. Đối số thứ nhất là biểu thức cần kiểm tra; đối số cuối cùng trả về giá trị; và mọi đối số ở giữa được đánh giá cho các hiệu ứng lề. Trong ví dụ bên dưới, giá trị của WHEN là NEW-RECORD khi TEMPRATURE có giá trị lớn hơn HIGH. * (setf high 98 temprature 102) 102 * (when (> temprature high) ; So sánh TEMPRATURE với HIGH (setf high temprature) ; Nếu lớn hơn, thay đổi giá trị HIGH ‘new-record) ; Nếu lớn hơn, trả về NEW-RECORD 50
  56. Hướng dẫn sử dụng Lisp 2. COND (cond (Test1 E1 ) (Test2 E2 ) (Test3 E3 ) (Testn En ) ) ≡ (if Test1 (progn E1 ) (if Test2 (progn E2 ) (if Test3 (progn E3 ) (if Testn (progn En )) ) ) ) Trong một mệnh đề kiểu (Test1), nếu Test1 đúng, kết quả của cond là giá trị của (Test1) Ví dụ: Viết hàm trả về kiểu của đối số * (type-of 1) FIXNUM * (type-of a) SYMBOL Giải: (defun type-of (x) (cond ((null x) ‘null) ((symbolp x) ‘symbolp) ((numberp x) ‘numberp) ((stringp x) ‘stringp) ((consp x) ‘consp) (t ‘unknown-type) ) ) 3. CASE Các dạng IF, WHEN và UNLESS có thể xem như những trường hợp đặc biệt của COND vì tất cả đều có thể biểu diễn bằng COND. Chúng ta xem một trường hợp đặc biệt khác, CASE, có ý nghĩa tương tự như COND. CASE theo sau là dạng khóa (key form) và một dãy các mệnh đề. (case Key (Key1 E11 ) (Key2 E21 ) (Keyn En1 ) ) ≡ 51
  57. Hướng dẫn sử dụng Lisp (cond ( (eql Key Key1) E11 ) ( (eql Key Key2) E21 ) ( (eql Key Key3) E31 ) ( (eql Key Keyn) En1 ) ) CASE dùng vị từ EQL và so sánh khóa được đánh giá với các khóa chưa được đánh giá. Nếu tìm thấy khóa, mệnh đề tương ứng sẽ được thực hiện và tất cả mọi biểu thức trong mệnh đề được đánh giá. Chúng ta dùng CASE khi ta muốn có COND trong đó mọi biểu thức kiểm tra tìm một giá trị trong nhiều khả năng. Trong ví dụ bên dưới, xét dạng COND sau: * (cond ((eq thing ‘circle) (* pi r r)) ((eq thing ‘sphere) (* 4 pi r r))) Ví dụ trên được viết lại dưới dạng CASE như sau. * (case thing ;ký hiệu THING sẽ được đánh giá (circle (* pi r r)) ;ký hiệu CIRCLE chưa được đánh giá (sphere (* 4 pi r r))) ;ký hiệu SPHERE chưa được đánh giá 52
  58. Hướng dẫn sử dụng Lisp Chương V. Trừu tượng hóa dữ liệu Phần này sẽ giới thiệu khái niệm trừu tượng hóa dữ liệu – tiến trình giúp bạn xây dựng các chương trình lớn và phức tạp trong LISP. V.1 Các trường của một ký hiệu Ký hiệu là một đối tượng bao gồm nhiều trường: ¾ CVAL: giá trị của ký hiệu cũng như biến ¾ PNAME: chuỗi ký tự tương ứng với tên của ký hiệu (dùng cho máy in) ¾ FVAL: hàm gắn liền với ký hiệu, trường này không tồn tại trong LISP đơn trị LISP đa trị (bi-valued) LISP đơn trị (mono-valued) * (setq + 4) * (setq + 4) 4 4 * (+ + 3) * (+ + 3) 7 func + undef * (setq + *) * (* 4 3) var + indef = 12 ¾ FTYPE: kiểu hàm Ví dụ: * (setq foo 3) 3 foo 3 CVAL * (defun foo(x) ) FVAL FOO EXPR FTYPE PNAME “foo” V.2 Doublets 1. Doublets Một danh sách không rỗng được biểu diễn bằng một đối tượng có hai trường gọi là doublet trường trường car cdr phần còn lại phần tử đầu 53
  59. Hướng dẫn sử dụng Lisp Tương tự như vậy, danh sách (1 2 3) được thể hiện bởi: nil 1 2 3 Hay đơn giản hơn: 1 2 3 nil 2. Pointed pair Thông số thứ hai của cons có thể không phảI là một danh sách. Trong trường hợp đó, chúng ta gọi là cặp con trỏ (pointed pair) * (cons ‘a ‘b) (A . B) * (car ‘(a . b)) A * (cdr ‘(a . b)) B 3. Ký hiệu pointed pair Ký hiệu danh sách là viết tắt của ký hiệu pointed pair *‘(1 . nil) (1) *‘(1 . (2 . (3 . nil))) (1 2 3) Nói chung, chúng ta có: (exp.(exp1 expN))=(exp exp1 expN) Chúng ta có thể kết hợp hai lối ký hiệu: * ‘(1 . (2 3)) (1 2 3) * ‘(1 . (2 . 3)) (1 2 . 3) 4. Doublets trong LISP ¾ Mỗi biểu thức trong Lisp là một doublet hay một atom expression ::= (expression.expression) | atom ¾ Consp là một vị từ để kiểm tra thông số của nó có là một doublet hay không (defun listp(p) (or (null x) (consp x) ) ) 54
  60. Hướng dẫn sử dụng Lisp V.3 Lời gọi hàm tính toán 1. Apply ¾ (apply F L) áp dụng hàm F trên các phần tử của danh sách L * (apply ‘append ‘((a b) (c d))) (a b c d) * (apply ‘+ ‘(1 2)) 3 * (setq a ‘*) * * (apply a ‘(3 4)) 12 ¾ (apply F L) ≡ (eval (cons F L)) Bt. Đếm số ký hiệu, số hay chuỗi trong một list (defun count(test l) (if (null l) 0 (if (apply test (list (car l))) (1+ (count test (cdr l))) (count test (cdr l)) ) ) ) 2. Funcall ¾ funcall: áp dụng giá trị của thông số thứ nhất (một hàm hay tên của một hàm) vào các thông số tiếp theo (funcall ‘F E1 En) = (F E1 En) ¾ (apply f (list e1 en)) ≈ (funcall f e1 e2) * (setq a ‘+) + * (funcall a (+ 3 4) 5) 12 Lưu ý: Trong Lisp đơn trị (như Scheme), chúng ta có thể viết trực tiếp: * (a (+ 3 4) 5) = 12 vì ở đó có sự đánh giá hàm Bt. Đếm số ký hiệu, số hay chuỗi trong một list (defun count(test l) (if (null l) 0 (if (funcall test (car l)) (1+ (count test (cdr l))) (count test (cdr l)) ) ) ) Bt. Đếm số ký hiệu, số hay chuỗi trong một list 55
  61. Hướng dẫn sử dụng Lisp V.4 Hàm vô danh 1. Lambda expression Dùng hàm count để đếm số số nguyên nhỏ hơn 10 trong danh sách. * (defun inf10(x) (and (integerp x) (< x 10)) ) INF10 * (count ‘inf10 ‘(4 12 a 11 3)) 2 Nhận xét : Chúng ta định nghĩa hàm inf10 chỉ để sử dụng một lần duy nhất Có thể sử dụng một hàm không tên. Hàm như thế trong Lisp được gọi là lambda- expression và được viết: (lambda header content) * (count (lambda (x) (and (integer x) (< x 10) ) ) ‘(4 12 a 11 3) 2 Có thể trực tiếp định nghĩa lambda-expression khi xử lý: * (+ 10 ((lambda (x) (* x x)) 4) ) 26 2. Hàm vô danh và biến cục bộ Các biến cục bộ được bắt đầu với let là các tham số của một hàm vô danh (anonymous) (let ((var1 val1) (varN valN)) corps) ≡ ( ( lambda (var1 varN) corps) val1 valN) * (let ((x 1) (y 2)) (+ x y)) 3 * ( ( lambda (x y) (+ x y) ) 1 2 ) 3 56
  62. Hướng dẫn sử dụng Lisp Chương VI. Lặp trên số và trên danh sách Mục đích chính của chương này nhằm giúp bạn đọc làm thế nào để thực hiện một việc một số lần nào đó (tính lũy thừa, giai thừa của một số) hay làm thế nào cùng thực hiện một việc cho mỗi phần tử trong danh sách (trong một danh sách hai chiều, sắp xếp mỗi danh sách con theo thứ tự tăng dần). VI.1 Các cấu trúc lặp 1. DOTIMES Là cách đơn giản và thông dụng nhất để thực hiện một vòng lặp, có cú pháp chung như sau: (dotimes ( ) ) Khi thực hiện DOTIMES, đầu tiên upper-bound-form được đánh giá và trả về kết quả là một số n. Sau đó, các số từ 0 đến n-1 được gán lần lượt cho tham số đếm count. Vì thế tham số đếm count được gán n lần. Để minh họa, chúng ta xét một chương trình tính lũy thừa, nhưng lần này lũy thừa được xét theo cách thức lặp thay vì đệ quy: mn = m × m × × m DOTIMES là cách chúng ta hiện thực chương trình lặp để tính lũy thừa bởi vì nó giúp chúng ta thực hiện công việc việc một số lần nhất định. (defun dotimes-expt(m n) (let ((result 1)) (dotimes (count n result) (setf result (* m result)) ) ) ) Bên trong DOTIMES, thân vòng lặp (phần body - setf result (* m result)) được thực hiện n lần, và giá trị của RESULT, result form, chính là kết quả cần tính. Lưu ý là tham số count không xuất hiện trong phần thân của DOTIMES trong ví dụ đặc biệt này. Bt: Viết DOTIMES-FACTORIAL, dùng DOTIMES để tính giai thừa. n * (n - 1)!, với n > 0; n! = 1, với n = 0. 2. DOLIST Hỗ trợ lặp trên danh sách Tương tự như DOTIMES, nhưng các phần tử của danh sách được gán lần lượt cho tham số, có cú pháp chung như sau: (dolist ( ) ) 57
  63. Hướng dẫn sử dụng Lisp Khi thực hiện DOLIST, đầu tiên list form được đánh giá và trả về kết quả là một danh sách các phần tử. Sau đó, các phần tử của danh sách được gán lần lượt cho tham số. Với mỗi giá trị, phần thân vòng lặp (body) được đánh giá. Cuối cùng, tham số này được bỏ đi và kết quả được đánh giá, trả về giá trị cho DOLIST form. Nếu DOLIST không có result form, DOLIST sẽ trả về NIL và mục đích của nó bây giờ chỉ là sắp xếp cho mục đích nào đó. Bây giờ chúng ta sẽ viết phương thức đếm số phần tử trong danh sách ở dưới nhiệt độ đông lạnh hay trên nhiệt độ sôi, tính bằng độ Fahrenheit: * (count-outlyers ‘(18 75 31 180 270 52)) 3 Cách đơn giản nhất để làm việc này là hiện thực COUNT-OUTLYERS dùng COUNT-IF. Một cách khác nữa là dùng DOLIST như sau: (setf freezing 32 boiling 212) (defun count-outlyers(list-of-elements) (let ((result 0)) (dolist (element list-of-elements result) (when (or (> element boiling) ( element boiling) (< element freezing)) (setf result (+ result 1)) (push element outlyers)) ((= n result) (return outlyers)) ) ) ) ) Bt. Viết DOLIST-MEMBER hiện thực MEMBER dùng DOLIST. Viết DOLIST-REVERSE hiện thực REVERSE dùng DOLIST. 58
  64. Hướng dẫn sử dụng Lisp 3. DO tổng quát hơn DOLIST và DOTIMES DO được dùng khi DOLIST và DOTIMES không đủ tính mềm dẻo. (DO ( ( ) ( ) ( ) ) ( ) ) Chương trình sau minh họa cách dùng DO để tính lũy thừa: (defun do-expt(m n) (do ((result 1) (exponent n)) ((zerop exponent) result) (setf result (* m result)) (setf exponent (- exponent 1)) ) ) Chúng ta thấy trong vòng lặp DO trên có hai phần: - Phần thứ nhất là một danh sách các tham số cùng giá trị khởi tạo khi mới vào vòng DO. - Phần thứ hai sẽ xác định khi nào vòng lặp kết thúc và giá trị trả về. Phần này bao gồm một danh sách có: ƒ Phần tử đầu tiên của danh sách là một kiểm tra kết thúc Test ƒ Các phần tử tiếp theo của danh sách lần lượt được đánh giá khi Test khác NIL. Giá trị trả về của DO là giá trị của phần tử cuối cùng trong danh sách. VI.2 Các dạng đặc biệt 1. progn (progn E1 En) đánh giá tuần tự các biểu thức E1, , En từ trái sang phải và kết quả trả về là giá trị của biểu thức En * (progn (setq x ‘(a b c)) (append x x) ) (A B C A B C) * (progn) NIL 2. prog1 (prog1 E1 En) đánh giá tuần tự các biểu thức E1, , En từ trái sang phải và kết quả trả về là giá trị của biểu thức E1 59
  65. Hướng dẫn sử dụng Lisp * (prog1 (setq x ‘(a b c)) (append x x) ) (A B C) 60
  66. Hướng dẫn sử dụng Lisp Chương VII. Các thao tác với tập tin Trong các phần trước, chúng ta đã biết định nghĩa hàm để thực hiện công việc của mình, chúng ta bắt đầu muốn biết làm thế nào để lưu lại các hàm và xử lý mình đã tạo ra. Chương này sẽ giải thích làm thế nào để lưu lại các định nghĩa dưới dạng tập tin để ta có thể sử dụng lại sau này. VII.1 Lưu lại tập tin chương trình và dữ liệu Để tạo mới một tập tin hay sửa đổi một tập tin có sẵn, chúng ta dùng ED (viết tắt của editor). (ed name) ED sẽ mở trình soạn thảo để soạn chương trình (các lệnh, định nghĩa hàm, ) trên đó. Sau đó, để đánh giá một tập tin, trở về LISP và dùng LOAD. (load name tên hay đường dẫn đến file chứa định nghĩa hàm ¾ (read) đọc một biểu thức và trả về kết quả * (+ (read) 3) * 4 = 7 * (read) * (+ 3 4) = (+ 3 4) VII.2 Biên dịch tập tin Một khi đã lưu lại một tập tin chứa đầy đủ các định nghĩa LISP, bạn có thể dùng ngay các định nghĩa đó hoặc dịch chúng sang tập lệnh máy tính. Khi chúng ta dùng cách thứ nhất, nghĩa là không cần dịch, trình thông dịch LISP (LISP interpreter) sẽ thường xuyên tham chiếu đến các định nghĩa trong chương trình và, theo các định nghĩa đó, từng dạng một, tính toán kết quả một cách tường minh đối với mỗi dạng. Khi dùng cách thứ hai, trình thông dịch LISP (LISP compiler), các định nghĩa trong chương trình của bạn sẽ được chuyển thành một tập lệnh hoàn toàn khác – tập lệnh máy tính. Để dùng những định nghĩa này, LISP sẽ gọi tập lệnh máy tính đã được chuyển bằng lệnh COMPILE. Ví dụ: (compile name) VII.3 Debugging ¾ Đây là ngôn ngữ tương tác (interactive), do đó chúng ta có thể kiểm tra mỗi hàm ở toplevel mà không bắt buộc phải định nghĩa các chương trình tests ¾ Một kỹ thuật theo vết (trace) cho phép theo dõi quá trình thực hiện một hàm 61
  67. Hướng dẫn sử dụng Lisp * (defun fac(n) (if (= n 0) 1 (* n (fac (1- n))) ) ) FAC * (trace fac) ;Autoload: TRACE from “TRACE” in “C:\\GCLISP\\LISPLIB” T * (fac 2) ENTERING: FAC, ARGUMENT LIST: (2) ENTERING: FAC, ARGUMENT LIST: (1) ENTERING: FAC, ARGUMENT LIST: (0) EXITING: FAC, VALUE: 1 EXITING: FAC, VALUE: 1 EXITING: FAC, VALUE: 2 2 ¾ untrace cho phép trở về sự thực hiện bình thường của hàm * (untrace fac) (FAC) * (fac 2) 2 ¾ trace cập nhật định nghĩa hàm theo vết bằng cách in ra kết quả từng giai đoạn ¾ có thể theo dõi sự thực hiện nhiều hàm cùng lúc 62
  68. Hướng dẫn sử dụng Lisp Chương VIII. Cài đặt và sử dụng gcLisp VIII.1 Cài đặt - Download GC-Lisp từ trang web môn học. - Double-click để giải nén file. - Chọn extract vào “C:\” - Click nút “Extract” VIII.2 Startup Gclisp Trên cửa sổ Windows, chọn menu Start -> Run và đánh vào “C:\GcLisp\gclisp.exe” Hay double-click GcLisp.exe để load trong thư mục “C:\GcLisp” Chúng ta sẽ thấy cửa sổ gclisp như sau: VIII.3 Phím nóng - -H giúp đỡ - -E đi vào LISP Explorer - -E dùng trình soạn thảo GMACS (kiểm tra dấu ngoặc) - ra khỏi môi trường soạn thảo 63
  69. Hướng dẫn sử dụng Lisp - load một file vào trình soạn thảo - lưu một file - save file với tên khác VIII.4 Dòng lệnh Đánh các dòng lệnh theo sau ký hiệu * VIII.5 Lệnh tiền tố (Prefix command) - Mọi lệnh đều nằm giữa dấu ngoặc đơn ( ) - Lisp sẽ đánh giá (evaluate) khi chúng ta đánh “)” - Lệnh có dạng tiền tố: (function ) VIII.6 Cửa sổ soạn thảo GMAC - Nhấn “Ctrl-E” để đi vào cửa sổ soạn thảo GMAC - Nhấn để lưu file và để quay trở lại GcLisp VIII.7 Load file vào gclisp - Ví dụ: load first.lsp * (load ‘first) 64
  70. Hướng dẫn sử dụng Lisp 65
  71. PHẦN III. SMALLTALK
  72. Hướng dẫn sử dụng SmallTalk Chương I. LÝ THUYẾT VỀ OOP VÀ NGÔN NGỮ SMALLTALK I.1 Lập trình hướng đối tượng (Object Oriented Programming) với Smalltalk 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). Đối tượng là khái niệm căn bản nhất của OOP. Hiểu theo một cách đơn giản, đối tượng là sự mở rộng của record (có thể thấy rõ điều này qua sự phát triển của ngôn ngữ Pascal). Một record thì bao gồm nhiều trường (field), trong đó mỗi field lại được xem như một biến thành phần của record. Như vậy mỗi record được xem như một đối tượng dữ liệu cấu trúc, trong đó mỗi thành phần của cấu trúc lại là một đối tượng dữ liệu con. Tương tự như record, mỗi đối tượng cũng có nhiều thành phần (member), tuy nhiên các thành phần không chỉ là dữ liệu, mà còn có thể là các đoạn mã (code). Các thành phần dữ liệu của đối tượng được gọi là các thuộc tính (properties) của đối tượng, còn các thành phần mã của đối tượng có thể được coi như là các chương trình con (procedure) đặc biệt được viết dành riêng cho đối tượng. Mỗi chương trình con này được gọi là một phương thức (method). Như vậy một đối tượng được xem như là một đối tượng dữ liệu có cấu trúc trong đó các thành phần của nó là các thuộc tính và các phương thức. Sự thống nhất dữ liệu và mã thành một thực thể duy nhất như vậy gọi là sự bao đóng(encapsulation). Đối tượng là một sự bao đóng giữa các thuộc tính và các phương thức. 2. Khái niệm class - Mối quan hệ giữa object và class - Khái niệm instance. Các đối tượng có cùng một số tính chất được tập hợp lại thành một lớp (class). Hiểu một cách tương đối, mối quan hệ giữa đối tượng và lớp gần giống như mối quan hệ giữa một đối tượng dữ liệu (hằng, biến) với kiểu dữ liệu (data type). Các đối tượng thuộc cùng một lớp thì có các thành phần như nhau, nghĩa là có cùng các thuộc tính và các phương thức như nhau. Chính vì vậy với lập trình OOP, lập trình viên sẽ không làm công việc định nghĩa hay khai báo các thành phần cho một đối tượng cụ thể nào, mà sẽ định nghĩa hoặc khai báo các thành phần cho một lớp cụ thể nào đó, theo đó, tất cả các đối tượng thuộc về lớp này sẽ có chung tính chất về các thành phần được khai báo cho lớp. Một đối tượng của một lớp trong thời gian sống (life - time) của nó được gọi là một thực thể (instance) của lớp đó. Khi chương trình Smalltalk thực thi, lập trình viên luôn được cho biết thông tin về các lớp đang có của chương trình, các thuộc tính và các phương thức được xây dựng cho các đối tượng của lớp đó. 67
  73. Hướng dẫn sử dụng SmallTalk Trong tài liệu này, chúng ta sẽ sử dụng phần mềm lập trình Vwin để minh họa ngôn ngữ lập trình Smalltalk này. Tên lớp Tên các thuộc tính của lớp Tên các phương thức của lớp Thuộc tính thường, thuộc tính lớp Nội dung phương thức 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) Một phương thức, như đã trình bày, có thể xem như một chương trình con được viết riêng cho một đối tượng. Tuy nhiên, chương trình con này, về lý thuyết, không được phép gọi trực tiếp từ bên ngòai đối tượng. Từ môi trường bên ngòai đối tượng, chỉ có thể tác động đến đối tượng bằng một thông điệp (message). Nếu một đối tượng nhận một thông điệp, nó sẽ trả lời bằng một phương thức thích hợp (nếu thông điệp mà đối tượng nhận được là thông điệp mà nó có khả năng trả lời). Về mặt lý thuyết, tên thông điệp và tên phương thức tương ứng dùng để trả lời thông điệp không cần phải giống nhau, tuy nhiên với ngôn ngữ Smalltalk, phương thức dùng để trả lời thông điệp sẽ có cùng tên với thông điệp. 68
  74. Hướng dẫn sử dụng SmallTalk Như vậy, khi môi trường tác động lên một đối tượng qua một thông điệp, có thể coi như đó là một lời gọi chương trình con (procedure - call), qua đó đối tượng sẽ thực thi phương thức tương ứng. Như vậy, nếu hiểu trên phương diện một phương thức là một chương trình con đặc biệt, thì cũng như các chương trình con bình thường, một phương thức cũng có thể có các thông số hình thức, và trong lời gọi chương trình con, tại nơi gọi phải truyền các thông số thực. Các thông số thực này được gọi là các đối số (argument) của thông điệp. Các đối số này cũng là các đối tượng khác. Ví dụ: Xét câu lệnh Smalltalk như sau: 3 + 4. Trong trường hợp trên đây, 3 và 4 là hai đối tượng, biểu hiện cho hai con số. Ký hiệu + là một thông điệp, và theo quy định của cú pháp Smalltalk, thông điệp trên được gởi cho đối tượng là số 3. Như vậy 3 là đối tượng nhận thông điệp. 4 là đối số của thông điệp này. Khi thực thi, đối tượng 3 sẽ gọi đến một phương thức tương ứng với thông điệp + và truyền đối số là 4, phương thức này sẽ thực hiện và cho ra kết quả. Tất nhiên, kết quả là 7. Để thực thi đoạn ví dụ (trong trường hợp này chỉ là một dòng lệnh) trên, cũng như tất cả các đoạn mã ví dụ khác của phần này, hãy thực hiện theo trình tự sau (độc giả có thể xem phần 3 để được hướng dẩn kỹ hơn) Tại vùng cửa sổ soạn thảo kịch bản (Transcript), đánh đọan mã ví dụ vào. Sau khi nhập xong đoạn script, chọn (highlight) đoạn mã cần thực thi, chọn mục Show It trong menu Smalltalk như trong hình dưới. Nếu đoạn lệnh không sai cú pháp, kết quả sẽ hiện ra và được highlight ở cuối vùng mã được chọn. 4. Các loại thông điệp: unary, binary và keyword. Độ ưu tiên giữa các thông điệp. Smalltalk quy định ba loại thông điệp có thể truyền cho các đối tượng, giữa các loại thông điệp này có độ ưu tiên khác nhau. Nếu xem các thông điệp tương tự như các tóan tử, thì các tóan tử này có sự kết hợp trái. Thông điệp unary là loại thông điệp không yêu cầu thông số. Ví dụ: -2 abs. 69
  75. Hướng dẫn sử dụng SmallTalk Ở đây -2 là đối tượng nhận thông điệp, abs là một thông điệp unary. Kết quả cho biết trị tuyệt đối của đối tượng nhận thông điệp (2). Tương tự với câu lệnh ‘abcd’ size. Đối tượng nhận thông điệp là một chuỗi ‘abcd’, tên thông điệp là size. Kết quả sẽ cho biết chiều dài chuỗi (4). Thông điệp binary là loại thông điệp được biểu diễn bằng một hoặc hai ký hiệu đặc biệt (không phải là chữ hoặc số.). Ví dụ như >=, binary->keyword message Ví dụ: ‘abcd’ size + 2 and: 10 Æ 2 ‘abcd’ size + (2 and: 10) Æ 6 5. Câu lệnh (statement) - kịch bản (script) Như các ví dụ trên cho thấy, một câu lệnh (statement) bất kỳ của Smalltalk đều chỉ có một dạng duy nhất: đối tượng nhận thông điệp, trong đó thông điệp này có thể có hoặc không có đối số, và các đối số này cũng là các đối tượng, được truyền qua tên hoặc truyền trực tiếp từ các lệnh truyền thông điệp cho các đối tượng khác. Như vậy một đoạn lệnh, tức nhiều câu lệnh trên ngôn ngữ Smalltalk trong đó các lệnh ngăn cách bằng ký tự ‘.’ thực chất là các phát biểu truyền thông điệp có thể có thông số tới các đối tượng, tức là lập trình viên làm công việc chỉ ra mối quan hệ giữa các đối tượng (giữa đối tượng nhận thông điệp và đối số của nó) hoặc tác động đến dữ liệu bên trong của đối tượng thông qua các thông điệp được truyền đến các đối tượng. Vì vậy một đoạn lệnh 70