めざそう言語処理系の沼 〜shift/resetへの旅 〜 その２１ やはり俺のListモナドはまちがっている。

前回こう書いた：

ちなみにこの記事を書いている最中にListモナド実装にも重大なミスがあることに気づいた

今回はその話。

reifyの型

Representing Monadsのreifyとreflectの型定義：

signature RMONAD = 
  sig
    structure M : MONAD
    val reflect : '1a M.t -> '1a
    val reify : (unit -> 'a) -> 'a M.t
  end;

これを見てみるとreifyは'a型を返すthunkを引数にとり、'aを包んだモナディックな値を返す、という型になっている。（前回の記事でも言及したが、Kontlangではreifyはマクロなので(unit -> 'a)なthunk関数ではなく、評価されたら'a型になる式をそのまま受け取れる）

それに対して、前々回でListモナドを使ってみた時、このような形で書いた：

(reify
  (let [(x (reflect (list 1 2 3 4 5)))
        (y (reflect (list 1 2 3 4 5)))
        (z (reflect (list 1 2 3 4 5)))]
    (if (= (* z z)
           (+ (* x x)
              (* y y)))
      (return (list x y z))
      nil)))

reifyの中の式が返す値は(return ...)かnilで、どちらもモナディックな値（この場合リスト）となっている。（(return (list x y z))は(list x y z)をreturnでさらにネストした要素１のリストに変換していることに注意）

これだとreifyの型は(unit -> 'a M.t) -> 'a M.tとなってしまう。

実際reifyの定義もこうなっていた：

(define reify (macro [expr] (reset expr)))

resetに包むだけで他の変換は何もしていないわけだから、(unit -> 'a M.t) -> 'a M.tなのも当然とも言える。

そう考えると正しい定義は：

(define reify (macro [expr] (reset (list expr))))

このように式の結果をモナディックな値（Listモナドなら当然リスト）に変換する処理を入れるのが大事。こうすれば(return (list x y z))からreturnが省ける。

しかし今度はif分岐のもう一つの結果であるnilが問題となってくる。こちらもreifyの(reset (list expr))でリスト化されてしまって、最終的な結果に残ってしまう（例えば(nil nil ... (3 4 5) nil ... (4 3 5) ...)のような結果が返ってくる）。

nilの代わりに「分岐のこちら側は失敗でなんの結果も返さない」という意味の処理が必要となる。

failあるいは(reflect nil)

この問題の解決方法もやはりRepresenting Monadsに書かれていた。

failという関数を定義して使えばいい：

(letfn [fail [] (reflect nil)]
  ...)

少し非直観的なのでreflect関数の挙動を考えてみる。

複数の要素が含まれるリストをreflectすると、それ以降の処理が各要素につき一回ずつ、バックトラックで行われる。

要素数１のリストをreflectすると、それ以降の処理がその一つの要素に関してのみ実行される。なので(let [a (reflect (list b))] ...)は(let [a b] ...)と変わらない。

では空リストをreflectするとどうなるのか？それ以降の処理を適用する要素がないので、そのまま実行を打ち切り、なんの結果も返さずにバックトラックする。

この挙動が(if condition result nil)のnilの部分に本当に欲しかったものだ。

なので(letfn [fail [] (reflect nil)] ...)で「空リストをreflect」を実行する引数０の関数failを定義する。

これで「この式が評価されるところまで来たらなんの結果も返さずに処理を打ち切ってバックトラック」というポイントを(fail)で指定できる。

使ってみる：

修正したreifyと追加したfailを前述の例で使ってみる：

(reify
  (let [(x (reflect (list 1 2 3 4 5)))
        (y (reflect (list 1 2 3 4 5)))
        (z (reflect (list 1 2 3 4 5)))]
    (if (= (* z z)
           (+ (* x x)
              (* y y)))
      (list x y z)
      (fail))))

これでreifyのなかの式は返り値がモナディックではない値でよくなった（わかりにくいことにこのケースではそれでも返り値はリストだが、「モナドとしてのリスト」ではない）。

気になるのはfailの型だが・・・　なんの値も返さない（nilすら）ので、逆になんの型とも矛盾しないということで() -> 'aになるのか・・・？まあkontlangは動的型付けなのであまり関係ないが・・・

次回

次は話を戻してモジュールの実装を進めていく。