ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

VŨ QUANG HƢNG

Nghiên cứu ứng dụng ngôn ngữ F* trong
phát triển phần mềm

LUẬN VĂN THẠC SĨ 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Ũ QUANG HƢNG

Nghiên cứu ứng dụng ngôn ngữ F* trong
phát triển phần mềm

Ngành:
Chuyên ngành:
Mã số:

Công nghệ thông tin
Kỹ thuật phần mềm
60480103

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC:

PGS. TS. Trƣơng Anh Hoàng
NGƢỜI ĐỒNG HƢỚNG DẪN KHOA HỌC: TS. Nguyễn Nhƣ Sơn

Hà Nội – 2015


3

LỜI CAM ĐOAN
Tôi xin cam đoan luận văn này là công trình nghiên cứu của cá nhân tôi, dƣới sự
hƣớng dẫn trực tiếp từ phía PGS.TS. Trƣơng Anh Hoàng và TS. Nguyễn Nhƣ Sơn. Các số
liệu, nội dung tham khảo đƣợc trích dẫn có nguồn gốc rõ ràng, tuân thủ tôn trọng quyền
tác giả. Kết quả cuối cùng đạt đƣợc của luận văn là thành quả của quá trình nghiên cứu
bản thân, chƣa từng đƣợc công bố dƣới bất kỳ hình thức nào.
Tôi xin chịu trách nhiệm về nghiên cứu trong luận văn.

Hà Nội, ngày 28 tháng 5 năm 2015
Tác giả

Vũ Quang Hƣng


4

LỜI CẢM ƠN
Để hoàn thành đề tài luâ ̣n văn này , bên ca ̣nh sƣ̣ chủ đô ̣ng cố gắ ng của bản thân , tôi
đã nhâ ̣n đƣơ ̣c sƣ̣ ủng hô ̣ và giúp đỡ nhiê ̣t tin
, cá nhân trong và ngoài
̀ h tƣ̀ các tâ ̣p thể
trƣờng.

Qua đây , cho phép tôi đƣơ ̣c bày tỏ lòng cảm ơn sâu sắ c tới thầ y giáo
PGS.TS.Trƣơng Anh Hoàng , giảng viên bộ môn Công nghệ phần mềm trƣờng Đại học
công nghê ̣ – Đa ̣i ho ̣c Quố c gia Hà Nô ̣i , ngƣời đã trƣ̣ c tiế p đô ̣ng viên , đinh
̣ hƣớng và
hƣớng dẫn tâ ̣n tiǹ h trong quá trin
̀ h ho ̣c tâ ̣p và hoàn thành đề tài luâ ̣n văn này .
Đồng kính gửi lời cảm ơn đến tập thể các thầy , cô giáo trong trƣờng Đa ̣i ho ̣c Công
Nghê ̣ – Đa ̣i ho ̣c Quố c gia Hà Nô ̣i đã trau dồ i kiế n thƣ́c cho tôi , điề u đó là nề n tảng quí
báu góp phần to lớn trong quá trình vận dụng vào hoàn thiện luận văn .
Cuố i cùng, tôi xin đƣơ ̣c gƣ̉i lòng biế t ơn sâu sắ c đế n gia đin
̀ h , bạn bè, đồ ng nghiê ̣p
đã ta ̣o điề u kiê ̣n về vâ ̣t chấ t cũng nhƣ tinh thầ n , luôn sát cánh bên tôi , đô ̣ng viên giúp tôi
yên tâm ho ̣c tâ ̣p và kế t thúc khóa ho ̣c .
Xin chân thành cảm ơn!

Tác giả

Vũ Quang Hƣng


5

MỤC LỤC
LỜI CAM ĐOAN ................................................................................................................ 3
LỜI CẢM ƠN ...................................................................................................................... 4
MỤC LỤC ........................................................................................................................... 5
DANH MỤC CÁC KÝ HIỆU, THUẬT NGỮ, CHỮ VIẾT TẮT ...................................... 7
DANH MỤC CÁC BẢNG .................................................................................................. 8
DANH MỤC CÁC HÌNH VẼ ............................................................................................. 9
PHẦN MỞ ĐẦU ............................................................................................................... 10

