[原]重新开始学习Scheme（7）：续延的例子

先说一些题外话。

关于函数式编程，这是Lisp 最常见的编程范式，它是构建在计算的基础上的。而另一个派别——命令式编程（包括面向过程范式、面向对象范式等等）则是构建在机器模型和汇编语言的基础上的。那么，函数式编程的特征有哪些呢？通常说来，具备下面特征的编程范式就可以说是函数式编程：

• 声明式的。一个程序/过程更像是对问题的描述，或者对解决方法的描述，而不是如何进行一步步的计算。
• 无（或者最小化）副作用的。所谓副作用（side-effect）指的是除了返回的计算结果之外，还修改了其他的对象。C库函数中strcat()函数就是典型具有副作用的函数。
• 如果有副作用，这个副作用仅仅作用于唯一属主为该函数的对象。例如一个函数返回一个新构造的对象，该对象被修改了。
• 计算结果只与输入有关，与执行次数无关。无论执行多少次，同样的定义域对应的值域完全一样
• 返回值可被安全地修改

至于闭包（closure），在Lisp中可以说无处不在，因此要特别注意。所谓闭包，就是一个计算过程以及其所使用的计算环境所构成的东西。

在“[原]重新开始学习Scheme（4）：难学却重要的Scheme特性”中提到了续延（continuation）以及call/cc，然而里面有很多分析并不是可以形式化的，因此，很难作为普适的分析方法。这次让通过对“ [原]重新开始学习Scheme（4）：难学却重要的Scheme特性 ”中的例子重新进行说明，来看看比较形式化的方法。

首先回忆一下，continuation是指某个计算的未来路径。它是一个过程（procedure），而过程又是闭包（closure），因此continuation就是closure。

来看看下面的表达式

(if (null? x) (quote ()) (cdr x))

假定求值的顺序为从右到左，那它所包含的continuation有：

1. 等待x的continuation
2. 等待cdr的continuation
3. 等待 x的continuation
4. 等待 null?的continuation
5. 等待 (null? x)的continuation
6. 等待 (if (null? x) (quote ()) (cdr x))的continuation

根据定义，第一个continuation可以写成：

(lambda (v1) (if (null? x) (quote ()) (cdr v1)))

一旦x值确定之后，就可以将该continuation应用到x的值上：

((lambda (v1) (if (null? x) (quote ()) (cdr v1))) x)

而第二个continuation在第一个continuation的基础上，等待cdr的值：

((lambda (v2) (if (null? x) (quote ()) (v2 v1))) cdr)

以此类推，后面的continuation如下：

((lambda (v3) (if (null? v3) (quote ()) (v2 v1))) x)
((lambda (v4) (if (v4 v3) (quote ()) (v2 v1))) null?)
((lambda (v5) (if v5 (quote ()) (v2 v1))) (null? x))
((lambda (v6) v6) (if v5 (quote ()) (v2 v1)))

也许这个例子比较复杂一些，那我们还是看看最简单的这个吧：

(/ (- x 3) 10)

在求出(- x 3)的值val之后，其后续计算为：

(/ val 10)

那么该continuation就可以写成：

(lambda (val) (/ val 10))

将(- x 2)的值作为该continuation的参数，便可以得到结果了。

再说一个题外话：这里“-”操作被隐式地传递了一个continuation，即(lambda (val) (/ val 10))。如果将continuation显式传递的话，那就是另外一个大话题：CPS（Continuation Passing Style）。

再回忆一下call-with-current-continuation，它捕获当前的continuation，并执行其函数参数。该函数参数是一个函数，接受continuation为参数并执行相应的操作。因此，call/cc的含义为：捕获当前的continuation，然后执行相应的操作。

在上面的例子中，val就是当前continuation所期待的值，用call/cc来改写，则是如下形式：

(/ (call/cc
    (lambda (cc)
      (cc (- x 3))))
   10)

因此，可以将对call/cc的调用视为后续计算所需要的val，然后将该continuation作为call/cc的函数参数的参数，执行(cc (- x 3))操作。

因此，对于call/cc操作，可以分为两步来分析：

1. 用val替代call/cc调用——确定continuation是什么
2. 使用该continuation做什么

此处需要特别注意的是：在第二步中，一旦将该continuation应用之后，该continuation后面的所有continuation都会被抛弃，表达式立即返回。因此捕获的continuation又被称为逃逸函数（escape procedure）。在上面的例子中，如果(cc (- x 3))之后还有任何后续操作，这些操作都将被忽略。

根据这个规则，可以将上面的形式反推回去。当前的continuation是：

(/ val 10)
;; 因为continuation是procedure，因此应当使用lambda来表示：
(lambda (val) (/ val 10))

