Bài giảng Nguyên lý ngôn ngữ lập trình - Chương 7: Ngôn ngữ lập trình hàm - Nguyễn Văn Hòa

1Chương 7: Ngơn ngữ lập 
trình hàm
Giảng viên: Ph.D Nguyễn Văn Hịa
Khoa KT-CN-MT – ðH An Giang
2Một số đặc trưng của NN mệnh lệnh

 Sử dụng nguyên lý tinh chế từng bước, hay mịn 
dần

 Khai báo dữ liệu để nối kết tên biến → trị

 Các kiểu dữ liệu cơ bản → kiểu dữ liệu cĩ cấu 
trúc

 Cấu trúc điều khiển từng tự, rẽ nhánh, gọi chương 
trình con

 Hiệu ứng lề

 Lập trình cấu trúc: khối, chương trình con, 
module
3Nội dung chính của chương

 Giới thiệu

 Hàm tốn học

 Dạng hàm

 Bản chất của lập trình hàm

 Ngơn ngữ LISP
4Giới thiệu

 Ngơn ngữ lập trình mệnh lệnh được xây dựa trên 
nguyên lý kiến trúc máy tính của von Neumann
 ðơn trị làm việc trong chương trình là câu lệnh
 Các NNLT Fortran, Pascal, Ada sự hiệu quả quan 
trọng hơn là sự thích hợp để phát triển phần mềm

 Ngơn ngữ lập trình hàm (LTH) được xây dựng 
dựa trên các hàm tốn học → ngơn ngữ khơng ra 
lệnh
 Vì dựa trên nguyên lý hàm tốn học nên LTH gần gủi 
với người dùng hơn, nhưng LTH thì khơng liên hệ chặt 
chẽ với kiến trúc máy tính
5Hàm tốn học

 Mỗi hàm tốn học là một ánh xạ các phần tử của 
tập hợp (miền xác định) với các phần tử của tập 
hợp khác (miền giá trị)

 Mỗi phần tử của miền xác định tương ứng một 
phần tử của miền giá trị

 Mỗi định nghĩa hàm xác định miền xác định, 
miền giá trị và quy tắc tương tác (ánh xạ)

 ðịnh nghĩa hàm
 Tên hàm + danh sách tham số ≡ biểu thức
 VD lap_phuong(x) ≡ x*x*x ; 
6Biểu thức lambda

 ðơi khi người ta dùng hàm khơng tên → sử dụng 
biểu thức lambda
 VD λ(x) x * x * x thay thế lap_phuong(x) ≡
x*x*x

 Tham số biểu thức lambda gọi là tham số biến kết 
ghép

 Khi biểu thức lambda được định trị đối với một 
tham số đã cho → biểu thức được áp dụng cho 
tham số đĩ
 (λ(x) x * x * x)(2) cĩ giá trị là 8
7Ngơn ngữ lập trình hàm

 Tập hợp các đối tượng dữ liệu

 Các hàm nguyên thủy

 Các dạng hàm

 Tác vụ áp dụng hàm
8ðối tượng dữ liệu

 ðối tượng dữ liệu của ngơn ngữ lập trình hàm rất 
đơn giản
 Nguyên tử (Atom): một chuỗi các ký tự; ABC, 123, Z34
 Hai nguyên tử đặc biệt: T và F
 Dãy n các đối tượng x1, x2, , xn được ký hiệu là < x1, 
x2, , xn>
 NIL là ký hiệu dãy rỗng
9Hàm nguyên thủy

 Là các hàm được định nghĩa sẵn trong ngơn ngữ

 Bĩn nhĩm dạng hàm nguyên thủy
 Nhĩm hàm số học: +, -,*, /
 Nhĩm hàm vị từ: ATOM và NULL
 Hàm đồng nhất ID:x ≡ x
 Nhĩm liên quan đến cấu trúc danh sánh (dãy)
10
Dạng hàm

 Dạng hàm là sự tổ hợp của các hàm: một hàm 
(chương trình) được xây dựng từ các hàm sẵn cĩ 
bằng cách sử dụng các tác vụ tạo chương trình

 Các dạng hàm
 Hàm hợp
 Hàm xây dựng
 Hàm áp dụng cho tất cả
11
Hàm hợp (composition)

 Hàm hợp là hàm dùng 2 hàm như là 2 tham số và 
