4

継続渡しスタイルと非同期制御フローを処理するために、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、その利点は私には明らかになりませんが、すべて正常に動作します。

ここで、Javascript の同期制御フローのthrow/メカニズムを模倣したいと思います。http://hackage.haskell.org/に記載されているように、継続モナドで使用するためのエスケープ継続メカニズムを提供するため、適合しているようです。catchcallcc

しかし、申請方法がcallccわかりませんし、そのような申請について説明している適切な情報源も見つかりませんでした。

4

1 に答える 1

6

一言で言えば継続

継続は強力な抽象化です。それを強調させてください。継続は非常に強力な抽象化です。なぜ継続はそれほど強力なのですか？継続は単なる関数[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)))である関数として表されます。Haskell の型は、そのコンテキストではなく、計算自体を表すcontextことに注意してください。Cont

わかりましたが、継続がそれほど強力な理由は何ですか?

前に述べたように、継続は単なる関数であり、「関数には呼び出し可能であるという危険な性質があります」。特に、関数は 1 回だけでなく、任意に何度も呼び出されるか、まったく呼び出されないことさえあります。これが継続を非常に強力にするものです。

たとえば(* 3 x)、関数として表された前述の計算を考えてみましょう。

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

context複数回申し込んだ場合はどうなりますか？次のように、結果を 2 倍にするために使用できます。

(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)には context があります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実行する計算全体を表すa を返します。これを適用してk計算結果を取得します。

ただし、計算内ではshort-circuit、評価を短絡したいときはいつでも呼び出すことができます。この関数は結果を受け取り、そのコンテキストを無視して現在の継続kを結果に適用する計算を返し、それによって評価を短絡します。

JavaScript ですべてをまとめます。

Scheme の継続とは何かを理解しました。callCCHaskell でどのように動作するかを理解しました。新たに発見した知識を使用して、継続をcallCCJavaScript で実装しましょう。

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次のような任意の制御フロー構造を作成できます。throwgoto

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 のようなファーストクラスの継続を伴う言語では、継続と関数が区別されます。それにもかかわらず、継続が関数でなくても、呼び出し可能であるという点では関数に似ています。

于 2016-10-03T17:26:47.573 に答える