BK

Thực hành Ngôn ngữ lập trình

TP.HCM

Nguyễn Thị Trúc Viên
Khoa Công Nghệ Thông Tin
Đại Học Bách Khoa TPHCM

BK

Nội dung

TP.HCM

Các loại Ngôn ngữ lập trình
Lập trình hàm với Lisp: GcLisp
Lập trình logic với Prolog: B_Prolog
Lập trình hướng đối tượng với SmallTalk:
Vwin

Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 2/67

1

BK

Lịch sử phát triển

TP.HCM

Nghĩ ra năm 1958 bởi John McCarthy (MIT)
Hai thế hệ đầu tiên ra đời ngay sau đó:
MacLisp và InterLisp
Franz-Lisp
Zeta-Lisp
Đầu thập niên 80, có 12 hệ Lisp khác nhau
Common Lisp chuẩn ra đời năm 1984
Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 3/67

Lisp – Các ứng dụng

TP.HCM

Expert problem solvers
Common reasoning
Learning
Natural-language interfaces
Education and intelligent support systems

Speech and vision
Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 4/67

2


BK

Ngôn ngữ hướng chức năng

TP.HCM

Từ khi được John McCarthy (MIT) nghĩ ra năm
1958, LISP được tinh chế dần đến version 1.5 và
được sử sụng lâu dài về sau
Ngôn ngữ hướng chức năng (functional
language), dùng ký hiệu tiền tố (prefix):
f(x,y, z)
x+y

Bt:
Nguyễn Thị Trúc Viên

BK

ký hiệu là (f x y z)

ký hiệu là (+ x y)

π

sin  3 x +  ký hiệu ra sao ?
2

Ngôn ngữ lập trình Lisp

Slide 5/67

Giải đáp bài tập

TP.HCM

(sin (+ (* 3 x) (/ pi 2)))

Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 6/67

3


BK

Ngôn ngữ thông dịch


TP.HCM

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

đánh giá
trả lời

chương trình thực thi

Kết quả

thực thi
kết quả

Nguyễn Thị Trúc Viên

BK

vòng lặp top-level

Ngôn ngữ lập trình Lisp

Slide 7/67

List Processing (1)


TP.HCM

Lisp là ngôn ngữ đặc trưng cho việc xử lý
danh sách
Biểu diễn chương trình bằng các danh
sách và thao tác trên đó như dữ liệu
(+ (* 3 4) (- 5 2))
chương trình: hàm + áp dụng vào hai đối số
dữ liệu: danh sách gồm ba thành phần
Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 8/67

4


BK

List Processing (2)

TP.HCM

Ví dụ:
* (+ 3 4)
7
* (+ (* 3 4) (- 5 2))
15

*4
4
Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 9/67

List Processing (3)

TP.HCM

Danh sách là sự thực hiện một hàm
* (+ 3 4) ; danh sách được đánh giá
7

Để không đánh giá một danh sách, dùng
dấu ‘ đặt trước danh sách
* ‘(+ 3 4)
(+ 3 4)

Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 10/67

5



BK

Symbol (1)

TP.HCM

