TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN
────────*────────
TIỂU LUẬN MÔN HỌC
NGUYÊN LÝ CÁC NGÔN NGỮ LẬP TRÌNH
ĐỀ TÀI: LẬP TRÌNH HÀM
TÌM HIỂU VÀ ÁP DỤNG NGÔN NGỮ LISP
GIẢI BÀI TOÁN “THÁP HÀ NỘI”
Nhóm thực hiện : Tạ Xuân Thọ
Nguyễn Trần Minh
Hà Minh Đức
Lớp : 13BCNNT1
Giáo viên hướng dẫn : TS. Cao Tuấn Dũng
Hà Nội 12/2013
Lập trình hàm – tìm hiểu và áp dụng ngôn ngữ Lisp giải bài toán “Tháp Hà Nội”
MỤC LỤC
MỞ ĐẦU
Theo thống kê đã có khoảng 2500 ngôn ngữ lập trình được phát triển và
sử dụng trên toàn thế giới. Hầu hết các ngôn ngữ lập trình được thiết kế dựa
trên nguyên lý Von Newmann, phụ thuộc rất nhiều vào phần cứng của máy tính,
đó là các ngôn ngữ lập trình mệnh lệnh. Do sự phổ biến, sự ứng dụng mạnh mẽ
vào việc phát triển các ứng dụng thương mại và sự chấp nhận rộng rãi ngôn
ngữ lập trình mệnh lệnh nên phần lớn các lập trình viên chỉ nghe qua và thậm
Nhóm 11
2
Lập trình hàm – tìm hiểu và áp dụng ngôn ngữ Lisp giải bài toán “Tháp Hà Nội”
chí không biết đến các ngôn ngữ lập trình dạng khác, như lập trình logic hay
lập trình hàm.
Nhằm mục đích hiểu sâu hơn về môn học “Nguyên lý các ngôn ngữ lập
trình” và cũng là cơ hội tìm hiểu, tiếp cận cách tư duy khác về lập trình, tiểu
luận Nhóm 11 sẽ trình bày các tìm hiểu và áp dụng ngôn ngữ lập trình hàm vào

