モナドのインタープリタ

モナドを実行するインタープリタを書かないといけません。必要なのはaicmdを受け取って、次に実行するコマンドと残りのaicmdを返す関数です。OCaml側がその関数を順に呼び出します。

とりあえずの実装なので、動くんだけど効率とかよくないし直したい。継続を返すようにするともっと効率がよくなる気がするし、よく考えたらCoFixpointで実装してもいい気がする。多分。

最初のフェーズはモナドの先頭部分がコマンドになるまで、bindを崩していきます。

hnf_cmd : forall A, cmdex A -> cmdex A.
hnf_ai : forall A, aicmd A -> aicmd A.

がそれを行います。match in return withが飛び交う修羅場になっています。

hnf_cmdはコマンドcを受け取ると、cで場合分けして

• c' >>= f の形でない場合はc自身を返す
• c' >>= f の形だったら、再帰的に c' に適用する。その結果の c'' で場合分けして
  • ret v の形だったら、f v に再帰的に適用する。
  • ExState の形だったら、現在の状態をfに渡して、結果に再帰的に適用する
  • ExNop だったら、f tt に再帰的に適用する。
  • そのほかの場合は c'' >>= f を返す。

よく考えると、ExNopは必要ないです。ret ttを使えばいいので。

hnf_aiはほとんど同じですが、arun に対しては hnf_cmd を呼び出します。

あとは先頭を取り出す関数を書けばモナドインタープリタは完成です。