Symbol (~ identifier): từ tạo bởi các ký tự
bất kỳ, ngoại trừ ( ) ‘ ` “ ; và
khoảng trắng
Ví dụ: + * example là các symbol

Ba trường hợp thường sử dụng:
Tên hàm
Dữ liệu: chuỗi ký tự hay số
Tên biến
Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 11/67

Symbol (2)

TP.HCM

Với vai trò là đối số trong hàm, symbol được

xem như tên của một biến
* example
Unbound variable: EXAMPLE
* (setf example 3)
3
* (+ example 4)
7

Để không đánh giá một symbol, dùng dấu ‘ đặt
trước danh sách
* ’example
example
Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 12/67

6


BK

Symbol (3)

TP.HCM

Bài tập: Symbol hay số ?
AARDVARD
87

1-2-3-GO
3.12
7-11
22/7
-12
Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 13/67

Symbol (4)

TP.HCM

Giải bài tập
AARDVARD
87
1-2-3-GO
3.12
7-11
22/7
12
Nguyễn Thị Trúc Viên

symbol
number
symbol

number
symbol
symbol
number
Ngôn ngữ lập trình Lisp

Slide 14/67

7


BK

Boolean

TP.HCM

Lisp không có kiểu dữ liệu Boolean
nil biểu diễn giá trị logic sai, tất cả các biểu thức
khác biểu diễn trị logic đúng
Mặc định dùng T → trị logic đúng

nil và T là các symbol hằng
* nil
NIL
*T
T

nil ≈ danh sách rỗng ()
Nguyễn Thị Trúc Viên


BK

Ngôn ngữ lập trình Lisp

Slide 15/67

Kiểu dữ liệu

TP.HCM

Symbol (~ identifier): từ tạo bởi các ký tự bất
kỳ, ngoại trừ ( ) ‘ ` “ ; và khoảng trắng
Ví dụ: + * example là các symbol
Biểu thức

expression::= atom | list

Danh sách

list::=(expression1...expressionn)

Atoms

atom::= số|chuỗi ký tự|symbols

Boolean

T và nil


Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 16/67

8


BK

Các loại biểu thức trong Lisp

TP.HCM

Các loại biểu thức (expression):
Ký hiệu (symbol). Ví dụ: a-symbol
Danh sách (list). Ví dụ: (f x y)
Literal:
Số: 0.42e2
Chuỗi: “a string”
Ký tự: ‘c
Mảng: ‘(1 2 3)
Ngôn ngữ lập trình Lisp

Nguyễn Thị Trúc Viên

BK

Slide 17/67


Phân cấp dữ liệu

TP.HCM

expression

list

atom

symbol

list

Nguyễn Thị Trúc Viên

nil

...

number

interger

Ngôn ngữ lập trình Lisp

...

real


...

Slide 18/67

9


BK

Ngôn ngữ động (dynamic type)

TP.HCM

Biến không có kiểu dữ liệu định sẵn
(không khai báo)
Cùng một biến có thể có nhiều kiểu dữ
liệu khác nhau

Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 19/67

Ngôn ngữ lập trình Lisp

Slide 20/67


Ví dụ

TP.HCM

* (setf a ‘(1 2 3))
(1 2 3)
*a
(1 2 3)
* (setf a 2)
2
*a
2
Nguyễn Thị Trúc Viên

10


BK

Các vị từ kiểu

TP.HCM

(numberp E) trả về đúng nếu E là số
(stringp E)

chuỗi

(listp E)


danh sách

(null E)

nil

(atom E)

atom

Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 21/67

Các vị từ kiểu

TP.HCM

* (numberp 4)
T
* (numberp 3.45)
T
* (symbolp ‘ListProcessor)
T
* (listp ‘(a b c))

T
Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 22/67

11


BK

Các vị từ trên số

TP.HCM

ZEROP
PLUSP
MINUSP
ODDP
EVENP
<
>
=
Nguyễn Thị Trúc Viên

BK

kiểm tra zero
kiểm tra số dương

kiểm tra số âm
kiểm tra số lẻ
kiểm tra số chẵn
so sánh first < second
so sánh first > second
so sánh first = second
Ngôn ngữ lập trình Lisp

Slide 23/67

Các hàm cơ bản

TP.HCM

Gán: setf và setq
Các phép tính số học
+, –, *, /, \\
1+ và 1max, min và abs

Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 24/67

12


BK


Ví dụ

TP.HCM

* (setf x 27)
1.111
* (/ x 9)
3
* (/ 22 7)
3.14286
* (max 3 4 5)
5
* (abs -2)
2
Ngôn ngữ lập trình Lisp

Nguyễn Thị Trúc Viên

BK

Slide 25/67

Các hàm so sánh (1)

TP.HCM

Các phép so sánh
=
eq
eql

equal

Nguyễn Thị Trúc Viên

