A page about call/cc 翻译

原文 : http://www.madore.org/~david/computers/callcc.html#rmk_contofcont
很好的一篇文章
翻译了一下来理解 call/cc

A page about call/cc 翻译

[TOC]

什么是 call/cc ? 这篇文章在讲什么 ?

call/cc 表示 call with current continuation (用当前延续调用)。 这是一个存在于某些编程语言中的函数。它究竟做了什么并不是一两句话就能说完的;事实上,我认为这是计算机科学史上最奇怪的发明之一。这篇文章将试图解释 call/cc 做了什么,它是什么意思,它为什么很有用以及它是如何工作的。

背景知识的需求相当广泛。为了完整的理解它,你需要对理论计算机科学和数理逻辑有透彻的了解——如果是真的那么不用讲你也知道它是什么。实际上大多数部分跟这些东西的关系很小或者根本没有。我始终试图让没有 Scheme 基础的人去理解但并不总是那么顺利。无论如何,就先把它当作一个包含了很多吓人的东西没有章法地组成的集合而不是一个系统的讲述call/cc的文章。如果对其中某些概念不是很理解,直接跳过,它们可能在后面的继续用不同角度的讲解中变得清晰明了。

开门见山的介绍

call/cc 是某种类似于 goto 指令的(或者说,一个 goto 指令的标签),但远远比它强大的东西。你可能看到这里开始头皮发麻了,毕竟 Dijkstra 曾说过,goto 是邪恶的,它不可能是一种强大的好东西——直到你对 call/cc 有更深的了解。

call/cc 代表了什么

它代表 call-with-current-continuation 。至少,这是 Scheme 中的官方名字 (虽然 call/cc 这个缩写更加普遍,但很多 Scheme 的实现中并没有采用这个缩写 )。这表示了 call/cc 获取了 当前延续 (current-continuation) 然后把它的参数应用到这个延续上(请先让我解释什么是延续 (continuation) 再来理解这句话)。

接下来我将用 call/cc 来代替 call-with-current-continuation

什么编程语言有 call/cc

Scheme 是拥有 call/cc 的语言中最权威的一门。官方的写法是 call-with-current-continuation ,虽然 call/cc 这种表示法也是半标准的。

Standard ML of New Jersey 也有 call/cc ,叫做 SMLofNJ.Cont.callcc (它与 Scheme 版的有一些区别,在于它并不能直接当作函数来调用而需要使用 SMLofNJ.Cont.throw , 但在本质上没有区别)。

Unlambda 语言也有 call/cc (仅仅是为了让这门语言更加蛋疼)。

在我的记忆中只有这些语言完全实现了 call/cc(已经过了快 20 年了) 。而很多其它语言 (例如 Java, CAML 或者 C++ )引入了一种更弱形式的 call/cc ,叫做“异常” (Exceptions) 。我们将会解释什么是异常以及为什么它们比真正的 延续 要弱。

在更底层的角度,一些操作系统实现了某种程度上的 call/cc ,Unix 中的 Solaris 系统支持了 getcontext() 函数,这个函数与 call/cc 有着很强的关联。

最后,我们可以在 Coq 中添加一个 call/cc 函数,而需要做的仅仅是输入 Axiom callcc : (P : Type) ((P -> EmptyT) -> P) -> P 。然而,因为 Coq 不是图灵完备的,这么做并不算真正的实现。

只向外的延续 :异常

异常在很多编程语言中都有体现,而且大多数人在理解异常方面没有任何障碍。我们接下来进行简单的复习。

一个异常发出了在程序执行的过程中出现了一些特殊的状况(一般是错误)的一个信号。发出信号这个过程我们成为引发(raise)异常(很多人都用“抛出(throw)异常”,但我更喜欢前面一种),当异常发生时,正常的程序执行过程终止。抛出异常所在的函数立即停止执行,并继续在其调用者中引发异常,直到整个程序结束或者这个异常被捕获(caught)。捕获这个异常需要把可能引起异常的代码放在特殊的代码块中;如果异常被引发,程序控制流将会转移到异常处理的部分并决定接下来做什么。在异常处理代码返回之后,正常的程序执行过程被恢复,就像代码被正常的终止一样。

异常本身与特定的数据相关联,而这个过程发生于异常的抛出;这些数据将在异常捕获时被利用。同一个代码块可能会引发不同的异常,它们会被以各自的方法处理掉。所以异常处理程序要对所有可能出现的异常进行处理,放置因为抛出的异常而终止整个程序。

异常最弱的形式是在词法作用域上的哪些,我们也通常叫做 block/break 异常。它们事实上并不是真正的异常而仅仅是一些标签和一些goto语句。这意味着只有在存在一个词法块 (lexically surrounding block) 时才能抛出这个异常。这些非常弱的形式有 C 语言的 return , break, continue 。然而 C 语言并没有带标签的break语句,所以这些“异常”被限制为一次一个的退出函数。除此之外,Java中的带标记的break语句也是“词法作用下的异常”的一个例子。

