Continuation Passing Style

https://cgi.soic.indiana.edu/~c311/lib/exe/fetch.php?media=cps-notes.scm

(f (g (h i) j) k) 哪部分先求值? (h i), 然后(g (h i) j)才能求值.

(f (g (h i) (j k)))呢? scheme没有规定求值的顺序, 所以可能是(h i)或者(j k).

假设有(h i (lambda (hi) ...), 其中hi是(h i)求值的结果, 那么我们重写(f (g (h i) (j k)))成下面的形式: (h i (lambda (hi) (f (g hi (j k))))), 其中(lambda (hi) (f (g hi (j k))))就是一个continuation(有些地方译成延续?).

CPS(https://en.wikipedia.org/wiki/Continuation-passing_style)

以rember为例

以CPS形式写一个rember函数.

先看一个最简单形式.

(define rember8
  (lambda (ls)
    (cond
     [(null? ls) '()]
     [(= (car ls) 8) (cdr ls)]
     [else (cons (car ls) (rember8 (cdr ls)))])))

(rember8 '(1 2 3 8 4 5))

(1 2 3 4 5)

第一个原则

当我们在需要转成CPS形式的代码中, 看见lambda, 都需要给它添加一个参数, 然后相应的处理body.

(lambda (x ...) ...) => (lambda (x ... k) ...^)

第二个原则

不要漏掉每一个small stuff, 由rember到rember8*, 我们需要从cond开始, 每行仔细考虑, 进行改动. 尤其注意else部分, 我们将构建结果的过程全部放进了最后这个continuation, 数据存储本身存在这个闭包中, 同时要注意k对构造出的结构的应用.

(define rember8*
  (lambda (ls k)
    (cond
     [(null? ls) (k '())]
     [(= (car ls) 8) (k (cdr ls))]
     [else (rember8* (cdr ls)
                      (lambda (x) (k (cons (car ls) x))))])))

(rember8* '(1 2 3 4 8 4 5) (lambda (x) x))

(1 2 3 4 4 5)

(lambda (x) x)就是”identity function”.

现在观察rember8*, 首先, 所有的分支调用, 都是尾递归.

Small stuff is stuff we know will terminate right away.

再次, 所有的参数, 都是small stuff. =, car, cdr, cons以及lambda都是small stuff, lambda总是small stuff.

上面被CPSed的程序, 求值时做的所有工作, 就是把continuation变成数据结构. 观察(rember8* '(1 2 8 3 4 6 7 8 5) (lambda (x) x))的求值过程:

ls | k |

:— |:— |

‘(1 2 8 3 4 6 8 5) | (lambda (x) x) = id |

‘(2 8 3 4 6 8 5) | (lambda (x) (id (cons (car 1) x))) = k2 |

‘(8 3 4 6 8 5) | (lambda (x) (k2 (cons (car 2) x))) = k3 |

开始求值(k3 (cdr ls)) |

(k3 ‘(3 4 6 8 5) = (k2 (cons 2 ‘(3 4 6 8 5)) |

(k2 ‘(2 3 4 6 8 5) = (id (cons 1 ‘(2 3 4 5 6 8 5))) |

(rember8* '(1 2 8 3 4 6 8 5) (lambda (x) x))

(1 2 3 4 6 8 5)

multirember

(define multirember8
  (lambda (ls)
    (cond
     [(null? ls) '()]
     [(= (car ls) 8) (multirember8 (cdr ls))]
     [else
      (cons (car ls) (multirember8 (cdr ls)))])))

(multirember8 '(1 2 8 3 4 6 8 5))

(1 2 3 4 6 5)

开始CPSing~, 应用第一原则, 加参数k, 应用第二原则, 对各个分支应用调整.

(define multirember8*
  (lambda (ls k)
    (cond
     [(null? ls) (k '())]
     [(= (car ls) 8) (multirember8* (cdr ls)
                                    (lambda (x)
                                      (k x)))]
     [else
      (multirember8* (cdr ls)
                     (lambda (x)
                       (k (cons (car ls) x))))])))

(multirember8* '(1 2 8 3 4 6 8 5) (lambda (x) x))

(1 2 3 4 6 5)

(lambda (x) (k x))具体做什么, 它的作用是将接收到的东西不做处理, 传给k, 表示跳过这个分支(忽略(car ls), 将递归上层的逻辑传到下层去.

(lambda (x) (M x) = M, 如果x在M中不是自由变量, 且M能保证终止. 据此, 化简上面的程序, 得到下面的最终形式.

(define multirember8**
  (lambda (ls k)
    (cond
     [(null? ls) (k '())]
     [(= (car ls) 8) (multirember8** (cdr ls) k)]
     [else
      (multirember8** (cdr ls)
                     (lambda (x)
                       (k (cons (car ls) x))))])))

(multirember8** '(1 2 8 3 4 6 8 5) (lambda (x) x))

(1 2 3 4 6 5)