Thực hành lập trình lisp

Chia sẻ: | Ngày: | Loại File: PDF | Số trang:34

Thêm vào BST

Báo xấu

310
lượt xem 88
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo cung cấp kiến thức từ cơ bản đến nâng cao phần lập trình lisp, cung cấp kiến thức thực ành cảu phần lập trình này

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thực hành lập trình lisp

Th c hành Ngôn ng l p trình BK TP.HCM Nguy n Th Trúc Viên Khoa Công Ngh Thông Tin i H c Bách Khoa TPHCM N i dung BK 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 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 2/67 1
L ch s phát tri n BK 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 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 3/67 Lisp – Các ng d ng BK TP.HCM Expert problem solvers Common reasoning Learning Natural-language interfaces Education and intelligent support systems Speech and vision Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 4/67 2
Ngôn ng hư ng ch c năng BK 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) ký hi u là (f x y z) x+y ký hi u là (+ x y)  π sin  3 x +  ký hi u ra sao ? Bt:  2 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 5/67 Gi i áp bài t p BK TP.HCM (sin (+ (* 3 x) (/ pi 2))) Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 6/67 3
Ngôn ng thông d ch BK 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 vòng l p top-level Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 7/67 List Processing (1) BK 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 is d li u: danh sách g m ba thành ph n Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 8/67 4
List Processing (2) BK TP.HCM Ví d : * (+ 3 4) 7 * (+ (* 3 4) (- 5 2)) 15 *4 4 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 9/67 List Processing (3) BK 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) Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 10/67 5
Symbol (1) BK 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 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 11/67 Symbol (2) BK 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 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 12/67 6
Symbol (3) BK TP.HCM Bài t p: Symbol hay s ? AARDVARD 87 1-2-3-GO 3.12 7-11 22/7 -12 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 13/67 Symbol (4) BK TP.HCM 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 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 14/67 7
Boolean BK 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 Mc 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 () Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 15/67 Ki u d li u BK 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 expression::= atom | list Bi u th c list::=(expression1...expressionn) Danh sách atom::= s |chu i ký t |symbols Atoms T và nil Boolean Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 16/67 8
Các lo i bi u th c trong Lisp BK 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 Slide 17/67 Phân c p d li u BK TP.HCM expression list atom ... symbol number ... interger real list nil ... Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 18/67 9
Ngôn ng ng (dynamic type) BK 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 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 19/67 Ví d BK TP.HCM * (setf a ‘(1 2 3)) (1 2 3) *a (1 2 3) * (setf a 2) 2 *a 2 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 20/67 10
Các v t ki u BK 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 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 21/67 Các v t ki u BK TP.HCM * (numberp 4) T * (numberp 3.45) T * (symbolp ‘ListProcessor) T * (listp ‘(a b c)) T Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 22/67 11
Các v t trên s BK TP.HCM 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 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 23/67 Các hàm cơ b n BK TP.HCM Gán: setf và setq Các phép tính s h c +, –, *, /, \\ 1+ và 1- max, min và abs Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 24/67 12
Ví d BK 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 Slide 25/67 Các hàm so sánh (1) BK TP.HCM Các phép so sánh = hai i s cùng là m ts 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 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 26/67 13
Các hàm so sánh (2) BK 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) Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 27/67 Ví d (1) BK TP.HCM * (setf k ‘(a b) l ‘(a b)) (A B) * (equal k l) T * (eq k l) NIL * (eql k l) NIL Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 28/67 14
Ví d (2) BK TP.HCM * (setf x ‘a y ‘a) A * (equal x y) T * (eq x y) T * (eql x y) T Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 29/67 Ví d (3) BK TP.HCM * (eq 3 3) T * (eql 3 3.0) NIL * (= 3 3) T * (= 3 3.0) T Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 30/67 15
Các hàm x lý trên danh sách (1) BK TP.HCM FIRST và REST – CAR và CDR CONS, APPEND, LIST NTHCDR, BUTLAST và LAST LENGTH và REVERSE Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 31/67 Các hàm x lý trên danh sách (2) BK 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) Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 32/67 16
Các hàm x lý trên danh sách (3) BK 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) Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 33/67 Toán t ASSOC (1) BK 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 Value Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 34/67 17
ASSOC (2) BK TP.HCM L y các thành ph n t m t danh sách: (ASSOC ) Ví d : * (setf sarah ‘((height .54) (weight 4.4))) ((HEIGHT 0.54) (WEIGHT 4.4)) * (assoc ‘weight sarah) (WEIGHT 4.4) Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 35/67 ASSOC (3) BK TP.HCM Thêm m t thành ph n m i vào danh sách: (ACONS ) 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)) Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 36/67 18
nh nghĩa hàm BK TP.HCM * (defun square (x) (* x x)) SQUARE * (square 3) 9 * (defun abs(x) (if (>= x 0) x (* -1 x) ) ) ABS Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 37/67 quy trong Lisp BK 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. Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 38/67 19
ánh giá bi u th c (Evaluation) BK 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 Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 39/67 Các câu l nh i u ki n (1) BK 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) Ngôn ng l p trình Lisp Nguy n Th Trúc Viên Slide 40/67 20