简而言之的延续
延续是一种强大的抽象。让我强调一下。延续是一个非常强大的抽象。为什么延续如此强大?这是因为延续只是一个函数[1]并且“函数具有可调用的危险特性”。稍后再谈。
那么,如果延续只是一个函数,那么为什么它如此特别呢?
是的,延续只是一个函数。然而,让延续如此特别的是它所代表的东西。延续代表“计算的其余部分”(也称为计算上下文)。例如,考虑以下 Scheme 表达式:
(add1 (* 3 x))
; |_____|
; |
; computation
(add1 [])
; |_______|
; |
; context
这里的计算具有代表一个洞(* 3 x)
的上下文。可以用计算的结果来堵住这个洞。这是为一些写的。延续只是上下文的表示。例如,函数表示上下文。(add1 [])
[]
(add1 [result])
result
(lambda (result) (add1 result))
(add1 [])
另一方面,计算(* 3 x)
也可以表示为函数。它表示为函数(lambda (context) (context (* 3 x)))
,其中context
是表示计算上下文的延续。应该注意的是Cont
,Haskell 中的类型代表计算本身,而不是它的上下文。
好的,但是是什么让延续如此强大?
正如我之前所说,延续只是一个函数,“函数具有可调用的危险特性”。特别是,一个函数不仅可以被调用一次,也可以任意多次甚至从不被调用。这就是让延续如此强大的原因。
例如,考虑将上述计算(* 3 x)
表示为一个函数:
(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
但是,我们通过将(ie )的上下文应用于计算结果来缩短short-circuit
计算。因此,我们忽略了原始上下文(即add1
)并返回了答案。
如何call/cc
实施?
现在我们了解了延续,让我们看看callCC
Haskell 中的定义:
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
代表要执行的整个计算的 a。我们将其应用于k
获得计算结果。
short-circuit
但是,在计算内部,只要我们想短路评估,我们就可以调用。此函数接受一个结果并返回一个忽略其上下文并将当前延续应用于k
结果的计算,从而使评估短路。
将它们放在 JavaScript 中。
我们了解了 Scheme 中的延续。我们了解callCC
Haskell 的工作原理。callCC
让我们使用我们新发现的知识在 JavaScript中实现延续:
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 这样具有一流延续的语言中,延续和函数是有区别的。尽管如此,即使延续不是一个函数,它仍然像一个函数,因为它是可调用的。