Ngôn ngữ lập trình hàm: 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

Giảng viên: Ph.D Nguyễn Văn Hòa Khoa KT-CN-MT – ðH An Giang

Một số ñặc trưng của NN mệnh lệnh

dần

(cid:1) Sử dụng nguyên lý tinh chế từng bước, hay mịn

trúc

(cid:1) Khai báo dữ liệu ñể nối kết tên biến → trị (cid:1) Các kiểu dữ liệu cơ bản → kiểu dữ liệu có cấu

trình con (cid:1) Hiệu ứng lề (cid:1) Lập trình cấu trúc: khối, chương trình con,

module

(cid:1) Cấu trúc ñiều khiển từng tự, rẽ nhánh, gọi chương

Nội dung chính của chương

(cid:1) Giới thiệu (cid:1) Hàm toán học (cid:1) Dạng hàm (cid:1) Bản chất của lập trình hàm (cid:1) Ngôn ngữ LISP

Giới thiệu

(cid:1) 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 (cid:2) ðơn trị làm việc trong chương trình là câu lệnh (cid:2) 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

dựa trên các hàm toán học → ngôn ngữ không ra lệnh (cid:2) Vì dựa trên nguyên lý hàm toá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

(cid:1) Ngôn ngữ lập trình hàm (LTH) ñược xây dựng

Hàm toán học

(cid:1) Mỗi hàm toá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ị)

phần tử của miền giá trị

(cid:1) Mỗi phần tử của miền xác ñịnh tương ứng một

(cid:1) 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ạ)

(cid:2) Tên hàm + danh sách tham số ≡ biểu thức (cid:2) VD lap_phuong(x) ≡ x*x*x ;

(cid:1) ðịnh nghĩa hàm

Biểu thức lambda

biểu thức lambda (cid:2) VD l (x) x * x * x thay thế lap_phuong(x) ≡

x*x*x

(cid:1) ðôi khi người ta dùng hàm không tên → sử dụng

ghép

(cid:1) Tham số biểu thức lambda gọi là tham số biến kết

(cid:1) 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ố ñó (cid:2) (l (x) x * x * x)(2) có giá trị là 8

Ngôn ngữ lập trình hàm

(cid:1) Tập hợp các ñối tượng dữ liệu (cid:1) Các hàm nguyên thủy (cid:1) Các dạng hàm (cid:1) Tác vụ áp dụng hàm

ðối tượng dữ liệu

ñơn giản (cid:2) Nguyên tử (Atom): một chuỗi các ký tự; ABC, 123, Z34 (cid:2) Hai nguyên tử ñặc biệt: T và F (cid:2) Dãy n các ñối tượng x1, x2, …, xn ñược ký hiệu là < x1,

x2, …, xn>

(cid:2) NIL là ký hiệu dãy rỗng

(cid:1) ðối tượng dữ liệu của ngôn ngữ lập trình hàm rất

Hàm nguyên thủy

(cid:2) Nhóm hàm số học: +, -,*, / (cid:2) Nhóm hàm vị từ: ATOM và NULL (cid:2) Hàm ñồng nhất ID:x ≡ x (cid:2) Nhóm liên quan ñến cấu trúc danh sánh (dãy)

(cid:1) Là các hàm ñược ñịnh nghĩa sẵn trong ngôn ngữ (cid:1) Bón nhóm dạng hàm nguyên thủy

Dạng 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

(cid:1) Dạng hàm là sự tổ hợp của các hàm: một hàm

(cid:1) Các dạng hàm (cid:2) Hàm hợp (cid:2) Hàm xây dựng (cid:2) Hàm áp dụng cho tất cả

Hàm hợp (composition)

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

(cid:1) 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 (cid:1) VD hàm hợp của h

Hàm xây dựng (construction)

cũng là hàm

(cid:1) Hàm xây dụng là hàm mà các tham số của chúng

ñối số ñược áp dụng vào hàm tham số → tập hợp kết quả

(cid:1) Ký hiệu hàm xây dựng: [] (cid:1) Khi áp dụng vào một ñối số vào hàm xây dựng:

(cid:2) G(x) ≡ x*x, H(x) ≡ 2*x và I(x) ≡ x/2 (cid:2) [G,H,I](4) có kết quả là (16,8,2)

(cid:1) VD

Áp dụng cho tất cả

ta ñược một danh sách kết quả

(cid:1) Là hàm lấy một hàm ñơn như là một tham số (cid:1) Hàm áp dụng cho tất cả ñược ký hiệu là a (cid:1) Áp dụng hàm tham số vào danh sách các ñối số,