真正的异常(使用引发/抛出结构,而不是break这种)性质完全不同:任何一个代码块都可以引发一个异常,它并不需要嵌入在一个catch词法块里。这个异常将被最靠内的catch捕获,而后者是动态地包围在异常引发处地。我们称(这些动态作用域下的)异常沿着程序向上扩散 (沿着调用栈向上),从被调用者到调用者。需要提醒的重要的一点是,break 这样的词法作用异常是良好定义的并可以在编译期确定下来,而真正的异常是无法事先确定会被哪一个catch块捕捉的,引发异常的方式不同,异常被捕捉的时机也不同。

C 语言中的异常 : setjmp()longjmp()

在 POSIX 标准下的 C 语言定义了两个函数, setjmp()longjmp() ,而这也是 C 语言中最接近于 异常 和 延续 的东西。我们将会细致地观察这两个函数因为它们分别与 call/ccthrow 有着一些有趣的相似之处。

setjmp() 函数把所谓的 “栈的上下文 (stack context)” (这个称呼对于向外的延续而言并不是很合适)储存在一个传给它的变量里,叫做”跳转缓冲 (jump buffer)“,然后返回 0。longjmp() 函数拿到一个跳转缓冲和一个非零返回值;它让当前的执行点跳转到设置完跳转缓冲的setjmp()函数返回处,然后以相应的返回值返回。换句话说,longjmp() 永远不返回, 而它所做的事是让 setjmp() 函数返回;对于setjmp()函数,它会以两种方式返回:第一种是在第一次调用时返回一个 0 ,第二种是通过longjmp()返回一个非 0 的值。这种”一个函数让另一个函数返回一个特定的值“的调用是理解call/cc 的关键。

这些函数是用来实现 C 语言中异常的:异常处理部分通过setjmp()来实现,并通过longjmp()来抛出一个异常。这些函数事实上做的是:setjmp()把栈的大小储存在 跳转缓冲 中,而longjmp()来恢复它(当然这后面有着大量不可告人的黑魔法,尤其是在编译器那块,防止与编译器的优化产生冲突,同时在使用它们时还有着很复杂的限制。如果在异常处理块中调用了longjmp(),事情就会变得非常混乱)。

对于setjmp()longjmp()一个很重要的限制就是不能在调用setjmp()和调用longjmp()之间返回,比如下面的代码,就是不合法的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
#include <setjmp.h>

jmp_buf buf;

int
foo (volatile int n)
{
if ( setjmp (buf) )
{
printf ("%d\n", n);
return 0;
}
else
return 1;
}

int
main (void)
{
if ( foo (42) )
longjmp (buf, 1);
/* Yow! DEMONS are flying through my NOSE! */
exit (0);
}

虽然在实际上这份代码能跑,但一些更复杂的例子可能会痛苦地crash掉。

这个限制的主要原因就是setjump储存的是栈顶指针,所以只有在保证“调用了setjmp()之后,标记的当前指针以下的栈内容不变”的情况下setjmp()longjmp()才能正常工作,这也是为什么我们把它叫做“只向外的延续”(或者更准确的,向上,因为我们讨论的是动态作用域下的异常)。

call/cc 做了什么

call/cc 接受一个参数。这个参数本身是一个函数 f (因此我们的这门编程语言需要函数作为第一公民)。call/cc 把 f 应用 (apply) 到 当前延续 (current continuation) 。当前延续 是一个看上去像函数的东西(至少在 Scheme 版本是这样的,在 SML/NJ 版本下有一点区别但这并不重要)。如果把一个 延续 应用到一个值上(或者有人喜欢这样说:被以一个值抛出),它可以让(产生了这个延续的) call/cc 返回那个值。

我们给出一些例子,这些例子使用 Scheme 实现,但大家大概都能看懂。

考虑第一个例子: (call/cc (lambda (k) (k 42))) 。它把 call/cc 应用到函数 (lambda (k) (k 42)) 。因此,后面这个函数调用时的 k 就是 当前延续。但它的函数体是 (k 2) ,换句话说,这个延续被以 42 抛出,这让 call/cc 返回了 42 。因此,对整个的表达式求值会得到 42。

现在再考虑第二个例子 : (call/cc (lambda (k) (+ (k 42) 1729))) 。这里的函数对当前延续抛出了 42 ,并试图在此之后做点什么。但仅仅是这样做没有任何效果,因为一旦延续被 使用 (invoked) (通过对其抛出一个值),程序跳转 (精确地说,当前延续变成了这个被使用的延续)而原本要执行 (+ x 1729) 的延续丢失在了空间中(并被 gc 回收掉)。所以这个的结果仍然是 42。

在另一方面,考虑 (call/cc (lambda (k) 42)) 。这里应用到当前延续的函数是 (lambda (k) 42) 并没有使用到延续,它以“正常方法”返回了。在这种情况下所有对 call/cc 的实现都默认直接返回这个函数的返回值,但这并不是 call/cc 规定的,所以我们并不能把它当作 call/cc 的一个性质。

