ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Đỗ Duy Hưng
ỨNG DỤNG RELATIONAL INTERFACE CHO JAVA
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: Ths. Phạm Thị Kim Dung HÀ NỘI – 2010
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
I
hợp các thành phần, một số được xây dựng từ đầu, một số kế thừa lại.
Giao diện (Interface) đóng một vai trò quan trọng trong thiết kế dựa trên thành
phần vì chúng cung cấp phương tiện để mô tả cho thành phần. Một interface có thể
được xem như là một bản tóm tắt, một đại diện của thành phần: giữ lại các thông tin
cần thiết của thành phần, giấu thông tin không cần thiết và làm cho mô tả thành phần
trở nên đơn giản và hiệu quả hơn.
Trong khóa luận tốt nghiệp này, bằng việc sử dụng lý thuyết về relational
interface, tôi xây dựng một công cụ tự động phân tích, trích rút các thành phần có
trong file mã nguồn Java và biến đổi nó thành các relational interface, thực hiện việc
kết hợp tự động các interface này với nhau. Để từ đó, ta có thể biết được khả năng kết
hợp của các thành phần này với nhau. Interface mới được kết hợp vẫn giữ nguyên tính
chất của các interface cũ. Qua đó, ta cũng có thể dự đoán được giá trị đầu ra của các
thành phần nếu biết được giá trị đầu vào thông qua các tính chất.
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
III
MỤC LỤC
Bảng các kí hiệu nghĩa tiếng anh V
Danh mục hình vẽ VI
CHƯƠNG 1: MỞ ĐẦU 1
1.1 Đặt vấn đề 1
1.2 Nội dung bài toán 1
1.3 Cấu trúc khóa luận 2
CHƯƠNG 2: GIỚI THIỆU CHUNG VỀ ĐẶC TẢ VÀ GIAO DIỆN 3
2.1 Công nghệ phần mềm hướng thành phần 3
2.2 Đặc tả hình thức 3
2.2.1 Các phương pháp hình thức 4
2.2.2 Đặc tả 4
4.4.2 Lớp RInterface.java 48
4.4.3 Lớp JavaFile.java 49
4.4.4 Lớp JavaClass.java 50
4.4.5 Lớp Tools.java 51
4.4.6 Lớp Expresstion.java 56
4.4.7 Lớp FOLOptimizer.java 59
CHƯƠNG 5: CÀI ĐẶT VÀ THỬ NGHIỆM 60
5.1 Xây dựng công cụ 60
5.2 Dữ liệu thử nghiệm 61
5.3 Kết quả thử nghiệm 62
5.3.1 Phân tích file mã nguồn 62
5.3.2 Chuyển những phương thức này thành relational interface 63
5.3.3 Kết hợp các interface 65
5.3.4 Dự đoán kết quả: 68
5.4 Đánh giá 69
CHƯƠNG 6: KẾT LUẬN 69
6.1 Kết luận về khóa luận 69
6.2 Hướng phát triển trong tương lai 70
Phụ lục 71
Phụ lục 1: Nội dung mã nguồn file thử nghiệm Sample.java 71
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
V
Bảng các kí hiệu nghĩa tiếng anh
Kí hiệu Diễn giải
Input Đầu vào
Output Đầu ra
Well-formed Định dạng hoàn chỉnh
Hình 5.7: Kết quả thử nghiệm 5.3.1 đối với hàm nhan 63
Hình 5.8: Kết quả thử nghiệm 5.3.1 đối với hàm chia 63
Hình 5.9: Kết quả thử nghiệm 5.3.1 đối với hàm triTuyetDoi 63
Hình 5.10: Kết quả thử nghiệm 5.3.2 với hàm cong 64
Hình 5.11: Kết quả thử nghiệm 5.3.2 đối với hàm tru 64
Hình 5.12: Kết quả thử nghiệm 5.3.2 đối với hàm nhan 64
Hình 5.13: Kết quả thử nghiệm 5.3.2 đối với hàm chia 64
Hình 5.14: Kết quả thử nghiệm 5.3.2 đối với hàm triTuyetDoi 65
Hình 5.15: Biểu đồ interface cho kết hợp chia(cong(a, b), tru(a, b)) 66
Hình 5.16: Kết quả thử nghiệm 5.3.3 đối với hàm main 68
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
1
CHƯƠNG 1: MỞ ĐẦU
1.1 Đặt vấn đề
Hiện nay, với sự phát triển mạnh mẽ của công nghệ thông tin, nhiều hệ thống lớn
được xây dựng nên nhằm mục đích giải quyết những bài toán với độ phức tạp tương
đương. Với kích thước và độ phức tạp của những hệ thống như vậy, đòi hỏi phải có
một phương pháp thiết kế hợp lý, hiệu quả và đáng tin cậy. Phương pháp thiết kế dựa
trên thành phần đáp ứng được yêu cầu này, bởi vì, thay vì phải thiết kế toàn bộ từ đầu,
hệ thống được thiết kế như là một tập các thành phần. Các thành phần này hoặc là
được xây dựng lại từ đầu, hoặc là được thừa kế từ những thành phần khác. Do vậy mỗi
thành phần phải có tính độc lập cao và chuẩn đặc tả rõ ràng. Điều này thường được thể
hiện qua interface (giao diện) của thành phần. Một interface có thể coi như một đặc tả
của một thành phần. Việc kết hợp các thành phần cũng thông qua việc kết hợp các
interface.
1.2 Nội dung bài toán
Trong phương pháp thiết kế dựa trên thành phần, interface chính là đặc tả của
CHƯƠNG 2: GIỚI THIỆU CHUNG VỀ ĐẶC TẢ VÀ GIAO DIỆN
2.1 Công nghệ phần mềm hướng thành phần
Công nghệ phần mềm hướng thành phần (component-based software engineering
[8]) là một trong những bước tiến của quá trình sản xuất phần mềm trong công nghiệp.
Nhờ vào đó, việc sản xuất phần mềm trở nên phát triển mạnh mẽ.
Ta cùng nhìn lại các ngành kĩ nghệ khác. Mỗi ngành kĩ nghệ đều có riêng cho
mình một số thành tố cơ bản. Sự khác biệt của công nghệ phần mềm so với các ngành
kĩ nghệ khác là ở chỗ sự lắp ráp các thành phần khác nhau của phần mềm còn mang
tính tùy biến. Nghĩa là đưa ra cùng hai linh kiện (hay thành phần) phần mềm với cùng
một thiết kế, hai lập trình viên có thể lắp ráp theo cách khác nhau.
Nhận thức được điều này, kỹ nghệ hướng thành phần trong sản xuất phần mềm
được bắt đầu áp dụng. Điều cơ bản mà mỗi thành phần phải có là: tính độc lập cao và
có chuẩn đặc tả rõ ràng cho từng thành. Đặc tả này phải không phụ thuộc vào cấu trúc
bên trong của thành phần. Dựa trên 2 điểm cơ bản này của một thành phần, điều đầu
tiên khi bắt đầu thiết kế thành phần là quan tâm đến đặc tả của thành phần. Điều này
thường được thể hiện qua interface (giao diện). Tiếp theo, tính độc lập của thành phần.
Do tất cả các thành phần được kết nối qua interface thay vì trực tiếp, mọi quá trình xây
dựng bên trong thành phần đều được khép kín. Sự phụ thuộc sẽ chủ yếu dựa vào
interface. Vì vậy sẽ tách được sự phụ thuộc về cách xây dựng bên trong.
Việc xây dựng thành phần có thể bằng bất cứ phương pháp nào dù là lập trình
cấu trúc hay lập trình hướng đối tượng.
2.2 Đặc tả hình thức
Phương pháp hình thức bao gồm một số các hoạt động khác nhau như: đặc tả hệ
thống hình thức, dẫn chứng và phân tích đặc tả, phát triển chuyển đổi, và kiểm chứng
chương trình. Tất cả các hoạt động này đều phụ thuộc vào đặc tả hình thức của phần
mềm. Một đặc tả hình thức phần mềm là một đặc tả được thể hiện bằng một loại ngôn
ngữ mà từ vựng, cú pháp, ngữ nghĩa của nó được định nghĩa một cách hình thức. Điều
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
5
o Ngôn ngữ tự nhiên
o Ngôn ngữ toán
o Ngôn ngữ lập trình
o Ngôn ngữ hình thức
2.2.3 Đặc tả hình thức
Đặc tả hình thức là đặc tả với các tính chất:
o Chính xác và nhất quán.
o Ngắn gọn nhưng đầy đủ.
o Có thể xử lý bởi máy tính.
Đặc tả hình thức có các ứng dụng như sau:
o Sử dụng trong giai đoạn phân tích, thiết kế, nhằm mục đích tạo ra các
phác hoạ chi tiết, cụ thể và chặt chẽ về hệ thống sẽ được xây dựng.
o Trong quá trình xây dựng hệ thống, các đặc tả này sẽ là công cụ định
hướng để đảm bảo hệ thống được xây dựng một cách phù hợp và đầy
đủ.
o Sau khi hệ thống được xây dựng thì đặc tả sẽ đóng vai trò là thước đo
để kiểm chúng, khẳng định hệ thống được tạo ra có đúng đắn và tin cậy
hay không.
2.3 Giao diện
2.3.1 Đặc tả giao diện
Các hệ thống lớn thường được chia thành các hệ thống nhỏ và các hệ thống nhỏ
này được phát triển độc lập. Các hệ thống nhỏ tận dụng các hệ thống nhỏ khác, nên
một phần quan trọng của quá trình đặc tả là định nghĩa những giao diện của hệ thống
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
6
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
7
Extended interfaces: giống với relational interface, tuy nhiên interface này
không được đánh giá cao bởi hạn chế tính chất của những bước làm mịn và thực thi
độc lập là không có[6].
Moore interfaces: được định nghĩa bởi công thức ϕ
i
và ϕ
o
. Trong đó công thức ϕ
i
chỉ rõ giá trị hợp lệ của các biến input tại các trạng thái tiếp theo khi mà trạng thái hiện
tại được cho trước, và công thức ϕ
o
chỉ rõ giá trị hợp lệ của các biến output tại các
trạng thái tiếp theo khi mà trạng thái hiện tại được cho trước. Công thức này không
cho phép miêu tả mỗi quan hệ giữa input và output tại cùng một trạng thái [2].
Hạn chế của các interface trên là không bắt được mối quan hệ giữa input và
output. Lý thuyết về relational interface giải quyết các vấn đề đó bằng việc xây dựng
một thành phần ξ trong interface. ξ là tập tất các quan hệ giữa input và output, mô tả
ràng buộc giữa input và môi trường.
Việc kết hợp tổng quát các interfaces, có thể đạt được thông qua hai toán tử có
tên là parallel conposition ( kết hợp song song ) và connection ( kết nối ) [5],[6]. Điều
này cho phép tạo ra các feedback loop (phản hồi lặp) tùy ý. Khi nghiên cứu về
relational interface, có rất nhiều vấn đề nảy sinh từ feekback loop đồng bộ. Có thể
tránh vẫn đề được nảy sinh bởi feekback loop bằng cách hạn chế các trường hợp mà
feedback loop được cho phép. Cụ thể, ta cho phép một output của một interface I được
(kết nối), feedback loop (phản hồi lặp) có trong relational interface có thể dẫn tới
những khẳ năng:
a. Thiết kế phần mềm dựa trên relational interface là sự kết hợp giữa các
interface mà trong đó, các ràng buộc phải được thỏa mãn, hoặc có thể
thỏa mãn.
b. Ta cũng có thể kiểm chứng và dự đoán được khả năng kết hợp của các
interface lại với nhau.
c. Ngoài ra, dựa trên các rằng buộc, ta cũng có thể dự đoán được kết quả
đầu ra từ dữ liệu đầu vào.
d. Khả năng tối ưu hóa thiết kế phần mềm bằng tính chất refinement và
shared-refinement.
Một khái niệm quan trọng của relational interface mà đã được nhắc đến ở trên đó
là well-formed và well-formable. Điều này giúp cho các thành phần, hay nói đúng hơn
là các relational interface được liên kết hay có thể liên kết được với nhau.
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
9
Với những định hướng này, và do giới hạn của khóa luận, tôi sẽ giải quyết vấn đề
a, b, c. Vấn đề và những chế còn lại sẽ được giải quyết trong những nghiên cứu sau
này.
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
10
CHƯƠNG 3: NỘI DUNG LÝ THUYẾT VỀ RELATIONAL
INTERFACE
Tóm tắt về relational interface đã mô tả ở phần 2.3.5, trong chương này, tôi sẽ đề
cập đến nội dung lý thuyết về relational interface. Nội dung lý thuyết này được sử
dụng từ [7].
: … : ∃v
n
: ϕ.
Tương tự như vậy, ∀V’ : ϕ là cách viết ngắn gọn của ∀v
1
: ∀v
2
: … : ∀v
n
: ϕ.
Chúng ta hoàn toàn có thể giả định rằng tất cả các biến là kiểu, có nghĩa là tất cả
các biến được kết hợp với một tập xác định nào đó. Một phép gán trên một tập các
biến V là một hàm cho tướng ứng mỗi biến trong V với một giá trị nào trong tập xác
định của biến đó. Một bộ các phép gán trên V được kí hiệu là
(V). Nếu a là một phép
gán ( assignment ) trên V
1
và b là một là một phép gán trên V
2
,và V
1
và V
2
là 2 tập tách
rời thì chúng ta sẽ sử dụng (a, b) để kí hiệu một phép gán kết hợp trên V
1
∪ V
2
. Một
Gọi (V) là tập tất cả các phép gán trên tập các biến V. Do đó, (X ∪ Y)* là tập
tất cả các chuỗi hữu hạn của các phép gán trên X ∪ Y. Chú ý rằng X hoặc Y có thể là
rỗng: nếu X là rỗng thì I là interface nguồn, nếu Y là rỗng thì I là một bộ chứa (sink).
Một phần tử của (X ∪ Y)* được gọi là một trạng thái (state). Trạng thái khởi tạo là
một chuỗi rỗng ε. Gọi ℱ(X ∪ Y) là một tập tất cả các thuộc tính (property) trên X ∪ Y.
Do đó, ξ liên kết với mỗi trạng thái s một công thức ξ(s) trên X ∪ Y. Công thức này thể
hiện như là ràng buộc (contract) giữa I và môi trường của nó tại trạng thái đó. Khi
ràng buộc thay đổi thì trạng thái của I thay đổi.
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
14
Định nghĩa 2 (Assumption , Guarantees): Cho một ràng buộc ϕ ∈ ℱ(X ∪ Y),
input assumptions của ϕ có công thức in(ϕ) ≔ ∃
Y
: ϕ. Output guarantees của ϕ có
công thức out(ϕ) ≔ ∃X : ϕ. Chú ý rằng in(ϕ) là một thuộc tính trên X và out(ϕ) là một
thuộc tính trên Y, và ϕ → in(ϕ), ϕ → out(ϕ) là công thức hợp lệ với mọi ϕ.
Giả sử tại thời điểm ban đầu của một quy trình cho trước, trạng thái của I là s.
Môi trường sẽ biểu diễn I với một phép gán a
X
trên biến input X, như vậy a
X
thỏa mãn
giả thiết input in(ξ (s)). Sau đó, I sẽ chọn một phép gán a
Y
trên biến output Y, để cả 2
phép gán đều thỏa mãn ξ(s). Những phép gán được kết hợp với nhau tạo ra 1 phép gán
trên X ∪ Y, a ≔ (a
≔ ({x}, {y}, { x > 0 → (y = x ∨ y = x + 1) }).
Ràng buộc của I
2
khác với của I
1
: nó cho phép x ≤ 0, nhưng nó không bảo đảm về
output y trong trường hợp này. I
2
được gọi là input-complete interface, trong trạng thái
này nó chấp nhận tất cả các input. Ta có, in(I
2
) ≡ true.
Nhìn chung, không gian trạng thái của một interface là vô hạn. Tuy nhiên trong
một số trường hợp chỉ cần một tập hữu hạn các trạng thái để chỉ ra ξ. Ví dụ ξ có thể
được chỉ ra bởi một máy tự động hữu hạn các trạng thái. Mọi trạng thái trong máy tự
động được gán nhãn với một ràng buộc. Mọi bước chuyển tiếp (transition) của máy tự
động được gán nhãn với một guard, hay nói cách khác, nó là một điều kiện trên các
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
16
biến input và output. Những bước chuyển tiếp hướng ra ngoài của một trạng thái phải
có các guard tách rời, và hợp của những guard phải là true. Một interface có thể được
chỉ rõ như một máy tự động hữu hạn trạng thái được gọi là một interface hữu hạn trạng
thái (finite-state interface).
Các A/G interface là trường hợp đặc biệt của relational interface. Một A/G
interface phi trạng thái là một bộ (X, Y, ϕx, ϕy), trong đó ϕx là một thuộc tính trên X
biểu diễn giả thiết input và ϕy là một thuộc tính trên Y biểu diễn những bảo đảm
output. Interface này có thể được biểu diễn đơn giản như là một relational interface (X,
Y, ϕx ∧ ϕy).
không thể thỏa mãn. Trong trường hợp cụ thể, đặt ξ(ε) ≔ ¬x, ta sẽ đạt được mục tiêu
trên.
Ví dụ 2 chỉ ra rằng một số interface mặc dù không là well-formed vẫn có thể
được chuyển thành well-formed interface bằng cách hạn chế hợp lý các dữ liệu input.
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
18
Định nghĩa 5 (Well-formable interface): một interface I = (X, Y, ξ) là well-
formable nếu tồn tại một well-formed interface I’ = (X, Y, ξ’), như vậy: với tất cả s ∈
ℛ(I’), ξ’(s) ≡ ξ(s) ∧ ϕ
s
, trong đó ϕ
s
là một vài thuộc tính trên X.
Rõ ràng, tất cả các well-formed interface là well-formable interface, nhưng điều
ngược lại thì không đúng, như trong ví dụ 2 đã chỉ ra. Tuy nhiên, với interface phi
trạng thái, 2 phép biều diễn này trùng nhau.
Định lý 1: Một interface phi trạng thái I là well-formed nếu nó là well-formable.
Định nghĩa 6 (Tương đương - Equivalence): 2 interface I = (X, Y, ξ) và I’ = (X’,
Y’, ξ’) là tương đương, kí hiệu là I ≡ I’, nếu X = X’, Y = Y’, và với tất cả s ∈ ℛ(I) ∩
ℛ(I’), công thức ξ(s) ≡ ξ’(s) là hợp lệ.
Bổ đề 1: Nếu I ≡ I’ thì ℛ(I) ≡ ℛ(I’)
Copyright: Tài liệu đại học ©