yếu của ngôn ngữ đó. Tuy nhiên, hầu hết các ngôn ngữ từ trước đến nay là ngôn
Nhóm 11
4
Lập trình hàm – tìm hiểu và áp dụng ngôn ngữ Lisp giải bài toán “Tháp Hà Nội”
ngữ lập trình mệnh lệnh, dựa trên nguyên lý kiến trúc máy tính Von Newmann
và được phát triển rộng rãi, như C, C++, Pascal… Mặc dù phát triển và được hầu
hết lập trình viên chấp nhận, nhưng ngôn ngữ lập trình mệnh lệnh là một sự hạn
chế trong việc phát triển phần mềm do quá phụ thuộc vào kiến trúc máy tính.
Ngược lại, ngôn ngữ lập trình hàm ra đời và phát triển dựa trên các hàm toán
học, là dạng ngôn ngữ không ra lệnh.
Lập trình hàm xuất phát từ phép tính labada, một hệ thống hình thức được
phát triển để nghiên cứu định nghĩa hàm số, ứng dụng của hàm số và đệ quy.
Lập trình hàm là một mô hình lập trình xem việc tính toán là sự đánh giá các
hàm toán học, tránh sử dụng các trạng thái và các kiểu dữ liệu biến đổi, nhấn
mạnh vào việc ứng dụng các hàm sô, trái ngược với lập trình mệnh lệnh nhấn
mạnh vào sự thay đổi trạng thái.
Trong thực tế, sự khác biệt giữa hàm số toán học và hàm trong lập trình
mệnh lệnh đó là hiệu ứng lề: là hiệu ứng làm thay đổi giá trị phép tính trước đó.
Điều đó có nghĩa là cùng một biểu thức ngôn ngữ lại có thể tạo ra nhiều giá trị
khác nhau vào các thời điểm khác nhau tùy vào trạng thái của chương trình đang
thực thi. Trái lại, trong lập trình hàm, giá trị xuất ra của một hàm chỉ phụ thuộc
các tham số đầu vào của hàm, do đó gọi hàm nhiều lần với cùng tham số sẽ cho
kết quả như nhau. Loại bỏ hiệu ứng lề khiến chương trình dễ hiểu và dễ dự đoán
được hành vi của chương trình, đó cũng là điểm mạnh cho sự phát triển của lập
trình hàm.
Hiện nay, các ngôn ngữ lập trình hàm chủ yếu ảnh hưởng đến giới nghiên
cứu nhiều hơn là thương mại vì nhiều lý do. Một số các ngôn ngữ nổi bật như
Haskell, Sheme, Lisp… mà trong phần sau chủ yếu sẽ trình bày về ngôn ngữ
Lisp.
1.2. Hàm toán học

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ả.
- Ví dụ: f(x) = x, g(x) = x+1 và h(x) = x*x*x thì [f,g,h](4) có kết quả là
(4,5,64)
1.4.3. Hàm áp dụng cho tất cả
- Là hàm lấy một hàm đơn như là một tham số, 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ả.
- Ví dụ: f(x) = x * x thì α( f, (1,2)) kết quả (1, 4)
Nhóm 11
6
Lập trình hàm – tìm hiểu và áp dụng ngôn ngữ Lisp giải bài toán “Tháp Hà Nội”
1.5. Bản chất ngôn ngữ lập trình hàm
Mục đích 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. Tiến trình tính toán trong ngôn ngữ
lập trình hàm khác ngôn ngữ lập trình mệnh lệnh:
- Trong lập trình 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à một trong những nhân tố làm
phức tạp thiết kế ngôn ngữ lập trình, trong ngôn ngữ lập trình hàm biến
là không cần thiết.
- 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ố.Ví dụ: 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.
2. NGÔN NGỮ LISP
Lisp - viết tắt bởi từ LIST PROCESSING - phát triển từ rất sớm (1958),

2.2. Các khái niệm cơ bản
Cũng như các ngôn ngữ lập trình khác, chương trình viết bằng ngôn ngữ
Lisp được xây dựng nên từ các đối tượng cơ bản:
2.2.1. Nguyên tử (atom)
Nguyên tử là khái niệm cơ bản của Lisp, nguyên tử có thể là số
hoặc ký hiệu.
- Số: biểu diễn như trong các ngôn ngữ lập trình khác, ví dụ 1,-2, 1/3,…
- Ký hiệu: là một chuỗi các ký tự , trừ các ký tự đặc biệt, dấu ngoặc đơn
và khoảng trống. Các hằng ký hiệu được biểu diển bởi một dấu nháy
đơn đằng trước (ví dụ ‘A, ‘Anh), các hằng ký hiệu số được xem như là
số (ví dụ ‘2 = 2) và một số hằng ký hiệu được định nghĩa trước ( như T
= True, NIL = null…).
2.2.2. Danh sách (list)
Danh sách là kiểu cấu trúc duy nhất trong Lisp, là một dãy các phần
tử ngăn cách nhau bởi khoảng trắng, có phân biệt thứ tự và đặt trong cặp
ngoặc đơn. Hằng danh sách được bắt đầu bởi dấu nháy đơn đằng trước,
phần tử của danh sách có thể là nguyên tử hoặc danh sách khác.
Ví dụ:
Nhóm 11
8
Lập trình hàm – tìm hiểu và áp dụng ngôn ngữ Lisp giải bài toán “Tháp Hà Nội”
- Hằng danh sách: ‘(1 2 3), ‘(a b c)…
- Danh sách là phần tử: ‘(a (b c) d e)…
2.2.3. Biểu thức
Biểu thức luôn có một giá trị, có thể là một nguyên tử hoặc một
danh sách. Cách xác định giá trị biểu thức như sau:
- Nếu biểu thức là một số thì giá trị biểu thức là giá trị của số đó.
- Nếu biểu thức là một ký hiệu thì giá trị của biểu thức sẽ được xác định
bởi Lisp (như T có giá trị TRUE) hoặc giá trị người dùng gán cho biến
được xác định bởi ký hiệu đó. Ví dụ:

