The Little Schemer

The goal of this book is to teach the reader to think recursively. Our first task is to decide which language to use to communicate this concept. There are three obvious choices: a natural language, such as English; formal mathematics; or a programming language. Natural languages are ambiguous, imprecise, and sometimes awkwardly verbose. These are all virtues for general communication, but something of a drawback for communicating concisely as precise a concept a s recursion. The language of mathematics is the opposite of natural language: it can express powerful formal ideas with only a few symbols. Unfortunately, the language of mathematics is often cryptic and barely accessible without special training. The marriage of technology and mathematics presents us with a third, almost ideal choice: a programming language. We believe that programming languages are the best way to convey the concept of recursion. They share with mathematics the ability to give a formal meaning to a set of symbols. But unlike mathematics, programming languages can be directly experienced-you can take the programs in this book, observe their behavior, modify them, and experience the effect of these modifications.

书中给出的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工作起来像是一个collector，把所有数据/状态不断保存起来，在结束状态的时候调用，然后不断沿着创建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.

偏序函数在这里的意思是，对于函数f(x)来说，不是所有的x都可以得到一个y（这个函数根本就不会有任何返回）。比如类似eternity这样的函数：

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

这个函数对所有的x都不会返回。或者是下面类似跳转程序，如果调用的是 (jump 5 0 vec)的话，那么就只能一直循环了。

(define (nth n l)
  (if (or (> n (length l)) (< n 0))
    (error "Index out of bounds.")
    (if (eq? n 0)
      (car l)
      (nth (- n 1) (cdr l)))))

(define (jump a p vec)
  (let ((x (nth p vec)))
    (print "trying " x)
    (cond
     ((eq? x a) a)
     (else
      (jump a x vec)))))

(define vec '(7 0 3 4 5 6 7 1))
(print (jump 5 2 vec))

停机问题学习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)会一直循环下去。

作者在这里还附带了一句："It makes will-stop? the first function that we can describe precisely but cannot define in our language. Thank you Alan Turing and Kurt Godel". 感觉这句话有点哥德尔不完备性的意思。

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