Продолжения в двух словах

Продолжения — мощная абстракция. Позвольте мне подчеркнуть это. Продолжения — это чрезвычайно мощная абстракция. Почему продолжения так сильны? Это потому, что продолжение — это просто функция^[1], а функции имеют опасное свойство вызываться. Подробнее об этом позже.

  (add1 (* 3 x))
;       |_____|
;          |
;     computation

  (add1 [])
; |_______|
;     |
;  context

С другой стороны, вычисление (* 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 (то есть 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, который представляет собой все вычисление, которое необходимо выполнить. Мы применяем его к 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, есть различие между продолжениями и функциями. Тем не менее, даже если продолжение не является функцией, оно все равно похоже на функцию в том смысле, что оно вызывается.