ĐẠ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
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
HÀ NỘI – 2010
II
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
Lời cảm ơn
Trước tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc đến thạc sỹ Phạm Thị
Kim Dung, người đã tận tình chỉ bảo hướng dẫn tôi trong suốt quá trình thực hiện khoá
luận tốt nghiệp.
Tôi xin bày tỏ lời cảm ơn sâu sắc đến các thầy cô giáo đã giảng dạy tôi trong suốt
bốn năm học qua, đã cho tôi nhiều kiến thức quý báu để tôi vững bước trên con đường
học tập của mình.
Tôi xin gửi lời cảm ơn tới các bạn trong lớp K51CB, và K51CNPM đã ủng hộ
khuyến khích tôi trong suốt quá trình học tập tại trường.
Và cuối cùng, tôi xin bày tỏ niềm biết ơn vô hạn tới bố mẹ, và những người bạn
thân luôn bên cạnh, động viên tôi trong suốt quá trình thực hiện khoá luận tốt nghiệp.
Hà Nội, ngày 22 tháng 05 năm 2010
Sinh Viên
Đỗ Duy Hưng
I
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
TÓM TẮT NỘI DUNG
Hiện nay, thiết kế dựa trên thành phần (Component-based design) đang được ứng
2.2.1 Các phương pháp hình thức............................................................................................4
2.2.2 Đặc tả..............................................................................................................................5
2.2.3 Đặc tả hình thức..............................................................................................................5
2.3 Giao diện.............................................................................................................6
2.3.1 Đặc tả giao diện..............................................................................................................6
2.3.2 Thành phần và giao diện.................................................................................................6
2.3.3 Các loại interface............................................................................................................6
2.3.4 Statelful và stateless interface........................................................................................7
2.3.5 Relational interface.........................................................................................................8
CHƯƠNG 3: NỘI DUNG LÝ THUYẾT VỀ RELATIONAL INTERFACE.........10
3.1 Sơ bộ về bài viết và các ký hiệu........................................................................10
3.2 Relational interfaces..........................................................................................11
3.3 Môi trường và khả năng lắp ghép......................................................................14
3.4 Kết hợp.............................................................................................................16
CHƯƠNG 4: XÂY DỰNG CÔNG CỤ CHUYỂN ĐỔI TỰ ĐỘNG TỪ JAVA
SANG RELATIONAL INTERFACE.........................................................................22
4.1 Cở sở lý thuyết..................................................................................................22
4.1.1 Các thành phần của lớp trong ngôn ngữ lập trình hướng đối tượng...........................22
III
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
4.1.2 Relational interface.......................................................................................................23
4.1.3 Một số kiến thức về logic.............................................................................................24
4.2 Mục tiêu của bài toán........................................................................................26
4.3 Hướng giải quyết bài toán.................................................................................27
4.3.1 Tạo relational interface tự động từ phương thức.........................................................27
4.3.2 Tính input assumption tự động.....................................................................................28
4.3.3 Tính ξ mới được tạo ra tự động....................................................................................28
4.3.4 Thực hiện việc kết hợp tự động....................................................................................29
4.4 Mô tả các thành phần của công cụ.....................................................................30
4.4.1 Lớp SourceFormat.java................................................................................................31
Interface Giao diện
Relational Interface Giao diện quan hệ
Stateless Phi trạng thái
Stateful Có trạng thái
Feedback Phản hồi
Formal methods Các phương pháp hình thức
Formal specification Đặc tả hình thức
Assumption Giả thiết
Guarantee Bảo đảm
Refinement Làm mịn
VI
Ứng dụng Relational Interface cho Java Đỗ Duy Hưng
Danh mục hình vẽ
Hình 3.1: Sơ đồ một interface cho ví dụ 4..................................................................18
Hình 3.2: Sơ đồ một interface với feedback...............................................................20
Hình 3.1: Hàm parse() trong lớp JavaFile.java.........................................................33
VII
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.
[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
này có nghĩa là ngôn ngữ đặc tả phải được dựa trên các khái niệm toán học với thuộc
tính đã được nghiên cứu và dễ hiểu [3].
2.2.1 Các phương pháp hình thức
Trong tin học, thuật ngữ phương pháp hình thức [8] (ngôn ngữ hình thức, đặc tả
hình thức,…) thường được dùng để chỉ các kỹ thuật dựa trên cơ sở toán học dùng trong
quá trình mô tả chi tiết (đặc tả), phát triển và kiểm chứng các hệ thông phần mềm cũng
Đặ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 nhỏ.
Ngay khi các giao diện được định nghĩa và chấp nhận, các hệ thống nhỏ có thể được
phát triển độc lập.
Giao diện của hệ thống nhỏ thường được định nghĩa như là một tập các đối tượng
hoặc kiểu dữ liệu trừu tượng. Chúng mô tả dữ liệu và những hoạt động mà có thể được
truy cập thông qua giao diện của các hệ thống nhỏ. Do đó, một đặc tả giao diện của hệ
thống nhỏ có thể được tạo nên bằng cách kết hợp đặc tả của các thành phần được tạo
nên bởi các giao diện hệ thống nhỏ [3].
2.3.2 Thành phần và giao diện
Một cách chung mô tả cấu trúc của hệ thống là sơ đồ khối. Một sơ đồ khối bao
gồm các thực thể gọi là các khối được kết nối với nhau bởi một liên kết. Cách mô tả này
phân loại một cấu hình (mạng) cho truyền thông giữa các khối. Một khối có thể trình
bày một thành phần vật lý hoặc logic, ví dụ như một phần của phần cứng hoặc phần
mềm. Nhưng phổ biến hơn là nó trình bày một mô tả trừu tượng của thành phần hoặc
một mô tả của interface thành phần. Mô tả thành phần trả lời cho câu hỏi: Nó làm gì ?
Và một mô tả interface trả lời cho câu hỏi: nó được sử dụng như thế nào? Mô tả thành
phần có thể rất gần với thành phần cơ bản, hoặc nó có thể chỉ định một vài thuộc tính
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 với một
trong các input x của nó chỉ trong trường hợp I là Moore đối với x, có nghĩa ràng buộc
của I không phụ thuộc vào x.
2.3.4 Statelful và stateless interface
[7] nói đến hai dạng của interface là stateless interface ( giao diện phi trạng thái )
và stateful interface ( giao diện có trạng thái ). Stateful interface, một ràng buộc có thể
khác nhau tại mỗi trạng thái khác nhau. Stateless interface có thể được xem như một
trường hợp đặc biệt của stateful interface khi ràng buộc là giống nhau ở tất cả các trạng
thái.
Trong trường hợp stateful, ta phân biệt giữa well-formed interface và well-
formable interface (hai khái niệm này trùng khớp trong trường hợp stateless interface).
Với well-formed interface, các ràng buộc luôn luôn được thỏa mãn tại mọi trạng thái có
thể đạt được (reachable state). Well-formable interface không nhất thiết phải là well-
formed, nhưng mà có thể được chuyển thành well-formed bằng cách hạn chế một cách
hợp lý các input.
2.3.5 Relational interface
Trong khóa luận này, tôi muốn đề cập đến relational interface [7]. Relational
interface là một interface chỉ ra những relation ( quan hệ ) giữa những input và output.
Xem xét ví dụ về một thành phần đồng bộ sẽ lấy input là một số n ≥ 0 và trả về output
là n + 1. Interface cho mỗi thành phần có thể được mô tả như là một quan hệ nhị phân
giữa input và output: các relation chứa tất cả các cặp (n, n+1) với n ≥ 0. Mỗi một
relation có thể được hiểu như một ràng buộc giữa thành phần và môi trường (
environment ) của nó: ràng buộc chỉ ra rằng với mỗi input hợp lệ, thoải mãn điều kiện
Chúng ta sử dụng kí hiệu ≔ để định nghĩa cho một khái niệm hoặc một kí hiệu
mới, ví dụ: x
0
≔ max {1, 2, 3} chỉ ra rằng x
0
là giá trị lớn nhất của tập {1, 2, 3}
Gọi V là tập hữu hạn các biến. Một thuộc tính trên V là một công thức FOL ϕ như
vậy thì với mọi biến tự do của ϕ đều thuộc V. Một tập tất cả các thuộc tính trên V được
kí hiệu là
ℱ
(V). Coi ϕ là một thuộc tính trên V và V’ là tập con hữu hạn của V, V’ = {v
1
,
v
2
, …, v
n
}. Khi đó, ∃V’ : ϕ là một cách viết ngắn gọn của ∃v
1
: ∃v
2
: … : ∃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
2
…a
n
, thì phần tử thứ i của chuỗi, a
i
, được kí hiệu là s
i
,
với i = 1, … , n.
3.2 Relational interfaces
Định nghĩa 1 (Relational interface): một relational interface (hay một interface
đơn giản) là 1 bộ I = ( X, Y, ξ ). Trong đó X, Y là 2 tập hữu hạn và tách rời của các biến
input và output tương ứng, và ξ là hàm tổng
ξ: ξ(X ∪ Y)* → ℱ(X ∪ Y)
Gọi G(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 p(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.
Đị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
1
) ≡ x > 0.
Một interface phi trạng thái có thể khác của thành phần này là:
I
2
≔ ({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 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 ∧
Đị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’)
3.3 Môi trường và khả năng lắp ghép
Định nghĩa 7 (Môi trường): Một interface là một bộ E = (X, Y, hX, hY), trong X và
Y được định nghĩa trong Định nghĩa 1, và h
X
và h
Y
là các hàm tổng.
h
X
: (X ∪ Y)* → ℱ(X), h
Y
: (X ∪ Y)* → ℱ(Y)
h
X
biểu diễn những đảm bảo trên những input X, cái mà môi trường cung cấp tại
(s) là có thể thỏa mãn.
Định nghĩa 8 (Khả năng lắp ghép): Interface I = (X’, Y’, ξ) có thể ghép vào với
môi trường E = (X, Y, h
X
, h
Y
), được kí hiệu I ⊨ E, nếu X’ = X, Y’ = Y, và với tất cả s ∈
ℛ(I
E
), thì công thức sau là hợp lệ:
h
X
(s) → (in(ξ(s)) ∧ (ξ(s) → h
Y
(s))) (1)
trong đó I
E
là một interface được định nghĩa như sau:
I
E
≔ (X, Y, ξ
E
) (2)
ξ
E
(s) ≔ ξ(s) ∧ h
X
(s), với tất cả s ∈ (X ∪ Y)* (3)
Khả năng lắp ghép có thể được nhìn nhận một cách trực quan như là một trò chơi
giữa interface và môi trường. Giả sử s là trạng thái hiện tại của I và E (ban đầu, s = ε).
2
từ ví dụ 1 và môi trường phi trạng
thái E
1
≔ ({x}, {y}, x > 0, y > 0). Có thể thấy rằng cả I
1
và I
2
có thể lắp ghép với E
2
≔
({x}, {y}, x ≥ 0, y > 0): ràng buộc x ≥ 0 không đủ mạnh để đạt giả thiết input x > 0. Cần
chú ý rằng I
2
không áp đặt giả thiết input một cách rõ ràng, tuy nhiên, nó lại ngầm sử
dụng giả thiết này, vì nó không tạo nên bảo đảm nào khi giả thiết x > 0 bị vi phạm. Cuối
cùng, xem xét E
3
≔ ({x}, {y}, true, true). I
2
có thể ghép với E
3
: E
3
không cung cấp bảo
đảm trên input nhưng cũng không kì vọng bảo đảm trên output. I
1
không thể ghép với E
3
vì true x > 0.
Định lý 2: Nếu một interface I là well-formable thì tồn tại một môi trường thực
(live environment) E để I ⊨ E.
Copyright: Tài liệu đại học ©