在下一个例子中,我们需要添加 Scheme 中两个新的元素 : (let ((variable value)) body) 用来在 body 中绑定一个新的变量,以及 (set! variable value) ,用来改变变量 variable 的值为 value 。所以我们的例子是: (let ((cont #f)) (call/cc (lambda (k) (set! cont k))) (cont #f)) 。我们这里有一个变量 cont :它的初始值无关紧要。我们对函数 (lambda (k) (set! cont k)) 调用了 call/cc ,拿到了延续 k 并绑定 cont。然后它以正常方式返回。我们忽略这个返回值然后我们对一个无关紧要的值调用了保存下来的延续 cont 。而当这个延续被调用时,它拥有一个能力,可以说,时光倒流,到call/cc 返回的那个时候,然后让它再一次返回,然后这个延续又一次被调用,使得 call/cc 又一次返回,从而不停地往复:我们陷入了 ”时间错位 (time warp)“ ,而我们地例子永无止境地跑了下去。

上面的变量有一件很有意思的事情:它的延续 逃逸 (escaped) 了。它跑到了作为 call/cc 的参数的函数 (也就是 (lambda (k) (set! cont k))) 的外面,这也恰是异常所做不到的。它(指 延续)被绑定到了变量 cont 上,并在当前的作用域 外界 使用了它的值。异常本身是无法实现这样一个无限循环的。

什么是延续 (Continuation) ?

是时候解释这次讨论的核心了,那就是 延续 (Continuation) 。

一个延续是 一个”等着一个值并进行利用这个值一些演算”的东西。这是一个很模糊的定义,但我认为它反而说的很清晰。对于计算中的每一个中间值,都有着相关的一个延续,这个延续代表着 “一旦知道当前计算的结果,下一步需要做的事情”。一个延续不是某种类似于函数的东西,接受一个值返回另一个;它仅仅接受一个值然后跟着它做一系列事情,并永远不会返回。

考虑下面的一个计算过程 : (* (+ 2 4) (+ 1 6))。这里参与的延续有很多。例如对于子计算过程 (+ 2 4) 的延续为 ” 拿到这个值,并保存下来,然后计算 1 + 6 并得到结果,然后把它与我们保存下来的值进行乘法,并结束“。而 (+ 1 6) 的延续为 ”获得当前的计算结果,把它与 6 相乘并得到结果,然后结束“。注意到的是 (+ 2 4) 的结果是 (+ 1 6) 的延续中的一部分,因为它的值已经被计算出来保存了下来。延续不是一种可以在编译时确定的静态的东西:它们是动态创建的作为程序执行过程的入口。

在程序的每一步,当一个值在被计算之时,有一个 当前延续 ,等待着这个值被抛给它(为什么我想到了等待着抛给自己的新鲜的肉的一只狮子?(笑))。当前延续将会进行剩下的计算,包括计算别的值和调用其它的延续。

可以说,如果我们相信基于栈的计算范式,那么延续对应着一个调用栈,即作为在程序的执行过程中一个给定值的调用者的嵌套函数的组成的序列,

一个程序语言中最基本的求值元素是:用一个等待着结果的 当前延续 cont 为一个表达式 exp 求值(更有可能的是在一个给定环境 env下,如果这个语言频繁地定义变量)。当我们说 ”用“ 一个延续来为一个表达式求值时,实际上是表示这个延续在等待着求值的结果。

一个重要的例子是如果一个延续的结果决定了(给,提供,或者说 是)另一个延续的结果,比如说一个函数中的组合指令中的最后一条,那么这个延续和另一个延续是相同的。

如果我们允许程序显式地操控延续(而这也是 call/cc 的核心/全部),我们正在 ”具体化“ 这些延续。如果它们能被像 比如整数 (它们可以作为函数的参数,返回值,传递给别的延续,等等)一样操控,那么我们就给了它们”一等公民“的身份。

所以,当我们为一个有延续 k (饥渴地等待着call/cc结果的当前延续)的 函数 f 应用了 call/cc 时,call/cc 将 f 应用到 k,而此时的当前延续也是 k 。注意到 k 是如何同时扮演了两个角色的:它作为传递给 f 的值,而同时又是当前函数调用的延续。

我们得以重新考虑之前的例子们。首先 (call/cc (lambda (k) (k 42))) 。这里, k 绑定到了等待着 call/cc 结束的当前延续。所以我们去求值 (k 42)k 被绑定到了之前我们说的那个延续,而 k 同时也是当前延续 (我们没有用到”call/cc正常结束返回最后一个式子的值“这个结论)而直接返回了 42,并使 call/cc 返回。第二个例子 (call/cc (lambda (k) (+ (k 42) 1729))) 。这里,我们有两个延续, k : 等待着 call/cc 结束,同时也等待 (+ (k 42) 1729)结束的延续;l :等待着 (k 42) 结束并得到这个值再把它与 1729 想加并抛给 k。但事实上延续 l 会一直等下去(直到被垃圾回收掉)因为 (k 42) 永远都不会结束,因为 k 是一个延续。 第三个例子 (call/cc (lambda (k) 42)) : 这一次我们必须得用到之前提到的双重角色的延续,因为 (lambda (k) 42) 调用时获得的延续和 call/cc 的延续使相同的。