Chương 8 Chương trình con

Chương 8 CHƯƠNG TRÌNH CON Lý thuyết ngôn ngữ lập trình Nội dung Khái niệm Đặc tả và cài đặt chương trình con Phương pháp truyền tham số cho chương trình con chương trình con chung Đồng thường trình Thực thi chương trình con Khái niệm Có hai khả năng trừu tượng hoá cơ bản có thể được bao gồm trong một NNLT là: • sự trừu tượng hoá quá trình • sự trừu tượng hoá dữ liệu. Trong thời kỳ đầu của NNLT bậc cao, chỉ có sự trừu tượng hoá quá trình. Trong thập niên 80 của thế kỷ 20, nhiều người đã bắt đầu tin rằng sự trừu tượng hoá dữ liệu là cũng quan trọng như sự trừu tượng hoá quá trình. Khái niệm Máy tính có thể lập trình được đầu tiên, Babbages’s Analytical Engine, được xây dựng trong những năm 1940, đã có khả năng sử dụng lại các tập hợp của các thẻ đục lỗ mang lệnh trong các vị trí khác nhau của chương trình. Trong một NNLT hiện đại, những thẻ đục lỗ mang lệnh đó giống như là các tập hợp các câu lệnh được viết ra và được gọi là chương trình con. Chương trình con là một phép toán trừu tượng được định nghĩa bởi người lập trình. Khái niệm (tt) Chương trình con có các đặc tính chung như sau: - Tất cả chương trình con đều chỉ có một điểm vào (entry point). - Chương trình gọi bị tạm dừng trong suốt thời gian nó gọi chương trình con thực thi, có nghĩa là chỉ có một chương trình con duy nhất (thuộc chương trình đó) được thực thi trong thời gian đó. - Điều khiển luôn luôn được trả về cho chương trình gọi khi việc thực thi chương trình con kết thúc. Đặc tả và cài đặt chương trình con Đặc tả chương trình con Sự đặc tả chương trình con bao gồm: - Tên của chương trình con - Số lượng các tham số, thứ tự của chúng và kiểu dữ liệu của mỗi một tham số. - Số lượng các kết quả, thứ tự của chúng và kiểu dữ liệu của mỗi một kết quả. - Hoạt động được thực hiện bởi chương trình con. Đặc tả và cài đặt chương trình con Chương trình con biểu diễn một hàm toán học, là một ánh xạ từ tập hợp các tham số đến tập hợp các kết quả. Chương trình con trả về một kết quả duy nhất trong tên chương trình con thường được gọi là một hàm. Cú pháp điển hình đặc tả hàm được quy định trong ngôn ngữ lập trình C như sau: () { } Đặc tả và cài đặt chương trình con (tt) Trong đó : + Tên hàm : buộc phải có. + Danh sách các đối số : không bắt buộc. Có hay không tuỳ theo chúng ta định dùng hàm đó làm gì. + Khai báo biến : Nếu Danh sách các đối số mà có thì phần này buộc phải có. Còn nếu không thì ngược lại có thể bỏ qua. + Phần trong { } : là thân hàm. Dấu { } là bắt buộc đối với mọi hàm. + : ngay sau { và gọi là biến cục bộ dành riêng cho hàm sử dụng. + đối số luôn luôn truyền theo trị ( không thay đổi giá trị). Đặc tả và cài đặt chương trình con (tt) Ví dụ : Chương trình C tính giai thừa có sử dụng chương trình con. #include unsigned long giaithua(int n) { unsigned long ketqua = 1; int i; for (i=2; i<=n; i++) ketqua *= i; return ketqua; } Đặc tả và cài đặt chương trình con (tt) void main() { int n; printf("\nNhap vao gia tri N : "); scanf("%d", &n); printf("%d! = %lu", n, giaithua(n)); getch(); } Đặc tả và cài đặt chương trình con (tt) Nếu chương trình con trả về nhiều hơn một kết quả hoặc không có kết quả trả về trong tên chương trình con thường được gọi là thủ tục (procedure hoặc subroutine). Đặc tả và cài đặt chương trình con (tt) Chúng ta xét một thủ tục được viết trong ngôn ngữ lập trình Pascal như sau: Ví dụ: Procedure Docdl; Var i:integer; Begin Readln(fi,n); For i:=1 to n do read(fi,a[i]); end; Trong ví dụ này, tham số có tên đứng sau VAR biểu thị một kết quả hoặc một tham số có thể bị thay đổi. Đặc tả và cài đặt chương trình con (tt) Mặc dù chương trình con biểu diễn một hàm toán học nhưng nó cũng có các vấn đề tương tự như đối với các phép toán nguyên thuỷ: - Chương trình con có thể có các tham số ẩn trong dạng biến non-local mà nó tham chiếu. - Chương trình con có thể có kết quả ẩn (hiệu ứng lề) được trả về thông qua sự thay đổi các biến non-local hoặc thông qua việc thay đổi các tham số vào-ra của nó. Đặc tả và cài đặt chương trình con (tt) - Chương trình con có thể nhạy cảm với tiền sử (tự sửa đổi), có nghĩa là kết quả của nó không chỉ phụ thuộc vào tham số được cho tại lần gọi đó mà còn phụ thuộc vào toàn bộ lịch sử các lần gọi trước đó. Nhạy cảm với tiền sử có thể do dữ liệu cục bộ vẫn còn giữ lại giữa các lần gọi của chương trình con hoặc thông qua sự thay đổi mã riêng của nó (ít phổ biến hơn). Đặc tả và cài đặt chương trình con (tt) Cài đặt chương trình con Các phép toán nguyên thuỷ được cài đặt bằng cách dùng cấu trúc dữ liệu và các phép toán được cung cấp bởi máy tính ảo bên dưới ngôn ngữ lập trình. Chương trình con biểu diễn một phép toán được xây dựng bởi người lập trình và do đó chương trình con được cài đặt bằng cách dùng cấu trúc dữ liệu và các phép toán được cung cấp bởi chính bản thân ngôn ngữ lập trình đó. Đặc tả và cài đặt chương trình con (tt) Sự cài đặt được xác định bởi thân chương trình con, bao gồm cả việc khai báo dữ liệu cục bộ xác định cấu trúc dữ liệu được dùng cho chương trình con và các lệnh xác định hành động sẽ làm khi chương trình con thực hiện. Đặc tả và cài đặt chương trình con (tt) Sự khai báo và các lệnh thường được bao gói, người sử dụng chương trình con không thể truy xuất được tới dữ liệu cục bộ và các lệnh bên trong chương trình con. Người sử dụng chỉ có thể gọi chương trình con với một tập hợp các tham số và nhận lại các kết quả đã được tính toán. Đặc tả và cài đặt chương trình con (tt) Thông thường trong chương trình con còn có thể có các chương trình con khác biểu thị các phép toán được định nghĩa bởi người lập trình và các chương trình con đó chỉ dùng cho chương trình con chứa chúng. Những chương trình con "cục bộ" này được bao gói, nghĩa là chúng không thể được gọi tới từ bên ngoài chương trình con chứa chúng. Đặc tả và cài đặt chương trình con (tt) Kiểm tra kiểu cũng là một vấn đề quan trọng đối với chương trình con. Mỗi lần gọi chương trình con đòi hỏi các tham số có kiểu đúng như đã được xác định trong sự đặc tả chương trình con. Kiểu của kết quả được trả về của chương trình con cũng phải được biết đến. Đặc tả và cài đặt chương trình con (tt) Vấn đề kiểm tra kiểu tương tự như đối với các phép toán nguyên thuỷ. Kiểm tra kiểu có thể được thực hiện một cách tĩnh trong quá trình dịch, nếu đã có sự khai báo kiểu cho các tham số và kết quả của mỗi một chương trình con. Mặt khác kiểm tra kiểu có thể là động trong quá trình thực hiện chương trình. Sự chuyển đổi kiểu ẩn các tham số để đổi chúng thành các kiểu đúng cũng có thể được cung cấp một cách tự động bởi sự cài đặt ngôn ngữ. Đặc tả và cài đặt chương trình con (tt) Ví dụ 8.3: #include unsigned USCLN (unsigned n, unsigned m) { while (n != 0 && m != 0) if (n>m) n -= m; else m -= n; if (n == 0) return m; else return n; } Đặc tả và cài đặt chương trình con (tt) unsigned BSCNN (unsigned n, unsigned m) { return n * m / USCLN(n, m); } void main() { unsigned n, m; printf("\nNhap hai vao so nguyen duong : "); scanf("%u%u", &n, &m); printf("\nUSCLN cua %u va %u = %u", n, m, USCLN(n,m)); printf("\nBSCNN cua %u va %u = %u", n, m, BSCNN(n,m)); getch(); } Phương pháp truyền tham số cho chương trình con Phương pháp truyền tham số cho chương trình con là lộ trình mà trên đó các tham số được truyền đến và/hoặc truyền từ các chương trình con được gọi. Tham số có hai loại là tham số hình thức và tham số thực tế. Tham số hình thức là một loại đặc biệt của ÐTDL cục bộ trong chương trình con. Nó được xác định lúc định nghĩa chương trình con. Khi định nghĩa chương trình con, phải xác định một danh sách các tham số hình thức cùng với khai báo kiểu tương ứng. Phương pháp truyền tham số cho chương trình con Tham số thực tế là một ÐTDL được gởi cho chương trình con bằng cách truyền trong lời gọi thực hiện chương trình con. Hay nói cách khác, tham số thực tế là giá trị của biến tại thời gian chạy chương trình. Thông thường, tham số hình thức được gọi là tham số, còn tham số thực tế còn được gọi là đối số. Phương pháp truyền tham số cho chương trình con (tt) Chúng ta xét ví dụ sau để phân biệt giữa tham số hình thực và tham số thực tế. Ví dụ : int sum(int a, int b) { return (a+b); } int sumValue; int value1 = 20; int value2 = 40; sumValue = sum(value1,value2); Phương pháp truyền tham số cho chương trình con (tt) Như vậy hàm sum có hai tham số hình thức là a và b. Khi hàm sum được gọi trong lệnh gán sumValue = sum(value1,value2), hai tham số thực sự là 20 và 40, còn hai biến value1 và value2 chỉ là hai biến được khởi tạo với hai giá trị là 20 và 40. Phương pháp truyền tham số cho chương trình con (tt) Các tham số hình thức được khai báo bằng một trong ba mô hình ngữ nghĩa (semantic model) riêng biệt sau: + In mode: chúng có thể nhận dữ liệu từ tham số thực tế tương ứng; + Out mode: chúng có thể chuyển dữ liệu cho các tham số thực tế; + In-out mode: chúng có thể làm cả hai việc đó. Phương pháp truyền tham số cho chương trình con (tt) Có nhiều phương pháp truyền tham số được phát triển bởi các nhà thiết kế ngôn ngữ để lập trình viên có thể lựa chọn để xác định khai báo tham số hình thức khi định nghĩa chương trình con và cung cấp các tham số thực tế khi thực hiện gọi chương trình con. Phương pháp truyền tham số cho chương trình con (tt) Truyền bằng giá trị (Pass-by-Value) Truyền bằng giá trị thực thi cho các tham số In-mode. Trong phương pháp này, tham số hình thức là tham số chỉ vào (IN-only parameters), tức là chỉ nhận giá trị vào cho chương trình con, không có nghĩa vụ trả kết quả về cho chương trình gọi. Tham số hình thức được xem như là một biến cục bộ của chương trình con và được cấp phát ô nhớ riêng. Còn tham số thực tế là một biểu thức (là một biến, một hằng, một hàm hoặc là một biểu thức thực sự). Phương pháp truyền tham số cho chương trình con (tt) Phương pháp thực hiện: Tại thời điểm gọi, giá trị của tham số thực tế được sao chép vào trong ô nhớ của tham số hình thức. Trong quá trình thực hiện chương trình con, mọi thao tác trên tham số hình thức là sự thao tác trên ô nhớ riêng của nó, không ảnh hưởng đến tham số thực tế. Khi chương trình con kết thúc, sự thay đổi giá trị của tham số hình thức, không làm ảnh hưởng đến giá trị của tham số thực tế. Phương pháp truyền tham số cho chương trình con (tt) Ví dụ : Chương trình hoán vị 2 số nguyên #include void hoanvi(int k, int h) { int j; j = k; k = h; h = j; } Phương pháp truyền tham số cho chương trình con (tt) void main() { int a,b; a = 40; b = 100; hoanvi(a,b); getch(); } Phương pháp truyền tham số cho chương trình con (tt) Truyền bằng kết quả (Pass-by-Result) Truyền bằng kết quả là một phương pháp thực thi cho các tham số Out-mode. Trong phương pháp này, tham số hình thức là tham số chỉ ra (OUT-only parameters), tức là chỉ trả kết quả về cho chương trình gọi, không có nghĩa vụ nhận giá trị vào cho chương trình con. Tham số hình thức được xem như là một biến cục bộ của chương trình con và được cấp phát ô nhớ riêng. Còn tham số thực tế phải là một biến, tức là một ĐTDL có ô nhớ. Phương pháp truyền tham số cho chương trình con (tt) Phương pháp thực hiện: Giá trị của tham số thực tế không được sử dụng trong chương trình con. Tham số hình thức có thể được gán trị như đối với một biến cục bộ. Trong quá trình thực hiện chương trình con, mọi thao tác trên tham số hình thức là sự thao tác trên ô nhớ riêng của nó, không ảnh hưởng đến tham số thực tế. Khi chương trình con kết thúc, giá trị cuối cùng của tham số hình thức được sao chép vào ô nhớ của tham số thực tế. Phương pháp truyền tham số cho chương trình con (tt) Ví dụ : Chương trình hoán vị 2 số nguyên #include void hoanvi(int k, int h) { int j; k =10; h = 20; j = k; k = h; h = j; } Phương pháp truyền tham số cho chương trình con (tt) void main() { int a,b; a = 40; b = 100; hoanvi(a,b); getch(); } Phương pháp truyền tham số cho chương trình con (tt) Truyền bằng giá trị-kết quả (Pass-by- Value-Result) Truyền bằng giá trị-kết quả là một hình thức thực thi cho các tham số inout-mode, mà trong đó các tham số thực tế được sao chép lại. Trên thực tế, đây là một sự kết hợp của truyền bằng giá trị và truyền bằng kết quả. Giá trị của tham số thực tế được dùng như là giá trị khởi đầu của tham số hình thức tương ứng, và các tham số này sau đó hoạt động như một biến cục bộ. Phương pháp truyền tham số cho chương trình con (tt) Trên thực tế, khi truyền bằng giá trị-kết quả các tham số hình thức phải có bộ nhớ cục bộ kết hợp với chương trình con được gọi. Tại thời điểm dùng chương trình con, giá trị của tham số hình thức được trả về lại cho tham số thực tế. Phương pháp truyền tham số cho chương trình con (tt) Phương pháp thực hiện: Tại thời điểm gọi chương trình con, giá trị của tham số thực tế được sao chép vào trong ô nhớ của tham số hình thức. Trong quá trình thực hiện chương trình con, mọi thao tác trên tham số hình thức là sự thao tác trên ô nhớ riêng của nó, không ảnh hưởng đến tham số thực tế. Khi chương trình con kết thúc, giá trị cuối cùng của tham số hình thức được sao chép vào ô nhớ của tham số thực tế. Phương pháp truyền tham số cho chương trình con (tt) Phương pháp này nhiều khi còn được gọi là truyền bằng cách sao chép (pass-by- copy), bởi vì các tham số thực tế được sao chép cho các tham số hình thức tại đầu vào của chương trình con và được sao chép ngược lại tại thời điểm dừng chương trình con. Truyền bằng giá trị-kết quả có hạn chế giống như truyền bằng giá trị và truyền bằng kết quả đó là việc đòi hỏi nhiều bộ nhớ cho các tham số và thời gian sao chép các giá trị. Phương pháp truyền tham số cho chương trình con (tt) Ví dụ : Chương trình hoán vị 2 số nguyên #include void hoanvi(int k, int h) { int a,b; int j; j = k; k = h; h = j; a = k; b = h; } Phương pháp truyền tham số cho chương trình con (tt) void main() { int a,b; a = 40; b = 100; hoanvi(a,b); getch(); } Phương pháp truyền tham số cho chương trình con (tt) Truyền bằng tham chiếu (Pass-by- Reference) Truyền bằng tham chiếu là phương pháp thực thi thứ hai cho các tham số inout- mode. Tham số hình thức là tham số vào ra (IN-OUT parameters), do đó nó có nghĩa vụ nhận giá trị vào cho chương trình con và trả kết quả về cho chương trình gọi. Tham số hình thức là một con trỏ và tham số thực tế phải là một biến, tức là một ĐTDL có ô nhớ. Phương pháp truyền tham số cho chương trình con (tt) Phương pháp thực hiện: Tại thời điểm gọi, nó truyền một đường dẫn truy cập (access path), thông thường chỉ là một địa chỉ, đến chương trình con được gọi. Điều này cung cấp đường truy cập đến ô nhớ lưu trữ tham số thực sự. Do vậy, chương trình con được phép truy cập đến tham số thực tế của chương trình chủ. Khi chương trình con kết thúc, mọi thay đổi giá trị của tham số hình thức đều làm giá trị của tham số thực tế thay đổi theo. Trên thực tế, tham số thực tế được chia sẻ với chương trình con được gọi. Phương pháp truyền tham số cho chương trình con (tt) Ví dụ a: void incInt(int *y) { (*y)++; // tăng giá trị của x trong main 1 đơn vị } void main(void) { int x = 0; incInt(&x); // chuyển một tham chiếu vào incInt cho 'x' } Phương pháp truyền tham số cho chương trình con (tt) Ví dụ b: void setInt(int **p, int n) { *p = (int *) malloc(sizeof(int)); // đăng kí một vùng nhớ *p = n; // cài giá trị vào } void main(void) { int *p; //khai báo một con trỏ kiểu integer setInt(&p, 42); // chuyển giá trị của 'p' vào. } Phương pháp truyền tham số cho chương trình con (tt) Ngoài bốn phương pháp trên, còn một phương pháp đó là truyền bằng tên, là một phương pháp truyền các tham số inout-mode. Tuy nhiên, phương pháp này không được dùng rộng rãi trong các ngôn ngữ. Nó chỉ được dùng tại thời điểm biên dịch bằng các dãy lệnh trong các hợp ngữ và cho các tham số chung của chương trình con chung trong ngôn ngữ C++ và Ada Chương trình con chung Việc dùng lại phần mềm là một đóng góp quan trọng trong việc làm tăng hiệu quả của phần mềm. Một cách để tăng khả năng có thể sử dụng lại của phần mềm là giảm việc tạo ra các chương trình con khác nhau, mà các chương trình con này thực thi với một thuật toán giống nhau với các kiểu dữ liệu khác nhau. Ví dụ, một lập trình viên không cần thiết phải viết bốn chương trình con sắp xếp khác nhau cho việc sắp xếp bốn mảng mà bốn mảng này chỉ khác nhau ở kiểu của các phần tử. Chương trình con chung (tt) Sự đặc tả chương trình con thông thường liệt kê số lượng, thứ tự và kiểu dữ liệu của các tham số. Chương trình con chung (generic subprogram) là một chương trình con có một tên nhưng có nhiều định nghĩa khác nhau, được phân biệt bởi số lượng, thứ tự và kiểu dữ liệu của các tham số. Hay nói cách khác, một chương trình con chung, hay còn gọi là chương trình con đa hình (polymorphic subprogram), nhận các tham số với nhiều kiểu khác nhau trong các hoạt động khác nhau. Chương trình con chung (tt) Một khi phép toán hay chương trình con chung xuất hiện, vấn đề cơ bản đối với trình biên dịch là làm sao xác định được đúng ý nghĩa của nó trong một tập hợp nhiều ý nghĩa có thể có. Thông tin về đối số của phép toán hoặc tham số của chương trình con giúp chương trình dịch nhận biết ý nghĩa đích thực của chương trình con chung. Chương trình con chung (tt) Ví dụ : Chương trình tính tổng 2 số #include int sum(int k, int h) { return (k + h); } double sum(double a, double b) { return (a + b); } Chương trình con chung (tt) void main() { int a,b; a = 40; b = 100; sum(a,b); double m,n; m = 5.5; n = 10; sum(m,n); getch(); } Đồng thường trình Đồng thường trình là một loại đặc biệt của chương trình con. Thay cho mối quan hệ chủ-tớ giữa chương trình gọi (chủ) và chương trình con được gọi trong cách gọi chương trình con truyền thống, quan hệ giữa chương trình gọi và các đồng thường trình được gọi trên cơ sở công bằng hơn. Trong thực tế, kỹ thuật điều khiển đồng thường trình thường được gọi là mô hình điều khiển đơn vị đối xứng (the symmetric unit control model). Đồng thường trình Ví dụ như A và B là hai chương trình con trong một chương trình. Trong A có lời gọi đến B và trong B có lời gọi đến A. Khi đó, A và B được gọi là đồng thường trình. Đồng thường trình (tt) Đồng thường trình có nhiều điểm vào, và các điểm vào đó được điều khiển bởi chính đồng thường trình. Các điểm vào đó còn có ý nghĩa để duy trì trạng thái của chúng giữa các hoạt động. Có nghĩa là các đồng thường trình phải có các biến cục bộ tĩnh (do chúng nhạy với lịch sử - history- sensitive). Lần thực thi thứ hai của một đồng thường trình thường bắt đầu tại một điểm vào khác với điểm vào của lần đầu tiên. Điều đó là bởi vì, nguyên tắc của đồng thường trình là được gọi thực hiện lại (resume) thay cho một lời gọi mới. Đồng thường trình (tt) Một trong những đặc trưng của chương trình con được duy trì trong các đồng thường trình là: Chỉ duy nhất một đồng thường trình thực sự thực thi trong một thời điểm. Tuy nhiên, thay cho việc thực thi chúng đến hết, các đồng thường trình thường thực thi một phần sau đó chuyển điều khiển đến một đồng thường trình khác. Khi được khởi động lại, một đồng thường trình sẽ thực thi phần tiếp ngay sau mệnh đã đề được dùng để chuyển điều khiển. Đồng thường trình (tt) Việc sắp xếp tuần tự các thực thi chen giữa đó phụ thuộc vào cách làm việc của các hệ thống đa lập trình (multiprogramming operating systems). Mặc dù có thể chỉ có một bộ xử lý, nhưng tất cả các chương trình thực thi thuộc một hệ thống