Chương 4: Chương trình con (SubPrograms)

Giảng viên: Ph.D Nguyễn Văn Hòa Khoa KT-CN-MT – ðH An Giang

1

Pascal Code Fragment

procedure C;

procedure A (P : procedure; i : integer);

procedure B; begin B

write(i);

end B;

begin A

if i = 1 then A(B,2) else P;

end A; begin main A(C,1); end main.

2

JavaScript Code Fragment

function sub1() {

var x; function sub2() { alert(x);

}; function sub3() {

var x; x = 3; sub4(sub2);

}; function sub4(subx) {

var x; x = 4; subx();

}; x = 1; sub3();

};

3

Chương trình con chung C++

template

Type max(Type first, Type second) {

return first > second ? first : second;

}

int max(int first, int second) {

return first > second ? first : second;

}

4

Nội dung chính của chương

(cid:1) Giới thiệu chương trình con (cid:1) Cơ chế gọi chương trình con (cid:1) Truyền tham số cho chương trình con (cid:1) Chương trình con ña năng (overloaded) (cid:1) Chương trình con chung (generic)

5

Giới thiệu

(cid:1) Có hai cách trù tượng hóa

(cid:2) Trù tượng tiến trình (process abstraction): ñược chú

trọng ngày từ rất sớm

(cid:2) Trù tượng dữ liệu (data abstraction): ñược chú trọng

trong 1980s

(cid:1) Chương trình con (CTC):

(cid:2) Một phép toán trừu tượng tiến trình (process) ñược

ñịnh nghĩa bởi người lập trình

(cid:2) Khi một khối công việc ñược lặp ñi lặp lại nhiều lần

trong chương trình → CTC

(cid:2) Hoặc CTC ñược dùng ñể tách một khối công việc cụ

thể, ñể chương trình chính ñỡ phức tạp

6

Giới thiệu (tt)

(cid:1) ðặc tính cơ bản của CTC

(cid:2) Mỗi chương trình con có một ñiểm vào duy nhất (cid:2) Chương trình gọi CTC thì tạm dừng trong khoảng thời

gian thực hiện CTC

(cid:2) Ðiều khiển luôn ñược trả về chương trình gọi khi kết

thúc chương trình con (cid:2) Mô hình Master/Client

(cid:1) Hai khía cạnh khi nói ñến CTC

(cid:2) ðịnh nghĩa CTC (cid:2) Lời gọi CTC

7

Giới thiệu (tt)

(cid:1) CTC có thể truy xuất dữ liệu : (cid:2) Truy xuất các biến không cục bộ (cid:2) Truyền tham số (cid:1) Ưu ñiểm của CTC

(cid:2) Cho phép sử dụng nhiều lần 1 chức năng/khối công

việc ~ CTC → tiết kiệm không gian lưu trữ code và ẩn giấu các chi tiết của CT

(cid:2) Tăng tính dễ ñọc hiểu của CT vì dễ dàng thấy cấu trúc

ñiều khiển của CT hơn

(cid:2) Phát hiện và sữa lỗi dễ dàng

8

Mô hình cài ñặt CTC

(cid:1) Mô hình cài ñặt của CTC trong các NNLT có thể

khác nhau

(cid:1) ðiều khiển tuần tự (Imperative) :

(cid:2) Thủ tục : một khối các câu lệnh ñể thực hiện 1 chức

năng

(cid:2) Hàm : một khối câu lệnh trả về 1 kết quả duy nhất (cid:2) Ngôn ngữ C không phân biệt hàm và thủ tục

(cid:1) Hàm: VD Hàm tính dãy Fibonacci (cid:1) Logic: Mệnh ñề Horn (Horn claus)

9

ðặc tả của CTC

(cid:1) Tên của CTC (cid:1) Số lượng, thứ tự và kiểu của các tham số (ñối số) (cid:2) Tham số hình thức: là danh sách các tham số ñược

dùng trong CTC ở phần Header của CTC

(cid:2) Tham số thực: là các giá trị hoặc ñịa chỉ ô nhớ ñược

