Как применить callcc, чтобы обеспечить механизм продолжения escape для использования с монадой продолжения

Я пытаюсь реализовать монаду продолжения в Javascript для обработки стиля передачи продолжения и асинхронных потоков управления. Вот моя монада продолжения обучения:

// auxiliary functions

const log = prefix => x => console.log(prefix, x);
const addk = x => y => k => setTimeout((x, y) => k(x + y), 0, x, y);
const inck = x => k => setTimeout(x => k(x + 1), 0, x);
const sqr = x => x * x;


// continuation monad

const cont = {
  of: x => k => k(x),

  map: ftor => f => k => ftor(x => k(f(x))),

  ap: ftor => gtor => k => ftor(x => gtor(f => k(f(x)))),

  chain: ftor => mf => k => ftor(x => mf(x) (k)),

  callcc: f => k => f(x => () => k(x)) (k)
};


// map a normal, unary function with an asynchronous function:

cont.map(inck(9)) (sqr) (log("map"));


// chain two asynchronous CPS computations with an asynchronous binary CPS function

const comp1 = cont.map(inck(4)) (sqr);
const comp2 = cont.map(inck(9)) (sqr);

cont.chain(comp1) (x => cont.chain(comp2) (y => addk(x) (y))) (log("chain"));

Помимо cont.ap, чья выгода не раскрывается мне, все работает отлично.

Теперь я хотел бы подражать throw / catch Механизм синхронного управления потоками в Javascript. callcc кажется подходящим, потому что он обеспечивает механизм продолжения Escape для использования с монадами продолжения, как указано на http://hackage.haskell.org/.

Но я не могу понять, как подать заявку callcc и я не нашел подходящего источника, который описывает такое приложение.

Источник

1 ответ

Решение

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

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

Итак, если продолжение - это просто функция, то почему оно такое особенное?

Да, продолжение - это просто функция. Однако то, что делает продолжение таким особенным, это то, что оно представляет. Продолжение представляет "остальную часть вычислений" (или контекст вычислений). Например, рассмотрим следующее выражение схемы:

  (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 (т.е. short-circuit) к результату расчета. Следовательно, мы игнорировали исходный контекст (т.е. add1) и вернул ответ.

Какcall/ccреализованы?

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

Собираем все это вместе в JavaScript.

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

Источник
Другие вопросы по тегам