Luận văn:Mô phỏng lập trình hướng đối tượng trong lập trình hàm

Chia sẻ: Nhung Thi | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

73
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong ngành khoa học máy tính, lập trình hàm là một mô hình lập trình xem việc tính toán là sự đánh giá các hàm toán học và tránh sử dụng trạng thái và các dữ liệu biến đổi. Lập trình hàm nhấn mạnh việc ứng dụng hàm số, trái với phong cách lập trình mệnh lệnh, nhấn mạnh vào sự thay đổi trạng thái.[1] Lập trình hàm xuất phát từ phép tính lambda, một hệ thống hình thức được phát triển vào những năm 1930 để nghiên cứu định nghĩa hàm số, ứng dụng của hàm số, và đệ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn:Mô phỏng lập trình hướng đối tượng trong lập trình hàm

B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG TR N TH OANH KHUYÊN MÔ PH NG L P TRÌNH HƯ NG Đ I TƯ NG TRONG L P TRÌNH HÀM Chuyên ngành : KHOA H C MÁY TÍNH Mã s : 60.48.01 TÓM T T LU N VĂN TH C SĨ K THU T ĐÀ N NG - 2011
Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: PGS.TS. Phan Huy Khánh Ph n bi n 1 : PGS.TS. Lê Văn Sơn Ph n bi n 2 : TS. Trương Công Tu n Lu n văn ñư c b o v trư c H i ñ ng ch m Lu n văn t t nghi p th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 16 tháng 10 năm 2011 Có th tìm hi u lu n văn t i: - Trung tâm Thông tin - H c li u, Đ i h c Đà N ng - Trung tâm H c li u, Đ i h c Đà N ng.
3 CHƯƠNG 1. M Đ U 1. Lý do ch n ñ tài Ngành công nghi p ph n m m ñã chuy n sang m t k nguyên m i. Ngày nay, các ph n m m không ñư c phát tri n nh l mà thư ng là nh ng h th ng l n, t p trung, ph c t p. Đó là s k t h p c a nhi u thành ph n dư i d ng thư vi n, gói, d ch v ,…ñư c phát tri n trên nh ng n n t ng chuyên bi t, ñ m nh n nh ng ch c năng và nhi m v khác nhau. Do ñó nh ng mô hình l p trình cũ tr lên b t c p, thi u linh ñ ng, ph c t p,… S ra ñ i c a l p trình hư ng ñ i tư ng ñánh d u m t s phát tri n nh y v t trong l p trình máy tính. L p trình hư ng ñ i tư ng ra ñ i như m t bư c ti n hóa c a tư duy thi t k ph n m m. Mô hình ñó cho phép chúng ta k t h p tri th c bao quát v quá trình v i nh ng khái ni m tr u tư ng ñư c s d ng trong máy tính. Ph ng theo m t ñ i tư ng trong th gi i th c, các ñ i tư ng trong ph n m m ñư c t o xác ñ nh chính xác nh ng ñ c trưng, thành ph n, hành vi, kh năng, m i quan h d li u,…Chúng ta có th t o ra m t ho c nhi u ñ i tư ng t m t khuôn hình cài ñ t s n v i d li u m i, ñ c l p [18]. L p trình hư ng ñ i tư ng (Object-Oriented Programming, vi t t t là OOP) là m t phương pháp m i trên bư c ñư ng ti n hóa c a vi c l p trình máy tính, nh m làm cho chương trình tr nên linh ho t, tin c y và d phát tri n. Ngôn ng l p trình hư ng ñ i tư ng không ch ñơn thu n là ng pháp ngôn ng , trình biên d ch hay toàn b môi trư ng phát tri n ng d ng mà nó bao g m r t nhi u nh ng thư vi n quan tr ng tr giúp vi c thi t k , s d ng ñ i tư ng t t hơn. L p trình hư ng
4 ñ i tư ng có th ñư c h tr b i b t c ngôn ng l p trình nào. Hi n nay h u h t các ngôn ng thông d ng ñ u h tr l p trình hư ng ñ i tư ng. Trong logic toán h c và khoa h c máy tính, phép tính lambda (ti ng Anh:lambda calculus) hay còn ñư c vi t là λ-calculus, là m t h th ng hình th c dùng trong vi c ñ nh nghĩa hàm s , ng d ng hàm s và ñ quy. Phép tính lambda ñư c Alonzo Church ñ xu t vào nh ng năm 193x như là m t ph n c a m t nghiên c u v các n n t ng toán h c. H th ng nguyên th y ñã ñư c ch ng minh là xung kh c logic vào năm 1935 khi Stephen Kleene và J. B. Rosser phát tri n ngh ch lí Kleene–Rosser. Phép tính lambda sau ñó ñã ñư c phát tri n ñ tr thành m t công c quan tr ng trong vi c nghiên c u các v n ñ lý thuy t tính toán và lý thuy t ñ quy, và hình thành nên n n t ng cơ b n c a mô hình l p trình hàm L p trình hàm là phong cách l p trình d a trên ñ nh nghĩa hàm s d ng phép tính lambda (λ-calculus). L p trình hàm không s d ng các l nh gán bi n và không gây ra hi u ng ph như v n g p trong l p trình m nh l nh. Trong các ngôn ng l p trình hàm, hàm (th t c, chương trình con) ñóng vai trò trung tâm, thay vì th c hi n l nh, máy tính tính bi u th c. Đã có r t nhi u ngôn ng hàm ñư c phát tri n và ng d ng như Miranda, Haskell, ML, các ngôn ng h Lisp : Scheme, Common Lisp... Ngôn ng Scheme có tính sư ph m cao, gi i quy t thích h p các bài toán h c và x lý ký hi u.Scheme có cú pháp ñơn gi n, d l p trình. M t chương trình Scheme là m t dãy các ñ nh nghĩa hàm góp l i ñ ñ nh nghĩa m t ho c nhi u hàm ph c t p hơn. Scheme làm vi c theo ch ñ thông d ch, tương tác v i ngư i s d ng.
5 Đ tài này mô ph ng l p trình hư ng ñ i tư ng trong l p trình hàm (Scheme). 2. M c tiêu và nhi m v c a ñ tài M c tiêu Mô ph ng ñư c ngôn ng l p trình hư ng ñ i tư ng trong l p trình hàm. Nhi m v Khái quát l i l p trình hư ng ñ i tư ng. Nghiên c u cơ s l p trình hàm và ng d ng. Nghiên c u kh năng mô ph ng l p trình hư ng ñ i tư ng trong l p trình hàm. Th c hi n mô ph ng l p trình hư ng ñ i tư ng trong l p trình hàm . 3. Đ i tư ng và ph m vi nghiên c u Nghiên c u v l p trình hàm, l p trình hư ng ñ tư ng, các ñ c trưng cơ b n. Mô ph ng l p trình hư ng ñ i tư ng s d ng l p trình hàm. Cài ñ t, th nghi m: ñưa ra bài toán x lý hình 2D gi i quyêt b ng phương pháp l p trình hư ng ñ i tư ng s d ng l p trình hàm. 4. Phương pháp nghiên c u Thu th p, tìm hi u và phân tích các tài li u và thông tin b ng ti ng Vi t và ti ng Anh liên quan ñ n lu n văn. Đưa ra bài toán thu c lĩnh v c trí tu nhân t o ñ gi i quy t theo phương pháp l p trình hư ng ñ i tư ng trong l p trình hàm s d ng ngôn ng Scheme. 5. Ý nghĩa khoa h c và th c ti n c a ñ tài V m t lý thuy t
6 Nghiên c u chuyên sâu v kh năng tr u tư ng hóa d li u trong l p trình hàm T ng h p ñư c các nguyên lý mô ph ng l p trình hư ng ñ i tư ng trong l p trình hàm d a trên kh năng tr u tư ng hóa d li u l p trình hàm Ý nghĩa th c ti n Mô ph ng l p trình hư ng ñ i tư ng trong l p trình hàm m r ng ph m vi ng d ng th c ti n c a l p trình hàm Mô ph ng thành công m t bài toán x lý hình 2D ñơn gi n là tiên ñ ñ th c hi n mô ph ng ñ y ñ t p các bài toán x lý hình 2D nh m giúp cho vi c x lý hình c n thi t trong các bài toán ho c ng d ng ñ n lĩnh v c tri th c nhân t o. 6. B c c lu n văn Chương 1. Tìm hi u v l p trình hư ng ñ i tư ng và l p trình hàm chương ñ u tiên này, tôi trình bày khái quát v ngôn ng l p trình, các phong cách l p trình ph bi n. Trong ñó, tôi t p trung nghiên c u cơ s c a hai phong cách l p trình: hư ng ñ i tư ng và l p trình hàm nh m ph c v cho n i dung chính c a lu n văn là mô ph ng l p trình hư ng ñ i tư ng trong l p trình làm. Bên c nh ñó, ngôn ng Scheme là ngôn ng l p trình hàm ñư c ch n ñ nghiên c u ph c v cho vi c cài ñ t mô ph ng. Chương 2. Mô ph ng l p trình hư ng ñ i tư ng trong l p trình hàm. Trong chương này, tôi nghiên c u kh năng mô ph ng l p trình hư ng ñ i tư ng trong l p trình hàm; kh năng tr u tư ng hóa d li u trong ngôn ng l p trình Scheme, ñ ng th i phát bi u ñư c
7 bài toán x lý hình 2D, th c hi n vi c gi i quy t theo phong cách l p trình hư ng ñ i tư ng và th c hi n mô ph ng trong l p trình hàm.
8 Chương 3. Cài ñ t và ñánh giá k t qu th nghi m Trong chương này, tôi mô t l i vi c cài ñ t bài toán theo hai phong cách l p trình và ñánh giá k t qu th nghi m c a vi c mô ph ng l p trình hư ng ñ i tư ng trong l p trình hàm.
9 CHƯƠNG 1. TÌM HI U L P TRÌNH HƯ NG Đ I TƯ NG VÀ L P TRÌNH HÀM chương ñ u tiên này, tôi trình bày khái quát v ngôn ng l p trình, các phong cách l p trình ph bi n. Trong ñó, tôi t p trung nghiên c u cơ s c a hai phong cách l p trình: hư ng ñ i tư ng và l p trình hàm nh m ph c v cho n i dung chính c a lu n văn là mô ph ng l p trình hư ng ñ i tư ng trong l p trình hàm. Bên c nh ñó, ngôn ng Scheme là ngôn ng l p trình hàm ñư c ch n ñ nghiên c u ph c v cho vi c cài ñ t mô ph ng. 1.1. Khái quát ngôn ng l p trình và phong cách l p trình 1.1.1. Khái quát ngôn ng l p trình 1.1.1.1. Khái ni m v ngôn ng l p trình Như chúng ta ñã bi t, máy tính bao g m ph n c ng là các thi t b ñi n t trong ñó thông tin ñư c bi u di n dư i d ng s nh phân và ph n m m bao g m các chương trình ñư c t o ra b ng cách s d ng các ngôn ng l p trình. Như v y ngôn ng l p trình là ngôn ng dùng ñ vi t các chương trình cho máy tính. Cũng như các ngôn ng thông thư ng, Ngôn ng l p trình cũng có t v ng, cú pháp và ng nghĩa. 1.1.1.2. L a ch n ngôn ng l p trình 1.1.2. Phong cách l p trình 1.1.2.1. Đ nh nghĩa phong cách (paradigm) 1.1.2.2. Các phong cách l p trình chính a. Phong cách hư ng m nh l nh b. Phong cách hư ng ch c năng c. Phong cách hư ng logic d. Phong cách hư ng ñ i tư ng
10 1.1.3. Xu th l p trình 1.1.3.1. Yêu c u v ch t lư ng 1.1.3.2. Kh năng ñ c c a mã ngu n 1.1.3.3. Đ ph c t p c a thu t toán 1.1.3.4. Các phương pháp 1.1.3.5. T n su t s d ng ngôn ng 1.1.3.6. Tìm l i (debugging) 1.1.3.7. Môi trư ng phát tri n tích h p (IDE) 1.2. L p trình hư ng ñ i tư ng 1.2.1. L p trình hư ng ñ i tư ng OOP là gì ? L p trình hư ng ñ i tư ng (Object-Oriented Programming, vi t t t là OOP) là m t phương pháp m i trên bư c ñư ng ti n hóa c a vi c l p trình máy tính, nh m làm cho chương trình tr nên linh ho t, tin c y và d phát tri n. Tuy nhiên ñ hi u ñư c OOP là gì, chúng ta hãy b t ñ u t l ch s c a quá trình l p trình – xem xét OOP ñã ti n hóa như th nào [2],[16]. 1.2.1.1. S tr u tư ng hóa d li u 1.2.1.2. L p trình hư ng ñ i tư ng Khái ni m hư ng ñ i tư ng ñư c xây d ng trên n n t ng c a khái ni m l p trình có c u trúc và s tr u tư ng hóa d li u. L p trình hư ng ñ i tư ng (Object Oriented Programming - g i t t là OOP) hay chi ti t hơn là L p trình ñ nh hư ng ñ i tư ng, chính là phương pháp l p trình l y ñ i tư ng làm n n t ng ñ xây d ng thu t gi i, xây d ng chương trình. Th c ch t ñây không ph i là m t phương pháp m i mà là m t cách nhìn m i trong vi c l p trình. Đ phân bi t, v i phương pháp l p trình theo ki u c u trúc mà chúng ta quen thu c trư c ñây, hay còn g i là phương pháp l p trình hư ng th t c (Procedure-Oriented Programming), ngư i l p trình phân tích
11 m t nhi m v l n thành nhi u công vi c nh hơn, sau ñó d n d n chi ti t, c th hoá ñ ñư c các v n ñ ñơn gi n, ñ tìm ra cách gi i quy t v n ñ dư i d ng nh ng thu t gi i c th rõ ràng qua ñó d dàng minh ho b ng ngôn ng gi i thu t (hay còn g i các thu t gi i này là các chương trình con). Cách th c phân tích và thi t k như v y chúng ta g i là nguyên lý l p trình t trên xu ng (top-down), ñ th hi n quá trình suy di n t cái chung cho ñ n cái c th . Các chương trình con là nh ng ch c năng ñ c l p, s ghép n i chúng l i v i nhau cho chúng ta m t h th ng chương trình ñ gi i quy t v n ñ ñ t ra. Chính vì v y, cách th c phân tích m t h th ng l y chương trình con làm n n t ng, chương trình con ñóng vai trò trung tâm c a vi c l p trình, ñư c hi u như phương pháp l p trình hư g v th t c. Tuy nhiên, khi phân tích ñ thi t k m t h th ng không nh t thi t ph i luôn luôn suy nghĩ theo hư ng “làm th nào ñ gi i quy t công vi c”, chúng ta có th ñ nh hư ng tư duy theo phong cách “v i m t s ñ i tư ng ñã có, ph i làm gì ñ gi i quy t ñư c công vi c ñ t ra” ho c phong phú hơn, “làm cái gì v i m t s ñ i tư ng ñã có ñó”, t ñó cũng có th gi i quy t ñư c nh ng công vi c c th . V i phương pháp phân tích trong ñó ñ i tư ng ñóng vai trò trùng tâm c a vi c l p trình như v y, ngư i ta g i là nguyên lý l p trình t dư i lên (Bottom-up). L p trình hư ng ñ i tư ng liên k t c u trúc d li u v i các thao tác, theo cách mà t t c thư ng nghĩ v th gi i quanh mình. Chúng ta thư ng g n m t s các ho t ñ ng c th v i m t lo i ho t ñ ng nào ñó và ñ t các gi thi t c a mình trên các quan h ñó [2],[16].
12 1.2.2. Tính ch t cơ b n c a l p trình hư ng ñ i tư ng L p trình hư ng ñ i tư ng là m t phương pháp l p trình có các tính ch t chính sau: a. Tính tr u tư ng (abstraction) b. Tính ñóng gói (encapsulation) và che gi u thông tin (information hiding) c. Tính ña hình (polymorphism) d. Tính k th a (inheritance) 1.3. L p trình hàm 1.3.1. Nguyên lý l p trình hàm 1.3.1.1. Tính khai báo c a các ngôn ng hàm Trong các ngôn ng m nh l nh, m t chương trình thư ng ch a ba l i g i chương trình con (th t c, hàm) liên quan ñ n quá trình ñưa vào d li u, x lý d li u và ñưa ra k t qu tính toán như sau : begin GetData(...) ; { ñưa vào } ProcessData(...); { x lý } OutPutResults(...); { xem k t qu } end Trong các ngôn ng l p trình hàm, các l i g i chương trình con ñư c vi t thành bi u th c r t ñơn gi n (print (process-data (get-data (...))))
13 1.3.1.2. Đ nh nghĩa hàm 1.3.1.3. Danh sách 1.3.1.4. Khái ni m v b c c a hàm Tính hàm theo ki u khôn ngoan 1.3.2. Ki u d li u ph c h p Ki u d li u trong Scheme g m : ki u chu i (string), ki u vectơ (vector), ki u b ñôi (doublet), ki u danh sách. Ngoài ra, Scheme còn m t s ki u d li u ph c h p khác. Ki u d li u th t c (procedure) ch ñ nh các bi n ch a giá tr tr v c a hàm. Ki u d li u c ng (port) ch ñ nh các c ng vào-ra tương ng v i các t p và các thi t b vào-ra (bàn phím, màn hình). Cu i cùng, t t c các ki u d li u v a xét trên ñây, k c ki u ñơn gi n, ñ u ñư c Scheme gom l i thành m t giu c ñư c g i là ki u s- bi u th c [1]. 1.3.2.1. Ki u chu i 1.3.2.2. Ki u vectơ 1.3.2.3. Ki u d li u b ñôi 1.3.2.4. Ki u d li u danh sách 1.3.3. K thu t x lý hàm 1.3.3.1. S d ng hàm Cho ñ n lúc này, ta ñã s d ng define ñ ñ nh nghĩa bi n và hàm Scheme như sau (define v s) trong ñó : v (variable) là m t bi n s là m t bi u th c (define (f L) s) trong ñó : L dãy t 0.. n bi n, f là tên hàm hay tên bi n,
14 s là bi u th c ñóng vai trò thân c a hàm. M t hàm trong Scheme ñư c xem như m t ki u d li u hay m t s-bi u th c, do ñó, hàm có th ñư c dùng làm tham ñ i và cũng có th làm giá tr tr v . Ta s xét l n lư t hai kh năng này và m t cách khác ñ nh nghĩa hàm nh phép tính lambda (λ-calculus) [1]. 1.3.3.2. Phép tính Lambda 1.3.3.3. Đ nh nghĩa hàm nh lambda 1.4. So sánh hai phong cách l p trình L p trình hàm ñư c thi t k ñ h tr cách ti p c n gi i quy t bài toàn theo hư ng thu n ch c năng. L p trình hàm là m t hình th c l p trình ki u khai báo. phía ngư c l i, l p trình hư ng ñ i tư ng ñư c thi t k ñ h tr cách ti p c n gi i quy t bài toàn theo hư ng mênh l nh. V i cách ti p c n theo hư ng m nh l nh, ngư i l p trình vi t các ño n mã mô t m t cách chính xác các bư c mà máy tính c n ph i làm ñ gi i quy t bài toán. L p trình hư ng ñ i L p trình hàm tư ng Tương tác v i d - Phân tích d li u Áp d ng các toán t li u b ng cách truy n cơ b n lên m t ph n m t thông ñi p ñ n d li u m t ñ i tư ng và ch ñ i s ph n h i t ñ i tư ng ñó - Đ i tư ng s d ng: - Đ i tư ng s d ng: các hàm các phương th c c a l p
15 Các thành ph n ngôn - D li u cơ b n: các - D li u cơ b n: các ng s , ký t , s , ký t - Đ nh nghĩa các l p, - Ki u d li u các giao ti p - Đ nh nghĩa phương - Đ nh nghĩa hàm th c - Các c u trúc - Các c u trúc + bi n + bi n + toán t + toán t + c u trúc ñi u ki n + c u trúc ñi u ki n + l i g i phương + l i g i phương th c th c + kh i phương th c + kh i phương th c + phép gán + phép gán Tr ng thái c a - Phương th c và ñ i - N u l p trình hàm chương trình tư ng trong l p trình thu n túy có gán giá hư ng ñ i tư ng có tr ñ n m t bi n, lưu gi tr ng thái bi n ñó ph i ñư c bên trong c a chúng xem và lưu gi như (thông qua bi n n i nh ng thành ph n t i c a phương th c không thay ñ i và thu c tính c a ñ i ñư c. tư ng) - Tr ng thái có th - Vi c gán giá tr cho ñư c luân chuy n bi n là d u hi u cho như m t tham s ñ n th y ñ i tư ng có m t hàm, ñi u này lưu gi tr ng thái ñư c g i như là s bên trong ti p t c.
16 1.5. Gi i thi u Scheme Scheme là m t ngôn ng thao tác ký hi u (symbolic manipulation) do Guy Lewis Steele Jr và Gerald Jay Sussman ñ xu t năm 1975 t i MIT (Massachusetts Institute of Technology, Hoa Kỳ), sau ñó ñư c phát tri n nhanh chóng và ng d ng r t ph bi n Scheme là m t ngôn ng l p trình hàm thu c h Lisp. Ngôn ng Scheme r t thích h p ñ mô t các khái ni m tr u tư ng và các công c l p trình. Scheme có cú pháp ñơn gi n, d hi u, d l p trình. Ho t ñ ng cơ b n trong l p trình Scheme là tính giá tr các bi u th c. Scheme làm vi c theo ch ñ tương tác. 1.5.1. Các ki u d li u c a Scheme Trong Scheme có hai lo i ki u d li u là ki u ñơn gi n (simple data type) và ki u ph c h p (compound data type). 1.5.1.1. Các ki u d li u ñơn gi n Các ki u d li u ñơn gi n c a Scheme bao g m ki u s (number), ki u lôgích (boolean), ki u ký t (character) và ki u ký hi u (symbol). 1.5.1.2. Khái ni m v các bi u th c ti n t 1.5.2. Các ñ nh nghĩa trong Scheme 1.5.2.1. Đ nh nghĩa bi n Bi n (variable) là m t tên g i ñư c gán m t giá tr có ki u nào ñó. M t bi n ch ñ nh m t v trí nh lưu gi giá tr này. Các tên ñ c bi t như define g i là t khóa c a ngôn ng do nó ch ñ nh m t phép toán ti n ñ nh. 1.5.2.2. Đ nh nghĩa hàm a. Khái ni m hàm trong Scheme b. G i hàm sau khi ñ nh nghĩa c. S d ng các hàm b tr 1.5.3. Kh năng ñ h a trong Scheme
17 CHƯƠNG 2. MÔ PH NG L P TRÌNH HƯ NG Đ I TƯ NG TRONG L P TRÌNH HÀM Trong chương này, tôi nghiên c u kh năng mô ph ng l p trình hư ng ñ i tư ng trong l p trình hàm; kh năng tr u tư ng hóa d li u trong ngôn ng l p trình Scheme, ñ ng th i phát bi u ñư c bài toán x lý hình 2D, th c hi n vi c gi i quy t theo phong cách l p trình hư ng ñ i tư ng và th c hi n mô ph ng trong l p trình hàm. 2.1. Kh năng l p trình hư ng ñ i tư ng trong l p trình hàm 2.1.1. Khái quát Như chúng ta ñã bi t, trong l p trình hư ng ñ i tư ng, tr u tư ng hóa d li u là ý tư ng quan tr ng nh t ñ phát tri n ngôn ng l p trình hư ng ñ i tư ng. Nên vi c nghiên c u ñ mô ph ng l p trình hư ng ñ i tư ng trong l p trình hàm chính là vi c nghiên c u kh năng tr u tư ng hóa d li u trong l p trình hàm. Đ ñ nh nghĩa ñư c ki u d li u tr u tư ng trong l p trình hàm, chúng ta ph i xem m i tr ng thái c a m t c u trúc là m t th c th ñ c l p. V i cách nhìn này, b t kỳ thác tác nào làm thay ñ i ki u d li u tr u tư ng ñư c mô hình hóa gi ng như m t phương th c toán h c, mà thao tác này n m gi tr ng thái cũ như là tham s và tr v tr ng thái m i như là k t qu c a hàm th c thi. Không gi ng như các thao tác trong ngôn ng l p trình m nh l nh, nh ng hàm này s không có nh ng nh hư ng ph ñ i v i nh ng thu c tính ho c phương th c khác c a ki u d li u tr u tư ng. Vì th , th t th c thi c a chúng không quan tr ng và v i cùng m t thao tác ñ i v i cùng m t s tham s nh t ñ nh, k t qu th c hi n s là như nhau.
18 2.1.2. Tr u tư ng hóa d li u trong l p trình hàm Tr u tư ng hoá th t c (procedure abstraction) là xây d ng các ng d ng ph c t p t nh ng thao tác ñơn gi n, b ng cách che d u trong ch ng m c có th nh ng chi ti t x lý. Tr u tư ng hoá d li u cũng nh m m c ñích ñ nh nghĩa m t l p d li u ph c t p và cách thao tác trên các d li u ñó mà không quan tâm ñ n cách bi u di n và cài ñ t chúng trong máy v t lý như th nào. Phương pháp tr u tư ng hoá d li u ñư c ng d ng r ng rãi trong l p trình hư ng ñ i tư ng. M t c u trúc d li u tr u tư ng hay ki u d li u tr u tư ng ñư c ñ nh nghĩa, hay ñư c ñ c t (specification) b i 4 thành ph n : tên ki u d li u tr u tư ng (types), các ñ nh nghĩa hàm (functions), các ñi u ki n ñ u (preconditions) n u có và các tiên ñ (axioms). Hai thành ph n ñ u mô t cú pháp v m t c u trúc thu c tính c a ki u d li u tr u tư ng, hai thành ph n sau mô t ng nghĩa. Thành ph n functions li t kê các khuôn m u hàm (function pattern). M i khuôn m u hàm, còn ñư c g i là m t ký pháp (signature), có d ng m t ánh x cho bi t ki u c a các tham ñ i và c a k t qu như sau : Tên-hàm : mi n-xác-ñ nh −> mi n-tr Ngư i ta thư ng phân bi t ba lo i hàm là hàm ki n t o (constructor) ñ t o ra ki u d li u m i, hàm ti p nh n (accessor) ñ trích ra các thu c tính và hàm bi n ñ i (transformator) ñ chuy n ki u d li u. Do các hàm không ph i luôn luôn xác ñ nh v i m i d li u nên ngư i ta cũng phân bi t các hàm toàn ph n (total functions) và các hàm b ph n (partial functions). Trong trư ng h p các hàm là b
19 ph n, ngư i ta c n cung c p các ñi u ki n ñ u là các ràng bu c trên mi n xác ñ nh c a hàm. M t l i g i hàm không tuân theo ñi u ki n ñ u ñ u d n ñ n sai sót (chia cho 0, tính căn b c hai c a m t s âm, v.v...). Thành ph n axioms mô t các ch c năng v n d ng hàm, ph i ñư c khai báo rõ ràng, ñ y ñ và d hi u. M i v n d ng hàm có d ng m t m nh ñ lôgích h p th c luôn có giá tr true, nghĩa là m t h ng ñúng (tautology). Khi c n s d ng các bi n, ngư i ta s d ng t khoá var ñ khai báo trư c tên các bi n, tương t trong các ngôn ng l p trình m nh l nh như C, Pascal... V i nh ng kh năng nêu trên, nh n th y r ng, hoàn toàn có th mô ph ng l p trình hư ng ñ i tư ng trong l p trình hàm d a trên vi c tr u tư ng hóa d li u. Trong ñó, ‘d li u’ là các l p, thành ph n cơ b n c a l p trình hư ng ñ i tư ng. 2.2. Mô ph ng l p trình hư ng ñ i tư ng trong scheme Trong quá trình th c hi n ñ tài này, tôi ch n Racket như là phiên b n phát tri n c a Scheme ñ nghiên c u, nên vi c nghiên c u kh năng mô ph ng l p trình hư ng ñ i tư ng trong Scheme ñư c di n t là kh năng mô ph ng l p trình hư ng ñ i tư ng trong Racket. Đây chính là nguyên lý l p trình hư ng ñ i tư ng trong l p trình hàm. 2.2.1. L p và ñ i tư ng 2.2.2. Phương th c 2.2.3. Tham s kh i t o 2.3. Ví d bài toán x lý hình 2D 2.3.1. Phát bi u bài toán x lý hình 2D
20 Cho tam giác trong m t ph ng không gian 2 chi u. Tìm ñư ng tròn ngo i ti p tam giác khi m t ñ nh thay ñ i t a ñ trong không gian 2 chi u tâm O. 2.3.2. Phân tích bài toán Phát bi u bài toán trên, tôi nh n th y m t s ñ i tư ng tham gia trong bài toán bao g m: - Tam giác ABC: là ñ i lư ng bao g m m t b ba ñ i tư ng ñi m, trong ñó ñ i tư ng ñi m ñư c ñ c trưng b ng b giá tr x và y là s th c, ñ i di n cho hoành ñ và tung ñ c a ñi m trên m t ph ng t a ñ 2 chi u. - Đư ng tròn tâm O: là ñ i lư ng bao g m m t ñi m trong m t ph ng t a ñ 2 chi u và ñ i lư ng R là s th c, ñ i di n cho bán kính c a ñư ng tròn này. Các công vi c c n gi i quy t: - Xác ñ nh b ba ñ i tư ng ñi m có thõa mãn ñi u ki n t o thành m t tam giác ABC hay không? - Xác ñ nh tâm c a ñư ng tròn ngo i ti p tam giác ABC trên - Xác ñ nh bán kính c a ñư ng tròn ngo i ti p Trên cơ s xác ñ nh các ñ i tư ng c n ñ c t trong h th ng và các phương th c tính toán liên quan, ngư i vi t th c hi n ñ c t trong theo hai phong cách l p trình: hư ng ñ i tư ng và l p trình hàm. 2.3.3. Đ c t bài toán trong l p trình hư ng ñ i tư ng Trên c s phát bi u c a bài toán, danh sách các l p ñư c phân tích và li t kê trong mô hình l p bên dư i.