めざそう言語処理系の沼 〜shift/resetへの旅 〜 その１９ shift/resetでつくるStateモナド

shiftとresetを使ってStateモナドを実装する。ちなみに今まで実装したモナドの中で随一のややこしさである。

Stateモナドはその名のとおり、計算に局所的な「状態」を持たせることができるモナドである。状態とは「値を参照したり書き換えたりできる何か」を指す。

詳細はHaskell Wikiを参照してほしい：

wiki.haskell.org

reify、get、put、run_state

今回reifyが複雑になっている：

(let [reify (macro [expr]
        (reset
          (let [result expr]
            (fn [state] (cons result state)))))]
  ...)

最終的にreifyが返すのは「初期状態」を受けとり「exprの評価結果と最終状態のタプル」を返す関数となる。例によってreifyはマクロなのでexprはresetの中でresultに束縛される時点までは評価されない。

Stateモナドにはreflectに直接当たる処理はなく、getとputの二つの関数がモナディックな処理を担う。

まず現在のStateの値をとってくる関数であるget：

(let [get (fn []
        (shift [k]
          (fn [state] ((k state) state))))]
  ...)

そしてStateの値を更新した上で評価結果はnilになるput：

(let [put (fn [val]
        (shift [k]
          (fn [state] ((k nil) val))))]
  ...)

これら二つの関数は形がけっこう似ている。どちらもshiftを使って限定継続をとり、reset内の式を(fn [state] ((k X) Y))という形の関数に置き換えてしまう。

Xは「この関数呼び出しの評価結果」で、Yは「この関数呼び出し以降のstateの値」である。

getの場合はXは現在のstate、Yも（状態を変更しないので）現在のstateで(fn [state] ((k state) state))となる。

putの場合はXはnil、Yはputの引数であるvalで、(fn [state] ((k nil) val))となって元々のstateは破棄されて新しい値に更新される。

reifyの中でgetやputが呼ばれるかどうかに関わらず、reifyの結果は(fn [state] ...)という関数であることがわかる。

その関数に対して初期状態値を適用してやるrun_state関数を定義する：

(let [run_state (fn [m state]
        (m state)))]
  ...)

Stateモナドな値と初期状態値をとって関数適用するだけ。

これらの関数があればStateモナドが使える。ここからはいくつか使用例を紹介する。

使用例１

getもputも使わず、reifyに直接値を渡す場合：

(run_state (reify 5) 0)

reifyの部分は、内部でshiftが呼ばれなかったのでそのまま(fn [state] (cons 5 state))という関数になり、run_stateで0をstate引数として渡されて、最終的な結果は(5 . 0)。

使用例２

getを使ってみる：

(run_state (reify (get)) 0)

今回はreifyの中にgetがあるのでshiftが実行され、

(reify (get))

は

(fn [state] ((k state) state))

に置き換えられる。

この時点での限定継続kを関数として表現すると(fn [v] (let [result v] (fn [state] (cons result state))))となるので、(reify (get))はこの：

(fn [state] ((k state) state))

からkを置き換えて：

(fn [state] ((let [result state] (fn [state'] (cons result state'))) state))

簡約して：

(fn [state] ((fn [state'] (cons state state')) state))

さらに簡約して

(fn [state] (cons state state))

となり、(run_state (reify (get)) 0)の結果は(0 . 0)となる。

使用例３

putを使ってみる：

(run_state (reify (put 5)) 0)

これも(reify (put 5))が

(fn [state] ((k nil) 5))

に置き換えられ、限定継続kはやはり(fn [v] (let [result v] (fn [state] (cons result state))))となるので

(fn [state] (((fn [v] (let [result v] (fn [state] (cons result state)))) nil) 5))
(fn [state] ((let [result nil] (fn [state] (cons result state))) 5))
(fn [state] ((fn [state] (cons nil state)) 5))
(fn [state] (cons nil 5))

となり、(run_state (reify (put 5)) 0)の結果は(nil . 5)になる。

使用例４

最後に「shift/resetプログラミング入門」の例題を実装してみる：

(run_state
  (reify
    (let* [(tick (fn [] (put (+ (get) 1))))
           (_ (tick))
           (_ (tick))
           (a (get))
           (_ (tick))]
       (- (get) a)))
  0)

• 「状態をインクリメントする」tick関数をgetとputを使って定義
• tickを複数回使って状態を更新
• 途中の状態の値を変数aに束縛
• 最終的な状態の値とaとの差を求める

という処理になっており、最終的な結果は(1 . 3)（求めた差と最終状態のタプル）となる。

このコードの全容：

(let [(reify (macro [expr]
        (reset
          (let [result expr]
            (fn [state] (cons result state))))))
      (get (fn []
        (shift [k]
          (fn [state] ((k state) state)))))
      (put (fn [val]
        (shift [k]
          (fn [state] ((k nil) val)))))
      (run_state (fn [m state]
        (m state)))]
  (run_state
    (reify
      (let* [(tick (fn [] (put (+ (get) 1))))
             (_ (tick))
             (_ (tick))
             (a (get))
             (_ (tick))]
         (- (get) a)))
    0))

まとめ

shiftとresetを使ってHaskellのStateモナドと同等のことができるようになった。他にも関数適用する形で状態を更新するmodifyなどがあるが、tickと同じようにgetとputの組み合わせで書ける。

do記法のように特殊なモナド構文を使わず、reifyの中では普通のlet、let*や関数呼び出しなどを使って処理が記述できるところは面白い。

次回

別ファイルに記述されたスタンダード・ライブラリを読み込む機能がほしい。その前準備として簡単なモジュール機構を実装する。