妄想パターンマッチ言語実例(逆転パーサー6)

前回提案した文法 http://d.hatena.ne.jp/propella/20100320/p1 を元に、AVM2 ABC ファイルの 32 ビット整数 u32 http://www.adobe.com/devnet/actionscript/articles/avm2overview.pdf のリーダー(パーサー)とライターを記述してみます。準備として、必要なデータ構造を挙げます。

data U32 b32 b31 b30 b29 b28 b27 b26 b25 b24 b23 b22 b21 b20 b19 b18 b17 b16 b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0
data U7 b6 b5 b4 b3 b2 b1 b0
data U4 b3 b2 b1 b0
data 1
data 0

U32 U7 U4 はそれぞれプリミティブとして定義され、整数リテラルが使える物とします。

またここに挙げた物の他、Haskell と同じように [ ] でリスト終端 [a, b, c] または a : b : c : [ ] でリスト ( : は右結合の cons) と言う事にします。ライターは 32 ビット整数を受取りリスト(要素は 1 か 0) を返す関数。リーダーはリストを受取り 32 ビット整数を返す関数になります。

経験上リーダーを考えるよりライターを考える方が簡単なので、順番としては 32 ビット整数を書き出す手順を考えます。まず、32 ビットを 7 ビットずつと上位 4 ビットに分解します。要素を分解するのはパターンマッチの役割なので、定義としては上位 4 ビットと 7 ビットずつを受取り 32 ビット整数を返す関数になります。

chunk = U4 b31 b30 b29 b28,
        U7 b27 b26 b25 b24 b23 b22 b21,
        U7 b20 b19 b18 b17 b16 b15 b14,
        U7 b13 b12 b11 b10  b9  b8  b7,
        U7  b6  b5  b4  b3  b2  b1  b0 ->
        U32 b31 b30 b29 b28 b27 b26 b25 b24 b23 b22 b21 b20 b19 b18 b17 b16 b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0

この関数 chunk を定義すると、逆に 32 ビット整数を 7 ビットずつに分解する展開子 chunk~ が自動的に定義されます。

次に分解した整数を元にビット列を作る関数を作ります。この関数 bits はリスト xs の前に数字に応じたビット列を追加します。例えば、bits 15 [0, 0, 0] の答えは [1, 1, 1, 1, 0, 0, 0] になります。xs が必要なのはこの関数を他と組み合わせて使うからです。

bits7 = U7  b6  b5  b4  b3  b2  b1  b0, xs -> b6 : b5 : b4 : b3 : b2 : b1 : b0 : xs
bits4 = U4  b3  b2  b1  b0            , xs ->           b4 : b3 : b2 : b1 : b0 : xs

ここで、bits7 と bits4 は同じような関数なのでポリモフィック関数にしても良さそうな物ですが、答えが可変長リストなのでポリモフィックにすると逆関数でリストを読む際にどちらか一方が必ずマッチしてしまい上手くいきません。

次に、最終的なライターの定義です。それぞれの場合に応じてビット列を作ります。| で区切ったパターンは下から上に評価される事に注意です。

u32 = chunk~ n4 n3 n2 n1 n0 -> 1 : bits7 n0 (1 : bits7 n1 (1 : bits7 n2 (1 : bits7 n3 (bits4 0 (bits4 n4 [])))))
    | chunk~  0 n3 n2 n1 n0 -> 1 : bits7 n0 (1 : bits7 n1 (1 : bits7 n2 (0 : bits7 n3 [])))
    | chunk~  0  0 n2 n1 n0 -> 1 : bits7 n0 (1 : bits7 n1 (0 : bits7 n2 []))
    | chunk~  0  0  0 n1 n0 -> 1 : bits7 n0 (0 : bits7 n1 [])
    | chunk~  0  0  0  0 n0 -> 0 : bits7 n0 []

これで完成です。ここで定義した関数 chunk、bits7、bits4、u32 を見ると、どれも逆関数を定義するのに必要な条件を備えている事に気がつきます。つまり、使っている関数全てに逆関数が存在し、変数に増減がありません。という事で、逆関数 chunk~ bits7~ bits4~ u32~ がそれぞれ定義されます。u32~ はリーダーとして使う事が出来ます。実際に右から左に視線を追って、矛盾無く動作する事を確認してみて下さい。

我ながらきれいに行きました。理屈上生成されるデータはビット列という事になっていますが、実装はバイト列やワード列を使う事になると思います。書いてある通りに動けば良いだけで、書いてある通りに実装する必要はありません。: のある部分で書いたり読んだりするだけので、ホスト言語に応じて副作用のあるストリームを使う形に変換するのも簡単だと思います。

あとは読みやすいかどうかですね。私には読みやすいですけど、あまりにも Haskell 臭すぎるかもしれない。