dùng kết quả của hàm đầu tiên như là tham số 
thực cho hàm thứ 2

 VD hàm hợp của h
h ≡ f ° g
nghĩa là h(x) ≡ f ( g ( x))
Nếu f (x) ≡ x + 2 và g (x) ≡ 3 * x,
h ≡ f ° g tương đương (3 * x)+ 2
12
Hàm xây dựng (construction)

 Hàm xây dụng là hàm mà các tham số của chúng 
cũng là hàm

 Ký hiệu hàm xây dựng: []

 Khi áp dụng vào một đối số vào hàm xây dựng: 
đối số được áp dụng vào hàm tham số → tập hợp 
kết quả

 VD 
 G(x) ≡ x*x, H(x) ≡ 2*x và I(x) ≡ x/2 
 [G,H,I](4) cĩ kết quả là (16,8,2)
13
Áp dụng cho tất cả

 Là hàm lấy một hàm đơn như là một tham số

 Hàm áp dụng cho tất cả được ký hiệu là α

 Áp dụng hàm tham số vào danh sách các đối số, 
ta được một danh sách kết quả

 VD h (x) ≡ x * x
α( h, (2, 3, 4)) kết quả (4, 9, 16)
14
Bản chất của NN lập trình hàm

 Mục đích của việc thiết kế NN LTH là mơ phỏng 
các hàm tốn học một cách nhiều nhất cĩ thể 
được

 Tiến trình tính tốn trong NN LTH khác NN LT 
mệnh lệnh: 
 Trong LT mệnh lệnh, biểu thức được định giá và kết 
quả của nĩ được lưu trữ trong ơ nhớ
 Quản lý biến là 1 trong những nhân tố làm phức tạp 
NNLT mệnh lệnh

 Trong NN LTH, biến khơng cần thiết, như là 
trong trường hợp của tốn học
15
Bản chất của NN lập trình hàm (tt)

 Các lệnh lập lại sẽ được xử lý bằng đệ qui

 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ố
 VD f(x) + f(x) và 2 * f(x) luơn luơn cùng kết quả

 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 mệnh lệnh
16
Bản chất của NN lập trình hàm (tt)

 Ngơn ngữ hàm cung cấp một tập hợp các hàm 
nguyên thủy và một tập các dạng hàm

 Ngồi cịn cung cấp một phép tốn áp dụng hàm 
và các cấu trúc lưu trữ dữ liệu

 Ngơn ngữ hàm được thiết kế tốt là LISP
17
NN biên dịch vs NN thơng dịch
18
LISP: giới thiệu

 Ðược John McCarthy đề xuất vào năm 1958

 Trình biên dịch LISP đầu tiên được viết bởi Tim 
Hart và Mike Levin (1962) bằng chính ngơn ngữ 
LISP

 LISP là một trong những ngơn ngữ LT sớm nhất

 LISP đã được sử dụng rộng rãi và phát triển mạnh 
trong lĩnh vực trí tuệ nhân tạo trong 1980s

 Common Lisp chuẩn ra đời năm 1984
19
Ưu điểm của LISP

 Cú pháp đơn giản
 Cấu trúc dữ liệu duy nhất: danh sách
 Khơng cĩ lệnh, khơng từ khĩa
 Tất cả các hàm đều viết ở dạng hàm

 Là một ngơn ngữ mạnh nhờ tính tương đương 
giữa dữ liệu và chương trình

 Mềm dẻo và dễ phát triển
20
Các khái miện cơ bản

 Nguyên tử (Atom): là một đối tượng cơ bản của 
LISP, nguyên tử cĩ thể là số hoặc ký hiệu
 Số: giống như trong các NNLT khác như Pascal, C
VD : các hằng số 5, -20, 10.45, 18.2E+5
 Ký hiệu (symbol): là chuỗi các ký tự (trừ các ký tự đặc 
biệt, dấu ngoặc & khoảng trống)

 Các ký hiệu được bắt đầu băng dấu «‘»

 VD ‘a, ‘anh, ‘anh_ba

 Ký hiệu số được xem là số; VD ‘5 = 5
