めざそう言語処理系の沼 〜shift/resetへの旅 〜 その20 Stateモナドとreflect
前回このように書いた:
Stateモナドにはreflectに直接当たる処理はなく、getとputの二つの関数がモナディックな処理を担う。
しかし「限定継続を使ってモナドを表現する」というアイデアの元となるRepresenting Monadsという論文を読み直していたらちゃんとStateモナドのreflect
についても書かれていたので訂正したい。
モジュールの話はまた後々。
reflect
の定義
そもそもreflect
とは何をする関数なのか。
前述の論文を当たってみると:
signature RMONAD = sig structure M : MONAD val reflect : '1a M.t -> '1a val reify : (unit -> 'a) -> 'a M.t end;
というSMLでのモジュールシグニチャ(つまりモジュールの型)定義が出てくる。
reflect
は何らかのモナディックな値を引数にとり、モナディックではない値を返す関数とのこと。
逆にreify
は「モナディックではない値を返すthunk」を引数にとり、モナディックな値を返す関数となっている。(SMLではreify
はマクロではなく関数なので、評価を遅延させるために引数0のthunk関数を使っている)
例えばListモナドを例にとると:
(reify (let [(a (reflect (list 1 2 3))) (b (reflect (list 4 5 6)))] ...))
この場合モナディックな値とはリストのことなので、(list 1 2 3)
や(list 4 5 6)
の部分である。
それらを包んだreflect
の結果を束縛しているa
やb
は確かにリストではなく整数として扱われている。reify
の中でというのが前提条件だが、確かにreflect
はモナディックな値を普通の値に変換する役割を持つようだ。
(ちなみにこの記事を書いている最中にListモナド実装にも重大なミスがあることに気づいた。次の記事で修正する話を書きたい)
Stateモナドにおけるモナディックな値
reflect
がモナディックな値を普通の値に変換することがわかった。
それではStateモナドにとっての「モナディックな値」とは何だろうか?
reify
は「モナディックではない値を返すthunk」を引数にとり、モナディックな値を返す関数
という型情報から、(reify ...)
が返す値がStateにとってのモナディックな値(の型)であることがわかる。
reify
の定義:
(define reify (macro [expr] (reset (let [result expr] (fn [state] (cons result state))))))
というわけで(fn [state] (cons ... ...))
という関数がStateモナドのモナディックな値の形である。
直感的な説明としては「現在の状態を引数にとり、計算結果である値と次の状態のタプルを返す関数」だ。
Stateモナドのreflect
このStateモナドの型定義と前述のreflect
の型定義:
reflect
は何らかのモナディックな値を引数にとり、モナディックではない値を返す関数
これらを踏まえてreflect
を書いてみる:
(letfn [reflect [f] (shift [k] (fn [state] (let* [(val-state (f state)) (val (car val-state)) (state1 (cdr val-state))] ((k val) state1))))] ...)
reflect
の引数である関数f
はstate
を引数として渡され、(cons val state1)
を返しているので正しくStateモナドのモナディック値(fn [state] (cons .. ..))
という形になっていることが確認できる。
shift
内で「モナディックではない値を返す」とは限定継続にモナディックではない値を渡すということ。((k val) state1)
とやっているのでそこもクリアしている。
次はreflect
を使ってget
とput
を書き直す:
(letfn [get [] (reflect (fn [state] (cons state state)))] ...) (letfn [put [val] (reflect (fn [state] (cons nil val)))] ...)
get
は「限定継続に渡す値」も「次の状態」も、引数であるstate
をそのまま使っている。なので「状態を変更せずに、現在の状態を値として取り出す」という挙動となる。
put val
は「限定継続に渡す値」はnil
、「次の状態」はval
となる。「返す値はnilで状態だけをセットする」という挙動だ。
前回使った「shift/resetプログラミング入門」の例題をreflect
も使って書くと:
(run_state (reify (let* [(tick (fn [] (reflect (fn [state] (cons nil (+ state 1)))))) (_ (tick)) (_ (tick)) (a (get)) (_ (tick))] (- (get) a))) 0)
これもちゃんと(1 . 3)
という結果が返ってくる。
次回
次回はListモナドを修正して型がちゃんとあうようにする。