dụ:
> (+ 1 2 3) ; tính giá trị biểu thức
> 6 ; giá trị hàm + là 6
2.3. Hàm trên Lisp
Chương trình trên Lisp là một hàm hoặc hàm hợp, có thể là các hàm đã
được xây dựng sẵn trong ngôn ngữ hoặc hàm do người dùng định nghĩa. Trong
phần này tiểu luận sẽ giới thiệu một số hàm cơ bản của Lisp và cách xây dựng
hàm do người dùng định nghĩa.
2.3.1. Hàm số học
Hàm số học tác động lên các biểu thức số học, kết quả trả về là một
số. Các hàm số học được xây dựng sẵn trong ngôn ngữ Lisp:
- Hàm +,-,*,/: thực hiện phép toán cộng, trừ, nhân, chia trên các số:
> (+ 1 2 3) = 6 ; phép toán cộng
> (- (+ 1 2) 3) = 0 ; phép toán trừ
- Hàm MOD, SQRT: thực hiện phép chia lấy dư, phép bình phương:
> (MOD 10 3) = 1 ; phép chia lấy dư
> (SQRT 10) = 100 ; phép bình phương
Nhóm 11
9
Lập trình hàm – tìm hiểu và áp dụng ngôn ngữ Lisp giải bài toán “Tháp Hà Nội”
2.3.2. Hàm so sánh
Hàm so sánh xây dựng sẵn có nhiều loại: so sánh giá trị số, so sánh
ký hiệu hoặc so sánh hai đối tượng bất kỳ:
- Hàm >, <, >=, <=, =, /=: thực hiện phép so sánh giá trị trên các số, kết
quả là T (True) hoặc NIL (trong Lisp không có giá trị False):
> (> 1 2) = NIL ; so sánh 1 >2, kết quả NIL
> (< 1 2) = T ; so sánh 1 >2, kết quả T
- Hàm EQ: so sánh hai ký hiệu:
> (EQ ‘a ‘ab) = NIL ; so sánh ký hiệu ‘a và ‘ab
- Hàm EQUAL: so sánh hai đối tượng bất kỳ:

) nhận vào các biểu thức E
0
, E
1
, … E
n
sau
đó định trị từ trái qua phải, nếu E
k
<> NIL thì hàm trả về giá trị biểu
thức đó và dừng tính toán, nếu không hàm sẽ trả lại giá trị NIL;
> (OR (- 1 3) (+ 1 2)) = -2 ; biểu thức đầu tiên không NIL
- Hàm NOT: (NOT E) nhận biểu thức E, nếu E <> NIL thì trả về NIL và
ngược lại trả về T.
> (NOT (>1 2)) = T ; biểu thức NIL, trả lại T
2.3.4. Hàm thao tác trên danh sách
Do xử lý chủ yếu trên các danh sách nên trong Lisp định nghĩa sẵn
một số hàm cơ bản để thao tác với danh sách thuận tiện hơn:
- Hàm CAR: (CAR L) nhận vào danh sách L và trả về phần tử đầu tiên
của danh sách. Trình thông dịch sẽ báo lỗi nếu L không phải là danh
sách:
> (CAR ‘(1 2 3)) = 1 ; trả lại 1 là phần tử đầu tiên
> (CAR NIL) = NIL ; trả lại NIL với danh sách rỗng
Nhóm 11
10
Lập trình hàm – tìm hiểu và áp dụng ngôn ngữ Lisp giải bài toán “Tháp Hà Nội”
> (CAR 1) = error ; lỗi khi không phải là danh sách
- Hàm CDR: (CDR L) nhận vào sách sách L và trả về phần còn lại của
danh sách trừ phần tử đầu tiên. Tương tự CAR, khi sử dụng CDR sẽ
nhận được báo lỗi nếu L không phải là danh sách:

