こんにちは、びしょ〜じょです。 気づけば2020年になってました。 2020年ってなんだ? SFですか?


1. はじめに - Algebraic Effectsおさらい

本日はshallow effect handlerを実装します。 まず shallow effect handlerとはなんでしょう? 最初にalgebraic effects and handlersについておさらいします。 あれとかこれとかそれとかを読んでおさらいしてください。

こんにちは、びしょ〜じょです。ここしばらく20行/日くらいしかコード書いてません。いやもっと少ないかも…。いや研究してますんで! いや〜研究もそんなにしてないな…じゃあ何を…1. はじめにAlg…
ReactのHooksが実質algebraic effectsなんじゃないかということでalgebraic effectsに関する怪文書が流布して鼻白んでしまう、そんな未来を阻止するため、曲がりなりにもalgebraic effect…

なるほど、 復帰可能な例外 ですね。承知しました。

2. shallow effect handler

では改めて、 shallow effect handlerとはなんでしょう? 上に挙げられたシステムでは、ハンドラが取ってきた継続を起動させたときにまた発生するエフェクトが、また同じハンドラによって捕捉されています。 逆に shallow effect handler は、ハンドラが取得した継続の中で発生するエフェクトは同じハンドラによっては捕捉されず、一つ外側のハンドラまで到達します。 論文はこちら:

Plotkin and Pretnar’s effect handlers offer a versatile abstraction for modular programming with user-defined effects. Traditional deep handlersare defined by folds over computation trees. In this…

感覚としては、 shift/resetshift が継続を切り取るときに reset がくっついてくるけど、 shift0/reset0 ではくっついてこないという関係と同じですね。 shift/reset などについてはコチラ

こんにちは、びしょ〜じょです。control/promptとprompt tagへの理解が必要になったため、やっていきましょう。1. continuation??? 継続??? is power…

ごちゃごちゃ言ったけどEff言語でサクッと例を見てみましょう。 こんなエフェクトと関数を定義します。 ハンドラhPエフェクトが2回発生する式をハンドルします。

effect P : int -> int

let c h =
  with h handle
    perform (P 2) + perform (P 3)

ほんで

let a1 = c (handler
  | effect P i k -> k (i + i)
  | val x -> x)

assert (a1 = (4 + 9))

うん、よさそうだ。 (+) の評価は左辺の部分項を評価してから右辺に移る、と自然に考えると、最初にPが発生したときにハンドラが取得する継続 kwith h handle □ + perform (P 3) となる。 (i + i)[i/2]を放り込むので(中略) 4 + 9 (= 13) という結果が得られる。

続いてshallow handlerを使います。 ジッサイのEffにはないんですが、 handler† をshallow handlerとします。

let a2 = c (handler
  | effecf P i k ->
    with (handler
      | effect P i k -> k 10
      | val x -> x
    ) handle
    k (i + i)
  | val x -> x)

assert (a2 = (4 + 10))

フーム妙だ、妙だな……。 最初にperform (P 2)をハンドルすると、取得する継続 k□ + perform (P 3) です。 おや、これはa1の評価と異なりますね。 これが shallow です。 ハンドラは継続の中まで追っていきません。 なので2回めのエフェクトの発生は、 P のマッチアーム内で新たに定義しているハンドラによってハンドルされます。 なので 4 + 10 (= 14) が返ってきます。

2-1. 役に立つんですか?

Hillerströmらの論文では、pipe/copipeのように生成と消費をおこなう相互再帰関数を例にあげている。 またコルーチンのようにリターンポイントをハンドラで実装するときなども、shallow handlerで事足りるだろう。

3. fcontrol/runでshallow effect handlerの実装

ところでわたくしこういう研究をしてるんですが、実は先日もポーランドに行って発表しました(隙自語)。 このコルーチンによるalgebraic effectsの実装は、ハンドラがdeepになってます。 修論ではshallowな方の埋め込み方法も乗せているんですが、ご覧の通りなんかぱっとしないし効率もよく無さそうだ。

ところで fcontrol/run というコントロールオペレータがあるのですが

CiteSeerX - Document Details (Isaac Councill, Lee Giles, Pradeep Teregowda): Non-local control transfer and exception handling have a long tradition in higher-order programming languages such as Common Lisp, Scheme and ML. However, each language stops short of providing a full and complementary approach — control handling is provided only if the corresponding control operator is first-order. In this work, we describe handlers in a higher-order control setting. We invoke our earlier theoretical result that all denotational models of control languages invariably include capabilities that handle control. These capabilities, when incorporated into the language, form an elegant and powerful higher-order generalization of the first-order exception-handling mechanism. 1 Introduction Control manipulation in applicative programming languages comes in two flavors. First-order control operators allow computations to abort to a dynamically enclosing control context, e.g., Common Lisp’s [23, 24] throw and ML’s [9, 17] raise. They are invariably accompanied by forms th…

あんまりいい感じに意味論が書かれてないんでracket/control のドキュメントより引用すると

$$ \begin{array}{rcll} \left(\%\ \mathit{val}\ \mathit{proc}\right) & \rightarrow & \mathit{val} & \cr \left(\%\ E \left[\left(\mathtt{fcontrol}\ \mathit{val}\right)\right] \mathit{proc} \right) & \rightarrow & \left(\mathit{proc}\ \mathit{val}\ \left(\lambda \left(x\right)\ E\left[x\right]\right)\right) & \text{$E$ has no $\%$} \end{array} $$

