ĐẠi học bách khoa tphcm khoa công nghệ thông tin

	Symbol
	đại diện cho các biến
	biểu thức

*(defun square (x) (* x x))

SQUARE
*(square 3)

9
*(defun abs(x)

(if (>= x 0) x

(* -1 x) ) )

ABS

IV.4Chương trình đệ quy trong Lisp

Ví dụ: Tính giai thừa

Trong Pascal, hàm n! được viết bằng vòng lặp:

function fac(integer:n):integer;

var i:integer

begin

fac:=1;

fac:=fac*i;

end

Định nghĩa đệ quy của giai thừa:

Trong Lisp:

(defun fac(n)

(if (= n 0)

1

(* n fac (1- n)) ) )

1. 
   Viết hàm in ra phần tử thứ n trong danh sách
   

(if (= n 1)

(car l)

(nth (1- n) (cdr l)) ) )

2. 
   Ví dụ đệ quy chéo hay lời gọi đệ quy:
   

(or (= n 0)

(impair (1- n)) ) )
(defun impair (n)

(and (<> n 0)

(pair (1- n)) ) )

IV.5Đánh giá

*‘a

(QUOTE A)

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.6Các dạng đặc biệt

đá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ị của biểu thức En

*(progn (setq x ‘(a b c))

(append x x) )

(A B C A B C)
*(progn)

NIL

(defun name(p1 … pm) E1 … En)

(if Test E1 (progn E2 … En))

điều này không đúng trong Clisp

(prog1 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ị của biểu thức E1

*(prog1 (setq x ‘(a b c))

(append x x) )

(A B C)

IV.7Các trường hợp điều kiện

(Test2 E2 …)

(Test3 E3 …)

…

(Testn En …) )

(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

(defun type-of (x)

(cond ((null x) ‘null)

((symbolp x) ‘symbolp)

((numberp x) ‘numberp)

((stringp x) ‘stringp)

((consp x) ‘consp)

(t ‘unknown-type) )

)

IV.8Biến cục bộ

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))

• 
  Các biến cục bộ che phủ các biến toàn cục
  

5
*(let ((x 1)) x)

= 1
*x

5
*(let ((x 1)) (setq x 2) x)

2
*x

5

• 
  Các biến cục bộ che phủ các đối số của một hàm
  

(let ((x 1)) x ) )

FOO
*(foo 4)

1

• 
  Các liên kết được thực hiện song song
  

(let ((x 1) (y (1+ x)))

y) )

BAR
*(bar 4)

• 
  Dạng let* thực hiện một liên kết tuần tự các đối số
  

(let ((x 1) (y (1- x)))

y) )

BAR
*(defun bar1(x)

y) )

2
*(bar1 3)

0

• 
  let* tương ứng với let lồng nhau
  

(let ((x 1))

(let ((y (1+ x)))

y) ) )

IV.9Symbols

• 
  So sánh hai symbols
  

*(eq ‘a ‘b)

NIL
*(eq ‘a ‘a)

T

(neq Exp) = (null (eq Exp))

• 
  Các trường của một symbol
  

• 
  FVAL: hàm gắn liền với symbol, trường này không tồn tại trong LISP đơn trị
  

  LISP đa trị (bi-valued)	LISP đơn trị (mono-valued)
  *(setq + 4) 4 *(+ + 3) 7 *(setq + *) var + indef	*(setq + 4) 4 *(+ + 3) func + undef *(* 4 3) = 12

• 
  FTYPE: kiểu hàm
  
• 
  Ví dụ:
  

3
*(defun foo(x) …)

FOO

foo

IV.10Lậ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 chuỗi
  
• 
  Giải pháp 1
  

(cond ((numberp x) (+ x y))

((listp x) (append x y) ) )

)

• 
  Giải pháp 2
  

(putprop ‘add ‘append ‘listp)

(defun add(x y)

(funcall (getprop ‘add (type-of x))

x y) )

funcall cho phép gọi các hàm tính toán

IV.11Lời gọi hàm tính toán

• 
  funcall: áp dụng giá trị của thông số thứ nhất (một hàm hay tên của một hàm) vào các thông số tiếp theo
  

(funcall ‘F E1…En) = (F E1…En)

IV.12Nhập/xuất cơ bản

• 
  Có thể dễ dàng viết các định nghĩa hàm trong một file (có thể edit) sau đó load file đó lên
  

load name

tên hay đường dẫn đến file chứa định nghĩa hàm

• 
  (read) đọc một biểu thức và trả về kết quả
  

* (+ (read) 3)

* 4

= 7
* (read)

* (+ 3 4)

= (+ 3 4)

IV.13Lưu ý

• 
  Có thể viết vòng lặp toplevel:
  

(defun toplevel ()

(print (eval (read)))

(toplevel) )

IV.14Hiệ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

• 
  untrace cho phép trở về sự thực hiện bình thường của hàm
  

*(untrace fac)

(FAC)

*(fac 2)

2

• 
  trace cập nhật định nghĩa hàm theo vết bằng cách in ra kết quả từng giai đoạn
  
• 
  có thể theo dõi sự thực hiện nhiều hàm cùng lúc
  

V.Nâng cao

V.1Doublets

V.1.1Doublets

• 
  Một danh sách không rỗng được biểu diễn bằng một đối tượng có hai trường gọi là doublet
  

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

Hay đơn giản hơn:

V.1.2Pointed 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))

B

V.1.3Ký hiệu pointed pair

• 
  Ký hiệu danh sách là viết tắt của ký hiệu pointed pair
  

*‘(1 . nil)

(1)
*‘(1 . (2 . (3 . nil)))

(1 2 3)

Nói chung, chúng ta có:

(exp.(exp1 … expN))=(exp exp1 … expN)

• 
  Chúng ta có thể kết hợp hai lối ký hiệu:
  

*‘(1 . (2 3))

(1 2 3)
*‘(1 . (2 . 3))

(1 2 . 3)

V.1.4Doublets

• 
  Mỗi biểu thức trong Lisp là một doublet hay một atom
  

expression ::= (expression.expression) | atom

• 
  Consp là một vị từ để kiểm tra thông số của nó có là một doublet hay không
  

(defun listp(p)

(or (null x)

(consp x) ) )

V.2Apply

• 
  (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.3Funcall và ứng dụng

• 
  (apply f (list e1 … en))  (funcall f e1 … e2)
  

*(setq a ‘+)

+
*(funcall a (+ 3 4) 5)

12

Lưu ý: Trong Lisp đơn trị (như Scheme), chúng ta có thể viết trực tiếp:

* (a (+ 3 4) 5)

= 12

vì ở đó có sự đánh giá hàm

Bt. Đếm số symbols, numbers hay strings trong một list

(defun count(test l)

(if (null l) 0

(if (funcall test (car l))

(1+ (count test (cdr l)))

(count test (cdr l)) ) )

)

Bt. Đếm số symbols, numbers hay strings trong một list

V.4Lambda expression

Dùng hàm count để đếm số số nguyên nhỏ hơn 10 trong danh sách

*(defun inf10(x)

(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à lambda-expression 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.5Hà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 )

3

VI.Tổng kết