Tính cấp thiết của đề tài .................................................................................................. 10
Mục tiêu của luận văn ..................................................................................................... 10
Công cụ phần mềm.......................................................................................................... 10
Phƣơng pháp nghiên cứu................................................. Error! Bookmark not defined.
Bố cục luận văn ............................................................... Error! Bookmark not defined.
CHƢƠNG 1: TỔNG QUAN VỀ LẬP TRÌNH HÀM ...... Error! Bookmark not defined.
1.1 Giới thiệu chung về ngôn ngữ lập trình hàm ............ Error! Bookmark not defined.
1.2 Các đặc điểm nổi bật của ngôn ngữ lập trình hàm .... Error! Bookmark not defined.
1.3 Sự phổ biến của ngôn ngữ lập trình hàm .................. Error! Bookmark not defined.
1.4 Giới thiệu tổng quan về ngôn ngữ lập trình hàm F# . Error! Bookmark not defined.
CHƢƠNG 2: NGHIÊN CỨU LÝ THUYẾT VỀ NGÔN NGỮ F* . Error! Bookmark not
defined.
2.1. Giới thiệu chung ....................................................... Error! Bookmark not defined.
2.1.1. Giới thiệu về ngôn ngữ F* ................................. Error! Bookmark not defined.
2.1.2. Giới thiệu về kiểu phụ thuộc, hệ thống kiểu phụ thuộc ....Error! Bookmark not
defined.
2.2. Các đặc điểm nổi bật của ngôn ngữ F* .................... Error! Bookmark not defined.
2.2.1. Ngôn ngữ tự chứng thực F* ............................... Error! Bookmark not defined.
2.2.2. Trình biên dịch từ F* sang mã JavaScript ......... Error! Bookmark not defined.
2.3. Các khái niệm cơ bản khi lập trình với F* ............... Error! Bookmark not defined.


6
2.3.1. Các định nghĩa kiểu và loại thƣờng dùng trong F* ..........Error! Bookmark not
defined.
2.3.2. Các khái niệm chung về khai báo kiểu trong F* Error! Bookmark not defined.
2.3.3. Lý thuyết về tập hợp: ......................................... Error! Bookmark not defined.
2.3.4. Định nghĩa, sử dụng mảng dữ liệu trong F* ...... Error! Bookmark not defined.
2.3.5. Kiểu của số tự nhiên (NAT) .............................. Error! Bookmark not defined.
2.3.6. Chứng minh tính chất cơ bản trong F* .............. Error! Bookmark not defined.

2.3.7. Loại suy luận và các ảnh hƣởng tới tính toán .... Error! Bookmark not defined.
2.3.8. Sử dụng F* lập trình với các bài toán đơn giản . Error! Bookmark not defined.
2.3.9. Chứng minh bổ đề (Lemmas) ............................ Error! Bookmark not defined.
2.3.10. Chứng minh tính kết thúc của chƣơng trình trong F* (Proving termination)
Error! Bookmark not defined.
2.4. Kết luận chƣơng ....................................................... Error! Bookmark not defined.
CHƢƠNG 3: BÀI TOÁN ỨNG DỤNG ........................... Error! Bookmark not defined.
3.1. Ứng dụng F* vào các bài toán lập trình ................... Error! Bookmark not defined.
3.1.1. Ứng dụng trong bài toán sắp xếp mảng nổi bọt (Buble sort) . Error! Bookmark
not defined.
3.1.2. Ứng dụng trong lập trình sắp xếp mảng nhanh (Quick sort) .. Error! Bookmark
not defined.
3.1.3. Ứng dụng trong cái bài toán làm việc với các tập tin, thƣ mục ................. Error!
Bookmark not defined.
3.2. Ứng dụng F* trong bài toán tính tổng tài nguyên sử dụng chƣơng trình ........ Error!
Bookmark not defined.
3.2.1. Giới thiệu bài toán ............................................. Error! Bookmark not defined.
3.2.2. Giải quyết bài toán ............................................. Error! Bookmark not defined.
3.2.3. Tính toán giá trị mức giới hạn trên tổng chi phí tài nguyên cho chƣơng trình
Error! Bookmark not defined.
KẾT LUẬN ....................................................................... Error! Bookmark not defined.
TÀI LIỆU THAM KHẢO ................................................................................................. 11


7
PHỤ LỤC. CÁC CÔNG CỤ HỖ TRỢ CÀI ĐẶT THỰC NGHIỆM .....Error! Bookmark
not defined.


8


DANH MỤC CÁC KÝ HIỆU, THUẬT NGỮ, CHỮ VIẾT TẮT
CHỮ VIẾT TẮT, THUẬT
NGỮ, KÝ HIỆU

STT

GIẢI NGHĨA
CHỮ VIẾT TẮT

1

F*

2

STM (Software
Transactional Memory)

3

TFJ string

