Một cách đặc tả thiết kế hướng đối tượng dựa trên mô hình Rcos - Nguyễn Mạnh Đứ

T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 3 MỘT CÁCH ĐẶC TẢ THIẾT KẾ HƯỚNG ĐỐI TƯỢNG DỰA TRÊN MÔ HÌNH rCOS Nguyễn Mạnh Đức (Trường ĐH Sư phạm - ĐH Thái Nguyên) Đặng Văn Đức (Viện Công nghệ Thông tin-Viện KH&CN Việt Nam) 1. Đặt vấn đề Thiết kế và phát triển hệ thống phần mềm với ngôn ngữ hướng đối tượng đã được thừa nhận là rất phức tạp [1, 4]. Nhiều nhà nghiên cứu chỉ ra sự cần thiết phát triển công cụ hình thức hoá làm nền tảng cho việc phát triển phần mềm hướng đối tượng. Bài báo này sẽ giới thiệu lý thuyết lập trình thống nhất của Hoare và He [2] dùng vào việc xây dựng một cách đúng đắn các chương trình hướng đối tượng. Lý thuyết lập trình được vận dụng để trình bày ngữ nghĩa của ngôn ngữ lập trình hướng đối tượng với các lớp, tính rõ ràng, liên kết động, các phương thức đệ quy và tính đệ quy. Để cho đơn giản, những gì liên quan đến các định nghĩa hình thức về biến, tham chiếu tới các kiểu được bỏ qua (có thể xem trong [2, 5]). Phần 2 của bài báo là trình bày tóm tắt mô hình tính toán rCOS đã được He Jifeng và cộng sự đề xuất và phát triển [3]. Phần 3 là đề xuất mới về việc áp dụng rCOS vào việc xây dựng một số đặc tả hệ thống phục vụ cho phát triển hệ thống phần mềm theo phương pháp hướng đối tượng. 2. Mô hình tính toán rCOS [3] Một chương trình lệnh được xác định bằng quan hệ nhị phân (α, P) [2, 5, 11], trong đó: α ký hiệu tập các biến đã biết trong chương trình. P là tân từ quan hệ các giá trị của các biến trong chương trình khi khởi tạo với các giá trị cuối của chúng, P còn được gọi là thiết kế (design). Với chương trình tuần tự lệnh, ta quan tâm theo dõi các giá trị của các biến vào inα và các biến ra outα. Ở đây ta đưa ra qui ước rằng với mỗi biến x ∈ inα, phiên bản x’ của nó là một biến ra trong outα, mang giá trị cuối của x sau khi thực hiện chương trình. Ta dùng biến logic ok chỉ ra một chương trình có khởi tạo đúng hay không và phiên bản ok’ của nó biểu diễn sự thực hiện có kết thúc hay không. Bảng ký tự α được định nghĩa là inα ∪ outα ∪ {ok, ok’} và thiết kế có dạng: p(x) ├ R(x, x’) def ok ∧ p(x) ⇒ ok’ ∧ R(x, x’) Trong đó: p là tân từ trên inα và R là tân từ trên outα; p là tiền điều kiện, xác định trạng thái khởi đầu của chương trình; R là hậu điều kiện, xác định trạng thái kết thúc của chương trình; x và x’ biểu diễn giá trị khởi đầu và kết thúc của biến x trong chương trình; ok và ok’ tương ứng mô tả trạng thái ban đầu và cuối của chương trình, nếu chương trình được kích hoạt hợp thức ok là true, nếu việc thực hiện chương trình cuối cùng thành công ok’ là true, ngược lại chúng là false. 2.1. Thiết kế Một thiết kế biểu diễn sự thoả thuận giữa “người sử dụng” và chương trình, nếu chương trình được khởi tạo một cách hợp thức trong trạng thái thoả mãn tiền điều kiện p thì nó sẽ kết thúc trong trạng thái thoả mãn hậu điều kiện R. Một thiết kế V thường có dạng sau: V: (p├ R) def p ⊢ (R ∧ w = w’) Ở đây w là tất cả các biến trong inα, nhưng không thuộc V. 2.2. Chương trình như các thiết kế Để xác định ngữ nghĩa của chương trình, trước hết cần xác định một số toán tử trong các thiết kế. Cho hai thiết kế P1 và P2.
Toán tử tuần tự: Nếu tập các ký tự ra của P1 giống như tập các ký tự vào của P2, thành phần tuần tự của chúng được xác định như sau: T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 4 P1(input1, output1); P2(input2, output2) def ∃m • P1(input1, m) ∧ P2(m, output2) Trong đó: input1 và output1 là các tập ký tự vào và ra của P1. input2 và output2 là các tập ký tự vào và ra của P2.
Toán tử chọn có điều kiện: (P1⊳b⊲P2) def (b ∧ P1) ∨ (¬b ∧ P2), ở đây b là biểu thức logic có thể nhận giá trị true hoặc false.
Các toán tử lựa chọn không tiền định và tiền định: P1 ⊓ P2 def P1 ∨ P2, P1 ⊔ P2 def P1 ∧ P2
Vòng lặp while b do P được xác định như là điểm bất định nhỏ nhất: X = ((P; X)⊳b⊲ skip) của phương trình đệ qui X = F(X). 2.3. Biểu thức Một biểu thức có thể có một trong các dạng sau đây: e ::= x | null | new N | e is N | (N)e | e.a | f(e) | self Trong đó: x là một biến đơn, null biểu diễn đối tượng đặc biệt của lớp đặc biệt NULL là lớp con của mọi lớp và null là duy nhất; new N là tạo đối tượng mới của N; e is N là biểu thức kiểm thử (test); (N)e là biểu thức ép kiểu; e.a là biểu thức thuộc tính, f(e) là phép toán gắn liền với các kiểu nguyên thuỷ; self được sử dụng để chỉ đối tượng hoạt động trong phạm vi hiện tại. 2.4. Các lệnh Phần này xem xét các lệnh và ngôn ngữ sẽ hỗ trợ các cấu trúc lập trình hướng đối tượng tiêu biểu. Một lệnh chung nhất có dạng: c ::= | skip | chaos bỏ qua | không xác định | var T x = e | end x khai báo | kết thúc khai báo | c; c | c
bc trình tự | chọn theo điều kiện | c ⊓ c | b*c không tiền định | lặp | read(x: T) đọc giá trị kiểu T | le.m(e, v, u) gọi phương thức | le:=e | C.new(x) gán | tạo đối tượng mới. Ở đây b là biểu thức logic, c là lệnh, e là một biểu thức, le có thể xuất hiện ở vế trái của phép gán và có dạng le:= x | le.a với x là biến đơn còn a là thuộc tính của đối tượng. Chú ý rằng ở đây ký hiệu C (viết hoa) chỉ tên một lớp, còn c (viết thường) chỉ các lệnh. 2.5. Khai báo lớp Một chương trình hướng đối tượng có thể được chỉ ra bởi dạng cdecls•P. Nó bắt đầu bằng phần khai báo một số lớp, tiếp sau là khối lệnh P biểu diễn phương thức main của chương trình có dạng (glb, c). Phần khai báo lớp cdecls là một số hữu hạn các khai báo cdecl1; cdecl2; ...; cdeclk, mỗi cdecli có dạng như sau: [private] class N [extends M] { pri: ; pro:; pub: <c: W, w>; meth: m1(x11: T11, y12: T12, z13: T13) {c1}; ... ; mℓ(xℓ1 : Tℓ1, yℓ2: Tℓ2, zℓ3: Tℓ3) {cℓ} } Ở đây:
N và M là tên các lớp và M được gọi là lớp cha của N.
Phần pri khai báo các thuộc tính private a với các kiểu U và các giá trị khởi đầu u. Tương tự cho các phần pro và pub của lớp N. T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 5
Phần meth khai báo các phương thức, các tham biến giá trị xi: Ti1, các tham biến kết quả yi: Ti2, các tham biến giá trị-kết quả zi: Ti3 và các phần thân ci. Ta cũng sử dụng ký hiệu m(paras) { c } để chỉ sự khai báo các phương thức. 2.6. Tinh chế hệ thống đối tượng [3, 11] Định nghĩa 1 (tinh chế thiết kế): Thiết kế D2 = (α, P2) là tinh chế của thiết kế D1=(α, P1) được chỉ ra bởi D1 ⊑ D2, nếu P2 dẫn tới P1, nghĩa là: ∀x, x’, ..., z, z’, ok, ok’ • (P2 ⇒ P1). Ở đây x, ..., z là các biến chứa trong α.. D1≡ D2 nếu và chỉ nếu D1⊑ D2 và D2 ⊑ D1. Định nghĩa 2 (tinh chế dữ liệu): Cho ρ là ánh xạ (cũng có thể được coi như là thiết kế) từ α2 tới α1. Thiết kế D2 = (α2, P2) là tinh chế của thiết kế D1 = (α1, P1) dưới ρ, được chỉ ra bởi D1⊑ρ D2, nếu (ρ; P1)⊑ (P2; ρ). Trong trường hợp này ρ được gọi là ánh xạ tinh chế. Định nghĩa 3 (tinh chế hệ thống): Cho S1 và S2 là các đối tượng chương trình có cùng một tập các biến chung glb. S1 là tinh chế của S2, được chỉ ra bởi S2 ⊑sys S1, nếu hành vi của nó có thể kiểm soát và dự đoán nhiều hơn trong S2, tức là: ∀ x, x’, ok, ok’ • (S1⇒ S2). Định nghĩa 4 (tinh chế lớp): Cho cdecls1 và cdecls2 là hai phần khai báo. cdecls1 tinh chế cdecls2, được chỉ ra bởi cdecls1 ⊒class cdecls2 nếu như phần trước có thể thay thế phần sau trong bất kỳ hệ thống đối tượng: cdecls1⊒class cdecls2 def ∀P • (cdecls1• P ⊒sys cdecls2• P). Ở đây P đóng vai trò là phương thức chính (glb, c). 2.7. Các luật làm mịn và chế tác lại Nói chung, một luật làm mịn và chế tác lại có dạng như sau: cdecls • P ⊑ cdecls1 • P1 trong đó, chương trình vế trái của ⊑ có một thành phần được làm mịn và vế bên phải có một chương trình kết quả của việc làm mịn. Khi viết các luật làm mịn, chúng ta sử dụng ký pháp sau để chỉ sự khai báo lớp N: N [M, pri, pro, pub, op] Trong đó, M là tên lớp cha của N; pri, pro và pub là các tập thuộc tính private, protected và public của N; op là tập các phương thức của N. Ta có thể chỉ đưa ra các tham số liên quan cần thiết chẳng hạn như, nếu sử dụng N[op] để chỉ lớp N với tập các phương thức op, N[pro, op] chỉ lớp N với các thuộc tính protected là pro và các phương thức là op... Chi tiết về vấn đề làm mịn hệ thống đối tượng, các luật làm mịn và chế tác lại có thể xem trong trong [3, 5, 6, 7, 8, 9]. Dựa trên mô hình rCOS đã trình bày ở trên, trong phần 3 chúng tôi sẽ xây dựng một số đặc tả cho việc thiết kế các hệ thống hướng đối tượng. 3. Xây dựng một số đặc tả cho thiết kế hướng đối tượng 3.1. Đặc tả hệ thống Một hệ thống đối tượng S = (α, P), trong đó P có dạng p(x) ⊢ R(x, x’) và α gồm 3 thành phần như sau: 1) Phần thứ nhất: Cung cấp các thông tin ngữ cảnh lớp và các quan hệ của chúng:
cname: Tập các tên lớp đã được khai báo.
superclass: Là ánh xạ từ một tên lớp tới tên lớp cha của nó. T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 6 2) Phần thứ hai: Mô tả chi tiết cấu trúc của mỗi lớp: với mỗi tên lớp N ∈ cname, nó bao gồm:
attribute(N): Là ánh xạ từ một lớp N tới tập các thuộc tính được khai báo của nó, tập thuộc tính có dạng . Trong đó a là tên thuộc tính, T là kiểu và d là giá trị khởi đầu.
Attribute là hàm mở rộng của attribue(N), với mỗi lớp N bao gồm các thuộc tính protected và public mà N được kế thừa từ các lớp ông cha của nó.
meth(N): Là ánh xạ từ một lớp N tới tập các phương thức được khai báo hoặc kế thừa của N, tập phương thức có dạng: m → (, D), hoặc: m → (paras, D) Trong đó: m là tên phương thức và có x, y và z tương ứng là tham biến giá trị, tham biến kết quả và tham biến giá trị-kết quả của nó; Tx, Ty và Tz là các kiểu dữ liệu. Thiết kế D biểu diễn hành vi của phương thức m. 3) Phần thứ ba: Nhận biết các biến mà chương trình sử dụng:
alphabet: Tập các biến chung cùng với kiểu của chúng đã biết trong chương trình, nó có dạng . Ở đây, x là tên biến, T là kiểu của x.
locvar: Tập các biến địa phương có dạng . Trong đó v là tên biến, T là kiểu của nó.
visibleattr: Tập các thuộc tính tường minh trong lớp hiện tại, tức là tất cả thuộc tính đã được khai báo thuộc miền private, protected và public (đã khai báo) của lớp. Nó bao gồm 3 ánh xạ: pri: N → , pro: N → <a: T, d>, pub: N → Trong đó N là tên lớp, a là tên thuộc tính, T là kiểu thuộc tính và d là trị khởi đầu. Ở đây ta chỉ quan tâm tới việc đưa ra một số thuật toán xử lý các lớp, tinh chế và làm mịn các thành phần dữ liệu, các quan hệ giữa chúng trong phần khai báo cdecls, nên thành phần P của hệ thống không thay đổi. Vấn đề cần phải giải quyết là đưa ra các cách đặc tả các lớp và các thuật toán xử lý trên các lớp của hệ thống được mô tả như vậy. Trong khuôn khổ bài báo này, chúng tôi sẽ trình bày phương pháp đặc tả mối lớp bằng một tệp văn bản (text), tương ứng với cách đặc tả lớp này là xây dựng các thuật toán làm mịn thông qua việc xử lý sự biến đổi nội dụng của tệp văn bản đó. 3.2. Đặc tả mỗi lớp bằng một tệp văn bản 3.2.1. Mô tả hệ thống bằng các tệp văn bản Trong cách mô tả hệ thống này, chúng tôi sử dụng một tệp văn bản để đặc tả các thành phần của một lớp và biểu diễn quá trình biến đổi của nó trong hệ thống, nghĩa là thành phần α của hệ thống là một là một tập các file văn bản, mỗi file văn bản đặc trưng cho một lớp bao gồm các thành phần:
name: tên lớp
supername: tên lớp cha
pri: các thuộc tính private
pro: các thuộc tính protected
pub: các thuộc tính public
meth:các phương thức Trong file văn bản đặc tả lớp như trên: Thành phần mô tả tên lớp name bắt buộc phải có (khác trống) và không thay đổi; Các thành phần khác có thể có hoặc không và sẽ thay đổi trong quá trình hoạt động của hệ thống, do các xử lý như thêm bớt các thuộc tính hay phương thức, thay đổi tính visibility của lớp T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 7 Để quản lý các lớp trong hệ thống, ta sẽ sử dụng một tệp văn bản cname.txt. Khi hệ thống bắt đầu khởi động thì tệp cname.txt mà nội dung của nó là trống lập tức được tạo ra. Hàm tạo ra tệp này có thể được viết bằng C++ như sau: // Tao file cname.txt de luu class // names class cnameFile { public: void cname() { ofstream outfile; outfile.open("cname.txt"); outfile.close(); } }; Khi một lớp được tạo ra trong hệ thống thì tên của nó sẽ được bổ sung ngay vào trong tệp này. Để quản lý sự thay đổi của các lớp trong hệ thống chúng ta cần phải xây dựng các hàm sau cho mỗi lớp:
pri(C) trả về xâu có dạng | U a = u, mô tả tập các thuộc tính private của lớp C. Nó được xác định từ thành phần pri của tệp C.txt.
pro(C) trả về xâu có dạng | U b = v, mô tả tập các thuộc tính protected của lớp C. Nó được xác định từ thành phần pro của tệp C.txt.
pub(C) trả về xâu có dạng <c: W, w>| U c = w, mô tả tập các thuộc tính public của lớp C. Nó được xác định từ thành phần pub của tệp C.txt.
attr(C) hàm trả về xâu là pri(C) ∪ pro(C) ∪ pub(C).
super(C) trả về tên lớp cha của lớp C nếu có, nếu lớp C không có cha thì trả về một xâu trống. Nó được xác định từ thành phần super của tệp C.txt.
meth(C) trả về tập các phương thức của lớp C. Nó được xác định từ thành phần meth của tệp C.txt.
alpha(cdecls) trả về tập các biến dùng chung.
locvar(C) trả về xâu biểu diễn tập các biến cục bộ của lớp C, nó được xác định từ tệp thành phần meth của tệp C.txt.
Attr là sự mở rộng của attr(C), với mỗi lớp C nó bao gồm các thuộc tính protected và public mà lớp C được kế thừa từ các lớp cha của nó.
Meth(C) trả về tập các phương thức mà lớp C được kế thừa từ lớp cha.
ATTR(cdecls) là tập { C.a | C ∈ cname ∧ a ∈ Attr(C) } Sau đây chúng tôi sẽ đưa ra một số đặc tả thuật toán làm mịn hình thức, dựa trên mô hình của hệ thống hướng đối tượng đã nêu ra, để thực hiện một số công việc tinh chế và làm mịn phần khai báo trong hệ thống, làm cơ sở cho việc phát triển mô hình thiết kế trên UML sau này. 3.2.2. Đặc tả các thuật toán làm mịn Các thuật toán làm mịn ở đây đều sử dụng luật 11 trong [3] và một hoặc một số luật khác trong [3, 5, 9]. Do đó trong các thuật toán sau, ta không nhắc lại việc sử dụng luật 11 mà chỉ đề cập tới các luật khác được sử dụng thêm. 3.2.2.1. Thuật toán thêm một tên lớp vào hệ thống Thêm một tên lớp mới C vào phần khai báo của một hệ thống, thì hệ thống sẽ được tinh chế theo luật làm mịn trong như sau: cdecls ⊑ C; cdecls. Thêm một lớp trống C (lớp chỉ có tên và chưa có một thuộc tính hay phương thức nào) vào trong một hệ thống S sẽ làm α thay đổi, cụ thể là thành phần cname của hệ thống sẽ thay T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 8 đổi, tệp cname.txt được bổ sung thêm tên lớp C, các thành phần của C ban đầu có nội dung là trống. Ta sẽ được một hệ thống mới S’ = (α’, P). Thuật toán này có thể viết như sau: Algorithm AddNewClass Format: AddNewClass(S, C) Input: Hệ thống S = (α, P), C: String, C ∉ cname . Output: Hệ thống mới S’ = (α’, P’) với C ∈ cname.txt và tệp C.txt Method 1. Nếu C là xâu trống thì sang bước 3 2. Nếu C khác trống thì xét tiếp: 2.1. Nếu C ∈ cname thì sang bước 3 2.2. Ngược lại, C ∉ cname thì: //bổ sung xâu C vào tệp cname.txt 2.2.1. Write(cname.txt, C); 2.2.2. Tạo file C.txt 2.2.3. Write(C.txt, “name:”+C); 3. Dừng End Khi thực hiện thuật toán này thì tệp cname.txt sẽ được thêm một phần tử mới là xâu C, đó chính là một tên lớp mới được bổ sung vào hệ thống, tệp C.txt sẽ được tạo ra và thành phần name có giá trị là C chính là tên lớp, còn các thành phần khác của tệp này là trống. Độ phức tạp của thuật toán AddNewClass: Độ phức tạp của thuật toán được đánh giá thông qua bước 2.1. Giả sử tệp cname.txt có i (i = 1..n) phần tử, tức là trong hệ thống có i lớp. Việc kiểm tra xem C có trong cname hay không cần nhiều nhất là n lần. Do đó độ phức tạp của thuật toán này là O(n). (Nếu sử dụng phép tìm kiếm nhanh thì độ phức tạp của thuật toán chỉ là O(log2 n), giả sử ở đây chúng tôi sử dụng tìm kiếm tuần tự). 3.2.2.2. Thuật toán thêm một tên thuộc tính riêng vào một lớp Thêm một thuộc tính vào thành phần riêng của một lớp có thể được thực hiện theo luật bổ sung thuộc tính: N[pri]; cdecls ⊑ N[pri ∪ ]; cdecls. Thêm một thuộc tính riêng vào một lớp trong một hệ thống S sẽ làm α thay đổi, cụ thể là các thành phần attribute và pri của visibleattr sẽ thay đổi. Ta sẽ được một hệ thống mới S’ = (α’, P). Thuộc tính riêng thêm vào lớp là xâu có dạng , trong đó a là tên thuộc tính, T là kiểu và d là trị khởi đầu của nó. Ở đây ta phải cập nhật lại thành phần pri trong tệp văn bản C.txt đặc tả cho lớp. Thuật toán này có thể viết như sau: Algorithm AddNameAttribute Format: AddAttr(S, C, st) Input: Hệ thống S, C ∈ cname, st: String, st ≠ “”. Output: Hệ thống mới S’ = (α’, P) trong đó st ∈ pri(C). Method 1. Nếu st là xâu trống thì sang bước 3 2. Nếu st khác trống thì xét tiếp: 2.1. Nếu st ∈ attr(C) thì sang bước 3; 2.2. Ngược lại, st ∉ attr(C) thì: <bổ sung st vào thành phần pri của tệp C.txt>; 3. Dừng End Độ phức tạp của thuật toán: Giả sử số phần tử của cname là n, số phần tử của attr(C) là m. Khi đó để xác định C có thuộc cname hay không cần nhiều nhất n lần, st có thuộc attr(C) T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 9 hay không cần nhiều nhất m lần. Do đó độ phức tạp của thuật toán là O(max(n, m)). 3.2.2.3. Thuật toán chuyển một thuộc tính private thành protected Chuyển một thuộc tính private thành thuộc tính protected trong một lớp được thực hiện theo luật làm mịn: N[pri ∪ {<x: T, d>}, pro]; cdecls ⊑ N[pri, pro ∪ {<x: T, d>}]; cdecls. Algorithm MoveAttPriToPro Format: MovePro(S, C, attrName) Input: S; C ∈ cname, attrName ∈ attribute(C). Output: S’ = (α’, P) và attrName ∈ pro(C). Method 1. Nếu C ∉ cname thì sang bước 3. 2. Nếu C ∈ cname thì: 2.1. Nếu attrName ∉ pri(C) thi sang bước 3. 2.2. Nếu attrName ∈ pri(C) thì thực hiện: Move(“C.txt”, attrName, pri, pro); 3. Dừng. End Ở đây, Move(C.txt, attrName, pri, pro) là hàm chuyển xâu con attrName từ thành phần pri sang thành phần pro trong tệp văn bản C.txt. Độ phức tạp của thuật toán: O(max(n, m), trong đó n là số phần tử của cname, m là số phần tử của pri(C). 3.2.2.4. Thuật toán chuyển một thuộc tính protected thành public Chuyển thuộc tính protected thành thuộc tính public trong một lớp của hệ thống S được thực hiện theo luật: N[pro ∪ {}, pub]; cdecls ⊑ N[pro, pub ∪ {<x: T, d>}]; cdecls. Thuật toán này có thể được viết như sau: Algorithm MoveAttProToPub Format: MovePub(S, st) Input: S; C ∈ cname, attrName ∈ pro(C). Output: S’ = (α’, P) và attrName ∈ pub(C). Method 1. Nếu C ∉ cname thì sang bước 3. 2. Nếu C ∈ cname thì: 2.1. Nếu attrName ∉ pro(C): sang bước 3. 2.2. Nếu attrName ∈ pro(C) thực hiện: Move(“C.txt”, attrName, pro, pub); 3. Dừng End Ở đây, Move(C.txt, attrName, pro, pub) là hàm chuyển xâu con attrName từ thành phần pro sang thành phần pub trong tệp văn bản C.txt. Khi thực hiện thuật toán này, thuộc tính protected attrName của lớp C sẽ trở thành thuộc tính public. Độ phức tạp của thuật toán: O(max(n, m), trong đó n là số phần tử của cname, m là số phần tử của pro(C). 3.2.2.5. Thuật toán chuyển một thuộc tính private thành public Chuyển thuộc tính private thành thuộc tính public trong một lớp của hệ thống S được thực hiện theo luật: N[pri ∪ {}, pub]; cdecls ⊑ N[pro, pub ∪ {}]; cdecls. Algorithm MoveAttPriToPub Format: MovePro(S, C, attrName) Input: S; C ∈ cname, attrName ∈ attribute(C). T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 10 Output: S’ = (α’, P) và attrName ∈ pro(C). Method 1. Nếu C ∉ cname thì sang bước 3. 2. Nếu C ∈ cname thì: 2.2.1. Nếu attrName ∉ pri(C): sang bước 3. 2.2.2. Nếu attrName ∈ pri(C) thì thực hiện: Move(“C.txt”, attrName, pri, pub); 3. Dừng End Ở đây, Move(C.txt, attrName, pri, pub) là hàm chuyển xâu con attrName từ thành phần pri sang thành phần pub trong tệp văn bản C.txt. Khi thực hiện thuật toán này, thuộc tính pivate attrName của lớp C sẽ trở thành thuộc tính public. Độ phức tạp của thuật toán: O(max(n, m), trong đó n là số phần tử của cname, m là số phần tử của pri(C). 3.2.2.6. Thuật toán chuyển thuộc tính từ một lớp tới lớp cha Chuyển một thuộc tính từ một lớp tới lớp cha của nó được thực hiện theo luật làm mịn sau [3, 11]: Nếu N có các lớp con là M1, M2,, Mk, thì: N[pro]; M1[pro1 ∪ A];; Mk[prok ∪ A] cdecls ⊑ N[pro ∪ A]; M1[pro1]; ; Mk[prok]; cdecls. Sau đây là thuật toán chuyển một thuộc tính protected từ lớp con sang miền protected của lớp cha. Algorithm MoveAttributeToSuperclass Format: MoveAtt(S, N, M, attrName) Input: Hệ thống S; N, Mi ∈ cname, super(Mi) = N, attrName ∈ attr(Mi). Output: Hệ thống mới S’ = (α’, P) | attrName ∈ N. Method 1. Kiểm tra các điều kiện Input, nếu thoả thì thực hiện các bước sau: 2. for each attrName ∈ pro(Mi) DO Delete(“Mi.txt”, Mi.pro, attrName); 3. Write(“N.txt”, N.pro, attrName); End Ở đây Delete(, st1: String, st2: String) là hàm xoá xâu con st2 khỏi xâu st1 trong . Write(, st1: String, st2: Sting) là hàm bổ sung xâu st2 vào xâu st1 trong . Độ phức tạp của thuật toán: Giả sử cname có n phần tử, số các lớp con Mi của lớp N là m, số thuộc tính pro lớn nhất trong các lớp Mi là k. Độ phức tạp của thuật toán sẽ là O(max(n, m, k)). 3.2.2.7. Thuật toán lập kế thừa cho một lớp Để làm mịn quan hệ kế thừa giữa các lớp, ta có thể thực hiện theo luật làm mịn sau: N[∅, pri, pro, pub, op]; cdecls ⊑ N[M, pri, pro, pub, op]; cdecls Trong một hệ thống S, nếu không có thuộc tính nào của N đã được xác định trong lớp M hoặc bất kỳ các lớp ông cha nào của M, chúng ta có thể đặt M là lớp cha của N. Khi một lớp N có nhu cầu sử dụng các thành phần trong một lớp M, ta có thể lập kế thừa cho chúng, tức là tạo lập lớp cha M cho lớp N. Thuật toán này có thể được viết như sau: Algorithm CreateInheritance Format: Inheritance(S, N, M) T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 11 Input: Hệ thống S; N,M ∈ cname; attr(N)∩attr(M)=∅, attr(N) ∩ Attr(super(M)) = ∅, super(N)= ∅. Output: Hệ thống mới S’ = (α’, P), super(N) = M. Method 1. Kiểm tra các điều kiện Input, nếu thoả thì thực hiện các bước sau: 2. Nếu (attr(N) ∩ attr(M) ∅) và (attr(N) ∩ Attr(super(M)) = ∅) 3. Write(“N.txt”, N.super, M); End Độ phức tạp của thuật toán CreateInheritance: Độ phức tạp của thuật toán là O(n), trong đó n là số phần tử các lớp của tập cname. Thêm một lớp mới N vào phần khai báo của một hệ thống và cho nó kế thừa một lớp M đã có, thì hệ thống sẽ được làm mịn theo luật: cdecls ⊑ N[M, pri, pro, pub, op]; cdecls. Ta có thể xây dựng thuật toán này như sau: Algorithm Inheritance Format: Inheri(N, M) Input: Hệ thống S; M ∈ cname, xâu N. Output: Hệ thống mới S’ = (α’, P), superclass(N)=M. Method 1. Kiểm tra các điều kiện Input, nếu thoả mãn thì thực hiện các bước sau: 2. AddNewClass(S, N); 3. Write(“N.txt”, N.super, M); End Độ phức tạp của thuật toán Inheritance: Giả sử cname có n phần tử, khi đó độ phức tạp của bước 1 và 2 là O(n) bước 3 là O(1). Do vậy độ phức tạp của thuật toán này là O(n). Ta có thể viết thủ tục Update tính các thành phần được kế thừa, thêm thuộc tính mới... cho lớp N như sau: Update(N) { 1. Tính Attr(N); // các thuộc tính được kế thừa 2. Tính Meth(N); // các p/thức được kế thừa 3. AddAttr(S, N, st); // thêm thuộc tính mới 4. MovePro(S, N, attrName); // thay đổi visibility // cho thuộc tính của lớp nếu cần 5. AddMethod(S, N, m); //thêm p.thức nếu cần } 3.2.2.8. Thuật toán thêm một phương thức vào một lớp Thêm một phương thức vào một lớp để làm mịn hệ thống có thể được thực hiện theo luật làm mịn sau: N[op]; cdecls ⊑ N[op ∪ m(paras) {c}]; cdecls. Thêm một phương thức vào một lớp trong hệ thống S sẽ làm thành phần meth và locvar của α thay đổi và sẽ được một hệ thống mới S’ = (α’, P). Một phương thức có tên là m, các tham số hình thức của nó là paras= và phần thân là thiết kế D chứa các lệnh c. Ta có thể biểu diễn phương thức m là một xâu như sau: op(x: Tx, y: Ty, z: Tz) { c } . Thuật toán này có thể được biểu diễn như dưới đây: T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 12 Algorithm AddNameMethod Format: AddMethod(S, C, m) Input: Hệ thống S, C ∈ cname, m: String. Output: Hệ thống mới S’ = (α’, P) và m meth.∈ Method 1. Nếu C ∉ cname thì sang bước 3 2. Nếu C ∈ cname thì: 2.1. Nếu m = ”” thì chuyển sang bước 3. 2.2. Nếu m “” thì: 2.2.1. Nếu m ∈ meth(C): sang bước 3; 2.2.2. Nếu m ∉ meth(C): Write(C.txt, meth, m); 3. Dừng. End Độ phức tạp của thuật toán AddNameMethod: Giả sử tệp cname.txt có n phần tử, tập meth(C) có k phần tử, phép tìm kiếm trong bước 1 sẽ là O(n) và phép tìm kiếm trong bước 2.2.1 là O(k). Như vậy, độ phức tạp của thuật toán này sẽ là O(max(n, k)). 3.2.2.9. Thuật toán chuyển phương thức từ một lớp sang lớp khác Ta có thể chuyển một phương thức từ một lớp tới lớp khác dựa theo luật chuyển phương thức sau: N[op];M[{N}, op1] cdecls ⊑ N[op];M[{N}, op1 ∪ m(paras) {c}]; cdecls. Khi các lớp có nhu cầu sử dụng phương thức của một lớp, hoặc khi cần phải thực hiện tính đa hình của một số phương thức trong các lớp, ta có thể chuyển phương thức từ một lớp sang lớp khác. Khi đó các thành phần meth(lớp_con), meth(lớp_cha) của α sẽ thay đổi. Ta có thể viết thuật toán này như sau: Algorithm MoveMethod Format: MoveMethod(S, N, M, m) Input: Hệ thống S; N, M ∈ cname; super(N) = M, m ∈ meth(M). Output: Hệ thống mới S’ = (α’, P), m ∈ meth(M). Method 1. Kiểm tra các điều kiện Input, nếu thoả thì thực hiện các bước sau: 2. Delete(M.txt, meth, “m(paras) { c }”); 3. Write(N.txt, meth, “m(paras) { c }”); End Độ phức tạp của thuật toán: Độ phức tạp của thuật toán này chỉ cần xác định thông qua các bước 1 và 2. Giả sử tập cname có n phần tử và tập meth(M) có k phần tử, khi đó bước 1 cần nhiều nhất n lần kiểm tra xem N, M có thuộc cname hay không, bước 2 cần nhiều nhất k lần tìm kiếm phương thức m trong meth(M) để loại bỏ. Như vậy độ phức tạp của thuật toán này là O(max(n, k)). Ta có thể kết hợp các thuật toán trên để thực hiện các yêu cầu tinh chế và làm mịn theo các yêu cầu đặt ra cho các hệ thống đối tượng. 4. Kết luận Trong bài này chúng tôi đã nghiên cứu ngữ nghĩa của các quan hệ đặc tả cho hệ thống hướng đối tượng. Các đặc tả hệ thống đối tượng trong nghiên cứu này được phát triển dựa theo mô hình rCOS. Việc xử lý kết hợp kiểu động và cơ chế kiểm tra trạng thái với ngữ nghĩa giống như hướng đặc tả truyền thống. Các cơ sở tính toán cho hệ thống hướng đối tượng ở đây cũng có thể được sử dụng để hình thức hoá liên kết các mô hình ca sử dụng (use case) và mô hình lớp trong UML. Nó cũng có thể sử dụng làm cơ sở cho việc làm mịn tính toán trong tiến trình phát triển