BK
TP.HCM

ĐẠI HỌC BÁCH KHOA TPHCM
KHOA CÔNG NGHỆ THÔNG TIN

MÔN HỌC : NGÔN NGỮ LẬP TRÌNH

LÝ THUYẾT VÀ BÀI TẬP THỰC HÀNH
GOLDEN COMMON LISP

TPHCM, Tháng 10 – 2004


LÝ THUYẾT VÀ BÀI TẬP THỰC HÀNH
GOLDEN COMMON LISP


Mục lục
LÝ THUYẾT VÀ BÀI TẬP THỰC HÀNH GOLDEN COMMON LISP....................................................1
LÝ THUYẾT VÀ BÀI TẬP THỰC HÀNH GOLDEN COMMON LISP....................................................2
Mục lục................................................................................................................................................. 3
Lý thuyết LISP...................................................................................................................................... 1
I. Giới thiệu............................................................................................................................................ 1
II. Cài đặt và sử dụng gcLisp............................................................................................................... 1
III. Đặc điểm của gcLisp....................................................................................................................... 3
IV. Lập trình với gcLisp........................................................................................................................ 5
V. Nâng cao......................................................................................................................................... 17
VI. Tổng kết......................................................................................................................................... 20




Phiên bản đầu tiên của Common Lisp chuẩn ra đời năm 1984 – kết hợp nhiều ý tưởng
của ngôn ngữ lập trình như thông dịch và biên dịch hàm, dọn rác (garbage collection),
gọi hàm đệ quy, theo vết và dò lỗi (tracing and debugging) và trình soạn thảo theo cú
pháp.

II. Cài đặt và sử dụng gcLisp
II.1

Cài đặt

-

Chép tập tin GC LISP.rar vào và giải nén ra thư mục \GC LISP

-

Vào thư mục \GC LISP, chạy tập tin caidat.bat để cài gcLisp vào đĩa cứng

-

Vào thư mụcC:\Gclisp, chạy tập tin Gclisp.exe để bắt đầu.

II.2

Môi trường Gclisp

Chúng ta sẽ thấy cửa sổ gclisp như sau:
Trang 1



<F8>

to load a file into the editor

-

<F9>

to save a file

-

<F10>

to save a file as another name

II.4

Dòng lệnh

Đánh các dòng lệnh theo sau ký hiệu *

II.5

Lệnh tiền tố (Prefix command)

-

Mọi lệnh đều nằm giữa dấu ngoặc đơn ( )

Lisp là ngôn ngữ hướng chức năng (functional language hay applicative), dùng lối ký
hiệu tiền tố (prefix) và dấu ngoặc đơn:
f(x,y, z) được ký hiệu là (f x y z)
Cũng như vậy x+y ký hiệu là (+ x y)
Bt.

-

π

sin  3 x +  viết trong Lisp như thế nào ?
2

( sin ( + ( * 3 x ) ( / pi 2) ) )

Lisp là ngôn ngữ thông dịch (interpreted language)
Ngôn ngữ biên dịch

Ngôn ngữ thông dịch

câu lệnh (instructions)

Biểu thức

biên dịch
chương trình thực thi
thực thi
kết quả

đánh giá

 Atoms
atom::= số | chuỗi ký tự | symbols
 Symbol (~ identifier): từ tạo bởi các ký tự bất kỳ, ngoại trừ (
khoảng trắng

)

‘

