Giáo trình Lý thuyết ngôn ngữ lập trình (Phần 2) - Nghề: Lập trình máy tính - Trình độ: Cao đẳng nghề

Nội dung text: Giáo trình Lý thuyết ngôn ngữ lập trình (Phần 2) - Nghề: Lập trình máy tính - Trình độ: Cao đẳng nghề

1. Bài 3 TÊN BÀI:HÀM THỦ TỤC MÃ BÀI:: ITPRG3-06.3 Giới thiệu Khái niệm chương trình con (sub-program hay sub-routine) ra đời từ rất sớm vào những năm 1950. Mà sau đó chương trình con dạng hàm hay thủ tục đã được sử dụng rộng rãi trong các ngôn ngữ lập trình, đặc biệt là các ngôn ngữ lập trình mệnh lệnh. Cho đến ngày nay, khi mà các ngôn ngữ lập trình rất pgong phú đa dạng thì khái niệm này vẫn tồn dưới nhiều hình thức khác nhau. Mục tiêu thực hiện - Hiểu rõ cơ chế thực hiện của chương trình con dạng hàm và thủ tục - Phân biệt và sử dụng đúng các dạng tham số - Nắm cấu trúc chuẩn của một chương trình con - Hiểu được tính ưu việt của các chương trình con - Nắm được cách xây dựng và sử dụng chương trình con trong ngôn ngữ lập trình Pascal - Nắm được khái niệm đệ quy Nội dung chính Trình bày hai khái niệm hàm và thủ tục. Nêu bật ưu điểm của hàm và thủ tục. Trình bày cách xây dựng hàm và thủ tục trong ngôn ngữ lập trình Pascal. Khái niệm chương trình con Khái niệm chương trình con (sub-program hay sub-routine) được ra đời từ rất sớm vào những năm 1950, khi mà ngôn ngữ để lập trình mới chỉ là ngôn ngữ máy. Do việc, viết chương trình bằng các bit nhị phân là rất phức tạp, khó khăn, người ta đã nghĩ đến việc xây dựng sẵn các đoạn chương trình thường hay sử dụng. Các đoạn chương trình này chính là tiền thân cho khái niệm chương trình con. Chương trình con thực ra là những đoạn chương trình (dãy các câu lệnh) thường được hay sử dụng lặp đi lặp lại trong khi lập trình. Để giảm bớt thời gian lập trình, người ta xây dựng sẵn các thư viện chứa các chương trình con mà sau đó các chương trình con này có thể được sử dụng nhiều lần. Ví dụ, tính cos hay sin là các công việc thường hay gặp trong toán học. Thế thì thay vì mỗi lần cần đến ta phải thực hiện tính toán, ta có thể xây dựng sẵn các chương trình con cho phép thực hiện công việc tính toán này và sau đó chỉ việc sử dụng. Trong thực tế, trong hầu hết tất cả các ngôn ngữ lập trình các công việc thường được lặp đi lặp lại như thế này đều được xây dựng sẵn thành các chương trình con chứa trong các thư viện dành cho người sử dụng. Ngoài ra trong quá trình lập trình, người lập trình có thể tự xây dựng cho mình các chương trình con được sử dụng nhiều lần trong một chương trình. Khái niệm chương trình con có hầu hết trong các ngôn ngữ lập trình, mà có thể tên gọi của nó bị thay đổi đi chút ít, như: hàm, thủ tục, thao tác, phương thức, Đặc biệt trong các 66
2. ngôn ngữ lập trình mệnh lệnh (như Pascal) thì chương trình con được chia làm hai loại: hàm (function) và thủ tục (procedure). Trong bài học này chúng ta sẽ tìm hiểu về hai loại chương trình con này thông qua ngôn ngữ lập trình Pascal, là một ngôn ngữ mang tính sư phạm cao và thể hiện rất rõ hai khái niệm này. Xây dựng hàm và thủ tục Trước hết hàm hay thủ tục đều là những đoạn chương trình thường được sử dụng lặp đi lặp lại. Thế sự khác nhau giữa hai khái niệm này là gì? Hàm sau khi thực hiện xong công việc thì tra về một giá trị thông qua tên hàm, trong khi thủ tục không trả về giá trị nào cả. Ví dụ, hàm binhphương tính giá trị bình phương của một số nguyên sẽ trả về giá trị đó qua tên hàm. Trong khi thủ tục xuatmanhinh thực hiện việc in ra màn hình một kết quả tính toán nào đó thì nó không trả về một giá trị nào cả. Trong ngôn ngữ Pascal, các chương trình con phải được khai báo và viết bên trên thân chương trình, sau đó được sử dụng trong thân chương trình. Cú pháp tổng quát để viết một hàm trong Pascal như sau: Function tên_hàm (khai báo các tham số hình thức) : kiểu_trả_về_của_hàm; (* Các khai báo hằng, biến cục bộ *) Begin (*thân hàm*) tên_hàm := biểu_thức; (* gán giá trị trả về *) End; Khi khai báo một hàm, nếu hàm đó có sử dụng các hằng hay biến cục bộ thì phải khai báo sau khi khai báo hàm. Ở đây chúng ta thấy xuất hiện khái niệm biến cục bộ (local variable) là các biến được khai báo bên trong một hàm (hay thủ tục). Trong thân hàm luôn phải có phép gán giá trị trả về cho tên hàm. Ví dụ, viết hàm tính tổng của 3 số thực: Function tong3so (x, y, z : real) : real; Begin tong3so := x + y + z; End; Đây là hàm rất đơn giản, nhận 3 giá trị số thực và trả về tổng của chúng. Đối với hàm này không có các khai báo thêm hằng, biến cục bộ. Hàm được bắt đầu bởi từ khóa Function, sau đó là tên hàm tong3so. Hàm nhận 3 tham số hình thức là x, y, z có kiểu real và trả về giá trị kiểu real. Thân hàm gồm các câu lệnh được đặt giữa hai từ khóa Begin và End. Giá trị tổng 3 số thực được gán trực tiếp cho tên hàm trong thân hàm. Dưới đây là một ví dụ khác, chương trình có chứa hàm tính giá trị lớn nhất của hai số thực. Hàm được sử dụng trong thân chương trình để tính giá trị lớn nhất của các biểu thức a+b và a-b. Program vi_du_max; Var 67
3. a, b, s : real; (*Khai báo hàm max2so*) Function max2so(x, y : real) : real; Var r : real; (* khai báo biến cục bộ *) Begin if x > y then r := x else r := y; max2so = r; End; (*Thân chương trình chính*) Begin a := 11.45 b := -42.7 s := max2so(a+b, a-b); (* gọi chương trình hàm *) Writeln(‘Max = ’, s:5:1); End. Như thế, chúng ta nhận thấy hàm luôn trả về một giá trị trong tên hàm. Trong khi định nghĩa hàm thì phải gán tên hàm cho giá trị trả về. Ngược lại, thủ tục không trả về giá trị. Cú pháp tổng quát để viết một thủ tục trong Pascal là như sau: Procedure tên_thủ_tục (khai báo các tham số hình thức); (* Các khai báo hằng, biến cục bộ*) 1. Begin (*thân thủ tục*) End; Bây giờ chúng ta viết lại chương trình tính giá trị lớn nhất hai số thực sử dụng chương trình con là thủ tục như sau: Program vi_du_max; Var a, b : real; (*Khai báo thủ tục max2so*) Procedure max2so(x, y : real); Var r : real; (* khai báo biến cục bộ *) Begin if x > y then r := x else r := y; Writeln(‘Max = ’, r:5:1); End; 68
4. (*Thân chương trình chính*) Begin a := 11.45 b := -42.7 max2so(a+b, a-b); (* gọi chương trình thủ tục *) End. Trong ngôn ngữ Pascal, còn cho phép viết các chương trình con bên trong thân một chương trình con khác. Chẳng hạn, chúng ta xem xét ví dụ thủ tục M sau: (* khai báo thủ tục M*) Procedure M (x, y : real); Var s : real; (* biến cục bộ của thủ tục M*) (* khai báo hàm M1 bên trong thân thủ thủ tục M*) Function M1 (m, n : real) : real; Var r : real; (* biến cục bộ của thủ tục M1*) Begin if m > n then r := m else r := n; M1 := r; End; (* khai báo thủ tục M2 bên trong thân thủ tục M*) Procedure M2 (a : real); Begin Writeln(‘In ket qua : ’, a:5:1); End; (* thân của thủ tục M *) Begin s := M1(x, y); (* gọi hàm M1*) M2(s); (* gọi thủ tục M2*) End; Trong ví dụ này, bên trong thân của thủ tục M chứa hai chương trình con khác là hàm M1 và thủ tục M2. Sau đó, trong thân của thủ tục M sử dụng hai chương trình con này. Lưu ý là không phải ngôn ngữ lập trình nào cũng cho phép khai báo các chương trình con bên trong chương trình con khác, chẳng hạn như ngôn ngữ C không cho phép điều này. Cơ chế hoạt động của chương trình con Liên quan đến chương trình con (hàm và thủ tục ở trên), chúng ta có một số khái niệm sau: - Biến cục bộ: là biến được khai báo và chỉ sử dụng bên trong thân một chương trình con, là biến r trong ví dụ trên. - Biến toàn cục: là biến được khai báo ở đầu chương trình và có thể được sử dụng bất cứ đâu trong chương trình, là các biến a và b trong ví dụ trên. 69
5. - Tham số hình thức (hay còn được gọi là đối): là các biến được khai báo sau tên của chương trình con (chúng ta sẽ được giới thiệu chi tiết hơn về tham số hình thức trong các phần tiếp theo), là các tham số x và y trong ví dụ trên. - Tham số thực: là các giá trị truyền cho các tham số hình thức tương ứng khi gọi các chương trình con. Chẳng hạn, trong ví dụ trên là các giá trị của biểu thức a+b và a- b. Cơ chế hoạt động của một chương trình con là như sau: chương trình được batứ đầu từ câu lệnh đầu tiên và kết thúc khi thực hiện xong câu lệnh cuối cùng trong thân chương trình, nếu chương trình gặp một lời gọi chương trình con (thủ tục hay hàm) thì máy sẽ thực hiện: - cấp phát bộ nhớ cho các biến cục bộ của chương trình con, - truyền giá trị của các tham số thực cho các tham số hình thức tương ứng, - thực hiện lần lượt các câu lệnh trong thân chương trình con, - giải phóng các biến cục bộ và trở về nơi gọi nó, nếu chương trình con là hàm thì khi trở về mang theo một giá trị. Quay trở lại chương trình chứa thủ tục max2so trên, hoạt động của nó là như sau: - gán giá trị 11.45 cho biến a và –42.7 cho biến b, - gặp lời gọi thủ tục max2so, thực hiện thủ tục max2so: o cấp phát bộ nhớ cho biến cục bộ r và các tham số hình thức x và y, o giá trị của biểu thức a+b và a-b được truyền cho các tham số hình thức x và y, o thực hiện các câu lệnh trong thân thủ tục để tính giá trị lớn nhất chứa trong biến r, o gọi thủ tục Writeln để in ra kết quả, o giải phóng các biến cục bộ r và tham số hình thức x, y, o máy thoát ra khỏi thủ tục để trở về chương trình chính, - kết thúc chương trình chính. Biến toàn cục và biến cục bộ Ở trên chúng ta đã nhắc đến hai khái niệm biến cục bộ và biến toàn cục, trong phần này chúng ta sẽ xem xét một cách chi tiết hơn. Biến toàn cục (global variable) là những biến được khai báo ở đầu chương trình, chúng tồn tại trong suốt thời gian làm việc của chương trình. Biến toàn cục được sử dụng bất kì đâu ở trong chuơnưg trình, nghĩa là trong thân chương trình chính hoặc trong các thân chương trình con. Biến cục bộ (local variable) là biến được khai báo ở đầu một chương trình con. Biến cục bộ được cấp phát bộ nhớ khi chương trình con được gọi tới và bị giải phóng khỏi bộ nhớ khi máy ra khỏi chương trình con. Biến cục bộ chỉ được sử dụng bên trong thân của chương trình con khai báo nó cũng như các chương trình con khác nằm bên trong thân của chương trình con khai báo nó. Để phân biệt rỏ sự khác nhau của biến cục bộ và biến toàn cục, chúng ta quan sát ví dụ sau: 70
6. Program cac_loai_bien; Var x : integer; (* x là biến toàn cục *) (* Khai báo thủ tục M *) Procedure M; Var a, b : integer; (* a và b là biến cục bộ trong M *) (* Khai báo thủ tục M1 *) Procedure M1; Var n : inetger; (* n là biến cục bộ trong M1 *) Begin x := x + 1; (* sử dụng biến toàn cục x *) n := a + b; Writeln(‘n = ’, n); a := a + 1; b := b + 1; End; (* Thân thủ tục M *) Begin a := 1; b := 5; Writeln(‘a = ’, a); Writeln(‘b = ’, b); M1; (* gọi thủ tục M1 *) Writeln(‘a = ’, a); Writeln(‘b = ’, b); End; (* Thân chương trình chính *) Begin x := 10; Writeln(‘x = ’, x); M; (* gọi thủ tục M *) Writeln(‘x = ’, x); End. Trong ví dụ này, chương trình chính chứa thủ tục M, thủ tục M lại chứa thủ tục M1. x là biến toàn cục được khai báo ở đầu chương trình chính, x có thể được sử dụng bất kỳ đâu trong chương trình. a và b là các biến cục bộ khai báo đầu thủ tục M, nên a và b chỉ có thể được sử dụng trong thân thủ tục M và thủ tục M1. n là biến cục bộ khái báo trong thủ tục M1, nên m chỉ có thể được sử dụng trong thân thủ tục M1. Hoạt động của chương trình này là như sau: - bắt đầu chương trình chính, biến x được gán giá trị 10, 71
7. - in x ra màn hình, - gọi thủ tục M, thực hiện các câu lệnh trong thân thủ tục M, o gán biến a bằng 1 và biến b bằng 5, o in ra màn hình giá trị các biến a và b, o gọi thủ tục M1, thực hiện các câu lệnh trong thân thủ tục M1, . biến toàn cục x được tăng lên một đơn vị, . gán biến cục bộ n bằng giá trị biểu thức a+b, . in n ra màn hình, . tăng mỗi biến cục bộ a và b của thủ tục M lên một đơn vị, . kết thúc thủ tục M1, quay trở về thủ tục M, o in ra giá trị của các biến cục bộ a và b, o kết thúc thủ tục M, quay trở về chương trình chính, - in ra giá trị của biến cục bộ x và kết thúc chương trình. Kết quả của chương trình trên là: x = 10 a = 1 b = 5 n = 6 a = 2 b = 6 x = 11 Nhận xét: - Biến cục bộ và tham số hình thức có cơ chế hoạt động giống nhau, chúng chỉ tồn tại trong thời gian chương trình con hoạt động. - Biến toàn cục có thể bị thay đổi giá trị bất cứ đâu trong chương trình, điều này dẫn đến việc sử dung tùy tiện các biến toàn cục sẽ làm cho chương trình rất phức tạp, khó gỡ rối khi có lỗi xảy ra. Vì vậy, nên hạn chế sử dụng biến toàn cục. Cơ chế truyền tham số Ở trong các phần trên, chúng ta đã được giới thiệu cách xây dựng các chương trình con. Sau đó, chúng ta có thể sử dụng (lời gọi chương trình con) chương trình con. Mỗi khi sử dụng chương trình con, thông thường đều phải truyền dữ liệu cho nó. Có các cách truyền dữ liệu cho chương trình con khác nhau sau: - truyền tham số dạng biến toàn cục, - truyền tham số dạng tham trị, - truyền tham số dạng tham biến. D. Truyền tham số dạng biến toàn cục Do phạm vi sử dụng của biến toàn cục là bất kỳ mọi nơi trong chương trình nen ta có thể sử dụng chúng đẻ truyền dữ liệu cho các chương trình con cũng như nhận kết quả tính được từ các chương trình con. 72
8. Ví dụ chương trình giải phương trình bậc hai (ax2 + bx + c = 0) dưới đây truyền tham số bằng biến toàn cục. Trong ví dụ này, để giảm bớt phức tạp, chúng ta không xét đến các trường hợp suy biến của phương trình bậc 2. Program Phuong_trinh_bac_2; Var a, b, c, x1, x2, delta : real; Procedure gptb2; Var r : real; Begin delta := b*b – 4*a*c; if delta >= 0 then Begin r := sqrt(delta); x1 := (-b-r)/(2*a); x2 := (-b+r)/(2*a); End; End; (* Thân chương trình *) Begin Write(‘a = ’); readln(a); Write(‘b = ’); readln(b); Write(‘c = ’); readln(c); gptb2; (* gọi thủ tục gptb2 *) if (delta 0) then Writeln(‘Phương trình có hai nghiệm: x1 = ’, x1:5:2, ‘x2 = ’, x2:5:2); End. Trong ví dụ trên, thủ tục gptb2 sử dụng 6 biến toàn cục của chương trình chính , các biến a, b, c truyền dữ liệu cho thủ tục, còn các biến x1, x2, delta nhận giá trị từ thủ tục. Nhận xét: Cách truyền tham số dùng biến toàn cục rất là đơn giản, tuy nhiên phương pháp này có nhược điểm rất lớn: vì chương trình con sử dụng biến toàn cục nên khi viết chương trình con phải luôn luôn nhớ toiư các biến này, nếu có sự thay đổi biến toàn cục trong chương trình chính thì phải thay đổi tương ứng trong chương trình con. Ngoài ra, cách sử dụng biến toàn cục như thế này rất khó để kiểm soát giá trị của chúng nên điều này thường dẫn đến sai sót. Do những nhược điểm như vây, nên người ta khuyến khích người lập trình không sử dụng phương pháp truyền tham số bằng biến toàn cục. Phương pháp dưới đây sẽ khắc phục nhược điểm trên. 73
9. E. Truyền tham số dạng tham trị Chúng ta cần nhắc lại rằng, đối với chương trình con có hai loại tham số. Tham số hình thức là các biến khai báo sau tên chương trình con, tham số thực là các giá trị hay biến truyền cho các tham số hình thức tương ứng khi gọi chương trình con. Tham số hình thức được chia làm hai dạng: tham trị và tham biến. Trước hết chúng ta sẽ xét đến dạng tham trị. Các tham số hình thức dạng tham trị được khai báo sau tên chương trình con giữa hai dấu ngoặc theo mẫu sau: danh_sách_tham_số : kiểu; danh_sách_tham_số : kiểu; Ví dụ: Function ham (x, y : real; a, b : real) : real; Procedure thutuc (x : real; a, b, c : real); Khi có lời gọi chương trình con, các tham số thực sẽ được truyền cho các tham số hình thức. Các tham số thực phải là một biểu thức cùng kiểu với tham số hình thức tương ứng. Chẳng hạn, nếu tham số hình thức có kiểu nguyên thì tham số thực phải là một biểu thức kiểu nguyên. Bây giờ chúng ta viết lại chương trình giải phương trình bậc 2 sử dụng tham số dạng tham trị như sau: Program Phuong_trinh_bac_2; Var x, y, z : real; Procedure gptb2(a, b, c : real); Var x1, x2, delta, r : real; Begin delta := b*b – 4*a*c; if delta 0) then Writeln(‘PT có hai nghiệm: x1 = ’, x1:5:2, ‘x2 = ’, x2:5:2); End; End; (* Thân chương trình chính *) Begin Write(‘x = ’); readln(x); 74
10. Write(‘y = ’); readln(y); Write(‘z = ’); readln(z); gptb2(x, y, z); (* gọi thủ tục gptb2 *) End. Cơ chế hoạt động của một chương trình sử dụng tham số dạng tham trị là như sau: khi chương trình gặp một lời gọi tới chương trình con, máy sẽ: - cấp phát bộ nhớ cho biến cục bộ và các tham số hình thức dạng tham trị của chương trình con, trong ví dụ trên là cấp phát cho các biến x1, x2, delta, r và các tham số hình thức a, b, c, - truyền giá trị của các tham số thực cho các tham số dạng tham trị tương ứng, các giá trị x, y, z, được truyền vào tương ứng cho a, b, c, - thực hiện các câu lệnh trong chương trình con, - kết thúc chương trình con, máy sẽ giải phóng các biến cục bộ và các tham số hình thức, như thế các giá trị đặt trong các biến cục bộ và các tham số hình thức không thể đưa về để sử dụng trong một chương trình khác. Nhận xét: các tham số hình thức dạng tham trị chỉ được sử dụng trong chương trình con khai báo chúng. F. Truyền tham số dạng tham biến Trong ví dụ trên, các nghiệm của phương trình được in ra ngay trong thủ tục. Tuy nhiên, nếu chúng ta muốn chương trình phải trả về nghiệm của phương trình và việc in sẽ được thực hiện trong chương trình chính thì cách sử dụng tham số dạng tham trị không giải quyết được. Trong trường hợp này, chúng ta sử dụng tham số dạng tham biến, tức là giá trị của tham số vẫn được sử dụng sau khi ra khỏi chương trình con. Các tham số dạng tham biến được khai báo sau tên chương trình con giữa hai dấu ngoặc theo mẫu sau (với từ khóa Var): Var danh_sách_tham_số : kiểu; Var danh_sách_tham_số : kiểu; Ví dụ: Function (x,y : real; Var a : real; Var p,q : real) : real; Khi có lời gọi chương trình con, các tham số thực sẽ được truyền cho các tham số hình thức. Các tham số thực phải là một biến hay phần tử mảng có cùng kiểu với tham số hình thức tương ứng. Chẳng hạn, nếu tham số hình thức có kiểu nguyên thì tham số thực phải là một biến kiểu nguyên. Chúng ta viết lại chương trình giải phương trình bậc 2, trong đó thủ tục gptb2 nhận 3 tham số dạng tham trị là a, b, c, trả về ba giá trị bởi tham biến là delta, x1, x2. Program Phuong_trinh_bac_2; Var x, y, z, d, n1, n2 : real; Procedure gptb2(a, b, c : real; Var delta, x1, x2 : real); Var r : real; Begin delta := b*b – 4*a*c; if delta >= 0 then 75
11. Begin r := sqrt(delta); x1 := (-b-r)/(2*a); x2 := (-b+r)/(2*a); End; End; (* Thân chương trình chính *) Begin Write(‘x = ’); readln(x); Write(‘y = ’); readln(y); Write(‘z = ’); readln(z); gptb2(x, y, z, d, n1, n2); (* gọi thủ tục gptb2 *) if (d 0) then Writeln(‘Phương trình có hai nghiệm: x1 = ’, n1:5:2, ‘x2 = ’, n2:5:2); End. Đối với chương trình con sử dụng tham số dạng tham biến, thì khi gặp lời gọi chương trình con, máy sẽ: - cấp phát bộ nhớ cho các biến cục bộ và các tham số dạng tham trị và tham biến, - truyền giá trị của tham số thực cho các tham số dạng tham trị tương ứng, - truyền địa chỉ của các biến tham số thực cho các tham số dạng tham biến, - thực hiện các câu lệnh trong thâm chương trình con Như thế, đối với các tham số dạng tham biến, thay vì truyền giá trị của tham số thực thì phải truyền địa chỉ của biến tham số thực. Vì vậy, mọi sự thay đổi giá trị của tham biến trong chương trình con sẽ kéo theo sự thay đổi của biến tham số thực. Trong ví dụ trên, mọi thay đổi giá trị trên các biến d, n1, n2 trong chuơng trình con cũng sẽ có hiệu lực sau khi đã thoát ra khỏi chương trình con. Đệ quy Một chương trình con được gọi là đệ quy (recursivity) nếu trong thân chương trình con đó có lời gọi đến chính nó. Nhiều ngôn ngữ lập trình cho phép xây dựng các chương trình con đệ quy. Chúng ta lấy ví dụ tính giai thừa của một số nguyên n. Giai thừa n được định nghĩa như sau: n! = 1.2.3 (n-1).n hoặc 1 nếu n = 0 n! = n.(n-1)!nếu n 1 76
12. Trong cách định nghĩa sau, cách tính n! phụ thuộc vào (n-1)!. Với định nghĩa này chúng ta xây dựng hàm đệ quy tính n! bằng ngôn ngữ Pascal như sau: Function giai_thua1(n : longint) : longint; Begin if n = 0 then giai_thua1 := 1; else giai_thua1 := n * giai_thua1(n-1); End; Như thế, chúng ta nhận thấy hàm giai_thua1 được gọi trong khi định nghĩa chính nó. Mỗi lời gọi đệ quy cũng như lời gọi chương trình con, máy phải cấp phát bộ nhớ cho các biến cục bộ, và sau khi kết thúc thì phải giải phóng chúng. Với một chương trình con đệ quy thì có thể có nhiều lần gọi, vì vậy có bao nhiêu lần gọi thì cũng có bấy nhiêu lần cấp phát và giải phóng các biến cục bộ. Quá trình giải phóng các biến cục bộ được thực hiện theo thứ tự ngược lại quá trình cấp phát chúng: các biến cục bộ được tạo ra trước sẽ được giải phóng sau. Như thế, đối với một chương trình con đệ quy thì sẽ cần rất nhiều bộ nhớ cho các biến cục bộ. Thậm chí nếu chương trình con đệ quy thực hiện lời gọi đệ quy không dừng thì sẽ dẫn đến tình trạng tràn bộ nhớ. Chẳng hạn, nếu người sử dụng gọi hàm giai_thua1 trên như sau: n = giai_thua1(-1); thì sẽ bị lỗi tràn bộ nhớ. Tuy nhiên, chúng ta có thể dễ dàng nhận thấy rằng để tính n! chúng ta có thể sử dụng vòng lặp thay vì đệ quy như sau: Function giai_thua2(n : longint) : longint; Var i, gt : longint; Begin gt := 1; if n > 0 then for i : = 1 to n do gt := gt * i; giai_thua2 := gt; End; Bây giờ nếu, chúng ta phân tích hai lời gọi chương trình con sau: n = giai_thua1(100); n = giai_thua2(100); Với lời gọi thứ nhất, hàm giai_thua1 được gọi đệ quy đến 100 lần, và mỗi lần gọi cần cấp phát 4 byte cho tham số n kiểu longint, như thế cần 400 byte bộ nhớ. Trong khi với lời gọi thứ hai, hàm giai_thua2 chỉ được gọi 1 lần, chỉ cần cấp phát 12 byte bộ nhớ cho tham số n và hai biến cục bộ i, gt kiểu longint. Một ví dụ thứ hai minh họa chương trình con đệ quy. Ước số chung lớn nhất của hai số nguyên a và b được xác định theo công thức: - nếu x = y thì usc(x, y) = x - nếu x > y thì usc(x, y) = usc(x-y, y) - nếu x < y thì usc(x, y) = usc(x, y-x) Hàm đệ quy usc được viết như sau: 77
13. Function usc(a, b : int) : int; Begin if x = y then usc := x; else if x > y then usc := usc(x – y, y); else usc := usc(x, y - x); End; Nhận xét: Phương pháp đệ quy cho phép viết chương trình ngắn gọn đơn giản, nhưng lại không hiệu quả về mặt sử dụng tài nguyên bộ nhớ. Tính ưu việt của chương trình con Hầu hết tất cả các ngôn ngữ lập trình đều sử dụng khái niệm chương trình con. Chương trình con chỉ định nghĩa một lần nhưng sao đó được sử dụng nhiều lần. Việc viết chương trình sử dụng chương trình con chúng ta nhận thấy có các ưu điểm sau: - giảm bớt số dòng lệnh của một chương trình, - giảm thời gian lập trình, - giảm độ phức tạp của chương trình, - chương trình được tổ chức theo dạng tập hợp các chương trình con, nên dễ quản lý hơn, - dễ sữa đổi chương trình khi cần thiết, - dễ kiểm tra lỗi. Bài tập 1. Hai khái niệm hàm và thủ tục khác nhau chổ nào? 2. Tại sao không nên sử dụng biến toàn cục? 3. Viết thủ tục giải phương trình trùng phương ax4 + bx2 + c = 0. 4. Viết hàm tính giá trị lớn nhất (nhỏ nhất) của một dãy số. 5. Viết hàm hay thủ tục giải hệ phương trình bậc nhất: ax + by = p cx + dy = q 6. Viết hàm đệ quy tính: P(n) = 1 + 22 + 32 + + n2 7. Viết chương trình sử dụng hàm đệ quy đẻ tạo ra dãy số Fibonacci F1, F2, Fn được định nghĩa như sau: F1 = 1, F2 = 1 Fn = Fn-1 + Fn-2 Ví dụ: 1, 1, 2, 3, 5, 8, 13, 21, 8. Hãy viết lại hàm tính ước số chung lớn nhất của hai số nguyên sử dụng vòng lặp. 78
14. BÀI 4 ĐẶC TRƯNG CÚ PHÁP VÀ NGỮ NGHĨA CHƯƠNG TRÌNH Mã bài:ITPRG3-06.4 Giới thiệu Bài học sẽ trình bày tổng quan các vấn đề liên quan đến ngôn ngữ lập trình. Chẳng hạn, một ngôn ngữ lập trình được xây dựng như thế nào, làm sao để máy tính có thể hiểu được một chương trình nào đó, Như thế, việc hiểu được bản chất của ngôn ngữ lập trình sẽ giúp cho người lập trình viết các chương trình hữu hiệu hơn. Mục tiêu thực hiện - Hiểu được cú pháp của các ngôn ngữ - Nắm các đặc trưng mang tính ngữ nghĩa của chương trình - Nắm các tiền đề cho sự phát triển của chương trình qua ngữ pháp và ngữ nghĩa - Viết chương trình có khả năng thân thiện hơn Nội dung chính Trình bày ngắn gọn cách định nghĩa, xây dựng một ngôn ngữ lập trình, cách phân tích một chương trình, các thành phần cần thiết để phân tích một chương trình. Khái niệm ngôn ngữ Một ngôn ngữ dù là ngôn ngữ tự nhiên như tiếng Việt hay là ngôn ngữ lập trình như Pascal, cũng đều có thể xem là một tập hợp các câu có cấu trúc quy định nào đó. Cấu trúc câu được quy định ra sao thì đó là vấn đề cách biểu diễn ngôn ngữ. Chúng ta có thể nhận xét thấy rằng, một câu của ngôn ngữ, dù là câu tiếng Việt “bạn đi học” hay cả một văb bản chương trình từ chữ “Program” cho đến dấu chấm “.” kết thúc chương trình, thì cũng đều chẳng qua là một dãy các xâu/từ có sẵn như “bạn”, “đi”, “học”, hay “Program”, được liệt kê trong một bảng chữ nào đó, mà ta có thể xem là các kí hiệu cơ bản của ngôn ngữ. Từ nhận xét trên đây, chúng ta đi đến một số khái niệm hình thức về ngôn ngữ như dưới đây. Bảng chữ (alphabet) là một tập hợp các kí hiệu. Ví dụ: {a, b, c, , z} : bảng chữ cái Latin {0,1, 2, , 9} : bảng chữ số thập phân {0,1} : bảng chữ số nhị phân Xâu (string) là một dãy hữu hạn các kí hiệu từ bảng chữ cái. Ví dụ, với bảng chữ {0, 1} thì các xâu là 0, 1, 00, 01, 11, 001, 000, Một cách không hình thức, ngôn ngữ (language) là một tập hợp các xâu trên một bảng chữ cái. Ví dụ, với bảng chữ {0, 1} thì ngôn ngữ trên bảng chữ này là tập hợp {0, 1, 00, 01, 11, 001, 000, }. Cụ thể, ngôn ngữ lập trình là một hệ thống gồm các kí hiệu và các quy tắc kết hợp các kí hiệu thành một cấu trúc có ý nghĩa. Phần cú pháp (syntax) qui định sự kết hợp các kí hiệu, còn phần ngữ nghĩa qui định ý nghĩa của mỗi sự kết hợp đó. Sau đây là một ví dụ về các khía cạnh cú pháp và ngữ nghĩa trong ngôn ngữ lập trình. Chúng ta có các biểu thức sau: 79
15. bt1 = 2 bt2 = 1 + 1 bt3 = 1 * 2 Cả ba biểu thức trên có cùng giá trị, tức giống nhau về mặt ngữ nghĩa, tuy nhiên chúng khác nhau về mặt cú pháp. 1. Định nghĩa cú pháp Trước hết, phần này sẽ trình bày chi tiết hơn về khai niệm cú pháp, văn phạm là cơ chế để mô tả ngôn ngữ. G. Văn phạm phi ngữ cảnh Ðể xác định cú pháp của một ngôn ngữ, người ta dùng văn phạm phi ngữ cảnh CFG (Context Free Grammar). Văn phạm phi ngữ cảnh bao gồm bốn thành phần: 1. Một tập hợp các token , gọi là các ký hiệu kết thúc (terminal symbols). Ví dụ: Các từ khóa, các chuỗi, dấu ngoặc đơn, 2. Một tập hợp các ký hiệu chưa kết thúc (nonterminal symbols), còn gọi là các biến (variables) Ví dụ: Câu lệnh, biểu thức, 3. Một tập hợp các luật sinh (productions) trong đó mỗi luật sinh bao gồm một ký hiệu chưa kết thúc - gọi là vế trái, một mũi tên và một chuỗi các token và / hoặc các ký hiệu chưa kết thúc gọi là vế phải. 4. Một trong các ký hiệu chưa kết thúc được dùng làm ký hiệu bắt đầu của văn phạm. Chúng ta qui ước: - Mô tả văn phạm bằng cách liệt kê các luật sinh. - Luật sinh chứa ký hiệu bắt đầu sẽ được liệt kê đầu tiên. - Nếu có nhiều luật sinh có cùng vế trái thì nhóm lại thành một luật sinh duy nhất, trong đó các vế phải cách nhau bởi ký hiệu “ | “ đọc là “hoặc”. Ví dụ 4.1: Xem biểu thức là một danh sách của các số phân biệt nhau bởi dấu + và dấu -. Ta có, văn phạm với các luật sinh sau sẽ xác định cú pháp của biểu thức. list list + digit list list – digit list digit digit 0 | 1 | 2 | | 9 Như vậy văn phạm phi ngữ cảnh ở đây là: - Tập hợp các ký hiệu kết thúc: 0, 1, 2, , 9, +, - - Tập hợp các ký hiệu chưa kết thúc: list, digit. - Các luật sinh đã nêu trên. - Ký hiệu chưa kết thúc bắt đầu: list. Ví dụ 4.2 Từ ví dụ 2.1 ta thấy: 9 - 5 + 2 là một list vì: 9 là một list vì nó là một digit. 9 - 5 là một list vì 9 là một list và 5 là một digit. 80
16. 9 - 5 + 2 là một list vì 9 - 5 là một list và 2 là một digit. Ví dụ 4.3: Một list là một chuỗi các lệnh, phân cách bởi dấu ; của khối begin - end trong Pascal. Một danh sách rỗng các lệnh có thể có giữa begin và end. Chúng ta xây dựng văn phạm bởi các luật sinh sau: block begin opt_stmts end opt_stmts stmt_list |  stmt_list stmt_list ; stmt | stmt Trong đó opt_stmts (optional statements) là một danh sách các lệnh hoặc không có lệnh nào ( ). Luật sinh cho stmt_list giống như luật sinh cho list trong ví dụ 2.1, bằng cách thay thế +, - bởi ; và stmt thay cho digit. H. Cây phân tích cú pháp (parsing tree) Cây phân tích cú pháp minh họa ký hiệu ban đầu của một văn phạm dẫn đến một chuỗi trong ngôn ngữ. Nếu ký hiệu chưa kết thúc A có luật sinh A XYZ thì cây phân tích cú pháp có thể có một nút trong có nhãn A và có 3 nút con có nhãn tương ứng từ trái qua phải là X, Y, Z. Hình 4.1 Cây phân tích cú pháp nhãn A Một cách hình thức, cho một văn phạm phi ngữ cảnh thì cây phân tích cú pháp là một cây có các tính chất sau đây: 1. Nút gốc có nhãn là ký hiệu bắt đầu. 2. Mỗi một lá có nhãn là một ký hiệu kết thúc hoặc một  . 3. Mỗi nút trong có nhãn là một ký hiệu chưa kết thúc. 4. Nếu A là một ký hiệu chưa kết thúc được dùng làm nhãn cho một nút trong nào đó và X1 Xn là nhãn của các con của nó theo thứ tự từ trái sang phải thì A X1X2 Xn là một luật sinh. Ở đây X1, , Xn có thể là ký hiệu kết thúc hoặc chưa kết thúc. Ðặc biệt, nếu A  thì nút có nhãn A có thể có một con có nhãn  . 1. Các vấn đề cú pháp Sự nhập nhằng của văn phạm Một văn phạm có thể sinh ra nhiều hơn một cây phân tích cú pháp cho cùng một chuỗi nhập thì gọi là văn phạm nhập nhằng. Ví dụ 4.4: Giả sử chúng ta không phân biệt một list với một digit, xem chúng đều là một string ta có văn phạm: string string + string | string - string | 0 | 1 | | 9. Với văn phạm này thì chuỗi biểu thức 9 - 5 + 2 có đến hai cây phân tích cú pháp như 81
17. sau : Hình 4.2 Hai cây phân tích cú pháp Tương tự với cách đặt dấu ngoặc vào biểu thức như sau : (9 - 5) + 2 9 - ( 5 + 2) Bởi vì một chuỗi với nhiều cây phân tích cú pháp thường sẽ có nhiều nghĩa, do đó khi biên dịch các chương trình ứng dụng, chúng ta cần thiết kế các văn phạm không có sự nhập nhằng hoặc cần bổ sung thêm các qui tắc cần thiết để giải quyết sự nhập nhằng cho văn phạm. Sự kết hợp của các toán tử Thông thường, theo quy ước ta có biểu thức 9 + 5 + 2 tương đương (9 + 5) + 2 và 9 - 5 - 2 tương đương với (9 - 5) - 2. Khi một toán hạng như 5 có hai toán tử ở trái và phải thì nó phải chọn một trong hai để xử lý trước. Nếu toán tử bên trái được thực hiện trước ta gọi là kết hợp trái. Ngược lại là kết hợp phải. Thường thì bốn phép toán số học: +, -, *, / có tính kết hợp trái. Các phép toán như số mũ, phép gán bằng (=) có tính kết hợp phải. Ví dụ 4.5 : Trong ngôn ngữ C, biểu thức a = b = c tương đương a = ( b = c) vì chuỗi a = b = c với toán tử kết hợp phải được sinh ra bởi văn phạm: right letter = right | letter letter a | b | | z Ta có cây phân tích cú pháp có dạng như sau (chú ý hướng của cây nghiêng về bên phải trong khi cây cho các phép toán có kết hợp trái thường nghiêng về trái): 82
18. Thứ tự ưu tiên của các toán tử Xét biểu thức 9 + 5 * 2. Có 2 cách để diễn giải biểu thức này, đó là 9 + (5 * 2) hoặc ( 9 + 5) * 2. Tính kết hợp của phép + và * không giải quyết được sự mơ hồ này, vì vậy cần phải quy định một thứ tự ưu tiên giữa các loại toán tử khác nhau. Thông thường trong toán học, các toán tử * và / có độ ưu tiên cao hơn + và -. Cú pháp cho biểu thức Văn phạm cho các biểu thức số học có thể xây dựng từ bảng kết hợp và ưu tiên của các toán tử. Chúng ta có thể bắt đầu với bốn phép tính số học theo thứ bậc sau : Kết hợp trái +, - Thứ tự ưu tiên Kết hợp trái *, / từ thấp đến cao Chúng ta tạo hai ký hiệu chưa kết thúc expr và term cho hai mức ưu tiên và một ký hiệu chưa kết thúc factor làm đơn vị phát sinh cơ sở của biểu thức. Ta có đơn vị cơ bản trong biểu thức là số hoặc biểu thức trong dấu ngoặc. factor digit | (expr) Phép nhân và chia có thứ tự ưu tiên cao hơn đồng thời chúng kết hợp trái nên luật sinh cho term tương tự như cho list : term term * factor | term / factor | factor Tương tự, ta có luật sinh cho expr : expr expr + term | expr - term | term Vậy, cuối cùng ta thu được văn phạm cho biểu thức như sau : expr expr + term | expr - term | term term term * factor | term / factor | factor factor digit | (expr) Như vậy: Văn phạm này xem biểu thức như là một danh sách các term được phân cách nhau bởi dấu + hoặc -. Term là một list các factor phân cách nhau bởi * hoặc /. Chú ý rằng bất kỳ một biểu thức nào trong ngoặc đều là factor, vì thế với các dấu ngoặc chúng ta có thể xây dựng các biểu thức lồng sâu nhiều cấp tuỳ ý. Cú pháp các câu lệnh Từ khóa (keyword) cho phép chúng ta nhận ra câu lệnh trong hầu hết các ngôn ngữ. Ví dụ trong Pascal, hầu hết các lệnh đều bắt đầu bởi một từ khóa ngoại trừ lệnh gán. Một số lệnh Pascal được định nghĩa bởi văn phạm (nhập nhằng) sau, trong đó id chỉ một danh biểu (tên biến). stmt id := expr 83
19. | if expr then stmt | if expr then stmt else stmt | while expr do stmt | begin opt_stmts end Ký hiệu chưa kết thúc opt_stmts sinh ra một danh sách có thể rỗng các lệnh, phân cách nhau bởi dấu chấm phẩy (;). Dạng chuẩn Backus-Naur Thông thường để mô tả cú pháp của các ngôn ngữ lập trình người ta sử dụng dạng chuẩn Backus-Naur (Backus-Naur Form, viết tắt là BNF). Một văn phạm được định nghĩa bởi BNF gồm một dãy các quy tắc. Mỗi quy tắc gồm vế trái, dấu định nghĩa ::= (đọc được định nghĩa bởi) và vế phải. Vế trái là một kí hiệu phải được định nghĩa, còn vế phải là một dãy các kí hiệu, hợac được thừa nhận hoặc đã được định nghĩa từ trước đó, tuân theo một quy ước nào đó. BNF dùng các kí tự quy ước như sau: Kí hiệu Ý nghĩa ::=, hoặc , hoặc = được định nghĩa là { } chuỗi của 0 hoặc nhiều mục liệt kê tùy chọn [ ] hoặc 0 hoặc 1 mục liệt kê tùy chọn mục liệt kê phải được thay thế | hoặc (theo nghĩa loịa trừ) Các quy tắc BNF định nghĩa tên trong Pascal: ::= { | } ::= ‘A’ | | ‘Z’ | ‘a’ | | ‘z’ ::= ‘)’ | | ‘9’ Ví dụ văn phạm của một ngôn ngữ lập trình đơn giản dang BNF như sau: ::= program end ::= := ; ::= while do done ::= | + | ::= | ::= | | ::= | ::= ‘A’ | | ‘Z’ | ‘a’ | | ‘z’ ::= ‘)’ | | ‘9’ Một xâu, tức là một chương trình đơn giản, viết trong văn phạn được định nghĩa ở trên như sau: program i := 1; while i <= 10 do i := i + 1 done 84
20. end 1. Phân tích cú pháp Một ngôn ngữ lập trình, như trình bày ở phần trên, được thường định nghĩa bởi cú pháp hay văn phạm của nó bởi dạng chuẩn BNF. Sau đó, khi người lập trình sử dụng ngôn ngữ để viết chương trình, người lập trình phải tuân theo văn phạm đã được định nghĩa. Để kiểm tra xem một chương trình có đúng cú pháp hay không thì cần phải thực hiện phân tích cú pháp. Phân tích cú pháp là quá trình xác định xem một xâu/câu có thể được sinh ra từ một văn phạm cho trước không. Cụ thể, phân tích cú pháp của một chương trình là xác định xem từng câu lệnh của chương trình có được sinh ra bởi cú pháp của ngôn ngữ lập trình đó không. Trong phần này, chúng ta chỉ giới thiệu sơ bộ về quá trình phân tích cú pháp. Vấn đề này sẽ được trình bày đầy đủ hơn trong bài cuối cùng của môn học. Có nhiều phương pháp phân tích cú pháp khác nhau. Tuy nhiên, các phương pháp này đều nằm trong hai lớp: từ trên xuống (top down) và từ dưới lên (bttom-up). Để xác định xem một chương trình nguồn có được sinh ra từ một văn phạm hay không, các phương pháp phân tích cú pháp thường xây dựng cây phân tích của chương trình nguồn dựa trên văn phạm. Nếu tồn tại cây phân tích thì ta nói chương trình được sinh ra bởi văn phạm hay chương trình đúng cú pháp, ngược lại thì chương trình nguồn là không đúng cú pháp. Để xây dựng cây phân tích cho một chương trình nguồn, chúng ta có thể tiến hành hai cách cơ bản tương ứng với hai lớp các phương pháp phân tích cú pháp. Phương pháp phân tích từ trên xuống sẽ bắt đầu xây dựng cây phân tích từ các lá đi đến đỉnh của một câu hay chương trình cho trước. Ngược lại, phương pháp phân tích từ dưới lên sẽ bắt đầu xây dựng cây phân tích từ đỉnh đến các lá của một câu hay chương trình cho trước. Đối với mỗi lớp phương pháp phân tích cú pháp, có nhiều phương pháp khác nhau: - Phân tích cú pháp từ trên xuống gồm: o Phân tích đệ quy đi xuống: phương pháp này thực hiện việc xây dựng cây phân tích từ gốc đến lá và có khả năng quay lui (backtracking). o Phân tích cú pháp đoán nhận trước: phương này phân tích từ trên xuống nhưng không bị quay lui. o Phân tích cú pháp đoán nhận trước không đệ quy: phương này sử dụng ngăn xếp (stack) thay vì quay lui. - Phân tích cú pháp từ dưới lên gồm: o Phân tích cú pháp thứ tự yếu o Phân tích cú pháp LR Dưới đây là một ví dụ đơn giản minh họa phân tích cú pháp. Chúng có văn phạm G định nghĩa ngôn ngữ sau: + - 0 85
21. 9 Chương trình nguồn là biểu thức: 9 – 5 + 3. Thực hiện việc phân tích cú pháp sẽ tạo được cây phân tích như sau: Như thế, chương trình nguồn 9 – 5 + 3 là đúng đắn về mặt cú pháp. 4. Ngữ nghĩa hình thức Căn cứ vào cú pháp của ngôn ngữ lập trình, người lập trình viết chương trình gồm các câu lệnh theo trình tự cho phép để giải quyết bài toán đặt ra. Để đạt được mục đích đó, mỗi câu lệnh viết ra không những chỉ đúng đắn về mặt cú pháp mà còn phải đúng đắn về mặt ngữ nhĩa (semantic) hay ý nghĩa logic câu lệnh. Tính đúng đắn về mặt ngữ nghĩa cho phép giải quyết được bài toán, chương trình chạy luôn dừng, ổn định và cho kết quả phù hợp với yêu cầu đặt ra. Ngữ nghĩa không chỉ là cơ sở cho việc chứng minh tính đúng đắn của chương trình mà còn có ích cho quá trình thiết kế và cài đặt ngôn ngữ lập trình. Trong bài học này sẽ giới thiệu hai loại ngữ nghĩa hình thức: ngữ nghĩa tiên đề (axiomatic semantics) và ngữ nghĩa biểu thị (denotationnal semantics). 5. Ngữ nghĩa tiên đề Ngữ nghĩa của phát biểu Ngữ nghĩa của phát biểu đượcđặc tả bởi biểu thức sau: { P } S { Q } trong đó P là điều kiện về trị các biến trước khi thực thi S, gọi là điều kiện trước (precondition) của S; Q là điều kiện về trị các biến sau khi thực thi S, gọi là hậu điều kiện (postcondition) của S. Diễn dịch đặc tả trên: nếu P đúng thì sau khi S được thực hiện xong ta có Q đúng. Nếu với điều kiện sau bất kỳ của S, ta biết được những điều kiện trước sao cho khi S được thực hiện xong điều kiện sau trên được thỏa mãn, thì ta nói biết được ngữ nghĩa của S. Điều kiện P2 gọi là yếu hơn P1 nếu P1 P2. Điều kiện trước ở đặc tả của phát biểu càng yếu, ngữ nghĩa của phát biểu càng rõ. Với điều kiện sau Q của S, chúng ta kí hiệu p (S, Q) là điều kiện trước yếu nhất bảo đảm Q đúng sau khi được thực hiện xong. Hàm p (S, Q) với Q là biến số có thể xem là ngữ nghĩa chính xác của S. Ví dụ: p (n := n +1, n > 0) = n 0 (n nguyên). 86
22. Với mọi điều kiện trước P về n thỏa mãn đặc tả: { P } n : = n + 1 { n > 0 } ta đều có P n 0. Hệ luật Hoare Ngữ nghĩa tiên đề được phát triển dựa trên hệ luật Hoare. Hệ luật Hoare gồm các tiên đề và luật suy dẫn về ngữ nghĩa của phát biểu theo đặc tả vừa được trình bày ở trên. Trong hệ luật Hoare, các kí hiệu , ,  lần lượt tương ứng với các phép toán logic NOT, AND, OR. Kí hiệu  được sử dụng làm kí hiệu định nghĩa. Luật L1: Nếu ( {P} S {Q})  (Q R) thì {P} S {R} Luật L2: Nếu ( {P} S {Q})  (R P) thì {R} S {Q} Luật L3: (tiên đề về phép gán) { Px->E} x := E {P} ở đây E là biểu thức và Px->E là P trong đó x được thay bằng E. Ví dụ 4.6, chứng minh tính đúng đắn của đặc tả: { f = i!} i := i +1 {f * i = i!} trong ví dụ này ta có: P  f * i = i! E  i + 1 Pi->E  f * (i + 1) = (i + 1)! Theo L3 chúng ta có: {f * (i + 1) = (i + 1) !} i := i + 1 {f * i = i!} Vì f = i! f * (i + 1) = (i + 1)! nên theo L2 chúng ta có điều phải chứng minh. Ví dụ 4.7, chứng minh tính đúng đắn của đặc tả: { f * i = i!} f := f * i {f = i!} ở đây: P  f = i! E  f * i Pi->E  f * i = i! Luật L3 cho chúng ta điều phải chứng minh. Luật L4: (luật về câu lệnh ghép) Nếu ({P} S1 {Q})  ({Q} S2 {R}) thì {P} S1 ; S2 {R} Ví dụ 4.8, chứng minh tính đúng đắn của đặc tả: {f = i!} i := i + 1; f = f * i {f = i!} Theo ví dụ 4.6 và 4.7chúng ta có: { f = i!} i := i +1 {f * i = i!}  { f * i = i!} f := f * i {f = i!} Áp dụng L4 cho chúng ta điều phải chứng minh. 87
23. Luật L5: (luật về phát biểu IF) Nếu ({P  B} S1 {Q})  ({P  B} S2 {Q}) thì {P} if B then S1 else S2 {Q} Luật L6: (luật về phát biểu IF không có thành phần ELSE) Nếu ({P  B} S1 {Q})  ({P  B} Q) thì {P} if B then S1 {Q} Ví dụ 4.9, chứng minh tính đúng đắn của đặc tả: {x.y y then max := x else max := y {max > 0} Áp dụng L3 ta có: { x > 0 } max := x {max > 0} Vì (x.y y) x > 0 nên theo L2 ta có: {(x.y y)} max := x {max > 0} (*) Tương tự theo L3 và L2 ta có: {(x.y 0} ( ) Áp dụng L5 cho (*) và ( ) với: P  x.y y Q  max > 0 S1  max := x S2  max := y chúng ta có điều phải chứng minh. Luật L7: (luật về vòng lặp WHILE) Nếu {P  B} S {Q} thì {P} while B do S {P  B} P được gọi là bất biến của vòng lặp. Ví dụ 4.10: chứng minh tính đúng đắn của đặc tả: {f = i!} while i n do begin i := i + 1, f := f*i {f = n!} Theo ví dụ 4.8 ta có: {f = i!} i = i +1; f := f*i {f = i!} Vì (f = i!)  (i n) f = i! Nên theo L2 ta có: {(f = i!)  (i n)} i = i +1; f := f*i {f = i!} Áp dụng L7 với: P  f = i! B  (i n) S  i := i + 1, f := f*i ta có: {f = i!} while i n do begin i := i + 1, f := f*i {(f = i!)  (i = n)} mà: (f = i!)  (i = n) f = n! 88
24. nên theo L1 chúng ta suy ra được điều phải chứng minh. 5. Ngữ nghĩa biểu thị Ở ngữ nghĩa biểu thị, ngữ nghĩa của mỗi cấu trúc cú pháp được đặc tả bằng một ánh xạ, gọi là hàm ngữ nghĩa (semantic function), từ miền cú pháp (semantic domain) vào miền ngữ nghĩa (semantic domain). Như thế, chúng ta nhận thấy, ngữ nghĩa biểu thị chỉ ra ngữ nghĩa của mỗi cấu trúc cú pháp, tưca là mỗi cấu trúc cú pháp có một ngữ nghĩa nhất định. Chúng ta sẽ lấy một ví dụ đơn giản: mô tả hình thức ngữ nghĩa của ngôn ngữ gồm các số nhị phân bằng ngữ nghĩa biểu thị. Ngôn ngữ số nhị phân là ngôn ngữ chỉ gồm các số nhị phân ‘0’ và ‘1’. Ngữ nghĩa của của số nhị phân chính là giá trị thập phân của số nhị phân đó. Như thế, miền cú pháp là tập hợp các số nhị phân, còn miền ngữ nghĩa là tập hợp các số tự nhiên (giá trị của các số nhị phân). Cú pháp và ngữ nghĩa của ngôn ngữ số nhị phân được định nghĩa như sau: Cú pháp: N Nml số nhị phân N ::= 0 | 1 | N0 | N1 Miền ngữ nghĩa: N = {0, 1, 2, } số tự nhiên Hàm ngữ nghĩa:  : Nml N [[ 0 ]] = 0 [[ 1 ]] = 1 [[ N 0 ]] = 2 * [[N]] [[ N 0 ]] = 2 * [[N]] + 1 Trong đó, tập hợp các số nhị phân Nml là miền cú pháp, tập hợp các số tự nhiên N là miền ngữ nghĩa và  là hàm ngữ nghĩa của số nhị phân. Bài tập: Câu 1: Trình bày định nghĩa cú pháp Câu 2:Hãy nêu các vấn đề cú pháp Câu 3: Hãy nêu các phương pháp phân tích cú pháp Câu 4: Hãy nêu các loại ngữ nghĩa hình thức 89
25. Bài 5 ĐẶC TRƯNG LẬP TRÌNH CÂU LỆNH (LẬP TRÌNH THỦ TỤC) MÃ BÀI ITPRG3_06.5 Học xong bài này học viên sẽ có khả năng: - Lập trình thực hiện một số các lệnh cơ bản : Gán, rẽ nhánh, lặp - Khai báo các đại lượng sử dụng trong chương trình - Sử dụng kỹ thuật lập trình có cấu trúc - Sử dụng các biến bí danh Nội dung: 5.1 Biến và hằng 5.2 Lập trình cấu trúc NỘI DUNG CHÍNH 5.1 Biến và hằng 5.1.1 Biến Biến là một ÐTDL được người lập trình định nghĩa và đặt tên một cách tường minh trong chương trình. Giá trị của biến có thể bị thay đổi trong thời gian tồn tại của nó. Tên biến được dùng để xác định và tham khảo tới biến. Trong các NNLT, tên biến thường được quy định dưới dạng một dãy các chữ cái, dấu gạch dưới và các chữ số, bắt đầu bằng một chữ cái và có chiều dài hữu hạn. 5.1.2 Hằng Hằng là một ÐTDL có tên và giá trị của hằng không thay đổi trong thời gian tồn tại của nó. Hằng trực kiện (literal constant) là một hằng mà tên của nó là sự mô tả giá trị của nó (chẳng hạn "27" là sự mô tả số thập phân của ÐTDL giá trị 27). Chú ý sự khác biệt giữa 2 giá trị 27. Một cái là một số nguyên được biểu diễn thành một dãy các bit trong bộ nhớ trong quá trình thực hiện chương trình và cái tên "27" là một chuỗi 2 ký tự "2" và "7" mô tả một số nguyên như nó được viết trong chương trình. 5.2 Lập trình cấu trúc Lệnh đơn là một sự tính toán được kết thúc bằng dấu chấm phẩy. Các định nghĩa biến và các biểu thức được kết thúc bằng dấu chấm phẩy như trong ví dụ sau: int i; // lệnh khai báo ++i; // lệnh này có một tác động chính yếu double d = 10.5; // lệnh khai báo d + 5; // lệnh không hữu dụng Ví dụ cuối trình bày một lệnh không hữu dụng bởi vì nó không có tác động chính yếu (d được cộng với 5 và kết quả bị vứt bỏ). Lệnh đơn giản nhất là lệnh rỗng chỉ gồm dấu chấm phẩy mà thôi. ; // lệnh rỗng Mặc dầu lệnh rỗng không có tác động chính yếu nhưng nó có một vài việc dùng xác thật. 90
26. Nhiều lệnh đơn có thể kết nối lại thành một lệnh phức bằng cách rào chúng bên trong các dấu ngoặc xoắn. Ví dụ: { int min, i = 10, j = 20; min = (i 0) { interest = balance * creditRate; balance += interest; } Một hình thức khác của lệnh if cho phép chúng ta chọn một trong hai lệnh: một lệnh được thực thi nếu như điều kiện được thỏa và lệnh còn lại được thực hiện nếu như điều kiện không thỏa. Hình thức này được gọi là lệnh if-else và có hình thức chung là: if (biểu thức ) lệnh 1; else lệnh 2; Trước tiên biểu thức được ước lượng. Nếu kết quả khác 0 thì lệnh 1 được thực thi. Ngược lại, lệnh 2 được thực thi. Ví dụ: if (balance > 0) { interest = balance * creditRate; balance += interest; } else { 91
27. interest = balance * debitRate; balance += interest; } Trong cả hai phần có sự giống nhau ở lệnh balance += interest vì thế toàn bộ câu lệnh có thể viết lại như sau: if (balance > 0) interest = balance * creditRate; else interest = balance * debitRate; balance += interest; Hoặc đơn giản hơn bằng việc sử dụng biểu thức điều kiện: interest = balance * (balance > 0 ? creditRate : debitRate); balance += interest; Hoặc chỉ là: balance += balance * (balance > 0 ? creditRate : debitRate); Các lệnh if có thể được lồng nhau bằng cách để cho một lệnh if xuất hiện bên trong một lệnh if khác. Ví dụ: if (callHour > 6) { if (callDuration = '0' && ch = 'A' && ch = 'a' && ch = '0' && ch <= '9') kind = digit; 92
28. else if (ch >= 'A' && ch = 'a' && ch <= 'z') kind = smallLetter; else kind = special; 3.3. Lệnh switch Lệnh switch cung cấp phương thức lựa chọn giữa một tập các khả năng dựa trên giá trị của biểu thức. Hình thức chung của câu lệnh switch là: switch (biểu thức) { case hằng : 1 các lệnh; case hằng : n các lệnh; default : các lệnh; } Biểu thức (gọi là thẻ switch) được ước lượng trước tiên và kết quả được so sánh với mỗi hằng số (gọi là các nhãn) theo thứ tự chúng xuất hiện cho đến khi một so khớp được tìm thấy. Lệnh ngay sau khi so khớp được thực hiện sau đó. Chú ý số nhiều: mỗi case có thể được theo sau bởi không hay nhiều lệnh (không chỉ là một lệnh). Việc thực thi tiếp tục cho tới khi hoặc là bắt gặp một lệnh break hoặc tất cả các lệnh xen vào đến cuối lệnh switch được thực hiện.Trường hợp default ở cuối cùng là một tùy chọn và được thực hiện nếu như tất cả các case trước đó không được so khớp. Ví dụ, chúng ta phải phân tích cú pháp một phép toán toán học nhị hạng thành ba thành phần của nó và phải lưu trữ chúng vào các biến operator , operand1 , và operand2 . Lệnh switch sau thực hiện phép toán và lưu trữ kết quả vào result . switch (operator) { case '+': result = operand1 + operand2; break; case '-': result = operand1 - operand2; break; case '*': result = operand1 * operand2; break; case '/': result = operand1 / operand2; break; default: cout << "unknown operator: " << operator << '\n'; break; } 93
29. Như đã được minh họa trong ví dụ, chúng ta cần thiết chèn một lệnh break ở cuối mỗi case. Lệnh break ngắt câu lệnh switch bằng cách nhảy đến điểm kết thúc của lệnh này. Ví dụ, nếu chúng ta mở rộng lệnh trên để cho phép x cũng có thể được sử dụng như là toán tử nhân, chúng ta sẽ có: switch (operator) { case '+': result = operand1 + operand2; break; case '-': result = operand1 - operand2; break; case 'x': case '*': result = operand1 * operand2; break; case '/': result = operand1 / operand2; break; default: cout << "unknown operator: " << operator << '\n'; break; } Bởi vì case 'x' không có lệnh break nên khi case này được thỏa thì sự thực thi tiếp tục thực hiện các lệnh trong case kế tiếp và phép nhân được thi hành. Chúng ta có thể quan sát rằng bất kỳ lệnh switch nào cũng có thể được viết như nhiều câu lệnh if-else. Ví dụ, lệnh trên có thể được viết như sau: if (operator == '+') result = operand1 + operand2; else if (operator == '-') result = operand1 - operand2; else if (operator == 'x' || operator == '*') result = operand1 * operand2; else if (operator == '/') result = operand1 / operand2; else cout << "unknown operator: " << ch << '\n'; Người ta có thể cho rằng phiên bản switch là rõ ràng hơn trong trường hợp này. Tiếp cận if-else nên được dành riêng cho tình huống mà trong đó switch không thể làm được công việc (ví dụ, khi các điều kiện là phức tạp không thể đơn giản thành các đẳng thức toán học hay khi các nhãn cho các case không là các hằng số). 3.4. Lệnh while Lệnh while (cũng được gọi là vòng lặp while) cung cấp phương thức lặp một lệnh cho tới khi một điều kiện được thỏa. Hình thức chung của lệnh lặp là: while ( biểu thức) lệnh; Biểu thức (cũng được gọi là điều kiện lặp) được ước lượng trước tiên. Nếu kết quả 94
30. khác 0 thì sau đó lệnh (cũng được gọi là thân vòng lặp) được thực hiện và toàn bộ quá trình được lặp lại. Ngược lại, vòng lặp được kết thúc. Ví dụ, chúng ta muốn tính tổng của tất cả các số nguyên từ 1 tới n. Điều này có thể được diễn giải như sau: i = 1; sum = 0; while (i <= n){ sum += i; i++; } Trường hợp n là 5, Bảng 3.1 cung cấp bảng phát họa vòng lặp bằng cách liệt kê các giá trị của các biến có liên quan và điều kiện lặp. Bảng 3.1 Vết của vòng lặp while. Vòng lặp i n i <= n sum += i++ Một 1 5 1 1 Hai 2 5 1 3 Ba 3 5 1 6 Bốn 4 5 1 10 Năm 5 5 1 15 Sáu 6 5 0 Đôi khi chúng ta có thể gặp vòng lặp while có thân rỗng (nghĩa là một câu lệnh null). Ví dụ vòng lặp sau đặt n tới thừa số lẻ lớn nhất của nó. while (n % 2 == 0 && n /= 2) ; Ở đây điều kiện lặp cung cấp tất cả các tính toán cần thiết vì thế không thật sự cần một thân cho vòng lặp. Điều kiện vòng lặp không những kiểm tra n là chẵn hay không mà nó còn chia n cho 2 và chắc chắn rằng vòng lặp sẽ dừng. 3.5. Lệnh do - while Lệnh do (cũng được gọi là vòng lặp do) thì tương tự như lệnh while ngoại trừ thân của nó được thực thi trước tiên và sau đó điều kiện vòng lặp mới được kiểm tra. Hình thức chung của lệnh do là: do lệnh; while ( biểu thức) ; Lệnh được thực thi trước tiên và sau đó biểu thức được ước lượng. Nếu kết quả của biểu thức khác 0 thì sau đó toàn bộ quá trình được lặp lại. Ngược lại thì vòng lặp kết thúc. Vòng lặp do ít được sử dụng thường xuyên hơn vòng lặp while. Nó hữu dụng trong những trường hợp khi chúng ta cần thân vòng lặp thực hiện ít nhất một lần mà không quan tâm đến điều kiện lặp. Ví dụ, giả sử chúng ta muốn thực hiện lặp đi lặp lại công việc đọc một giá trị và in bình phương của nó, và dừng khi giá trị là 0. Điều này có thể được diễn giải trong vòng lặp sau đây: do { 95
31. cin >> n; cout << n * n << '\n'; } while (n != 0); Không giống như vòng lặp while, vòng lặp do ít khi được sử dụng trong những tình huống mà nó có một thân rỗng. Mặc dù vòng lặp do với thân rỗng có thể là tương đương với một vòng lặp while tương tự nhưng vòng lặp while thì luôn dễ đọc hơn. 3.6. Lệnh for Lệnh for (cũng được gọi là vòng lặp for) thì tương tự như vòng lặp while nhưng có hai thành phần thêm vào: một biểu thức được ước lượng chỉ một lần trước hết và một biểu thức được ước lượng mỗi lần ở cuối mỗi lần lặp. Hình thức tổng quát của lệnh for là: for ( biểu thức1; biểu thức2; biểu thức3) lệnh; Biểu thức1 (thường được gọi là biểu thức khởi tạo) được ước lượng trước tiên. Mỗi vòng lặp biểu thức2 được ước lượng. Nếu kết quả không là 0 (đúng) thì sau đó lệnh được thực thi và biểu thức3 được ước lượng. Ngược lại, vòng lặp kết thúc. Vòng lặp for tổng quát thì tương đương với vòng lặp while sau: biểu thức1; while ( biểu thức 2) { lệnh; biểu thức 3; } Vòng lặp for thường được sử dụng trong các trường hợp mà có một biến được tăng hay giảm ở mỗi lần lặp. Ví dụ, vòng lặp for sau tính toán tổng của tất cả các số nguyên từ 1 tới n. sum = 0; for (i = 1; i <= n; ++i) sum += i; Điều này được ưa chuộng hơn phiên bản của vòng lặp while mà chúng ta thấy trước đó. Trong ví dụ này i thường được gọi là biến lặp. C++ cho phép biểu thức đầu tiên trong vòng lặp for là một định nghĩa biến. Ví dụ trong vòng lặp trên thì i có thể được định nghĩa bên trong vòng lặp: for (int i = 1; i <= n; ++i) sum += i; Trái với sự xuất hiện, phạm vi của i không ở trong thân của vòng lặp mà là chính vòng lặp. Xét trên phạm vi thì ở trên tương đương với: int i; for (i = 1; i <= n; ++i) sum += i; Bất kỳ biểu thức nào trong 3 biểu thức của vòng lặp for có thể rỗng. Ví dụ, xóa biểu thức đầu và biểu thức cuối cho chúng ta dạng giống như vòng lặp while: for (; i != 0;) // tương đương với: while (i != 0) 96
32. something; // something; Xóa tất cả các biểu thức cho chúng ta một vòng lặp vô hạn. Điều kiện của vòng lặp này được giả sử luôn luôn là đúng. for (;;) // vòng lặp vô hạn something; Trường hợp vòng lặp với nhiều biến lặp thì hiếm dùng. Trong những trường hợp như thế, toán tử phẩy (,) được sử dụng để phân cách các biểu thức của chúng: for (i = 0, j = 0; i + j > num; if (num > num; if (num >= 0) { 97
33. // xử lý số ở đây } } while (num != 0); Một biến thể của vòng lặp này để đọc chính xác một số n lần (hơn là cho tới khi số đó là 0) có thể được diễn giải như sau: for (i = 0; i > num; if (num > num; if (num > password; if (Verify(password)) // kiểm tra mật khẩu đúng hay sai break; // thoát khỏi vòng lặp cout << "Incorrect!\n"; } Ở đây chúng ta phải giả sử rằng có một hàm được gọi Verify để kiểm tra một mật khẩu và trả về true nếu như mật khẩu đúng và ngược lại là false. Chúng ta có thể viết lại vòng lặp mà không cần lệnh break bằng cách sử dụng một biến luận lý được thêm vào (verified ) và thêm nó vào điều kiện vòng lặp: verified = 0; 98
34. for (i = 0; i > password; verified = Verify(password)); if (!verified) cout > password; if (Verify(password)) // check password for correctness goto out; // drop out of the loop cout << "Incorrect!\n"; } out: //etc Bởi vì lệnh goto cung cấp một hình thức nhảy tự do không có cấu trúc (không giống như lệnh break và continue) nên dễ làm gãy đổ chương trình. Phần lớn các lập trình viên ngày nay tránh sử dụng nó để làm cho chương trình rõ ràng. Tuy nhiên, goto có một vài (dù cho hiếm) sử dụng chính đáng. Vì sự phức tạp của những trường hợp như thế mà việc cung cấp những ví dụ được trình bày ở những phần sau. 3.10.Lệnh return Lệnh return cho phép một hàm trả về một giá trị cho thành phần gọi nó. Nó có hình thức tổng quát: return biểu thức; trong đó biểu thức chỉ rõ giá trị được trả về bởi hàm. Kiểu của giá trị này nên hợp với kiểu của hàm. Trường hợp kiểu trả về của hàm là void , biểu thức nên rỗng: return; Hàm mà được chúng ta thảo luận đến thời điểm này chỉ có hàm main , kiểu trả về của nó là kiểu int . Giá trị trả về của hàm main là những gì mà chương trình trả về cho hệ điều hành khi nó hoàn tất việc thực thi. Chẳng hạn dưới UNIX qui ước là trả về 0 từ hàm main khi chương trình thực thi không có lỗi. Ngược lại, một mã lỗi khác 0 được trả về. Ví dụ: 99
35. int main (void) { cout = 0) if (n < 10) cout << "n is small\n"; else cout << "n is negative\n"; 3.3 Viết chương trình nhập một ngày theo định dạng dd/mm/yy và xuất nó theo định dạng month dd, year. Ví dụ, 25/12/61 trở thành: Thang muoi hai 25, 1961 3.4 Viết chương trình nhập vào một giá trị số nguyên, kiểm tra nó là dương hay không và xuất ra giai thừa của nó, sử dụng công thức: Chương 3: Lệnh 41 giaithua (0) = 1 giaithua (n) = n × giaithua (n-1) 3.5 Viết chương trình nhập vào một số cơ số 8 và xuất ra số thập phân tương đương. Ví dụ sau minh họa các công việc thực hiện của chương trình theo mong đợi: Nhap vao so bat phan: 214 BatPhan(214) = ThapPhan(140) 3.6 Viết chương trình cung cấp một bảng cửu chương đơn giản của định dạng sau cho các số nguyên từ 1 tới 9: 1 x 1 = 1 1 x 2 = 2 9 x 9 = 100
36. BÀI 6 LẬP TRÌNH HƯỚNG ĐỐI TƯỢNG Mà BÀI ITPRG3_06.5 6.1. Giới thiệu Hướng đối tượng (object orientation) cung cấp một kiểu mới để xây dựng phần mềm. Trong kiểu mới này, các đối tượng (object) và các lớp (class) là những khối xây dựng trong khi các phương thức (method), thông điệp (message), và sự thừa kế (inheritance) cung cấp các cơ chế chủ yếu. Lập trình hướng đối tượng (OOP- Object-Oriented Programming) là một cách tư duy mới, tiếp cận hướng đối tượng để giải quyết vấn đề bằng máy tính. Thuật ngữ OOP ngày càng trở nên thông dụng trong lĩnh vực công nghệ thông tin. Nếu bạn chưa bao giờ sử dụng một ngôn ngữ OOP thì trước tiên bạn nên nắm vững các khái niệm của OOP hơn là viết các chương trình. Bạn cần hiểu được đối tượng (object) là gì, lớp (class) là gì, chúng có quan hệ với nhau như thế nào, và làm thế nào để các đối tượng trao đổi thông điệp (message) với nhau, vâng vâng. OOP là tập hợp các kỹ thuật quan trọng mà có thể dùng để làm cho việc triển khai chương trình hiệu quả hơn. Quá trình tiến hóa của OOP như sau: ƒLập trình tuyến tính ƒLập trình có cấu trúc ƒSự trừu tượng hóa dữ liệu ƒLập trình hướng đối tượng Lập trình hướng đối tượng (OOP) là một phương pháp thiết kế và phát triển phần mềm dựa trên kiến trúc lớp và đối tượng. Chương 6: Lập trình hướng đối tượng 76 6.2. Trừu tượng hóa (Abstraction) Trừu tượng hóa là một kỹ thuật chỉ trình bày những các đặc điểm cần thiết của vấn đề mà không trình bày những chi tiết cụ thể hay những lời giải thích phức tạp của vấn đề đó. Hay nói khác hơn nó là một kỹ thuật tập trung vào thứ cần thiết và phớt lờ đi những thứ không cần thiết. Ví dụ những thông tin sau đây là các đặc tính gắn kết với con người: ƒ Tên ƒ Tuổi ƒ Địa chỉ ƒ Chiều cao ƒ Màu tóc Giả sử ta cần phát triển ứng dụng khách hàng mua sắm hàng hóa thì những chi tiết thiết yếu là tên, địa chỉ còn những chi tiết khác (tuổi, chiều cao, màu tóc, ) là không quan trọng đối với ứng dụng. Tuy nhiên, nếu chúng ta phát triển một ứng dụng hỗ trợ cho việc điều tra tội phạm thì những thông tin như chiều cao và màu tóc là thiết yếu. Sự trừu tượng hóa đã không ngừng phát triển trong các ngôn ngữ lập trình, nhưng chỉ ở mức dữ liệu và thủ tục. Trong OOP, việc này được nâng lên ở mức cao hơn – mức đối 101
37. tượng. Sự trừu tượng hóa được phân thành sự trừu tượng hóa dữ liệu và trừu tượng hóa chương trình. Khái niệm 6.2 6.3. Đối tượng (object) Các đối tượng là chìa khóa để hiểu được kỹ thuật hướng đối tượng. Bạn có thể nhìn xung quanh và thấy được nhiều đối tượng trong thế giới thực như: con chó, cái bàn, quyển vở, cây viết, tivi, xe hơi Trong một hệ thống hướng đối tượng, mọi thứ đều là đối tượng. Một bảng tính, một ô trong bảng tính, một biểu đồ, một bảng báo cáo, một con số hay một số điện thoại, một tập tin, một thư mục, một máy in, một câu hoặc một từ, thậm chí một ký tự, tất cả chúng là những ví dụ của một đối tượng. Rõ ràng chúng ta viết một chương trình hướng đối tượng cũng có nghĩa là chúng ta đang xây dựng một mô hình Trừu tượng hóa dữ liệu (data abstraction) là tiến trình xác định và nhóm các thuộc tính và các hành động liên quan đến một thực thể đặc thù trong ứng dụng đang phát triển. Trừu tượng hóa chương trình (program abstraction) là một sự trừu tượng hóa dữ liệu mà làm cho các dịch vụ thay đổi theo dữ liệu. của một vài bộ phận trong thế giới thực. Tuy nhiên các đối tượng này có thể được biểu diễn hay mô hình trên máy tính. Một đối tượng thế giới thực là một thực thể cụ thể mà thông thường bạn có thể sờ, nhìn thấy hay cảm nhận được. Tất cả các đối tượng trong thế giới thực đều có trạng thái (state) và hành động (behaviour). Ví dụ: Trạng thái Hành động ƒ Tên ƒ Sủa ƒ ƒ Vẫy tai Con chó Màu ƒ Chạy ƒ ƒ Ăn Giống ƒ Vui sướng ƒ Bánh răng ƒ Tăng tốc ƒ ƒ Giảm tốc Xe đạp Bàn đạp ƒ Chuyển ƒ bánh răng Dây xích ƒ Bánh xe Hình 6.1 Ví dụ về trạng thái và hành động 102
38. Các đối tượng phần mềm (software object) có thể được dùng để biểu diễn các đối tượng thế giới thực. Chúng được mô hình sau khi các đối tượng thế giới thực có cả trạng thái và hành động. Giống như các đối tượng thế giới thực, các đối tượng phần mềm cũng có thể có trạng thái và hành động. Một đối tượng phần mềm có biến (variable) hay trạng thái (state) mà thường được gọi là thuộc tính (attribute; property) để duy trì trạng thái của nó và phương thức (method) để thực hiện các hành động của nó. Thuộc tính là một hạng mục dữ liệu được đặt tên bởi một định danh (identifier) trong khi phương thức là một chức năng được kết hợp với đối tượng chứa nó. OOP thường sử dụng hai thuật ngữ mà sau này Java cũng sử dụng là thuộc tính (attribute) và phương thức (method) để đặc tả tương ứng cho trạng thái (state) hay biến (variable) và hành động (behavior). Tuy nhiên C++ lại sử dụng hai thuật ngữ dữ liệu thành viên (member data) và hàm thành viên (member function) thay cho các thuật ngữ này. Xét một cách đặc biệt, chỉ một đối tượng riêng rẽ thì chính nó không hữu dụng. Một chương trình hướng đối tượng thường gồm có hai hay nhiều hơn các đối tượng phần mềm tương tác lẫn nhau như là sự tương tác của các đối tượng trong trong thế giới thực. Khái niệm 6.3 Kể từ đây, trong giáo trình này chúng ta sử dụng thuật ngữ đối tượng (object) để chỉ một đối tượng phần mềm. Hình 6.1 là một minh họa của một đối tượng phần mềm: Đối tượng (object) là một thực thể phần mềm bao bọc các thuộc tính và các phương thức liên quan. Mọi thứ mà đối tượng phần mềm biết (trạng thái) và có thể làm (hành động) được thể hiện qua các thuộc tính và các phương thức. Một đối tượng phần mềm mô phỏng cho chiếc xe đạp sẽ có các thuộc tính để xác định các trạng thái của chiếc xe đạp như: tốc độ của nó là 10 km trên giờ, nhịp bàn đạp là 90 vòng trên phút, và bánh răng hiện tại là bánh răng thứ 5. Các thuộc tính này thông thường được xem như thuộc tính thể hiện (instance attribute) bởi vì chúng chứa đựng các trạng thái cho một đối tượng xe đạp cụ thể. Trong kỹ thuật hướng đối tượng thì một đối tượng cụ thể được gọi là một thể hiện (instance). Khái niệm 6.4 Hình 6.2 minh họa một xe đạp được mô hình như một đối tượng phần mềm: Đối tượng xe đạp phần mềm cũng có các phương thức để thắng lại, tăng nhịp đạp hay là chuyển đổi bánh răng. Nó không có phương thức để thay đổi tốc độ vì tốc độ của xe đạp có thể tình ra từ hai yếu tố số vòng quay và bánh răng hiện tại. Những phương thức này thông thường được biết như là các phương thước thể hiện (instance method) bởi vì chúng tác động hay thay đổi trạng thái của một đối tượng cụ thể. Một đối tượng cụ thể được gọi là một thể hiện (instance). 6.4. Lớp (Class) Trong thế giới thực thông thường có nhiều loại đối tượng cùng loại. Chẳng hạn chiếc xe đạp của bạn chỉ là một trong hàng tỉ chiếc xe đạp trên thế giới. Tương tự, trong một chương trình hướng đối tượng có thể có nhiều đối tượng cùng loại và chia sẻ những đặc điểm chung. Sử dụng thuật ngữ hướng đối tượng, chúng ta có thể nói rằng chiếc xe đạp của bạn là một thể hiện của lớp xe đạp. Các xe đạp có một vài trạng thái chung (bánh răng hiện 103
39. tại, số vòng quay hiện tại, hai bánh xe) và các hành động (chuyển bánh răng, giảm tốc). Tuy nhiên, trạng thái của mỗi xe đạp là độc lập và có thể khác với các trạng thái của các xe đạp khác. Trước khi tạo ra các xe đạp, các nhà sản xuất thường thiết lập một bảng thiết kế (blueprint) mô tả các đặc điểm và các yếu tố cơ bản của xe đạp. Sau đó hàng loạt xe đạp sẽ được tạo ra từ bản thiết kế này. Không hiệu quả nếu như tạo ra một bản thiết kế mới cho mỗi xe đạp được sản xuất. Trong phần mềm hướng đối tượng cũng có thể có nhiều đối tượng cùng loại chia sẻ những đặc điểm chung như là: các hình chữ nhật, các mẫu tin nhân viên, các đoạn phim, Giống như là các nhà sản xuất xe đạp, bạn có thể tạo ra một bảng thiết kế cho các đối tượng này. Một bảng thiết kế phần mềm cho các đối tượng được gọi là lớp (class). Khái niệm 6.5 Trở lại ví dụ về xe đạp chúng ta thấy rằng một lớp Xedap là một bảng thiết kế cho hàng loạt các đối tượng xe đạp được tạo ra. Mỗi đối tượng xe đạp là một thể hiện của lớp Xedap và trạng thái của nó có thể khác với các đối tượng xe đạp khác. Ví dụ một xe đạp hiện tại có thể là ở bánh răng thứ 5 trong khi một chiếc khác có thể là ở bánh răng thứ 3. Lớp Xedap sẽ khai báo các thuộc tính thể hiện cần thiết để chứa đựng bánh răng hiện tại, số vòng quay hiện tại, cho mỗi đối tượng xe đạp. Lớp Xedap cũng khai báo và cung cấp những thi công cho các phương thức thể hiện để cho phép người đi xe đạp chuyển đổi bánh răng, phanh lại, chuyển đổi số vòng quay, như Hình 6.3. Lớp (class) là một thiết kế (blueprint) hay một mẫu ban đầu (prototype) định nghĩa các thuộc tính và các phương thức chung cho tất cả các đối tượng của cùng một loại nào đó. Một đối tượng là một thể hiện cụ thể của một lớp. Sau khi bạn đã tạo ra lớp xe đạp, bạn có thể tạo ra bất kỳ đối tượng xe đạp nào từ lớp này. Khi bạn tạo ra một thể hiện của lớp, hệ thống cấp phát đủ bộ nhớ cho đối tượng và tất cả các thuộc tính thể hiện của nó. Mỗi thể hiện sẽ có vùng nhớ riêng cho các thuộc tính thể hiện của nó. Hình 6.4 minh họa hai đối tượng xe đạp khác nhau được tạo ra từ cùng lớp Xedap: Ngoài các thuộc tính thể hiện, các lớp có thể định nghĩa các thuộc tính lớp (class attribute). Một thuộc tính lớp chứa đựng các thông tin mà được chia sẻ bởi tất cả các thể hiện của lớp. Ví dụ, tất cả xe đạp có cùng số lượng bánh răng. Trong trường hợp này, định nghĩa một thuộc tính thể hiện để giữ số lượng bánh răng là không hiệu quả bởi vì tất cả các vùng nhớ của các thuộc tính thể hiện này đều giữ cùng một giá trị. Trong những trường hợp như thế bạn có thể định nghĩa một thuộc tính lớp để chứa đựng số lượng bánh răng của xe đạp.Tất cả các thể hiện của lớp Xedap sẽ chia thuộc tính này. Một lớp cũng có thể khai báo các phương thức lớp (class methods). Bạn có thể triệu gọi một phương thức lớp trực tiếp từ lớp nhưng ngược lại bạn phải triệu gọi các phương thức thể hiện từ một thể hiện cụ thể nào đó. 6.5. Thuộc tính (Attribute) Các thuộc tính trình bày trạng thái của đối tượng. Các thuộc tính nắm giữ các giá trị dữ liệu trong một đối tượng, chúng định nghĩa một đối tượng đặc thù. 104
40. Khái niệm 6.7 Một thuộc tính có thể được gán một giá trị chỉ sau khi một đối tượng dựa trên lớp ấy được tạo ra. Một khi các thuộc tính được gán giá trị chúng mô tả một đối tượng. Mọi đối tượng của một lớp phải có cùng các thuộc tính nhưng giá trị của các thuộc tính thì có thể khác nhau. Một thuộc tính của đối tượng có thể nhận các giá trị khác nhau tại những thời điểm khác nhau. Thuộc tính lớp(class attribute) là một hạng mục dữ liệu liên kết với một lớp cụ thể mà không liên kết với các thể hiện của lớp. Nó được định nghĩa bên trong định nghĩa lớp và được chia sẻ bởi tất cả các thể hiện của lớp. Phương thức lớp (class method) là một phương thức được triệu gọi mà không tham khảo tới bất kỳ một đối tượng nào. Tất cả các phương thức lớp ảnh hưởng đến toàn bộ lớp chứ không ảnh hưởng đến một lớp riêng rẽ nào. Thuộc tính (attribute) là dữ liệu trình bày các đặc điểm về một đối tượng. Chương 6: Lập trình hướng đối tượng 82 6.6. Phương thức (Method) Các phương thức thực thi các hoạt động của đối tượng. Các phương thức là nhân tố làm thay đổi các thuộc tính của đối tượng. Khái niệm 6.8 Các phương thức xác định cách thức hoạt động của một đối tượng và được thực thi khi đối tượng cụ thể được tạo ra.Ví dụ, các hoạt động chung của một đối tượng thuộc lớp Chó là sủa, vẫy tai, chạy, và ăn. Tuy nhiên, chỉ khi một đối tượng cụ thể thuộc lớp Chó được tạo ra thì các phương thức sủa, vẫy tai, chạy, và ăn mới được thực thi. Các phương thức mang lại một cách nhìn khác về đối tượng. Khi bạn nhìn vào đối tượng Cửa ra vào bên trong môi trường của bạn (môi trường thế giới thực), một cách đơn giản bạn có thể thấy nó là một đối tượng bất động không có khả năng suy nghỉ. Trong tiếp cận hướng đối tượng cho phát triển hệ thống, Cửa ra vào có thể được liên kết tới phương thức được giả sử là có thể được thực hiện. Ví dụ, Cửa ra vào có thể mở, nó có thể đóng, nó có thể khóa, hoặc nó có thể mở khóa. Tất cả các phương thức này gắn kết với đối tượng Cửa ra vào và được thực hiện bởi Cửa ra vào chứ không phải một đối tượng nào khác. 6.7. Thông điệp (Message) Một chương trình hay ứng dụng lớn thường chứa nhiều đối tượng khác nhau. Các đối tượng phần mềm tương tác và giao tiếp với nhau bằng cách gởi các thông điệp (message). Khi đối tượng A muốn đối tượng B thực hiện các phương thức của đối tượng B thì đối tượng A gởi một thông điệp tới đối tượng B. Ví dụ đối tượng người đi xe đạp muốn đối tượng xe đạp thực hiện phương thức chuyển đổi bánh răng của nó thì đối tượng người đi xe đạp cần phải gởi một thông điệp tới đối tượng xe đạp. Đôi khi đối tượng nhận cần thông tin nhiều hơn để biết chính xác thực hiện công việc gì. Ví dụ khi bạn chuyển bánh răng trên chiếc xe đạp của bạn thì bạn phải chỉ rõ bánh răng 105
41. nào mà bạn muốn chuyển. Các thông tin này được truyền kèm theo thông điệp và được gọi là các tham số (parameter). Phương thức (method) có liên quan tới những thứ mà đối tượng có thể làm. Một phương thức đáp ứng một chức năng tác động lên dữ liệu của đối tượng (thuộc tính). Chương 6: Lập trình hướng đối tượng 83 Một thông điệp gồm có: ƒ Đối tượng nhận thông điệp ƒ Tên của phương thức thực hiện ƒ Các tham số mà phương thức cần Khái niệm 6.9 Khi một đối tượng nhận được một thông điệp, nó thực hiện một phương thức tương ứng. Ví dụ đối tượng xe đạp nhận được thông điệp là chuyển đổi bánh răng nó sẽ thực hiện việc tìm kiếm phương thức chuyển đổi bánh răng tương ứng và thực hiện theo yêu cầu của thông điệp mà nó nhận được. 6.8. Tính bao gói (Encapsulation) Trong đối tượng xe đạp, giá trị của các thuộc tính được chuyển đổi bởi các phương thức. Phương thức changeGear() chuyển đổi giá trị của thuộc tính currentGear. Thuộc tính speed được chuyển đổi bởi phương thức changeGear() hoặc changRpm(). Trong OOP thì các thuộc tính là trung tâm, là hạt nhân của đối tượng. Các phương thức bao quanh và che giấu đi hạt nhân của đối tượng từ các đối tượng khác trong chương trình.Việc bao gói các thuộc tính của một đối tượng bên trong sự che chở của các phương thức của nó được gọi là sự đóng gói (encapsulation) hay là đóng gói dữ liệu. Đặc tính đóng gói dữ liệu là ý tưởng của các nhà thiết các hệ thống hướng đối tượng. Tuy nhiên, việc áp dụng trong thực tế thì có thể không hoàn toàn như thế. Vì những lý do thực tế mà các đối tượng đôi khi cần phải phơi bày ra một vài thuộc tính này và che giấu đi một vài phương thức kia. Tùy thuộc vào các ngôn ngữ lập trình hướng đối tượng khác nhau, chúng ta có các điều khiển các truy xuất dữ liệu khác nhau. Một đối tượng có một giao diện chung cho các đối tượng khác sử dụng để giao tiếp với nó. Do đặc tính đóng gói mà các chi tiết như: các trạng thái Một thông điệp (message) là một lời yêu cầu một hoạt động. Một thông điệp được truyền khi một đối tượng triệu gọi một hay nhiều phương thức của đối tượng khác để yêu cầu thông tin. Đóng gói (encapsulation) là tiến trình che giấu việc thực thi chi tiết của một đối tượng. được lưu trữ như thế nào hay các hành động được thi công ra sao có thể được che giấu đi từ các đối tượng khác. Điều này có nghĩa là các chi tiết riêng của đối tượng có thể được chuyển đổi mà hoàn toàn không ảnh hưởng tới các đối tượng khác có liên hệ với nó. Ví dụ, một người đi xe đạp không cần biết chính xác cơ chế chuyển bánh răng trên xe đạp thực sự làm việc như thế nào nhưng vẫn có thể sử dụng nó. Điều này được gọi là che giấu thông tin. 106
42. 6.9. Tính thừa kế (Inheritance) Hệ thống hướng đối tượng cho phép các lớp được định nghĩa kế thừa từ các lớp khác. Ví dụ, lớp xe đạp leo núi và xe đạp đua là những lớp con (subclass) của lớp xe đạp. Như vậy ta có thể nói lớp xe đạp là lớp cha (superclass) của lớp xe đạp leo núi và xe đạp đua. Các lớp con thừa kế thuộc tính và hành động từ lớp cha của chúng. Ví dụ, một xe đạp leo núi không những có bánh răng, số vòng quay trên phút và tốc độ giống như mọi xe đạp khác mà còn có thêm một vài loại bánh răng vì thế mà nó cần thêm một thuộc tính là gearRange (loại bánh răng). Các lớp con có thể định nghĩa lại các phương thức được thừa kế để cung cấp các thi công riêng biệt cho các phương thức này. Ví dụ, một xe đạp leo núi sẽ cần một phương thức đặc biệt để chuyển đổi bánh răng. Che giấu thông tin (information hiding) là việc ẩn đi các chi tiết của thiết kế hay thi công từ các đối tượng khác. Thừa kế (inheritance) nghĩa là các hành động (phương thức) và các thuộc tính được định nghĩa trong một lớp có thể được thừa kế hoặc được sử dụng lại bởi lớp khác. Lớp cha (superclass) là lớp có các thuộc tính hay hành động được thừa hưởng bởi một hay nhiều lớp khác. Lớp con (subclass) là lớp thừa hưởng một vài đặc tính chung của lớp cha và thêm vào những đặc tính riêng khác. Chương 6: Lập trình hướng đối tượng 85 Các lớp con cung cấp các phiên bản đặc biệt của các lớp cha mà không cần phải định nghĩa lại các lớp mới hoàn toàn. Ở đây, mã lớp cha có thể được sử dụng lại nhiều lần. 6.10.Tính đa hình (Polymorphism) Một khái niệm quan trọng khác có liên quan mật thiết với truyền thông điệp là đa hình (polymorphism). Với đa hình, nếu cùng một hành động (phương thức) ứng dụng cho các đối tượng thuộc các lớp khác nhau thì có thể đưa đến những kết quả khác nhau. Khái niệm 6.14 Chúng ta hãy xem xét các đối tượng Cửa Sổ và Cửa Cái. Cả hai đối tượng có một hành động chung có thể thực hiện là đóng. Nhưng một đối tượng Cửa Cái thực hiện hành động đó có thể khác với cách mà một đối tượng Cửa Sổ thực hiện hành động đó. Cửa Cái khép cánh cửa lại trong khi Cửa Sổ hạ các thanh cửa xuống. Thật vậy, hành động đóng có thể thực hiện một trong hai hình thức khác nhau. Một ví dụ khác là hành động hiển thị. Tùy thuộc vào đối tượng tác động, hành động ấy có thể hiển thị một chuỗi, hoặc vẽ một đường thẳng, hoặc là hiển thị một hình. Đa hình có sự liên quan tới việc truyền thông điệp. Đối tượng yêu cầu cần biết hành động nào để yêu cầu và yêu cầu từ đối tượng nào. Tuy nhiên đối tượng yêu cầu không cần lo lắng về một hành động được hoàn thành như thế nào. Bài tập cuối chương 6 6.1 Trình bày các định nghĩa của các thuật ngữ: ƒ Lập trình hướng đối tượng 107
43. ƒ Trừu tượng hóa ƒ Đối tượng ƒ Lớp ƒ Thuộc tính ƒ Phương thức ƒ Thông điệp Đa hình (polymorphism) nghĩa là “nhiều hình thức”, hành động cùng tên có thể được thực hiện khác nhau đối với các đối tượng/các lớp khác nhau. Chương 6: Lập trình hướng đối tượng 86 6.2 Phân biệt sự khác nhau giữa lớp và đối tượng, giữa thuộc tính và giá trị, giữa thông điệp và truyền thông điệp. 6.3 Trình bày các đặc điểm của OOP. 6.4 Những lợi ích có được thông qua thừa kế và bao gói. 6.5 Những thuộc tính và phương thức cơ bản của một cái máy giặt. 6.6 Những thuộc tính và phương thức cơ bản của một chiếc xe hơi. 6.7 Những thuộc tính và phương thức cơ bản của một hình tròn. 6.8 Chỉ ra các đối tượng trong hệ thống rút tiền tự động ATM. 6.9 Chỉ ra các lớp có thể kế thừa từ lớp điện thoại, xe hơi, và động vật Bài 7 TÊN BÀI:LẬP TRÌNH LOGIC VÀ LẬP TRÌNH HÀM Mà BÀI : ITPRG3-06.7 Giới thiệu Trong các họ ngôn ngữ lập trình, lập trình hàm và lập trình logic là hai họ ngôn ngữ lập trình ít phổ dụng hơn, do nét đặc trưng trong ứng dụng của nó. Tuy nhiên, trong lĩnh vực công nghệ thông tin, để giải quyết một số bài toán thực tế liên quan đến hệ chuyên gia, cơ sở tri thức hay trí tuệ nhân tạo thì việc sử dụng các họ ngôn ngữ lập trình này là rất phù hợp và mang lại hiệu quả cao. Mục tiêu thực hiện - Hiểu rõ lập trình logic và sự khác biệt với lập trình mệnh lệnh - Các thành phần ngôn ngữ lập trình logic - Xác định ngữ nghĩa của các ký hiệu - Nắm được thành phần cơ bản của ngôn ngữ Prolog - Viết được các chương trình cỡ nhỏ và vừa bằng Prolog - Hiểu cơ chế lập trình hàm - Thực hiện các phép biến đổi hàm và ngữ nghĩa hàm Nội dung chính Bài học này trình bày hai phương pháp: lập trình logic và lập trình hàm. Đồng thời cũng giới thiệu hai ngôn ngữ cụ thể là lập trình logic Prolog và lập trình hàm Scheme. 108
44. Giới thiệu lập trình logic Lập trình logic được sử dụng phổ biến trong lĩnh vực trí tuệ nhân tạo và hệ chuyên gia. Các ngôn ngữ lập trình logic rất thích hợp để giải quyết các bài toán liên quan đến các đối tượng (object) và mối quan hệ (relation) giữa chúng. Nguyên lý lập trình logic dựa trên các mệnh đề Horn (Horn clauses). Một mệnh đề Horn biểu diễn một sự kiện hay sự việc nào nào đó là đúng hoặc không đúng, xảy ra hoặc không xảy ra (có hoặc không có, ). Ví dụ sau đây là một số mệnh đề Horn: 1. Nếu một người An cha của Lộc và Lộc là cha của Dương thì An là ông của Dương. 2. Hùng là cha của Tuyết. 3. Nếu một học viên chịu khó và học hỏi thì học viên đó có kết quả tốt. 4. Học viên Linh có kết quả tốt. 5. Tất cả mọi người đều phải chết (Hoặc Nếu ai đó là người, thì ai đó phải chết). 6. Socrat là người. Trong các mệnh đề Horn ở trên, các mệnh đề 1, 3, 5 được gọi là các luật (rule), các mệnh đề còn lại được gọi là các sự kiện (fact). Một chưưng trình logic có thể được xem như là một cơ sở dữ liệu gồm các mệnh đề Horn, hoặc dạng luật hoặc dạng sự kiện, chảng hạn như tất cả các sự kiện và luật từ 1 đến 6 ở trên. Ngưới sử dụng gọi chạy một chương trình logic bằng cách đặt các câu hỏi (question) truy vấn trên cơ sở dũ liệu này, chẳng hạn câu hỏi: Socrat có chết không (tương đương với khẳng định “Socrat chết” là đúng hay sai)? Một hệ thống logic sẽ thực hiện chương trình theo cách suy luận – tìm kiếm dựa trên vốn tri thức (knowledge) đã có là chương trình – cơ sở dữ liệu, để chứng minh câu hỏi là một khẳng định đúng (Yes) hoặc sai (No). Với câu hỏi trên, hệ thống tìm kiếm trong cơ sở dữ liệu khẳng định Socrat chết bằng cách tìm xem ai đó là Socrat và tìm thấy luật 5 thỏa mãn (vế thì). Vận dụng luật 5, hệ thống nhận được Socrat là người (vế nếu) chính là sự kiện 6. Từ đó câu trả lời sẽ là: Yes Có nghĩa là sự kiện Socrat chết là đúng. Trong họ các ngôn ngữ logic thì Prolog (nghĩa là Programing in Logic) là ngôn ngữ lập trình được sử dụng rộng rãi nhất. Ngôn ngữ này ra đời năm 1970 do một nhóm nghiên cứu người Pháp đề xuất, sau đó Prolog nhanh chóng được áp dụng rộng rãi ở châu Âu và nhiều nước trên thế giới. Từ năm 1980, Prolog được công nhận như là một ngôn ngữ phát triển trong lĩnh vực Trí tuệ Nhân tạo. Và gần đây, Prolog còn được ứng dụng trong lập trình bởi các ràng buộc. Ngữ nghĩa các kí hiệu Một số khái niệm Một chương trình Prolog là một cơ sở dữ liệu gồm các mệnh đề (clause). Mỗi mệnh đề được xây dựng từ các vị từ (predicat). Một vị từ là một phát biểu nào đó về các đối tượng có giá trị chân lý đúng (true) hoặc sai (false). Một vị từ có thể có các đối là các nguyên tử (logic atom). 109
45. Mỗi nguyên tử biểu diễn một quan hệ giữa các hạng (term). Như vậy, hạng và quan hệ giữa các hạng tạo thành mệnh đề. Hạng được xem là những đối tượng dữ liệu trong một chương trình Prolog. Hạng có thể là hạng sơ cấp (elementary term) gồm hằng (constant) hay trực kiện (literal), biến (variable) và các hạng phức hợp (compound term). Các hạng phức hợp biểu diễn các đối tượng phức tạp của bài toán cần giải quyếtthuộc lĩnh vực đang xét. Hạng phức hợp là một hàm tử (functor) có chứa các đối (argument), có dạng: Tên_hàm_tử (đối_1, đối_2, ) Tên hàm tử là một chuỗi chữ cái hoặc chữ số được batư đầu bởi chữ cái. Các đối có thể là các biến, hạng sơ cấp, hoặc hạng phức hợp. Ví dụ các hàm tử: a(x, y, 5). Person(Hùng, 1980, địachỉ(15, Pasteur, ĐàNẵng)). Sau mỗi mệnh đề, Prolog quy ước kết thúc bởi một dấu chấm. Mệnh đề có thể là một sự kiện, một luật hay một câu hỏi. Mỗi mệnh đề được viết như sau: - Sự kiện: . - Luật: :- . - Câu hỏi: ?- . Các kiểu dữ liệu Prolog Hình 7.1 sau biểu diễn phân lớp các kiểu dữ liệu trong Prolog. Hình 7.1 Các kiểu dữ liệu trong Prolog kiểu dữ liệu kiểu sơ cấp kiểu phức hợp hằng biến số chuỗi kí tự nguyên tử Như thế, các kiểu dữ liệu gồm các kiểu sơ cấp và các kiểu phức hợp. Các kiểu sơ cấp gồm các kiểu hằng và biến. Kiểu hằng số gồm số nguyên và số thực. Cú pháp số nguyên và số thực rất đơn giản, ví dụ: 10 1111 546.67 -123.05 Các số thực rất ít được sử dụng trong Prolog, bởi vì Prolog là một ngôn ngữ lập trình kí hiệu, phi số. Kiểu hằng logic có giá trị true và fail. Kiểu hằng chuỗi kí tự được đặt giữa hai dấu nháy kép. Ví dụ: “Chuoi @ ki tu #” Chuỗi kí tự tùy ý “” Chuỗi rỗng Kiểu hằng nguyên tử là một chuỗi kí tự ở một trong 3 dạng sau: 110
46. 1. Chuỗi gồm chữ cái, chữ số và kí tự _ luôn được bắt đầu bởi một chữ cái in thường, ví dụ: ok student alain_smith x23 2. Chuỗi các kí hiệu đặc biệt: :::=== 3. Chuỗi đặt giữa hai dấu nháy đơn được bắt đầu bởi kí tự in hoa: ‘Alain Smith’ ‘No thing’ Biến là một chuỗi kí tự gồm chữ cái, chữ số, được bắt đầu bởi chữ in hoa hoặc dấu _: X, Y, Z Prog, Array_Of_Nat, _X, _A320 Kiểu dữ liệu phức hợp là các kiểu dữ liệu có cấu trúc (cây, danh sách, ), tương tự cấu trúc bản ghi, là đối tượng nhiều thành phần, mỗi thành phần lại có thể là một cấu trúc. Ví dụ: triangle(point(1, 4), point(6, 4), point(5, 8)) Chú thích Trong chương trình Prolog, chú thích (comment) được đặt giữa hai cặp ký hiệu /* và */. Ví dụ: / / / Đây là chú thích trong Prolog / / / Trong trường hợp muốn đặt một chú thích ngắn sau mỗi phần khai báo Prolog cho đến hết dòng thì có thể đặt trước kí hiệu %. Thực nghiệm ngôn ngữ lập trình Prolog Như chúng ta đã biết, một chương trình Prolog là một cơ sở dữ liệu gồm các mệnh đề. Mỗi mệnh đề hoặc là sự kiện hoặc là luật. Xây dựng sự kiện Một sự kiện khẳng định một thực thể có một vài tính chất nào đó. Để xây dựng các sự kiện chúng ta lấy ví dụ về cây gia hệ anna jerrry dam luc toto sam jan Hình 7.2.Ví dụ về cây gia hệ 111
47. Trong cây gia hệ, các nút chỉ người, các mũ tên chỉ quan hệ cha (hay mẹ) của (parent of). Sự kiện anna là cha (hay mẹ) của luc được viết thành vị từ như sau: parent(anna, luc). Vị từ parent có hai đối là anna và luc. Từ cây gia hệ trên chúng ta có thể viết các vị từ sau: parent(anna, luc). parent(jerry, luc). parent(jerry, dam). parent(luc, toto). parent(luc, sam). parent(toto, jan). Sau khi hệ thống nhận được chương trình này mà thực ra là một cơ sở dữ liệu thì người sử dụng có thể đặt ra các câu hỏi liên quan đến quan hệ parent. Chẳng hạn, câu hỏi luc có phải là cha (hay mẹ) của toto không được chuyển thành câu hỏi trong hệ thống đối thoại của Prolog như sau (dấu nhắc ?-): ?- parent(luc, toto). Sau khi tìm thấy sự kiện này, Prolog trả lời: Yes Tiếp tục đặt câu hỏi khác: ?- parent(luc, jan). No Bởi vì Prolog không tìm thấy sự kiện Luc là mẹ của Jan. Hơn nữa, chúng ta có thể đặt ra các câu hỏi khác. Chẳng hạn, ai là cha (hay mẹ) của của luc? ?- parent(X, luc). anna ; jerry Yes Với câu hỏi này Prolog sẽ có hai câu trả lời. Để biết câu trả lời tiếp theo, trong hầu hết các trình cài đặt Prolog, người sử dụng phải gõ vào dấu chấm phẩy (;) như trong ví dụ trên. Lưu ý, nếu đã hết phương án trả lời mà vẫn tiếp tục yêu cầu (;) thì Prolog trả lời No ngược lại trả lời Yes. Chúng ta có thể đặt các câu hỏi tổng quát hơn, như ai là cha (hay mẹ) của ai? Nói cách khác cần tìm tất cả X và Y sao cho X là cha (hay mẹ) của Y. Ta đặt câu hỏi như sau: ?- parent(X, Y). Sau khi nhận được câu hỏi trên, Prolog sẽ lân lượt tìm tất cả các cặp cha (hay mẹ) - conm thỏa mãn yêu cầu: X = anna Y = luc ; X = jerry 112
48. Y = luc ; X = jerry Y = dam ; X = luc Y = toto ; X = luc Y = sam ; X = toto Y = jan Yes Tùy theo trình cài đặt Prolog chúng ta có thể gõ vào một dấu chấm (.) hoặc Enter để chấm dứt giữa chừng luồng trả lời. Ngoài ra, chúng ta còn có thể đưa ra các câu hỏi phức tạp hơn, chẳng hạn ai là cháu của jerry. Thực tế, thì quan hệ cháu chưa được định nghĩa tuy nhiên chúng ta có thể tách câu hỏi thành hai thành phần sơ cấp: Ai là con của jerry? Giả sử có tên là X. Ai là con của X? Giả sử có tên là Y. Như vậy Y sẽ là cháu của jerry. Quan hệ cháu được thiết lập từ quan hệ cha (hay mẹ) (hay ngược lại là quan hệ con). Câu hỏi có thể được đặt ra như sau: ?- parent(jerry, X), parent(X, Y). Prolog trả lời: X = luc Y = toto ; X = luc Y = sam Yes Như thế, Prolog đưa ra hai trả lời là toto và sam. Mỗi câu hỏi trong Prolog được gọi là một đích (goal) cần phải được thỏa mãn. Nếu câu trả lời là Yes thì đích được thỏa mãn hay thành công, ngược lại câu trả lời là No thì đích là không được thỏa mãn hay thất bại. Xây dựng luật Từ chương trình Prolog trên, chúng ta có thể thêm vào các sự kiện về giới tính như sau: man(luc). man(jerry). man(dam). man(sam). woman(anna). woman(toto). woman(jan). 113
49. Trong ví dụ trên chúng ta đã nói đến quan hệ con, nhưng thực ra chúng ta vẫn chưa định nghĩa chúng mà chỉ coi là hệ quả của quan hệ cha (hay mẹ). Thật vây, jerry là cha (hay mẹ) của luc thì đương nhiên luc là con của jerry. Chúng ta có thể đưa vào quan hệ mới child như sau: child(luc, jerry). Thay vì định nghĩa từng sự kiện như thế này cho quan hệ cha (hay mẹ) - con, ta định nghĩa luật như sau: child(Y, X) :- parent(X, Y). Luật trên được hiểu là: với mọi X và Y, Y là con của X, nếu X là cha (hay mẹ) của của Y. Như thế, một luật bao gồm hai phần: - phần bên phải chỉ điều kiện, còn được gọi là thân (body) của luật; - phần bên trái chỉ kết luận, còn được gọi là đầu (head) của luật. Có sự khác nhau giữa sự kiện và luật. Một sự kiện luôn đúng, khong chịu bất cứ ràng buộc nào cả. Trong khi một luật chỉ đúng khi một số thuộc tính nào đó phải được thỏa mãn. Thật vậy, nếu parent(X, Y) là đúng thì child(Y, X) cũng phải đúng là kết quả logic của phép suy luận. Ngoài ra chúng ta có thể định nghĩa các luật (dấu phẩy (,) chỉ phép và logic (and)) để bổ sung thêm các quan hệ mới, như quan hệ mẹ/cha (mother/father) và quan hệ ông bà (grandparent). mother(X, Y) :- parent(X, Y), woman(X). father(X, Y) :- parent(X, Y), man(X). grandparent(X, Z) :- parent(X, Y), parent(Y, Z). Chẳng hạn quan hệ mẹ được hiểu là: với mọi X và Y, nếu X là cha (hay mẹ) của Y và X là phụ nữ thì X là mẹ của Y. Bây giờ chúng ta xem cách Prolog sử dụng các luật như thế nào. Giả sử ta đặt câu hỏi: luc có phải là con của anna không. ?- child(luc, anna). Trong chương trình không có sự kiện nào liên quan đến con, như thế phải tìm các luật. Luật trên áp dụng đối với đối tưuợng tổng quát bất kỳ mà ta lại quan tâm đến các đối tượng cụ thể luc và anna. Prolog sẽ sử dụng phép thế (substitution) bằng cách gán giá trị luc cho biến Y và anna cho biến X. Ta nói rằng X và Y đã được ràng buộc (bound): X = anna và Y = luc Lúc này phần điều kiện có giá trị parent(anna, luc) trở thành đích con (sub-goal) để Prolog thay thế cho đích child(luc, anna). Tuy nhiên, đích này chính là sự kiện đã có, nên câu trả lời sẽ là: Yes Ngoài ra, Prolog còn cung cấp chúng ta cách định nghĩa luật đệ quy (recursive rule). Bây giờ chúng ta muốn thêm quan hệ tổ tiên (ancestor). Ta phân biệt ra hai loại quan hệ: tổ tiên trực tiếp và tổ tiên gián tiếp. Tổ tiên trực tiếp được định nghĩa như sau: với mọi X và Z, X là tổ tiên trực tiếp của Z nếu X là cha hay mẹ của Z. 114
50. ancestor(X, Z):- parent(X, Z). Tổ tiên gián tiếp được định nghĩa phức tạp hơn, nếu càng mở rộng lớp hậu duệ. Chẳng hạn: ancestor(X, Z):- % tổ tiên là ông bà parent(X, Y), parent(Y, Z). ancestor(X, Z):- % tổ tiên là cố ông cố bà parent(X, Y1), parent(Y1, Y2), parent(Y2, Z). Tuy nhiên nhờ phép đệ quy, tổ tiên gián tiếp được định nghĩa một cách đơn giản hơn như sau: với mọi X và Z, X là tổ tiên của Z nếu tồn tại Y sao cho X là cha hay mẹ của Y và Y là tổ tiên của Z. ancestor(X, Z):- parent(X, Z). ancestor(X, Z):- parent(X, Y), ancestor(Y, Z). Nếu ta đặt câu hỏi: anna là tổ tiên của ai? ?- ancestor(anna, X). Câu trả lời sẽ là: X = luc ; X = toto ; X = sam ; X = jan Yes Trong Prolog, hầu hết các chương trình phức tạp đều sử dụng đệ quy, đệ quy là một khả năng mạnh của Prolog. Sử dụng biến trong Prolog Các biến xuất hiện trong các mệnh đề gọi là biến tự do. Người ta giải thiết rằng các biến là được lượng tử toàn thể và được đọc là “với mọi”. Tuy nhiên, có nhiều cách giải thích khác nhau trong trường hợp các biến chỉ xuất hiện trong phần bên phải của luật. Ví dụ: haveachild(X) :- parent(X, Y). có thể được đọc như sau: (a) Với mọi X và Y, nếu X là cha (hay mẹ) của Y thì X có một người con. (b) Với mọi X, X có một người con nếu tồn tại một Y sao cho X là cha (hay mẹ) của Y. Ngoài ra, khi một biến chỉ xuất hiện một lần trong các mệnh đề thì không cần đặt tên cho nó. Trong trường hợp này, Prolog cho phép sử dụng biến vô danh (anonymous variable) là các biến có tên chỉ là một dấu gạch dưới (_). 115
51. Quay trở lại với ví dụ trên, ta nhận thấy trong luật trên đích haveachild không phụ thuộc gì vào Y, nên ta có thể dùng biến vô danh như sau: haveachild(X) :- parent(X, _). Nghĩa là, X có một người con nếu X là cha (hay mẹ) của ai đó. Phạm vi sử dụng (lexical scope) của một biến trong một mệnh đề không vượt ra khỏi mệnh đề đó. Có nghĩa là, nếu một biến X xuất hiện trong hai mệnh đề khác nhau, thì sẽ tương ứng với hai biến phân biệt nhau. Logic trong Prolog Prolog có cú pháp là những công thức logic vị từ bậc một (first order predicate logic), được viết dưới dạng các mệnh đề (các lượng tử  và  xuất hiện không tường minh), nhưng hạn chế chỉ đơn thuần là các mênh đề Horn, là các mệnh đề được khẳng định là đúng. Prolog diễn giải chương trình là theo kiểu toán học: các sự kiện và các luật là các tiên đề, câu hỏi của người sử dụng như là một định lý cần khẳng định. Prolog sẽ tìm cách chứng minh định lý này, nghĩa là chỉ ra rằng định lý có thể được suy diễn một cách logic từ các tiên đề. Về mặt thủ tục, Prolog sử dụng phương pháp suy diễn quay lui (back-tracking) để hợp giải (resolution) bài toán, được gọi là chiến lược hợp giải. Có thể tóm tắt như sau: Để chứng minh P(a), người ta tìm sự kiện P(t) hoặc một luật P(t) :- L1, L2, , Ln sao cho a có thể hợp nhất được (unifiable) với t nhờ so khớp. Nếu tìm được sự kiện P(a) như vậy việc chứng minh là kết thúc. Còn nếu tìm được P(t) là luật, cần lần lượt chứng minh vế phải của L1, L2, , Ln nó. Trong Prolog, mỗi câu hỏi luôn là một dãy nhiều đích. Prolog trả lời câu hỏi là tìm cách làm thỏa mãn tất cả các đích hay còn gọi là xóa các đích. Nói cách khác, xóa một đích có nghĩa là đích này được suy ra một cách logic bởi các sự kiện và luật chứa trong chương trình. Nếu tất cả các đích của câu hỏi được xóa, câu trả lời là Yes, ngược lại là No. Giới thiệu lập trình hàm Ngôn ngữ lập trình hàm (functional programing language) là ngôn ngữ lập trình bậc cao, mang tính trừu tượng cao hơn so với ngôn ngữ mệnh lệnh. Khi lập trình với các ngôn ngữ hàm, người lập trình phải định nghĩa các hàm toán học dễ suy luận, dễ hiểu mà không cần quan tấm đến chúng được cài đặt thế nào trong máy. Ngôn ngữ hàm dựa trên việc tính giá trị của biểu thức được xây dựng từ bên ngoài lời gọi hàm. Ở đây, hàm là một hàm toán học thuần túy: là ánh xạ nhận các giá trị lấy từ một miền xác định để trả về giá trị thuộc một miền khác. Một hàm có thể có hoặc không có, các tham đối (arguments hay parameters) để sau khi tính toán, hàm trả về một giá trị nào đó. Chẳng hạn, có thể xem biểu thức 2 * 4 là một hàm tính nhân của hai tham đối là 2 và 4. Trong ngôn ngữ hàm, các biến toàn cục và phép gán bị loại bỏ, giá trị được tính bởi một hàm chỉ phụ thuộc vào các tham đối. Ngôn ngữ hàm thường được ứng dụng trong các lĩnh vực trí tuệ nhân tạo, giao tiếp hệ thống, xử lí kí hiệu, tính toán hình thức, 116
52. Ngôn ngữ hàm Scheme Giới thiệu Scheme Scheme là ngôn ngữ hàm thuộc học Lisp và mang tính sư phạm cao. Sheme có cú pháp đơn giản, dễ lập trình. Các cấu trúc dữ liệu cơ sở của Scheme là danh sách và cây, dựa trên khái niệm về kiểu dữ liệu trừu tượng. Một chương trình Scheme là một dãy các định nghĩa hàm (function) góp lại để định nghĩa một hoặc nhiều hàm phức tạp hơn. Hoạt động cơ bản trong lập trình Scheme là tính toán các biểu thức. Scheme làm việc theo chế độ tương tác với người sử dụng: - Người sử dụng gõ vào một biểu thức, sau mỗi dòng nhấn enter. - Hệ thống in kết quả (hoặc báo lỗi) và qua dòng mới. - Hệ thống đưa ra dấu nhắc và chờ người sử dụng nhập biểu thức tiếp theo. Để tiện theo dõi, chúng ta có các kí hiệu sau: - Kết quả tính toán được ghi sau dấu mũi tên ( >) - Các thông báo lỗi sai được đặt trước bởi ba dấu sao ( ). Chú thích trong Scheme được bắt đầu bởi một dấu chấm phẩy (;), viết trên một dòng bất kỳ, hoặc đầu dòng haợc cuối dòng. Ví dụ: ; đây là chú thích (= 1 1 1 1) ; so sánh 4 số Các kiểu dữ liệu của Scheme Trong scheme có hai loại kiểu dữ liệu: kiểu đơn gián và kiểu phức hợp. Trong phạm vi bài học này chúng ta chi xét các kiểu dữ liệu đơn giản bao gồm: kiểu số (number), kiểu logic (boolean), kiểu kí tự (character) và kiểu kí hiệu (symbol). Kiểu số Kiểu số của Scheme có thể là số nguyên, số thực, số hữu tỷ và số phức như sau: Kiểu số Ví dụ Số nguyên 10, 9999 Số thực 102.5, 1.7 Số hữu tỷ 6/7, 11/4 Số phức 2+5i, 4 Scheme không phân biệt số nguyên hay số thực. Các số không hạn chế về độ lớn miễn là bộ nhớ hiện tại cho phép. Với kiểu số, Scheme cũng sử dụng các phép toán số học thông dụng: +, -, *, /, sqrt, và các phép toán quan hệ: =, , >=, <=, với cú pháp như sau: (+ x1 x2 xn): tính tổng x1 + x2 + + xn (- x1 x2): tính x1 - x2 (* x1 x2 xn): tính tích x1 * x2 * * xn (/ x1 x2): tính x1/x2 (quotient x1 x2): tính phần nguyên của x1/x2, lấy dấu x1 (remainder x1 x2): tính phần nguyên của x1/x2, lấy dấu x2 117
53. Các phép so sánh sau đây trả về #t (đúng) nếu kết quả so sánh lần lượt các giá trị x1, x2, , xn được thỏa mãn, ngược lại trả về #f (sai): (= x1 x2 xn) (> x1 x2 xn) ( = x1 x2 xn) ( 21 (= 1 2 3 4 5) > #f ( #t (* 2/3 1/2) > 2/6 Kí tự Trong của kí tự Scheme có dạng #\ . Ví dụ: #\a ; kí tự a thường > #\a #\A ; kí tự a hoa > #\A Chuỗi Chuỗi là dãy kí tự tùy ý đặt giữa hai dấu nháy kép. Ví dụ: ”Chào các bạn !” > ” Chào các bạn ! ” Tên Tên được tạo thành từ các chữ cái, chữ số và dấu đặc biệt trừ # ( ) [] và dấu cách. Tên trong Scheme không phân biệt chữ in hoa hay in thường. Ví dụ các tên hợp lệ: pi ; không phân biệt với PI hay Pi x lambda Kiểu logic Kiểu logic (boolean) trong Scheme là các hằng được định nghĩa sẵn: #t (true) và #f (false). Vị từ Vị từ (predicate) là một hàm luôn trả về giá trị logic. Theo quy ước tên của các vị từ được kết thúc bởi dấu chấm hỏi (?). Thư viện Scheme có sẵn nhiều vị từ. Sau đây là một số vị từ dùng để kiểm tra kiểu giá trị của một biểu thức: (number? s) > #t nếu s là số thực, #f nếu không 118
54. (integer? s) > #t nếu s là số nguyên, #f nếu không (string? s) > #t nếu s là một chuỗi, #f nếu không (boolean? s) > #t nếu s là một logic, #f nếu không Ví dụ: (number? 111) > #t (string? 111) > #f (string? ”111”) > #t Kí hiệu Scheme xử lý kí hiệu (symbol) nhờ phép trích dẫn. Giá trị kí hiệu của Scheme là một tên (giống tên biến) mà không gắn với một giá trị nào khác. Để chỉ cho Scheme một giá trị kí hiệu ta sử dụng phép trích dẫn (quote operator). Ví dụ, kí hiệu sam: ‘sam > sam Kí tự ‘ là cách viết tắt của hàm quote: ‘ tương đươg (quote ) Để kiểm tra xem một biểu thức có phải là một kí hiệu hay không người ta sử dụng vị từ symbol? như sau: (symbol? ‘hello) > #t (symbol? ”hello”) > #f Ví dụ này chỉ rằng không nên nhầm lẫn kí hiệu với chuỗi. Khái niệm về biểu thức tiền tố Có nhiều cách để biểu diễn biểu thức, Scheme sử dụng dạng ngoặc tiền tố: nguyên tắc là viết các phép toán rồi mới đến các toán hạng và đặt tất cả trong dấu ngoặc. Ví dụ, biểu thức số học 2 + 3 được viết thành (+ 2 3). Một cách tổng quát, nếu op chỉ định một phép toán hai ngôi, một biểu thức số học có dạng: exp1 op exp2 sẽ được viết dưới dạng: (op ~exp1 ~exp2) trong đó ~exp1 và ~exp2 cũng là các biểu thức dạng tiền tố. Ví dụ biểu thức số học 1 + 2 + 3 được viết thành (+ 1 2 3). Ngoài ra, chíng ta có thể trộn lẫn các phép toán: 2*3 + 4*5*6 được viết thành (+ (* 2 3) (* 4 5 6)). Ví dụ, một biểu thức toán học phức tạp: (cos(a) + sin(a))/(a2 + b2) được viêt thành: (/ (+ (cos a) (cos b)) (+ (* a a) (* b b))) 119