# Continuation与CPS（Continuation Passing Style）的理解

Scheme是最早支持Continuation的语言，而Continuation对于初学者来说还是比较难以理解的，以下是我在学习TSPL中Continuation和CPS相关章节时的一些理解。更多Scheme、Continuation、CPS的相关知识到http://www.scheme.com/tspl4/ 查找学习。

## * Continuation

```(cons (exp) 'a)
```

```(call/cc
(lambda (k)
exp))
```

```(define product
(lambda (ls)
;显式调用break的时候，直接跳到这里，也就是返回(call/cc。。。)的返
回值
(call/cc
(lambda (break)
(let f ([ls ls])
(cond
[(null? ls) 1]
[(= (car ls) 0) (break "zero")]
[else (* (car ls) (f (cdr ls)))]))))))
;test
(product '(1 2 3 4 5))  => 120
(product '(7 3 8 0 1 9 5)) =>  "zero"
```

## * CPS

1. 正常函数的返回都隐含一个continuation，就是利用这个函数的返回值来 做的后续事情，而cps的本质就是将这个隐式的continuation显式的当做参 数传递进去，并在函数中完成应有的continuation并将最终结果返回。
2. 这跟尾递归似乎很像，在改造递归为尾递归的时候，就将当前状态通过accumulator汇集到函数内部的操作，当达到结束条件时返回汇集结果，而不必再返回来收集递归过程中的返回值。
3. cps似乎就是同样的道理，每次将continuation传递到内部进行操作的组合，当达到底部的时候直接将汇集的continuation的计算结果返回，而不必返回来再去计算每一步的continuation。

### ** TSPL的练习 3.4.3

Rewrite the following expression in CPS to avoid using call/cc.
```(define reciprocals
(lambda (ls)
(call/cc
(lambda (k)
(map (lambda (x)
(if (= x 0)
(k "zero found")
(/ 1 x)))
ls)))))
(reciprocals '(2 1/3 5 1/4))  (1/2 3 1/5 4)
(reciprocals '(2 1/3 0 5 1/4))  "zero found"
```

```(define reciprocals
(lambda (ls k)
(let ([break k])
(let f ([ls ls] [k k])
(cond
[(null? ls) (k '())]
[(= (car ls) 0) (break "zero!")]
[else (f (cdr ls)
(lambda (x)
(k (cons
(/ 1 (car ls))
x))))])))))
```

```(define map1
(lambda (p ls)
(if (null? ls)
'()
(cons (p (car ls))
(map1 p (cdr ls))))))
```

When one procedure invokes another via a nontail call, the called procedure receives an implicit continuation that is responsible for completing what is left of the calling procedure's body plus returning to the calling procedure's continuation. If the call is a tail call, the called procedure simply receives the continuation of the calling procedure.

```(define map1
(lambda (p ls k)
(if (null? ls)
(k '())
(map1 p
(cdr ls)
(lambda (v)
(cons (p (car ls)) v))))))
```

```(cons (p (car ls)) v)
=> (p (car ls)
(lambda (n)
(k (cons n v))))
```

```(define map1
(lambda (p ls k)
(if (null? ls)
(k '())
(map1 p
(cdr ls)
(lambda (v)
(p (car ls)
(lambda (n)
(k (cons n v)))))))))
```

```(define reciprocals
(lambda (ls k)
(let ([break k])
(map1
(lambda (x k)
(if (= x 0)
(break "error")
(k (/ 1 x))))
ls
k))))
```

```(reciprocals '(2 1/3 5 1/4) (lambda (x) x)) =>  (1/2 3 1/5 4)
(reciprocals '(2 1/3 0 5 1/4) (lambda (x) x)) => "error"
```

```(define reciprocals
(lambda (ls k)
(let ([break k])
(let map1 ([p (lambda (x k)
(if (= x 0)
(break "error")
(k (/ 1 x))))]
[ls ls]
[k k])
(if (null? ls)
(k '())
(map1
p
(cdr ls)
(lambda (v)
(p (car ls)
(lambda (n)
(k (cons n v)))))))))))
```

Continuation与CPS（Continuation Passing Style）的理解

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