21
Các khái miện cơ bản (tt)

 Danh sánh: dãy các 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
 Các phần tử khơng nhất thiết cĩ cùng kiểu
 Hằng danh sách được mở đầu bằng dấu «‘»
 VD 

 ‘() Danh sách rỗng, tương đương ký hiệu NIL

 ‘(a 5 c) Danh sách gồm 3 phần tử

 ‘(3 (b c) d (e (f g))) Danh sách gồm 4 phần tử
22
23
Các khái miện cơ bản (tt)

 Phân cấp dữ liệu
24
Các khái miện cơ bản (tt)

 Biểu thức: một nguyên tử hoặc một danh sách, 
luơn luơn cĩ trị được định theo nguyên tắc:
 Nếu là một số : trị là chính số đĩ
VD >25, = 25
 Nếu là ký hiệu: trị cĩ thể là 

 ðược định trước bởi LISP; VD t (TRUE), nil (NIL)

 Giá trị dữ liệu của người sử dụng, trị gán cho biến
VD >(setq a 3); gán 3 cho biến a
 Nếu là danh sách cĩ dạng (E0, E1,, En) thì trị là

 Phần tử đầu tiên phải là hàm đã được biết bởi LISP

 Các phần tử E1,, En được định trị từ trái sang phải

 VD >(+ 5 3 6) = 14; >(+ 4 (+ 3 5)) = 12
25
Các hàm

 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ể được LISP định nghĩa hoặc do người 
dùng định nghĩa

 Hàm số học: +, -, *, /, 1+, 1-, MOD, SQRT: tác động lên 
biểu thức số và cho kết quả là số
VD >(+ 5 6 2) =13
 >(- 8 3) = 5
 >(- 8 3 1) =4
 >(1+ 5) ; Tương đương (+ 5 1)
 >(1- 5) ; Tương đương (- 5 1)
>(MOD 14 3) hoặc >(sqrt 9)
26
Các hàm (tt)

 Các hàm so sánh các số , =, = và /=, cho 
kết quả là T hoặc NIL
 VD 
 >(< 4 5) = T
 >(> 4 (* 2 3)) = NIL

 (EQ s1 s2) so sánh xem hai ký hiệu s1 và s2 cĩ 
giống nhau hay khơng
 >(eq ‘tuong ‘tuong) = T
 >(eq ‘tuong ‘duong) = NIL
 >(eq ‘5 5 ) = T
27
Các hàm (tt)

 (EQUAL o1 o2) so sánh xem đối tượng bất kỳ o1
và o2 cĩ giống nhau hay khơng
 >(equal ‘(a b c) ‘(a b c)) = T
 >(equal ‘(a b c) ‘( b a c)) = NIL
 >(equal ‘a ‘a) = T
28
Các hàm thao tác trên danh sách

 CAR: nhận vào danh sách (DS) L, trả về phần tử đầu 