hai đối số cùng là một số
hai đối số cùng là một symbol
hai đối số cùng là một symbol
hay cùng một số
hai đối số có cùng biểu thức
biểu diễn

Ngôn ngữ lập trình Lisp

Slide 26/67

13


BK

Các hàm so sánh (2)

TP.HCM

eq kiểm tra cùng địa chỉ bộ nhớ (các symbol
giống nhau thỏa điều này).

eql kiểm tra thỏa eq hay không. Nếu không,
kiểm tra là hai số cùng kiểu và cùng giá trị.


equal kiểm tra thỏa eql hay không. Nếu
không, xem đối số là hai danh sách và xem
từng cặp phần tử có thỏa equal.

= kiểm tra hai đối số cùng là một số (có thể
không cùng kiểu)
Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 27/67

Ví dụ (1)

TP.HCM

* (setf k ‘(a b) l ‘(a b))
(A B)
* (equal k l)
T
* (eq k l)
NIL
* (eql k l)
NIL
Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp


Slide 28/67

14


BK

Ví dụ (2)

TP.HCM

* (setf x ‘a y ‘a)
A
* (equal x y)
T
* (eq x y)
T
* (eql x y)
T
Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 29/67

Ngôn ngữ lập trình Lisp

Slide 30/67


Ví dụ (3)

TP.HCM

* (eq 3 3)
T
* (eql 3 3.0)
NIL
* (= 3 3)
T
* (= 3 3.0)
T
Nguyễn Thị Trúc Viên

15


BK

Các hàm xử lý trên danh sách (1)

TP.HCM

FIRST và REST – CAR và CDR
CONS, APPEND, LIST
NTHCDR, BUTLAST và LAST
LENGTH và REVERSE

Nguyễn Thị Trúc Viên


BK

Ngôn ngữ lập trình Lisp

Slide 31/67

Các hàm xử lý trên danh sách (2)

TP.HCM

* (setf l ‘(a b c d e) k ‘(f g h))
(F G H)
* (first l)
A
* (rest l)
(B C D E)
* (cons ‘f l)
(F A B C D E)
* (list ‘a ‘b ‘c)
(A B C)
Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 32/67

16



BK

Các hàm xử lý trên danh sách (3)

TP.HCM

* (nthcdr 2 l)
(C D E)
*l
(A B C D E)
* (butlast l 2)
(A B C)
* (last l)
(E)
* (reverse l)
(E D C B A)
Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 33/67

Toán tử ASSOC (1)

TP.HCM

Gắn với một danh sách – association list
hay a-list

Key

Key

(setf sarah ‘((height .54) (weight 4.4)))

Value
Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Value
Slide 34/67

17


BK

ASSOC (2)

TP.HCM

Lấy các thành phần từ một danh sách:
(ASSOC <key> <asociation list>)
Ví dụ:
* (setf sarah ‘((height .54) (weight 4.4)))
((HEIGHT 0.54) (WEIGHT 4.4))
* (assoc ‘weight sarah)
(WEIGHT 4.4)

Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 35/67

ASSOC (3)

TP.HCM

Thêm một thành phần mới vào danh sách:
(ACONS <key><value><asociation list>)

Ví dụ:
* (setf Andrew ‘((height .74) (weight 6.4)))
((HEIGHT 0.74) (WEIGHT 6.4))
* (acons ‘nick ‘Bobby Andrew)
((NICK . BOBBY) (HEIGHT 0.74) (WEIGHT 6.4))
Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 36/67

18


BK


Định nghĩa hàm

TP.HCM

* (defun square (x) (* x x))
SQUARE
* (square 3)
9
* (defun abs(x)
(if (>= x 0) x
(* -1 x) ) )
ABS
Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 37/67

Đệ quy trong Lisp

TP.HCM

