image/svg+xml cond eq quote atom cdr cons car 七個公理 LISP 七日談 起初，神創造七個公理，於是有了lisp 。 cons 神先創造cons ，再用cons 創造世間萬物。 car cdr (cons 1 2) 1 2 (setq my-cons (cons 1 "hello"));; (1 . "hello")(car my-cons) ; 1(cdr my-cons) ; "hello" cons 是一種有二個欄位的資料結構，欄位內容可以是任何東西。 list 0 1 用cons 存放另一個cons ，構成列表。 對列表來說 car 是取首元素 cdr 是取其餘列表 (list 0 1 2 3);; 建構一個列表 3 4 nil 一個特殊的符號 nil 標示列表的結束。 (1 . (2 . (3 . (4 . nil)))) dot pair (1 2 3 4) list tree 於是我們可以用表建構樹的結構。 (1 2 (1 2) (3 (4 5) (5 6 7)) 5) 1 2 1 2 3 5 4 5 5 6 7 nil 本身表示空表 () 想像只有一個元素的表寫成 (1 . nil) ，則沒有元素的表 () 即是nil 。 2 接下來我們談談函數 f(a, b, c) 函數 參數 參數 參數 一個函數呼叫 這裡括號只代表一件事：函數呼叫 但引入算符後，括號多了改變優先權的功能。 a * b + c a * (b + c) 語法分析變麻煩 不優雅 算符還有右結合、二元算符多種情況。 約翰麥卡鍚決定，lisp 中只有函數，沒有算符。 multiply(a, add(b, c)) 語法 怎麼用lisp 的資料結構表示函數呼叫呢？ (f a b c) (f (g x) y) f(a b c) f(g(x) y) parser 最初麥卡鍚是這樣想的 但大家很快發現這樣的parser 沒意義，反而習慣原始的寫法。 (* 1 (/ 3 4 5) (+ 2 3)) (printf "%s is %s!\n" "LISP" "Rock") 於是就這麼定了 car 取出cons 的car 內容 cdr 取出cons 的cdr 內容 cons 創造出一個cons ，裡面記錄了car 和cdr 二筆資料 special form 程式語言除了函數呼叫，還有控制結構。 if switch while for 神說s 表達式是好的，就用s 表達式表達控制結構。 (if (= a b) (foo (* a 2)) (* a b)) (cond ((= a b) (foo (* a b))) ((> a b) a) (t (* b b)) 雖然看起來很像函數，但求值順序不同。 有別於一般控制結構，lisp 的控制結構是有返回值的。 (defun max (a b) (if (> a b) a b)) (define (max-square a b) (square (if (> a b) a b))) 關於迴圈 神不需要迴圈。 詳細說就是，可以用遞迴實現，所以迴圈並不是必要。 (defun while (test todo) (if (test) (progn (todo) (while test todo)))) 注意這裡的必要。像是你無法用函數實現短路求值的and 或or ，而是反過來短路求值需要由if 實現。 (defun and (a b) (let ((a-result (a))) (if a-result (b) nil))) 因為函數呼叫時會對所有參數求值，再把參數值傳入函數，所以是不可能用函數實現and 的。 尾端遞迴 遞迴有佔用大量stack 的問題，但一種特殊的稱為尾端遞迴可以避免這種的情況。 (defun sum-interval (i n sum) (if (> i n) sum (sum-interval (+ i 1) n (+ sum i))))(sum-interval 0 10 0) ; 55 語法樹 到這裡應該有人發現了，lisp 的語法和list 根本一模一樣。 (foo 1 2 3);; 用 1 2 3 作參數呼叫foo(foo bar baz);; 一個含有三個元素的表 那怎麼區分表和函數呢？ quote 這也是lisp 用來表達語法樹的關鍵 來寫interpreter 吧！ 函數eval，輸入一個列表，然後執行 quote (quote x) ; x;; 簡寫為 'x quote 的內容將不會被求值！ 此時x 成為symbol 可以想像成語法樹中一個token ，或一個hash 值 symbol 代表在一個dict 中的key ，可以在一個環境裡被求值 symbol (qoute (+ 1 2));; 也就是 '(+ 1 2);; 返回一個表 (+ 1 2);; 這裡的 + 是symbol 談談set 之前我們用過setq ，但他不是函數！ (setq n 10);; n 未定義！ (set 'n 10);; 此時n 是一個符號，不會被求值 ;; setq stand for set quote(setq n 10);; produce (set (quote n) 10);; or (set 'n 10) 我們可以寫一個函數來翻譯，也就是macro (defmacro setq (setq-list) (defun nth (n list) (if (= n 0) (car list) (nth (- n 1) (cdr list)))) (list 'set (list 'quote (nth 1 setq-list)) (nth 2 setq-list))) 我們做了什麼？ 接受一段程式，改寫內容，返回改寫的程式 atom 判斷是否非cons eq 判斷二符號是否相等 (eq (cons 0 1) (cons 0 1));; false! (eq 'foo 'foo);; true key value 節構 ((a . 0) (b . 1) (foo . bar) (hello . "world")) (defun assoc (key dict) (let ((first-pair (car dict))) (if (eq key (car first-pair)) (cdr first-pair) (assoc key (cdr dict))))) (eval '(car '(1 2 3))) cond (cond ((= 1 2) (print "imposible")) ((= 1 1) "hello world") (t -1)) cond 和if 可以互相實現 函數的結構 (defun subst (to from tree) (if (atom tree) (if (eq from tree) to tree) (cons (subst to from (car tree) (subst to from (cdr tree)))) (defun first (list) (car list)) (lambda (list) (car list)) (setq my-list '(1 2 3))(first my-list) (car first) ; lambda(car (cdr first)) ; (list)(car (cdr (cdr first))) ; (car list) (defun eval-function (function-body argument-name argument-value) (defun subst-list (from-list to-list tree) (if (null from-list) tree (subst-list (cdr from-list) (cdr to-list) (subst (car from-list) (car from-list) tree)))) (eval (subst-list argument-name argument-value))) (defun eval-cond (cond-list env) ;; cond-list: ;; ((= 1 2) 0) ;; ((> 3 4) (print "imposible")) ;; (t (print "yes")) (let ((first-cond (car cond-list))) (if (eval (car first-cond) env) (eval (second first-cond)) (eval-cond (cdr cond-list) env)))) (defun eval (elist env) (if (atom elist) (assoc elist env) (let ((f (car elist))) (case f ('cons (cons (eval (car elist) env) (eval (cdr elist) env))) ('car (car (eval (second elist) env))) ('cdr (cdr (eval (second elist) env))) ('atom (atom (eval (second elist) env))) ('eq (eq (eval (second elist) env) (eval (third elist) env))) ('quote (second elist)) ('cond (eval-cond (cdr elist) env)) ('otherwise ; f is (lambda (a b) ...) (let ((function-body (third f)) (argument-name (second f)) (argument-value (eval-list (second elist)))) (eval-function function-body argument-name argument-value env))))))) 副作用 lisp 的函數體是一或多個expression ，但除非有副作用，不然只有最後一個expression 有意義。 (defun my-function (x y) (+ x y) ; 沒有意義的expression (+ (* x 2) (* y 6)) ; 沒有意義的expression (setq x 18) ; 這個expression 有意義，因為有副作用 (* (/ x 2) (- 6 y))) ; 這個有意義，因為會被return let (let ((x 2) (y 3) (z 5)) (+ x y z)) ((lambda (x y z) (+ x y z)) 2 3 5) 試著實現let 看看吧 (defun let-to-lambda (let-list) (let ((argument-name (map first (second (let-list)))) (argument-value (map second (second (let-list)))) (body (nthcdr 2 let-list))) (cons `(lambda ,argument-name ,body) argument-value))) 參考資料 函數就只是個列表，可以直接用car cdr 操作！ todo * side effect* defun not work (lambda (x) (* x x));; mean:;; '(lambda (x) (* x x)) ((lambda () 100)) ; 100(map (lambda (x) (+ x 3)) '(1 2 3 4));; (4 5 6 7) 匿名函數lambda * SICP (structure and interpretation of computer program)* 想當然我在扯淡 (王垠blog)* ANSI Common Lisp* LISP 之根源 想像if 也對參數求值會發生什麼事 scope * lexical scope* dynamic scope (defun hello (user) (lambda (s) (printf "%s: %s\n" user s)))(let ((user "gold") (holk-hello (hello "holk"))) (holk-hello "hey!"));; dynamic: "gold: hey!";; lexical: "holk: hey!" (set 'a 'b)(set a "bbb")(print a) ; b(print b) ; "bbb" (set 't 't)(eval t) ; t(eval (eval t)) ; t 符號做為值 對自身求值的符號 符號的意義 yuri.say = function (s) { if (this.state == 'sleep') { return null } else { return s } if (Math.random() > 0.7) { this.state = 'sleep' }} int SLEEP = 1;int WAKE = 2;/* some code */if (yuri.state != SLEEP) { printf("hey!");}/* some code */if (random() > 0.5) { yuri.state = SLEEP;}
1
  1. lisp 七日談
  2. 七個公理
  3. cons as basic
  4. cons combine
  5. cons function
  6. cons to list
  7. cdr sub list
  8. nil end list
  9. list to tree
  10. tree figure
  11. about function
  12. bracket function call
  13. bracket order
  14. operator
  15. only function
  16. syntax structure
  17. m to s expression
  18. nosense parse
  19. no m expression
  20. only s expression
  21. s control flow
  22. like function
  23. evalute order
  24. god use no iteration
  25. recursion as loop
  26. necessary function
  27. eval if argument
  28. tail recursion
  29. tail recursion code
  30. syntax tree
  31. distinct function list
  32. distinct quote
  33. syntax tree quote
  34. quote no evalute
  35. quote list
  36. symbol
  37. symbol state
  38. symbol state c
  39. setq macro
  40. setq value symbol
  41. setq macro
  42. setq macro code
  43. what macro
  44. let us interprete
  45. eval type
  46. eval type code
  47. atom
  48. eq
  49. cond
  50. key value
  51. function structure
  52. access function internal
  53. eval function
  54. subst
  55. eval look
  56. full eval
  57. cond code
  58. implement let
  59. lambda
  60. side effect
  61. side effect code
  62. scope
  63. reference
  64. all