dùng trong lời gọi CTC

(cid:2) Header CTC = Tên + tham số hình thức

(cid:1) Hoạt ñộng của CTC hay phần thân (body) (cid:2) Các khối như các khai báo, các câu lệnh, etc (cid:1) Số lượng kết quả trả về và kiểu của chúng

10

VD CTC (thủ tục) trong Pascal

procedure count(k: array[1..5] of real);

const

type

var

// nested procedures and functions go here begin

end;

11

VD CTC (thủ tục) trong Ada

procedure Display_Even_Numbers is

< declarations> function even (number:integer) return boolean is

begin

end even; begin end Display_Even_Numbers;

12

Các yếu tố khi thiết kế CTC

(cid:1) Các hình thức truyền tham số: tham trị hay quy

chiếu,…?

(cid:1) Có kiểm tra kiểu hay không? (cid:1) Các biến cục bộ là tĩnh (static) hay ñộng? (cid:1) Một CTC có thể ñược khai báo lòng vào một CTC

khác không?

(cid:1) CTC có ñược ña năng hóa (overloaded) không? (cid:1) CTC là chung hay không (generic subprogram)?

13

Các biến cục bộ (local) của CTC

(cid:1) Các biến cục bộ ñộng stack

(cid:2) Liên kết vào các ô nhớ khi CTC bắt ñầu ñược thực hiện và

hủy liên kết khi kết thúc CTC

(cid:2) Ưu ñiểm

(cid:1) Hỗ trợ ñệ qui (cid:1) Ô nhớ dành cho các biến cục bộ có thể ñược shared giữa các

CTC (cid:2) Khuyết ñiểm

(cid:1) Cần thời gian cấp, giải phóng và khởi tạo (cid:1) Không thể lưu giá trị của biến giữa các lần gọi CTC

(cid:1) Các biến cục bộ tĩnh

(cid:2) Hiệu quả hơn (cid:2) Không hỗ ñệ qui (cid:2) Không thể chia sẽ các ô nhớ

14

Các biến cục bộ của CTC (tt)

(cid:1) Trong C và C++ biến cục bộ ñược khai báo tĩnh nếu ñứng