Ví dụ: Tính giai thừa:
n!=1*2*...*n
0!=1
(defun fac(n)
(if (= n 0)

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

Bài tập: Viết hàm in ra phần tử thứ n
trong danh sách.
Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 38/67

19


BK

Đánh giá biểu thức (Evaluation)

TP.HCM

‘Exp là cách viết tắt của (quote Exp)
* (setf c ‘a)
a

eval >< quote
* (setf l ‘(a b c))
(a b c)
* (eval (list ‘car ‘l))
a
* (eval (list ‘+ (1+ 3) 2))

6
Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 39/67

Các câu lệnh điều kiện (1)

TP.HCM

Câu lệnh IF
(if E1 E2): Nếu E1 đúng, trả về giá trị E2
(if E1 E2 E3): .. nếu không trả về giá trị E3
Ví dụ:
* (if (numberp 1) ‘(a number) ‘(not a number))
(A NUMBER)
* (if (numberp ‘a) ‘(a number) ‘(not a number))
(NOT A NUMBER)
Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 40/67

20



BK

Các câu lệnh điều kiện (2.1)

TP.HCM

Câu lệnh COND
(cond (Test1 E1 …)
(Test2 E2 …)
(Test3 E3 …)
…
(Testn En …) )
(if Test1 (progn E1 …)
(if Test2 (progn E2 …)
(if Test3 (progn E3 …)
…
(if Testn (progn En …)) … )
))
Ngôn ngữ lập trình Lisp

Nguyễn Thị Trúc Viên

BK

Slide 41/67

Các câu lệnh điều kiện (2.2)

TP.HCM


* (setf x ‘(a b c))
(A B C)
* (cond ((numberp x) ‘(This is a number))
((symbolp x) ‘(This is a symbol))
((listp x) ‘(This is a list))
)
(THIS IS A LIST)

Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 42/67

21


BK

Các câu lệnh điều kiện (3)

TP.HCM

Câu lệnh WHEN
(when Test E1 ... En): Nếu Test đúng, thực
hiện E1 ... En và trả về kết quả En
Ví dụ:
* (setf n 3)
* (when (numberp n) (setf n 5) (setf l ‘(a b c)))
(A B C)


Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 43/67

Các trường hợp điều kiện (1.1)

TP.HCM

Câu lệnh AND
(and E1 ... En) sai nếu ít nhất một Ei sai
AND đánh giá từ trái → phải và dừng lại
khi gặp đối số sai
Nếu mọi đối số đều đúng, AND trả về giá
trị của đối số cuối cùng

Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 44/67

22


BK


Các trường hợp điều kiện (1.2)

TP.HCM

* (setf n 3)
3
* (and (numberp n) (> n 3) )
NIL
* (and (numberp n) (oddp n))
T
* (and (numberp n) (oddp n) (1+ n))
4
Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 45/67

Các trường hợp điều kiện (2.1)

TP.HCM

Câu lệnh OR
(or E1 ... En) đúng nếu ít nhất một Ei đúng
OR đánh giá từ trái → phải và dừng lại khi
gặp đối số đúng


Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 46/67

23


BK

Các trường hợp điều kiện (2.2)

TP.HCM

* (setf x ‘a)
A
*x
A
* (or (numberp x) (> x 1))
wrong type argument
* (or (symbolp x) (list x))
T
Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 47/67


Các trường hợp điều kiện (3)

TP.HCM

Toán tử NOT
AND, OR trả về giá trị cuối cùng tính được
NOT đơn giản đổi nonNIL→NIL và NIL→T
* (not nil)
T
* (not ‘dog)
NIL
* (not (symbolp 4.3))
T
Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp

Slide 48/67

24


BK

Các dạng đặc biệt (1)

TP.HCM

Toán tử PROG1 và PROGN

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

Nguyễn Thị Trúc Viên

BK

Ngôn ngữ lập trình Lisp

Slide 49/67

Các dạng đặc biệt (2)

TP.HCM

* (progn (setf x ‘(a b c)) (append x x) )
(A B C A B C)
*x
(A B C)
* (prog1 (setf x ‘(a b c)) (append x x) )
(A B C)

Nguyễn Thị Trúc Viên

Ngôn ngữ lập trình Lisp


Slide 50/67

25