Ngôn ngữ lập trình Fstar
Bộ nhớ giao tác phần mềm, một giải pháp viết
các chƣơng trình tƣơng tranh, thay cho cơ chế
đồng bộ dựa trên khóa.
Là một ngôn ngữ mở rộng của FJ tích hợp mô
hình bộ nhớ giao tác phần mềm.
THUẬT NGỮ


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Type System
Transaction
Thread
Binary
Type checker
Strongly typed
AST (Abstract Syntax Tree)
Onacid
Commit
Lock-based synchronization
Nested transactions
Multi-threaded
Join

Merge
Spawn

16

Joint commits

17

Syntax

Hệ thống kiểu
Giao tác
Luồng
Mã nguồn chƣơng trình
Bộ kiểm tra kiểu
Kiểu mạnh
Cây cú pháp trừu tƣợng
Trạng thái mở một giao tác
Trạng thái kết thúc một giao tác
Đồng bộ hóa dựa trên khóa
Các giao tác lồng
Đa luồng
Hàm khử dấu trừ trong chuỗi có dấu chính tắc
Hàm gộp 2 chuỗi có dấu chính tắc
Sinh luồng
Các commit của các luồng song song đồng thời
thực hiện kết thúc một giao tác chung.
Cú pháp
KÝ HIỆU


1
2
3
4

+

m

−

m

#

m

¬

m

Mô tả thành phần + trong hệ thống kiểu dựa trên
chuỗi số có dấu, m thao tác onacid liên tiếp.
Mô tả thành phần – trong hệ thống kiểu dựa trên
chuỗi số có dấu, m thao tác commit liên tiếp.
Mô tả thành phần # trong hệ thống kiểu dựa trên
chuỗi số có dấu, m các giao tác lồng nhau.
Mô tả thành phần ¬ thể hiện số lƣợng joint
commit trong hệ thống kiểu dựa trên chuỗi số có



9
dấu.

DANH MỤC CÁC BẢNG
Bảng 2.1: Khai báo biểu thức, kiểu, loại trong ngôn ngữ F* ............Error! Bookmark not
defined.
Bảng 3.1 Bảng kết quả kiểm thử phép toán chính tắc chuỗi số có dấu ... Error! Bookmark
not defined.
Bảng 3.2 Bảng kết quả kiểm khử dấu “−” thành dấu “¬” .. Error! Bookmark not defined.
Bảng 3.3 Bảng kết quả kiểm khử hàm merge .................... Error! Bookmark not defined.
Bảng 3.4 Bảng kết quả kiểm khử hàm joint commit .......... Error! Bookmark not defined.


10

DANH MỤC CÁC HÌNH VẼ
Hình 2.1: Kết quả cho bài toán tính giai thừa..................... Error! Bookmark not defined.
Hình 2.2: Các kiểu, loại dữ liệu đƣợc sử dụng trong F* [4] .............Error! Bookmark not
defined.
Hình 3.1: Kết quả cho bài toán sắp xếp nổi bọt ................. Error! Bookmark not defined.
Hình 3.2: Kết quả cho bài toán sắp xếp nhanh ................... Error! Bookmark not defined.
Hình 3.3: Ví dụ mô hình giao tác lồng, đa luồng và joint [13] .........Error! Bookmark not
defined.


11

PHẦN MỞ ĐẦU