sau static int adder (int list[], int listlen){

static int sum = 0; int count; for (count=0; count

}

(cid:1) // count là biến cục bộ ñộng stack (cid:1) // sum biến tĩnh

15

Truyền tham số

(cid:1) Khi gọi CTC, các tham số ñược truyền bằng một

trong các cách sau ñây : (cid:2) Truyền tham trị (Pass-by-value) (cid:2) Truyền kết quả (Pass-by-result) (cid:2) Truyền trị và kết quả (Pass-by-value-result) (cid:2) Truyền quy chiếu (Pass-by-reference)

16

Các mô hình truyền tham số

17

Truyền tham trị - In Mode

(cid:1) Giá trị của tham số thực ñược dùng ñể truyền vào

tham số hình thức tương ứng (cid:2) Cách cài ñặt bình thường là copy (cid:2) Có thể cài ñặt bằng cách truyền ñịa chỉ nhưng cách này không ñược khuyến khích (vì ñòi hỏi biến phải ñược ñặt ở chế ñộ write-protection)

(cid:2) Khi tác vụ copy ñược dùng → cần thêm không gian

lưu trữ

(cid:2) Lưu trữ và tác vụ copy có thể mất thời gian

(cid:1) Trị cuối cùng của tham số thực bị mất khi CTC

kết thúc

18

Truyền tham trị - In Mode (tt)

(cid:1) Các NNLT hỗ trợ : C, Pascal, Ada, Scheme, Algol68

{ c : array [1..10] of integer;

m,n: integer; procedure r(k,j: integer);

begin

k:=k+1; /* m = 6 */ j:= j+2; /* n = 5 */

end; begin m := 5; n:=3; r(m,n); writeln(m,n); /* 5 & 3 */

}

19

Truyền kết quả - Out Mode

(cid:1) Tham số thực không truyền giá ñến CTC; tham số hình thức tương ứng ñống vai trò như biến cục bộ nhưng khi kết thúc CTC thì trị của tham số này ñược trả về cho tham số thực (cid:2) Yêu cầu không gian lưu trữ và tác vụ copy (cid:2) Tham số thực phải là 1 biến (cid:1) Khả năng bị ñụng ñộ về tham số

(cid:2) Sub(p1,p1); một khi tham số hình thức ñược copy trở lại thì

lần copy sau cũng thể hiện trị của p1

(cid:1) NNLT hỗ trợ : Ada

20

Truyền tham trị & kết quả - Inout Mode

(cid:1) Sự kết hợp truyền trị và truyền kết quả (pass-by-value

and pass-by-result)

(cid:1) Tham số hình thức cần không gian lưu trữ cục bộ (cid:1) Tham số hình thức phải là 1 biến (có ô nhớ), copy trị (cid:1) Giá trị cuối cùng của tham số hình thức ñược copy

cho tham số thực

(cid:1) Khuyết ñiểm:

(cid:2) Các khuyết ñiểm của truyền tham trị (cid:2) Các khuyết ñiểm của truyền kết quả

(cid:1) NNLT hỗ trợ : Fortran

21

Truyền tham trị & kết quả (tt)

{ c : array [1..10] of integer;

m,n: integer; procedure r(k,j: integer);

begin

k:=k+1; j:= j+2; end; begin /* set c[m] = m* m := 2; r(m,c[m]); write(c[1],c[2],..,c[10]); /* Gía trị của c[2] hay c[3] bị thay ñổi */

}

22

Truyền quy chiếu - Pass by Reference

(cid:1) Cách cài ñặt thứ 2 của Inout Mode (cid:1) Truyền bằng 1 ñường dẫn, có thể ñịa chỉ ô nhớ (cid:1) Tham số hình thức là pointer (cid:1) Hiệu quả hơn (không cần không gian lưu trữ) (cid:1) Khuyết ñiểm

(cid:2) Truy xuất chậm hơn (so sánh với truyền tham trị) (cid:2) Có thể gặp vấn ñề biệt danh (alias) không mong ñợi bởi vì các truy xuất là không cục bộ. VD trong C void fun(int &first, int &second) lúc gọi fun(total,total)

23

Cài ñặt các cách truyền tham số

(cid:1) Hầu hết các NNLT ñiều dùng stack ñể xây dựng

cơ chế truyền tham số

(cid:1) Truyền tham trị sẽ copy giá trị của tham số thực

vào trong stack tương ứng giá trị của tham số hình thức

(cid:1) Truyền tham trị-kết quả thì giá trị của tham số hình thức ñược lưu trong stack và sẽ trả về cho tham số thực

(cid:1) Truyền quy chiếu là ñơn giản nhất, chỉ cần lưu ñịa

chỉ ô nhớ vào trong stack

24

Cài ñặt các cách truyền tham số

Hàm Main gọi sub(w, x, y, z) : w truyền tham trị, x truyền kết quả, y truyền tham trị-kết quả, z truyền quy chiếu

25

Cách truyền tham số trong các NNLT

(cid:1) Fortran

(cid:2) Luôn dùng mô hình Inout (cid:2) Trước Fortran 77: truyền quy chiếu (cid:2) Từ fortran 77 trở về sau: truyền kết quả

(cid:1) C

(cid:2) Truyền tham trị (cid:2) Truyền quy chiếu với tham số hình thức khai báo kiểu con trỏ

(cid:1) C++

(cid:2) Truyền tham trị (cid:2) Truyền quy chiếu với tham số hình thức khai báo kiểu con trỏ (cid:2) Tham số ñối tượng truyền quy chiếu

(cid:1) Java

(cid:2) Tất cả tham số ñều truyền tham trị (cid:2) Tham số ñối tượng truyền quy chiếu

26

Cách truyền tham số trong các NNLT

(cid:1) Ada

(cid:2) Dùng 3 từ khóa ñể xác ñịnh cách truyền tham số : in,

out, in out; mặc ñịnh là in

(cid:2) Có thể gán trị cho tham số hình thức ñược khai báo với

out nhưng trị ñó không ñược tham khảo, còn những tham số ñược khai báo với in thì không trả về trị; tham số với in out thì truyền tham trị và trả về kết quả

(cid:1) C#

(cid:2) Mặc ñịnh là truyền tham trị (cid:2) Truyền tham số ñược xác ñịnh trong cả tham số hình thức

và tham số thực bởi từ khóa ref

(cid:1) PHP: Giống như C# (cid:1) Perl: tất các các tham số thực ñiều ñược ñặt sau @_

27

Kiểm tra kiểu các tham số

(cid:1) Kiểm tra kiểu của các tham số là rất cần thiết (for

reliability)

(cid:1) FORTRAN 77 và original C: không kiểm tra (cid:1) Pascal, FORTRAN 90, Java, và Ada: luôn luôn

kiểm tra kiểu

(cid:1) ANSI C và C++: Tùy thuộc vào người dùng

(cid:2) Prototypes : khai báo hàm Double sin(x) Double sin (double x){….} double x; {…}

(cid:1) Perl, JavaScript, và PHP thì không kiểm tra kiểu

28

Tham số là mãng nhiều chiều

(cid:1) Nếu tham số của CTC là mãng nhiều và CTC và CT gọi CTC ñược dịch ñộc lập thì chương trình dịch cần khai báo kích thước của mãng ñể xây dựng các chỉ số index

29

Tham số mãng nhiều chiều: C và C++

(cid:1) Yêu câu người dùng phải chỉ rõ số cột trong tham

số hình thức ñối với mãng 2 chiều (cid:2) void fun(int matrix[][10]);

(cid:1) CTC không ñược linh hoạt (cid:1) Giải pháp: dùng biến con trỏ trỏ ñến mãng và kích thước của các chiều thì truyền bằng cách tham số khác ~ người dùng phải chỉ ra kích thước lưu trữ của mãng thông qua các tham số (cid:2) VD void(float *mat_ptr, int num_rows,

int num_cols);

30

Tham số là mãng nhiều chiều : Java và C# (cid:1) Mãng là 1 ñối tượng, do ñó tất cả các mãng ñều 1

chiều nhưng từng phần tử có thể là mãng (cid:1) Mỗi mãng thừa kế 1 hằng số (length trong

Java, Length trong C#) ñược xem là chiều dài của mãng ngay lúc khởi tạo

31

Chọn cách truyền tham số

(cid:1) Hai cân nhắc quan trọng

(cid:2) Tính hiệu quả (cid:2) Truyền một chiều hay truyền 2 chiều

(cid:1) Nghịch lý

(cid:2) Người ta khuyên là nên hạn chế truy xuất các biến, tức

là nên dùng truyền 1 chiều nhiều nhất có thể

(cid:2) Nhưng truyền tham quy chiếu là cách hiệu quả nhất

32

Tham số là tên của CTC

(cid:1) Mội vài NNLT cho phép dùng tên của CTC như

là một tham số (cid:1) VD hàm integral

procedure integrate(function (fun(x : real) : real; lbound, rbound : real);

(cid:1) C và C++: không hỗ trợ cơ chế dùng tên hàm

như tham số

33

Tham số là tên của CTC - javaScript

function sub1(){

var x; function sub2(){

alert(x)

}; function sub3(){ var x; x = 3; sub4(sub2);

} function sub4(subx){

var x; x= 4; subx();

}; x=1; sub3();

Giá trị của x là bao nhiêu 4 hay 1 trong ngôn ngữ phạm vi ñộng và liên kết cạn và liên kết sâu

};

34

Chương trình con ña năng

(cid:1) Hầu hết các NNLT ñiều có các phép toán ña năng (cid:1) Chương trình con ña năng là CTC có cùng tên với

hàm có sẵn trong cùng một phạm vi (cid:2) Tất cả các phiên bản ñều có chung 1 protocol

(cid:1) Trình biên dịch chọn phiên bản thích hợp dựa trên các

tham số của hàm

(cid:1) Ada, Java, C++, và C# cho phép người dùng viết

nhiều phiên bản của CTC chùng tên nhau

(cid:1) C++, Java, C#, và Ada cho phép thêm vào các CTC

ña năng (VD toán tử)

35

Chương trình con ña năng (tt)

(cid:1) VD ba hàm trả về trị tuyệt ñối của một tham số

int MyAbs(int X) { return abs(X);

} long MyAbs(long X){ return labs(X);

} double MyAbs(double X){

return fabs(X);

} (cid:2) int a; long b; MyAbs(a); MyAbs(b) : trình biên

dịch dựa vào kiểu của tham số ñể xác ñịnh phiên bản thích hợp

36

Chương trình con chung

(cid:1) CTC chung (generic) hay ña hình (polymorphic) là một tên CTC có thể chấp nhận các tham số có nhiều kiểu khác nhau

(cid:1) CTC ña năng là trường hợp ñặc biệt của CTC chung (cid:1) Các tham số chung dùng ñể mô tả các kiểu khác nhau gọi là tham số ña hình (parametric polymorphism)

37

VD tính ña hình của CTC: C++ (cid:1) ðịnh nghĩa 1 template

template Type max(Type first, Type second) {

return first > second ? first : second;

}

(cid:1) Template trên có thể ñại diện cho phép toán so sánh

lớn hơn “>” với tất các kiểu của khác nhau (cid:2) int a,b,c; char c,d,f; (cid:2) C = max(a,b); f=max(d,e);

(cid:1) VD so sánh cho kiểu integer thông thường int max (int first, int second) {

return first > second? first : second;

}

38

VD tính ña hình của CTC: C++ (tt)

template void generic_sort (Type list[], int len){

int top, bottom; Type temp; for(top=0;top

for(bottom=top+1;bottom

if(list[top]>list[bottom]){

temp = list[top]; list[top] = list[bottom]; list[top] = temp:

}/*end of if*/ }/*end of generic_sort*/

39

Khi thiết kế hàm : các yếu tố

(cid:1) Có cho phép hiệu ứng lề không?

(cid:2) Các tham số nên ở in-mode ñể giảm hiệu ứng lề (như

Ada)

(cid:1) Cho phép giá trị trả về có kiểu gì?

(cid:2) Hầu hết các NNLT ñiều giới hạn kiểu trả về (cid:2) C cho phép trả về với bất cứ kiểu gì trừ kiểu mãng (cid:2) C++ cũng giống như C nhưng bao gồm luôn cả kiểu do

người dùng ñịnh nghĩa (cid:2) Ada cho phép tất cả các kiểu (cid:2) Java và C# không có hàm nhưng các methods có thể trả

về bất kỳ kiểu gì?

40

Phép toán ña nghĩa: do người dùng cài ñặt (cid:1) Ada và C++ cho phép người dùng cài ñặt các phép toán

ña nghĩa

(cid:1) VD trong Ada

Function “*”(A,B: in Vec_Type): return Integer is

Sum: Integer := 0; begin for Index in A’range loop

Sum := Sum + A(Index) * B(Index)

end loop return sum;

end “*”; … c = a * b; -- a, b, and c are of type Vec_Type

41

Sự ñang xen (Coroutines)

(cid:1) Xự ñang xen là một CTC có nhiều ñiểm vào (multiple entries ) và ñiều khiển lẫn nhau

(cid:1) Chương trình gọi (caller) và bị gọi (called) gọi ñang

xem lẫn nhau

(cid:1) Còn ñược gọi là ñiều khiển ñối xứng (symmetric

control)

(cid:1) Sự gọi ñang xen ñược ñặt tên là resume (cid:1) Sự ñang xen có thể lập ñi lập lại và có thể không

dừng

42

Minh họa sự ñang xen: trường hợp 1

43

Minh họa sự ñang xen: trường hợp 2

44