Inside Collection (Course): Ngôn ngữ lập trình
Sau khi học xong chương này, sinh viên cần phải nắm:
Kiến thức và kĩ năng lập trình căn bản.
Hầu hết các ngôn ngữ lập trình từ trước đến nay được xây dựng dựa trên nguyên lý kiến trúc máy tính Von Neumann. Lớp chủ yếu trong các ngôn ngữ đó là các ngôn ngữ ra lệnh. Ðơn vị làm việc trong một chương trình là câu lệnh. Kết quả của từng câu lệnh được tổ hợp lại thành kết quả của cả chương trình. Các ngôn ngữ này bao gồm: FORTRAN, COBOL, Pasacl, Ada... Mặc dù ngôn ngữ ra lệnh đã được hầu hết người lập trình chấp nhận nhưng sự liên hệ chặt chẽ với kiến trúc máy tính là một hạn chế đến việc phát triển phần mềm.
Ngôn ngữ lập trình hàm được thiết kế dựa trên các hàm toán học là một trong những ngôn ngữ không ra lệnh quan trọng nhất. Trong đó LISP là một ngôn ngữ tiêu biểu.
Hàm là một sự tương ứng giữa các phần tử của một tập hợp (miền xác định) với các phần tử của một tập hợp khác (miền giá trị). Ðịnh nghĩa hàm xác định miền xác định, miền giá trị và quy tắc tương ứng giữa các phần tử của miền xác định với các phần tử của miền giá trị. Thông thường sự tương ứng được mô tả bởi một biểu thức. Hàm toán học có hai đặc trưng cơ bản là:
Ðịnh nghĩa hàm thường được viết bởi tên hàm, danh sách các tham số nằm trong cặp dấu ngoặc và sau đó là biểu thức, ví dụ: lap_phuong(x) x*x*x trong đó x là một số thực. Miền xác định, miền giá trị là các tập số thực.
Lúc áp dụng, một phần tử cụ thể của miền xác định gọi là đối sẽ thay thế cho tham số trong định nghĩa hàm. Kết quả hàm thu được bằng cách đánh giá biểu thức hàm. Ví dụ lap_phuong(2.0) cho giá trị là 8.0. Trong định nghĩa hàm, x đại diện cho mọi phần tử của miền xác định. Trong lúc áp dụng, nó được cho một giá trị (chẳng hạn 2.0), giá trị của nó không thay đổi sau đó. Ðiều này trái ngược với biến trong lập trình có thể nhận các giá trị khác nhau trong quá trình thực hiện chương trình.
Trong định nghĩa hàm, ta bắt cặp tên hàm với biểu thức x*x*x. Ðôi khi người ta sử dụng hàm không tên, trong trường hợp đó người ta sử dụng biểu thức lambda. Giá trị của biểu thức lambda chính là hàm của nó. Ví dụ (x)x*x*x. Tham số trong biểu thức lambda được gọi là biến kết ghép. Khi biểu thức lambda được đánh giá đối với một tham số đã cho, người ta nói rằng biểu thức được áp dụng cho tham số đó.
Dạng hàm là sự tổ hợp của các hàm. Dạng hàm phổ biến nhất là hàm hợp. Nếu f được định nghĩa là hàm hợp của g và h, được viết là f g.h thì việc áp dụng f được định nghĩa là sự áp dụng h sau đó áp dụng g lên kết quả.
Xây dựng (construction) là một dạng hàm mà các tham số của chúng là những hàm. Người ta ký hiệu một xây dựng bằng cách để các hàm tham số vào trong cặp dấu ngoặc vuông. Khi áp dụng vào một đối số thì các hàm tham số sẽ được áp dụng vào đối đó và tập hợp các kết quả vào trong một danh sách. Ví dụ: G(x) x*x, H(x) 2*x và I(x) x/2 thì [G,H,I](4) có kết quả là (16,8,2).
Áp dụng cho tất cả là một dạng hàm mà nó lấy một hàm đơn như là một tham số. Áp dụng cho tất cả được ký hiệu là . Nếu áp dụng vào một danh sách các đối thì áp dụng cho tất cả sẽ áp dụng hàm tham số cho mỗi một giá trị và tập hợp các kết quả vào trong một danh sách. Ví dụ
Cho h(x) x*x thì (h, (2,3,4)) có kết quả là (4,9,16)
Mục đich của việc thiết kế ngôn ngữ lập trình hàm là mô phỏng các hàm toán học một cách nhiều nhất có thể được. Trong ngôn ngữ ra lệnh, một biểu thức được đánh giá và kết quả của nó được lưu trữ trong ô nhớ được biểu diễn bởi một biến trong chương trình. Ngược lại, trong ngôn ngữ lập trình hàm không sử dụng biến và do đó không cần lệnh gán. Ðiều này giải phóng người lập trình khỏi mối quan tâm về ô nhớ của máy tính trong khi thực hiên chương trình. Không có biến cho nên không có cấu trúc lặp (vì cấu trúc lặp được điều khiển bởi biến). Các lệnh lặp lại sẽ được xử lý bằng giải pháp đệ quy. Chương trình là các định nghĩa hàm và các áp dụng hàm. Sự thực hiện là việc đánh giá các áp dụng hàm. Sự thực hiện một hàm luôn cho cùng một kết quả khi ta cho nó cùng một đối số. Điều này gọi là trong suốt tham khảo (referential transparancy). Nó cho thấy rằng ngữ nghĩa của ngôn ngữ lập trình hàm đơn giản hơn ngữ nghĩa của ngôn ngữ lập trình ra lệnh và ngôn ngữ hàm bao gồm cả những nét đặc biệt của ngôn ngữ ra lệnh.
Ngôn ngữ hàm cung cấp một tập hợp các hàm nguyên thủy, một tập các dạng hàm để xây dựng các hàm phức tạp từ các hàm đã có. Ngôn ngữ cũng cung cấp một phép toán áp dụng hàm và các cấu trúc lưu trữ dữ liệu. Một ngôn ngữ hàm được thiết kế tốt là một ngôn ngữ có tập hợp nhỏ các hàm nguyên thủy. Phần sau chúng ta làm quen với một ngôn ngữ lập trình hàm khá nổi tiếng là ngôn ngữ LISP.
Ðược J. MAC CARTHY viết năm 1958, LISP là một trong những ngôn ngữ lập trình sớm nhất. Ðầu năm những năm 80, LISP được phát triển mạnh nhờ những áp dụng trong lĩnh vực trí tuệ nhân tạo. LISP có các ưu điểm chính như sau:
Nguyên tử là một đối tượng cơ bản của LISP, nguyên tử có thể là số hoặc ký hiệu.
Ví dụ về các hằng số: 5, -17, 5.35, 3/4, 118.2E+5,...
Ví dụ về các hằng ký hiệu: ‘a, ‘anh, ‘anh_ba,...
Một số ký hiệu được định nghĩa trước như: T (về mặt logic, được hiểu là TRUE), NIL (về mặt logic, được hiểu là FALSE).
Hằng ký hiệu số được xem như là một số, chẳng hạn ‘5 = 5.
Danh sách là một dãy có phân biệt thứ tự của các phần tử cách nhau ít nhất một khoảng trắng và đặt nằm trong cặp dấu ngoặc đơn ().
Phần tử của danh sách có thể là một nguyên tử hoặc là một danh sách.
Hằng danh sách được mở đầu bằng dấu nháy đơn ‘.
Ví dụ về các hằng danh sách:
Biểu thức là một nguyên tử hoặc một danh sách. Biểu thức luôn có một giá trị mà việc định trị nó theo nguyên tắc sau:
Ví dụ:
> 25
= 25
Ví du:
> (setq a 3) ; Gán số 3 cho biến có tên a
= 3
> a ; hỏi giá trị của ký hiệu “a”
= 3
Ví dụ
> (+ 5 3 6)
= 14
> ( + 4 (+ 3 5))
= 12
Ví dụ:
> ‘(+ 1 2)
= (+ 1 2)
Một chương trình của LISP là một hàm hoặc một hàm hợp. Các hàm có thể do LISP định nghĩa trước hoặc do lập trình viên tự định nghĩa.
Ví dụ:
> (+ 5 6 2)
= 13
> (- 8 3)
= 5
> (- 8 3 1)
= 4
>(1+ 5) ; Tương đương (+ 5 1)
= 6
> (1- 5) ; Tương đương (- 5 1)
= 4
>(MOD 14 3)
= 2
>(sqrt 9) ; Lấy căn bậc hai của 9
= 3
Ví dụ:
>(< 4 5)
= T
>(> 4 (* 2 3))
= NIL
Ví dụ:
>(eq ‘tuong ‘tuong)
= T
>(eq ‘tuong ‘duong)
= NIL
>(eq ‘5 5 )
= T
Ví dụ:
>(equal ‘(a b c) ‘(a b c))
= T
>(equal ‘(a b c) ‘( b a c))
= NIL
>(equal ‘a ‘a)
= T
Ví du:
> (CAR '(1 2 3))
= 1
> (CAR 3)
Error: bad argument type - 3
>(CAR nil)
= NIL
> (CAR '((a b) 1 2 3))
= (A B)
Ví dụ:
>(cdr '(1 2 3))
= (2 3)
>(cdr 3)
Error: bad argument type - 3
>(cdr nil)
= NIL
>(cdr '(1))
= NIL
>(CAR (CDR ‘(a b c)))
= B
Ví du:
(CADR ‘(a b c))
= B
Ví du:
>(CONS 3 '(1 2 3))
= (3 1 2 3)
>(CONS 3 nil)
= (3)
>(CONS '(a b) '(1 2 3))
= ((A B) 1 2 3)
Ví du:
>(list 1 2)
= (1 2)
>(list 'a 'b)
= (A B)
>(list 'a 'b (+ 2 3 5))
= (A B 10)
Ví du:
>(atom 'a)
= T
>(numberp 4)
= T
>(symbolp 'a)
= T
>(listp '(1 2))
= T
>(symbolp NIL)
= T
>(listp NIL)
= T
>(null NIL)
= T
>(null ‘(a b))
= NIL
>(null 10)
= NIL
Ví dụ:
>(AND (> 3 2) (= 3 2) (+ 3 2))
= NIL
>(AND (> 3 2) (- 3 2) (+ 3 2))
= 5
Ví du:
>(OR (= 3 2) (+ 2 1) (list 1 2))
= 3
>(OR (= 2 1) (Cdr ‘(a) ) (listp 3 ))
= NIL
(ÐK2E2)
..................
(ÐKnEn)
[(TEn+1)]
)
Nếu ĐK1 khác NIL thì trả về kết quả là giá trị của E1, ngược lại sẽ xét ĐK2. Nếu ĐK2 khác NIL thì trả về kết quả là giá trị của E2, ngược lại sẽ xét ĐK3...
......
Nếu ĐKn khác NIL thì trả về kết quả là giá trị của En, ngược lại sẽ trả về NIL hoặc trả về kết quả là giá trị của En+1 (trong trường hợp ta sử dụng (T En+1))
Cú pháp định nghĩa hàm là:
(defun <tên hàm> <danh sách các tham số hình thức>
<biểu thức>
)
Ví dụ 1: Ðịnh nghĩa hàm lấy bình phương của số a
(defun binh_phuong (a)
(* a a)
)
Sau khi nạp hàm này cho LISP, ta có thể sử dụng như các hàm đã được định nghĩa trước.
>(binh_phuong 5)
= 25
>(binh_phuong (+ 5 2))
= 49
Ví dụ 2: Ðịnh nghĩa hàm DIV chia số a cho số b, lấy phần nguyên.
Trước hết ta có: a DIV b = (a – a MOD b)/b
(defun DIV (a b)
(/ (- a (MOD a b)) b)
)
Một hàm đệ quy là một hàm có lời gọi chính nó trong biểu thức định nghĩa hàm. Mô tả một đệ quy bao gồm:
Ví dụ 1: Viết hàm tính n giai thừa
Công thức đệ quy tính n giai thừa là
Hàm (giai_thua N) viết bằng ngôn ngữ LISP:
(defun giai_thua (n)
(if (= n 0) 1 ; trường hợp “dừng”
(* n (giai_thua (1- n))); n-1 là yếu tố dẫn đến trường hợp dừng
) ; If
)
Ví dụ 2: Viết hàm DIV chia a cho b lấy phần nguyên, viết bằng đệ quy.
Công thức đệ quy:
Hàm (DIV a b) viết bằng LISP:
(defun DIV (a b)
(if (< a b) 0 ; Trường hợp “dừng”
(1+ (DIV (- a b) b)); a-b là yếu tố dẫn đến trường hợp dừng
) ; If
)
Ví dụ 3: Viết hàm (phan_tu i L), nhận vào số nguyên dương i và danh sách L. Hàm trả về phần tử thứ i trong danh sách L hoặc thông báo “không tồn tại”.
Công thức đệ quy:
Hàm (phan_tu i L) viết bằng LISP:
(defun phan_tu(i L)
(cond
((Null L) “Khong ton tai”)
((= i 1) (car L)); trường hợp dừng thứ hai
(T (phan_tu (1- i) (cdr L)))
) ; cond
)
Trong chương trình trên, (null L) là trường hợp “dừng” thứ nhất; (= i 1) là trường hợp “dừng” thứ hai; (cdr L) là yếu tố dẫn đến trường hợp “dừng” thứ nhất và (1- i) yếu tố dẫn đến trường hợp “dừng” thứ hai.
Nạp một tập tin vào cho LISP và trả về T nếu việc nạp thành công, ngược lại trả về NIL. Tên tập tin là một chuỗi kí tự có thể bao gồm cả đường dẫn đến nơi lưu trữ tập tin đó. Tên tập tin theo quy tắc của DOS, nghĩa là chỉ có tối đa 8 ký tự trong phần tên và 3 ký tự phần mở rộng và không chứa các ký tự đặc biệt.
Ta có thể sử dụng LOAD để nạp một tập tin chương trình của LISP trước khi gọi thực hiện các hàm đã được định nghĩa trong tập tin đó.
Ví dụ:
>(Load “D:\btlisp\bai1.lsp”)
Ðọc dữ liệu từ bàn phím cho đến khi gõ phím Enter, trả về kết quả là dữ liệu được nhập từ bàn phím.
In ra màn hình giá trị của biểu thức E, xuống dòng và trả về giá trị của E.
In ra màn hình giá trị của biểu thức E (không xuống dòng) và trả về giá trị của E.
Ðưa con trỏ xuống dòng và trả về NIL.
Biến toàn cục (global variables) là biến mà phạm vi của nó là tất cả các hàm. Biến toàn cục sẽ tự động giải phóng khi chương trình dịch LISP kết thúc.
Gán trị của <biểu thức> cho <tên biến> và trả về kết quả là giá trị của <biểu thức>.
Ví dụ:
>(setq x (* 2 3))
= 6
> x ; biến x vẫn còn tồn tại và có giá trị là 6
= 6
Biến cục bộ (local variables) là biến mà phạm vi của nó chỉ nằm trong hàm mà nó được tạo ra. Biến cục bộ sẽ tự động giải phóng hàm tạo ra nó kết thúc.
Ta thấy hàm này có 2 phần: phần gán trị cho các biến và phần định trị các biểu thức.
Gán trị của biểu thức Ei cho biến cục bộ vari tương ứng và thực hiện (PROGN Ek+1 ... En).
Ví dụ:
>(Let ((a 3) (b 5)) (* a b) (+ a b))
= 8
> a ; biến a lúc này đã được giải phóng nên LISP sẽ thông báo lỗi
error: unbound variable - A
Trong lập trình hàm, người ta rất hạn chế sử dụng biến, nếu thật sự cần thiết thì nên sử dụng biến cục bộ. Tuy nhiên việc khai báo biến cục bộ trong hàm LET gây khó khăn cho việc viết chương trình hơn là sử dụng biến toàn cục. Để khắc phục tình trạng này, ta sẽ kết hợp cả hai hàm LET và SETQ để sử dụng biến cục bộ che biến toàn cục. Cách làm như sau:
(LET ( (var E1)…..)
…….
(SETQ var E2)
……
)
Với cách làm này thì biến var trong hàm SETQ sẽ trở thành biến cục bộ.
Ví dụ: Giả sử ta đã định nghĩa được hàm (ptb2 a b c), giải phương trình bậc hai ax2+bx+c = 0. Bây giờ ta viết hàm (giai_ptb2) cho phép nhập các hệ số a, b, c từ bàn phím và gọi hàm (ptb2 a b c) để thực hiện việc giải phương trình. Có hai phương pháp để viết hàm này.
Phương pháp 1: dùng các biến toàn cục a, b, c
(defun giai_ptb2 ()
(progn
(print “Chương trình giải phương trình bậc hai“)
(princ “Nhập hệ số a: “) (setq a (read))
(princ “Nhập hệ số b: “) (setq b (read))
(princ “Nhập hệ số c: “) (setq c (read))
(ptb2 a b c)
)
)
Sau khi thực hiện chương trình này, thì các biến toàn cục a, b và c vẫn còn.
Phương pháp 2: dùng các biến cục bộ d, e, f
(defun giai_ptb2 ()
(let ((d 0) (e 0) (f 0))
(print “Chương trình giải phương trình bậc hai“)
(princ “Nhập hệ số a: “) (setq d (read))
(princ “Nhập hệ số b: “) (setq e (read))
(princ “Nhập hệ số c: “) (setq f (read))
(ptb2 d e f)
)
)
Sau khi thực hiện chương trình này, thì các biến cục bộ d, e và f được giải phóng.
XLISP là một trình thông dịch, chạy dưới hệ điều hành Windows. Chỉ cần chép tập tin thực thi XLISP.EXE có dung lượng 288Kb vào máy tính của bạn là có thể thực hiện được.
Để thực hiện các hàm, chỉ cần gõ trực tiếp hàm đó vào sau dấu chờ lệnh (>) của XLISP. Trong trường hợp không có dấu chờ lệnh, hãy dùng menu Run/Top level hoặc Ctrl-C để làm xuất hiện dấu chờ lệnh.
Việc định nghĩa một hàm cũng có thể gõ trực tiếp vào sau dấu chờ lệnh. Tuy nhiên cách làm này sẽ khó sửa chữa hàm đó và do vậy ta thường định nghĩa các hàm trong một tập tin chương trình, sau đó nạp vào cho XLISP để sử dụng.
Ta có thể lưu trữ lại tình trạng làm việc hiện hành vào trong tập tin .WKS bằng cách dùng menu File/Save workspace và sau đó có thể khôi phục lại bằng cách dùng menu File/Restore workspace.
Do XLISP không có công cụ để soạn thảo chương trình nên ta có thể sử dụng Notepad để soạn thảo tập tin chương trình.
Trong một tập tin chương trình ta có thể định nghĩa nhiều hàm.
Lưu tập tin chương trình có tên theo quy định của DOS (8.3) với phần mở rộng .LSP và để trong cặp dấu nháy kép.
Có hai phương pháp để nạp các hàm tự định nghĩa cho XLISP:
More about this module: Metadata | Downloads | Version History
This work is licensed by ThS. Nguyễn Văn Linh under a Creative Commons Attribution License (CC-BY 3.0), and is an Open Educational Resource.
Last edited by VOCW on Jul 27, 2009 5:15 am -0500.