`

“

; và

 Boolean: Lisp không có kiểu boolean. Trong Lisp, nil mang giá trị logic sai và tất cả
các biểu thức khác có giá trị đúng. Ký hiệu t dùng để chỉ trị logic đúng theo mặc
định.
Các kiểu dữ liệu được xếp theo cấp bậc như sau:
expression
list

atom
Trang
4
symbol

list

nil

(listp E)
(null E)
(atom E)

;;
;;
;;
;;
;;

trả
trả
trả
trả
trả

về
về
về
về
về

đúng
đúng
đúng
đúng
đúng

nếu
nếu

IV. Lập trình với gcLisp
IV.1 Các hàm xử lý trên danh sách

IV.1.1 FIRST và REST – CAR và CDR
 FIRST trả về phần tử đầu tiên của danh sách
 REST trả về danh sách theo sau phần tử đầu tiên
Cho đến gần đây, phần lớn lập trình viên LISP vẫn dùng CAR và CDR thay cho FIRST
và REST. Ngoài chức năng tương tự, CAR và CDR có thể kết hợp với nhau.thành dạng
phức hợp CxxR, CxxxR hay CxxxxR. Mỗi x tượng trưng cho A – CAR hay D – CDR.
Trang 5


Quy ước:
*(car nil)
NIL
*(cdr nil)
NIL

Bài tập:
1. Lấy phần tử thứ ba của danh sách
(car (cdr (cdr l)))
có thể viết:
(caddr l)
CAR và CDR có thể kết hợp với nhau đến mức độ 4
Ví dụ:
(caadr l) = (car (car (cdr l)))
(cadar l) = (car (cdr (car l)))
2. Làm thế nào trích ra chuỗi example trong danh sách:
L=((this) is (an (example)) more complex)
L=((this)

(a)

(CAR (CONS a l)) = a
(CDR (CONS a l)) = l
Trang 6


Bt. Cho biết giá trị của các biểu thức sau:
1. (cons ‘a (cons ‘b (cons ‘c nil)))
(cons ‘a (cons ‘b (cons ‘c nil)))
= (cons ‘a (cons ‘b ‘(c)))
= (cons ‘a ‘(b c))
= (a b c)

2. (list (car ‘(car ((1) (2)))) (cdr (cdr ‘((1) (2)))))
(list (car ‘(car ((1) (2))))
(cdr (cdr ‘((1) (2)))))
= (list ‘car
(cdr (cdr ‘((1) (2)))))
= (list ‘car
(cdr ((2))))
= (list ‘car nil)
= (list ‘car nil)
= (car nil)

 APPEND kết hợp các phần tử của mọi danh sách đã cho
(setq l1 ‘(a b)
l2 ‘(x y))
= (x y)
(append l1 l2)

((c d))

IV.1.4 LENGTH và REVERSE
 LENGTH trả về chiều dài của chuỗi
*(setq l ‘(a b c d e))
(a b c d e)
*(length l)
5

 REVERSE trả về chuỗi nghịch đảo
*(setq l ‘(a b c d e))
(a b c d e)
*(reverse l)
(e d c b a)

IV.1.5 ASSOC
 ASSOC gắn với một danh sách – association list hay còn gọi a-list
Key
Key
(setfl sarah ‘((height .54) (weight 4.4)))

Value

Value

height và weight là khóa trong danh sách được gán cho SARAH; .54 và 4.4 là các
giá trị biểu thị bằng met và kilograms.
 Có thể lấy các thành phần từ một danh sách dùng ASSOC, một khóa, và danh sách
liên kết:
(ASSOC <key> <asociation list>)

;Thương – số nguyên gần nhất
;Phần dư

*(+ round (/ 22 7)) (round (7/3)))
5
*(round (/ 5 2))
2

Một số hàm tính toán học:
*(MAX 2 4 3)
4
*(MIN 2 4 3)
2
*(expt 2 3)
8
*(expt 3 2)
9
*(expt 3.3 2.2)
13.827085
*(sqrt 9)
3
*(abs -5)
5

IV.2 Các câu lệnh điều kiện
 Câu lệnh IF
(if E1 E2 E3)
Nếu E1 đúng, trả về giá trị E2 nếu không trả về giá trị E3
Ví dụ:
*(if (numberp 1) ‘(a number) ‘(not a number))

error > A is not a number
*(or (symbolp x) (list x) )

T
IV.3 Định nghĩa hàm
(defun <tên> <danh sách đối số> <thân hàm>)
<tên> Symbol
<danh sách đối số> đại diện cho các biến
<thân hàm> biểu thức
Ví dụ:
*(defun square (x) (* x x))
SQUARE
*(square 3)
9
*(defun abs(x)
(if (>= x 0) x
(* -1 x) ) )
ABS
Trang 10


IV.4 Chương trình đệ quy trong Lisp
Vòng lặp trong Lisp được thực hiện chủ yếu nhờ vào đệ quy
Ví dụ: Tính giai thừa
n!=1*2*...*n
0!=1
Trong Pascal, hàm n! được viết bằng vòng lặp:
function fac(integer:n):integer;
var i:integer
begin

(defun pair (n)
(or (= n 0)
(impair (1- n)) ) )
(defun impair (n)
(and ( n 0)
(pair (1- n)) ) )

IV.5 Đánh giá
‘Exp là cách viết tắt của (quote Exp)
*‘a
A
*‘‘a
Trang 11


(QUOTE A)

QUOTE không đánh giá đối số
Ngược lại với quote là hàm eval đánh giá giá trị của đối số
*(setq l ‘(a b c))
(A B C)
*(eval (list ‘car ‘l))
A
*(eval (list ‘* (1+ 3) 2))
6

Giá trị của (eval ‘Exp) là Exp
IV.6 Các dạng đặc biệt
(progn E1 ... En)
đánh giá tuần tự các biểu thức E1, ..., En từ trái sang phải và kết quả trả về là giá trị

(if Test1 (progn E1 …)
(if Test2 (progn E2 …)
(if Test3 (progn E3 …)
…
(if Testn (progn En …)) … )
))
Trong một mệnh đề kiểu (Test1), nếu Test1 đúng, kết quả của cond là giá trị của (Test1)
Ví dụ: Viết hàm trả về kiểu của đối số
*(type-of 1)
FIXNUM
*(type-of a)
SYMBOL

Giải:
(defun type-of (x)
(cond ((null x) ‘null)
((symbolp x) ‘symbolp)
((numberp x) ‘numberp)
((stringp x) ‘stringp)
((consp x) ‘consp)
(t ‘unknown-type) )
)

IV.8 Biến cục bộ
(let ((var1 exp1) … (varm expm))
expm+1 … expn)
Chúng ta gán cho mỗi biến giá trị của biểu thức tương ứng, sau đó ta đánh giá
(progn expm+1 … expn)
Ví dụ:
*(let ((x (fac 4))) (* x x))

5

 Dạng let* thực hiện một liên kết tuần tự các đối số
*(defun bar(x)
(let ((x 1) (y (1- x)))
y) )
BAR
*(defun bar1(x)
(let* ((x 1) (y (1- x)))
y) )
BAR
*(bar 3)
2
*(bar1 3)
0

 let* tương ứng với let lồng nhau
* (defun bar(x)
(let ((x 1))
(let ((y (1+ x)))
y) ) )
BAR

IV.9 Symbols
 So sánh hai symbols
Có thể so sánh hai symbols nhờ hàm eq
*(eq ‘a ‘b)
NIL
*(eq ‘a ‘a)
T

var + indef
 FTYPE: kiểu hàm
 Ví dụ:
* (setq foo 3)
3

3

CVAL

*(defun foo(x) …)

…

FVAL

EXPR

FTYPE

“foo”

PNAME

foo

FOO

IV.10 Lập trình hướng dữ liệu
 Ví dụ: Chúng ta muốn dùng cùng một hàm thực hiện việc cộng hai số và nối hai

= 7
* (read)
* (+ 3 4)
= (+ 3 4)

IV.13 Lưu ý
 Có thể viết vòng lặp toplevel:
(defun toplevel ()
(print (eval (read)))
(toplevel) )

IV.14 Hiệu chỉnh
 Đây là ngôn ngữ tương tác (interactive), do đó chúng ta có thể kiểm tra mỗi hàm ở
toplevel mà không bắt buộc phải định nghĩa các chương trình tests
 Một kỹ thuật theo vết (trace) cho phép theo dõi quá trình thực hiện một hàm
*(defun fac(n)
(if (= n 0) 1 (* n (fac (1- n))) ) )
FAC
*(trace fac)
;Autoload: TRACE from “TRACE” in “C:\\GCLISP\\LISPLIB”
T
* (fac 2)
ENTERING: FAC, ARGUMENT LIST: (2)
ENTERING: FAC, ARGUMENT LIST: (1)
ENTERING: FAC, ARGUMENT LIST: (0)
EXITING: FAC, VALUE: 1
EXITING: FAC, VALUE: 1
EXITING: FAC, VALUE: 2
2



Tương tự như vậy, danh sách (1 2 3) được thể hiện bởi:
nil

1

2

3

2

3

Hay đơn giản hơn:
1

V.1.2

nil

Pointed pair

 Thông số thứ hai của cons có thể không phảI là một danh sách. Trong trường hợp
đó, chúng ta gọi là cặp con trỏ (pointed pair)
*(cons ‘a ‘b)
(A . B)
*(car ‘(a . b))
A
*(cdr ‘(a . b))

(defun listp(p)
(or (null x)
(consp x) ) )

V.2

Apply

 (apply F L) áp dụng hàm F trên các phần tử của danh sách L
*(apply ‘append ‘((a b) (c d)))
(a b c d)
*(apply ‘+ ‘(1 2))
3
*(setq a ‘*)
*
*(apply a ‘(3 4))
12

 (apply F L) ≡ (eval (cons F L))
Bt. Đếm số symbols, numbers hay strings trong một list
(defun count(test l)
(if (null l) 0
(if (apply test (list (car l)))
(1+ (count test (cdr l)))
(count test (cdr l)) ) )
)

V.3

Funcall và ứng dụng

(and (integerp x) (< x 10)) )
INF10
*(count ‘inf10 ‘(4 12 a 11 3))
2

Nhận xét : Chúng ta định nghĩa hàm inf10 chỉ để sử dụng một lần duy nhất
Có thể sử dụng một hàm không tên. Hàm như thế trong Lisp được gọi là lambdaexpression va được viết:
(lambda header content)
*(count (lambda (x)
(and (integer x)
(< x 10) ) )
‘(4 12 a 11 3)
2

Có thể trực tiếp định nghĩa lambda-expression khi xử lý:
*(+ 10 ((lambda (x) (* x x)) 4) )
26

V.5

Hàm vô danh và biến cục bộ

Các biến cục bộ được bắt đầu với let là các tham số của một hàm vô danh (anonymous)
(let ((var1 val1) … (varN valN)) corps)
≡
( ( lambda (var1 … varN) corps) val1 … valN)
*(let ((x 1) (y 2)) (+ x y))

3
* ( ( lambda (x y) (+ x y) ) 1 2 )