Tài liệu Ứng dụng mô hình ngôn ngữ ngữ nghĩa thống kê trong gợi ý mã cho ngôn ngữ C

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ VŨ CAO NAM ỨNG DỤNG MÔ HÌNH NGÔN NGỮ NGỮ NGHĨA THỐNG KÊ TRONG GỢI Ý MÃ CHO NGÔN NGỮ C LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2015 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ VŨ CAO NAM ỨNG DỤNG MÔ HÌNH NGÔN NGỮ NGỮ NGHĨA THỐNG KÊ TRONG GỢI Ý MÃ CHO NGÔN NGỮ C Ngành: Công Nghệ Thông Tin Chuyên ngành: Kỹ Thuật Phần Mềm Mã số: 60480103 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: Tiến Sĩ Nguyễn Thị Huyền Châu HÀ NỘI - 2015 LUẬN VĂN THẠC SĨ: 60 48 10 i Lời cảm ơn Để hoàn thành luận văn này tôi đã nhận được sự giúp đỡ tận tình của các thầy cô trong trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội, các bạn bè đồng nghiệp và gia đình. Tôi xin gửi lời cảm ơn tới cô giáo TS. Nguyễn Thị Huyền Châu đã tận tình hướng dẫn, truyền đạt cho tôi kiến thức và kinh nghiệm thực tiễn quý báu. Những kiến thức này không chỉ giúp tôi thực hiện luận văn mà còn giúp tôi có hành trang quan trọng trong tương lai. Mặc dù đã cố gắng hoàn thành luận văn một cách tốt nhất, song luận văn không tránh khỏi những thiếu sót. Tôi rất mong nhận được ý kiến góp ý từ quý thầy cô và các bạn. ii Lời cam đoan Tôi xin cam đoan kết quả được trình bày trong luận văn do quá trình tự nghiên cứu dưới sự giúp đỡ của giảng viên hướng dẫn. Các nội dung nghiên cứu và kết quả trong đề tài này hoàn toàn trung thực. Các trích dẫn từ nguồn tài liệu bên ngoài đều được liệt kê rõ ràng ở phần cuối của luận văn. Hà Nội, 23 tháng 06 năm 2015 Học viên Vũ Cao Nam iii Mục Lục Lời cảm ơn ........................................................................................................................i Lời cam đoan .................................................................................................................. ii Mục Lục ......................................................................................................................... iii Danh mục các ký hiệu và chữ viết tắt.............................................................................vi Bảng thuật ngữ anh việt ................................................................................................ vii Danh sách bảng ............................................................................................................ viii Danh sách hình vẽ...........................................................................................................ix Chương 1 Mở Đầu ......................................................................................................... 1 1.1 Đặt vấn đề .............................................................................................................. 1 1.2 Mục tiêu và phương pháp luận ............................................................................... 1 1.3 Bố cục của luận văn ............................................................................................... 2 Chương 2 Cơ Sở Lý Thuyết .......................................................................................... 3 2.1 Tổng quan về mô hình ngôn ngữ ........................................................................... 3 2.1.1 Từ tố và chuỗi mã từ vựng............................................................................... 3 2.1.2 Mô hình n-gram từ vựng cho mã nguồn .......................................................... 4 2.2 Mô hình ngôn ngữ ngữ nghĩa thống kê (SLAMC) ................................................. 5 2.2.1 Từ tố và chuỗi mã ngữ nghĩa ........................................................................... 5 2.2.2 Mô hình n-gram chủ đề.................................................................................... 6 2.2.2.1 Huấn luyện mô hình n-gram chủ đề .......................................................... 6 2.2.2.2 Dự đoán với mô hình n-gram chủ đề ........................................................ 8 2.2.3 Kết hợp cặp giá trị ........................................................................................... 8 2.3 Gợi ý mã ................................................................................................................. 9 2.3.1 Ngữ cảnh gợi ý mã ........................................................................................... 9 2.3.2 Dự đoán mã liên quan .................................................................................... 10 2.3.2.1 Mở rộng các từ tố liên quan .................................................................... 10 2.3.2.2 Kiểm tra sự phù hợp ngữ cảnh ................................................................ 11 2.3.2.3 Tính điểm liên quan ................................................................................. 11 2.3.3 Biến đổi tới các biểu mẫu từ vựng ................................................................. 11 Chương 3 Áp Dụng Mô Hình Ngôn Ngữ Ngữ Nghĩa Thống Kê Trong Gợi Ý Mã Cho Ngôn Ngữ C .......................................................................................................... 12 3.1 Biến đổi mô hình SLAMC để ứng dụng cho ngôn ngữ C ................................... 12 3.1.1 Bảng nguyên tắc xây dựng nghĩa vị .............................................................. 12 iv 3.1.2 Phạm vi .......................................................................................................... 15 3.2 Cách thức xây dựng chương trình mô phỏng ....................................................... 16 3.2.1 Cây cú pháp trừu tượng (AST) ...................................................................... 17 3.2.2 Duyệt cây cú pháp trừu tượng ....................................................................... 18 3.2.2.1 Nút lưu trữ thông tin khai báo toàn cục................................................... 19 3.2.2.2 Nút lưu trữ thông tin hàm ........................................................................ 21 3.2.2.3 Nút lưu trữ thông tin có vấn đề ............................................................... 22 3.2.3 Huấn luyện mô hình n-gram chủ đề và kết hợp cặp giá trị............................ 22 3.2.4 Gợi ý mã ........................................................................................................ 23 3.3 Sơ đồ thuật toán.................................................................................................... 25 3.3.1 Sơ đồ thuật toán ở mức tổng quan ................................................................. 26 3.3.2 Sơ đồ thuật toán duyệt cây cú pháp trừu tượng ............................................. 27 3.3.3 Các sơ đồ thuật toán huấn luyện .................................................................... 28 3.3.3.1 Sơ đồ thuật toán huấn luyện n-gram ....................................................... 28 3.3.3.2 Sơ đồ thuật toán huấn luyện n-gram chủ đề ............................................ 29 3.3.3.3 Sơ đồ thuật toán huấn luyện cặp giá trị ................................................... 30 3.3.4 Sơ đồ thuật toán gợi ý mã .............................................................................. 31 3.3.4.1 Sơ đồ thuật toán mở rộng từ tố liên quan ................................................ 32 3.3.4.2 Sơ đồ thuật toán tính điểm liên quan ....................................................... 33 3.3.4.3 Sơ đồ thuật toán kiểm tra sự phù hợp ngữ cảnh ...................................... 34 3.3.4.4 Sơ đồ thuật toán biến đổi từ dạng ngữ nghĩa sang từ vựng ..................... 35 Chương 4 Thực Nghiệm .............................................................................................. 37 4.1 Môi trường thực nghiệm ...................................................................................... 37 4.1.1 Môi trường ..................................................................................................... 37 4.1.2 Chương trình mô phỏng sử dụng cho thực nghiệm ....................................... 38 4.2 Gợi ý mã ............................................................................................................... 38 4.2.1 Kiểm định khả năng gợi ý của chương trình mô phỏng ................................ 38 4.2.1.1 Mục tiêu ................................................................................................... 38 4.2.1.2 Thiết kế thực nghiệm ............................................................................... 38 4.2.1.3 Kết quả .................................................................................................... 40 4.2.2 Tích hợp SLAMC trong gợi ý mã cho ngôn ngữ C vào Eclipse .................... 43 4.2.2.1 Mục tiêu ................................................................................................... 43 4.2.2.2 Thiết kế thực nghiệm ............................................................................... 43 4.2.2.3 Kết quả .................................................................................................... 43 v 4.3 Đánh giá độ chính xác .......................................................................................... 44 4.3.1 Phân tích sự ảnh hưởng của các yếu tố .......................................................... 44 4.3.1.1 Mục tiêu ................................................................................................... 44 4.3.1.2 Thiết kế thực nghiệm ............................................................................... 44 4.3.1.3 Kết quả .................................................................................................... 44 4.3.2 So sánh độ chính xác ..................................................................................... 45 4.3.2.1 Mục tiêu ................................................................................................... 45 4.3.2.2 Thiết kế thực nghiệm ............................................................................... 45 4.3.2.3 Kết quả .................................................................................................... 45 4.3.3 Huấn luyện chéo ............................................................................................ 46 4.3.3.1 Mục tiêu ................................................................................................... 46 4.3.3.2 Thiết kế thực nghiệm ............................................................................... 46 4.3.3.3 Kết quả .................................................................................................... 46 Chương 5 Kết Luận ..................................................................................................... 48 5.1 Kết quả đạt được .................................................................................................. 48 5.2 Hướng phát triển trong tương lai ......................................................................... 49 Tài liệu tham khảo ......................................................................................................... 50 vi Danh mục các ký hiệu và chữ viết tắt Ký hiệu/Chữ viết tắt API AST GUI I/O PPA SLAMC Nội dung/Giải thích Application Program Interface Abstract Syntax Tree Graphical User Interface Input/Output Partial Program Analysis Statistical Semantic Language Model for Source Code vii Bảng thuật ngữ anh việt Tiếng Anh Token Lexical code token Lexeme Lexical code sequence Lexical n-gram Semantic code token Role Sememe Vocabulary Scope Dependency Semantic code sequence Semantic n-gram File Tiếng Việt Từ tố Từ tố mã từ vựng Từ vị Chuỗi mã từ vựng N-gram từ vựng Từ tố mã ngữ nghĩa Vai trò Nghĩa vị Tập từ vựng Phạm vi Tập phụ thuộc Chuỗi mã ngữ nghĩa N-gram ngữ nghĩa Tệp viii Danh sách bảng Bảng 2. 1. Các từ tố mã từ vựng từ đoạn mã “si = arrStudent.size();” ........................... 4 Bảng 3. 1. Nguyên tắc xây dựng nghĩa vị ..................................................................... 12 Bảng 3. 2. Ví dụ biểu diễn truy cập thuộc tính .............................................................. 15 Bảng 3. 3. Thông tin khối .............................................................................................. 16 Bảng 4. 1. Các dự án C được sử dụng trong thực nghiệm ............................................ 37 Bảng 4. 2. Phân tích sự ảnh hưởng của các yếu tố cho dự án Bash .............................. 45 Bảng 4. 3. Độ chính xác gợi ý mã ................................................................................. 46 Bảng 4. 4. Độ chính xác của huấn luyện chéo .............................................................. 47 ix Danh sách hình vẽ Hình 2. 1. Huấn luyện và dự đoán mô hình n-gram chủ đề [8] ....................................... 7 Hình 2. 2. Gợi ý mã [8] ................................................................................................... 9 Hình 3. 1. Ví dụ về phân chia khối trong thân hàm ...................................................... 16 Hình 3. 2. Danh sách cần import để gọi CDT parser [3] ............................................... 17 Hình 3. 3. Gọi Eclipse CDT parser [3] .......................................................................... 18 Hình 3. 4. Chuyển đổi đoạn mã “void testBooks(int c, char b){}” ............................... 18 Hình 3. 5. Định nghĩa struct trong C ............................................................................. 19 Hình 3. 6. Định nghĩa union trong C ............................................................................. 20 Hình 3. 7. Duyệt một hàm ............................................................................................. 21 Hình 3. 8. Tệp chưa hoàn chỉnh..................................................................................... 22 Hình 3. 9. Gợi ý mã cho tệp chưa hoàn chỉnh ............................................................... 23 Hình 3. 10. Sơ đồ thuật toán áp dụng SLAMC trong gợi ý mã cho ngôn ngữ C [8] ..... 26 Hình 3. 11. Sơ đồ thuật toán duyệt cây cú pháp trừu tượng .......................................... 27 Hình 3. 12. Sơ đồ thuật toán huấn luyện n-gram [8] ..................................................... 28 Hình 3. 13. Sơ đồ thuật toán huấn luyện n-gram chủ đề [8] ......................................... 29 Hình 3. 14. Sơ đồ thuật toán huấn luyện cặp giá trị [8] ................................................ 30 Hình 3. 15. Sơ đồ thuật toán gợi ý mã [8] ..................................................................... 31 Hình 3. 16. Sơ đồ thuật toán mở rộng từ tố liên quan [8] ............................................. 32 Hình 3. 17. Sơ đồ thuật toán tính điểm liên quan [8] .................................................... 33 Hình 3. 18. Sơ đồ thuật toán kiểm tra sự phù hợp ngữ cảnh [8] ................................... 34 Hình 3. 19. Sơ đồ thuật toán biến đổi từ dạng ngữ nghĩa sang từ vựng [8] .................. 35 Hình 4. 1. Đoạn mã chưa đầy đủ sử dụng cho thực nghiệm (1) .................................... 39 Hình 4. 2. Đoạn mã chưa đầy đủ sử dụng cho thực nghiệm (2) .................................... 40 Hình 4. 3. Kết quả gợi ý mã cho thực nghiệm (1) ......................................................... 41 Hình 4. 4. Kết quả gợi ý mã cho thực nghiệm (2) ......................................................... 42 Hình 4. 5. Tích hợp SLAMC trong gợi ý mã cho ngôn ngữ C vào Eclipse ................... 43 1 Chương 1 Mở Đầu 1.1 Đặt vấn đề Thông qua việc áp dụng mô hình ngôn ngữ thống kê n-gram từ vựng các nghiên cứu gần đây đã chỉ ra rằng mã nguồn biểu lộ một mức độ khá cao sự lặp lại (các mẫu mã – code pattern) [1]. Mô hình n-gram từ vựng do đó cũng đồng thời tỏ ra có khả năng dự đoán tốt các sự lặp lại này nhằm hỗ trợ việc gợi ý và hoàn thành mã (code suggestion and automatic code completion). Tuy nhiên, cách tiếp cận của mô hình ngram từ vựng ghi nhận các sự lặp lại dựa trên duy nhất thông tin từ vựng trong ngữ cảnh cục bộ của đơn vị mã, trong khi còn nhiều yếu tố khác cũng có thể ảnh hưởng đến độ chính xác của gợi ý và hoàn thành mã. Để nâng cấp khả năng dự đoán, một nghiên cứu mới về mô hình ngôn ngữ ngữ nghĩa thống kê cho mã nguồn (Statistical Semantic LAnguage Model for Source Code -- SLAMC) [8] đã được giới thiệu. SLAMC đã tích hợp thêm vào mô hình n-gram thông tin ngữ nghĩa bên trong các từ tố, đồng thời kết hợp ngữ cảnh cục bộ với các mối quan tâm kỹ thuật toàn cục thể hiện bởi khái niệm chủ đề, và cuối cùng, xem xét thêm cả sự kết hợp cặp giá trị của các phần tử trong chương trình. Với những đóng góp đã được thừa nhận, SLAMC đã được sử dụng để xây dựng các ứng dụng có tính thực tiễn như phương thức gợi ý mã, chuyển đổi mã nguồn. Đối với ngành công nghệ phần mềm, một trong những lợi ích to lớn mà SLAMC mang lại là giúp chúng ta đưa ra một sự gợi ý chính xác và rút ngắn thời gian trong việc đưa ra các token (từ tố) tiếp theo trong mã nguồn. Ngày nay, có rất nhiều chương trình, ứng dụng hệ thống được lập trình sử dụng ngôn ngữ C bởi vì C được đánh giá là ngôn ngữ có hiệu quả. Ngoài ra, đây còn là một trong những ngôn ngữ phổ biến được đưa vào giảng dạy trong khoa học máy tính. Vì vậy, áp dụng SLAMC cho ngôn ngữ C là một nhiệm vụ cần được nghiên cứu. Nhận thấy ý tưởng này có tính khả thi, dưới sự hướng dẫn của tiến sĩ Nguyễn Thị Huyền Châu, tôi đã quyết định tìm hiểu áp dụng mô hình ngôn ngữ ngữ nghĩa thống kê trong gợi ý mã cho ngôn ngữ C. 1.2 Mục tiêu và phương pháp luận Luận văn sẽ xây dựng một chương trình mô phỏng mô hình ngôn ngữ ngữ nghĩa thống kê trong gợi ý mã cho ngôn ngữ C, tích hợp chương trình mô phỏng vào Eclipse và đánh giá độ chính xác sự gợi ý dựa trên chương trình mô phỏng này. Để cài đặt chương trình, luận văn sẽ thực hiện các bước như xây dựng bảng chuyển đổi nghĩa vị, phương pháp lưu trữ phạm vi, chuyển đổi mã nguồn C sang cây cú pháp trừu tượng, 2 duyệt cây cú pháp trừu tượng này nhằm lấy các thông tin cần thiết để huấn luyện và tính toán sự kết hợp của các yếu tố (ngữ nghĩa, chủ đề, cặp giá trị) để đưa ra danh sách các gợi ý phù hợp nhất. Sau khi chương trình được hoàn tất, việc đánh giá tính chính xác sẽ được thực hiện thông qua phương pháp đo lường độ chính xác top-k [7] để chỉ ra rằng SLAMC có độ chính xác tốt hơn so với mô hình n-gram từ vựng khi áp dụng cho ngôn ngữ C. 1.3 Bố cục của luận văn Luận văn được trình bày theo bố cục gồm 5 chương: Chương 1: Mở đầu. Giới thiệu khái quát vấn đề nghiên cứu, phương pháp luận và bố cục của luận văn. Chương 2: Cơ sở lý thuyết. Trình bày các khái niệm, định lý, thuật toán cần được hiểu rõ để áp dụng mô hình ngôn ngữ ngữ nghĩa thống kê trong gợi ý mã cho ngôn ngữ C. Chương 3: Áp dụng mô hình ngôn ngữ ngữ nghĩa thống kê trong gợi ý mã cho ngôn ngữ C. Trong phần này luận văn sẽ trình bày các bước để cài đặt SLAMC cho ngôn ngữ C. Đầu tiên, luận văn sẽ đưa ra bảng nguyên tắc xây dựng nghĩa vị và phương pháp lưu trữ phạm vi cho ngôn ngữ C. Bên cạnh đó, cách thức chuyển đổi từ tệp mã nguồn C sang cây cú pháp trừu tượng được trình bày. Tiếp theo, các công việc cần cho gợi ý mã được chỉ ra như duyệt cây cú pháp, huấn luyện mô hình n-gram chủ đề, kết hợp cặp giá trị và cách thức đưa ra danh sách các gợi ý phù hợp nhất. Cuối cùng, các sơ đồ thuật toán chính trong chương trình mô phỏng được đưa ra với mục đích làm rõ hướng cài đặt chương trình. Chương 4: Thực nghiệm. Trong chương này luận văn trình bày các thực nghiệm liên quan đến gợi ý mã và đánh giá độ chính xác khi áp dụng SLAMC cho ngôn ngữ C. Thứ nhất, xem xét gợi ý mã đối với các tệp mã nguồn chưa đầy đủ nhằm thấy được bước đầu chương trình mô phỏng đã đưa ra những gợi ý chính xác. Sau đó, phương pháp đo lường độ chính xác theo top-k [7] được áp dụng để thể hiện mức độ tốt hơn của SLAMC so với mô hình n-gram từ vựng. Chương 5: Kết luận. Tóm tắt những kết quả thu được và hướng phát triển trong tương lai. 3 Chương 2 Cơ Sở Lý Thuyết 2.1 Tổng quan về mô hình ngôn ngữ Các mô hình ngôn ngữ thống kê được sử dụng để ghi lại các quy tắc trong ngôn ngữ tự nhiên bởi việc gán xác suất xuất hiện các đơn vị ngôn ngữ học thí dụ như các từ, các cụm từ, các câu, và các tài liệu. Bởi vì một đơn vị ngôn ngữ học được trình bày như một chuỗi của một hoặc nhiều các ký tự cơ bản, mô hình hóa ngôn ngữ được thực thi thông qua việc tính xác suất của các chuỗi. Để tính xác suất của các chuỗi, một cách tiếp cận mô hình hóa cho rằng mỗi chuỗi được sinh ra bởi một tiến trình của mô hình tương ứng. Các khái niệm cơ bản sẽ được trình bày chi tiết như dưới đây. Mô hình ngôn ngữ (Language Model). Một mô hình ngôn ngữ L là một thống kê, mô hình có khả năng sinh ra được định nghĩa thông qua ba thành phần: một tập từ vựng V của các đơn vị cơ bản, một tiến trình G có khả năng sinh ra các phần tử của một chuỗi, và một hàm có khả năng xảy ra P(s|L). P(s|L) là xác suất một chuỗi s của của các phần tử trong V được sinh ra bởi mô hình ngôn ngữ L sau tiến trình G [8]. Khi ngữ cảnh thảo luận liên quan đến mô hình ngôn ngữ L, chúng ta sử dụng P(s) để biểu diễn P(s|L) và gọi là xác suất sinh của chuỗi s. Theo như đó, một mô hình ngôn ngữ có thể đơn giản được cân nhắc để có một sự phân phối xác suất của mỗi chuỗi có thể. P(s) có thể được ước lượng từ một tập hợp được cho của các chuỗi. 2.1.1 Từ tố và chuỗi mã từ vựng Các mô hình ngôn ngữ thống kê đã được áp dụng tới công nghệ phần mềm, thí dụ như trong gợi ý và hoàn thành mã. Để áp dụng một mô hình ngôn ngữ thống kê cho mã nguồn, đầu tiên chúng ta cần định nghĩa tập từ vựng. Một tập từ vựng có thể được cấu tạo thông qua việc thực thi phân tích từ vựng trên mã nguồn (như một chuỗi các ký tự). Các từ vị của các từ tố được thu thập như các đơn vị cơ bản trong tập từ vựng. Mã nguồn đầu vào được trình bày như một chuỗi của các từ vựng. Dưới đây là các định nghĩa về từ tố mã từ vựng, từ vị, và chuỗi mã từ vựng. Từ tố mã từ vựng (Lexical Code Token). Một từ tố mã từ vựng là một đơn vị trong đại diện văn bản của mã nguồn và được kết hợp với một loại từ tố từ vựng khác bao gồm định danh, từ khóa, hoặc ký hiệu, được chỉ định bởi ngôn ngữ lập trình [8]. Từ vị (Lexeme). Từ vị của một từ tố là một chuỗi của các ký tự đại diện giá trị từ vựng cho từ tố này [8]. Chuỗi mã từ vựng (Lexical Code Sequence). Một chuỗi mã từ vựng là một chuỗi của các từ tố mã từ vựng liên tiếp đại diện một phần của mã nguồn [8]. 4 Ví dụ, sau khi phân tích từ vựng, đoạn mã “si = arrStudent.size();” được đại diện bởi một chuỗi mã từ vựng của 8 từ tố với các loại từ tố của chúng và các từ vị được chỉ ra trong bảng 2.1. si, arrStudent, và size là ba từ tố định danh, trong khi các từ tố khác có các kiểu ký hiệu khác nhau. Trong phân tích từ vựng, không có thông tin ngữ nghĩa xuất hiện. Ví dụ, arrStudent không được ghi nhận như một biến ArrayList, và size không được ghi nhận như tên phương thức trong lớp ArrayList. Bảng 2. 1. Các từ tố mã từ vựng từ đoạn mã “si = arrStudent.size();” Từ vị si = arrStudent . size ( ) ; Loại từ tố Định danh Ký hiệu Định danh Ký hiệu Định danh Ký hiệu Ký hiệu Ký hiệu 2.1.2 Mô hình n-gram từ vựng cho mã nguồn Một mô hình n-gram là một mô hình ngôn ngữ với hai giả định. Đầu tiên, mô hình n-gram cho rằng một chuỗi có thể được sinh ra từ trái qua phải. Thứ hai, xác suất sinh của một từ vựng trong một chuỗi phụ thuộc duy nhất trên ngữ cảnh cục bộ. Sự phụ thuộc được mô hình hóa dựa trên sự xuất hiện của các chuỗi từ vựng với chiều dài giới hạn. Một chuỗi của n các từ vựng được gọi là n-gram. Khi n được cố định tại 1, 2 hoặc 3 mô hình được gọi là unigram, bigram, hoặc trigram. N-gram từ vựng (Lexical n-gram). Từ vị của một chuỗi n các từ tố mã liên tiếp được gọi là một n-gram từ vựng [8]. Các giả định là có lý cho mã nguồn. Đó là, từ tố mã tiếp theo có thể phụ thuộc và được dự đoán dựa trên các từ tố mã đã viết trước đó. Ví dụ, trong một tệp mã nguồn, chuỗi mã “for(int i = 0 ; i < n;” được xem xét như ngữ cảnh cục bộ của từ tố tiếp theo. Đoạn mã này có thể ghi nhận như một vòng lặp for với i như một biến lặp, và theo như đó từ tố mã tiếp theo là i. Với giả định của việc sinh các từ tố từ trái qua phải, xác suất sinh của chuỗi mã S = S1S2….Sm được tính như sau: P(S) = P(S1).P(S2|S1).P(S3|S1S2)…P(Sm|S1…Sm-1) (2.1) Trong đó, Si là từ tố thứ i trong chuỗi mã S với i = ̅̅̅̅̅̅ 1, 𝑚. Đây là xác suất sinh của một chuỗi mã được tính thông qua mỗi từ tố của nó. Theo đó, một mô hình ngôn ngữ cần tính toán tất cả xác suất điều kiện có thể P(c|p) ở đó c là một từ tố mã và p là một chuỗi mã. Theo công thức 2.1, mô hình ngôn ngữ phải có một lượng bộ nhớ vô cùng lớn để có thể lưu trữ hết xác suất của tất cả các chuỗi có độ dài nhỏ hơn m. Rõ ràng, điều này là không thể khi m có thể tiến tới vô cùng. Để có thể tính được xác suất của văn bản với lượng bộ nhớ chấp nhận được, ta sử dụng giả định Markov, xác suất điều kiện P(c|p) được tính như P(c|p) = P(c|Ɩ) trong đó c là một từ tố mã và Ɩ là một chuỗi 5 con được tạo ra bởi n-1 từ tố trước đó của p. Với phép tính xấp xỉ này, một mô hình duy nhất cần tính toán và lưu trữ xác suất điều kiện bao gồm nhiều nhất n các từ tố liên tiếp. P(c|Ɩ) thường được ước lượng như sau: P(c|Ɩ) ≃ 𝑐𝑜𝑢𝑛𝑡(𝑙𝑒𝑥(Ɩ,𝑐))+ ∝ 𝑐𝑜𝑢𝑛𝑡(𝑙𝑒𝑥(Ɩ))+𝑉.∝ (2.2) Ở đây, lex là hàm xây dựng nên từ vị của một chuỗi mã. Ví dụ, chuỗi mã “i < n” có thể xuất hiện trong một phát biểu for hoặc if. Các chuỗi từ vị giống nhau sẽ được tạo ra và được đếm như sự xuất hiện của các chuỗi mã giống nhau. V là kích cỡ của tập từ vựng, ∝ là một giá trị làm mịn cho trường hợp các giá trị đếm nhỏ. 2.2 Mô hình ngôn ngữ ngữ nghĩa thống kê (SLAMC) SLAMC là một mô hình ngôn ngữ ngữ nghĩa thống kê được thiết kế cho mã nguồn. SLAMC mã hóa thông tin ngữ nghĩa của các từ tố bên trong các đơn vị ngữ nghĩa cơ bản, và ghi lại các quy tắc của chúng. Bên cạnh đó, SLAMC kết hợp ngữ cảnh cục bộ với mối quan tâm toàn cục cũng như kết hợp cặp giá trị trong tiến trình mô hình hóa. 2.2.1 Từ tố và chuỗi mã ngữ nghĩa Từ tố mã ngữ nghĩa (Semantic Code Token). Một từ tố mã ngữ nghĩa là một từ tố mã từ vựng với thông tin ngữ nghĩa được kết hợp bao gồm định danh (ID), vai trò, kiểu dữ liệu, nghĩa vị, phạm vi, cấu trúc và các sự phụ thuộc dữ liệu [8]. Vai trò (Role). Vai trò của một từ tố mã ngữ nghĩa đề cập tới vai trò của từ tố trong một chương trình với khía cạnh một ngôn ngữ lập trình [8]. Các vai trò điển hình bao gồm: kiểu dữ liệu, biến, toán tử, từ khóa, lời gọi hàm, khai báo hàm. Ví dụ, trong “arrStudent.size()”, sau khi phân tích ngữ nghĩa, arrStudent ghi nhận như một từ tố mã ngữ nghĩa với vai trò của một biến, trong khi vai trò của size là một lời gọi hàm. Nghĩa vị (Sememe). Nghĩa vị của một từ tố mã ngữ nghĩa là một biểu diễn được cấu trúc đại diện giá trị hoặc thông tin ngữ nghĩa, bao gồm vai trò và kiểu dữ liệu của từ tố [8]. Tập từ vựng (Vocabulary). Một tập từ vựng là một tập hợp các nghĩa vị riêng biệt của tất cả các từ tố mã ngữ nghĩa [8]. Phạm vi (Scope). Một phạm vi được kết hợp với từ tố mã ngữ nghĩa nhận dạng khối chứa từ tố [8]. Tập phụ thuộc (Dependency). Tập phụ thuộc của một từ tố mã ngữ nghĩa t là một tập hợp các ID của các từ tố mã khác có các sự phụ thuộc cấu trúc hoặc dữ liệu với t [8]. Các sự phụ thuộc cấu trúc được định nghĩa như các quan hệ cha con trong một cây cú pháp trừu tượng. Các sự phụ thuộc dữ liệu được định nghĩa giữa các phần tử chương trình và được tính toán thông qua việc phân tích dữ liệu trên các biến. 6 Chuỗi mã ngữ nghĩa (Semantic Code Sequence). Một chuỗi mã ngữ nghĩa là một chuỗi của các từ tố mã ngữ nghĩa [8]. N-gram ngữ nghĩa (Semantic n-gram). Nghĩa vị của một chuỗi mã ngữ nghĩa có cỡ n, được gọi là một n-gram ngữ nghĩa, là chuỗi của các nghĩa vị của các từ tố tương ứng [8]. 2.2.2 Mô hình n-gram chủ đề Dựa vào ý tưởng từ mô hình chủ đề Wallach [5], SLAMC đã phát triển mô hình n-gram chủ đề tích hợp thông tin của ngữ cảnh cục bộ (thông qua n-gram) và các mối quan tâm toàn cục (thông qua các chủ đề). Ý tưởng chính là xác suất một từ tố c xuất hiện tại một vị trí được ước lượng đồng thời dựa trên thông tin toàn cục k và chuỗi cục bộ của n-1 từ tố phía trước. Mô hình n-gram chủ đề cho rằng một tập mã nguồn cơ sở (codebase) có K chủ đề (tương ứng với các mối quan tâm hoặc chức năng), bởi vì một tệp mã nguồn có thể bao gồm một vài mối quan tâm, SLAMC cho phép một chuỗi mã chứa tất cả K chủ đề thường với tỷ lệ phần trăm khác nhau. SLAMC trình bày các chủ đề của một chuỗi mã p như một phân phối đa thức θ được lấy mẫu từ sự phân phối Dirichlet (Dir(α, K)). θ được gọi là tỷ lệ chủ đề của p và θk là tỷ lệ chủ đề của k trong p. Tỷ lệ chủ đề của k có thể được đo lường thông qua tỷ lệ của số các từ tố thuộc chủ đề k trên tổng số các từ tố. Ví dụ, một chuỗi mã đại diện cho một tệp mã nguồn có thể có 30% các từ tố về I/O, 40% về xử lý chuỗi, và 30% về GUI. Mỗi từ tố trong chuỗi mã được gán với một chủ đề. Trong SLAMC, xác suất sinh của từ tố mã c phụ thuộc trên bài tập chủ đề k cũng như trên ngữ cảnh cục bộ Ɩ. Sự phụ thuộc này được mô hình bởi phân phối đa thức φk, Ɩ (được gọi là phân phối từ tố), là một mẫu của phân phối Dirichlet (Dir(β,V)). Sau đó, để tính xác suất sinh P(c|p) cho bất kỳ từ tố mã được cho c và chuỗi mã p, chúng ta cần thực hiện hai bước sau:  Huấn luyện, chính xác là ước lượng sự phân phối đa thức φk, Ɩ cho tất cả các chủ đề có thể k và ngữ cảnh cục bộ Ɩ từ một codebase huấn luyện.  Dự đoán, chính xác là ước lượng sự phân phối đa thức θ cho p để tính P(c|p). 2.2.2.1 Huấn luyện mô hình n-gram chủ đề Hình 2.1 minh họa thuật toán huấn luyện. Đầu vào bao gồm một codebase B, chứa một tập hợp các tệp mã nguồn, và các tham số được định nghĩa trước như số các chủ đề K, các tham số làm mịn α và β, kích cỡ tối đa của n-gram N, và số các phép lặp huấn luyện Nt. Đầu ra bao gồm tập từ vựng V chứa tất cả các từ tố mã được thu thập, sự phân phối từ tố φk, Ɩ cho mỗi chủ đề k và mỗi n-gram Ɩ có thể. Thêm vào đó, mỗi tệp mã nguồn được đại diện như một chuỗi mã s, đầu ra cũng bao gồm tỷ lệ chủ đề θ và bài tập chủ đề zi cho mỗi vị trí i trong s. 7 1 2 3 4 5 6 7 8 9 function Train(B, α, β, K, N, Nt) for each source file f in training codebase B extract its semantic code sequence s collect available sememes into V randomly initiate its θ, z loop Nt times for each available topic k and n-gram Ɩ for each token c ϵ V 𝑐𝑜𝑢𝑛𝑡(𝑙,𝑐,𝑘)+ 𝛽 φk, l(c) = 𝑐𝑜𝑢𝑛𝑡(𝑙,𝑘)+𝐾𝑉𝛽 10 for each code sequence s in B 11 [θ, z] = Estimate(s, φ) 12 return φ 13 14 function Estimate(s, φ) 15 Repeat 16 for each position i in s 17 sample zi where P (zi = k) = θk . φk, Sn, i (si) 18 for each topic k 𝑐𝑜𝑢𝑛𝑡(𝑧𝑖=𝑘)+ ∝ 19 θk ≃ 𝑙𝑒𝑛𝑔𝑡ℎ(𝑠)+𝐾∝ 20 21 until θ is stable return θ, z Hình 2. 1. Huấn luyện và dự đoán mô hình n-gram chủ đề [8] Đầu tiên, thuật toán huấn luyện phân tích cú pháp tất cả các tệp mã nguồn trong codebase, và xây dựng một chuỗi mã ngữ nghĩa cho mỗi tệp. Sau đó, thu thập tất cả các từ tố mã bên trong tập từ vựng V và khởi tạo ngẫu nhiên các biến tiềm ẩn (ví dụ: θ, φ, z). Tiếp theo, thuật toán thực hiện hai pha xử lý như sau: Pha 1: SLAMC sử dụng các bài tập chủ đề đã tồn tại của tất cả các chuỗi để ước lượng phân phối từ tố φk, Ɩ cho mỗi chủ đề có thể k và n-gram Ɩ. φk, Ɩ được tính theo công thức tại dòng 9 trong hình 2.1: φk, l(c) = 𝑐𝑜𝑢𝑛𝑡(𝑙,𝑐,𝑘)+ 𝛽 𝑐𝑜𝑢𝑛𝑡(𝑙,𝑘)+𝐾𝑉𝛽 (2.3) Trong công thức này, hàm count(Ɩ, c, k) đếm mỗi i có thể trong mỗi chuỗi s ở đó si = c, sn, i = Ɩ và zi = k, chính xác là từ tố tại vị trí i là c được gán tới chủ đề k, và n-1 từ tố trước đấy tạo nên chuỗi Ɩ. Tương tự, count(Ɩ, k) đếm các vị trí nhưng không yêu cầu si = c. Tham số dương β được thêm tới tất cả các đếm với mục đích làm mịn cho sự tính toán trong các vòng lặp sau. Pha 2: SLAMC sử dụng các phân phối từ tố để ước lượng tỷ lệ chủ đề θ và bài tập chủ đề z cho mỗi chuỗi mã s (mỗi chuỗi s đại diện cho một tệp mã nguồn) trong codebase (dòng 11, 14-21 trong hình 2.1). Trước tiên, các chủ đề được lấy mẫu và gán cho mỗi 8 vị trí i trong s. Xác suất chủ đề k được gán tới vị trí i được tính như dòng 17 trong hình 2.1: P(zi = k|s, θ, φ) ~ θk . φk, Sn,i (Si) (2.4) Ở đây si là từ tố của s tại vị trí i và si, n là chuỗi của n-1 từ tố trước i trong s. Ngay khi các chủ đề được gán tất cả các vị trí, tỷ lệ chủ đề θ được ước tính lại như dòng 19 trong hình 2.1: θk ≃ 𝑐𝑜𝑢𝑛𝑡(𝑧𝑖=𝑘)+ ∝ 𝑙𝑒𝑛𝑔𝑡ℎ(𝑠)+𝐾∝ (2.5) SLAMC đếm số các từ tố được gán tới chủ đề k, và ước lượng xấp xỉ tỷ lệ của chủ đề k dựa trên tỷ lệ của số các từ tố thuộc chủ đề k so với độ dài của chuỗi s. Tham số dương α được thêm tới tất cả các đếm với mục đích làm mịn. 2.2.2.2 Dự đoán với mô hình n-gram chủ đề Thuật toán dự đoán có đầu vào là một mô hình n-gram chủ đề được huấn luyện φ (φ chứa các phân phối từ tố cho tất cả các n-gram và các chủ đề) và một chuỗi mã p. Đầu tiên sử dụng hàm Estimate (Hình 2.1) để ước lượng tỷ lệ chủ đề θ của p. Sau đó, ước lượng xác suất sinh P(c|p) cho bất kỳ khả năng xuất hiện từ tố c và chuỗi pn của n1 từ tố trước của p, sử dụng công thức sau: P(c|p) = maxn (∑k θk . φk,pn (c)) (2.6) 2.2.3 Kết hợp cặp giá trị SLAMC sử dụng một xác suất điều kiện để mô hình hóa yếu tố kết hợp cặp giá trị. P(c|b) là xác suất mà c sẽ xuất hiện như từ tố tiếp theo nếu một từ tố b đã xuất hiện trước đấy. Xác suất này được ước tính như sau: P(c|b) = 𝑐𝑜𝑢𝑛𝑡(𝑐,𝑏) 𝑐𝑜𝑢𝑛𝑡(𝑏) (2.7) Để tránh các cặp cùng xuất hiện bởi sự thay đổi, SLAMC chỉ xem xét một cặp từ tố (c, b) nếu chúng có sự phụ thuộc dữ liệu. Ví dụ, nếu hai lời gọi hàm open và close được thực thi trên cùng tệp, chúng được đếm. Nếu chúng được sử dụng trên các tệp khác nhau, sự xuất hiện cùng nhau của chúng có thể không liên quan về ngữ nghĩa, vì thế không được đếm. Để giảm chi phí lưu trữ và tính toán, SLAMC không tính và lưu trữ xác suất P(c|b) cho tất cả các cặp (c, b). Thay vào đó, SLAMC xem xét duy nhất các từ tố cho các cấu trúc điều khiển (bao gồm: rẽ nhánh, lặp) và các thực thể API (bao gồm: các lớp, phương thức, và các trường). SLAMC cũng xem xét duy nhất các cặp từ tố bên trong phạm vi của một phương thức. Có thể một vài từ tố mã b kết hợp với c trong một chuỗi mã p. SLAMC chỉ chọn một từ tố mã với xác suất điều kiện P(c|p) cao nhất. 9 2.3 Gợi ý mã Thay vì gợi ý mã trong một mẫu, SLAMC gợi ý một danh sách tuần tự các từ tố được xếp loại thích hợp nhất tới ngữ cảnh của mã hiện thời và có khả năng xuất hiện tiếp theo. 2.3.1 Ngữ cảnh gợi ý mã Một từ tố được gợi ý sẽ hoàn thành mã tại vị trí hiện thời để tạo nên một đơn vị mã có ý nghĩa và xuất hiện như từ tố tiếp theo. Hiện tại SLAMC đã thực hiện các nguyên tắc để định nghĩa một đơn vị mã có ý nghĩa trong thuật ngữ của một sự truy cập thành viên, một lời gọi phương thức, một biểu thức trung tố, hoặc một biểu thức điều kiện. Ví dụ, nếu ngữ cảnh mã được ghi nhận như một biểu thức bậc hai chưa đầy đủ, thí dụ như trong “y -”, các gợi ý sẽ là một biểu thức với một kiểu dữ liệu tương thích với y. Nếu ngữ cảnh là một lời gọi phương thức chưa đầy đủ, một gợi ý sẽ là một biểu thức với kiểu tương thích cho đối số tiếp theo. Nếu không phù hợp với bất kỳ ngữ cảnh nào được chỉ định trước, từ tố với xác suất cao nhất được gợi ý. 1 function Recommend(CurrentCode F, NGramTopicModel φ) 2 s = BuildSequence(F) //sequence of semantic code tokens 3 θ = EstimateNGramTopic(s, φ) //topic proportion of F 4 p = GetCodePriorEditingPoint(s, edpos) 5 L = search(p, θ) 6 for each q ϵ L 7 lex[q] = Unparse(q) 8 u = UserSelect(lex) 9 Fillin(u) 10 11 function Search(p, θ) 12 L = new sorted list of size topSize, Q = new queue 13 Q.add(“”, 1) //empty sequence, score = 1 14 Repeat 15 q = Q.next() 16 if length(q) ≥ maxDepth then continue 17 C(q) = ExpandableTokens(p, q) 18 for each c ϵ C(q) Q.add(qc) 19 if ContextFit(p, q) then L.add(q, Score(q, p, θ, φ)) 20 until Q is empty 21 if L is empty then add the top relevant tokens to L 22 return L Hình 2. 2. Gợi ý mã [8] Thuật toán gợi ý mã của SLAMC trong hình 2.2 gồm ba bước. Trong bước đầu tiên (các dòng 2-3), SLAMC phân tích mã trong phương thức hiện thời và sản xuất chuỗi mã ngữ nghĩa tương ứng. Bởi vì mã hiện thời có thể chưa hoàn thành hoặc không đúng cú pháp, SLAMC sử dụng công cụ PPA để phân tích tệp mã nguồn và sau