The Little Schemer

http://www.ccs.neu.edu/home/matthias/BTLS/

关于partial/total function的解释这里有 http://en.wikipedia.org/wiki/Partial_function. 这里我只是记录一些continuation, halting problem, Y combinator的内容。


continuation

书中给出的continuation例子大致如下. 假设这个函数是从一个list中移除满足test-f?的元素.

(define rm
  (lambda (xs test? co)
    (cond
     ((null? xs) (co '()))
     ((test? (car xs))
      (rm (cdr xs) test?
          (lambda (nxs) (co nxs))))
     (else
      (rm (cdr xs) test?
          (lambda (nxs) (co (cons (car xs) nxs))))))))

(define cont
  (lambda (xs) xs))

(display
 (rm '(hello world hello justice)
     (lambda (x) (eq? x 'hello))
     cont))

函数rm里面的co就是continuation. 这里可能比较难懂的地方就是每次递归时都创建了一个新lambda. 这个lambda参数nxs实际上是下一次迭代返回结果, 然后做一些处理比如cons, 之后再交回给上层的continuation. 和普通函数直接返回结果不同,这里每次返回结果都会被上一层continuation捕捉到作为参数处理,然后再交回给上层。这种编程方式也称为CPS(continuation passing style).

另外一个和continuation相关的函数就是call-with-current-continuation(or call/cc). 关于call/cc介绍这里参考 这里. call/cc就是说以当前程序的continuation(或者说运行位置)作为参数发起一个函数调用,在这个函数调用里面可以使用这个continuation. 如果一旦使用这个continuation的话,那么就带上continuation的参数调回到原来程序的运行位置继续执行。以链接中给出的例子来说明

(+ 1 (call/cc
      (lambda (cont)
        (+ 2 (cont 3)))))

(define prod
  (lambda (xs)
    (call/cc
     (lambda (cont)
       (let recur ((ys xs))
         (display "doing on ")
         (display ys)
         (display "\n")
         (cond
          ((null? ys) 1)
          ((zero? (car ys)) (cont 0))
          (else (* (car ys) (recur (cdr ys))))))))))

(display "----------\n")
(prod '(1 2 3 4 5))
(display "----------\n")
(prod '(1 2 0 4 5))

第一个例子调用call/cc之后在(cont 3)时,实际上调回了(+ 1 [])这个位置,所以没有(+ 2)这个操作。第二个例子则是来判断链表乘积时候如果链表中存在0元素的话就可以提前返回,所调回的位置则是在(lambda (xs) [])这里,这里直接返回0.


halting problem

停机问题学习cs的同学都不会陌生:是否能够写出一个函数will-stop?,然后对于任意函数f, will-stop?都可以判断出f是否会终止。这本书里面给出了一段比较有意思的程序,来说明我们实际上不能写出这个will-stop?函数。我们这里给出三个函数 1)will-stop? 2)eternity 3)last-try. 其中eternity是一个无限循环函数, 而last-try则是反证程序。

(define eternity
  (lambda (x)
    (eternity x)))

(define will-stop?
  (lambda (f) ...))

(define last-try
  (lambda (x)
    (and (will-stop? last-try)
         (eternity x))))

如果(will-stop? last-try) = #f, 那么说明last-try不会终止,但是(and #f ...)会立刻返回。而如果(will-stop? last-try) = #t, 那么说明last-try会终止,但是(and #t …)后半部分(eternity x)会一直循环下去。


Y combinator

书中引入ycombinator的例子比较有趣,要求我们编写一个计算列表长度的函数但是不允许define。我始终不太明白yc到底有什么现实用途,或许是可以体现某种运算或者是表达能力吧。

Step 1 我们可以通过枚举列表长度来完成,大致程序如下. 不过这里的问题是我们没有办法穷举长度,下面程序能处理的长度<=1. 如果>1的话那么就会调用eternity(露馅了!)

(lambda (xs)
  (cond
   ((null? xs)  0)
   (else
    (+ 1
       ((lambda (xs)
         (cond
          ((null? xs) 0)
          (else
           (+ 1
              (eternity (cdr xs))))))
        (cdr xs))))))

Step 2 上面程序其实是有个pattern的(lambda (xs) (cond …)). 我们抽取这个pattern出来。同样如果处理长度>1的列表也会陷入eternity.

((lambda (length)
   (lambda (xs)
     (cond
      ((null? xs) 0)
      (else (+ 1 (length (cdr xs)))))))
 ((lambda (length)
    (lambda (xs)
      (cond
       ((null? xs) 0)
       (else (+ 1 (length (cdr xs)))))))
  eternity))

Step 3 上面程序(lambda (length) … ) 其实也是一个pattern. 同样如果处理长度>1的列表也会陷入eternity当中。

((lambda (mk-length)
   (mk-length
    (mk-length eternity)))
 (lambda (length)
   (lambda (xs)
     (cond
      ((null? xs) 0)
      (else (+ 1 (length (cdr xs))))))))

Step 4 然后我们反思,其实我们为的就是不陷入eternity. 并且最终结果肯定不会陷入eternity, 所以这里eternity其实可以是任意函数,比如mk-length:). 同时我们将内部函数参数名字换为mk-length. 那么上面程序就变化称为

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (xs)
     (cond
      ((null? xs) 0)
      (else (+ 1 (mk-length (cdr xs))))))))

但是注意这里我们只能够处理长度==0的列表。>0的列表会出现运行时错误,发生在(mk-length (cdr xs))时候因为mk-length要求输入一个函数而不是列表。

Step 5 那么如果要处理>0的列表该怎么修正呢?我们这里可以在调用mk-length作用在(cdr xs)之前,将mk-length作用在eternity上,也就是如下代码. 但是这个代码只能处理<=1的列表

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (xs)
     (cond
      ((null? xs) 0)
      (else (+ 1 ((mk-length eternity) (cdr xs))))))))

Step 6 和Step 4对比一下,如果我们这里不调用eternity而是调用mk-length, 那么是否可以处理>1的列表呢? 答案是可以的。至此我们可以得到一个工作的函数。

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (xs)
     (cond
      ((null? xs) 0)
      (else (+ 1 ((mk-length mk-length) (cdr xs))))))))

Step 7 然后我们尝试简化上面的函数。我们尽量将mk-length抽离出来,其他部分形成一个单独的函数.

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (xs)
     (cond
      ((null? xs) 0)
      (else (+ 1 ((lambda (x)
                    ((mk-length mk-length) x))
                  (cdr xs))))))))

然后再将(lambda (x) …) 外提形成

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   ((lambda (length)
      (lambda (xs)
        (cond
         ((null? xs) 0)
         (else (+ 1 (length (cdr xs)))))))
    (lambda (x)
      ((mk-length mk-length) x)))))

Step 8 现在我们基本上可以看到(lambda (length) …) 部分和mk-length没有任何关系,所以我们可以尝试将(lambda (length) …) 部分外提

((lambda (fun)
   ((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (fun (lambda (x) ((mk-length mk-length) x))))))
 (lambda (length)
   (lambda (xs)
     (cond
      ((null? xs) 0)
      (else (+ 1 (length (cdr xs))))))))

(lambda (length) …) 后面部分是我们自己的逻辑,前面部分则是Y combinator.

Step 9 我们把Y-combinator部分用更短的字符来表示的话就是如下形式

(define Y
  (lambda (fun)
    ((lambda (f) (f f))
     (lambda (f) (fun (lambda (x) ((f f) x)))))))

#note: 注意fun函数只允许接收一个参数。

comments powered by Disqus