Bài giảng nguyên lý ngôn ngữ lập trình: Thực hiện chương trình con (Chương 5)

Chương 5: Thực hiện chương trình con

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

ðịnh nghĩa

(cid:1) Trong NNLT, tác vụ gọi “call” và trả về (return) của chương trình con ñược gọi chung là liên kết chương trình con “subprogram linkage”

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

(cid:1) Giới thiệu chung về ngữ nghĩa của Call và Return (cid:1) Thực hiện chương trình con ñơn giản (cid:1) Thực hiện chương trình con với biến cục bộ ñộng

Stack

(cid:1) Chương trình con lòng nhau (nested

Subprograms) (cid:1) Khối (Blocks) (cid:1) Cài ñặt phạm vi ñộng

Ngữ nghĩa của việc gọi (call) và trả về (return) (cid:1) Một số tác vụ cần thiết cho việc gọi chương trình

con (cid:2) Cơ chế truyền các tham số (truyền tham trị, truyền quy

chiếu, truyền kết quả, ...)

(cid:2) Các biến cục bộ là static hay not static (cid:2) Lưu lại trạng thái hiện hành (execution status) của

chương trình gọi CTC

(cid:2) Chuyển quyền ñiều khiển cho CTC (cid:2) Cung cấp các truy xuất ñến các biến không cục bộ

Thực hiện CTC ñơn giản: Call

(cid:1) Chương trình con ñơn giản “simple”

(cid:2) Không lòng nhau và các biến là tĩnh (static)

(cid:1) Các tác vụ có cần thiết

(cid:2) Lưu hiện trạng thực thị của chương trình gọi “caller” (cid:2) Thực hiện tiến trình truyền tham số (cid:2) Chuyển ñịa chỉ trả về cho chương trình con “callee” (cid:2) Chuyển quyền ñiều khiển cho chương trình con

“callee”

Thực hiện CTC ñơn giản: Return

(cid:1) Nếu sử dụng truyền trị-kết quả, thì di chuyển giá trị hiện hành của các tham số hình thức ñến từng tham số thực tương ứng

(cid:1) Nếu là hàm, di chuyển giá trị của hàm ñến vị trí

mà caller có thể lấy ñược

(cid:1) Phục hồi lại trạng thái thực thi của caller (cid:1) Trả quyền ñiều khiển lại cho caller

Thực hiện CTC ñơn giản: Parts

(cid:1) Có 2 phần phân biệt: phần code thực và phần noncode (biến cục bộ và dữ liệu có thể bị thay ñổi)

(cid:1) ðịnh dạng, hoặc layout, của phần noncode của một chương trình thực thi con ñược gọi là bản hoạt ñộng (activation)

(cid:1) Một thể hiện (instance) bản hoạt ñộng là mẫu cụ thể của bản hoạt ñộng (bao gồm dữ liệu hoạt ñộng của chương trình con)

Bản hoạt ñộng của chương trình con ñơn giản

Code và bản hoạt ñộng của chương trình với chương trình con ñơn giản

Cài ñặt CTC với biến cục bộ ñộng Stack

(cid:1) Bản hoạt ñộng phức tạp

(cid:2) Trình biên dịch phải sinh code ñể cấp phát và giải

phóng một cách tường minh cho các tham số cục bộ (cid:2) Phải hỗ trợ ñệ qui “recursion” (tạo ñồng thời nhiều thể

hiện bản hoạt ñộng của một chương trình con)

(cid:2) ðệ qui yêu cầu nhiều thể hiện của bản hoạt ñộng, mỗi thể hiện của bản hoạt ñộng tương ứng với 1 một lần gọi ñệ qui

(cid:2) Mỗi thể hiện cầu 1 bản copy các tham số hình thức,

các biến cục bộ cấp phát ñộng và ñịa chỉ trả về

Bản hoạt ñộng của NN với biến cục bộ ñộng Stack

Cài ñặt CTC với biến cục bộ ñộng Stack : Bản hoạt ñộng

(cid:1) ðịnh dạng của bản hoạt ñộng là tĩnh, nhưng kích

thước của nó có thể ñộng

(cid:1) Liên kết ñộng (dynamic link) trỏ ñến ñỉnh của bản

hoạt ñộng của caller

(cid:1) Bản hoạt ñộng ñược xác ñịnh ra một cách ñộng

khi gọi chương trình con

(cid:1) Run-time stack

Ví dụ: Hàm C

void sub(float total, int part) {

int list[5]; float sum; …

}

Ví dụ không ñệ qui

void fun1(int x) {

(cid:3) 2

int y; ... fun3(y);

} void fun2(float r) {

(cid:3) 1

int s, t; ... fun1(s);

Hàm main gọi fun2 Hàm fun2 gọi fun1

} void fun3(int q) { (cid:3) 3

...

Hàm fun1 gọi fun3

} void main() { float p; ... fun2(p);

}

Ví dụ không ñệ qui

Dynamic Chain và Local Offset

(cid:1) Tập hợp các dynamic links trong stack tại một thời ñiểm nào ñó ñược gọi là dynamic chain, hoặc call chain

(cid:1) Các biến cục bộ có thể ñược truy xuất thông qua các offset của nó trong bản hoạt ñộng. Offset này ñược gọi là local_offset

(cid:1) Local_offset của một biến cục bộ có thể ñược xác ñịnh bởi trình biên dịch ngay thời ñiểm dịch hoặc thời ñiểm thực thi

Ví dụ với ñệ qui

int factorial (int n) {

<-----------------------------1

if (n <= 1) return 1; else return (n * factorial(n - 1)); <-----------------------------2

} void main() { int value; value = factorial(3);

<-----------------------------3

}

Bản hoạt ñộng của factorial

Chương trình con lòng nhau

(cid:1) Vài NNLT với phạm vi tĩnh (e.g., Fortran 95,

Ada, JavaScript) dùng các biến cục bộ ñộng stack và cho phép các chương trình con lòng vào nhau (cid:1) Các biến bên trong các bản hoạt ñộng trong stack có thể ñược truy xuất một cách không cục bộ (cid:1) Hai bước ñể tham chiếu các biến không cục bộ:

(cid:2)

Tìm kiếm thể hiện bản hoạt ñộng tương ứng

(cid:2) Xác ñịnh offset của biến trong thể hiện ñó

ðịnh vị các tham chiếu không cục bộ

(cid:1) Tìm Offset: khá dễ dàng (cid:1) Tìm thể hiện bản hoạt ñộng tương ứng

(cid:2) ðể ñảm bảo có thể tham chiếu ñến các biến không cục bộ thì các biến này phải ñược cấp phát trong các thể hiện bản hoạt ñộng trong stack

Phạm vi tĩnh

(cid:1) Static chain là tập hợp các static links liên kết một

vài bản hoạt ñộng trong stack

(cid:1) Static chain là cách cài ñặt phổ biến trong các NNLT

hỗ trợ CTC lòng nhau

(cid:1) Liên kết tĩnh (static link) trong một thể hiện bản hoạt ñộng nào ñó của 1 CTC là 1 pointer trỏ ñến phần dưới cùng của thể hiện bản hoạt ñộng cha, liên kết này dùng ñể truy xuất các biến không cục bộ

(cid:1) Chuỗi tĩnh (static chain) của một thể hiện bản hoạt ñộng nào ñó ñều phải kết nối với thể hiện bản hoạt ñộng của CTC tổ tiên (ancestors)