Khóa luận Xây dựng trình biên dịch cho ngôn ngữ wave: Xây dựng hệ thống track

- 1 - ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Trương Văn Hiếu XÂY DỰNG TRÌNH BIÊN DỊCH CHO NGÔN NGỮ WAVE XÂY DỰNG HỆ THỐNG TRACK KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY 1. 1 HÀ NỘI - 2009 - 2 - MỤC LỤC Mục lục hình vẽ ................................................................................................... 5  Khái niệm và cụm từ viết tắt .............................................................................. 8  CHƯƠNG 1.  GIỚI THIỆU .............................................................................. 9  1. 1  Wave............................................................................................................................9  1. 2  Các ứng dụng của Wave..........................................................................................10  1. 3  Nội dung khóa luận..................................................................................................11  CHƯƠNG 2.  NGÔN NGỮ WAVE................................................................ 12  2. 1  Giới thiệu về Ngôn ngữ Wave .................................................................................12  2. 2  Node, Link và Không gian phân tán : Knowledge Network (KN) ......................12  2. 3  Tổ chức chung của ngôn ngữ Wave .......................................................................13  2. 4  Cấu trúc dữ liệu cơ bản của Wave .........................................................................14  2. 5  Biến Spatial và kiểu .................................................................................................14  2. 5. 1  Task variables ................................................................................................................15  2. 5. 2  Environment variables ..................................................................................................15  2. 6  Các hành động - ACTS............................................................................................15  2. 6. 1  Control acts....................................................................................................................15  2. 6. 2  Fusion acts: Các phép toán hợp nhất...........................................................................17  2. 7  Rules – Các luật trong Wave ..................................................................................17  2. 8  Wave và mô hình lập trình truyền thống ..............................................................19  2. 8. 1  Sơ đồ luồng (SD) ...........................................................................................................19  2. 8. 2  Wave và mô hình lập trình song song ..........................................................................20  2. 8. 3  Wave và mô hình lập trình tuần tự...............................................................................22  CHƯƠNG 3.  XÂY DỰNG BỘ INTERPRETER ......................................... 28  - 3 - 3. 1  Wave không có Rule ................................................................................................28  3. 1. 1  Chi tiết ví dụ về các bước của Wave .............................................................................28  3. 1. 2  Thuật toán tổng quát cho Wave không có Rule ...........................................................30  3. 2  Wave có Rule ............................................................................................................31  3. 2. 1  Ví dụ về Wave có Rule...................................................................................................31  3. 2. 2  Thuật toán tổng quát cho Wave có Rule .....................................................................33  3. 3  Hệ thống Track ........................................................................................................36  3. 3. 1  Rule dựa trên bộ điều khiển Track...............................................................................36  3. 3. 2  Thuật toán cho Bộ xử lý track ......................................................................................39  3. 3. 3  Sự lan tỏa Track ............................................................................................................40  3. 4  Tổng quan và kiến trúc của Wave Interpreter .....................................................41  3. 5  Các thành phần trong Wave Interpreter...............................................................42  3. 5. 1  Wave và Wave Queue ....................................................................................................42  3. 5. 2  Knowledge Network.......................................................................................................42  3. 5. 3  Track Forest ..................................................................................................................43  3. 5. 4  Parsing Unit...................................................................................................................44  3. 5. 5  Excution Processor........................................................................................................51  3. 5. 6  TrackProcessor..............................................................................................................52  3. 5. 7  Communication Processor ............................................................................................56  3. 6  Quan hệ giữa các thành phần trong Wave Interpreter........................................57  3. 6. 1  Luồng xử lý Wave..........................................................................................................60  3. 6. 2  Luồng xử lý các echo và điều khiển các rule ...............................................................64  3. 6. 3  Xây dựng trình biên dịch Wave trên ngôn ngữ Java ...................................................67  CHƯƠNG 4.  THỰC HIỆN VÀ KẾT QUẢ .................................................. 69  4. 1  Cài đặt .......................................................................................................................69  4. 1. 1  Các yêu cầu về phần cứng ............................................................................................69  4. 1. 2  Các yêu cầu về phần mềm.............................................................................................69  - 4 - 4. 2  Thử nghiệm...............................................................................................................70  4. 2. 1  Sử dụng chương trình...................................................................................................70  4. 2. 2  Tạo lưới thực địa ...........................................................................................................71  4. 3  Di chuyển tự do ........................................................................................................72  4. 3. 1  Di chuyển tránh chướng ngại vật .................................................................................75  4. 3. 2  Di chuyển vòng quanh chướng ngại vật ......................................................................77  4. 4  Di chuyển cùng nhau kiểu tịnh tiến........................................................................80  4. 4. 1  Hiển thị hình ảnh 3D động bằng GnuPlot...................................................................80  4. 4. 2  Hiển thị hình ảnh 3D của tệp tin VRML......................................................................81  4. 4. 3  Hiển thị hình ảnh 3D với các góc nhìn khác nhau .....................................................82  4. 4. 4  Hiển thị hình ảnh 3D VRML trên nhiều máy..............................................................83  CHƯƠNG 5.  PHỤ LỤC.................................................................................. 86  5. 1  JJTree .......................................................................................................................86  5. 1. 1  Giới thiệu .......................................................................................................................86  5. 1. 2  Các kiểu cấu trúc cây ....................................................................................................86  5. 2  Thực thi trên ngôn ngữ simpleLang.......................................................................87  5. 3  Xây dựng bộ parser cho ngôn ngữ Wave...............................................................89  CHƯƠNG 6.  TÀI LIỆU THAM KHẢO....................................................... 92  - 5 - Mục lục hình vẽ Hình 1-1: Mô hình Wave .......................................................................................................................10  Hình 2-1: Knowledge Network ..............................................................................................................13  Hình 2-2: Thành phần của Spread Diagrams .........................................................................................20  Hình 2-3: Tự động tách trong chuỗi Wave.............................................................................................21  Hình 2-4: Một số trường hợp xử lý song song .......................................................................................21  Hình 2-5: Wave xử lý song song có kèm theo Rule...............................................................................22  Hình 2-6: Xử lý tuần tự không Rule và có Rule.....................................................................................23  Hình 2-7: Wave xử lý tuần tự có Rule ...................................................................................................23  Hình 2-8: một số trường hợp với mệnh đề If – else ...............................................................................24  Hình 2-9: Một số trường hợp với mệnh đề If – else...............................................................................24  Hình 2-10: else – if với filter..................................................................................................................25  Hình 2-11: Else – if parallel ...................................................................................................................25  Hình 2-12: Else – if với Rule .................................................................................................................26  Hình 2-13: Switch ..................................................................................................................................26  Hình 2-14: Câu lệnh lặp sử dụng Repetition..........................................................................................27  Hình 2-15: Câu lệnh lặp sử dụng Recursion ..........................................................................................27  Hình 3-1: Wave có Rule.........................................................................................................................31  Hình 3-2: Tạo track trong quá trình Wave thực thi và lan tỏa .................................................................1  Hình 3-3: Trạng thái và biến frontal.........................................................................................................1  Hình 3-4: Gửi echo và tổng hợp các kết quả trạng thái, sau đó loại các Track Link, Track Node thừa ..1  Hình 3-5: Truyền Tail tới các Track Node ngoài cùng (Node lá) ............................................................1  Hình 3-6: Kích hoạt Tail trong các Node lá .............................................................................................1  Hình 3-7. Các thành phần của Wave Interpreter ....................................................................................41  Hình 3-8: Wave và Wave Queue..............................................................................................................1  Hình 3-9: Knowledge Network ................................................................................................................1  Hình 3-10: Track Forest ...........................................................................................................................1  - 6 - Hình 3-11: Excution Processor ..............................................................................................................52  Hình 3-12: Sau khi nhận và xử lý CREATE ............................................................................................1  Hình 3-13: Sau khi nhận và xử lý EXPANDH ........................................................................................1  Hình 3-14: Sau khi nhận và xử lý ACTIVATE........................................................................................1  Hình 3-15: Sau khi nhận ECHO từ các nhánh con...................................................................................1  Hình 3-16: Sau khi xử lý ECHO nhận được ............................................................................................1  Hình 3-17: Communication Processor .....................................................................................................1  Hình 3-18: Quan hệ giữa các thành phần trong Wave Interpreter ...........................................................1  Hình 3-19: Luồng xử lý giữa các thành phần trong Wave Interpreter ...................................................60  Hình 3-20: Lan truyền echo lên trên ........................................................................................................1  Hình 3-21: Gửi tail cho các track con ......................................................................................................1  Hình 4-1. Chương trình hiển thị khi mới được chạy ..............................................................................70  Hình 4-2. Chương trình WAVE khi bắt đầu chạy.................................................................................71  Hình 4-3. Lưới 5x5................................................................................................................................71  Hình 4-4. Cửa sổ output của Netbeans...................................................................................................72  Hình 4-5. Vị trí đầu tiên 1-1...................................................................................................................72  Hình 4-6. Chạy ngẫu nhiên tới vị trí tiếp theo........................................................................................73  Hình 4-7. Các bước chạy ngẫu nhiên tiếp theo ........................................................................................1  Hình 4-9. Dừng khi chạy tới đích...........................................................................................................75  Hình 4-8. Tiếp tục chạy ngẫu nhiên .........................................................................................................1  Hình 4-10. Di chuyển qua chướng ngại vật .............................................................................................1  Hình 4-11. Vượt qua chướng ngại vật và về đến đích..............................................................................1  Hình 4-12. Di chuyển vòng quanh chướng ngại vật ................................................................................1  Hình 4-13. Vòng quanh chướng ngại vật 1 vòng thì dừng.......................................................................1  Hình 4-14. Di chuyển tịnh tiến cùng nhau ...............................................................................................1  Hình 4-15. Hình ảnh 3D trên máy thứ nhất sử dụng GnuPlot..............................................................81  Hình 4-16. Hình ảnh 3D trên máy thứ hai sử dụng GnuPlot..................................................................81  Hình 4-17. Tệp tin VRML được hiển thị sau khi được tạo bởi KN .......................................................82  - 7 - Hình 4-18. Các đối tượng hiển thị theo cách khác thi thay đổi Transform ............................................83  Hình 4-19. Một cách nhìn khác thi thay đổi Transform.........................................................................83  Hình 4-20. Hiển thị đối tượng đầu tiên trên máy 1 ................................................................................84  Hình 4-21. Hiển thị đối tượng thứ hai trên máy 2..................................................................................85  - 8 - Khái niệm và cụm từ viết tắt CP Communication Processor CQ Communication Queue EU Execution Unit KN Knowledge Network PU Parsing Unit SD Spread Diagrams SNR Set of Nodes reached TF Track Forest TN Track Node TP Track Processor TQ Track Queue WI Wave Interpreter WQ Wave Queue - 9 - CHƯƠNG 2. GIỚI THIỆU Ở chương này chúng tôi trình bày tổng quan về công nghệ Wave nhằm trả lời các câu hỏi sau: Wave là gì? Nó khác và ưu điểm hơn so với các hệ thống bình thường ở chỗ nào? Các ứng dụng viết trên Wave sử dụng trong lĩnh vực gì? 2. 1 Wave Ngày nay, các hệ thống mở và mạng máy tính đang phát triển rất nhanh và được cả thế giới quan tâm. Hệ thống mạng máy tính kết nối công việc từ khắp nơi trên thế giới, mạng máy tính cũng giữ một khối lượng khổng lồ dữ liệu dịch vụ và thông tin. Những công cụ tương tác không chỉ để tìm kiếm thông tin, dịch vụ hoặc file ngay trên máy tính mà còn được mở rộng về địa lý, không gian… và hoàn toàn mở trên Internet. Một ví dụ điển hình ở đây chính là World Wide Web. Tuy nhiên, hầu hết các mô hình và công cụ lập trình phân tán thiếu đi khả năng linh hoạt để khai thác thông tin về cấu trúc mở một cách tự động. Những mô hình lập trình và hệ thống phân tán truyền thống thường dựa trên dữ liệu đóng. Công việc được xử lý trong các ứng dụng phân tán thường phải được định nghĩa trước hoặc được gọi thông qua việc kích hoạt thủ tục, phương thức. Phần lớn việc xử lý và tương tác thông qua việc trao đổi thông điệp chứa dữ liệu. Ngoài ra hệ thống phân tán có thể cung cấp dữ liệu và dịch vụ chia sẻ. Trong mạng máy tính, dịch vụ và thông tin chỉ nằm ở các máy chủ ứng dụng (ví dụ như việc sử dụng của các tổ chức kinh doanh…). Tuy nhiên, phương pháp tiếp cận này vẫn chưa tối ưu. Do đó, chúng ta sẽ cần phải tích hợp linh hoạt các máy chủ ứng dụng trong một hệ thống tổng thể và có cơ sở hạ tầng mở hơn nữa. WAVE không chỉ là một mô hình. Wave còn là công nghệ dựa trên sự liên kết và điều khiển của các hệ thông lớn được hỗ trợ bởi mạng máy tính và viễn thông. Wave cho phép linh động tạo các cấu trúc điều khiển và việc xử lý mạng tri thức (phân tán và song song) thông minh. Các cấu trúc này có thể cung cấp khả năng tự tổ chức, phục hồi, tạo khuôn mẫu để kết nôai tới các hệ thống khác. Công nghệ này dựa trên việc cài đặt nhiều tác nhân thông minh trên hệ thống phân tán để tối ưu hóa việc xử lý dữ liệu cục bộ thông qua việc lan tỏa thông tin ở các hệ thống nhỏ với nhau hoặc ở hai hệ thống nhỏ khác nhau. Tất cả công việc trên đều được thông dịch qua ngôn ngữ Wave. Mã đệ quy được viết từ ngôn ngữ này có khả năng tự lan tỏa trong không gian hệ thống. Không giống các hệ thống truyền thống, nó là một hệ thống dựa trên sự linh động của chương trình có thể tùy ý mở rộng về mặt địa lý và hỗ trợ nhiều máy tính trên mạng. Trong Wave, chương trình có thể cho vào trong hệ thống bất kỳ chỗ nào. Khi đó các chương trình này có khả năng lan tỏa qua mạng như virus. Nhiều người sử dụng có thể độc lập phát triển các chương trình Wave hoặc liên kết trong cùng một hệ thống không gian, chia sẻ biến cục bộ (biến này được liên kết với Node) với các biến khác (được kèm theo sự duy chuyển của mã Wave). Nói cách khác: • Wave là một ngôn ngữ, model đặc biệt và là công nghệ mới cho hệ thống song song, phân tán hay kết hợp các hệ thống đó với nhau. - 10 - • Wave ban đầu được thiết kế cho việc mô phỏng mạng ảo như là mạng tri thức (Knowledge Networks). • Wave dựa trên các chương trình mà có thể lan tỏa, mở rộng, chia nhỏ và có thể tự hồi đáp trong những mạng tri thức đã được kích hoạt. Hình 2-1: Mô hình Wave 2. 2 Các ứng dụng của Wave Các thuật toán về phân tán đã được lập trình thành công trong WAVE như các bài toán liên quan đến đồ thị và các vấn đề lý thuyết về mạng (tìm đường ngắn nhất, phân tích topology mạng, các loại cây spanning…). Các hoạt động tự phục hồi đồ thị, thủ tục cập nhật thông tin liên lạc như địa điểm, đường đi…trên điện thoại di động. Những ứng dụng hiện nay bao gồm việc quản lý hệ thống mạng máy tính tích hợp với hệ thống quản lý truyền thống với công nghệ Wave. Một vài ứng dụng như: xử lý máy móc, mô hình và kiểm soát trong mạng di động, tích hợp cơ sở dữ liệu phân tán. Wave cũng có thể được gọi là “Điện thoại thông minh” với hàng loạt ứng dụng: • Mô hình giao tiếp mạng di động. • Tích hợp hệ thống cơ sở dữ liệu phân tán. • Mô phỏng mạng lưới giao thông, phân tích và điều khiển. • Điều khiển phân tán mạng lưới hàng không một cách tự động giữa các vùng, miền. • Ứng dụng vào việc đo đạc địa lý một cách tự động. • Quản lý thông minh trong hệ thống viễn thông và mạng máy tính mở. • Điều khiển trong robot. Các ứng dụng trên Wave còn được thể hiện chi tiết và rõ ràng trong khóa luận tốt nghiệp của các bạn: ‐ Vũ Đức Tiệp và Đỗ Thế Chuẩn hai bạn đã đưa ra vấn đề cụ thể: Xây dựng hệ thống mô phỏng và thực tại ảo bằng ngôn ngữ Wave. ‐ Phí Hồng Thái và Phạm Minh Ngọc: Hệ thống phân tích mạng xã hội Yahoo!360 dựa trên nền tảng công nghệ Wave. - 11 - 2. 3 Nội dung khóa luận Trong các chương ở khóa luận này, chúng tôi đề cập những vấn đề sau: Chương 1: Giới thiệu và trình bày tổng quan cũng như các ứng dụng của Wave Chương 2: Trình bày về cú pháp, ngữ nghĩa cách tổ chức chung của ngôn ngữ Wave. Ngoài ra chúng tôi còn đưa ra một vấn đề nữa là: Wave và các mô hình lập trình truyền thống (tuần tự hoặc song song). Chương 3: Trình bày về cách xây dựng hệ thống Interpreter cho Wave bằng cách tiếp cận từ lý thuyết tới việc tìm hiểu kiến trúc chung của hệ thống, các thành phần và quan hệ giữa các thành phần đó. Chương 4: Đưa ra các bài toán thực tế và kết quả đạt được. Chương 5: Phụ lục về JJTree Chương 6: Tài liệu tham khảo. - 12 - CHƯƠNG 3. NGÔN NGỮ WAVE Trong phần này chúng tôi trình bày về cú pháp và ngữ nghĩa của ngôn ngữ Wave. Đây là một ngôn ngữ đặc biệt cho phép tạo và xử lý thông tin trong không gian mạng theo hướng. Chương trình viết bằng ngôn ngữ này có thể được coi như những thành phần linh hoạt, có khả năng di động và kết hợp với các thành phần riêng lẻ, phân tán khác. Trong quá trình “di chuyển”, chương trình có thể mang theo dữ liệu đồng thời cập nhật vào dữ liệu lưu tại mạng KN. Các chương trình mặc dù được xử lý song song nhưng vẫn có những cơ chế cho phép chúng phối hợp đồng bộ với nhau thông qua hệ thống các luật. Ở phần cuối chương này chúng tôi còn đề cập tới một vấn đề nữa: Wave và các phương pháp lập trình truyền thống (lập trình tuần tự và lập trình song song). 3. 1 Giới thiệu về Ngôn ngữ Wave Wave là một ngôn ngữ đặc biệt cung cấp khả năng thực thi mềm dẻo, đa người dùng trên hệ thống phân tán. Quá trình thực thi của ngôn ngữ Wave giống như virus, tức là có khả năng nhân bản và lan tỏa qua mạng, thực thi phân tán mà không cần bất kỳ sự điều khiển tập trung nào. Kiến trúc Wave mô tả quá trình xử lý phân tán qua việc tự định hướng luồng chương trình qua không gian dữ liệu phân tán có cấu trúc như một đồ thị hay được gọi là Knowledge Network. Các node trên mạng phân tán thuộc về một Wave Interpreter nào đấy. WI là thành phần có trách nhiệm thực thi trên từng bộ phận riêng lẻ của mạng, thao tác lên dữ liệu được lưu trữ trong các node.Trong khi di chuyển, những thành phần của mã Wave có thể tự nhân bản, phân chia hay được chỉnh sửa trong khi vẫn duy trì sự trao đổi dữ liệu qua lại lẫn nhau. 3. 2 Node, Link và Không gian phân tán : Knowledge Network (KN) Định nghĩa: • Node: Có thể coi là một đối tượng – hay một điểm trong không gian, chứa các biến (biến là thuộc tính của node) • Link: Có thể coi là một quan hệ giữa các nút - hay một đoạn, đường thẳng trong không gian. Nó cũng có các thuộc tính Wave tạo và xử lý KN – là tập hợp các node và các link có hướng hoặc vô hướng. Cả node và link đều có nội dung riêng của mình (kiểu giá trị là string). KN có thể được phân tán trong không gian mạng, tồn tại trên nhiều máy tính khác nhau. Mỗi máy tính có thể không chứa hoặc chứa nhiều node của KN và các link có thể kết nối tới các node trong cùng máy tính hoặc với các máy tính khác. Tất cả các node đều có địa chỉ duy nhất trong không gian phân tán bao gồm 2 thành phần: thành phần thứ nhất để phân biệt các node trong cùng một máy, và thứ hai là để phân biệt các node giữa các máy khác nhau trong không gian mạng. Node có thể - 13 - được truy cập qua các node khác một cách trực tiếp bằng Content hay bằng Address của chúng hoặc qua quá trình mở rộng qua các link của KN, việc đặt tên cho link và node nhằm phục vụ điều này. Có hai kiểu nhảy qua lại giữa các node đó là direct hop và surface hop để thực hiện việc nhảy tới 1 node hay có thể nhảy đến tất cả các node khác – được dùng cho việc gửi quảng bá. Không giống với node, link của KN không thể truy xuất trực tiếp qua tên. Dữ liệu lưu trữ trong link chỉ có thể nhận được hoặc thay đổi một cách cục bộ, trong quá trình di chuyển qua link hay khi đứng trực tiếp tại một node cụ thể nào đó. Từ một node, cả nội dung và hướng của link có thể truy xuất trực tiếp. Ví dụ: Hình 3-1: Knowledge Network 3. 3 Tổ chức chung của ngôn ngữ Wave Ngôn ngữ Wave đặc trưng cho quá trình lan tỏa song song trong không gian dữ liệu phân tán được biết là KN. Do vậy cú pháp của ngôn ngữ miêu tả rõ quá trình hoạt động này: trong đó các phần nằm trong [] là tùy chọn wave Æ {{move , } . } move Æ { data_unit act } | [rule] (Wave) } rule Æ SQ | OS | AS | AP | RP | WT | ID | CR unit Æ { stirng; } | N{l_d} | F{l_d} | C | A | P | S | L | T | act Æ # | ~ | /~ | == | / = | < | <= | + | - | * | / | ** | | | % | & | : | :: | = | ? | ! - 14 - Một chương trình Wave hay gọi đơn giản là Wave bao gồm sự kết hợp các tác động lên KN gọi là các move – thành phần có thể thực hiện xử lý dữ liệu cục bộ tại các Node của KN và mở rộng tới các Node khác. Quá trình thực thi song song hay thực thi không theo thứ tự được tách biệt bởi dấu phẩy (,) phát triển một cách độc lập từ cùng một Node trong KN. Tập các moves độc lập gọi là zone, được tách biệt nhau bởi dấu chấm câu (.), các thành phần này sẽ được thực thi một cách tuần tự. Ví dụ: Ft={Fa=1;2;3}. Fa+1. ^Ft.T=Fa Các Rule trong Wave cung cấp cho Wave khả năng mở rộng trong không gian mạng, kết hợp cùng với các Wave khác. Một ví dụ, các luật có thể tự động tách Wave ra thành nhiều nhánh riêng biệt rồi sau đó phát triển chúng song song hoặc tuần tự trong KN, chúng có thể tạo ra hoặc mở rộng KN trong khi di chuyển. Các Rule sẽ được làm rõ hơn trong phần sau. Một cách tổng quát, việc thực thi phần đầu của Wave (Wave’s Head) tại một vài Node có thể là nguyên nhân dẫn tới quá trình lan tỏa của Tail của chuỗi Wave (Wave’s Tail) tới 0 hay nhiều các Node khác– chúng ta sẽ gọi chúng là tập các Node tới được (SNR). Ví dụ: • w1.w2.w3.w4 : cấu trúc của một chương trình Wave - sự nối tiếp của các zones • w1,w2,w3: zone đơn lẻ với tập các move độc lập, tất cả đều được thực thi tại cùng một Node bắt đầu • w1,w2.w3,w4: sự kết hợp của 2 kiểu trên. 3. 4 Cấu trúc dữ liệu cơ bản của Wave Wave là ngôn ngữ được dùng cho quá trình xử lý trên mạng, nhưng không giống các ngôn ngữ khác, kiểu dữ liệu cơ sở không phản ánh việc đó. Wave sử dụng kiểu dữ liệu cơ sở là Vector: là tập các string được phân tách nhau bới dấu chấm phẩy (;). Tất cả các hoạt động của ngôn ngữ đều thực thi trên Vector. Truy cập tới thành phần của Vector có thể thông qua chỉ số hay chính nội dung của các thành phần trong Vector – indexing và contenting. Dữ liệu lưu trữ trong Vector là động, tức có thể thay đổi khi có sự thêm bớt dữ liệu một cách tự động. Ví dụ: • Vector chứa 1 phần tử: 3 • Chứa 6 phần tử: 1;2;3;4;5;6 • Chứa nhiều kiểu dữ liệu khác nhau: 34;NONE;25;;a;;;b 3. 5 Biến Spatial và kiểu Wave thao tác trên kiểu biến được gọi là spatial variable, chúng nằm phân tán và thường liên quan tới dữ liệu cục bộ tại các Node của KN hay có thể thuộc về một - 15 - chuỗi Wave nào đó. Biến kiểu này được chia làm 2 loại: task variable và environment variable 3. 5. 1 Task variables Task variable bao gồm: node variable và frontal variable. Các biến kiểu nodal được lưu cục bộ tại node của KN, các biến kiểu frontal có thể đi cùng Wave qua các node khác nhau trong mạng. Cả 2 loại biến này đều là tạm thời. 9 Biến Nodal: các biến loại này được khai báo bắt đầu bằng ký tự N 9 Biến Frontal: các biến loại này được khai báo bắt đầu bằng ký tự F 3. 5. 2 Environment variables Biến môi trường có những định danh và ý nghĩa khác nhau: 9 CONTENT (C): chứa content của Node hiện thời. Giá trị của C luôn là string, việc thay đổi nội dung của C có thể được gán trực tiếp bằng giá trị nào đó hoặc NONE – xóa Node cùng với các Link liên kết với nó. 9 ADDRESS (A): địa chỉ của Node hiện thời. Luôn trả lại địa chỉ đầy đủ của Node nơi Wave đang đứng gồm định danh của Node trong máy và định danh của Node trong mạng. Đây là biến chỉ đọc. 9 PREDECESSOR (P): biến lưu địa chỉ của Node trước đó Wave đã đi qua. Nó chỉ thay đổi khi có sự di chuyển của Wave sang Node khác. 9 LINK (L): chứa content của Link vừa mới đi qua. 9 TERMINAL (T): một loại biến đặc biệt dùng để in ra giá trị tương ứng tại một đầu cuối nào đó. Ví dụ: ‐ Biến Nodal: N, Nhieu, Ntue.. ‐ Biến Frontal: Fpath, Ftemp… ‐ Biến môi trường: TERMINAL, LINK, L… 3. 6 Các hành động - ACTS 3. 6. 1 Control acts Các Act thực hiện các phép toán cơ bản bên trong move, dùng để thay đổi giá trị các biến, thay đổi trạng thái hoạt động của wave. Giá trị trả về gồm 3 loại chính sau: ‐ TRUE (2): thành công và cho phép Wave tiếp sau đó thực thi tại Node hiện thời. ‐ DONE (1): thành công nhưng không cho phép Wave thực thi tiếp tại Node hiện thời. ‐ FALSE (0): thất bại, loại bỏ Wave tại Node hiện thời. Control acts được phân loại như hop, filters, assignment, state genertator và code injection. Hop. Được thực thi bằng toán hạng #. Ta sẽ hiểu rõ hơn cách thực thi của Hop qua các Ví dụ sau: - 16 - • DIRECT # ANY, cách viết khác @#: nhảy tới tất cả các node khác trong KN trên cùng máy tính từ một node nào đó • -p#b: nhảy từ node hiện thời theo cung đi ra (-)p tới node b • ANY#ANY hay #: nhảy qua tất cả các link tới tất cả hàng xóm của một node • Và một số kiểu nhảy khác: x#ANY, ANY#x • Để nhảy sang 1 node ở máy khác ta có cấu trúc: a#b$$`IP, trong đó IP là địa chỉ IP của máy đích Filter. Các filter gồm các phép toán sau đây: ~ (thuộc về), /~ (không thuộc về), == (so sánh bằng), /= (so sánh không bằng), < (so sánh nhỏ hơn), <= (so sánh nhỏ hơn hoặc bằng), > (so sánh lớn hơn), >= (so sánh lớn hơn hoặc bằng). Giá trị trả về sẽ là TRUE hoặc FALSE. Nếu giá trị trả về là TRUE, node hiện thời sẽ trở thành một SNR và Wave tail sẽ tiếp tục phát triển từ node này. ‐ Filter ~: o Cú pháp: vector1 ~ vector2 o Chức năng: kiểm tra các phần tử của vector 1 có nằm trong vector 2 hay không ‐ Ví dụ: a;b ~ p;q;b;a sẽ trả về TRUE ‐ Filter /~: ngược lại toán tử ~ ‐ Filter ==: o Cú pháp: v1 == v2 o Chức năng: kiểm tra 2 vector có bằng nhau hay không o Ví dụ: 2;3 == 2;3 sẽ trả lại TRUE ‐ Filter /=: ngược lại với == ‐ Các filter còn lại: >,>=,<,<= có ý nghĩa toán học thông thường nhưng được thực hiện trên vector Nếu 1 filter trả lại giá trị TRUE, node hiện tại sẽ trở thành SNR, ngược lại SNR sẽ rỗng và chuỗi Wave sẽ dừng quá trình thực thi. Assignment. Toán tử gán = sẽ gán giá trị của toán hạng bên phải vào toán hạng bên trái. Dữ liệu bên phải có thể là giá trị số, string, biến, vector. Phép gán luôn trả lại kết quả là TRUE. Ví dụ: Na=1, Na=1;2;3, Na=Nb;2;3;Fc State Generator. Các trạng thái trả về ở trên đều xảy ra sau một quá trình thực thi nào đó. Đôi khi ta muốn trực tiếp xác định trạng thái kết quả trả về để điều khiển luồng chương trình, có một cách khác để thực hiện đó là dùng State Generator gồm 4 trạng thái: TRUE, DONE, FALSE, ABORT. Cú pháp gồm tên trạng thái, theo sau là dấu ! Ví dụ: w1.TRUE!.w2 Trong Ví dụ này w2 sẽ tiếp tục thực hiện - 17 - w1.DONE.w2 hoặc w1.!.w2 sẽ dừng sau khi thực hiện xong w1 Code Injection. Cú pháp ^Func, trong đó Func là một chuỗi Wave. Phép chèn mã này sẽ bổ sung thêm vào chuỗi Wave một chuỗi nằm trong biến sau ^. Phép này hay được sử dụng khi gọi chương trình con Ví dụ: Ft={Fa=1;2;3}. Fa+1. ^Ft.T=Fa 3. 6. 2 Fusion acts: Các phép toán hợp nhất Các phép toán số học. Bao gồm các phép toán +, -, *, /. Nếu thực hiện chia cho 0, kết quả trả về là FALSE Ví dụ: ‐ `124.36’ + 100 có kết quả: `224.36’ ‐ 66;4;24 – 1;1;1;1;1;1;1 có kết quả: 65;3;23;-1;-1;-1;-1 ‐ 1;2;3;4;5 * 1;1;1 có kết quả: 1;2;3;0;0 ‐ 2;3;4 / 1;2 có kết quả: FALSE ‐ NONE * sẽ trả lại rỗng Các phép toán trên Vector đặc biệt. Gồm 1 số phép toán sau: ‐ &: append, nối 1 Vector vào sau 1 Vector khác o Ví dụ: v1 & v2 – v1, v2 là 2 Vector ‐ Toán tử hai chấm (:) : lấy giá trị tại 1 vị trí của Vector o Ví dụ: Fa=3;2;3. Fa:1 sẽ trả lại 3 ‐ Toán tử (::): o Ví dụ: Fa=3;2;3. Fa::3 = 10. Kết quả Fa = 10;2;10 ‐ |: splits, chia string ở toán hạng bên trái thành 1 Vector các string con bởi dấu phân cách ở toán hạng bên phải o Ví dụ: `a+b+c’ | `+’ sẽ trả lại a;b;c ‐ %: join, ngược lại với | tức nó sẽ hợp các Vector con lại thành 1 string với phân cách là toán hạng bên phải o Ví dụ: a;b;c % `+’ sẽ trả lại a+b+c Gọi hàm bên ngoài (External calls). Thực hiện qua toán tử ?, gọi một hàm nào đó của hệ thống với đầu vào là các tham số từ Wave truyền vào Ví dụ: 50?`sleep’ sẽ dừng chương trình 50 giây 3. 7 Rules – Các luật trong Wave Wave có thể phát triển độc lập, dị bộ và được xử lý song song trong không gian phân tán. Tuy nhiên điểm mạnh của Wave là nó có hệ thống các RULE để quản lý và đồng bộ các các hành động. RULE thiết lập các ràng buộc trong việc lan tỏa chuỗi Wave. Thông qua RULE, hệ thống có thể thực thi nhiều lần một Wave, hay tiếp tục lan tỏa Wave nếu thỏa mãn một điều kiện nào đó, hoặc có thể chấm dứt toàn bộ wave. - 18 - RULE thường “treo” phần còn lại của chuỗi Wave (remainder) và lan tỏa nó ra chỉ khi chuỗi Wave nằm trong luật thực thi xong và trả lại trạng thái TRUE. Các Luật Rẽ Nhánh • SEQUENCE(SQ): kích hoạt tất cả các nhánh một cách tuần tự mà không cần quan tâm tới trạng thái kết quả trả về. SNR trên SQ là tập các SNR từ các nhánh con. Ví dụ: SQ(Fa=1, Fa+1).T=Fa sẽ tạo ra 2 nhánh Fa=1 và Fa+1, thực hiện tuần tự 2 nhánh này. Kết quả cuối là 2 • OS_SEQUENCE: kích hoạt tất cả các nhánh tuần tự cho tới khi nó nhận được kết quả TRUE hoặc DONE trả về từ một nhánh nào đó Ví dụ: OS(Fa=5.Fa>1, T=Fa) tạo ra 2 nhánh Fa=5.Fa>1 và T=Fa và thực hiện tuần tự. Nhưng do nhánh thứ nhất trả về TRUE nên không thực hiện tiếp nhánh thứ 2 • AND_SEQUENCE(AS): tương tự SQ nếu tất cả các nhánh đều trả về TRUE hoặc DONE, nếu 1 nhánh FALSE, trạng thái toàn bộ AS sẽ là FALSE Ví dụ: AS(TRUE!, FALSE!) sẽ trả lại FALSE • OR_PARALLEL(OP): kích hoạt các nhánh và thực thi chúng song song, nếu 1 nhánh trả về TRUE hoặc DONE, OP sẽ nhận TRUE. Nếu không nhánh nào trả về TRUE hoặc DONE, OP sẽ FALSE Ví dụ: OP(FALSE!, FALSE!, TRUE!) sẽ trả lại TRUE • AND_PARALLEL(AP): như AS nhưng các nhánh thực thi song song Ví dụ: AP(TRUE!, TRUE!, FALSE!) sẽ trả lại FALSE • RANDOM(RN): chọn một nhánh ngẫu nhiên để phát triển tiếp Repetition Luật REPEAT với khả năng vòng lặp cho phép chia Wave thành các phần nhỏ hơn khi di chuyển trong KN. Nếu kết quả trạng thái trả về là TRUE hoặc FALSE (SNR không rỗng) thì mỗi thành phần này sẽ được ghép thêm Tail của Wave. Lúc này, ở tất cả SNR Node đều chứa biến Frontal (biến này được mang tới từ các Node). Nếu kết quả trạng thái trả về là DONE (SNR không rỗng) thì Tail của Wave sẽ bị loại bỏ. Ví dụ: F = 1; 9; 5; 6; 7; 8; 12. REPEAT ( Fi +1. F : Fi /= NONE. N + ( F: Fi)). TERMINAL =N. Create - 19 - Luật CREATE(CR) cho phép Wave có khả năng mở rộng chính mạng KN trong khi lan tỏa trong không gian. Chuỗi Wave chứa luật này vẫn phát triển như thông thường, chỉ có các bước nhảy là bị ảnh hưởng - có thể thay đổi chế độ của chúng từ chế độ lan tỏa (navigation) sang chế độ tạo mới (creation). Khi đó các node và link nếu chưa có sẽ được tạo ra. Có rất nhiều chi tiết quan trọng trong ngữ nghĩa của luật CR. Nếu node của 1 bước nhảy tương ứng bằng địa chỉ của nó – điều này có nghĩa node đó đã tồn tại, tức các thành phần trong luật CR nếu chưa có sẽ được tạo ra, còn nếu đã tồn tại thì quá trình CR sẽ không tạo ra node hoặc link mới. Ví dụ: CR(@#a.+p#b.+q$$c`192.168.1.10’) Ý nghĩa: nhảy trực tiếp tới node a mặc dù node a chưa có nhưng do nằm trong luật CR nên node a sẽ được tạo ra, sau đó tạo ra link có hướng +p tới node b, tạo node c và link +q nối từ a đến c trên máy 192.168.1.10 Release Luật RL sẽ khởi tạo một Wave mới độc lập với chuỗi Wave ban đầu, mã của Wave mới này là phần nằm trong dấu ngoặc của RL, WE của Wave mới chính là WE của Wave ban đầu. Wave mới được tạo ra được đưa vào Wave Queue để chờ xử lý. Phần remainder của Wave ban đầu sẽ tiếp tục được thực hiện như bình thường. Ví dụ: w1.RL(w2).w3 Ý nghĩa: sau khi thực thi xong w1, gặp RL chương trình Wave sẽ tách w2 cùng với biến môi trường thành Wave mới cho vào hàng đợi xử lý, chuỗi Wave tiếp tục thực thi là w3 cùng với biến môi trường của nó. 3. 8 Wave và mô hình lập trình truyền thống 3. 8. 1 Sơ đồ luồng (SD) Wave là ngôn ngữ có khả năng xử lý cấu trúc dữ liệu không gian phân tán lớn. Một thuộc tính quan trọng của Wave là các chương trình điều khiển luôn được liên kết với vị trí nào đó trong không gian dữ liệu (trong khi dữ liệu giữa các Node lan tỏa, hay giữa các SNR lan tỏa). Dữ liệu của cùng một Node có thể xuất hiện ở những nơi khác nhau trong cùng một SNR ở cùng một không gian cục bộ. - 20 - Hình 3-2: Thành phần của Spread Diagrams Các kiểu module của Spread Diagram là • SNR • Move • Rule • Halt • Các thành phần liên quan o Link o Biến Spatial 3. 8. 2 Wave và mô hình lập trình song song Wave biểu diễn theo SD trong mạng dữ liệu có thể được điều khiển hoàn toàn bởi Rule. Các thành phần của chuỗi Wave tự tách thành các nhánh trước và trong quá trình thực thi. Ví dụ: Tách chuỗi Wave m1, m2 , m3. m4, m5 Æ (m1. m4, m5), (m2. m4, m5 ), (m3. m4, m5) - 21 - Hình 3-3: Tự động tách trong chuỗi Wave Ngoài ra, trong quá trình Wave thực thi, các thành phần của nó có thể được sao chép và thay thế mà dữ liệu không bị thay đổi (Như trong Hình 3-4: m2 được sao chép và thay thế mà dữ liệu vẫn được giữ nguyên) m1. m2. m3 Æ m1. m2, m2, m2. m3 Æ m1.(m2. (m3, m3, m3)), (m2. (m3, m3, m3)), (m2. (m3, m3, m3)) Hình 3-4: Một số trường hợp xử lý song song Ở một ví dụ khác ta thấy rõ hơn Rule điều khiển chuỗi Wave như thế nào (Hình 3-5). - 22 - Hình 3-5: Wave xử lý song song có kèm theo Rule m1. OR_PARALLEL (m2, m3. m4). m5 Æ m1. OR_PARALLEL((m2, m4), (m3. m4)) .m5 Æ m1. OR_PARALLEL((m2. m4, m4, m4), ( m3. m4, m4, m4) ). m5 3. 8. 3 Wave và mô hình lập trình tuần tự Việc cho phép phát triển không gian, xử lý song song và tự động trong môi trường phân tán, Wave có thể dễ dàng mô hình hóa một số chương trình xử lý tuần tự. Giống các chương trình bình thương, truyền thống ở cùng một máy tính, Wave phải ở cùng một điểm trong không gian và chỉ có duy nhất một luồng được xử lý. Chúng ta sẽ bàn về vấn đề này thông qua các ví dụ ở dưới đây. Ví dụ 1 s1. s2. s3. s4 Ví dụ 2 SEQUENCE (s1, s2, s3, s4) Hai ví dụ trên được thể hiện ở Hình 3-6 - 23 - Hình 3-6: Xử lý tuần tự không Rule và có Rule Ngoài ra có thể ví dụ ở Hình 3-7 s1. SQ ((s2. s3), s4) và SQ (s1, (s2. SQ (s3, s4))) Hình 3-7: Wave xử lý tuần tự có Rule • Biều thức If-else Biểu thức điều kiện “If- else” trong mô hình lập trình tuần tự có cú pháp như sau: If (e) s1 else s2 Mệnh đề s1 thực hiện và trả về kết quả đúng thì mệnh đề s2 sẽ được thực thi. Ở Hình 3-8: một số trường hợp với mệnh đề If – else: OR_SEQUENTIAL (( e. s1), s2) - 24 - và OR_ SEQUENTIAL (AND_SEQUENTIAL ( (e. DONE ! ) , s1). s2) Hình 3-8: một số trường hợp với mệnh đề If – else Hình 3-9: Một số trường hợp với mệnh đề If – else • Lựa chọn nhiều nhánh o If – else với filter - 25 - Hình 3-10: else – if với filter o Else – if parallel Hình 3-11: Else – if parallel o Else – if với Rule - 26 - Hình 3-12: Else – if với Rule o Switch Hình 3-13: Switch • Vòng lặp o while ( e ) s o do s while ( e ) o For (e1 ; e2 ; e3) s - 27 - Hình 3-14: Câu lệnh lặp sử dụng Repetition Hình 3-15: Câu lệnh lặp sử dụng Recursion - 28 - CHƯƠNG 4. XÂY DỰNG BỘ INTERPRETER Trong chương này chúng ta bàn tới thuật toán và kỹ thuật trong việc xử lý tuần tự hoặc song song của Wave trong hệ thống mạng máy tính. Sau đó chúng ta sẽ trình bày tiếp về cấu trúc chính trong bộ biên dịch và các hàm đơn vị điều khiển trên cấu trúc đó, cũng như việc thực hiện chúng ở từng giai đoạn khác nhau. Tất cả các thông tin được trình bày trong chương này coi như việc mô tả một khuôn mẫu của hệ thống Wave ảo, một kiểu điều khiển tự động trong không gian như: xử lý, mô phỏng hay điểu khiển trong những hệ thống lớn và mở. 4. 1 Wave không có Rule Các chuỗi Wave được thông dịch từng bước lần lượt từ trái qua phải, ở các giai đoạn khác nhau. Trong tất cả các giai đoạn thực thi, Wave luôn được gắn kết với Node nằm ở KN. Sau khi việc xử lý của Head, Tail của Wave vẫn tiếp tục được hoạt động trong cùng một Node hoặc Node khác. Những lúc như thế, Head cũng được sao chép chương trình điều khiển kèm theo ở cùng Node đó hoặc Node khác. 4. 1. 1 Chi tiết ví dụ về các bước của Wave Chú ý: Simple move: là 1 Head mà Head này không thể tách được thành Head đơn giản hơn (không có dấu phảy trong Simple move). Để hiểu rõ hơn về các thực hiện của Wave không đi kèm với Rule , ta xét một ví dụ đơn giản khi thực hiện ở Node b hiện tại: F = 3. r # a, (s # ANY. T # z ), STAY. N+F. TERMINAL = CONTENT. Hay viết ngắn gọn: F = 3. r # a, (s # ANY. T # z ),. N+F.T = C. Ở các bước thực hiện khác nhau trong ví dụ trên, nếu Head của Wave không phải là Simple move thì các Head này sẽ được tách ra thành các Simple move (các Simple move cách nhau bởi các dấu phảy). Sau khi Head được xử lý thành các thành phần nhỏ hơn (cách nhau bởi dấu phẩy), Tail của Wave sẽ được gửi tới Node tương ứng trong trường hợp thành phần đó là Simple move hoặc Tail được sao chép và gắn với Wave mà Head của Wave này là kết quả của một thành phần được chia ở Head trong Wave trước. Do đó Wave mới luôn được xử lý độc lập. Trong trường hợp rất nhiều Wave được xử lý cùng một lúc, chúng sẽ được cho vào trong Wave Queue để chờ xử lý. Ta phân tích lần lượt các bước thực hiện ở ví dụ trên 1. Bước 1 Head của Wave là: F=3 Và Tail r # a, (s # ANY. T # z ), N+F. TERMINAL = CONTENT 2. Bước 2 - 29 - Biến Frontal F đã được tạo gắn với Wave Tail cho vào cùng hàng đợi 3. Bước 3 Head của Wave là: r # a, (s # ANY. T # z ), STAY Và Tail N+F.TERMINAL = CONTENT Với việc tách biến Frontal đi rồi, Head của Wave mới không thể thực thi 1 cách trực tiếp mà là sự kết hợp lại từ 3 nhánh (mà mỗi nhánh cách nhau bởi 1 dấu phẩy). Do đó chuỗi Wave ban đầu sẽ được tách thành 3 Wave con là 9 Wave 1: r # a. N+F.TERMINAL = CONTENT 9 Wave 2: s # ANY. T # z. N+F.TERMINAL = CONTENT 9 Wave 3: N+F.TERMINAL = CONTENT Sau đó, biến Frontal F sẽ được ghép và xuất hiện ở 3 chuỗi Wave con, chúng sẽ được để vào trong hàng đợi Wave Queue 4. Bước 4 Wave Queue làm việc theo cơ chế: Chuỗi Wave nào vào trước thì được thực hiện trước. Do đó Wave1 sẽ được thực hiện trước Wave2 và Wave 3, được tách có Head là r# a và Tail: N+F.TERMINAL = CONTENT với biến Frontal đang được tách ra. Nhìn vào Head của Wave sau khi được tách ta thấy Head lúc này đã là 1 simple move và có thể được thực thi 1 cách trực tiếp (mà không qua vòng lặp tách Head cho tới khi là simple move). Hop thực thi từ Node hiện tại b qua Link r tới Node a (Node a được chứa trên máy tính khác). Tail cùng với biến Frontal F được gửi tới Node a và cho vào hàng đợi Wave Queue của máy tính đang chứa Node a này. Ở Node b tiếp tục thực thi chuỗi Wave 2 5. Bước 5 Head của Wave 2 là s # ANY và Tail t # z . N+F.TERMINAL = CONTENT biến Frontal được tách ra. Hop trong Head sẽ được thực thi và gửi tới tất cả các Node liền kề qua Link s (trong lúc gửi, Tail cũng được gửi cùng). Tất cả các Wave mới đều được kích hoạt trong hàng đợi ở máy tính chứa Node của Wave đó. Wave Queue chỉ lưu lại các simple move. 6. Bước 6 - 30 - N+F.TERMINAL = CONTENT ở đây biến N=7 (cho trước) và F = 3 và CONTENT là b, lúc này ta có TERMINAL là: b 4. 1. 2 Thuật toán tổng quát cho Wave không có Rule Như trong ví dự ở trên, công việc của trình biên dịch Wave trong mỗi máy có thể được miêu tả bằng thuật toán tổng quát. Vòng lặp: 1. Lấy Wave từ Wave Queue và tách biến môi trường ra. 2. Bỏ tất các dấu ngoặc đơn ở toàn bộ chuỗi Wave. 3. Phân tích chuỗi Wave thành 2 thành phần: Head và Tail 4. Bỏ tất cả dấu ngoặc đơn ở toàn bộ phần Head 5. Nếu Head là Simple move. a. Dừng Tail tạm thời b. Tất cả các công việc thực hiện trên move này sử dụng Frontal, Nodal và biến môi trường . Các trường hợp có thể xảy ra: i. Biến mới Nodal hoặc Frontal được tạo nếu thành phần chưa có biến . ii. Nếu trong chuỗi Wave có câu lệnh CREATE ở ngoài, một trong số act có thể được nhảy tới Node khác. Trong trường hợp này Hop sẽ trả lại Link mới hoặc Node mới. iii. Head có thể xóa Node hiện tại hoặc Link tới Node hiện tại bới việc gán CONTENT và LINK bằng NONE. Xóa bỏ tất cả các Node hiện tại bằng cách xóa các Link liên kết tới Node đó. c. Gửi các Tail của Wave, kèm theo biến Frontal tới Wave Queue ở trên tất cả các SNR Trong trường hợp khác d. Phân tích Head của Wave thành các thành phần riêng (các thành phần này cách nhau bởi dấu phẩy). Nếu mỗi thành phần riêng này vẫn còn các thành phần trong nó nhỏ hơn và cách nhau bởi dấu phẩy, thì công việc tách được tiếp tục cho tới khi các thành phần nhỏ trở thành Simple move. e. Thay thế và gắn Tail vào mỗi thành phần được chia ở trên. Do đó Wave mới sẽ nhận được các Tail này. f. Đưa các chuỗi Wave thu được, kèm theo biến Frontal, tới hàng đợi Wave Queue của máy tính hiện tại. - 31 - 4. 2 Wave có Rule Trong phần này chúng ta nói về Wave có Rule và xét các trường hợp khác nhau của Wave. Cũng giống như phần trước, đầu tiên ta lấy ví dụ về Wave có Rule sau đó ta sẽ đưa ra thuật toán chi tiết cho mỗi trường hợp. 4. 2. 1 Ví dụ về Wave có Rule Xét ví dụ sau: AND_PARALLEL ( OR_SEQUENTIAL ( w1, w2 ), ( OR_PARALLEL ( w3, w4, w5 ) .w6) ) . w7 Có thể viết ngắn gọn như sau: AP ( w1, w2) , (OP ( w3, w4, w5 ). w6). w7 Trong hình vẽ, w1, w2... w7 cùng với các Rule được thể hiện chi tiết qua từng bước. Ở các hình oval, bên trái tương ứng với tên của Rule, bên phải là Tail của Wave tương ứng với Rule đó. Hướng đi và sự di chuyển của w1, w2…w7 được chỉ rõ bởi các mũi tên. Hình 4-1: Wave có Rule - 32 - SNR thể hiện bởi các đường kẻ ngang. Tuy nhiên ở hình vẽ này thì việc duy chuyển của các biến Frontal chúng tôi không đưa ra. Việc xử lý ở chi tiết các bước như sau: 1. Bước 1 Luật AND_PARALLEL ở ngoài cùng thực thi, Head của Wave ban đầu tách thành: OR_SEQUENTIAL (w1, w2) Và (OR_PARALLEL (w3, w4, w5). w6) cho vào hàng đợi Wave Queue. Tail của Wave là w7 nằm ở máy tính hiện tại và vẫn kết nối với Rule AND_PARALEEL . Biến Frontal của Wave được tách ra. 2. Bước 2 Hai thành phần nằm trong Wave Queue ở bước 1 là: OR_SEQUENTIAL (w1, w2) và (OR_PARALLEL (w3, w4, w5). w6 được lấy ra, xử lý. Dấu mở, đóng ngoặc trong mỗi Rule bị loại bỏ. ‐ Đầu tiên ta xử lý OR_SEQUENTIAL (w1, w2), luật này có 2 thành phần là w1 và w2. Ở máy tính hiện tại, w1 sẽ được kích hoạt và cho vào Wave Queue. Biến Frontal sau khi được tách từ Wave sẽ được ghép vào. Thành phần thứ 2- w2 tạm dừng lại trong máy hiện tại. ‐ Đến lượt (OR_PARALLEL (w3, w4, w5). w6, luật này có Tail là w6. W6 tạm dừng lại trong máy hiện tại nhưng vẫn tiếp tục kết nối với luật OR_PARALLEL. W3, w4, w5 là ba thành phần song song, sau khi được tách riêng và kèm theo biến Frontal sẽ được kích hoạt rồi cho vào Wave Queue. 3. Bước 3 W1, w3, w4 và w5 sau khi được kích hoạt sẽ phát triển song song và độc lập trong KN. Giả thuyết rằng, trong kết quả của w3, w4 và w5 có ít nhất một kết quả trả về là TRUE. Khi đó kết quả của SNR1 sẽ trả lại TRUE, vì thế w6 sẽ được gửi tới SNR1 và được kích hoạt sau đó cho vào trong hàng đợi trên máy tính có chứa các Node SNR1. Tất nhiên, chúng có gắn các biến Frontal đi cùng. Sau khi gửi w6 tới SNR1, luật OP sẽ không rằng buộc nó với tất cả các Wave được sao chép từ w6. Trong khi đó, Wave w1 có thể đã hoàn thành hoặc có thể tiếp tục công việc của mình. 4. Bước 4 Sau khi được lấy ra từ Wave Queue tương ứng ,w6 phát triển độc lập trên tất cả các Node ở SNR1, lúc này w1 vẫn đang làm việc song song với các Wave bản sao của w6. Sau khi w1 kết thúc (giả thiết w1 kết thúc, w2 sẽ được giữ lại bởi luật OS vì coi như w1 trả lại kết quả TRUE) và các Wave bản sao của w6 cũng kết thúc (nếu không giả thiết, trên thực tế nó có thể kết thúc hoặc không). Lúc này, SNR2 được thành lập. - 33 - Từ tất cả các Node ở SNR2, w7 mà đã kết hợp với các luật AP được kích hoạt và chỉ định sẽ cho vào Wave Queue trên máy tính hiện tại. Sau đó nó ghép với các biến Frontal mang tới từ Node trên SNR2 bởi thành phần 1 và thành phần 2 ban đầu của luật AP. Ứng dụng của w7, khả năng cung cấp sự đồng bộ hóa cục bộ của rất nhiều hệ xử lý phân tán được liên kết với nhau từ nhiều Rule khác nhau (OS, OP…). Luật AP, sau khi gửi Tail của w7 tới SNR2 không rằng buộc của nó với các Wave được sao chép từ w7. Sau đó chúng kết thúc quá trình hoạt động. 5. Bước 5 Wave w7 không phụ thuộc vào các Node của SNR2, sau đó được đặt tại các Node của SNR3. Vì vậy ta thấy Wave w1,w2…w7 có thể được đặt ở các vị trí khác nhau trong cấu trúc và có thể được duy trì chúng cùng với Rule như đã miêu tả ở trên. 4. 2. 2 Thuật toán tổng quát cho Wave có Rule Phần trên chúng ta lấy một ví dụ về Wave có Rule nhưng chưa tách biệt và chi tiết. Trong phần này chúng ta sẽ đi sâu hơn về các thuật toán của những Rule khác nhau. Branching Rules Nếu các Head của Wave có nhiều nhánh (branching rule): 1. Phân tích Head Wave thành nhiều nhánh con, sau đó gắn các biến Frontal và Tail vào các thành phần đó. a. Kích hoạt các nhánh nhận được (tuần tự hoặc song song, phụ thuộc vào kiểu của Rule) bằng việc đưa chúng vào Wave Queue . b. Đợi kết quả trả về từ các nhánh và đưa ra quyết định xử lý. c. Kết hợp và xử lý các kết quả cuối cùng của các nhánh để đưa ra trạng thái kết quả của mỗi Rule, và tổng hợp các kết quả ở các nhánh khác nhau trên SNR, để suy ra được kết quả SNR trên Rule đó. 2. Nếu kết quả trả về của Rule là TRUE: a. Gửi Tail của chương trình tới tất cả các Node trên SNR (đã ghép thêm tất cả các biến Frontal của Node đó) bằng các nhánh của Wave, vì thế ta sẽ nhận được các Wave mới. b. Kích hoạt các Wave mới độc lập này trong tất cả các Node SNR (bằng việc đưa chúng vào Wave Queue). c. Kết quả cuối cùng được kích hoạt trong khi quyền điều khiển của nó được lan tỏa trên khắp các Tail của Wave. Quyền điều khiển này được gửi tới SNR Node. Trong trường hợp kết quả là DONE hoặc FALSE d. Kết quả trả về cuối cùng của Rule có thể DONE hoặc FALSE - 34 - Repetition: Nếu Head của Wave được dùng bởi luật REPEAT: 1. Tạm dừng chuỗi Wave. 2. Tách biến Frontal từ Wave. 3. Với luật khác nhau ta tách được các chuỗi Wave từ Head của Wave ban đầu. 4. Ghép các biến Frontal được lấy ra từ Wave, từ đó nhận được Wave mới 5. Kích hoạt Wave mới và cho vào hàng đợi trong máy tính hiện tại và đợi kết quả cuối cùng trả về (nơi mà Wave có thể lan rộng ra các máy khác). 6. Nếu kết quả cuối cùng trả về có trạng thái là TRUE: a. Sao chép và gửi tất cả các chuỗi Wave (mà bị trì hoãn ở bước 1) tới tất cả các Node SNR (có thể trong cùng máy hoặc khác máy). b. Ghép chuỗi Wave này trong SRN Node với các biến Frontal được lấy ra từ Node tương ứng. c. Kích hoặc các Wave mới nhận được trong mỗi SNR Node bằng việc đưa chúng vào hàng đợi của máy tính đang chứa Node này. d. Đưa quyền điều khiển vào các Wave đã được kích hoạt và kết quả cuối cùng của Rule trả về từ Node hiện tại. Trong trường hợp khác e. Tách các Tail của Wave và ghép các biến Frontal được lấy từ Node hiện tại với chúng f. Kích hoạt Wave mới trong Node hiện tại bằng cách đưa chúng vào trong hàng đợi Wait Nếu Head của Wave được dùng bởi luật WAIT: 1. Tách các biến Frontal từ Wave. 2. Lây chuỗi Wave từ Head và tạm dừng Tail. 3. Ghép các biến Frontal vào Wave (Wave này lấy từ Head) Æ ta nhận được Wave mới). 4. Kích hoạt Wave mới bằng cách cho chúng vào hàng đợi trong máy tính hiện tại và đợi kết quả trả về. 5. Nếu một số nhánh của Wave trả về với trạng thái kết quả là ABORT: a. Kích hoạt ngay kết quả trả về từ các thành Tail của Rule-controlled. b. Cài đặt trạng thái trả về trên Rule là FALSE. c. Nếu kết quả trả về có trạng thái là TRUE: - 35 - d. Thay thế và gửi Tail của Wave tới tất cả các Node SNR được nhận từ Head. e. Ghép Tail của Wave trong SNR Node với biến Frontal được lấy từ Node này. f. Kích hoạt Wave mới nhận được trong mỗi SNR Node bằng cách cho chúng vào hàng đợi của máy tính mà chứa SNR Node đó. g. Đưa quyền điều khiển vào các Wave đã được kích hoạt và kết quả cuối cùng của Rule trong Node hiện tại. Trong trường hợp trạng thái trả về DONE hoặc FALSE h. Trạng thái trả về của Rule là DONE hoặc FALSE nếu Tail của Wave bị mất. Indivisible Nếu Head của Wave được sử dụng bởi luật INDIVISIBLE: 1. Tách biến Frontal từ Wave 2. Lấy Wave từ Head và tạm dừng Tail của Wave. 3. Khóa Node hiện tại từ 1 Node khác. 4. Gắn biến Frontal, và đợi kết quả trả về. 5. Mở khóa cho Node hiện tại để sử dụng bới Wave khác. 6. Gửi Wave tới SNR Node, và gắn biến Frontal bởi Head của Wave. 7. Kích hoạt các Wave nhận được trong tất cả SNR Node bằng cách cho chúng vào hàng đợi. 8. Đưa quyền điều khiển tới Wave trong SNR. Create Nếu Head của Wave được sử dụng bởi luật CREATE: 1. Tách biền Frontal từ Wave 2. Lấy Wave từ Head và cho tạm dừng phần Tail của Wave. 3. Cung cấp trạng thái lan tỏa “Create”. 4. Kích hoạt Head của Wave bằng cách cho vào trong hàng đợi ở máy tính hiện tại. Ở đây Head có thể tạo ra Node mới, Link mới và đợi kết quả trả về. 5. Phân chia Tail của Wave thành các trạng thái như: create, navigation… 6. Gửi Tail của Wave tới tất cả các SNR Node. Sau đó gắn thêm các biến Frontal (được lấy từ các Node này). Kích hoạt Wave mới bằng cách cho vào hàng đợi. - 36 - 4. 3 Hệ thống Track Hệ thống điều khiển của Track có thể tự nhân bản, sao chép hoặc được tạo trong suốt quá trình Wave thực thi và di chuyển. Tín hiệu echo sẽ được trả lại cho các Track này. Hệ thống Track này được coi như là hệ thống cốt lõi trong việc điều khiển của ngôn ngữ Wave. Nó có khả năng tự tạo ra các “cây Track” tương ứng mỗi lần Wave được lan tỏa và thực thi. Track tổng hợp kết quả và trả lại trạng thái cuối cùng trong KN. Track cũng được xem như là “cây cấu trúc” tự động và lan tỏa trong KN hay giữa các máy tính. Track không tự động xuất hiện khi Wave trả về kết quả cuối cùng. Track chỉ phản ánh sự kiện quan trọng duy nhất khi mà nó cần cho việc điều khiển phân phối. Track Node luôn liên kết với mỗi KN Node. Một hoặc nhiều Track Node có thể liên kết tới cùng một KN Node. Mỗi một Track Link tương ứng với một KN Link; chúng có thể phản ánh “direct hop” giữa các KN Node hoặc nhảy tới các nhánh điều khiển khác nhau được chia ra bởi Rule. 4. 3. 1 Rule dựa trên bộ điều khiển Track Bây giờ chúng ta bàn đến vai trò của Track trong Wave (Wave này được bao bọc bởi Rule). Rule luôn luôn liên kết chặt chẽ với Track Node. Tail (remaider) của Wave cũng liên kết với Node này. Wave (có Rule) lan truyền qua KN. KN lúc này chứa các biến Frontal của Wave và được cấu tạo từ các Hop hoặc các nhánh khác nhau (các nhánh này được tạo bảo Wave mới, Wave này lại có sự gắn kết với các Wave bố mẹ nó). Trong suốt quá trình phát triển của Wave, biến Nodal mới có thể được tạo và sẽ được gắn kết với Track Node hiện tại. Việc tạo Track luôn kèm theo sự di chuyển, định hướng của Wave trong không gian mạng phân tán được thể hiện ở Hình 3-2: Tạo track trong quá trình Wave thực thi và lan tỏa. Exploratory Wave1 Wave2 Wave2 N N Rule Rest of wave Track Links Track Node liên kết với KN Biến Nodal Hình 4-2: Tạo track trong quá trình Wave thực thi và lan tỏa - 37 - Khi sự lan tỏa của Wave kết thúc, hoặc ngừng lại, phần cuối của Track Node sẽ được giữ trong trạng thái tương ứng và kết nối với biến Frontal (Hình 3-3: Trạng thái và biến frontal) Từ các Node cuối (fringe - lá) của Track Node, những tin nhắn “Echo” được tạo ra bởi kết quả trạng thái cuối cùng tương ứng sẽ được truyền lại thông qua Track. Echo khác nhau sẽ mang các biến trạng thái khác nhau. Kết quả cuối cùng trong mỗi Track Node chính là kết quả lớn nhất được trả về từ các Node con của nó. Biến kết quả này sẽ được gửi tới các Node cha của Node hiện tại trong “cây Track“. Rule Rest of wave Resulting state on the rule N 2 2 2 2 2 2 2 2 2 N 2 2 1 2 0 2 0 FV FV 0 Special track Nodes holding nodal variables Merging states in track Nodes Echoes with states Removing tracks N Rule Rest of wave Biến frontal N FV FV FV FV FV FV 0 0 2 2 1 0 Hình 4-3: Trạng thái và biến frontal Hình 4-4: Gửi echo và tổng hợp các kết quả trạng thái, sau đó loại các Track Link, Track Node thừa - 38 - Sau khi kết quả echo trả về Node cha. Nếu kết quả trả về trong Track Node là 0 hoặc 1 (FALSE hoặc DONE) thì Track Node này và Link liên kết tới Node cha của nó sẽ bị xóa. Tuy nhiên, trong trường hợp Track Node được liên kết với biến Nodal thì nó sẽ không bị ảnh hưởng gì (vẫn được giữ nguyên). Các Track Node khác mà có kết quả trả về là TRUE và có liên kết với biến Nodal sẽ tiếp tục giữ các biến Nodal và phân phối Wave (thể hiện ở Hình 3-4: Gửi echo và tổng hợp các kết quả trạng thái, sau đó loại các Track Link, Track Node thừa). Tail trong “Cây Track” bây giờ sẽ phục vụ như là một cơ sở hạ tầng phân tán đặc biệt. Tail sẽ được gửi tới các Track Node ngoài cùng (Node lá). Trên thực tế SNR sẽ được nhận do Rule liên kết với cây Track Node. Sau khi tất cả các Track Node con nhận được Tail của Wave, Rule sẽ tự kết thúc ở Node. Tiếp theo Rule sẽ được chuyển tiếp tới các Node con của Node nó vừa kết thúc (Hình 3-5: Truyền Tail tới các Track Node ngoài cùng (Node lá)) Tail của Wave sẽ được chuyển tới các Node lá, nó sẽ phát triển độc lập và tự động ở tất cả SNR Node. Ví dụ như: Wave3, Wave4 trong Hình 3-6: Kích hoạt Tail trong các Node lá. Wave routing tracks Variables binding tracks N Rule N FV Rest of wave Rest of wave Termination of the rule’s influence Rest of wave propagation FV S N R Hình 4-5: Truyền Tail tới các Track Node ngoài cùng (Node lá) - 39 - 4. 3. 2 Thuật toán cho Bộ xử lý track Thuật toán xử lý Track chủ yếu gồm: • Lan tỏa Exploratory Wave • Quảng bá Echoes • Phân bổ Tail tới Node qua Track Quảng bá các chuỗi Wave Việc liên kết trong những bước phát triển của wave kèm theo Track được miêu tả bằng thuật toán sau: Nếu Wave có trong hệ thống phân tán và có trạng thái Track, hoặcWave này nhảy từ một Node ở máy hiện tại sang một máy tính khác. 1. Tạo Track Node mới 2. Kết nối Track Node mới vừa tạo với KN Node 3. Tăng biến đếm (vì có thêm Track Node con) trong Track Node cha 4. Liên kết Wave hiện và biền Frontal với Track Node mới Quảng bá Echo thông qua Tracks 1. Nếu Echo có kết quả là ABORT a. Gửi Echo này tới tất cả các Node liền kề với Node hiện tại (cả Node con lẫn Node cha). b. Sau khi kết thúc thì loại bỏ các Wave, xóa hết các biến Frontal và Nodal lẫn biến đếm liên quan tới Track Node này. c. Loại bỏ Track Node hiện tại và các Link liên kết với nó N N Wave4 Development of new exploratory wave in the SNR Wave3 Hình 4-6: Kích hoạt Tail trong các Node lá - 40 - 2. Nếu Echo có kết quả trả về từ Track Node con lớn hơn một kết quả đang lưu trong Track Node này: a. Thay thế trạng thái mới ở các Node 3. Giảm biến đếm các Node con trong Node 4. Nếu biến đếm bằng 0 a. Gửi trạng thái kết quả cuối cùng trong Track Node hiện tại tới Track Node cha. b. Nếu kết quả trạng thái trong Node là TRUE i. Kết thúc công việc bằng cách rời các Node này và các Link (Node và Link vẫn được giữ nguyên). c. Nếu kết quả trả về trong Node là DONE hoặc FALSE, và Node được kết nối với biến Nodal: i. Xóa bỏ tất cả các biến frontal, chuỗi wave liên quan tới track node này. Xóa bỏ track node hiện tại và các link liên kết với nó. Quảng bá Tail thông qua Tracks 1. Nhận Tail của Wave từ Track Node cha. 2. Nếu Track Node là Node lá (nằm ngoài cùng trong cây Track). a. Ghép biến Frontal (biến Frontal này được liên kết với Track Node hiện tại) với Tail của Wave. Do đó ta nhận được một Wave hoàn toàn độc lập. b. Kích hoạt chuỗi Wave mới bằng cách cho nó vào hàng đợi của trình biên dịch hiện, trong khi vẫn liên kết với SNR Node hiện tại. c. Sao chép Tail của Wave và gửi nó tới tất cả các Track Node con, trong khi đó vẫn tăng biến đếm các Track Node con ở Track Node hiện tại (khi mỗi lần Tail gửi). 4. 3. 3 Sự lan tỏa Track Nếu luật RELEASE được sử dụng thì sự lan tỏa của Wave trở nên uyển chuyển hơn. Tuy nhiên, Track sẽ tự chuyển đổi cho phù hợp nếu nó không xác định được đường đi, khi có một Rule khác ở trong Wave. Track nhận ra việc chia nhánh của Wave, tổng hợp các kết quả trả về và phân kênh cho Tail của Wave tới SNR. Sau khi Rule thực hiện xong, cây Track sẽ bị vứt bỏ, Tail của Wave sẽ chuyển tới các Node của SNR. Biến Nodal tự động xuất hiện trong KN Node sau khi Wave kết thúc và di chuyển tới Node khác trong Track model. Trên thực tế, duy nhất Track Node (không phải Link) được tạo trong Track mode, khi Wave ở trong KN. Chúng không xuất hiện khi Wave di chuyển tới Node khác, loại bỏ các biến Nodal (biến này đã được liên kết với chúng). - 41 - 4. 4 Tổng quan và kiến trúc của Wave Interpreter Wave Interpreter (WI) là tập hợp bao gồm 3 hàng đợi chữa dữ liệu và 4 thành phần xử lý thực hiện những nhiệm vụ riêng biệt: Parsing Unit để phân tích cú pháp của các chuỗi WAVE, Execution Processor xử lý tất cả các kiểu dữ liệu và các toán tử trong ngôn ngữ WAVE, Track Processor dùng trong việc quản lý các cấu trúc điều khiển phân tán và cuối cùng là Communication Processor dùng trong việc trao đổi các thông điệp giữa các WI trên các máy khác nhau. Kiến trúc tổng thể của WI được thể hiện như trong hình dưới đây. Hình 4-7. Các thành phần của Wave Interpreter Không giống với các trình biên dịch thông thường, WI không có thanh ghi đếm chương trình mà thay vào đó là hàng đợi các toán hạng được lấy ra từ wave head (thành phần đầu tiên của chuỗi wave chỉ chứa một toán hạng) sẽ được xử lý trên node hiện tại trong knowledge network (KN) và wave tail (thành phần còn lại của chuỗi wave khi bỏ đi wave head) có thể sẽ được lan truyền tới các node khác trong KN của máy hiện tại hoặc gửi tới KN của một máy khác trong mạng, hơn thế nữa chuỗi wave còn có thể được nhân bản ra và tiếp tục được xử lý một cách song song. Trạng thái của wave và dữ liệu sinh ra sẽ được lưu trong các biến mỗi trường của wave và trong các node của KN. Tiếp theo sau đây chúng tôi xin trình bày chi tiết hơn về các thành phần trong kiến trúc của Wave Interpreter. - 42 - 4. 5 Các thành phần trong Wave Interpreter 4. 5. 1 Wave và Wave Queue Wave Queue là hàng đợi chứa các Wave. Được minh họa như hình dưới đây. Wave bao gồm 2 thành phần chính là Wave String và Wave Environment. Wave String là chuỗi được viết bằng ngôn ngữ Wave, có thể xem như đoạn mã của chương trình. Wave Environment chứa các biến môi trường của wave và các biến đi cùng wave trong quá trình xử lý, lan tỏa. Trong Wave Environment chứa những thông tin sau: • NODE: chứa tên của node hiện tại trong KN • LINK: chứa tên của link vừa đi qua để đến được node hiện tại • PREDECESSOR: chứa tên của node trước đó trong KN • COLOR: để phân biệt các chuỗi wave khác nhau • FRONTAL TABLE: là một bảng chưa các biến frontal của wave • TRACK ADDRESS: địa chỉ của track trong Track forest nếu Wave đang lan tỏa trong chế độ track 4. 5. 2 Knowledge Network Knowledge Network trong WI là tập hợp của các Node và các Link nối các Node lại với nhau. Để tiện cho việc truy xuất trực tiếp tới các Node một cách nhanh chóng qua tên của Node, trong KN có cài đặt thêm bảng NAT (Node Address Translation). Node trong KN chứa các thông tin sau: • NAME: tên của node hiện tại trong KN • LINK TABLE: là một bảng chưa dánh sách các link được nối với node • COLOR TABLE: bảng chứa cách biến Nodal Variable • NAT INDEX: Vị trí của node trong bảng NAT Link trong KN bao gồm: • NAME: tên của link • SIGN: hướng của link và có 3 loại là “+”, “-” và ko có hướng • DESTINATION: địa chỉ của node đích Link trong KN được chia làm 2 phần khi liên kết giữa 2 node, mỗi node sẽ chứa một phần link đó trong bảng LINK TABLE. Ngoài ra địa chỉ của trường Wave Queue Wave String Wave Environment Wave Hìn 4-8: ave và Wave Queu - 43 - DESTINATION trong link là tập hợp của 2 địa chỉ: địa chỉ của máy chứa node mà link nối tới và địa chỉ của node đó trong bảng NAT nằm trên máy tính đó. Như trên hình vẽ ta có: node a có LINK TABLE gồm 2 phần tử là +p và r, trong khi đó node c có LINK TABLE chứa 1 phần tử là -p. 4. 5. 3 Track Forest Track Forest được quản lý bởi Track Processor, được xem là toàn bộ các Track có trong hệ thống WI. Hệ thống Track được sinh ra trong quá trình xử lý các Rule. Thành phần chính của Track Forest bao gồm các Track Node (TN) được chứa trong một bảng gọi là Track Table, Track Table chính là ánh xạ trực tiếp từ địa chỉ vào vùng nhớ chứa TN. Các TN liên kết với nhau tạo thành một cấu trúc dạng cây. Ngoài ra Track Forest còn một thành phần cấp phát địa chỉ cho TN để đảm bảo khi TN được sinh ra thì nó là duy nhất trong mạng máy tính. Địa chỉ của TN thực chất bao gồm 2 thành phần đó là: địa chỉ của máy cục bộ đang chạy WI và thành phần địa chỉ của TN trên máy cục bộ (thành phần này được cấp phát một cách tự động) Cấu trúc dữ liệu của Track Node được mô tả như sau: • TYPE: Kiểu của track dùng để phân biệt phân biệt các nhánh của track là được sinh ra từ lệnh hop hay từ các sector trong Wave. Kiểu này có thể là PROP (cho lệnh hop) hoặc là SECT (cho các sector) • ADDRESS: địa chỉ của track node khi được cấp pháp bởi Track Forest • HOST: địa chỉ của máy tính nơi Track Node được sinh ra. • PARENT: Trỏ đến TN cha. • CHILDREN: là một danh sách các TN con. • RULE: luật được áp dụng cho Track để xác định các thức xử lý khi track nhận được echo từ các track con. • ACTIVE BRANCH: vị trí của nhánh (track con) đang được phát triển. a c b Máy 2 Máy 1 p r Hình 4-9: Knowledge Network - 44 - • SUSPENDED BRANCH: là một hàng đợi các nhánh chờ được xử lý. • ECHO: giá trị tổng hợp echo khi nhận được từ các nhánh con. Echo bao gồm 4 loại là: TRUE, FALSE, DONE, ABORT. • REMAINING ECHO: số lượng echo còn lại chờ nhận được từ các nhánh con. • ENCLOSED WAVE: chuỗi wave chứa trong Rule • SUSPENDED TAIL: chỗi wave còn lại khi loại bỏ toàn bộ Rule • WAVE ENVIRONMENT: Giá trị của các biến mỗi trường wave 4. 5. 4 Parsing Unit Trong bất cứ trình biên dịch, hay thông dịch nào, thành phần parser bao giờ cũng là quan trọng nhất. Thành phần parser chịu trách nhiệm phân tích các đoạn mã wave rồi từ đó đưa ra các hành động tương ứng với đoạn mã phân tích được. Vì tính chất quan trọng của nó nên thành phần này sẽ được mô tả chi tiết dưới đây. 1. Giới thiệu về JavaCC a. JavaCC là gì? JavaCC – Java Compiler Compiler là bộ sinh parser hiện đang được dùng phổ biến trong các ứng dụng Java. Bộ sinh parser này sẽ đọc các đặc tả cú pháp của ngôn ngữ nào đó và chuyển nó thành chương trình Java – chương trình có thể nhận dạng ra chính xác cấu trúc của ngôn ngữ đó. Bên cạnh đó, công cụ PROP ADDR2 OS Parent Children TRUE … PROP ADDR1 AP Parent Children TRUE … SECT ADDR3 NM Parent Children TRUE … SECT ADDR4 NM Parent Children FALSE … Hình 4-10: Track Forest - 45 - JavaCC còn cung cấp các khả năng khác trong quá trình đọc cú pháp như việc xây dựng cây, gỡ lỗi… Để sinh ra bộ mã Parser cho ngôn ngữ wave ta sử dụng 2 công cụ trong gói JavaCC bao gồm: - JJTree: đọc đặc tả file .jjt (jjt bao gồm các đặc tả về ngôn ngữ wave bao gồm các token và các luật triển khai, cây cú pháp của wave) và đưa ra đặc tả về Token (các files AST: abstract synctax tree) và file .jj dùng cho việc sinh ra mã nguồn parser - JavaCC: đọc đặc tả .jj và sinh ra bộ mã bao gồm parser và các mã để kiểm soát lỗi của ngôn ngữ wave b. Quá trình xử lý của JavaCC Quá trình phân tích từ vựng và cú pháp diễn ra song song với nhau. Bộ phân tích từ vựng sẽ đọc từng ký tự (ký tự trong các đoạn mã của wave) sau đó sẽ sinh ra các đối tượng Token. Cách tách các ký tự thành token tùy thuộc vào người lập trình – đó là các định nghĩa nằm trong biểu thức chính quy. JavaCC cho phép sử dụng luật sinh EBNF để định nghĩa. Mỗi token trong quá trình phân tích tự vựng sẽ là đầu vào cho quá trình phân tích cú pháp để thực thi phân tích cấu trúc của ngôn ngữ và sinh ra cây cú pháp. c. Các ngôn ngữ có thể xây dựng bởi JavaCC Rất nhiều loại ngôn ngữ khác nhau có thể được sinh bởi JavaCC như: Visual Basic, Python, Rational Rose mdl files, XML, XML DTDs, HTML, C, C++, Java, JavaScript, Oberon, SQL, VHDL, VRML, ASN1,.. và rất nhiều loại ngôn ngữ khác nữa: WAVE... 2. File cú pháp của JavaCC Để javaCC có thể biên dịch một đặc tả cú pháp sang dạng mã java, cần có một quy ước về cách viết file cú pháp để từ đó có thể sinh ra các đoạn mã java (phục vụ cho quá trình parser hay quản lý token) một cách hiệu quả. Cú pháp file đặc tả JavaCC bao gồm các thành phần sau: javacc_input ::= javacc_options "PARSER_BEGIN" "(" ")" java_compilation_unit "PARSER_END" "(" ")" ( production )* - 46 - Một file cú pháp bắt đầu với một danh sách các tùy chọn. Theo sau là thành phần biên dịch java được bao trong hai từ khóa "PARSER_BEGIN(parser_name)" và "PARSER_END(parser_name)". Tiếp đến là danh sách các cú pháp luật sinh. Các tùy chọn và luật sinh sẽ được trình bày dưới đây. Tham số name trong cặp từ khóa PARSER_BEGIN và PARSER_END là tên của bộ phân tích cú pháp được sinh ra. Đối với đề tài name có tên là WaveParser thì JavaCC tự động chèn các tên này vào sau các file tùy chọn được sinh ra như WaveParserConstants.java, WaveParserTokenManager.java … PARSER_BEGIN(parser_name) . . . class parser_name . . . { . . . } . . . PARSER_END(parser_name) a. Các từ khóa và tùy chọn của JavaCC JavaCC cung cấp một tập các từ khóa như bảng sau: EOF IGNORE_CASE JAVACODE LOOKAHEAD MORE options PARSER_BEGIN PARSER_END SKIP SPECIAL_TOKEN TOKEN TOKEN_MGR_DECLS Ngoài ra JavaCC còn cung cấp một số từ khóa thuộc loại tùy chọn trong một file đặc tả cú pháp của JavaCC. LOOKAHEAD: Số token được nhìn trước trước khi quyết định lựa chọn một điểm trong quá trình phân tích. Mặc định có giá trị 1. Số nhỏ hơn, quá trình phân tích nhanh hơn. Số này có thể định nghĩa lại cho các luật sinh cụ thể trong phạm vi ngữ pháp để định rõ tính chất giai đoạn sau. CHOICE_AMBIGUITY_CHECK: Đây là một tùy chọn số nguyên có giá trị mặc định là 2. Đây là số token có được trong việc kiểm tra sự lựa chọn của hình thức "A | B | ..." cho tình trạng có nhiều nghĩa. - 47 - OTHER_AMBIGUITY_CHECK: Đây là một tùy chọn số nguyên có giá trị mặc định là 1. Đây là số token có được trong việc kiểm tra tất cả các hình thức khác nhau của sự lựa chọn (ví dụ của hình thức "(A)*", "(A)+", and "(A)?") cho tình trạng có nhiều nghĩa. Việc này mất nhiều thời gian hơn sự kiểm tra lựa chọn, do đó giá trị mặc định được thiết lập là 1 hơn là 2. STATIC: Đây là một tùy chọn kiểu boolean có giá trị mặc định là true. Nếu true tất cả các phương thức và biến của lớp theo lý thuyết đều là static trong sự phát sinh cú pháp và quản lý token. DEBUG_PARSER: Đây là một tùy chọn kiểu boolean có giá trị mặc định là false. Tùy chọn này được sử dụng để gỡ lỗi từ việc phát sinh cú pháp. Thiết lập tùy chọn này là true là nguyên nhân quá trình phân tích cú pháp phát sinh dấu hiệu của hành động. DEBUG_LOOKAHEAD: Đây là tùy chọn kiểu boolean có giá trị mặc định là false. Thiết lập tùy chọn này là true là nguyên nhân quá trình phân tích cú pháp phát sinh tất cả dấu hiệu thông tin nó thực hiện khi tùy chọn DEBUG_PARSER là true, đó cũng là nguyên nhân để nó phát sinh ra dấu hiệu hành động đã thi hành trong thao tác lookahead. DEBUG_TOKEN_MANAGER: Tùy chọn boolean có giá trị mặc định là false. Tùy chọn này được sử dụng để gỡ lỗi thông tin từ các token đã phát sinh. Thiết đặt tùy chọn này là true là nguyên nhân để quản lý token phát sinh dấu hiệu của hành động. Dấu hiệu này khá rộng và chỉ nên sử dụng nó khi có một lỗi từ vựng, những lỗi thông báo đến bạn và bạn không biết tại sao. Điển hình trong trường hợp này, bạn có thể giải quyết vấn đề bằng cách chú ý đến vài dòng trước đó của dấu hiệu. ERROR_REPORTING: Tùy chọn boolean có giá trị mặc định là true. Thiết lập tùy chọn này là false là nguyên nhân các lỗi mắc phải từ các lỗi phân tích cú pháp có báo cáo thiếu chi tiết. Lý do để thiết lập tùy chọn này là false là để cải tiến sự thực thi. JAVA_UNICODE_ESCAPE: Đây là tùy chọn boolean có giá trị mặc định là false. Khi thiết lập true, sự phân tích cú pháp đã phát sinh sử dụng một luồng vào xử lý bởi Java Unicode escapes(\u...) trước khi gửi ký tự tới token manager. Mặc định Java Unicode escapes không xử lý. UNICODE_INPUT: Đây là tùy chọn kiểu boolean giá trị mặc định là false. Khi thiết lập true, sự phân tích cú pháp đã phát sinh sử dụng một luồng nhập để đọc file Unicode. Mặc định file ASCII được thừa nhận. Tùy chọn này được bỏ qua nếu một trong hai tùy chọn USER_TOKEN_MANAGER, USER_CHAR_STREAM được thiết lập là true. IGNORE_CASE: Tùy chọn kiểu boolean có giá trị mặc định là false. Thiết lập tùy chọn này là true là nguyên nhân phát sinh ra token manager để bác bỏ trong trường hợp token được chỉ định rõ và những hồ sơ đưa vào. Tùy chọn này hữu dụng trong việc viết ngữ pháp cho ngôn ngữ như HTML. - 48 - USER_TOKEN_MANAGER: Tùy chọn kiểu boolean, giá trị ngầm định là false. Hành động mặc định là phát sinh ra một token manager làm việc trên những token ngữ pháp đã chỉ rõ. Nếu nó được thiết lập true, bộ phân tích cú pháp được phát sinh để thừa nhận những token từ bất kỳ token quản lý nào thuộc kiểu "TokenManager"- giao diện được phát sinh vào trong thư mục bộ phân tích cú pháp. b. Bộ quản lý Token Phần đặc tả từ vựng của JavaCC được tổ chức thành tập các trạng thái từ vựng “lexical states”. Mỗi trạng thái từ vựng có một định danh. Trạng thái từ vựng chuẩn là DEFAULT. Trình quản lý token được sinh ra tại mỗi thời điểm sẽ có một trạng thái từ vựng trong tập các trạng thái từ vựng. Khi trình quản lý token khởi tạo nó sẽ có trạng thái từ vựng mặc định là DEFAULT. Trạng thái từ vựng bắt đầu có thể được xác định giống như là tham số khi xây dựng một đối tượng quản lý token. Có 4 loại biểu thức chính qui: SKIP, MORE, TOKEN, và SPECIAL_TOKEN. o SKIP: Bỏ qua chuỗi từ vựng khi gặp khai báo SKIP. o MORE: Tiếp tục cho đến khi gặp trạng thái kế tiếp, đưa chuỗi từ vựng khi gặp khai báo MORE vào trạng thái chờ. Chuỗi này sẽ là tiền tố cho chuỗi kế tiếp. o TOKEN: Tạo ra một token sử dụng chuỗi và gửi nó vào bộ phân tích cú pháp. o SPECIAL_TOKEN: Tạo ra một token đặc biệt không tham gia vào quá trình phân tích. c. Luật sinh Có 4 loại luật sinh trong JavaCC gồm javacode_production , bnf_production, regular_expr_production, token_manager_decls. javacode_production và bnf_production được sử dụng để định nghĩa ngữ pháp trực tiếp cho bộ phân tích cú pháp. regular_expr_production được sử dụng để định nghĩa ngữ pháp của các Token, trình quản lý Token sử dụng các ngữ pháp này để tạo ra Token manager, có thể hiểu đây các đặc tả token trong bộ phân tích cú pháp. token_manager_decls được sử dụng để giới thiệu các khai báo dùng để chèn vào bên trong trình quản lý token. • javacode_production javacode_production là một cách để viết mã Java cho một số các luật sinh thay vì sử dụng EBNF. Điều này hữu ích khi mà việc định nghĩa một cú pháp bằng EBNF quá khó khăn. Ví dụ sau minh họa cho việc định nghĩa xác định luật sinh của một block. JAVACODE void skip_to_matching_brace() { Token tok; - 49 - int nesting = 1; while (true) { tok = getToken(1); if (tok.kind == LBRACE) nesting++; if (tok.kind == RBRACE) { nesting--; if (nesting == 0) break; } tok = getNextToken(); } } • bnf_production bnf_production ::= java_access_modifier java_return_type java_identifier "(" java_parameter_list ")" ":" java_block "{" expansion_choices "}" bnf_production là luật sinh chuẩn được sử dụng trong JavaCC. Mỗi luật sinh BNF có vế trái là một đặc tả không kết thúc. Luật sinh BNF sẽ định nghĩa đặc tả không kết thúc này theo cách thức của BNF mở rộng hay EBNF. Điều này được thực hiện giống như các khai báo của các phương thức trong Java. Có 2 phần chính ở vế phải của luật sinh BNF : - Phần thứ nhất là tập các khai báo và mã của Java(Java block). Các mã java này sẽ được sinh ra ở phần đầu của các phương thức cho luật sinh BNF. Mỗi khi phương thức luật sinh này được thực thi trong quá trình phân tích cú pháp thì những khai báo và mã java này sẽ được thực thi. Khai báo trong phần này sẽ có mặt ở tất cả các hành động trong EBNF. JavaCC không xử lý bất kỳ một khai báo hoặc đoạn mã java nào, ngoại trừ việc bỏ qua các dấu ngoặc đơn và thu thập tất cả mã lệnh để làm cơ sở trong các phương thức được sinh ra sau này. - Phần thứ hai của vế phải là các lựa chọn mở rộng expansion_choices có cú pháp như sau: expansion_choices ::= expansion ( "|" expansion )* Các expansion_choices được viết giống như một danh sách của một hoặc nhiều các mở rộng (expansion) được ngăn cách nhau bởi các dấu hoặc | . expansion ::= ( expansion_unit )* - 50 - Một mở rộng(expansion) được viết thành một tập các đơn vị mở rộng(expansion units). Một expansion đúng khi tất cả các expansion units đều đúng. Ví dụ, mở rộng (expansion) "{" decls() "}" bao gồm 3 đơn vị mở rộng(expansion units) “{” , decls(), và “}”. Một cú pháp đúng cho mở rộng này là phải bắt đầu bằng một dấu “{” kết thúc bởi dấu “}” và thỏa mãn hàm decls() ở phần thân. Một đơn vị mở rộng(expansion_unit) có thể là một lookahead, một tập các khai báo và mã java (java_block), Các lựa chọn mở rộng(expansion_choices), .. expansion_unit ::= local_lookahead | java_block | "(" expansion_choices ")" [ "+" | "*" | "?" ] | "[" expansion_choices "]" | [ java_assignment_lhs "=" ] regular_expression | [ java_assignment_lhs "=" ] java_identifier "(" java_expression_list ")" Một đơn vị mở rộng có thể gồm các lựa chọn mở rộng có các tùy chọn “+”, “*”, “?”. lookahead ::= "LOOKAHEAD" "(" [ java_integer_literal ] [ "," ] [ expansion_choices ] [ "," ] [ "{" java_expression "}" ] ")" Số token được nhìn trước trước khi quyết định lựa chọn một điểm trong quá trình phân tích. Mặc định có giá trị 1. Số nhỏ hơn, quá trình phân tích nhanh hơn. Số này có thể định nghĩa lại cho các luật sinh cụ thể trong phạm vi ngữ pháp để định rõ tính chất giai đoạn sau. Ví dụ của luật sinh BNF: void WriteStatement() : { Token t; } { "printf" t = { jjtThis.name = t.image; } } • regular_expr_production regular_expr_production ::= [ lexical_state_list ] regexpr_kind [ "[" "IGNORE_CASE" "]" ] ":" "{" regexpr_spec ( "|" regexpr_spec )* "}" - 51 - Một luật sinh biểu thức chính qui (regular_expr_production) được sử dụng để định nghĩa các thực thể từ vựng sẽ được phân tích bởi trình quản lý token. Một luật sinh biểu thức chính qui (regular_expr_production) bắt đầu với một đặc tả của các tình trạng cho ứng dụng của nó. Tình trạng chuẩn là DEFAULT, đây là tình trạng mặc định cho các thực thể token. • token_manager_decls token_manager_decls ::= "TOKEN_MGR_DECLS" ":" java_block Phần khai báo của trình quản lý token ( token_manager_decls ) bắt đầu bằng từ khóa "TOKEN_MGR_DECLS" theo sau là dấu “:” và tập các khai báo và câu lệnh java(Java Block). 4. 5. 5 Excution Processor Excution Processor (EP) là thành phần đảm nhiệm chức năng xử lý các phép toán và các lệnh trong wave. EP sẽ được gọi đến để xử lý sau quá trình phân tích để lấy xác định phép toán cần được xử lý trong Wave Head. Các phép toán trong Wave được xử lý ở mức đơn giản là chỉ gồm một toán tử và hai toán hạng. Cấu trúc của EP bao gồm 3 thành phần chính đó là: Execution Control Unit (ECU), Operand Fetch Unit (OFU), Data Processing Unit (DPU) và Matching Unit (MU). • Execution Control Unit sẽ lấy ra chỉ lệnh và các tên của các toán hạng bên trái, bên phải. ECU chịu trách nhiệm điều khiển quá trình xử lý. • Operand Fetch Unit sẽ lấy ra giá trị của các biến bên trái, bên phải của toán hạng và điều khiển quá trình lưu trữ dữ liệu. • Data Processing Unit là thành phần xử lý sau khi đã xác định được toán tử và dữ liệu sẵn sàng. • Matching Unit đảm nhận công việc xử lý tìm kiếm trong KN. - 52 - Hình 4-11: Excution Processor 4. 5. 6 TrackProcessor Track Processor (TP) quản lý Track Forest của WI. TP xử lý tất cả các echo và suspended tail thông qua track. Track Processor nhận thông điệp điều khiển từ các thành phần khác thông qua Track Queue (TQ). Các thông điệp đi vào Track Queue gồm có: • CREATE: Thông điệp yêu cầu tạo track. • EXPANDH, EXPANDS: Tạo các nhánh con (Track con) của track hiện tại. EXPANDH dùng trong trường hợp các nhánh được sinh ra bởi lệnh hop, còn EXPANDS là trường hợp các nhánh sinh ra bởi các sector của wave head. • ACTIVATE: Thông điệp này sẽ được gửi ngay sau khi gửi hết thông điệp EXPAND để kích hoạt TN hiện tại. • ECHO: Thông điệp echo từ các nhánh con được gửi lên TN cha. • TAIL: Thông điệp gửi chuỗi wave tail đến các nhánh con để tiếp tục phát triển. Dưới đây là một quá trình nhận và xử lý các thông điệp của Track Processor - 53 - PROP Parent / Children / NONE 0 Wave Env #.C==b b c a PROP Parent Children / NONE 0 Wave Env b c a PROP Parent Children / NONE 0 Wave Env PROP Parent Children NONE 2 Wave Env C==b C==b TRR2 TRR3 TRR1 Hình 4-12: Sau khi nhận và xử lý CREATE Hình 4-13: Sau khi nhận và xử lý EXPANDH - 54 - PROP Parent Children / NONE 0 Wave Env b c a PROP Parent Children / NONE 0 Wave Env PROP Parent / Children NONE 2 Wave Env C==b C==b TRR2 TRR3 TRR1 Hình 4-14: Sau khi nhận và xử lý ACTIVATE - 55 - PROP Parent Children / NONE 0 Wave Env b c a PROP Parent Children / NONE 0 Wave Env PROP Parent / Children NONE 0 Wave Env C==b C==b TRR2 TRR3 TRR1 -1 2x Hình 4-15: Sau khi nhận ECHO từ các nhánh con - 56 - 4. 5. 7 Communication Processor Communication Processor đóng vai trò liên lạc giữa các WI trên các máy tính trong mạng. Khi chuỗi wave di chuyển trong KN bằng các lệnh hop, chúng có thể lan truyền từ WI trong máy tính này sang WI trên máy tính khác. Quá trình di chuyển của các chuỗi wave đó đều phải thông qua CP. Để đảm bảo dữ liệu giữa các máy tính là an toàn nên CP xử dụng giao thức TCP/IP của tầng giao vận để truyền và nhận các thông điệp, kết nối giữa các máy tính sẽ được giữ nguyên từ lúc các WI được thiết lập cho đến khi WI rời khỏi mạng. CP quản lý Communication Queue, đây là một hàng đợi chứa các thông điệp sẽ được gửi đi. PROP Parent Children / NONE 0 Wave Env b c a PROP Parent / Children NONE 0 Wave Env C==b TRR2 TRR1 -1 2x Hình 4-16: Sau khi xử lý ECHO nhận được - 57 - Cấu trúc chung của các thông điệp: • Type: kiểu của thông điệp bao gồm : o WAVE: thông điệp gửi wave đi o CREATE TRACK: thông điệp yêu cầu tạo track trên máy khác, o CREATE NODE: thông điệp yêu cầu tạo một node trong KN, o CREATE LINK: thông điệp yêu cầu tạo link giữa 2 node trong KN, o ECHO: thông điệp gửi echo đi, TAIL: thông điệp gửi wave tail đi) • Destination Address: địa chỉ của máy nhận thông điệp. • Source Address: địa chỉ của máy gửi thông điệp. • Data: Thành phần dữ liệu của thông điệp. 4. 6 Quan hệ giữa các thành phần trong Wave Interpreter Tổ chức các thành phần trong WI và quan hệ giữa chúng được thể hiện trong Hình 3-18: Quan hệ giữa các thành phần trong Wave Interpreter. Các thông điệp đến WI đều thông qua Communication Processor với 3 kiểu thông điệp chính là Wave, Echo và Tail. Type Destination Address Source Address Data Communication Queue Communication Message Hình 4-17: Communication Processor - 58 - Wave nhận được từ CP sẽ được gửi vào WQ để phân tích và xử lý, ngoài ra wave có thể được chèn vào WQ một cách trực tiếp từ WI, hoặc từ TP khi kích hoạt các nhánh để gửi các suspended wave. Thành phần EP cũng có thể gửi các wave vào WQ khi xử lý các sector, các toán tử code injection của ngôn ngữ Wave. Sự lan truyền của wave phụ thuộc vào TP và EP. Nếu trạng thái track của wave được kích hoạt, sự lan truyền của wave phụ thuộc gián tiếp vào EP, đầu tiên EP sẽ gửi thông điệp điều khiển vào TQ, thông điệp sẽ được TP xử lý và chuỗi wave được lan truyền khi track tương ứng được kích hoạt. Thông điệp ECHO và TAIL được CP và TP xử lý. Mỗi khi chuỗi wave kết thúc trong chế độ track EP sẽ tạo ra thông điệp ECHO và gửi vào TQ. Các suspended tail sẽ được TP gửi đi sau khi xử lý các ECHO mà điều kiện của rule được thỏa mãn để kích hoạt track. Các thành phần xử lý trong WI độc lập với nhau, mỗi thành phần sẽ xử lý dữ liệu trong các hàng đợi riêng. Tuy nhiên, EP có thể coi là thành phần xử lý chính, khi EP chịu trách nhiệm điều khiển toàn bộ quá trình xử lý wave và khởi tạo các thông điệp điều khiển tới các thành phần xử lý khác. PARSING UNIT (PU) TRACK PROCESSOR (TP) EXECUTION PROCESSOR (EP) COMMUNICATION PROCESSOR (CP) trackless sectors, code injection, hop, action track operations TQ resumed tails, activated sectors propagations, echoes, tails CQ wave, create KN echoes, tails ™ ƒÆ½Ä! waves  echoes  tails  WQ KN TN Hình 4-18: Quan hệ giữa các thành phần trong Wave Interpreter - 59 - WI là một hệ thống mở hoàn toàn khi 3 thông điệp WAVE, ECHO và TAIL có thể gửi trực tiếp từ bên ngoài vào trong hệ thống tới các node và link hoặc giữa các track. Người dùng có thể tương tác với WI bằng cách gửi các thông điệp tới CP hoặc trực tiếp gửi vào WQ thông qua các giao diện được cung cấp trên máy có cài đặt WI. Tương ứng với 3 loại thông điệp, WI có thể được tổ chức thành 3 luồng điều khiển chính cho từng thông điệp và thực thi một cách hoàn toàn độc lập. Các luồng điều khiền đó chính là đầu vào WI từ bên ngoài hệ thống, không những thế chúng còn tương tác qua lại lẫn nhau trong WI tạo thành chu trình xử lý các đoạn mã wave trên các node trong KN. Các hoạt động cơ bản của WI và tương tác giữa chúng được mô tả như trong Hình 4-19.Trước tiên, chúng tôi sẽ đưa ra cái nhìn tổng quát về các luồng chính này, sau đó sẽ mô tả chi tiết chúng trong phần tiếp theo. • Luồng xử lý Wave: Khi nhận được một wave từ bên ngoài, chuỗi wave thông thường được xử lý theo các bước: phân tích và xử lý wave head (parse, process_head), tạo ra các nhánh (spread_branches), sao chép wave tail cho các nhánh (replicate_tail) và lan tỏa chuỗi wave thu được đến các node đích (propagate). Quá trình này sẽ được tiếp tục cho đến khi chuỗi wave kết thúc hoặc được gửi ra ngoài hệ thống. • Luồng xử lý Echo: mỗi echo nhận được sẽ được gửi cho TP xử lý. Quá trình xử lý echo trải qua các bước: kích hoạt echo (activate_echo), gửi echo lên track cha (propagate_echo), và kết hợp echo nhận được với echo đã có ở track cha. Nếu tất cả các nhánh con của track cha đều đã gửi echo lên, thì quá trình lại được tiếp tục đối với track cha. Vòng lặp cứ tiếp diễn cho đến khi echo được gửi ra bên ngoài hệ thống. • Luồng xử lý Tail: tail từ các rule sẽ được gửi ngược lại thông qua track xuống các track con. Một wave tail từ bên ngoài đến sẽ được gửi tới track tương ứng và gửi xuống các track con thông qua hệ thống track hiện tại. Quá trình gửi wave tail sẽ được lặp lại cho đến khi tới các node đích hoặc wave tail được gửi đến các track con ở bên ngoài hệ thống. - 60 - Hình 4-19: Luồng xử lý giữa các thành phần trong Wave Interpreter 4. 6. 1 Luồng xử lý Wave Các wave nằm trong WQ độc lập với nhau, do đó sẽ được xử lý đồng thời. Đầu tiên, khi có wave nằm trong WQ, WI sẽ lần lượt lấy ra các wave, tách thành phần wave string và wave envrironment. Chuỗi wave thu được sẽ trải qua 2 giai đoạn: phân tích bởi PU và xử lý bởi EU. Ở giai đoạn phân tích, chuỗi wave được tách ra thành wave head và wave tail. Trong giai đoạn xử lý, wave head sẽ được xử lý ở node hiện tại và phụ thuộc vào kết quả xử lý mà wave tail sẽ được lan tỏa đến các node đích để tiếp tục quá trình thông dịch. Quá trình xử lý wave head được chia ra làm 7 trường hợp xử lý bao gồm: hop, action, sectors, control_rule, echo_dot_halt, code_injection, và external_call. Chi tiết về các trường hợp này được mô tả dưới đây: - 61 - • Hop Lệnh hop giúp cho wave di chuyển từ node này sang node khác cũng như từ WI này sang WI khác trong mạng. Quá trình xử lý hop như sau: 9 parser: wave string được phân tích thành wave head và wave tail. Wave head được phân tích thành 2 toán hạng và toán tử. 9 process_head: Toán tử xác định được từ bước trên dùng để xác định cấu trúc điều khiển trong 7 trường hợp xử lý. Trong trường hợp này là hop được xác định bằng toán tử ‘#’ 9 hop: xử lý lệnh hop. Hai toán hạng được xác định giá trị ở vị trí hiện tại trong KN. 9 match_KN: hai toán hạng sẽ được khớp với link và node của KN nối với node hiện tại. Nếu wave ở trong chế độ CREATE thì các link và node mới được tạo ra. Kết quả của bước này là danh sách các node thỏa mãn điều kiện. 9 spread_branch: Với mỗi node đích, một wave mới được tạo ra cùng với các biến frontal và biến environment ở node hiện tại. 9 replicate_tail: wave tail được gán làm wave string cho mỗi wave mới tạo ra. 9 activate_branch: kích hoạt xử lý các wave. 9 propagate: các wave tạo ra được gửi đến các node đích. Nếu node đích nằm trên cùng KN thì quá trình lan tỏa kết thúc và wave tail được gửi đến các node đích để tiếp tục được xử lý. Ngược lại wave sẽ được gửi ra ngoài mạng để tới node đích trên KN của máy khác. Độ dài của chuỗi wave giảm dần do wave head bị mất đi sau mỗi chu trình. Chu trình liên tục được diễn ra cho đến khi chuỗi wave di chuyển sang WI khác hoặc wave tail rỗng. Chuỗi wave rỗng nghĩa là đã được xử lý xong và có thể echo sẽ được gửi đi thông báo trạng thái kết thúc của wave • Action Các action được thực hiện ngay trên node hiện tại, bao gồm các toán tử gán và các toán tử so sánh. Các action được thực hiện dựa trên hai toán hạng bên trái và bên phải. Trong phép gán, kết quả sẽ được lưu trữ vào toán hạng bên trái. Trong các phép so sánh, trạng thái thực hiện của phép toán sẽ được ước lượng và quá trình xử lý chuỗi wave sẽ dừng lại nếu phép so sanh trả về kết quả là ‘fail’. Luồng xử lý các action sẽ bao gồm các bước sau: 9 parse: wave head và wave tail được tách ra từ chuỗi wave. Trong trường hợp này toán tử được xác định là các phép gán hoặc các phép so sánh. 9 process_head: quá trình xử lý chuyển sang xử lý các action 9 action_sequence: xử lý toán tử thu được. Việc xử lý các phép gán và các phép so sánh là khác nhau nên được chuyển thành 2 bước xử lý nhỏ hơn: − process_assign: Đây là bước xử lý cho các phép gán. Kết quả của phép gán sẽ được lưu lại vào toán hạng bên trái. - 62 - − process_filter: Các phép so sánh được xử lý. Nếu điều kiện so sánh được thỏa mãn thì quá trình xử lý sẽ tiếp tục, ngược lại việc xử lý sẽ ngừng lại và một echo thể hiện trạng thái thất bại được gửi đi (start_echo) − resume_tail: Khi action được xử lý xong, quá trình xử lý wave sẽ được tiếp tục lặp lại ở node hiện tại. • Sectors Nếu trong wave head chứa nhiều sector (mỗi sector phân cách nhau bởi dấu phẩy) thì chuỗi wave sẽ được phân chia ở node hiện tại thành các nhánh khác nhau. Mỗi nhánh nhận một wave string khác nhau, mà mỗi wave string là một sector được nối với wave tail. Việc xử lý sector cũng gần giống với hop nhưng khác một chút đó là các wave do quá trình xử lý sector sinh ra vẫn tiếp tục được xử lý ở node hiện tại. Quá trình xử lý các sector sẽ như sau: 9 parse: Wave head và wave tail được chia ra từ chuỗi wave, trong wave head chứa cú pháp của sector (chứa dấu phẩy phân cách). Trong trường hợp này, thay vì xác định các toán từ thì chuỗi wave giữa các sector sẽ được tách ra và trả lại cho bước xử lý tiếp theo. 9 process_head: quá trình xử lý chuyển sang xử lý các sector. 9 sectors: các nhánh ứng với mỗi sector bắt đầu được tạo ra. 9 spread_branches: mỗi nhánh ứng với một sectors được tạo ra trên cùng node hiện tại. Các biến frontal, environment được sao chép cho mỗi nhánh. 9 replicate_tail: wave tail sẽ được sao chép cho mỗi nhánh. Khác với việc sao chép wave tail trong hop, ở đây wave tail được nỗi vào chuỗi wave nằm trong từng nhánh được tách ra từ các sector trước đó. Các dấu ngoặc thừa bị xóa bỏ. 9 activate_branch: kích hoạt nhánh để xử lý (khác với hop, việc xử lý các sector không có bước propagation do các nhánh vẫn nằm trên node hiện tại) 9 resume_tail: wave string thu được sẽ tiếp tục được xử lý từ bước đầu tiên • Code injection Ngôn ngữ wave cho phép chèn vào các đoạn chương trình ngay trong quá trình xử lý từ các biến đi cùng wave trong quá trình đi chuyển hay từ các biến nằm trong node mà chuỗi wave đi qua. Đoạn chương trình được đưa vào sẽ nối vào đầu của wave tail và tiếp tục được xử lý trên cùng node với chuỗi wave trước đó. 9 parser: wave head và wave tail được tách ra. Wave head là toán tử ‘^’ đứng trước một biến báo hiệu đoạn mã được chèn thêm vào chính là giá trị của biến đó. 9 process_head: quá trình xử lý chuyển sang xử lý lệnh code injection 9 code_injection: Giá trị của biến được lấy ra và chuyển sang dạng xâu (nếu cần thiết). String thu được sẽ nối vào đầu của wave tail, quá trình xử lý với chuỗi wave tổng hợp lại tiếp tục từ đầu trên cùng node hiện tại. • External call - 63 - Toán tử external call là cách giao tiếp của WI với các hệ thống khác thông qua hệ điều hành. Một lời gọi external call sẽ tạm dừng nhánh hiện tại và tiếp tục quay lại xử lý sau khi lời gọi kết thúc. 9 parser: Quá trình phân tích gặp toán tử external call (cú pháp của ‘?’) 9 process_head: quá trình xử lý chuyển sang xử lý external call 9 external_call: hai toán tử được lấy giá trị và kết hợp thành lệnh để gọi chương trình. Lệnh này sẽ được gửi đi, nhánh hiện tại sẽ tạm treo cho đến khi chương trình được gọi thực hiện xong và trả về kết quả. 9 resume_tail: chuỗi wave sẽ tiếp tục quay lại quá trình xử lý • Control rule Chuỗi wave có 2 trạng thái lan tỏa, một là trong trạng thái không có track và một là trong trạng thái track. Khi di chuyển trong trạng thái track, sau mỗi lệnh hop, hoặc xử lý các sector thì sẽ tạo ra track mới nối với track hiện tại. Một control rule sẽ thiết lập một điểm điều khiển vào node hiện tại, việc điều khiển này được gắn với chuỗi wave nằm trong cặp mở đóng ngoặc của cú pháp rule. Chuỗi wave này gọi là enclosed wave. Quá trình xử lý được chia làm 2 phần: 9 Các biến frontal và environment của nhánh hiện tại sẽ được nhân bản cho enclosed wave, và một track mới được tạo ra. 9 Rule được gán cho track vừa tạo ra để xử lý các echo và wave tail sẽ được treo tại track mới này. Các luật tuần tự (SQ, OQ, AQ) đảm bảo các nhánh được thực hiện một cách lần lượt. Sau khi kích hoạt các nhánh thì chỉ duy nhất một nhánh được thực hiện và các nhánh khác sẽ tạm treo lại. Các bước xử lý như sau: 9 parser: Wave head và wave tail được tách ra. Wave head chứa một trong số các Rule của ngôn ngữ Wave và chuỗi wave nằm trong cặp mở đóng ngoặc. 9 process_head: Quá trình xử lý chuyển sang xử lý rule 9 control_rule: Xứ lý rule trong wave head 9 extract_head: tách wave string nằm trong cặp mở đóng ngoặc của rule, và tách các biến frontal, environment khỏi wave. 9 create_track: tạo ra track mới và track hiện tại (nếu có) sẽ là track cha của track vừa tạo 9 assign_rule: track mới tạo ra sẽ được gán với rule để xử lý các echo về sau. 9 suspend_tail: wave tail sẽ được treo ở track vừa tạo ra. • Echo dot halt Echo dot halt là các toán từ đặc biệt được xử dụng để kết thúc chuỗi wave đang thực thi trên node hiện tại và gửi lại các echo cho track. Sau đó, wave tail được treo tại track có thể được tiếp tục lan tỏa trong node hiện tại. Các bước xử lý như sau: - 64 - 9 parse: wave head và wave tail được tách ra, wave head chứa toán tử echo dot halt (cú pháp của ‘!’). 9 process_head: chuyển quá trình xủ lý sang echo dot halt 9 echo_dot_halt: giá trị của echo được xác định 9 start_echo: echo được gán cho track hiện tại và tiếp tục được lan tỏa lên trên theo track. 9 cancel_tail: wave tail sẽ được xóa bỏ sau khi gửi echo. Không chỉ có lệnh echo dot halt gửi echo sau khi xử lý mà lệnh hop và các lệnh so sánh cũng gửi echo. Lệnh hop sẽ gửi echo nếu việc khớp các toán hạng với KN thất bại. Các lệnh so sánh cũng gửi echo nếu điều kiện so sánh không được thỏa mãn. 4. 6. 2 Luồng xử lý các echo và điều khiển các rule Các echo sẽ lan truyền ngược lên gốc của hệ thống track và kết hợp với nhau tại các TN. Các echo sẽ được đồng bộ với nhau bằng cách track cha sẽ chờ các track con sau khi kết thúc gửi echo lên. Sau khi tất cả các echo đã được nhận đủ, track cha lại tiếp tục kích hoạt việc gửi echo tổng hợp lên trên. Quá trình trên sẽ tiếp tục cho đến khi gặp track có kèm theo rule hoặc echo được gửi tới gốc của hệ thống track. Sau khi xử lý xong