a ( h, (2, 3, 4)) kết quả (4, 9, 16)

(cid:1) VD h (x) ” x * x

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

(cid:1) Mục ñích của việc thiết kế NN LTH là mô phỏng các hàm toán học một cách nhiều nhất có thể ñược

mệnh lệnh: (cid:2) 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ớ

(cid:2) Quản lý biến là 1 trong những nhân tố làm phức tạp

NNLT mệnh lệnh

(cid:1) Tiến trình tính toán trong NN LTH khác NN LT

trong trường hợp của toán học

(cid:1) Trong NN LTH, biến không cần thiết, như là

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

dụng hàm

(cid:1) Các lệnh lập lại sẽ ñược xử lý bằng ñệ qui (cid:1) Chương trình là các ñịnh nghĩa hàm và các áp

khi ta cho nó cùng một ñối số (cid:2) VD f(x) + f(x) và 2 * f(x) luôn luôn cùng kết quả (cid:1) 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

(cid:1) Sự thực hiện là việc ñánh giá các áp dụng hàm (cid:1) Sự thực hiện một hàm luôn cho cùng một kết quả

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

nguyên thủy và một tập các dạng hàm

(cid:1) Ngôn ngữ hàm cung cấp một tập hợp các hàm

và các cấu trúc lưu trữ dữ liệu

(cid:1) Ngoài còn cung cấp một phép toán áp dụng hàm

(cid:1) Ngôn ngữ hàm ñược thiết kế tốt là LISP

NN biên dịch vs NN thông dịch

LISP: giới thiệu

(cid:1) Ðược John McCarthy ñề xuất vào năm 1958 (cid:1) 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

trong lĩnh vực trí tuệ nhân tạo trong 1980s

(cid:1) LISP là một trong những ngôn ngữ LT sớm nhất (cid:1) LISP ñã ñược sử dụng rộng rãi và phát triển mạnh

(cid:1) Common Lisp chuẩn ra ñời năm 1984

Ưu ñiểm của LISP

(cid:2) Cấu trúc dữ liệu duy nhất: danh sách (cid:2) Không có lệnh, không từ khóa (cid:2) Tất cả các hàm ñều viết ở dạng hàm

(cid:1) Cú pháp ñơn giản

giữa dữ liệu và chương trình

(cid:1) Là một ngôn ngữ mạnh nhờ tính tương ñương

(cid:1) Mềm dẻo và dễ phát triển

Các khái miện cơ bản

LISP, nguyên tử có thể là số hoặc ký hiệu (cid:2) 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

(cid:2) 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) (cid:1) Các ký hiệu ñược bắt ñầu băng dấu «‘» (cid:1) VD ‘a, ‘anh, ‘anh_ba (cid:1) Ký hiệu số ñược xem là số; VD ‘5 = 5

(cid:1) Nguyên tử (Atom): là một ñối tượng cơ bản của

Các khái miện cơ bản (tt)

một danh sách

(cid:2) Các phần tử không nhất thiết có cùng kiểu (cid:2) Hằng danh sách ñược mở ñầu bằng dấu «‘» (cid:2) VD

(cid:1) ‘() Danh sách rỗng, tương ñương ký hiệu NIL (cid:1) ‘(a 5 c) Danh sách gồm 3 phần tử (cid:1) ‘(3 (b c) d (e (f g))) Danh sách gồm 4 phần tử

(cid:1) 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 () (cid:2) Phần tử của danh sách có thể là một nguyên tử hoặc là

Các khái miện cơ bản (tt)

(cid:1) Phân cấp dữ liệu

Các khái miện cơ bản (tt)

VD >25, = 25

(cid:2) Nếu là ký hiệu: trị có thể là

(cid:1) ðược ñịnh trước bởi LISP; VD t (TRUE), nil (NIL) (cid:1) 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

(cid:2) Nếu là danh sách có dạng (E0, E1,…, En) thì trị là (cid:1) Phần tử ñầu tiên phải là hàm ñã ñược biết bởi LISP (cid:1) Các phần tử E1,…, En ñược ñịnh trị từ trái sang phải (cid:1) VD >(+ 5 3 6) = 14; >(+ 4 (+ 3 5)) = 12

(cid:1) 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: (cid:2) Nếu là một số : trị là chính số ñó

Các hàm

(cid:1) Một chương trình của LISP là một hàm hoặc một hàm

