こんにちは､びしょ〜じょです｡ 気づけば2020年になってました｡ 2020年ってなんだ? SFですか?
1. はじめに - Algebraic Effectsおさらい
本日はshallow effect handlerを実装します｡ まず shallow effect handlerとはなんでしょう? 最初にalgebraic effects and handlersについておさらいします｡ あれとかこれとかそれとかを読んでおさらいしてください｡
なるほど､ 復帰可能な例外 ですね｡承知しました｡
2. shallow effect handler
では改めて､ shallow effect handlerとはなんでしょう? 上に挙げられたシステムでは､ハンドラが取ってきた継続を起動させたときにまた発生するエフェクトが､また同じハンドラによって捕捉されています｡ 逆に shallow effect handler は､ハンドラが取得した継続の中で発生するエフェクトは同じハンドラによっては捕捉されず､一つ外側のハンドラまで到達します｡ 論文はこちら:
感覚としては､ shift/reset の shift が継続を切り取るときに reset がくっついてくるけど､ shift0/reset0 ではくっついてこないという関係と同じですね｡
shift/reset などについてはコチラ
ごちゃごちゃ言ったけどEff言語でサクッと例を見てみましょう｡
こんなエフェクトと関数を定義します｡
ハンドラhでPエフェクトが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が発生したときにハンドラが取得する継続 k は with 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 というコントロールオペレータがあるのですが
あんまりいい感じに意味論が書かれてないんで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/reset や control/prompt と違い､ fcontrol 自体は継続を扱わずにdelimiterの % の引数の proc が継続を使います｡
アレッ?! これすでに (% □ proc) がハンドラで fcontrol がエフェクト発生じゃん?!
ところでRacketの fcontrol/run はプロンプトタグが使えます｡
つまり fcontrol が評価されたときに､どのdelimiterまで戻ればいいかをタグにより指定することができるんですねえ｡
ここで吉報です｡multi-prompt shift/resetによるEff言語の埋め込みはKiselyovらにより示されています｡
よし! では実装しましたはいこちら
#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の実装を紹介しました｡
パフォーマンス比較とか他のコントロールオペレータとの関係は読者の皆さんの課題と勝手にさせて､ええ､いただきます｡
夏休み最終日に絶望する小学生にならないように､日々こつこつと取り組んでください｡
エッ修論?! 俺は卒業したのか……｡