柯里化的前生今世(七):first-class continuation

  1. 云栖社区>
  2. 博客>
  3. 正文

柯里化的前生今世(七):first-class continuation

何幻 2016-10-28 17:51:09 浏览1598
展开阅读全文

关于

在上一篇中,我们对比了动态作用域和词法作用域,并实现了一个支持词法作用域的Lisp方言。

我们看到,动态作用域和词法作用域的区别就在于“函数体在什么环境中被求值”。
动态作用域中的函数,在函数调用的环境中被求值。
而词法作用域中的函数,在被定义时的环境中求值。

从实现的角度来看,闭包就是一个数据结构,
它保存了函数的参数列表,函数体和被定义时的环境,并没有什么神秘的地方。

上一篇文章中,我们还对比了闭包与对象,它们都是有内部状态的实体。
引出了我们let over lambda的优雅断言。

Continuation

这一篇文章,我们将学习新的概念了,它不过是一个“坑”。
之所以这么说,一方面,这个概念极难理解,普通人被坑数月也不为过。
另一方面,它的表现形式好像是一个“坑”,它可以看成一个“有去无回”的单参函数。

1. 什么是后续的计算

我们先看一个小例子吧。

(+ 1 (* 2 3))

求值结果是7,它是怎么得来的呢?
是先求值(* 2 3)得到6,然后求值(+ 1 6)得到了7

值得注意的是,乘法那一步得到了运算结果,而加法那一步,使用了这个运算结果。

如果乘法得到的不是6,而是10
加法运算使用10这个运算结果,那么最终结果是多少?
(+ 1 10),即11了。

更进一步,如果乘法得到的不是6,而是x,最终结果是多少?
我们知道了,将会是(+ 1 x)

因此,一旦我们有了乘法的值,整个计算结果就知道了。
而当乘法值尚未确定的时候,我们只能用一个单参函数来表示“后续的计算”,

(define cont
  (lambda (x)
    (+ 1 x)))

计算完乘法的值后,只要调用这个单参函数,就能拿到整个程序的计算结果了。
因此,我们称这个单参函数为乘法表达式的continuation。

2. 未来要做的事情是一个单参函数

如图,我们不但关心表达式的值是怎样得出来了,
还关心表达式的值是怎样被使用的,
于是,每个表达式都对应了一个“它的”continuation。

一旦我们用表达式的值,填充了它的continuation,整个程序就算跑完了。
程序的未来,就是这个单参函数。

call-with-current-continuation

在所有语言中,我们都可以引入continuation这个概念,
但是Lisp更强大,它们的continuation是first-class的。

1. first-class

什么叫first-class的呢?
某个东西是first-class的,就是说这个东西可以当做函数的参数,也可以当做函数的返回值。

有了高阶函数之后,函数就是first-class的了。
现在我们来看continuation变成first-class会有什么好玩的事情发生。

2. 例子

Racket提供了call/cc,来拿到(call/cc ...)表达式本身的continuation,
即,current continuation,看一个例子吧。

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

结果是3,其中cont就是(call/cc ...)这个表达式的continuation,
不就是这个函数吗?

(define cont
  (lambda (x)
    (+ 1 x)))

是的,因此,(cont 2)的结果就是整个计算结果,(cont 2)得到3

3. 语法规则

(1)call/cc接受一个单参函数fn作为参数。
这里fn指的就是上面的(lambda (cont) ...)
(2)求值(call/cc ...)表达式,会使用(call/cc ...)表达式的continuation调用fn
因此,fn的形参cont就是(call/cc ...)表达式的continuation。
(3)另外,我们规定,fn的continuation就是call/cc的continuation。
即,如果fn中没有调用cont,则(call/cc ...)的值就是函数的返回值。

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

结果也是3

4. 这有何难?

可能看了上面的例子,会对continuation付之一笑,这还要坑几个月?怎么可能?
那好吧,我们看一个稍微复杂点的例子。

((call/cc (lambda (cont) cont)) (lambda (x) "hi"))

谁能告诉我,结果为什么是"hi"?