hợp

(cid:1) Các hàm có thể ñược LISP ñịnh nghĩa hoặc do người

dùng ñịnh nghĩa

(cid:1) 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)

Các hàm (tt)

kết quả là T hoặc NIL (cid:2) VD (cid:2) >(< 4 5) = T (cid:2) >(> 4 (* 2 3)) = NIL

(cid:1) Các hàm so sánh các số <, >, <=, >=, = và /=, cho

giống nhau hay không (cid:2) >(eq ‘tuong ‘tuong) = T (cid:2) >(eq ‘tuong ‘duong) = NIL (cid:2) >(eq ‘5 5 ) = T

(cid:1) (EQ s1 s2) so sánh xem hai ký hiệu s1 và s2 có

Các hàm (tt)

và o2 có giống nhau hay không (cid:2) >(equal ‘(a b c) ‘(a b c)) = T (cid:2) >(equal ‘(a b c) ‘( b a c)) = NIL (cid:2) >(equal ‘a ‘a) = T

(cid:1) (EQUAL o1 o2) so sánh xem ñối tượng bất kỳ o1

Các hàm thao tác trên danh sách

(cid:1) CAR: nhận vào danh sách (DS) L, trả về phần tử ñầu

tiên của L (cid:2) > (CAR '(1 2 3)) = 1 (cid:2) > (CAR 3) Error: bad argument type - 3 (cid:2) >(CAR nil) = NIL (cid:2) > (CAR '((a b) 1 2 3)) = (A B)

(cid:1) CDR: nhận DS L, trả về DS sau khi bỏ phần tử ñầu