对当前continuation做什么：

(lambda (cc) (cc (- x 3)))
;;由于已经获得了当前的continuation，因此将该函数应用于当前的continuation，如下：
((lambda (cc) (cc (- x 3))) (lambda (val) (/ val 10)))

有了这个分析的基础，现在来看看使用这两个步骤来分析使用call/cc的函数。

(call/cc
  (lambda (k)
    (* 5 4)))
;; CC:
(define cc1 (lambda (v) v))
;; What to do with CC:
((lambda (cc) (* 5 4)) cc1)

(call/cc
  (lambda (k)
    (* 5 (k 4))))
;; CC:
(define cc2 (lambda (v) v))
;; What to do with CC:
((lambda (cc) (cc 4)) cc2)

(+ 2
   (call/cc
     (lambda (k)
       (* 5 (k 4)))))
;; CC:
(define cc3 (lambda (v) (+ 2 v)))
;; What to do with cCC:
(cc3 4)

这三个相对简单些，因此不做说明。

(define the-continuation #f)
(define (test)
  (let ((i 0))
    (call/cc (lambda (k) (set! the-continuation k)))
    ( i (+ i 1))
    i))
;; CC:
(define cc4
  (let ((i 0))
    (lambda (v)
      v
      ( i (+ i 1))
      i)))
;; What to do with CC:
((lambda (cc)
  (set! the-continuation cc)) cc4)
;; Testing
(cc4 0)
(cc4 0)
(test)
(the-continuation 0)
(the-continuation 0)

此处，cc4引用了一个自由变量i。由于所有对test这个closure的调用（而不是每个closure的示例）都共享变量i，因此，i在cc4中也应当是一个共享变量。因此，cc4不应该是这样：

(define cc4
  (lambda (v)
    (let ((i 0))
      v
      (set! i (+ i 1))
      i)))

下面这个例子就复杂一些：

(let ([x (call/cc
          (lambda (k) k))])
  (x (lambda (ignore) "hi")))
;; CC:
(define cc5
  (lambda (v)
    (let (( x v))
      (x (lambda (ignore) "hi")))))
;; What to do with cc:
((lambda (cc)
  (cc (lambda (ignore) "hi")))) cc5)
;; Testing
(cc5 (lambda (i) "hI"))

关键在于“what to do with cc”部分。因为(lambda (cc) cc)只是返回cc，而且是在let中，因此需要对cc做什么就变成了(cc (lambda (ignore) "hi"))。同样：

(((call/cc
   (lambda (k) k))
  (lambda (x) x))
 "HEY!")
;; CC
(define cc6
  (lambda (v)
    ((v (lambda (x) x))
     "HEY~!")))
;; What to do with cc:
((lambda (cc) (cc (lambda (x) x))) cc6)

在下面这个例子中：

(define retry #f)
(define factorial
  (lambda (x)
    (if (= x 0)
        (call/cc (lambda (k) (set! retry k) 1))
        (* x (factorial (- x 1))))))
;; CC:
(define f
  (lambda (x)
    (lambda (v)
      (if (= x 0)
          v
          (* x ((f (- x 1)) v))))))
(define cc7 (f 4))
;; What to do with cc:
((lambda (cc) (set! retry cc) ((cc 1)) cc7)
;; Testing
(retry 1)
(retry 2)
(retry 5)

要注意当x不等于0的情况。此时由于 (f (- x 1)) 返回的是一个continuation，因此，需要将其应用到v上。另外就是call/cc捕获到当前的continuation是将f应用于某个数的结果。

对于下面这个函数：

(define product
  (lambda (ls)
    (call/cc
      (lambda (break)
        (let f ([ls ls])
          (cond
            [(null? ls) 1]
            [(= (car ls) 0) (break 0)]
            [else (* (car ls) (f (cdr ls)))]))))))

由于用到了命名let，不是很直观，因此，首先将其改成如下形式：

(define product-variant
  (lambda (ls)
    (call/cc
      (lambda (break)
          (cond
            [(null? ls) 1]
            [(= (car ls) 0) (break 0)]
            [else (* (car ls) (product (cdr ls)))])))))

其continuation如下：

;; CC:
(define cc8 (lambda (v) v))
;; What to do with cc:
(define (p-1 ls)
  (lambda (cc)
    (cond
      [(null? ls) 1]
      [(= (car ls) 0) (cc 0)]
      [else (* (car ls)
               [(p-1 (cdr ls)) cc])])))
((p-1 '(1 2 3 0 5)) cc8)
((p-1 '(5 4 3 2)) cc8)

由于p-1是一个以cc为参数的函数，因此，(product (cdr ls))就需要转换成[(p-1 (cdr ls)) cc]