果壳中的延续

延续是一个强大的抽象。让我强调一下。延续是一个非常强大的抽象。为什么延续如此强大?这是因为延续只是一个函数^[1]，而函数具有可调用的危险属性。稍后再详细介绍。

那么，如果延续只是一个函数，那么为什么它如此特殊?

是的，延续就是一个函数。然而，让延续如此特别的是它所代表的东西。延拓表示计算的其余部分。(也就是计算上下文)。例如，考虑以下Scheme表达式:

  (add1 (* 3 x))
;       |_____|
;          |
;     computation
  (add1 [])
; |_______|
;     |
;  context

这里计算(* 3 x)具有上下文(add1 [])，其中[]表示一个洞。这个洞可以用计算的结果来填补。对于某些result，它被写成(add1 [result])。延续只是一个上下文的表示。例如，函数(lambda (result) (add1 result))表示上下文(add1 [])。

另一方面，计算(* 3 x)也可以表示为函数。它被表示为函数(lambda (context) (context (* 3 x)))，其中context是表示计算上下文的延续。需要注意的是，Haskell中的Cont类型代表计算本身，而不是其上下文。

好吧，但是是什么让延续如此强大呢?

正如我之前所说的，延续只是一个函数，而函数具有可调用的危险属性。特别是，函数可能不仅被调用一次，还可能被任意多次调用，甚至根本不被调用。这就是延续如此强大的原因。

(lambda (context)
  (context (* 3 x)))

如果我们多次应用context会怎样?可以使用它将结果翻倍，如下所示:

(lambda (context)
  (+
    (context (* 3 x))
    (context (* 3 x))))

如果给定的context是add1，那么这将产生(* 2 (add1 (* 3 x)))的答案。

另一方面，如果我们从未应用context呢?我们可以短路计算:

(lambda (context)
  (* 3 x))

这正是call/cc所做的。它忽略上下文，简单地返回一个答案，从而缩短了计算过程。例如，考虑:

(call/cc (lambda (short-circuit)
  (add1 (short-circuit (* 3 x)))))

这里，计算(* 3 x)具有上下文add1。然而，我们通过将call/cc(即short-circuit)的上下文应用于计算结果而缩短了计算。因此，我们忽略了原始上下文(即add1)并返回了一个答案。

call/cc是如何实现的?

现在我们理解了延续，让我们看一下Haskell中callCC的定义:

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
       -- |___________________________|
       --               |
       --               f
callCC f = Cont $ 'k -> runCont (f ('a -> Cont $ '_ -> k a)) k
       --        __|___            |______________________|
       --       |      |                       |
       --       (a -> r)                 short-circuit

需要注意的是，k是当前的延续(即整个表达式的延续)。f函数是callCC的唯一输入。它返回一个Cont r a，表示要执行的整个计算。我们将其应用于k来得到计算结果。

然而，在计算内部，只要我们想短路求值，就可以调用short-circuit。这个函数接受一个结果并返回一个忽略上下文的计算，并对结果应用当前continuation k，从而缩短了求值。

在JavaScript中把它们放在一起。

我们理解Scheme中的延续是什么。我们了解callCC在Haskell中的工作原理。让我们使用新学到的知识在JavaScript中实现continuation和callCC:

var Cont = defclass({
    constructor: function (runCont) {
        this.runCont = runCont;
    },
    map: function (f) {
        return new Cont(k => this.runCont(x => k(f(x))));
    },
    apply: function (g) {
        return new Cont(k => this.runCont(f => g.runCont(x => k(f(x)))));
    },
    bind: function (f) {
        return new Cont(k => this.runCont(x => f(x).runCont(k)));
    }
});
Cont.of = x => new Cont(k => k(x));
var callCC = f => new Cont(k => f(x => new Cont(_ => k(x))).runCont(k));
var log = prefix => x => console.log(prefix, x);
var add1 = x => Cont.of(x + 1);
callCC(short_circuit => short_circuit(15).bind(add1)).runCont(log("short"));
callCC(short_circuit => Cont.of(15).bind(add1)).runCont(log("no short"));
function defclass(prototype) {
    var constructor = prototype.constructor;
    constructor.prototype = prototype;
    return constructor;
}

注意，callCC可以用来实现goto。

callCC的强大功能允许您创建任意的控制流结构，如throw，协程甚至goto，如图所示:

var Cont = defclass({
    constructor: function (runCont) {
        this.runCont = runCont;
    },
    map: function (f) {
        return new Cont(k => this.runCont(x => k(f(x))));
    },
    apply: function (g) {
        return new Cont(k => this.runCont(f => g.runCont(x => k(f(x)))));
    },
    bind: function (f) {
        return new Cont(k => this.runCont(x => f(x).runCont(k)));
    }
});
Cont.of = x => new Cont(k => k(x));
var callCC = f => new Cont(k => f(x => new Cont(_ => k(x))).runCont(k));
var log = (x, ms) => new Cont(k => setTimeout(_ => k(console.log(x)), ms));
var omega = x => x(x); // This is a very dangerous function. Run `omega(omega)`.
callCC(omega).bind(cc => log("loop", 1000).bind(_ => cc(cc))).runCont(x => x);
function defclass(prototype) {
    var constructor = prototype.constructor;
    constructor.prototype = prototype;
    return constructor;
}

这段代码相当于:

forever:
    delay(1000);
    print("loop");
    goto forever;

因此，在使用延续时应该小心。

^[1]延续通常使用一级函数实现。然而，在像Scheme这样具有一等延续的语言中，延续和函数之间是有区别的。然而，即使continuation不是一个函数，它仍然像一个函数，因为它是可调用的。