Tính cấp thiết của đề tài
Hiện nay ngành công nghiệp phần mềm đang rất phát triển ở nhiều lĩnh vực. Trên
thực tế, tùy theo yêu cầu của mỗi lĩnh vực mà chúng ta có thể lựa chọn các ngôn ngữ lập
trình sao cho phù hợp. Chúng ta có thể thấy rất nhiều ngôn ngữ lập trình đƣợc sử dụng
ngày nay, trong đó phải kể đến một số ngôn ngữ lập trình rất đƣợc phổ biến nhƣ là Java,
C#, Objective-C, JavaScript, SQL, PHP. Các ngôn ngữ lập trình hàm nhƣ OCaml, ML, F#
cũng dần đƣợc phổ biến trong khoảng thời gian gần đây. Ngôn ngữ lập trình hàm F# là
ngôn ngữ có kiểu mạnh (strongly-typed) và tự suy luận kiểu (không cần phải khai báo
kiểu cho các biến đầu vào), trình biên dịch có thể tự suy luận ra kiểu của các biến đầu vào
đó khi dịch chƣơng trình. Tuy nhiên các kiểu đƣợc sử dụng để gán cho các biến đầu vào
của ngôn ngữ là có sẵn và đƣợc gán một cách tự động khiến ngƣời lập trình khó có thể tùy
biến đƣợc trong F#.
Từ nhu cầu này, ngôn ngữ F* đã ra đời. Ngôn ngữ F* có hệ thống kiểu đƣợc xây
dựng dựa trên nền tảng lý thuyết System Fω [1] nhƣng đƣợc mở rộng hơn với hệ thống
kiểu phụ thuộc, các kiểu đƣợc tùy chỉnh, cho phép ngƣời lập trình có thể làm mịn kiểu dữ
liệu cho chặt hơn, phù hợp hơn với ý đồ. Ngoài ra F* có thể kiểm chứng tính đúng đắn
của chƣơng trình theo kiểu dữ liệu mới đƣợc làm mịn này. Tức là thông thƣờng, chúng ta
chỉ có kiểu số nguyên (int) nhƣng với ngôn ngữ F* chúng ta có thể khai báo kiểu số
nguyên nằm trong khoảng 0 đến 10, hay chỉ gồm các số chẵn hoặc chỉ có các số lẻ. Hơn
nữa ngôn ngữ F* có thể đƣợc dịch sang những ngôn ngữ khác nhƣ OCaml, F# hoặc
JavaScript để thực thi. Những vấn đề trên là cơ sở khoa học và thực tiễn để tôi thực hiện
đề tài “Nghiên cứu ứng dụng ngôn ngữ F* trong phát triển phần mềm”.
Mục tiêu của luận văn
Trên cơ sở nghiên cứu lý thuyết, cài đặt, thử xây dựng các chƣơng trình cơ bản, luận
văn đã ứng dụng ngôn ngữ F* vào việc xây dựng công cụ tính tổng tài nguyên đƣợc sử
dụng trong chƣơng trình đa luồng có dùng bộ nhớ giao dịch, theo bài báo nghiên cứu của
thầy hƣớng dẫn.
Công cụ phần mềm
Trong luận văn, tôi có sử dụng mã nguồn F* để cài đặt thuật toán chƣơng trình.
Ngoài ra còn một số công cụ hỗ trợ nhƣ Cygwin, OCaml và Visual Studio (C#, F#).



12

TÀI LIỆU THAM KHẢO
Tiếng Anh
[1] Reynolds and John, "Towards a Theory of Type Structure," Carnegie Mellon
University, 1974.
[2] P. Hudak, Conception, evolution, and application of functional programming
languages, ACM Computing Surveys, 1989.
[3] P.-Y. Strub, N. Swamy, C. Fournet and J. Chen, "Self-Certification, Bootstrapping
Certified Typecheckers in F* with Coq," Microsoft Research, 2012.
[4] U. N. a. J. Chapman, "Dependently Typed Programming in Agda," Chalmers
University, Gothenburg, 2013.
[5] P. H. Khanh, Lập Trình Hàm và Lập Trình Logic, Đà Nẵng, 2009.
[6] N. Swamy, C. Hritcu, C. Keller, P.-Y. Strub, A. Rastogi, A. Delignat-Lavaud, K.
Bhargavan and C. Fourne, "Semantic Purity and Effects Reunited in F," ICFP, 2015.
[7] H. Geuvers, "Introduction to Type Theory," Radboud University Nijmegen; The
Netherlands Technical University Eindhoven;, The Netherland, 2008.
[8] P. Castéran and M. Sozeau, "A Gentle Introduction to Type Classes and Relations in
Coq," CNRS; LaBRI; UMR 5800; F-33400 Talence, France, 2014.
[9] R. Harper, "Programming in Standard ML," Carnegie Mellon University, 2011.
[10] N. Swamy, J. Chen, C. Fournet, P.-Y. Strub, K. Bhargavan and J. Yang, "Secure
Distributed Programming with Value-Dependent Types," Microsoft Research, MSRINRIA, INRIA, MIT, 2011.
[11] J. Condit, M. Harren, Z. Anderson, D. Gay and G. C. Necula, "Dependent Types for
Low-Level Programming," University of California, Berkeley, Intel Research,
Berkeley, 2007.
[12] A. Bove and P. Dybjer, "Dependent Types at Work," Chalmers University of
Technology, Sweden, 2008.
[13] H. Truong, "Type Systems for Guaranteeing Resource Bounds of Component

Software," 2006.
[14] C. Fournet, N. Swamy, J. Chen, Pierre-Evariste, D. Pierre-Yves, Strub and B.
Livshits, "Fully Abstract Compilation to JavaScript," Microsoft Research and MSRINRIA, 2013.
[15] J. Bengtson, K. Bhargavan, C. Fournet, A. D. Gordon and S. Maffeis, "Refinement
Types for Secure Implementations," 2008.
[16] H. Truong, "A type and effect system for counting logs of multi-threaded nested
transactional programs," Vietnam National Foundation for Science and Technology
Development (NAFOSTED), 2014.
[17] D. Wahlstedt, "Dependent Type Theory with Parameterized First-Order Data Types
and Well-Founded Recursion," 2007.


13