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

shiftとresetが実装できたのでそれらを使ってモナドっぽい機能を実装してみる。

手始めに以前も紹介したこの資料に出てくるMaybeモナド的なものを試してみたい：

モナドをつくろう from dico_leque

www.slideshare.net

HaskellやOCamlでMaybeモナドといえばJust x（あるいはSome x）かNoneの値を取る型とそれを返す関数を繋げていくような演算がポイントとなる。

しかし今回実装しているのはなんちゃってとは言えLispである。Lisperなら黙ってnilを返そう。（そもそも代数的データ型やパターンマッチを実装していないのでSome xとかできないし・・・）

というわけで演算の結果が何らかの値かnilであるというような処理を繋げていって、途中の計算結果がnilになった場合はショートサーキットして全体の結果がnilになる、といった処理が書けるようにしたい。JustやSomeにあたるケースはそのような特定のタグをつけるのではなく、そのままの値を使う。

そのために

• Haskellのdoにあたるような「ここからはMaybeモナドのコンテキスト内である」と指示するreify
• x <- ...に（おおまかに）対応するような「これはモナディックな値である」と指示するreflect
• 値かnilかを返すfind関数

の三つを定義する。

まずreify：

(let [reify (macro [expr] (reset expr))]
  ...)

マクロで式をresetに包むだけ。reifyを定義しなくてもresetをそのまま使えば同じことができるが、resetはモナドを実装するプリミティブとしてとりあえず隠蔽しておく。

次にreflect：

(let [reflect (fn [m]
        (shift [k] (if (nil? m) m (k m))))]
  ...)

shiftで現在の限定継続をとり、reflectが受け取った値がnilならそのまま全体の値をnilとし、そうでないならそのnilではない値を限定継続に渡して評価を続ける。

そしてfind：

(letrec [find [f xs]
          (cond
            [(nil? xs) nil]
            [(f (car xs)) (car xs)]
            [true (find f (cdr xs))])]
  ...)

要素に対する述語関数とリストを受け取り、もし述語を満たす値があればその一つを返し、もし満たすものがないならnilを返す。find関数はMaybeモナドの一部ではない。Maybeモナドを使うためにnilを返し得る関数が必要だったので定義しただけである。

組み合わせて使ってみる：

(reify
  (let [(a (reflect (find (fn [x] (= x 2)) (list 1 0 3))))
        (b (reflect (find (fn [x] (= x 3)) (list 2 3 1))))]
    (list a b)))

この場合、aがnilになるので全体の値もnilになる。さらにbに束縛される値は評価されずじまいとなる。

上記のコードを全部合わせてインタプリタで走らせられるようにしたプログラムは以下のとおり：

(let [(reify (macro [expr] (reset expr)))
      (reflect (fn [m]
        (shift [k] (if (nil? m) m (k m)))))]
  (letrec [find [f xs]
            (cond
              [(nil? xs) nil]
              [(f (car xs)) (car xs)]
              [true (find f (cdr xs))])]
    (reify
      (let [(a (reflect (find (fn [x] (= x 2)) (list 1 2 3)))) (* ここは変更 *)
            (b (reflect (find (fn [x] (= x 3)) (list 2 3 1))))]
        (list a b)))))

aの式に少しだけ変更を加えていて、そのせいで今回はaもbもnilにならないので、最終的に結果は(2 3)となる。

というわけでMaybeモナドのように、途中結果がnilなら全体の結果もnilになるような処理が簡単に記述できるようになった。

次はsshiftとresetで非決定性プログラミングができるようなListモナドをつくってみる。