前言

The Little Schemer(TLS)的目的是教讀者寫遞迴。 這篇筆記不依照章節順序，用主題式的方式，把我心中的這本書呈現出來。

行前須知

知道什麼是?

  • base 與 inductive case 在歸納法中大概的意思

快速Scheme Tutorial

調用: (<function-or-operator) <args...>) 宣告變數: (define <var-name> <value>) 條件式:

(if <predicate>
  <when-true>
  <when-false>)
(cond
  [<predicate> <do-somthing>]
  ...
  [else <do-somthing>])

函數:

(define <func-name>
  (lambda (<args...>)
    <do-somthing>))
;; OR
(define (<func-name> (<args...>))
    <do-somthing>)

匿名函數:

(lambda (<args...>)
  <do-somthing>)

本書用到的資料結構介紹

Atom

<line-of-characters>還有數字

List of OO

有哪些可能性(case)

  • base case: 空
  • inductive case: 有東西

建構

  • 空 的case : ‘()
  • 有東西 的case : cons

分解

  • 有東西 的case : car 與 cdr 對應到cons有兩個參數，所以會有兩個解構子。

區分case

  • 空 的case : null?

Integer

有哪些可能性(case)

  • base case: 0
  • inductive case: 零以上

建構

  • 0 的case : 0
  • 零以上 的case : add1

分解

  • 零以上 的case : sub1

區分case

  • 0 的case : zero?

List of List & S-Exp

後面再說

在 OO 上做遞迴

遞迴就是分解資料再建構出需要的資料。

所以在寫遞迴程式之前要先問是對什麼資料做遞迴，不同的資料有不同的分解方式。

先來看看如何分解資料，如何分解資料與資料結構的定義有關。

List只有兩種case，空的(()) 或是 有一個東西加在前面(cons x (sub-list)) 所以要寫 List of Atom的函數時要區分這兩種case，同時做相對應的處理。 所以List of Atom的程式大致上都會長成

(define (<func-name> l ...)
  (if (null? l)
    <when l is () >
    <when l is (cons x (sub-list))>))

Integer與List of Atom很像，但是

  • 空的 變成 零
  • (cons x …) 變成 (add1 …) 與List of Atom的程式有八十七%像
(define (<func-name> n ...)
  (if (zero? n)
    <when n is () >
    <when n is (cons x (sub-list))>))

還有一個是List of List，其實就是樹。 與List of Atom不同的是Atom沒有不同的case要處理但是List有兩種case要處理!! 因此List of List的程式還要看第一個東西是不是List

(define (<func-name> l ...)
  (if (null? l)
    <when l is () >
    (if (atom? (car l))
      <when (car l) is atom>
      <when (car l) is list>)))

所以從上面的三個模板可以看到，遞迴程式的骨架，是與資料結構的定義綁在一起的。

接著來看怎麼重組資料，像同樣對List of Atom做遞迴可以有

  • 吃 List of Atom 回傳 該List長度 的 length
  • 吃 List of Atom 與 某個Atom 回傳 移除該Atom的List of Atom 的 rember

找著前面的List of Atom模板，可以快速寫出

(define (length l)
  (if (null? l)
    ...
    ...))
(define (rember l x)
  (if (null? l)
    ...
    ...))

length的回傳值是Integer，所以一定會用到建構Integer的工具， 0就是建構零這個case的工具，另一個case就是用add1。

rember的List of Atom，有兩種case，空是()，前面有東西是(cons x <sub-list>)。 所以上面兩個程式寫成

(define (length l)
  (if (null? l)
    0
    (add1 ...)))
(define (rember l x)
  (if (null? l)
    '()
    (if (eq? x (car x)) ;; 第一項是不是x
        ...
        (cons (car l) ...))))

接著剩下的部分要填什麼? 遞迴的時候!!

(define (length l)
  (if (null? l)
    0
    (add1 (length (cdr l)))))
(define (rember l x)
  (if (null? l)
    '()
    (if (eq? x (car x)) ;; 第一項是不是x
        (rember (cdr l) x)
        (cons (car l) (rember (cdr l) x)))))

基本上，遞迴只要確定要遞迴的資料結構，就很簡單。 依據輸入的資料結構分解，依循回傳的資料結構建構資料。

但是還是有一些奇耙的遞迴，像河內塔與阿克曼函數。

本書介紹的遞迴都是原始遞迴函數(primitive recursive function)。 也就是說，每次遞迴時只有一個參數與遞迴有關，同時參數只縮小一個單位，其他參數保持不變。

像斐波那契就不是原始遞迴函數，詳細的可以去這裡看。

