前言

The Seasoned Schemer(TSS)的目的是補完TLS中沒有提及的狀態。 這篇筆記同樣不依照章節順序，用主題式的方式，把我心中的這本書呈現出來。

行前須知

知道什麼是?

  • Scheme
  • 遞迴

accumulator parameter

reverse

如果要反轉list，在有append情況下可以寫成

(define (rev l)
  (if (null? l)
    '()
    (append (rev (cdr l)) (cons (car l) '()))))

但我們需要一直append嗎? 如果我們可以從第一個開始就先cons出來的東西，不就是我們要的。

(define (rev l acc)
  (if (null? l)
    acc
    (rev (cdr l) (cons (car l) acc))))

引入acc可以記下我們從頭到目前看過的東西。

flatten

同樣在要攤平list時，如果有append可寫成

(define (atom? x) 
  (and (not (pair? x))
       (not (null? x))))
(define (fl lol)
  (cond
    [(null? lol) '()]
    [(atom? (car lol)) (cons (car lol) (fl (cdr lol)))]
    [else (append (fl (car lol)) (fl (cdr lol)))]))

這裡是不是可以利用剛剛acc可以記下目前看過的東西的特性來改寫呢?

(define (flat lol acc)
  (cond
    [(null? lol) acc]
    [(atom? (car lol)) (flat (cdr lol) (cons (car lol) acc))]
    [else (flat (cdr lol) (flat (car lol) acc))])) ;;先走car，再走cdr

但是這樣出來的是反的，要記得反轉。

let & letrec

從TLS到現在引入變數不是用define(全域)，不然就是lambda(區域) 如果想引入區域變數，就要用lambda，且apply值，不過這樣寫起來還蠻難看的。 所以有let

(let ((a 10))
  (+ a 10))
<=>
((lambda (a)
  (+ a 10))
 10)

但這樣無法遞迴，如果要遞迴就是用Y組合子，不然就是letrec

(letrec ((len (lambda (l)
                      (if (null? l)
                          0
                          (+ 1 (len (cdr l)))))))
          len)
<=>
(define len
  (lambda (l)
    (if (null? l)
        0
        (+ 1 (len (cdr l))))))

let over lambda

如果把let包在lambda外面會變成像

(let ((a ...))
  (lambda (...)
    ...))

這樣會變成只有這個lambda看的到a，可以用這個手法保護變數。 還可以搭配set!做出getter與setter，十分OO。

set!

一般常見的程式語言中都有改寫變數值的方法。 Scheme也有叫set!

(define a 10) ;; a is 10
(set! a 20)
;; a is 20

原本在同一個scope中的變數的資料都是不會變的，現在就被打破了!!

我們必須意識到與自行安排與管理狀態與時間。

原本用lambda可以做出List的效果

(define ((kons a d) f)
    (f a d))
(define (kar c)
    (c (lambda (a d) a)))
(define (kdr c)
    (c (lambda (a d) d)))

但現在把set!做到List中，我們只需要set-kdr!

(define (bons a)
    (let ((d '()))
        (lambda (f)
          (f (lambda (x) (set! d x))
              a d))))
(define (kar c)
    (c (lambda (s a d) a)))
(define (kdr c)
    (c (lambda (s a d) d)))
(define (set-kdr! c x)
    ((c (lambda (s a d) s)) x))
(define (kons a d)
    (let ((c (bons a)))
        (set-kdr! c d)
        c))

有了set-kdr!就可以做出cycle， 要怎麼找出cycle?

首先要找出兩個變數是不是一樣，沒有set!之前，只要值相等，這兩個變數就是一樣的． 但有了set!就不一樣了，所謂的一樣應該是來自同一個地方才對． 所以相等的也不等於一樣了，如果一樣，set!後應該會同時改變才對．

(define (same? a b)
     (let ((t1 (kdr a))
            (t2 (kdr b)))
       (set-kdr a 1)
       (set-kdr b 2)
       (let ((ans (= (kdr a) (kdr b))))
        (set-kdr a t1)
        (set-kdr b t2)
        ans)))
(define (same? a b)
     (let ((t1 (cdr a))
            (t2 (cdr b)))
       (set-cdr! a 1)
       (set-cdr! b 2)
       (let ((ans (= (cdr a) (cdr b))))
        (set-cdr! a t1)
        (set-cdr! b t2)
        ans)))

如果兩個速度不同的人在cycle中走，那速度快的一定會碰到速度慢的． 所以讓兩個變數往前走，但速度不同就好，而龜兔賽跑演算法速度給(1,2)．

(define (finite-len p)
    (letcc out
        (letrec ((C (lambda (p q)
                      (cond
                        ((same? p q) (out ‘oops))
                        ((null? q) 0)
                        ((null? (kdr q)) 1)
                        (else (+ (C (kddr p) (kdr q)) 2)))
                 (kddr (lambda (x) (kdr (kdr x))))))
    (if (null? p)
        0
        (add1 (C p (kdr p)))))))
(define (finite-len l)
  (call-with-current-continuation
   (lambda (oops)
     (define (F a b)
       (cond
         ((null? b) 0)
         ((same? a b) (oops 'no))
         (else
          (+ 1 (F (cdr a) (cddr b))))))
     (cond
       ((null? l) 0)
       ((null? (cdr l)) 1)
       (else
        (+ 1 (F l (cdr l))))))))

(0,1) - (+2,+1) -> (2,2)

letrec & let & set!

為什麼let引入的變數沒辦法遞迴?

因為在lambda中其實看不到遞迴的那個變數。 所以在Y組合子的遞迴函數那邊才會多一個接收另一個函數的參數。

那多了set!的現在，能不能簡單的完成遞迴?(在沒有define的狀態下)

先引入遞迴函數的名字(let)，再用看的到該名字的lambda改寫變數(set!)

(let ((len 'whatever))
  (set! len (lambda (l)
                    (if (null? l)
                        0
                        (+ 1 (len (cdr l))))))
  len)
<=>
(define len
  (lambda (l)
    (if (null? l)
        0
        (+ 1 (len (cdr l))))))
<=>
(letrec ((len (lambda (l)
                      (if (null? l)
                          0
                          (+ 1 (len (cdr l)))))))
          len)

Y!

有了set!可以有新的遞迴產生方法，那能不能有新的Y組合子? 從len開始看。

(define len
  (lambda (l)
    (if (null? l)
        0
        (+ 1 (len (cdr l))))))

用剛剛的方式改寫

(define len
  (let ((len2 'whatever))
    (set! len2 (lambda (l)
                      (if (null? l)
                          0
                          (+ 1 (len2 (cdr l)))))) ;; !!
    len2))

lambda與len2綁在一起，我們必須要抽出來

(define len
  (let ((len2 'whatever))
    (set! len2 (lambda (f) ;; !!
                  (lambda (l)
                      (if (null? l)
                          0
                          (+ 1 (f (cdr l)))))) ;; !!
    len2))

f必須是個可以碰到len2的函數，來把參數丟進去。

(define len
  (let ((len2 'whatever))
    (set! len2 ((lambda (f)
                  (lambda (l)
                      (if (null? l)
                          0
                          (+ 1 (f (cdr l))))))
                (lambda (arg) (len2 arg)))
    len2))

熟悉的東西出來了，抽出來。

(define lenMK
  (lambda (f)
    (lambda (l)
        (if (null? l)
            0
            (+ 1 (f (cdr l)))))))
(define (Y! mk)
  (let ((len2 'whatever))
    (set! len2 (mk
                (lambda (arg) (len2 arg)))
    len2)))
(define len (Y! lenMK))

continuation

continuation可以想像成代辦事項或是Program conuter，也許會比較好想像一點。 如果改變continuation的內容，可以讓原本的程式跑去做別的事，一去不復返，或是再回來同一個地方。

continuation可以當成C語言中的label，調用continuation就是用jump。 但與label不同的是這是可以存在變數的label!!

escape from here

連乘List中的數字

(define (fac l)
  (if (null? l)
      1
      (* (car l) (fac (cdr l)))))

不過如果中間有0的話應該不用繼續做下去，要直接跳出去。 那我們應該可以用continuation來跳出去，只要continuation在程式的外面就ok了

(define call/cc call-with-current-continuation)
(define (fac l)
  (call/cc (lambda (escape)
    (define (fac2 l)
      (cond
        [(null? l) 1]
        [(zero? (car l)) (escape 0)]
        [else (* (car l) (fac2 (cdr l)))]))
    (fac2 l))))

一旦調用了escape整個call/cc的回傳值會變成傳入escape中的資料。 如果沒有用到escape call/cc的部分就像不存在一樣。

go back to here

(define return 0)
(define resume 0)
(define (walk* lol)
  (cond
    ((null? lol)
      'empty)
    ((atom? (car lol))
      (call/cc (lambda (here)
        (set! resume here)
        (return (car lol))))
      (walk* (cdr lol)))
    (else
      (walk* (car lol))
      (walk* (cdr lol)))))
(define (get-next)
  (call/cc (lambda (here)
    (set! return here)
    (resume 'whatever))))
(define (loop old)
      (if (eq? old 'nothing)
          #f
          (let ((secend-one (get-next)))
            (if (eq? secend-one old)
                #t
                (loop secend-one)))))
(define (two* lol)
  (let ((first-one
          (call/cc (lambda (here)
            (set! return here)
            (walk* lol)
            (return 'nothing)))))
      (loop first-one)))

iteraor & set! & define

define 可以當成lambda引入新的變數(參數)

set! 視為partial apply 來自define的參數

;; [LISTOF X] -> ( -> X u 'you-fell-off-the-end)
(define (generate-one-element-at-a-time lst)

  ;; Hand the next item from a-list to "return" or an end-of-list marker
  (define (control-state return)
    (for-each 
     (lambda (element)
               (set! return (call-with-current-continuation
                              (lambda (resume-here)
                                ;; Grab the current continuation
                               (set! control-state resume-here)
                               (return element)))))
     lst)
    (return 'you-fell-off-the-end))
  
  ;; (-> X u 'you-fell-off-the-end)
  ;; This is the actual generator, producing one item from a-list at a time
  (define (generator)
    (call-with-current-continuation control-state))

  ;; Return the generator 
  generator)

(define generate-digit
  (generate-one-element-at-a-time '(0 1 2)))

陰陽謎題

(define (now)
  (call-with-current-continuation (lambda (c) c)))
(let* ((yin
         (let ((cc (now)))
          (display #\@)
          cc))
       (yang
          (let ((cc (now)))
            (display #\*)
            cc)))
    (yin yang))

一開始會印出@*

再來會跳回去yin的call/cc，所以此時的yin是上一次的yang(第一個)，所以新出現的yang(第二個)會apply到第一個yang去，所以會再多印一個*，所以總共印@**

在這裏第二個yang透過原本的yin跳回去印@，再產生第三個yang再印一個*，如此重複

在每一次的循環中產生新的yang，所以經過每一次的循環都會多一個*

略過的部分

  • 直譯器 直譯器等到以後打EoPL與LiSP的心得再說。