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

1BK TP.HCM Thực hành Ngôn ngữ lập trình Nguyễn Thị Trúc Viên Khoa Công Nghệ Thông Tin Đại Học Bách Khoa TPHCM BK TP.HCM Slide 2/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Nội dung
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 2BK TP.HCM Slide 3/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Lịch sử phát triển
Nghĩ ra năm 1958 bởi John McCarthy (MIT)
Hai thế hệ đầu tiên ra đời ngay sau đó: MacLisp và InterLisp
Đầu thập niên 80, có 12 hệ Lisp khác nhau
Common Lisp chuẩn ra đời năm 1984 Franz-Lisp Zeta-Lisp BK TP.HCM Slide 4/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Lisp – Các ứng dụng
Expert problem solvers
Common reasoning
Learning
Natural-language interfaces
Education and intelligent support systems
Speech and vision 3BK TP.HCM Slide 5/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Ngôn ngữ hướng chức năng
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) ký hiệu là (f x y z)
x+y ký hiệu là (+ x y)
Bt: ký hiệu ra sao ?      + 2 3sin pix BK TP.HCM Slide 6/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Giải đáp bài tập
(sin (+ (* 3 x) (/ pi 2))) 4BK TP.HCM Slide 7/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Ngôn ngữ thông dịch Ngôn ngữ thông dịch Biểu thức đánh giá trả lời Kết quả vòng lặp top-level Ngôn ngữ biên dịch câu lệnh (instructions) biên dịch chương trình thực thi thực thi kết quả BK TP.HCM Slide 8/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp List Processing (1)
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 5BK TP.HCM Slide 9/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp List Processing (2)
Ví dụ: * (+ 3 4) 7 * (+ (* 3 4) (- 5 2)) 15 * 4 4 BK TP.HCM Slide 10/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp List Processing (3)
Danh sách là sự thực hiện một hàm
Để không đánh giá một danh sách, dùng dấu ‘ đặt trước danh sách * (+ 3 4) ; danh sách được đánh giá 7 * ‘(+ 3 4) (+ 3 4) 6BK TP.HCM Slide 11/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Symbol (1)
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 BK TP.HCM Slide 12/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Symbol (2)
Với vai trò là đối số trong hàm, symbol được xem như tên của một biến
Để không đánh giá một symbol, dùng dấu ‘ đặt trước danh sách * example Unbound variable: EXAMPLE * (setf example 3) 3 * (+ example 4) 7 * ’example example 7BK TP.HCM Slide 13/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Symbol (3)
Bài tập: Symbol hay số ?
AARDVARD
87
1-2-3-GO
3.12
7-11
22/7
-12 BK TP.HCM Slide 14/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Symbol (4)
Giải bài tập
AARDVARD symbol
87 number
1-2-3-GO symbol
3.12 number
7-11 symbol
22/7 symbol
12 number 8BK TP.HCM Slide 15/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Boolean
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 ≈ danh sách rỗng () * nil NIL * T T BK TP.HCM Slide 16/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Kiểu dữ liệu
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 9BK TP.HCM Slide 17/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các loại biểu thức trong Lisp
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) BK TP.HCM Slide 18/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Phân cấp dữ liệu expression list atom symbol realnillist ...number ... ...interger 10 BK TP.HCM Slide 19/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Ngôn ngữ động (dynamic type)
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 BK TP.HCM Slide 20/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Ví dụ * (setf a ‘(1 2 3)) (1 2 3) * a (1 2 3) * (setf a 2) 2 * a 2 11 BK TP.HCM Slide 21/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các vị từ kiểu (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 BK TP.HCM Slide 22/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các vị từ kiểu * (numberp 4) T * (numberp 3.45) T * (symbolp ‘ListProcessor) T * (listp ‘(a b c)) T 12 BK TP.HCM Slide 23/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các vị từ trên số ZEROP kiểm tra zero PLUSP kiểm tra số dương MINUSP kiểm tra số âm ODDP kiểm tra số lẻ EVENP kiểm tra số chẵn < so sánh first < second > so sánh first > second = so sánh first = second BK TP.HCM Slide 24/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các hàm cơ bản
Gán: setf và setq
Các phép tính số học
+, –, *, /, \\
1+ và 1-
max, min và abs 13 BK TP.HCM Slide 25/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Ví dụ * (setf x 27) 1.111 * (/ x 9) 3 * (/ 22 7) 3.14286 * (max 3 4 5) 5 * (abs -2) 2 BK TP.HCM Slide 26/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các hàm so sánh (1)
Các phép so sánh
= hai đối số cùng là một số
eq hai đối số cùng là một symbol
eql hai đối số cùng là một symbol hay cùng một số
equal hai đối số có cùng biểu thức biểu diễn 14 BK TP.HCM Slide 27/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các hàm so sánh (2)
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) BK TP.HCM Slide 28/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Ví dụ (1) * (setf k ‘(a b) l ‘(a b)) (A B) * (equal k l) T * (eq k l) NIL * (eql k l) NIL 15 BK TP.HCM Slide 29/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Ví dụ (2) * (setf x ‘a y ‘a) A * (equal x y) T * (eq x y) T * (eql x y) T BK TP.HCM Slide 30/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Ví dụ (3) * (eq 3 3) T * (eql 3 3.0) NIL * (= 3 3) T * (= 3 3.0) T 16 BK TP.HCM Slide 31/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các hàm xử lý trên danh sách (1)
FIRST và REST – CAR và CDR
CONS, APPEND, LIST
NTHCDR, BUTLAST và LAST
LENGTH và REVERSE BK TP.HCM Slide 32/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các hàm xử lý trên danh sách (2) * (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) 17 BK TP.HCM Slide 33/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các hàm xử lý trên danh sách (3) * (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) BK TP.HCM Slide 34/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Toán tử ASSOC (1)
Gắn với một danh sách – association list hay a-list (setf sarah ‘((height .54) (weight 4.4))) Key Key Value Value 18 BK TP.HCM Slide 35/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp ASSOC (2)
Lấy các thành phần từ một danh sách:
Ví dụ: (ASSOC ) * (setf sarah ‘((height .54) (weight 4.4))) ((HEIGHT 0.54) (WEIGHT 4.4)) * (assoc ‘weight sarah) (WEIGHT 4.4) BK TP.HCM Slide 36/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp ASSOC (3)
Thêm một thành phần mới vào danh sách:
Ví dụ: (ACONS ) * (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)) 19 BK TP.HCM Slide 37/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Định nghĩa hàm * (defun square (x) (* x x)) SQUARE * (square 3) 9 * (defun abs(x) (if (>= x 0) x (* -1 x) ) ) ABS BK TP.HCM Slide 38/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp
Ví dụ: Tính giai thừa:
Bài tập: Viết hàm in ra phần tử thứ n trong danh sách. Đệ quy trong Lisp n!=1*2*...*n 0!=1 (defun fac(n) (if (= n 0) 1 (* n fac (1- n)) ) ) 20 BK TP.HCM Slide 39/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp
‘Exp là cách viết tắt của (quote Exp)
eval >< quote Đánh giá biểu thức (Evaluation) * (setf l ‘(a b c)) (a b c) * (eval (list ‘car ‘l)) a * (eval (list ‘+ (1+ 3) 2)) 6 * (setf c ‘a) a BK TP.HCM Slide 40/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các câu lệnh điều kiện (1)
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) 21 BK TP.HCM Slide 41/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các câu lệnh điều kiện (2.1)
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 …)) … ) ) ) BK TP.HCM Slide 42/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các câu lệnh điều kiện (2.2) * (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) 22 BK TP.HCM Slide 43/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các câu lệnh điều kiện (3)
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) BK TP.HCM Slide 44/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các trường hợp điều kiện (1.1)
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 23 BK TP.HCM Slide 45/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các trường hợp điều kiện (1.2) * (setf n 3) 3 * (and (numberp n) (> n 3) ) NIL * (and (numberp n) (oddp n)) T * (and (numberp n) (oddp n) (1+ n)) 4 BK TP.HCM Slide 46/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các trường hợp điều kiện (2.1)
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 24 BK TP.HCM Slide 47/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các trường hợp điều kiện (2.2) * (setf x ‘a) A * x A * (or (numberp x) (> x 1)) wrong type argument * (or (symbolp x) (list x)) T BK TP.HCM Slide 48/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các trường hợp điều kiện (3)
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 25 BK TP.HCM Slide 49/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các dạng đặc biệt (1)
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 BK TP.HCM Slide 50/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Các dạng đặc biệt (2) * (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) 26 BK TP.HCM Slide 51/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Biến cục bộ (1)
Toán tử let
(let ((var1 E1) … (varm Em)) Em+1 … En)
Ta gán cho mỗi biến giá trị của biểu thức tương ứng, sau đó đánh giá:
(progn expm+1 … expn)
Ví dụ: * (let ((x (fac 4))) (* x x)) 576 BK TP.HCM Slide 52/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Biến cục bộ (2) * (setf x 5) 5 * (let ((x 1)) x) 1 * x 5 * (let ((x 1)) (setf x 2) x) 2 * x 5
Che phủ các biến toàn cục 27 BK TP.HCM Slide 53/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Biến cục bộ (3) * (defun foo(x) (let ((x 1)) x ) ) FOO * (foo 4) 1
Che phủ các đối số của một hàm BK TP.HCM Slide 54/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Biến cục bộ (4) * (defun bar(x) (let ((x 1) (y (1+ x))) y) ) BAR * (bar 4) 5
Các liên kết được thực hiện song song 28 BK TP.HCM Slide 55/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Cấu trúc lặp
DOTIMES
Lặp trên số
DOLIST
Lặp trên danh sách BK TP.HCM Slide 56/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp DOTIMES – Hỗ trợ lặp trên số
upper-bound-form được đánh giá → n.
count được gán các số từ 0 → n-1 (n lần)
Thân vòng lặp được thực hiện n lần, giá trị của là kết quả cần tính. (dotimes ( ) ) 29 BK TP.HCM Slide 57/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp
Ví dụ: Tính lũy thừa mn = m×m×.. ×m DOTIMES (2) (defun power(m n) (let ((result 1)) (dotimes (count n result) (setf result (* m result)) ) ) ) BK TP.HCM Slide 58/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp DOLIST – Lặp trên danh sách
list form được đánh giá → danh sách a1→an
element được gán từ a1 → an (n lần)
Với mỗi giá trị ai, phần thân vòng lặp (body) được đánh giá.
Không có result form, DOLIST sẽ trả về NIL (dolist ( ) ) 30 BK TP.HCM Slide 59/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp
Đếm số phần tử là số trong danh sách: DOLIST (2) (defun collect-number(l) (let ((result 0)) (dolist (e l result) (when (numberp e) (setf result (+ result 1)) ) ) ) ) BK TP.HCM Slide 60/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Cài đặt Lisp
Download GC-Lisp từ trang Web:

Double click để giải nén file zip
Extract vào “C:\”
Xuất hiện dialog, tạo thư mục “C:\GCLisp”
Trả lời OK 31 BK TP.HCM Slide 61/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Startup gclisp
Chạy từ file ‘C:\GcLisp\GcLisp.exe’ BK TP.HCM Slide 62/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Môi trường GC-LISP
Ta thấy cửa sổ GCLISP như sau: 32 BK TP.HCM Slide 63/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Một số phím tắt
-H giúp đỡ
-E vào LISP Explorer
-E vào cửa sổ soạn thảo GMACS
rời khỏi GMACS và trở về Lisp
load một file vào GMACS
lưu một file
lưu file với tên khác BK TP.HCM Slide 64/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Dòng lệnh
Gõ thử các lệnh sau: 33 BK TP.HCM Slide 65/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp GMAC editor window
Nhấn -E để vào trình soạn thảo
để lưu file and trở lại GcLisp BK TP.HCM Slide 66/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp Load file vào GcLisp * (load ‘first)
Load file “first.lsp” 34 BK TP.HCM Slide 67/67Nguyễn Thị Trúc Viên Ngôn ngữ lập trình Lisp DEBUG