equal? & s-exp

來試著寫寫相等吧，先從Atom開始。

(define (eqAtom? a b)
  (cond
    [(and (number? a) (number? b)) (= a b)] ;; 都是數字用 =
    [(or (number? a) (number? b)) #f] ;; 連type都不一樣就一定不一樣
    [else (eq? a b)])) ;; 都是symbol用eq?

接著寫List of List的。 先把所有可能性列出來 3*3 = 9 3是List of List的case數

(define (eqList? a b)
  (cond
    [(and (null? a) (null? b))
      #t]
    [(and (null? a) (atom? (car b))) ;; !!
      #f]
    [(null? a) ;; !!
      #f]
    [(and (atom? (car a)) (null? b))
      #f]
    [(and (atom? (car a)) (atom? (car b)))
      (and (eqAtom? (car a) (car b))
           (eqList? (cdr a) (cdr b)))]
    [(atom? (car a))
      #f]
    [(null? b)
      #f]
    [(atom? (car b)))
      #f]
    [else
      (and (eqList? (car a) (car b))
           (eqList? (cdr a) (cdr b)))]))

只要有(null? a)就是錯，所以可以合起來，讓下面的吃掉上面的， 因為下面的可以cover上面的情形。

(define (eqList? a b)
  (cond
    [(and (null? a) (null? b))
      #t]
    [(null? a) ;; !!1
      #f]
    [(and (atom? (car a)) (null? b))
      #f]
    [(and (atom? (car a)) (atom? (car b)))
      (and (eqAtom? (car a) (car b))
           (eqList? (cdr a) (cdr b)))]
    [(atom? (car a)) ;; !! 2
      #f]
    [(null? b) ;; !!1
      #f]
    [(atom? (car b))) ;; !!2
      #f]
    [else
      (and (eqList? (car a) (car b))
           (eqList? (cdr a) (cdr b)))]))

回答都是錯，同時條件之間，不會互相影響，在and後做都ok， 所以用or合起來。

(define (eqList? a b)
  (cond
    [(and (null? a) (null? b))
      #t]
    [(or (null? a) (null? b))
      #f]
    [(and (atom? (car a)) (null? b)) ;; !!
      #f]
    [(and (atom? (car a)) (atom? (car b)))
      (and (eqAtom? (car a) (car b))
           (eqList? (cdr a) (cdr b)))]
    [(or (atom? (car a)) (atom? (car b))))
      #f]
    [else
      (and (eqList? (car a) (car b))
           (eqList? (cdr a) (cdr b)))]))

過了第2條式子，代表a與b皆不為空，在後面的式子與檢查a或b是空的都沒有用。 可以刪掉。

(define (eqList? a b)
  (cond
    [(and (null? a) (null? b))
      #t]
    [(or (null? a) (null? b))
      #f]
    [(and (atom? (car a)) (atom? (car b)))
      (and (eqAtom? (car a) (car b))
           (eqList? (cdr a) (car b)))]
    [(or (atom? (car a)) (atom? (car b)))
      #f]
    [else
      (and (eqList? (car a) (car b))
           (eqList? (cdr a) (cdr b)))]))

其實寫的時候要遵照，先and再or，從最小的case開始到後面的case， 就可以直接寫出最終版了。

接著寫個萬用的equal?

(define (equal? a b)
  (cond
	  [(and (atom? a) (atom? b))
      (eqAtom? a b)]
	  [(or (atom? a) (atom? b))
      #f]
	  [else
      (eqList? a b)]))

先把相關的程式列出來看看。

(define (eqAtom? a b)
  (cond
    [(and (number? a) (number? b))
      (= a b)]
    [(or (number? a) (number? b))
      #f]
    [else
      (eq? a b)]))
(define (eqList? a b)
  (cond
    [(and (null? a) (null? b))
      #t]
    [(or (null? a) (null? b))
      #f]
    [(and (atom? (car a)) (atom? (car b))) ;; !!
      (and (eqAtom? (car a) (car b))
           (eqList? (cdr a) (car b)))]
    [(or (atom? (car a)) (atom? (car b))) ;; !!
      #f]
    [else
      (and (eqList? (car a) (car b)) ;; !!
           (eqList? (cdr a) (cdr b)))]))
(define (equal? a b)
  (cond
	  [(and (atom? a) (atom? b)) ;; !!
      (eqAtom? a b)]
	  [(or (atom? a) (atom? b)) ;; !!
      #f]
	  [else
      (eqList? a b)])) ;; !!

eqList?與equal?的後三條式子好像!! 有沒有辦法用equal?來縮減eqList?? 如果用equal?先求(car a)是否等於(car b)的話…

(define (eqList? a b)
  (cond
    [(and (null? a) (null? b))
      #t]
    [(or (null? a) (null? b))
      #f]
    [else
      (and (equal? (car a) (car b))
           (eqList? (cdr a) (cdr b)))]))
(define (equal? a b)
  (cond
	  [(and (atom? a) (atom? b))
      (eqAtom? a b)]
	  [(or (atom? a) (atom? b))
      #f]
	  [else
      (eqList? a b)]))

最後，再把所有式子列出來吧。

(define (eqAtom? a b)
  (cond
    [(and (number? a) (number? b))
      (= a b)]
    [(or (number? a) (number? b))
      #f]
    [else
      (eq? a b)]))
(define (eqList? a b)
  (cond
    [(and (null? a) (null? b))
      #t]
    [(or (null? a) (null? b))
      #f]
    [else
      (and (equal? (car a) (car b))
           (eqList? (cdr a) (cdr b)))]))
(define (equal? a b)
  (cond
	  [(and (atom? a) (atom? b))
      (eqAtom? a b)]
	  [(or (atom? a) (atom? b))
      #f]
	  [else
      (eqList? a b)]))

到這裡就可以看出Lisp的s-exp的定義了。

  • S-Exp
    • Atom
      • Number
      • Symbol
    • List
      • Null
      • Cons List

first-class function & CPS

一級函數可以捕捉變數，與當成資料丟來丟去，所以可以用它來做一些噁心的事。

像我們可以試著替下面這個函數加入C語言中的return

(define (sum l)
  (if (null? l)
    0
    (+ (car l) (sum (cdr l)))))

0可以直接return，但是return要從哪裡來? 我們可以多加一個參數，叫return

(define (sum l return)
  (if (null? l)
    (return 0)
    (return (+ (car l) (sum (cdr l))))))

等等，(sum (cdr l))是不是少了一個參數，要給他什麼?

痾…，直接傳入return? 但是這樣接不起來…

(return 0)應該要回到，(+ (car l) 0)才對 所以(return 0)的return應該是

(lambda (n)
  (+ (car l) n))

這個加總應該要return才對，所以再改成

(lambda (n)
  (return (+ (car l) n)))

可以回到原本的sum了

(define (sum l return)
  (if (null? l)
    (return 0)
    (return (+ (car l) (sum (cdr l)
                            (lambda (n)
                              (return (+ (car l) n))))))))

痾…，那個最外層的(return (+ ...))不是在lambda中嗎 應該要刪掉吧

(define (sum l return)
  (if (null? l)
    (return 0)
    (sum (cdr l)
         (lambda (n)
           (return (+ (car l) n))))))

這個就是cps版本的sum，觀察這個程式會發現

  1. 他從遞迴變成迴圈了
  2. 每過一次迴圈，return會變多變長，所以
  3. 雖然說是迴圈，但是遞迴的成本還在
  4. 這return是函數，所以應該可以有(回傳)多個參數

像是說再sum中加入看有沒有0的功能

(define (sum l return)
  (if (null? l)
    (return 0 #f)
    (sum (cdr l)
         (lambda (n z)
           (return (+ (car l) n) (or (zero? (car l)) z))))))

完成了cps版本的程式，那有沒有辦法直接轉出cps的作法? 先看無cps與cps的對比

(define (sum l)
  (if (null? l)
    0
    (+ (car l) (sum (cdr l)))))

(define (sum l return)
  (if (null? l)
    (return 0)
    (sum (cdr l)
         (lambda (n)
           (return (+ (car l) n))))))

看到參數列，他多了return 看到base case，直接調用return 看到inductive case，

  1. 遞迴的部分被拉出來了
  2. 跳回來要做的事，被放到lambda中
  3. 在lambda因為完成了計算，所以調用了return

根據剛剛的觀察，我們可以找到手工轉cps的方法

  1. 參數列加入return
  2. base case直接調用return
  3. 把遞迴的部分拉到最外面
  4. 在lambda完成原本跳回來的計算，並調用return

來試試轉fib吧

(define (fib n)
  (if (< n 2)
    1
    (+ (fib (- n 1)) (fib (- n 2)))))

先加return與base case調用return

(define (fib n return)
  (if (< n 2)
    (return 1)
    (+ (fib (- n 1)) (fib (- n 2)))))

接著要把遞迴拉出來，但是這有兩個遞迴，要怎麼辦? 如果用C語言來寫原本的fib可以寫成

int fib(int n) {
  if(n < 2)
    return 1;
  else {
    int tmp1 = fin(n-1);
    int tmp2 = fib(n-2);
    return tmp1 + tmp2;
  }
}

所以我們應該也可以像tmp1與tmp2一樣，一次處理一個，在最後再調用return

(define (fib n return)
  (if (< n 2)
    (return 1)
    (fin (- n 1)
         (lambda (tmp1)
            (fib (- n 2)
                 (lambda (tmp2)
                    (return (+ tmp1 tmp2))))))))

應該要修修前面的手工方法

  1. 參數列加入return
  2. base case直接調用return
  3. 一次把一個遞迴的部分拉到最外面
  4. 在lambda完成原本跳回來的計算，並調用return

到這裡終於可以來說明什麼是cps了!! cps是continuation-passing-style的簡稱。 continuation中文叫延續。

雖然上面都是用return來代稱，但是continuation能做的事不只是return而已。

continuation可以想像成代辦事項或是Program conuter，也許會比較好思考一點。

如果改變continuation的內容，可以讓原本的程式跑去做別的事，一去不復返，或是再回來同一個地方。

可以用continuation實現像prolog的DSL、exception的catch-throw與簡單的thread等神奇的應用。

有機會可以等The Seasoned Schemer的心得寫完，來整理continuation的應用與在邏輯上的意義。

題外話，其實再多一點推導，可以推出continuation的monad，但是monad的推導與整理，也是之後再拉一篇文章來寫。

TODO

Y combinator的CPS版是?

Y combinator

我們從sum開始

(define sum
  (lambda (l)
    (if (null? l)
      0
      (+ (car l) (sum (cdr l))))))

假設我們沒有define來做遞迴了，但是要做出sum的效果。

可以多加一層來引入能做出sum效果的函數

(define sum-cant-work
  (lambda (sum1)
    (lambda (l)
      (if (null? l)
        0
        (+ (car l) (sum1 (cdr l)))))))

那原本的sum要給什麼，不然不會動 把整個lambda再丟到，sum的參數中就可以用了

(define sum-still-cant-work
  ((lambda (sum1)
    (lambda (l)
      (if (null? l)
        0
        (+ (car l) (sum1 (cdr l))))))  ;; sum1需要sum1!!
  (lambda (sum1)
    (lambda (l)
      (if (null? l)
        0
        (+ (car l) (sum1 (cdr l)))))))) ;; sum1需要sum1!!

等等還是不能動，看到遞迴的sum，應該要先把sum1丟到sum1中

(define sum-can-work-but-ugly
  ((lambda (sum1)
    (lambda (l)
      (if (null? l)
        0
        (+ (car l) ((sum1 sum1) (cdr l))))))
  (lambda (sum1)
    (lambda (l)
      (if (null? l)
        0
        (+ (car l) ((sum1 sum1) (cdr l))))))))

好醜，抽象重複的部分

(define sum-can-work-but-wierd
  ((lambda (mk)
    (mk mk))
   (lambda (sum1)
     (lambda (l)
       (if (null? l)
        0
        (+ (car l) ((sum1 sum1) (cdr l)))))))) ;; (sum1 sum1) 能不能改成 像 sum 這樣

現在就是(sum1 sum1)怪怪的 能不能把他抽掉嗎?

(define sum-can-work
  ((lambda (mk)
    (mk mk))
   (lambda (sum1)
    ((lambda (sum)                   ;; 從這裡到 ...
      (lambda (l)
       (if (null? l)
        0
        (+ (car l) (sum (cdr l)))))) ;; 這裡與原本的sum好像
     (lambda (arg) ((sum1 sum1) arg)))))

sum好像浮出來了 試著把他拉出去

(define sum-mk
  (lambda (sum)
      (lambda (l)
       (if (null? l)
        0
        (+ (car l) (sum (cdr l)))))))
(define sum-can-work
  (lambda (sum-mk)
    ((lambda (mk)
      (mk mk))
     (lambda (sum1)
      (sum-mk
        (lambda (arg) ((sum1 sum1) arg)))))))

這sum-can-work好像可以產生sum以外的遞迴函數，應該換個名字

(define Y
  (lambda (mk)
    ((lambda (f)
      (f f))
     (lambda (g)
      (mk
        (lambda (arg) ((g g) arg)))))))

這就是Y combinator嚴格求值版。 還有惰性求值版與set!版。 set!版在The Seasoned Schemer有介紹，而惰性求值版之後會在Y combinator的專文中補完。

略過的部分

  • 直譯器
  • set & relation
  • 停機問題 直譯器等到以後打EoPL與LiSP的心得再說。 set與relation的部分直接去看就好。 停機問題等摸熟計算理論再說吧。