> (LENGTH ‘(1 2 3)) = 3 ; danh sách có 3 phần tử
- Hàm REVERSE: (REVERSE L) đảo ngược danh sách:
> (REVERSE NIL) = NIL ; danh sách rỗng
> (REVERSE ‘(1 2 3)) = (3 2 1) ; danh sách có 3 phần tử
- Hàm APPEND: (APPEND L1 L2) kết hợp các danh sách:
> (APPEND ‘(1 2) ‘(2 4) = (1 2 3 4) ;kết hợp 02 danh sách
2.3.5. Hàm điều khiển
Lisp hỗ trợ một số hàm điều khiển IF, COND, PROG1 và PROGN:
a. Hàm IF:
- Hàm (IF E
1
E
2
E
3
) nhận vào 3 biểu thức E
1
E
2
E
3
, kết quả trả về nếu E
1
khác NIL, ngược lại là E
3
.
- Hàm có thể viết gọn (IF E
1
E
2

)
(ĐK
2
E
2
)
(ĐK
3
E
3
)
Nhóm 11
11
Lập trình hàm – tìm hiểu và áp dụng ngôn ngữ Lisp giải bài toán “Tháp Hà Nội”
…
[(T E
n+1
)]
)
- Hàm sẽ dừng và trả lại giá trị E
k
nếu ĐK
k
khác NIL. Nếu tất cả các ĐK
đều NIL sẽ trả lại NIL hoặc giá trị E
n+1
nếu có khai báo.
c. Hàm PROG1:
- Hàm (PROG1 E
1

n
.
> (PROGN (+ 1 2) (+ 2 3)) = 5 ; trả lại giá trị biểu thức cuối cùng
2.3.6. Hàm xuất/nhập
Một số hàm xuất nhập cơ bản như đọc dữ liệu từ bàn phím, xuất giá trị ra
màn hình là các hàm thường dùng:
- Hàm READ: (READ) đọc dữ liệu từ bàn phím, kết thúc khi nhấn phìm
Enter và trả lại dữ liệu đã được nhập.
- Hàm PRINT: (PRINT E) xuất dữ liệu biểu thức E ra màn hình, xuống
dòng và trả lại giá trị biểu thức E.
- Hàm PRINC: (PRINC E) xuất dữ liệu biểu thức E ra màn hình trên
cùng một dòng và trả lại giá trị biểu thức E.
- Hàm FORMAT: (FORMAT T “~A~%” E) sử dụng xuất dữ liệu biểu
thức E ra màn hình, trong đó ~A tương ứng vị trì biểu thức E, ~% nếu
định dạng xuống dòng.
2.3.7. Biến số
Trong lập trình hàm, việc sử dụng biến số nên hạn chế tối đa và nếu cần
thiết thì nên sử dụng các biến số cụ bộ.
Biến toàn cục: là biến mà phạm vi của nó có thể sử dụng trong tất cả các
hàm, biến được giải phòng khi chương trình kết thúc.
Biến cục bộ: là biến mà phạm vi của nó chỉ nằm trong hàm tạo ra nó vf sẽ
tự giải phóng khi hàm kết thúc.
Một số các hàm khai báo biến và cách khai báo biến cục bộ:
Nhóm 11
12
Lập trình hàm – tìm hiểu và áp dụng ngôn ngữ Lisp giải bài toán “Tháp Hà Nội”
- Hàm SETQ: (SETQ x E): khai báo biến x, gán giá trị bằng biểu thức E.
Biến khai báo trở thành biến toàn cục, không mất đi sau khi hàm thực
hiện xong.
> (SETQ x 100) ; khai báo biến x, gán cho biến giá trị 100

n
từ
trái qua phải, trả lại E
n
. Để sử dụng V
i
như biến cục bộ, trong phần
định trị biểu thức sử dụng SETQ để gán giá trị cho biến vừa tạo ra.
2.3.8. Đệ quy
Cũng như các ngôn ngữ lập trình khác, Lisp xử lý các hàm đệ quy và xử
lý rất mạnh. Đệ quy là hàm có lời gọi đến chính nó trong biểu thức định nghĩa
hàm. Hàm đệ quy có hai đặc tính:
- Phải có ít nhất một trường hợp dừng để có thể kết thúc lời gọi đệ quy.
- Lời gọi đệ quy phải bao hàm yếu tố xảy ra trường hợp dừng.
- Ví dụ hàm tính giai thừa:
(defun giai_thua(n)
(if (= n 0) 1 ; trường hợp dừng
(* n (giai_thua (- n 1))))) ; đệ quy
3. ỨNG DỤNG GIẢI BÀI TOÁN “THÁP HÀ NỘI”
Trong phần này tiểu luận sẽ tình bày về bài toán “Tháp Hà Nội”, phân tích
bài toán dưới góc độ đệ quy, áp dụng viết chương trình giải trên LISP.
3.1. Bài toán “Tháp Hà Nội”
Về mặt lịch sử, Tháp Hà Nội được E.Lucas phát hiện từ năm 1883, nhưng
chưa rõ vì sao Lucas lại gọi chồng đĩa trong bài toán là Tháp Hà Nội. Bài toán
thường được lấy làm ví dụ trong các giải thuật đệ quy khi trình bày trong các
cuốn sách về lập trình. Lời giải tối ưu cho bài toán có thể tìm thấy chính xác
trong trường hợp ba cọc, nhưng khi mở rộng số cọc thì hiện nay lời giải chính
xác vẫn chưa được khẳng định, vì thế trong phạm vi tiểu luận, chúng ta sẽ xem
xét bài toán với ba cọc đĩa.
Nhóm 11

nằm trên đĩa lớn. *thapA* có dạng: (1 2 3 4 5 6…).
- *thapB* là tháp đích, khởi tạo bởi danh sách trống.
- *thapC* là tháp trung gian
Nhóm 11
14
Lập trình hàm – tìm hiểu và áp dụng ngôn ngữ Lisp giải bài toán “Tháp Hà Nội”
- *count* là biến đếm số lần dịch chuyển
3.2.2. Hàm thực hiện:
- Hàm IN_CHI_TIET: có chức năng in lại tình trạng các tháp để có được
cái nhìn sau mỗi lần dịch chuyển.
(defun in_chi_tiet()
(format t "Thap A: ~A,"
(if (= (length *thapA*) 0) "()" (reverse *thapA*)))
(format t "Thap B: ~A,"
(if (= (length *thapB*) 0) "()" (reverse *thapB*)))
(format t "Thap C: ~A~%"
(if (= (length *thapC*) 0) "()" (reverse *thapC*)))
) ; in tình trạng các tháp sau mỗi lần thực hiện
- Hàm CHUYEN: thưc hiện việc chuyển 1 đĩa từ tháp này sang tháp kia,
sử dụng cơ chế POP và PUSH
(defun chuyen(thapNguon thapDich)
(if (not (eq thapNguon thapDich))
(let ((tg 0)) ; khai báo biến trung gian
; đếm số lần chuyển
(setq *count* (1+ *count*))
; pop phần tử trong danh sách tương ứng
(if (eq thapNguon 'A) (setq tg (pop *thapA*)))
(if (eq thapNguon 'B) (setq tg (pop *thapB*)))
(if (eq thapNguon 'C) (setq tg (pop *thapC*)))
; push phần tử vào danh sách tương ứng

(format t "Ban dau: ")
(in_chi_tiet)
(de_quy sodia 'A 'B 'C)
(format t "Ket thuc: ")
(in_chi_tiet)
(format t "So lan chuyen: ~A" *count*)
)
)
- Chương trình bắt đầu thực hiện với lời gọi:
> (THAP_HA_NOI)
3.3. Kết quả chạy ứng dụng
Nhóm 11
16
Lập trình hàm – tìm hiểu và áp dụng ngôn ngữ Lisp giải bài toán “Tháp Hà Nội”
Chương trình thực hiện tốt, kiểm tra đã thấy chạy đúng thuật toán. Trong
trường hợp tăng số đĩa thì số lần di chuyển tăng nhanh theo đúng công thức
(2
so_dia
- 1). Lời giải trong trường hợp 5 đĩa:
So dia: 5
Ban dau: Thap A: (5 4 3 2 1),Thap B: (),Thap C: ()
Dia 1 tu thap A sang thap B: Thap A: (5 4 3 2),Thap B: (1),Thap C: ()
Dia 2 tu thap A sang thap C: Thap A: (5 4 3),Thap B: (1),Thap C: (2)
Dia 1 tu thap B sang thap C: Thap A: (5 4 3),Thap B: (),Thap C: (2 1)
Dia 3 tu thap A sang thap B: Thap A: (5 4),Thap B: (3),Thap C: (2 1)
Dia 1 tu thap C sang thap A: Thap A: (5 4 1),Thap B: (3),Thap C: (2)
Dia 2 tu thap C sang thap B: Thap A: (5 4 1),Thap B: (3 2),Thap C: ()
Dia 1 tu thap A sang thap B: Thap A: (5 4),Thap B: (3 2 1),Thap C: ()
Dia 4 tu thap A sang thap C: Thap A: (5),Thap B: (3 2 1),Thap C: (4)
Dia 1 tu thap B sang thap C: Thap A: (5),Thap B: (3 2),Thap C: (4 1)

KẾT LUẬN
Tiểu luận đã trình bày các vấn đề:
- Khái niệm, nguyên lý chung và các đặc trưng của ngôn ngữ lập trình
hàm.
- Các đặc trưng cơ bản, các định nghĩa, quy tắc và hàm cơ bản của ngôn
ngữ lập trình Lisp.
- Giới thiệu bài toán “Tháp Hà Nội”, xây dựng chương trình trên ngôn
ngữ Lisp, thực hiện và cho kết quả.
Qua các trình bày cho thấy: việc tìm hiểu và nghiên cứu ngôn ngữ lập
trình hàm là một phạm vi rất rộng, sự gắn bó chặt chẽ giữa lập trình hàm và hàm
toán học đòi hỏi việc tiếp cận phải có một kiến thức tốt về toán.
Về mặt tư duy, lập trình hàm khác biệt khá nhiều so với lập trình mệnh
lệnh nên điều này ít nhiều cũng sẽ khó khăn với các lập trình viên đã quen thuộc
với ngôn ngữ lập trình mệnh lệnh khi bắt đầu tiếp cận.
Việc tìm hiểu lập trình hàm thông qua ngôn ngữ Lisp cũng cho thấy Lisp
là một ngôn ngữ rất mạnh về xử lý danh sách, xử lý đệ quy và thuần túy theo
hướng lập trình hàm. Chương trình xây dựng trên Lisp tương đối ngắn gọn tuy
nhiên cũng là khó khăn khi áp dụng xây dựng ứng dụng thương mại do thiếu các
cộng đồng phát triển mạnh mẽ như lập trình mệnh lệnh.
Tiểu luận chưa đi sâu được vào các vấn đề phức tạp hơn của lập trình
hàm, tuy nhiên đã tạo điều kiện tiếp cận sơ lược về hướng tư duy này, mở đường
cho các tiếp cận sâu hơn trong thực tế khi áp dụng các bài toán phù hợp.
Nhóm 11
19
Lập trình hàm – tìm hiểu và áp dụng ngôn ngữ Lisp giải bài toán “Tháp Hà Nội”
TÀI LIỆU THAM KHẢO
1. Bài giảng “Nguyên lý các ngôn ngữ lập trình” TS. Cao Tuấn Dũng
2. Lập trình hàm – TS. Phan Huy Khánh – NXB Khoa học kỹ thuật – 2007
3. Hppt://www.lispworks.com
4. Nguồn tham khảo Internet: http://wikipedia.org