tiên (cid:2) >(cdr '(1 2 3)) = (2 3) (cid:2) >(cdr 3) Error: bad argument type – 3 (cid:2) >(CAR (CDR ‘(a b c))) = B

Các hàm thao tác trên DS (tt)

ñể kết hợp nhiều CAR và CDR (cid:2) VD (CADR ‘(a b c)) = B

(cid:1) Viết gộp các hàm: ta có thể dùng hàm C..A/D..R

(cid:1) (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 (cid:2) >(CONS 3 '(1 2 3)) = (3 1 2 3) (cid:2) >(CONS 3 nil) = (3) (cid:2) >(CONS '(a b) '(1 2 3)) = ((A B) 1 2 3)

Các hàm thao tác trên DS (tt)

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

(cid:1) (APPEND L1 L2 ... Ln)

(cid:1) (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) (cid:2) >(list 1 2) = (1 2) (cid:2) >(list 'a 'b) = (A B) (cid:2) >(list 'a 'b (+ 2 3 5)) = (A B 10)

Các hàm thao tác trên DS (tt)

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

(cid:1) (LENGTH L)

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

(cid:1) (REVERSE L)

(cid:2) Trả về phần tử ñầu tiên của DS L (cid:2) (first ‘(A B C D)) = A

(cid:1) (FIRST L)

Các hàm thao tác trên DS (tt)

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

(cid:1) (REST L)

(cid:2) Trả về phần tử cuối cùng của DS L (cid:2) (last ‘(A B C D)) = D

(cid:1) (LAST L)

Các vị từ kiểm tra

thì trả về kết quả là T, ngược lại thì trả về kết quả là NIL (cid:2) >(atom 'a) = T; >(numberp 4) = T; >(symbolp 'a) = T (cid:2) >(listp '(1 2)) = T; >(symbolp NIL) = T; (cid:2) >(null NIL) = T; >(null ‘(a b)) = NIL; >(null 10) = NIL

(cid:1) (ATOM a) xét xem a có phải là một nguyên tử (cid:1) (NUMBERP n) xét xem n có phải là một số (cid:1) (LISTP L) xét xem L có phải là một danh sách (cid:1) (SYMBOLP S) xét xem S có phải là một ký hiệu (cid:1) (NULL L) nhận vào 1 danh sách L. Nếu L rỗng

Các hàm logic AND, OR và NOT

En (cid:2) AND ñịnh trị các biểu thức E1 E2... En từ trái sang

phải

(cid:2) 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

(cid:2) >(AND (> 3 2) (= 3 2) (+ 3 2)) = NIL (cid:2) >(AND (> 3 2) (- 3 2) (+ 3 2)) = 5

(cid:1) (AND E1 E2.. En) nhận vào n biểu thức E1, E2,...

Các hàm logic (tt)

En (cid:2) OR ñịnh giá các biểu thức E1 E2... En từ trái sang phải (cid:2) 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 ñó

(cid:2) Nếu tất cả các biểu thứcñều là NIL thì trả về kết quả là

NIL

(cid:2) >(OR (= 3 2) (+ 2 1) (list 1 2)) = 3 (cid:2) >(OR (= 2 1) (Cdr ‘(a) ) (listp ‘(3) )) = T

(cid:1) (OR E1 E2 ... En) nhận vào n biểu thức E1, E2, ....

Các hàm logic (tt)

(cid:2) 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

(cid:2) (NOT (listp '(1 2)) = NIL (cid:2) (NOT (eq ‘tuong ‘duong)) = T

(cid:1) (NOT E) nhận vào biểu thức E

Các hàm ñiều khiển

(cid:1) (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

(OR (AND E1 E2) E3)

(cid:1) (IF E1 E2) tương ñương (IF E1 E2 NIL) (cid:1) Nếu E2 khác NIL thì (IF E1 E2 E3) tương ñương

Các hàm ñiều khiển (tt)

(COND (ÐK1 E1) (ÐK2 E2) .................. (ÐKn En) [(T En+1)]

)

(cid: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. (cid:1) 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... (cid:1) Nếu ðKn bằng NIL, thì trả về kết quả là trị của En+1

Các hàm ñiều khiển (tt)

E2,... En (cid:2) 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

(cid:1) (PROGN E1 E2 ... En) nhận vào n biểu thức E1,

E2,... En (cid:2) 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

(cid:1) (PROG1 E1 E2 ... En) nhận vào n biểu thức E1,

Hàm do người dùng ñịnh nghĩa

(cid:2) (defun

) (cid:1) Ví dụ 1:

(cid:2) Ðịnh nghĩa hàm lấy bình phương của số a (cid:2) (defun binh_phuong (a)

(* a a)

)

(cid:2) >(binh_phuong 5) = 25

(cid:1) Cú pháp ñịnh nghĩa hàm là:

Hàm do người LT ñịnh nghĩa (tt)

(cid:2) Ðịnh nghĩa hàm DIV chia số a cho số b, lấy phần

nguyên

(cid:2) Trước hết ta có: a DIV b = (a – a MOD b)/b

(defun DIV (a b)

(/ (- a (MOD a b)) b)

)

(cid:2) >(div 6 (div 4 2)) = 3

(cid:1) Ví dụ 2:

ðệ qui

(cid:2) Có ít nhất một trường hợp “dừng” ñể kết thúc việc gọi

ñệ quy

(cid:2) Lời gọi ñệ quy phải bao hàm yếu tố dẫn ñến các trường

hợp “dừng”

(cid:1) Mô tả một ñệ quy bao gồm:

(defun giai_thua (n)

(if (= n 0) 1 (* n (giai_thua (1- n))))

)

(cid:2) (giai_thua 4) = 24

(cid:1) Ví dụ 1: hàm giai thừa

ðệ qui (tt)

(cid:1) 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)))

)

(cid:1) 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)))

)

Các hàm nhập xuất

(cid:2) 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 (cid:2) Tên tập tin theo quy tắc của DOS (cid:2) 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 ñó

(cid:2) VD >(Load “D:\btlisp\bai1.lsp”)

(cid:1) (Load )

Các hàm nhập xuất (tt)

(cid:1) (READ)

(cid:2) Ðọc dữ liệu từ bàn phím cho ñến khi gõ phím Enter (cid:2) trả về kết quả là dữ liệu ñược nhập từ bàn phím

(cid:1) (PRINT E)

(cid:2) 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 (cid:1) (PRINC E)

(cid:2) 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

(cid:1) (TERPRI)

(cid:2) ðưa con trỏ xuống dòng và trả về NIL

Biến toàn cục và biến cục bộ

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

trị là 6 (cid:1) Biến cục bộ

(cid:2) Phạm vi chỉ nằm trong hàm mà nó ñược tạo ra (cid:2) Hàm (LET ( (var1 E1) (var2 E2) ... (vark Ek)) Ek+1... En) (cid:2) VD >(Let ((a 3) (b 5)) (* a b) (+ a b)) = 8

(cid:1) Biến toàn cục

Biến toàn cục và biến cục bộ (tt)

(cid:2) 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 (cid:2) 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 toàn cục

(cid:2) VD (LET ( (var E1)…..)

……. (SETQ var E2) …… )

(cid:1) Biến cục bộ che biến toàn bộ

Biến toà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)

)

) (cid:1) 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