tiên của L
 > (CAR '(1 2 3)) = 1
 > (CAR 3) Error: bad argument type - 3
 >(CAR nil) = NIL
 > (CAR '((a b) 1 2 3)) = (A B)

 CDR: nhận DS L, trả về DS sau khi bỏ phần tử đầu 
tiên
 >(cdr '(1 2 3)) = (2 3)
 >(cdr 3) Error: bad argument type – 3
 >(CAR (CDR ‘(a b c))) = B
29
Các hàm thao tác trên DS (tt)

 Viết gộp các hàm: ta cĩ thể dùng hàm C..A/D..R 
để kết hợp nhiều CAR và CDR
 VD (CADR ‘(a b c)) = B

 (CONS x L) nhận vào phần tử x và danh sách L, 
trả về một danh sách, cĩ được bằng cách thêm 
phần tử x vào đầu danh sách L
 >(CONS 3 '(1 2 3)) = (3 1 2 3)
 >(CONS 3 nil) = (3)
 >(CONS '(a b) '(1 2 3)) = ((A B) 1 2 3)
30
Các hàm thao tác trên DS (tt)

 (APPEND L1 L2 ... Ln)
 Trả về DS là nối kết của DS L1 L2 ... Ln
 (append ‘(A) ‘(B C)) = (A B C)

 (LIST E1 E2 ... En) nhận vào n biểu thức E1, E2, ..., 
En, trả về danh sách bao gồm n phần tử V1, V2, ..., 
Vn, trong đĩ Ei là giá trị của biểu thức Ei (i=1..n)
 >(list 1 2) = (1 2)
 >(list 'a 'b) = (A B)
 >(list 'a 'b (+ 2 3 5)) = (A B 10)
31
Các hàm thao tác trên DS (tt)

 (LENGTH L)
 Trả về tổng số phần tử trong của DS L
 (length ‘(A B C D)) = 4

 (REVERSE L)
 Trả về DS đảo của DS L
 (reverse ‘(1 2 3)) = (3 2 1)
 (reverse ‘(A B C D)) = (D C B A)

 (FIRST L)
 Trả về phần tử đầu tiên của DS L
 (first ‘(A B C D)) = A
32
Các hàm thao tác trên DS (tt)

 (REST L)
 Trả về DS sau khi bỏ phần tử đầu tiên của DS L
 (rest ‘(A B C D)) = ‘(B C D)

 (LAST L)
 Trả về phần tử cuối cùng của DS L
 (last ‘(A B C D)) = D
33
Các vị từ kiểm tra

 (ATOM a) xét xem a cĩ phải là một nguyên tử

 (NUMBERP n) xét xem n cĩ phải là một số

 (LISTP L) xét xem L cĩ phải là một danh sách

 (SYMBOLP S) xét xem S cĩ phải là một ký hiệu

 (NULL L) nhận vào 1 danh sách L. Nếu L rỗng 
thì trả về kết quả là T, ngược lại thì trả về kết quả 
là NIL
 >(atom 'a) = T; >(numberp 4) = T; >(symbolp 'a) = T
 >(listp '(1 2)) = T; >(symbolp NIL) = T;
 >(null NIL) = T; >(null ‘(a b)) = NIL; >(null 10) = NIL
34
Các hàm logic AND, OR và NOT

 (AND E1 E2.. En) nhận vào n biểu thức E1, E2,... 
En
 AND định trị các biểu thức E1 E2... En từ trái sang 
phải
 Nếu gặp một biểu thức là NIL thì dừng và trả về kết 
quả là NIL. Nếu tất cả các biểu thức đều khác NIL thì 
trả về giá trị của biểu thức En
 >(AND (> 3 2) (= 3 2) (+ 3 2)) = NIL
 >(AND (> 3 2) (- 3 2) (+ 3 2)) = 5
35
Các hàm logic (tt)

 (OR E1 E2 ... En) nhận vào n biểu thức E1, E2, .... 
En
 OR định giá các biểu thức E1 E2... En từ trái sang phải
 Nếu gặp một biểu thức khác NIL thì dừng và trả về kết 
quả là giá trị của biểu thức đĩ
 Nếu tất cả các biểu thứcđều là NIL thì trả về kết quả là 
NIL
 >(OR (= 3 2) (+ 2 1) (list 1 2)) = 3
 >(OR (= 2 1) (Cdr ‘(a) ) (listp ‘(3) )) = T
36
Các hàm logic (tt)

 (NOT E) nhận vào biểu thức E
 Nếu E khác NIL thì trả về kết quả là NIL, ngược lại thì 
trả về kết quả là T
 (NOT (listp '(1 2)) = NIL
 (NOT (eq ‘tuong ‘duong)) = T
37
Các hàm điều khiển

 (IF E1 E2 E3) nhận vào 3 biểu thức E1, E2 và E3
Nếu E1 khác NIL thì hàm trả về giá trị của E2 
ngược lại trả về giá trị của E3

 (IF E1 E2) tương đương (IF E1 E2 NIL)

 Nếu E2 khác NIL thì (IF E1 E2 E3) tương đương 
(OR (AND E1 E2) E3)
38
Các hàm điều khiển (tt)
(COND (ÐK1 E1)
(ÐK2 E2)
..................
(ÐKn En)
[(T En+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 bằng NIL, thì trả về kết quả là trị của En+1
39
Các hàm điều khiển (tt)

 (PROGN E1 E2 ... En) nhận vào n biểu thức E1, 
E2,... En
 Hàm định trị các biểu thức E1, E2,... En từ trái sang phải 
và trả về kết quả là giá trị của biểu thức En

 (PROG1 E1 E2 ... En) nhận vào n biểu thức E1, 
E2,... En
 Hàm định trị các biểu thức E1, E2,... En từ trái sang phải 
và trả về kết quả là giá trị của biểu thức E1
40
Hàm do người dùng định nghĩa

 Cú pháp định nghĩa hàm là:
 (defun 
)

 Ví dụ 1: 
 Ðịnh nghĩa hàm lấy bình phương của số a
 (defun binh_phuong (a)
(* a a)
)
 >(binh_phuong 5) = 25
41
Hàm do người LT định nghĩa (tt)

 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)
)
 >(div 6 (div 4 2)) = 3
42
ðệ qui

 Mơ tả một đệ quy bao gồm:
 Cĩ ít nhất một trường hợp “dừng” để kết thúc việc gọi 
đệ quy
 Lời gọi đệ quy phải bao hàm yếu tố dẫn đến các trường 
hợp “dừng”

 Ví dụ 1: hàm giai thừa
(defun giai_thua (n)
(if (= n 0) 1 (* n (giai_thua (1- n))))
)
 (giai_thua 4) = 24
43
ðệ qui (tt)

 Ví dụ 2: hàm DIV chia a cho b lấy phần nguyên
(defun DIV (a b) 
(if (< a b) 0 (1+ (DIV (- a b) b)))
)

 Ví dụ 3: hàm truy xuất phần tử thứ i trong DS L
(defun phan_tu(i L)
(cond
((Null L) “Khong ton tai”)
((= i 1) (car L)); 
(T (phan_tu (1- i) (cdr L)))
) 
)
44
Các hàm nhập xuất

 (Load )
 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 theo quy tắc của DOS
 Dùng để load tập tin để nạp tâp tin CT trước khi gọi lời 
thực hiện các hàm trong tập tin đĩ
 VD >(Load “D:\btlisp\bai1.lsp”)
45
Các hàm nhập xuất (tt)

 (READ)
 Ðọ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

 (PRINT E)
 In tra màn hình trị biểu thức E đồng thời xuống dịng trả về giá trị 
của E

 (PRINC 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

 (TERPRI)
 ðưa con trỏ xuống dịng và trả về NIL
46
Biến tồn cục và biến cục bộ

 Biến tồn cục
 Là biến mà phạm vi của nĩ là tất cả các hàm
 Hàm (SETQ )
 VD >(setq x (* 2 3)) = 6 ↔ biến x vẫn tồn tại và cĩ giá
trị là 6

 Biến cục bộ
 Phạm vi chỉ nằm trong hàm mà nĩ được tạo ra
 Hàm (LET ( (var1 E1) (var2 E2) ... (vark Ek)) Ek+1... En)
 VD >(Let ((a 3) (b 5)) (* a b) (+ a b)) = 8
47
Biến tồn cục và biến cục bộ (tt)

 Biến cục bộ che biến tồn bộ
 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 tồn cục
 Giải pháp: kết hợp cả hai hàm LET và SETQ để sử 
dụng biến cục bộ che biến tồn cục
 VD (LET ( (var E1)..)
.
(SETQ var E2)
) 
48
Biến tồn cục và biến cục bộ (tt)
(defun giai_ptb2 ()
(let ((d 0) (e 0) (f 0))
(print ‘’Chương trình giải phương trình bậc 2’’)
(princ ‘’ Nhập số a: ‘’) (setq d (read))
(princ ‘’ Nhập số b: ‘’) (setq e (read))
(princ ‘’ Nhập số c: ‘’) (setq f (read))
(ptb2 d e f)
)
)

 Sau khi thực hiện xong chương trình này thì 
các biến d, e và f được giải phĩng
49
Exercise
1. Viết hàm cĩ 3 đối số và tính tích của hai số lớn nhất
2. Viết hàm consp kiểm tra xem đối số của nĩ cĩ phải là một 
danh sách khơng rỗng
3. Viết hàm tính xn.
4. Viết hàm tính độ dài một chuỗi.
5. Viết hàm thực hiện phép nối hai chuỗi.
(noi ‘(1 2 3) ‘(4 5)
(1 2 3 4 5)
6. Viết hàm run để cĩ đối số là một danh sách các số 
nguyên L, hàm này sẽ trả về một danh sách 2 chiều các 
dãy tăng (run) trong L
>(run ‘(1 2 3 2 1 5 4 7)) = ((1 2 3) (2) (1 5) (4 7))