Arantium Maestum

プログラミング、囲碁、読書の話題

めざそう言語処理系の沼 〜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の結果を束縛しているabは確かにリストではなく整数として扱われている。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の引数である関数fstateを引数として渡され、(cons val state1)を返しているので正しくStateモナドのモナディック値(fn [state] (cons .. ..))という形になっていることが確認できる。

shift内で「モナディックではない値を返す」とは限定継続にモナディックではない値を渡すということ。((k val) state1)とやっているのでそこもクリアしている。

次はreflectを使ってgetputを書き直す:

(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モナドを修正して型がちゃんとあうようにする。