continuation 的支持

如前文讨论的通过 CPS 可以实现一定程度的 continuation,还有不少语言内置了对 continuation 的支持。在 imperative programming 的世界里,乃至一般性 functional programming 的世界里,函数的基本抽象仍然是主流行为,其实现主要还是依赖调用和返回两个概念,而 continuation 的应用与此是背道而行:与其返回比如执行下一步要干啥,我们比较下面的一个过程:

val b: A = f (a)
val c: C = g (a, b)
val d: D = h (a, b, c)

如果需要改写成为 CPS 的话则为

def f (a: A) (bb: B => Unit) : Unit {
  // do something about a and compute b
  bb (b)
}
def g (a: A, b: B) (cc: C => Unit): Unit {
  // do something about a and b and compute c
  cc (c)
}
def h (a: A, b: B, c: CC) (dd: D => Unit) {
  // do something about a, b and c and compute d
  dd (d)
}

f (a) {b =>
  g (a, b) { c =>
    h (a, b, c) { d =>
      Unit
    }
  }
}

这个过程可以用函数调用本身来书写,但是的确没有必要编译成为函数的调用返回这种形式。因此一种合理的策略是以某种形式暗示编译器这种代码应该编译成为另外一种样子。另外一个问题是 CPS 本身是传染性的,在一个 CPS 不占主导的程序里面如何将这段 CPS 与其他的代码交互(获得输入,产生输出),这也是一个难的问题。事实上,scala 为了解决这个问题使用了 delimited continuation,除了我们需要通过 -P:continuations:enable 打开编译器插件以外,我们还需要使用 scala.util.continuations._ 提供的 DSL。

这个 DSL 中重要的是 reset/shift 这两个东西,reset 这个部分标志着 CPS 的开始,其中有若干 shift 产生的对象,每个这个对象都有点内外颠倒的感觉,因为 shift 本身对应的是 continuation 部分,也就是说其中有个函数表示的是结束后应该干啥,如何产生这个函数的输入却是在 reset 里面实现的:

reset {
  shift { f: (Int => Int) => f(2)
  } + 1
}

这个例子我们看到 shift 产生的对象如果记为 r,则 r + 1 表示的是一个 Int => Int 的函数,这正是 f 的定义,因此这个 continuation 对应的结果就是 2 + 1 = 3。为了将这个 reset 块中的 shift 分离出去,写成“函数”形式以便重用,scala 提供了 @cps/@cpsParam 这个 annotation:

def bar (n: Int) : Int @cps[Int] = shift {f: (Int => Int) => f(2)} + n
def foo (a: Int) = reset { bar(a) }

值得注意的是 reset 中的 shift 具有嵌套性质,shift 对应的那个 f 其实是将 reset 中它之后的所有部分当作一个 closure,因此之后的 shift 就被嵌套在之前的 shift 里面形成了前面我们看到的 CPS 的形式。如此 API 究竟有什么好处呢?有空继续看几个库…

与 scala 不同的是 C++ 并没有提供 continuation 的支持,有人试图为 C++ 提供类似的库,还有人说 boost.phoenix 里面有(即便没有使用 C++11 的 lambda)粗看一下 phoenix 的介绍里面确实是说为 C++ 提供了 functional programming,不知道里面哪个部分实现了 CPS,记得 boost.spirit 用它的 lambda 的… Java 里面尙没有把函数当成 first-type class,不知道到 JDK 8 是否会出现一些这方面的东西。

——————
And said unto them, I see your father’s countenance, that it is not toward me as before; but the God of my father hath been with me.

Advertisements
continuation 的支持

一个有关“continuation 的支持”的想法

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s