となっています。 %runのwrapperで、(% exp handler) === (run (λ () exp) handler)とのことです。 % がdelimiterで fcontrol が継続を取り出すオペレータです。 面白いのは shift/resetcontrol/prompt と違い、 fcontrol 自体は継続を扱わずにdelimiterの % の引数の proc が継続を使います。 アレッ?! これすでに (% □ proc) がハンドラで fcontrol がエフェクト発生じゃん?! ところでRacketの fcontrol/run はプロンプトタグが使えます。 つまり fcontrol が評価されたときに、どのdelimiterまで戻ればいいかをタグにより指定することができるんですねえ。 ここで吉報です。multi-prompt shift/resetによるEff言語の埋め込みはKiselyovらにより示されています。

PDF | We present the embedding of the language Eff into OCaml, using the library of delimited continuations or the OCaml-effects branch. The embedding… | Find, read and cite all the research you need on ResearchGate

よし! では実装しましたはいこちら

#lang racket

(require racket/control)

(define (fcontrol f #:tag [prompt-tag (default-continuation-prompt-tag)])
  (call-with-composable-continuation
   (lambda (k)
     (abort-current-continuation
      prompt-tag
      f
      k))
   prompt-tag))

Racket v7.6以前はfcontrol/runをプロンプトタグを指定して使う場合にバグがあったので、最新の環境でない場合は上記のようにfcontrolを上書きします。 次こそ本題です。

(define (perform eff v)
  (fcontrol v #:tag eff))

(define (new-effect)
  (make-continuation-prompt-tag))

エフェクトeffを引数vを渡して発生させるので、そのままfcontrolを使います。 Racketのfcontrolではオプショナル引数#:tagでタグを渡せます。

エフェクトはプロンプトタグに対応するのでそのままです。

ハンドラの実装がメインディッシュです。

(define ((call-with-shallow-handler eff vh effh) th)
    (let* [(p (make-continuation-prompt-tag 'return))
           (const (λ (x _) x))
           (effh~ (λ (x k)
                     (fcontrol (effh x k) #:tag p)))]
      (%
        (let [(r (% (th) effh~ #:tag eff))]
          (vh r))
        const #:tag p)))

(call-with-shalow-handler effe vh effh)で、エフェクトeffをハンドルするハンドラを作ります。 んでサンクthをこのハンドラに渡すと、ハンドラのもとでサンクが潰れて評価が走ります。

基本的な考え方は非常に簡単、fcontrol/runがalgebraic effects & handlersであるという直感をそのまま使います。 (% (th) effh #:tag eff) でエフェクトeffが起きたときにエフェクトハンドラeffhでハンドルします。 しかしfcontrol/runに足りないものがある。なにか。value handlerである。 shallow effect handlerにおいてvalue handlerが介入するタイミングはdeepな場合と同じ、値をハンドルする場合のみです。 そしてshallowなので一度エフェクトをハンドルしたらハンドラは撤退しなければならない。 なのでこういう戦略でいきます。

  • 戻り値は常にvalue handlerで取るようにする
  • しかしエフェクトが発生したらvalue handlerを迂回する

ベストか? と言われると自信ないですが、ハンドリングされた式を評価したときにエフェクトハンドラでハンドルされたかどうかのフラグを持っておくのはなんかダサいし状態を持ちたくないというのはピュアな感覚です。 またタグをつけたり外したりもちょっと面倒です。 なので今回はどうにかして迂回します。 幸い今回はコントロールオペレータが1つ、fcontrol/runが与えられています。 しかも今回はプロンプトタグのおまけ付きだ。 エフェクトハンドラの戻り値をfcontrolで飛ばしてvalue handlerに渡るのを阻止しました。 吹っ飛んだときの継続は使わなくていいので、const関数でエフェクトハンドラの戻り値だけ受け取って返します。

いい感じじゃないですか。 それではコルーチンを実装してみます。

(struct coroutine ([it #:mutable]) #:extra-name Coroutine)

(define Yield (new-effect))
(define (yield v)
  (perform Yield v))

(define (resume co v)
  ((call-with-shallow-handler Yield
                              (λ (x) x)
                              (λ (u k)
                                 (begin
                                   (set-coroutine-it! co k)
                                   u)))
   (λ () ((coroutine-it co) v))))

yieldはエフェクトの発生、resumeはハンドラ、コルーチンスレッドは継続が保存されたセルです。 実装うまくいったかな?

(let [(co (coroutine
           (λ (_)
              (begin
                (display "hello,")
                (displayln (yield '()))
                ))))]
  (begin
    (resume co '())
    (resume co "world")))

こいつ、動くぞ……!

4. おわりに

fcontrol/runというおもしろいコントロールオペレータとそれを利用したshallow effect handlerの実装を紹介しました。 パフォーマンス比較とか他のコントロールオペレータとの関係は読者の皆さんの課題と勝手にさせて、ええ、いただきます。 夏休み最終日に絶望する小学生にならないように、日々こつこつと取り組んでください。


エッ修論?! 俺は卒業したのか……。