实际上,执行过程是这样的:
(1)这是一个函数调用表达式,形如(f a),因此先求值f,再求值a
(2)求值(call/cc (lambda (cont) cont)),因为cont没有被调用,
所以,(call/cc ...)表达式的值就是cont了,f的值是cont了。
(3)(lambda (x) "hi")求值为一个函数对象#<procedure>
a的值是#<procedure>了。
(4)开始用cont调用这个函数对象,
注意了啊。。因为cont(call/cc ...)表达式的continuation,
会导致程序从(call/cc ...)求完值后的位置再次执行,
即,看起来好像(call/cc ...)又返回了。
并且,(call/cc ...)的值就是这个函数对象。
因为用谁调用cont(call/cc ...)的值就是谁嘛。
(5)(call/cc ...)求完值后要做什么呢?那就是第(3)步了啊,
(lambda (x) "hi")又求值为一个函数对象#<procedure>
a的值是#<procedure>了。
(6)然后进行函数调用了,((lambda (x) "hi") (lambda (x) "hi"))
结果为"hi"。

5. 我彻底凌乱了

是不是有些凌乱啊,下面这个阴阳谜题难度更大。

(let* [(yin ((lambda (foo) (newline) foo)
             (call/cc (lambda (bar) bar))))
       (yang ((lambda (foo) (display "*") foo)
              (call/cc (lambda (bar) bar))))]
  (yin yang))

结果会无限输出,
先输出一个星号,换行输出两个星号,换行输出三个星号,等等。

这里把值得注意的几个点,重点表述一下,
(1)什么时候cont被调用,就相当于对应于这个cont(call/cc ...)表达式返回了,
并且该(call/cc ...)表达式的值,就是用来调用cont的值,
即,(cont v)(call/cc ...)的值就是v
(2)不同位置,或者相同位置不同时间调用的(call/cc ...)产生的continuation是不同的,不同的cont被调用,会返回到“历史上”的某个位置。

call/cc的威力

说了这么多call/cc,有什么卵用?

我们知道很多动态语言有generator这个概念,
伴随generator有一个yield,很诡异。
它居然可以让一个函数返回多次,没错,它无非就是continuation嘛。

1. python中的generator

def gen(x):
    yield x
    yield x+1
    yield x+2

iter=gen(1)
print(iter.next())  #1
print(iter.next())  #2
print(iter.next())  #3

我们看到gen()返回一个迭代器iterator
不断的调用next()会导致genyield位置继续向下执行。

相似的例子,可参考ES6的generatorRuby的Fiber

2. 用call/cc实现yield

(define (gen x)
  (define k-body #f)
  (define k-yield #f)
  
  (define (yield x)
    (call/cc (lambda (k2)
               (set! k-yield k2)
               (k-body x))))
  
  (lambda ()
    (call/cc (lambda (k1)
               (if (eq? k-body #f)
                   (begin
                     (set! k-body k1)
                     (yield x)
                     (yield (+ x 1))
                     (+ x 2))
                   (k-yield))))))

(define iter (gen 1))
(iter)  ;1
(iter)  ;2
(iter)  ;3

后续文章我们还会发现,我们可以定义宏(macro),让上述表达方式更简练。
宏,才是Lisp语言的精髓。

3. 用宏做语法糖

(make-generator (gen x y)
                (yield x)
                (yield y)
                (+ x y))

(define iter (gen 1))
(iter)  ;1
(iter)  ;2
(iter)  ;3

其中,make-generator是一个宏,按下面的方法定义,感兴趣的可以一试。

(define-syntax make-generator
  (lambda (form)
    (syntax-case form ()
      [(keyword (name ...) . body)
       (syntax-case (datum->syntax #'keyword 'yield) ()
         [yield
          #'(define (name ...)
              (define k-body #f)
              (define k-yield #f)
              (define (yield . args)
                (call/cc (lambda (k2)
                           (set! k-yield k2)
                           (apply k-body args))))
              (lambda ()
                (call/cc (lambda (k1)
                           (if (eq? k-body #f)
                               (begin
                                 (set! k-body k1) . body)
                               (k-yield))))))])])))

下文

本文介绍了continuation,还介绍了Lisp中的first-class continuation,
最后,用call/cc实现了yield
然而,只停留在使用层面的话,神秘感是无法抹除的,
下一篇文章,我们来实现call/cc,你准备好了吗?

参考

Python: Iterators & Generators
Continuation
The Scheme Programming Language, 4th Edition
Practical Common Lisp

网友评论

登录后评论
0/500
评论
何幻
+ 关注