Đề tài Xây dựng tác tửgiao diện hỗtrợlập trình sửdụng mạng Bayes

84 Abstract: In this paper, we describe the design and construction of an interface agent for assisting Java programming. The agent automatically monitors programm fragments being coded and recommends to the programmer library components that can be used for these fragments. Our agent is different from one described in [8] in that the former uses bayesian networks for making decision. The use of bayesian networks enables integrating different evidences in a flexible way when making decision. The agent is integrated into IDE IntelliJ Idea as a plug-in. The usefullness of the agent has been verified by experiments. I. ĐẶT VẤN ĐỀ Các ngôn ngữ lập trình hiện nay đều có hệ thống đồ sộ các thư viện hàm và các thành phần khác (lớp, phương thức, giao diện .v.v.) đi kèm. Những thư viện này do nhà sản xuất chương trình dịch cung cấp hoặc do những tổ chức và lập trình viên khác xây dựng nên. Ví dụ, thư viện Java phiên bản 1.4 có tới 2723 lớp. Thư viện ngôn ngữ cho phép tiết kiệm đáng kể thời gian lập trình. Tuy nhiên, không phải lập trình viên nào cũng biết thư viện cung cấp những thành phần nào, chức năng của thành phần đó là gì. Việc tìm kiếm thành phần cần thiết bằng cách duyệt thư viện hay sử dụng công cụ tìm kiếm theo từ khoá thường không cho kết quả mong muốn nếu lập trình viên thậm chí không biết thành phần cần tìm có tồn tại trong thư viện hay không. Do vậy, cần có công cụ giúp lập trình viên tìm ra những thành phần thư viện cần thiết vào thời điểm thích hợp. Agent (tác tử) giao diện là những chương trình chạy trong chế độ nền, có khả năng theo dõi quá trình giao tiếp giữa người với máy tính và chủ động đưa ra những trợ giúp cần thiết tuỳ vào tình huống cụ thể [4]. Khác với những chương trình tra cứu hoặc tìm kiếm thông thường, agent giao diện có cơ chế suy diễn cho phép tự động ra quyết định khi nào cần trợ giúp mà không cần đến yêu cầu từ phía người dùng. Bài báo mô tả agent giao diện với khả năng tự động theo dõi quá trình viết mã chương trình trên Java. Tuỳ vào tình huống cụ thể và kinh nghiệm của lập trình viên, agent sẽ đưa ra gợi ý về những thành phần của thư viện Java mà lập trình viên có thể sử dụng trong đoạn chương trình hiện tại. Mặc dù ý tưởng về agent này được lấy từ [7, 8], có hai thay đổi đáng kể so với nguyên bản. Thứ nhất, cơ chế suy diễn được xây dựng dựa trên mạng Bayes. Đây là cơ chế suy diễn xấp xỉ cho phép kết hợp thông tin từ những nguồn khác nhau. Thứ hai, agent nguyên bản được tích hợp vào trình soạn thảo emacs chạy trên hệ điều hành Linux, còn agent của chúng tôi được tích hợp vào môi trường lập trình IntelliJ Idea chạy trên Windows vốn quen thuộc với lập trình viên Việt nam hơn. Phần còn lại của bài báo sẽ trình bày chi tiết về các thay đổi này. II. NGUYÊN LÝ VÀ HOẠT ĐỘNG CỦA AGENT Do được tích hợp vào môi trường lập trình (IDE), agent giao diện được trình bày ở đây có thể theo dõi những gì đang diễn ra trong cửa sổ soạn thảo chương trình. Những thông tin này cho phép agent so sánh Xây dựng tác tử giao diện hỗ trợ lập trình sử dụng mạng Bayes Constructing an Interface Agent to Assist Programming Using Bayesian Networks Từ Minh Phương, Nguyễn Nam Phong 84 tình huống lập trình hiện tại với những thành phần đã có trong thư viện. Nếu tìm được các thành phần tương tự với tình huống hiện tại, agent sẽ giới thiệu các thành phần đó với lập trình viên thông qua một cửa sổ riêng. Mức độ tương tự của tình huống hiện tại so với thành phần thư viện được đánh giá dựa trên hai tiêu chí sau: − Tương tự về chức năng. Thông thường, trước khi viết một đoạn chương trình, lập trình viên thường chèn chú giải mô tả chức năng đoạn chương trình đó. Các chú giải này cung cấp cho agent thông tin về chức năng của đoạn chương trình đang xây dựng. − Tương tự về kiểu dữ liệu. Mỗi phương thức hoặc hàm đều có kiểu dữ liệu đầu vào, đầu ra, còn được gọi là dấu hiệu (signature) của thành phần đó. Dấu hiệu được agent sử dụng khi tìm kiếm các thành phần thư viện tương tự. Mỗi khi lập trình viên viết một đoạn chú giải mô tả chức năng của phương thức hoặc lớp sắp viết, agent sẽ sử dụng kỹ thuật tìm kiếm thu thập thông tin (information retrieval) để tìm và hiển thị danh sách những thành phần thư viện có chức năng tương tự. Trên hình 1 là một ví dụ minh họa kết quả tìm kiếm theo chức năng. Phía trên là cửa sổ soạn thảo thông thường của IntelliJ IDEA, phía dưới là cửa sổ giao diện của agent. Trong ví dụ này, lập trình viên định viết một phương thức tạo số ngẫu nhiên nằm giữa hai giới hạn. Sau khi quan sát thấy lập trình viên nhập dòng chú giải trong cửa sổ soạn thảo, agent hiển thị danh sách một số phương thức có mô tả chức năng tương tự với chú giải. Mỗi phương thức được hiển thị cùng với mô tả vắn tắt. Cột bên trái là điểm số dùng để so sánh độ phù hợp của phương thức. Việc sử dụng thông tin từ chú giải thường chưa đầy đủ để tìm ra thành phần phù hợp. Vì vậy, sau khi lập trình viên khai báo kiểu dữ liệu cho phương thức định viết như ví dụ trên hình 2, agent sử dụng kỹ thuật đối sánh dấu hiệu (signature matching) [9] để tìm những thành phần có dấu hiệu tương tự. Kết quả đối sánh theo chú giải và theo dấu hiệu được kết hợp với nhau để đưa ra danh sánh các phương thức phù hợp nhất. Trong ví dụ trên hình 2, kết hợp so sánh theo chức năng và theo dấu hiệu cho thấy phương thức getLong có điểm số cao nhất. Hình 1. Các thành phần tìm được nhờ so sánh chức năng trong phần chú giải Hình 2. Kết quả tìm kiếm sau khi kết hợp so sánh chức năng và so sánh dấu hiệu Chi tiết về kỹ thuật so sánh theo chức năng, theo dấu hiệu và kết hợp kết quả so sánh sẽ được trình bày trong phần tiếp theo của bài báo. Ngoài việc phân tích hai loại thông tin trên, một yêu cầu quan trọng với agent là không gợi ý lại những thành phần mà lập trình viên đã biết và sử dụng thành thạo. Một lập trình viên được coi là đã biết một thành phần nếu lập trình viên từng sử dụng thành phần đó một số lần nhất định trong các chương trình của mình. Như vậy, ngoài yêu cầu đưa ra trợ giúp theo tình huống, agent còn phải đưa ra trợ giúp tuỳ theo kinh nghiệm cá nhân của từng người lập trình. Để làm được điều này, agent lưu giữ một mô hình riêng cho từng người lập trình bao gồm những thành phần người đó đã biết. Khởi đầu mô hình này rỗng. Mô hình được cập nhật nhờ phân tích những chương trình mà lập trình viên đã viết cũng như theo dõi quá trình làm việc 85 của lập trình viên. III. SO SÁNH TÌNH HUỐNG VÀ RA QUYẾT ĐỊNH 1. Tương tự về chức năng Như đã nói ở trên, các chú giải do người lập trình chèn vào đoạn mã được sử dụng để tìm kiếm những thành phần có mô tả chức năng tương tự. Ở đây, agent sử dụng kỹ thuật thu thập thông tin, các chú giải được coi như những câu truy vấn, phần mô tả chức năng thành phần thư viện là văn bản cần tìm. Để thực hiện so sánh, câu truy vấn và mô tả thành phần được mô hình hoá dưới dạng các biến ngẫu nhiên, quan hệ giữa chúng được biểu diễn bởi mạng Bayes như trình bày dưới đây. Gọi 1 2{ , ,..., }nD d d d= là tập văn bản chứa mô tả chức năng các thành phần thư viện (gọi tắt là văn bản). Văn bản được đánh chỉ mục và biểu diễn bởi từ khoá [1]. Gọi 1 2{ , ,..., }mU t t t= là tập tất cả các từ khoá của D. Mỗi tập con u ⊆ U bao gồm các từ khoá được gọi là một khái niệm. Để biểu diễn các thành phần hệ thống bằng mạng Bayes ta sử dụng các biến ngẫu nhiên như sau [6]. Với mỗi từ khoá ( 1.. )it i m= và khái niệm u sử dụng một biến ngẫu nhiên nhị phân cũng ký hiệu là it . 1it = nếu từ khoá it là một thành phần của khái niệm u, ti=0 nếu ngược lại. Ký hiệu ( )iI u là giá trị của biến it đối với khái niệm u. Khi đó tập u biểu diễn khái niệm dưới dạng tập con của U được tạo bởi những từ khoá it có ( ) 1iI u = . Có tất cả 2m khái niệm như vậy được định nghĩa trên U. Văn bản và câu truy vấn khi đó được định nghĩa như những khái niệm trên U. Định nghĩa 1. Văn bản id được định nghĩa như khái niệm 1 2{ , ,..., }i md t t t= trong đó it là biến nhị phân cho phép xác định từ khoá it có thuộc khái niệm id không. Tương tự, câu truy vấn q được định nghĩa như khái niệm ' ' '1 2{ , ,..., }mq t t t= với biến nhị phân ' it xác định q có chứa từ khoá ' it không. Với các khái niệm định nghĩa ở trên, bài báo sử dụng mạng Bayes [3] để biểu diễn và tìm kiếm văn bản theo câu truy vấn. Mô hình mạng được cho trên hình 3. Các từ khoá được biểu diễn bởi các biến nhị phân ngẫu nhiên it , mỗi biến tương ứng với một nút trên mạng. Ở đây, các từ khoá được coi như độc lập với nhau, giữa các từ khoá không có những liên kết trực tiếp. Mặc dù trên thực tế, từ khoá không hoàn toàn độc lập với nhau nhưng giả thiết này thường được sử dụng để làm giảm độ phức tạp của bài toán. q t1 t2 ti tm d1 dj dn ... ... Hình 3. Mô hình mạng Bayes cho tìm kiếm văn bản Câu truy vấn q được biểu diễn bởi một nút (nút q) trên hình vẽ và tương ứng với một biến nhị phân (cũng ký hiệu là q). Biến 1q = nếu q hoàn toàn tương ứng với U. Xác suất ( )P q được tính bởi mức độ tương ứng giữa U và q, tức là nếu biết U, ta có thể suy ra q với độ tin tưởng ( )P q . Nút q được liên kết với những từ khoá tạo nên câu truy vấn q như trên hình 3. Tương tự như q, mỗi văn bản id được biểu diễn bởi một nút id và được liên kết với những từ khoá liên quan tới văn bản này. Xác suất ( )iP d cho văn bản id cũng có ý nghĩa tương tự như ( )P q cho q. Với mạng Bayes trên hình 3, mức độ phù hợp của văn bản id đối với câu truy vấn q được xác định bởi xác suất có điều kiện ( | )iP d q . Agent tính toán ( | )iP d q cho các văn bản và sắp xếp văn bản theo thứ tự giảm dần của xác suất này. Đặt 1/ ( )P qη = , 86 trong đó ( )P q là hằng số đối với tất cả văn bản id , ta có ( ) ( | ) ( ) ( ) ( | ) ( ) j j j j u U P d q P d q P q P d q P d q u P u η η ∈ ∧= = ∧ = ∧∑ trong đó ( ) 1/ 2mP u = . Trên mạng Bayes ở hình 3, id độc lập với nút q nếu biết giá trị u, do đó ( | ) ( | ) ( | ) ( )i i u U P d q P d u P q u P uη ∈ = ∑ (1) Để tính ( | )iP d q cần xác định giá trị ( | )iP d u và ( | )P q u . Các giá trị này được chọn sao cho mô hình mạng Bayes cho kết quả tương tự mô hình vec tơ trong tìm kiếm thu thập tin. Mô hình vec tơ biểu diễn câu truy vấn q và văn bản dj dưới dạng vec tơ các từ khoá qr , jd r và coi độ phù hợp giữa câu truy vấn và văn bản như côsin của góc giữa hai vec tơ. Cụ thể, gọi wij là trọng số tương ứng với từ khoá ti trong văn bản dj, gọi wiq là trọng số tương ứng với từ khoá ti trong q. wij được tính theo phương pháp tf-idf [1]. Giá trị wiq bằng 1 nếu từ khoá có trong q và bằng 0 trong trường hợp ngược lại. Chọn : 1 ( | ) 0 P q u ⎧= ⎨⎩ nếu , ( ) ( )i q i u it g t g t∀ = nếu ngược lại (2) 1 2 2 1 1 ( | ) m ij iui j t t ij iui i w w P d u w w = = = ×= × ∑ ∑ ∑ (3) Dễ dàng nhận thấy, nếu thay (2) và (3) vào (1) ta có ' '1 2 2 1 1 ( | ) m ij iq ji j m m jij iqi i w w d q P d u d qw w η η= = = × •= = ×× ∑ ∑ ∑ r r r r Như vậy, ( | )iP d q tỷ lệ với côsin của góc giữa q r và jd r , tức là mô hình mạng Bayes cho phép sắp xếp văn bản theo mức độ phù hợp với câu truy vấn tương tự mô hình vec tơ trong tìm kiếm thu thập thông tin [5]. 2. Tương tự về kiểu dữ liệu Trong trường hợp không biết chính xác tên của thành phần thư viện cần tìm, có thể tìm kiếm những thành phần thư viện có kiểu dữ liệu tương tự với thành phần cần xây dựng. Kiểu dữ liệu đầu vào, đầu ra của mỗi thành phần (ví dụ hàm, phương thức) được gọi là dấu hiệu của thành phần đó. Đối với phương thức, dấu hiệu có thể biểu diễn dưới dạng: Phương_thức: Đầu_vào → Đầu_ra Trong đó Đầu_vào và Đầu_ra là tập các kiểu dữ liệu đầu vào và đầu ra của phương thức đó. Ví dụ, phương thức int indexOf(String str,int fromIndex) của lớp String có dấu hiệu là indexOf: {int}→{String, int}. Để tìm thành phần phù hợp với tình huống hiện tại, agent đối sánh dấu hiệu của thành phần thư viện với dấu hiệu do lập trình viên vừa nhập vào. Như vậy, dấu hiệu nhập vào được sử dụng như một câu truy vấn để tìm kiếm thành phần thư viện phù hợp. Định nghĩa 2. Hai thành phần được gọi là phù hợp về kiểu dữ liệu nếu có tập Đầu_vào giống nhau và tập Đầu_ra giống nhau. Trên thực tế, định nghĩa trên về phù hợp kiểu dữ liệu là quá chặt. Việc tìm kiếm theo định nghĩa đó sẽ bỏ qua những thành phần có dấu hiệu khá giống với thành phần cần tìm. Cần có tiêu chuẩn so sánh lỏng hơn, cho phép tìm được các thành phần với dấu hiệu tương tự như thành phần mà lập trình viên yêu cầu. Tiêu chuẩn so sánh lỏng hơn không yêu cầu kiểu dữ liệu trong tập Đầu_vào và Đầu_ra phải hoàn toàn trùng nhau mà chỉ yêu cầu kiểu dữ liệu so sánh có quan hệ khái quát hoá hoặc cụ thể hoá với nhau. Ví dụ, trong Java, kiểu long là khái quát hoá của kiểu int , tương tự như vậy, kiểu double là khái quát hoá của int (Java cho phép tự động biến đổi từ kiểu int sang kiểu double) với khoảng cách giữa int và double là 2 (cần 2 phép biến đổi thông quan kiểu float). Có thể dễ dàng xác định mạng quan hệ kiểu này dựa trên đặc tả của ngôn ngữ cụ thể. Đối với ngôn ngữ lập trình hướng đối tượng, kiểu dữ liệu tương ứng với lớp con được coi là cụ thể hoá của kiểu dữ liệu tương 87 ứng với lớp cha mẹ. Ví dụ, kiểu FileInputStream là dạng cụ thể của InputStream với khoảng cách là 1 (kế thừa trực tiếp từ InputStream). Định nghĩa 3. Mức độ tương tự s (0≤s≤1) giữa hai kiểu dữ liệu t1 và t2 được xác định như sau: s=1 nếu t1trùng t2; s=max(1- nγ, 0) nếu giữa t1 và t2 có quan hệ cụ thể hoá / khái quát hoá và khoảng cách giữa t1 và t2 là n, γ là tham số và được chọn bằng 0.05 trong hệ thống đang mô tả; s=0 trong những trường hợp còn lại. Theo định nghĩa này, nếu hai kiểu dữ liệu có thể làm cho trùng nhau bằng cách thực hiện một phép biến đổi khái quát hoá/cụ thể hoá thì độ tương tự giảm đi γ, càng cần nhiều biến đổi thì độ tương tự càng giảm nhiều hơn. Với định nghĩa 3, độ tương tự giữa hai dấu hiệu được định nghĩa như sau. Định nghĩa 4. Mức độ tương tự S (i, j) giữa hai dấu hiệu i và j được xác định bằng tích các độ tương tự của các kiểu dữ liệu thuộc tập Đầu_vào1 với Đầu_vào2 và Đầu_ra1 với Đầu_ra2 ; độ tương tự kiểu dữ liệu được tính lần lượt từ những cặp kiểu dữ liệu giống nhau nhất đến những cặp ít giống nhau hơn. 3. Kết hợp tương tự về chức năng với tương tự về dấu hiệu Sau khi có định nghĩa độ tương tự giữa dấu hiệu, bước tiếp theo là kết hợp độ tương tự dấu hiệu với độ tương tự về chức năng để quyết định độ phù hợp của thành phần thư viện. Mỗi tình huống lập trình được coi như một câu truy vấn q. Câu truy vấn q cung cấp thông tin về hai thành phần: 1) Thông tin về chức năng như mô tả ở phần 3.1. Thông tin này được biểu diễn bởi thành phần truy vấn qf; 2) Thông tin về dấu hiệu ở phần 3.2, được biểu diễn bởi câu truy vấn qs. Để kết hợp hai thành phần truy vấn này, chúng tôi sử dụng mạng Bayes như trên hình 4. Đây là mở rộng của hình 3 (phần nằm trong hình chữ nhật không liền nét bên trái). Cũng như trình bày trong phần trước, mỗi nút trên mạng tương ứng với một biến nhị phân ngẫu nhiên. Nút ds1,ds2,…dsn tương ứng với các thành phần thư viện và cho phép mô hình hoá mối liên quan theo dấu hiệu với qs. Nút di kết hợp mức độ tương tự theo chức năng sinh ra bởi qf với tương tự về dấu hiệu cho bởi qs. Nút dj được tạo thành từ nút fjd và dsi sử dụngtoán tử AND (dj bằng một khi và chỉ khi cả và fjd và dsi bằng một). Tương tự như vậy, nút q được tạo thành từ qs và qf bởi toán tử AND. d1 dn dj ... ... AND AND AND qf t1 t2 ti tm df1 dfn ... ... dfj qs ds1 dsndsj ... ... ... ... q AND Hình 4. Mô hình mạng Bayes mở rộng kết hợp chức năng và dấu hiệu Với mạng cho trên hình 2, sử dụng tính chất độc lập xác suất có điều kiện của mạng Bayes, độ tương tự của văn bản (thành phần thư viện) dj được tính như sau: , 0,1 , 0,1 , 0,1 ( | ) ( | , ) ( | , ) ( ) ( ) ( | ) ( | ) ( | ) ( | ) ( ) ( ) ( | ) ( | ) ( | ) ( ) ( ) s s s j j s s s u q j j s f s s s u q j j s f s u q P d q P d u q P q u q P u P q P df u P ds q P q u P q q P u P q P df u P ds q P q u P u P q η η η = = = = = = ∑ ∑ ∑ (4) Trong biểu thức (4), giá trị ( | )fP q u được tính theo (2), xác suất ( | )jP df u được tính theo (3), ( ) 1/ 2mP u = , ( )sP q có giá trị như nhau với mọi jd và có thể đưa vào hằng số η ở bên ngoài dấu cộng. Giá trị ( | )j sP ds q còn lại được xác định như sau ( | ) ( , )j s j sP ds q S ds q= với ( , )j sS ds q là độ tương tự về dấu hiệu giữa jds và sq theo định nghĩa 4. Việc chọn giá trị xác suất như vậy là hợp lệ do ta có 0 ( , ) 1j sS ds q≤ ≤ . Như 88 vậy, công thức (4) cho phép xác định mức độ phù hợp của thành phần thư viện kết hợp cả độ tương tự về chức năng và độ tương tự về dấu hiệu. IV. TRIỂN KHAI VÀ THỬ NGHIỆM Agent hỗ trợ lập trình được triển khai dưới dạng một plug-in cho môi trường lập trình IntelliJ IDEA [10]. IntelliJ IDEA được lựa chọn bởi hai lý do. Thứ nhất, đây là một trong những môi trường lập trình (IDE) khá phổ biến hiện nay. Thứ hai, IntelliJ IDEA cung cấp giao diện lập trình OpenAPI cho phép xây dựng plug-in trên Java để bổ sung chức năng cho môi trường. Chúng tôi đã sử dụng API này để lập trình agent. Các thành phần thư viện được lấy từ thư viện chuẩn của Java, phiên bản 1.4.1 do hãng Sun cung cấp. Thông tin về chức năng và dấu hiệu từng thành phần được lấy từ tài liệu javadoc tương ứng với thành phần đó và được chứa trong cơ sở dữ liệu. Ở đây, thông tin về dấu hiệu được lưu trữ nguyên văn, còn thông tin về chức năng lấy từ mô tả chức năng thành phần và được đánh chỉ mục dưới dạng các từ khoá. Quá trình đánh chỉ mục được thực hiện với sự trợ giúp của công cụ miễn phí Lucene ( trọng số được sử dụng khi đánh chỉ mục được xác định theo phương pháp tf-idf . Sau khi được tích hợp vào IntelliJ IDEA, agent sẽ hoạt động trong chế độ nền, theo dõi những gì diễn ra trong cửa sổ soạn thảo và hiển thị thông tin về thành phần tìm được trong một cửa sổ tool window ở phía dưới màn hình như trên hình 1,2. Để kiểm tra hoạt động của hệ thống, agent được giao cho một nhóm lập trình viên sử dụng, sau đó lấy đánh giá của những người này. Đối tượng tham gia thử nghiệm bao gồm: một số lập trình viên đang làm việc tại Trung tâm xuất khẩu phần mềm FPT –Fsoft, một số giáo viên và học viên Trung tâm đào tạo lập trình viên quốc tế FPT-Aptech. Mặc dù không có những đánh giá mang tính định lượng chính xác song kết quả phản hồi từ những người tham gia thử nghiệm cho phép rút ra một số kết luận sau: − Agent đưa ra nhiều thông tin có ích cho cả người đang học lập trình cũng như lập trình viên chuyên nghiệp. Một số lập trình viên chuyên nghiệp được giới thiệu những thành phần chưa hề biết đến trước đó. − Chất lượng thông tin trợ giúp phụ thuộc vào chất lượng chú giải mà lập trình viên sử dụng trong chương trình của mình, việc tìm kiếm theo chức năng cho kết quả quan trọng hơn tìm kiếm theo dấu hiệu. − Khác với trợ giúp kiểu “Tips of the day”, hoạt động của agent không cản trở quá trình lập trình do không bắt lập trình viên phải tạm dừng để đóng cửa sổ thông báo. Theo đánh giá chung của nhóm thử nghiệm, agent hoạt động tốt và có ích cho người lập trình. Đặc biệt, khả năng chủ động đưa ra trợ giúp rất cao. V. KẾT LUẬN Bài báo đã trình bày các giải pháp thiết kế và xây dựng agent giao diện hỗ trợ lập trình. Những tính năng chính của agent là được tích hợp vào môi trường lập trình, có khả năng chủ động gợi ý những thành phần thư viện phù hợp với tình huống đó. Việc đánh giá tình huống và tìm kiếm được thực hiện nhờ so sánh theo chức năn