Tài liệu Nghiên cứu cơ chế lập trình tương tranh cho ngôn ngữ lập trình hàm sml#

TRẦN NHẬT HÓA BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------------------------------------- Trần Nhật Hóa CÔNG NGHỆ THÔNG TIN NGHIÊN CỨU CƠ CHẾ LẬP TRÌNH TƯƠNG TRANH CHO NGÔN NGỮ LẬP TRÌNH HÀM SML# LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN 2006-2008 HÀ NỘI – 2008 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------------------------------------- TRẦN NHẬT HÓA NGHIÊN CỨU CƠ CHẾ LẬP TRÌNH TƯƠNG TRANH CHO NGÔN NGỮ LẬP TRÌNH HÀM SML# Chuyên ngành: CÔNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN HỮU ĐỨC HÀ NỘI – 2008 i LỜI CAM ĐOAN Tôi xin cam đoan Luận văn này là công trình nghiên cứu khoa học của riêng tôi, không hề sao chép bất kỳ một công trình nào. ii MỤC LỤC LỜI CAM ĐOAN ..................................................................................................... i MỤC LỤC ............................................................................................................... ii DANH MỤC CÁC BẢNG .....................................................................................iii DANH MỤC CÁC HÌNH...................................................................................... iv DANH MỤC CÁC TỪ VIẾT TẮT ....................................................................... v CHƯƠNG 1. ĐẶT VẤN ĐỀ .................................................................................. 1 1.1. Giới thiệu .................................................................................................... 1 1.2. Nội dung nghiên cứu đề tài ......................................................................... 3 1.3. Phương pháp nghiên cứu đề tài ................................................................... 4 1.4. Các bước thực hiện đề tài............................................................................ 4 1.5. Kết cấu của Luận văn .................................................................................. 4 CHƯƠNG 2. NGÔN NGỮ LẬP TRÌNH HÀM SML# ....................................... 6 2.1. Giới thiệu .................................................................................................... 6 2.2. Lớp ngôn ngữ SML (Standard Metalanguage) ......................................... 10 2.3. Ngôn ngữ SML# ....................................................................................... 19 CHƯƠNG 3. KỸ THUẬT LẬP TRÌNH TƯƠNG TRANH ............................. 25 3.1. Lập trình tương tranh (Concurrent Programming) ................................... 25 3.2. Một số vấn đề về tương tranh ................................................................... 28 3.3. Các cách tiếp cận tương tranh trên một số ngôn ngữ lập trình ................. 36 CHƯƠNG 4. XÂY DỰNG CƠ CHẾ LẬP TRÌNH TƯƠNG TRANH ............ 52 4.1. Thiết kế hệ thống biên dịch hỗ trợ lập trình đa luồng trên SML# ............ 52 4.2. Thiết kế hệ thống thực thi hỗ trợ lập trình đa luồng trên SML# ............... 61 CHƯƠNG 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................... 78 5.1. Những kết quả đã đạt được và đóng góp mới của Luận văn .................... 78 5.2. Hướng phát triển tiếp theo của Luận văn .................................................. 79 DANH MỤC CÁC THUẬT NGỮ ....................................................................... 80 TÀI LIỆU THAM KHẢO .................................................................................... 82 iii DANH MỤC CÁC BẢNG BẢNG TRANG Bảng 4.1. Một số lệnh thực thi trên máy ảo của SML# .................................................57 Bảng 4.2. Các bước biên dịch trong SML# .....................................................................60 iv DANH MỤC CÁC HÌNH HÌNH TRANG Hình 3.1. Các mô hình kết hợp giữa tiến trình và luồng ...............................................30 Hình 3.2. Mô hình tiến trình đơn luồng và tiến trình đa luồng ....................................31 Hình 3.3. Wait set ..............................................................................................................39 Hình 3.4. Các thông điệp trong Mailbox .........................................................................44 Hình 3.5. Kiến trúc Heap trong Manticore .....................................................................50 Hình 4.1. Ví dụ minh họa thực thi đa luồng ...................................................................54 Hình 4.2. Các mô đun chính trong quá trình biên dịch .................................................59 Hình 4.3. Mô hình tổ chức máy ảo trong SML# .............................................................62 Hình 4.4. Mô hình tổ chức mới của máy ảo ....................................................................63 Hình 4.5. Mô hình bộ nhớ hiện tại của SML# ................................................................63 Hình 4.6. Mô hình bộ nhớ thực thi đa luồng...................................................................64 Hình 4.7. Cài đặt các thanh ghi trong máy ảo của SML# .............................................65 Hình 4.8. Lớp Session ........................................................................................................66 Hình 4.9. Các bước khởi tạo Session ...............................................................................67 Hình 4.10. Cấu trúc Executable .......................................................................................67 Hình 4.11. Các bước thực thi máy ảo ..............................................................................68 Hình 4.12. Quá trình khởi tạo máy ảo thực thi đa luồng...............................................69 Hình 4.13. Phương thức khởi tạo các luồng ....................................................................70 Hình 4.14. Các bước khởi tạo luồng ................................................................................71 Hình 4.15. Thuật toán GC ................................................................................................74 Hình 4.16. Xử lý ngoại lệ...................................................................................................77 v DANH MỤC CÁC TỪ VIẾT TẮT CML Concurrent ML GC Garbage Collection JVM Java Virtual Machine ML Metalanguage SML Standard Metalanguage SML/NJ Standard ML of New Jersey VM Virtual Machine 1 CHƯƠNG 1. ĐẶT VẤN ĐỀ 1.1. Giới thiệu Trong thế giới thông tin ngày nay, sự phát triển mạnh mẽ của các ứng dụng song song và phân tán kéo theo những nhu cầu cấp thiết về một nền tảng phát triển phần mềm để đảm bảo tính hiệu quả cho ứng dụng. Với mục đích phục vụ tốt nhất cho người sử dụng, các phần mềm phải đảm bảo hiệu năng cao nhất cũng như sự hợp lý trong việc sử dụng tài nguyên. Công nghệ mạng hay gần đây là công nghệ chế tạo chíp đa lõi (multicore) có thể được coi như những hạ tầng cần thiết cho nền tảng này. Tuy nhiên, khi nhắc đến một ứng dụng song song hay phân tán, ta không thể không đề cập đến ngôn ngữ lập trình sử dụng để phát triển ứng dụng. Ngôn ngữ hỗ trợ lập trình song song và phân tán (gọi tắt là ngôn ngữ lập trình song song) không những phải giúp lập trình viên chuyển tải ý tưởng thiết kế thành các phần mềm mà còn phải đảm bảo được rằng phần mềm đó có thể thực thi hiệu quả trên nền các hạ tầng tính toán sẽ sử dụng. Một ngôn ngữ lập trình song song tốt phải hướng đến việc cung cấp các cơ chế song song hóa ở nhiều cấp độ khác nhau. Thông thường, tính song song được thể hiện ở ba cấp độ, đó là [FF+07]: - Song song hóa ẩn (implicit parallelism): ở đó, trình biên dịch tự động phân chia công việc và song song hóa chúng bằng cách thực thi trên các luồng tính toán (thread) khác nhau. - Phân luồng ẩn (implicit threading): ở đó, người lập trình cần cung cấp các thông tin có ích cho việc song song hóa. Tuy nhiên, việc phân chia công việc và ánh xạ chúng lên các luồng tính toán được giao phó cho trình biên dịch. - Phân luồng tường minh (explicit threading): ở đó, người lập trình 2 phải tự phân chia công việc và ánh xạ chúng lên các luồng tính toán trong chương trình. Trên thực tế, phần lớn các ngôn ngữ mới chỉ hỗ trợ ở mức phân luồng tường minh. Các ngôn ngữ lập trình chỉ thị (imperative) như C hay Java khó có thể cài đặt cơ chế song song hóa tự động do những đặc trưng ngôn ngữ (sự phụ thuộc về thứ tự thực hiện quá chặt chẽ trong cơ chế chỉ thị). Ta hãy phân tích khả năng song song hóa của lớp các ngôn ngữ lập trình hàm. Với cách tiếp cận dựa trên các lời gọi hàm, lập trình hàm là một mô hình lập trình dạng khai báo (Declarative Programming) được xây dựng dựa trên cơ sở định giá các biểu thức toán học mà bỏ qua trạng thái và những dữ liệu có thể thay đổi (mutable data) [HPa89]. Việc tính toán một biểu thức toán học có thể thực hiện bằng cách đánh giá độc lập các biểu thức con sau đó kết hợp giá trị của chúng. Đây là một yếu tố quan trọng cho việc song song hóa tự động. Ngoài ra, với việc không sử dụng khái niệm biến nên người lập trình không cần phải quan tâm đến thao tác đọc và ghi nó. Trong bối cảnh lập trình tương tranh, điều này giúp người lập trình tránh khỏi những phức tạp trong việc xử lý xung đột khi truy cập tài nguyên. Những đặc điểm trên đây cho thấy các ngôn ngữ lập trình hàm tỏ ra rất phù hợp với mô hình lập trình tương tranh. Thực tế là, một số ngôn ngữ lập trình hàm như: Erlang và SML/NJ đã bước đầu xây dựng cơ chế lập trình này. Tuy nhiên, thực tiễn cho thấy các ngôn ngữ lập trình hàm không được áp dụng phổ biến trong phát triển ứng dụng. Nếu bỏ qua những yếu tố về thói quen lập trình thì hai trong những nguyên nhân chính của thực trạng này là sự kém hiệu quả (hiệu năng ứng dụng thấp) và khả năng tương tác yếu (chia sẻ thư viện) với các ngôn ngữ khác. Dự án xây dựng ngôn ngữ SML# [SP07] ra đời nhằm mục tiêu khắc phục được những nhược điểm này. Tuy nhiên, phiên bản hiện tại của SML# chưa hỗ trợ các cơ chế lập trình tương tranh. 3 Xuất phát từ điều đó, Luận văn tham vọng xây dựng một ngôn ngữ lập trình hàm có hỗ trợ song song hóa ở nhiều cấp, đồng thời có tính tương tác mạnh đối với những ngôn ngữ lập trình khác. Trong bước tiếp cận đầu tiên, Luận văn tập trung vào việc giải quyết cơ chế lập trình tương tranh cho SML# ở mức độ hỗ trợ cấp ngôn ngữ (explicit parallelism). Với mục tiêu nói trên, Luận văn nghiên cứu và đề xuất một hệ thống thực thi đa luồng cho SML# theo mô hình bộ nhớ chia sẻ. Mỗi luồng được thực thi trong một không gian riêng với một hệ thống ngăn xếp (stack) riêng và bộ thanh ghi (register) riêng. Mã thực thi của các luồng được đặt trên một bộ đệm lệnh (code buffer) chung. Các đối tượng phức hợp tạo ra trong các luồng được cấp phát trên một vùng nhớ duy nhất (heap). 1.2. Nội dung nghiên cứu đề tài Trong khuôn khổ của một luận văn thạc sĩ, đề tài chỉ giới hạn nghiên cứu lập trình tương tranh trong ngôn ngữ lập trình hàm SML#. Cụ thể, về nội dung, Luận văn tập trung vào: - Nghiên cứu lập trình hàm nói chung và xem xét cụ thể với ngôn ngữ lập trình hàm SML#. - Nghiên cứu hệ thống biên dịch và hệ thống thực thi của ngôn ngữ lập trình này. - Nghiên cứu kỹ thuật lập trình tương tranh và cách tiếp cận lập trình tương tranh hiện nay của một số ngôn ngữ hỗ trợ nó. - Đề xuất cơ chế lập trình tương tranh thông qua việc sửa đổi hệ thống biên dịch và hệ thống thực thi của ngôn ngữ lập trình hàm SML#. 4 1.3. Phương pháp nghiên cứu đề tài Khi nghiên cứu các đặc điểm của ngôn ngữ lập trình và các kỹ thuật lập trình tương tranh, Luận văn tuân thủ một số nguyên tắc cơ bản sau: Nguyên tắc 1: Giữ vững các đặc trưng vốn có của ngôn ngữ lập trình hàm SML#. Bởi lẽ, bất kỳ một sự thay đổi nào cũng có thể dẫn đến việc phải hiệu chỉnh toàn bộ hệ thống. Nguyên tắc 2: Nghiên cứu kết hợp các giải pháp lập trình tương tranh để đề xuất mô hình và chiến lược cài đặt phù hợp với ngôn ngữ lập trình SML#. Nguyên tắc 3: Quá trình phân tích được triển khai từ tổng quan cho đến chi tiết từng vấn đề, theo hướng từ trên xuống (Top-down). 1.4. Các bước thực hiện đề tài Để thực hiện đề tài, quá trình nghiên cứu được triển khai qua từng bước sau: - Nghiên cứu tổng quan về lập trình hàm, xem xét các đặc trưng của ngôn ngữ SML#. - Nghiên cứu cách tiếp cận lập trình tương tranh trên một số ngôn ngữ có hỗ trợ như: Java, SML/NJ, Erlang, CML,… - Xem xét phần cài đặt cụ thể của SML# và đề xuất mô hình lập trình tương tranh phù hợp với ngôn ngữ này. 1.5. Kết cấu của Luận văn Luận văn gồm có 5 chương với các nội dung như sau: Chương 1. Đặt vấn đề Khái quát mục đích và tính cần thiết của việc song song hóa. Đề cập các đặc điểm chung của lập trình hàm. Đưa ra nội dung, cách tiếp cận và các 5 bước thực hiện để giải quyết cơ chế lập trình tương tranh trên ngôn ngữ lập trình hàm SML#. Chương 2. Ngôn ngữ lập trình hàm SML# Giới thiệu tổng quan về lập trình hàm, tập trung vào lớp ngôn ngữ SML và xem xét chi tiết SML#, qua đó cung cấp cái nhìn rõ ràng hơn về các đặc điểm của ngôn ngữ lập trình này. Chương 3. Kỹ thuật lập trình tương tranh Giới thiệu kỹ thuật lập trình tương tranh và các vấn đề cơ bản của nó. Tiếp đó, xem xét và phân tích các cách tiếp cận lập trình tương tranh trên một số ngôn ngữ hỗ trợ như: Java, Erlang, CML và Manticore, từ đó rút ra các đặc điểm và giải pháp của từng cách tiếp cận. Chương 4. Xây dựng cơ chế lập trình tương tranh Trên cơ sở nghiên cứu kiến trúc hiện tại của ngôn ngữ SML# về hệ thống biên dịch, hệ thống thực thi và đặc trưng của các mô hình lập trình tương tranh đã được đề cập trong Chương 3, Luận văn đề xuất cơ chế lập trình tương tranh phù hợp với ngôn ngữ SML# và chiến lược cài đặt nó trên ngôn ngữ này. Chương 5. Kết luận và hướng phát triển Tóm tắt những kết quả nghiên cứu đã đạt được, qua đó đề ra hướng phát triển tiếp theo cho Luận văn. 6 CHƯƠNG 2. NGÔN NGỮ LẬP TRÌNH HÀM SML# Chương này giới thiệu các đặc trưng của ngôn ngữ lập trình hàm, những điểm chính của lớp ngôn ngữ SML và tập trung khảo sát các đặc điểm của ngôn ngữ lập trình hàm SML#. 2.1. Giới thiệu Lập trình hàm (Functional Programming) là cách tiếp cận lập trình dựa trên các lời gọi hàm. Đây là điểm khác biệt so với các ngôn ngữ thuộc lớp lập trình chỉ thị vốn được xây dựng dựa trên các lệnh. Lập trình hàm là mô hình lập trình, trong đó, việc tính toán được thực hiện thông qua việc định giá các hàm mà bỏ qua sự thay đổi trạng thái và dữ liệu. Lập trình hàm dựa trên các biểu thức. Những biểu thức này thỏa mãn các quy luật toán học trên cơ sở giới hạn của máy (ví dụ như: các thuật toán đối với số thực chỉ cho kết quả gần đúng). Ngữ nghĩa của một biểu thức, đơn giản là kết quả của việc tính toán biểu thức đó, vì thế, các biểu diễn con có thể được định giá một cách độc lập. Trong khi đó, lệnh là việc chuyển đổi trạng thái hoặc một thao tác khác phức tạp tương tự. Vì vậy, để hiểu một lệnh, ta phải hiểu được đầy đủ ảnh hưởng của nó lên trạng thái của máy. Một biểu diễn ở lập trình hàm đơn giản và dễ hiểu hơn so với một biểu diễn trong các ngôn ngữ lập trình chỉ thị. Việc sử dụng các hàm đệ quy có thể mang lại sự rõ ràng hơn về mặt diễn đạt thuật toán, tuy nhiên nó lại làm cho vấn đề cài đặt trở nên kém hiệu quả. Thông thường, các biểu diễn trong ngôn ngữ lập trình chỉ thị (như Pascal) không thể thỏa mãn các hàm toán học. Một bộ tối ưu biên dịch có thể dẫn đến việc tính toán biểu thức: f(z) + u/2 được chuyển thành u/2 + f(z). Do đó, nó có thể sẽ không cho ra cùng kết quả bởi hàm f có thể làm thay đổi giá trị của u. Điều đó có nghĩa là một biểu diễn trong Pascal bao gồm cả trạng thái lẫn giá trị. 7 Lập trình hàm và lập trình Logic là những thể hiện của lập trình khai báo (Declarative Programming). Ý tưởng về dạng lập trình này là tạo sự tự do khi viết chương trình, nghĩa là, người lập trình chỉ cần đặt ra yêu cầu còn máy tính sẽ làm phần còn lại. Mục đích thực tế của lập trình khai báo là làm cho chương trình dễ hiểu hơn. Tính chính xác của nó được đảm bảo bởi các lý do toán học mà không cần bận tâm về các vấn đề khác. Tuy nhiên, lập trình khai báo vẫn là lập trình, vì vậy, ta vẫn phải viết mã một cách có hiệu quả. Đặc trưng của các ngôn ngữ lập trình hàm là không có biến và cũng không có lệnh gán. Trong dạng lập trình này, các hàm được xây dựng dựa trên tư tưởng của các hàm toán học. Thông thường, chúng định ra nhiều trường hợp. Mỗi trường hợp như vậy lại được định nghĩa độc lập qua việc xác định ra các hàm. Ta hãy xem xét thuật toán để tìm ra ước số chung lớn nhất của hai số tự nhiên. Trong Pascal, ta có thể cài đặt thuật toán này như sau: function gcd(m,n: integer): integer; var prevm: integer; begin while (m<>0) do begin prevm := m; m := n mod m; n := prevm; end; gcd := n; end; Trong lớp ngôn ngữ lập trình hàm Standard ML (sẽ được đề cập ở phần sau), thuật toán Euclid cho bài toán này được biểu diễn: 8 fun gcd (m,n) = if m = 0 then n else gcd (n mod m, m); Rõ ràng, với ngôn ngữ lập trình chỉ thị, mặc dầu mã nguồn (code) được cài đặt trên một ngôn ngữ cấp cao (như đoạn mã ở trên) nhưng thật khó trong sáng và ngắn gọn. Với một ngôn ngữ lập trình như Pascal, ta cũng có thể cài đặt một chương trình đệ quy cho bài toán này. Tuy nhiên, cũng cần lưu ý rằng các lời gọi thủ tục mang tính đệ quy hầu như không có hiệu quả. Trong các ngôn ngữ lập trình hàm, những định nghĩa hàm được biên dịch ít nhiều thành cú pháp của ngôn ngữ. Toàn bộ chương trình đơn giản là một hàm, mà chính nó được định nghĩa trong mối quan hệ với các hàm khác. Ở đây, tất cả định nghĩa đều bị giới hạn bởi các giá trị. Các biến không thực sự cần thiết cho hình thức lập trình này, bởi vì, chúng sẽ nhận giá trị trong quá trình liên kết (binding) và kết quả của một hàm ngay lập tức được chuyển cho một hàm khác như một tham số. Về mặt quản lý bộ nhớ, các ngôn ngữ lập trình hàm thực hiện hoàn toàn tự động. Theo đúng chu kỳ, hệ thống sẽ quét bộ nhớ, đánh dấu những phần được truy cập và giải phóng những phần còn lại. Thao tác này được gọi là garbage collection. Tuy nhiên, nó có thể làm chậm quá trình xử lý và yêu cầu nhiều không gian nhớ hơn nhưng cũng mang lại nhiều lợi ích quan trọng. Người lập trình được giải phóng khỏi các thao tác quản lý bộ nhớ phức tạp và nhiều rủi ro, do vậy có thể làm việc hiệu quả hơn. Thông thường, các hàm là đệ quy và không có hiệu ứng phụ (effectfree). Nghĩa là, chúng chỉ tính toán kết quả mà không cần cập nhật các giá trị tương ứng với các biến. Điều đó cung cấp cho chúng ta một cách tiếp cận để giải quyết về bản chất việc tính toán. Trên thực tế, xuất phát từ lý thuyết tính toán, lập trình hàm tạo ra cầu nối giữa các phương thức tính toán hình thức với các ứng dụng của chúng. 9 Để tăng sức mạnh của các biểu diễn, các hàm phải không bị bó buộc, nghĩa là, chúng có thể nhận bất kỳ loại tham số nào (ngay cả chính các hàm) và cũng có thể trả về bất kỳ dạng kết quả nào. Hầu hết các ngôn ngữ lập trình hàm cho phép việc phân tích các tham số đầu vào bằng việc sử dụng hình thức khớp mẫu (pattern-matching), như đoạn mã tính toán về số phần tử của một danh sách sau: fun length [] = 0 | length (x::xs) = 1 + length xs; Ngoài ra, một tính năng khác mà các ngôn ngữ lập trình hàm có hỗ trợ đó là đa hình (polymorphic). Tính đa hình được thể hiện ở cả hàm lẫn kiểu dữ liệu: - Đa hình ở kiểu dữ liệu cho phép khai báo một kiểu đơn (chẳng hạn như danh sách – “list”) để mô tả cho cả danh sách các số nguyên (integer), các xâu (string), v.v. Tuy nhiên, người lập trình vẫn được đảm bảo với một danh sách dạng “int list” thì tất cả các thành phần của nó đều là số nguyên. - Các hàm đa hình cho phép khai báo một hàm đơn (chẳng hạn như hàm lọc – filter_list) để xử lý trên các danh sách số nguyên, các xâu, v.v. mà không cần phải lặp lại mã. Yêu cầu đầu tiên của lập trình hàm là tính đúng đắn (correctness), thứ hai là tính rõ ràng (clarity) và cuối cùng mới là tính hiệu quả (efficient) [LCP96]. Các ngôn ngữ lập trình hàm điển hình như: APL, Erlang, Haskell, Lisp, ML, Oz, F#, Scheme, Standard ML, Lazy ML, CAML, CAML Light. Ngôn ngữ lập trình hàm kém phổ biến hơn các ngôn ngữ lập trình khác vì nhiều lý do, chẳng hạn như tốc độ thực thi và tính hiệu quả. Điều này dẫn đến việc ứng dụng thực tế của nó vẫn còn nhiều hạn chế. Các ngôn ngữ lập trình hàm chỉ phù hợp với các ứng dụng lớn, phức tạp. Hiện nay, vẫn còn 10 nhiều vấn đề về lập trình hàm đang được tập trung nghiên cứu. Một trong những lĩnh vực quan trọng đó là mở rộng tính năng của lập trình hàm và việc tối ưu chương trình dịch. 2.2. Lớp ngôn ngữ SML (Standard Metalanguage) Tất cả các ngôn ngữ được thiết kế thành công đều vì mục đích đặc biệt nào đó, chẳng hạn như: Lisp cho trí tuệ nhân tạo, Fortran cho tính toán số, Prolog cho xử lý ngôn ngữ tự nhiên. Trong khi đó, các ngôn ngữ được thiết kế cho mục đích chung như ngôn ngữ thuật toán (algorithmic language): Algol 60 và Algol 68 lại đạt được nhiều thành công về ý tưởng hơn là những công cụ thực hành. Ngôn ngữ ML (Metalanguage) ban đầu được thiết kế để chứng minh định lý. Đây là một lĩnh vực không rộng. Trong phạm vi này, ML tập trung cho lập trình chứng minh định lý đặc biệt, đó là logic cho hàm tính toán (Edinburgh LCF - Logic for Computable Functions). Phần thiết kế của ngôn ngữ này dựa trên những đặc trưng cần thiết cho nhiệm vụ của nó, cụ thể là: - Các luật suy diễn và phương thức chứng minh được mô tả thành các hàm, vì thế ML mang đầy đủ sức mạnh của hàm bậc cao (higherorder function). - Các luật suy diễn định nghĩa kiểu trừu tượng với hình thức kiểm tra kiểu mạnh và chấp nhận kiểu đa hình. - Chứng minh có thể được thực hiện theo nhiều nhánh. Sự thất bại tại bất kì nhánh nào phải được phát hiện để chuyển sang nhánh khác. - ML được thiết kế an toàn và nó không làm hỏng môi trường trong bất kỳ trường hợp nào. Trình biên dịch ML đầu tiên được xây dựng vào năm 1974. Sau đó, 11 cộng đồng của ngôn ngữ này phát triển, dẫn đến nhiều lớp ngôn ngữ mới được ra đời. Standard ML (còn gọi là SML hoặc ML) là một ngôn ngữ chung ra đời do sự phối hợp của cả cộng đồng ML. ML nhanh chóng được chú ý và trở nên phổ biến trong khoảng thời gian ngắn sau đó. Nhiều trường đại học giảng dạy ML cho sinh viên như là một ngôn ngữ lập trình đầu tiên. ML cung cấp mức độ lập trình cơ bản cho tất cả các sinh viên, mặc dù họ biết về C, Basic, ngôn ngữ máy hoặc chưa biết bất kỳ ngôn ngữ nào. Sử dụng ML, sinh viên có thể học phân tích các vấn đề dưới góc độ toán học, bỏ đi thói quen bắt đầu từ những ngôn ngữ cấp thấp. Các tính toán có thể được biểu diễn trong một vài dòng. Những người mới làm quen với ngôn ngữ này có những đánh giá đặc biệt về phần kiểm tra kiểu. Nó có thể phát hiện các lỗi thông thường và không điều gì làm cho hệ thống đổ vỡ. Trên thực tế, các nhà phát triển ứng dụng đã lựa chọn ML để làm ngôn ngữ cài đặt vì ML làm cho việc viết chương trình đơn giản, sáng sủa và đáng tin cậy. Tuy nhiên, điểm quan trọng hơn cả là ML bảo vệ cho người lập trình tránh khỏi những lỗi thường mắc phải. Trước khi chương trình được thực hiện, bộ biên dịch kiểm tra sự hợp lệ của tất cả các mô đun và tính toàn vẹn của các dữ liệu được sử dụng. Khi thực thi, các thao tác kiểm tra sẽ được tiếp tục thực hiện để đảm bảo tính an toàn, ngay cả một chương trình ML có sai sót. Chương trình có thể thực hiện mãi mãi và có thể trả về cho người dùng một thông điệp lỗi nhưng nó không bao giờ bị đổ vỡ. 2.2.1. Các đặc điểm của SML Chương trình hàm hoạt động với các giá trị và không sử dụng trạng thái. Công cụ của chúng là những biểu thức chứ không phải là những lệnh. Tuy nhiên, người lập trình có thể sử dụng các kỹ thuật trong lập trình chỉ thị cho lập trình hàm để giải quyết các vấn đề cần thiết như lệnh gán, lặp và cấu 12 trúc mảng. - Suy diễn kiểu tự động Đối với hầu hết các ngôn ngữ lập trình chỉ thị, việc định kiểu cho các thành phần ngôn ngữ được thực hiện bởi lập trình viên thông qua khai báo. ML giải phóng người sử dụng khỏi động tác này bằng cách cung cấp một hệ thống suy diễn kiểu tự động trong quá trình biên dịch. Người lập trình không cần phải đưa ra tất cả các kiểu dữ liệu của biến và các tham số của hàm. Tuy nhiên, từ ngữ cảnh, bộ biên dịch có thể tính toán ra kiểu của chúng. Điều này làm cho chương trình ngắn gọn và đơn giản hơn trong cách viết. # val x = 1 + 2 x : int # val f y = x + y f : int -> int # val r = (x, f, f 1) r : int * (int -> int) * int - Biểu diễn dữ liệu Ngoài những kiểu dữ liệu cơ bản như số nguyên (int), xâu ký tự (string), số thực (real), giá trị logic (bool), ML cung cấp một số cấu trúc dữ liệu phức hợp như: • Bản ghi (không có nhãn): # val r = (“Tran Nhat Hoa”, 27, (“Ha noi”, “Dong Da”)) # val thanhpho = #1 (#3 r) ==> thanhpho=”Ha noi” • Bản ghi (có nhãn): # val r = {ten = “Tran Nhat Hoa”, tuoi = 27, diachi = {thanhpho = “Ha noi”, quan = “Dong Da”}} # val thanhpho = #thanhpho (#diachi r) ==> thanhpho = “Ha noi” • Danh sách: 13 # val li = [1,2,3,4] # val ls = [“a”, “b”, “c”, “d”] Danh sách hỗ trợ cho việc truy cập tuần tự từ trái sang phải. Điều này là đủ cho hầu hết các mục đích, thậm chí với cả các thao tác sắp xếp và ma trận. Thư viện chuẩn của ML cung cấp một số hàm tiện ích rất hữu dụng cho thao tác trên danh sách như: map, app, foldr,... • Kiểu dữ liệu tự định nghĩa: Người lập trình có thể dễ dàng tự định nghĩa các kiểu dữ liệu của riêng mình. Ví dụ cây nhị phân có thể được định nghĩa như sau: datatype 'a tree = Leaf of 'a |Node of 'a * 'a tree * 'a tree val t = Node(1, Leaf 2, Node (3, Leaf 4, Leaf 5)) - Các hàm Trong ML, hàm được xem là đối tượng cơ sở của ngôn ngữ (first class citizen). Hàm có thể được lưu trữ trong cấu trúc dữ liệu, có thể là kết quả trả về của một hàm nào đó hoặc được truyền vào một hàm khác như là tham số. # val fl = [fn x => x + 1, fn x => x + 2] # val l = map (fn f => f 10) fl ==> val l = [11,12] : int list Hàm có thể được định nghĩa lồng nhau và đệ quy. fun sum n = let fun sum2 (0, s) = s | sum2 (n, s) = sum2 (n – 1, s + n) in sum2 (n, 0) end ==> val sum = fn : int -> int Hàm có thể đa hình và có thể áp dụng trên mọi kiểu dữ liệu.