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

前から随分経ちましたが、前回 http://d.hatena.ne.jp/propella/20100321/p1 の続きです。久しぶりなので最初から考え直します。

データ

逆転パーサーでは、全てのデータはタグ内容内容... の正規形を持っている事にします。Prolog と一緒です。Pair 1 Nil や Apple はデータです。

プリミティブ型

とりあえず整数とタプルとリストと関数をプリミティブ型として考えています。プリミティブ型も正規形を持ちます。例えば 3 の正規形は Succ (Succ (Succ Zero)) だという事にします。

関数

関数はタプルからタプルへの写像です。表記は以下のような感じ。| で区切ってケースを追加する事が出来ます。パターンは | の後ろの方から前に評価され、マッチした所の左辺が返り値になります。後ろから評価する理由は、最初に一般的な場合を書いてだんだん特殊例を追加する事を想定してるからです。

(pattern1, pattern2, ...) -> (result1, result2, ...)
| (pattern3, pattern4, ...) -> (result3, result4, ...)
| ...

Haskell と違って部分適用やカリー化や可変引数は無しです。アリティ固定じゃないと関数をパターンマッチに使う時に困るからです。多くの場合、引数か結果のどちらかの要素が一つです。引数たくさんで結果が一つの関数を構築子、引数一つで結果が沢山の関数を展開子と呼びます。関数とデータのタグは同じように振る舞います。

関数適用とパターンマッチ

関数適用は Func arg1 arg2 のような前置記法と arg1 + arg2 のような中値記法があります。arg1 や arg2 はタプルの要素ですが、引数として書く時は括弧やコンマを書きません。関数名が記号の時には中値記法になります。パターンマッチの記法も同じです。

パターンマッチの場合、やって来た値が関数によって評価されて、その結果のタプル要素が arg1 や arg2 に束縛されます。どの関数もパターンとして使えるように引数も値も固定長タプルという事になっています。式が -> の左辺にある時パターン、右辺にある時は関数適用として解釈されます。例えば、cons が Pair を作る関数で、cons~ がその逆関数の場合、

car  = (cons~ x y)  <-> (x)

という関数があったとき、car (Pair 1 2) を評価すると展開子 cons~ によって x に 1 が束縛されて 1 が返ります。

定義

定義文は名前 = データと書きます。例えば one = 1 とか、double = x -> x * x です。特別な例として右辺に <-> を使うと関数と逆関数を同時に定義出来ます。例えば

cons = (x, y) <-> (Pair x y)

と書くと、

cons = (x, y) -> (Pair x y)
cons~ = (Pair~ x y) -> (x, y)

という二つの関数を定義したのと一緒です。func~ は (inverse func) の略です。関数は逆関数を持つ事が出来ます。実際に逆関数の性質を満たしているかどうかはプログラマの責任です。

データの定義

データの定義は data タグ要素型要素型... と書きます。この定義によって、データ構築子とその逆関数の展開子が同時に作られます。例えば、

data Pair a b

と書くと、構築子 Pair と展開子 Pair~ が定義されます。タグと関数は定義の仕方が違うだけで外から見れば同じ物です。慣習としてタグは大文字で始めます。また、これは次の定義と同じです。

Pair :: (a, b) <-> (Symbol, a, b)
Pair  = (x, y) -> (<Pair>, x, y)
Pair~ = (<Pair>, x, y) -> (x, y)

型

あるデータが、展開子 X~ で展開出来る時、そのデータを X 型であると呼びます。一つのデータは複数の型を持ちます。例えば any = x <-> x という定義がある時、全てのデータは any 型になります。タグ~ は展開子なので、タグはそのまま型として使えます。もっと役に立ちそうな例では、

data True
data False
bool = (True)  <-> (True)
     | (False) <-> (False)

という定義がある時、True と False は bool 型だという事になります。この型情報はdata 定義の引数部分に使います。

また、型を Haskell 風に :: の後に書く事によって型チェックが出来ます。関数の引数も値も必ずタプルなので、型は一般的に (引数, 引数, ...) -> (値, 値, ...) という形をしています。

例: 8 ビット整数

bit = 0 <-> 0            -- 0 と 1 にマッチする型 bit を定義
    | 1 <-> 1
data U8 bit bit bit bit bit bit bit bit -- bit 8個を要素に持つ U8 を定義

この 8 ビット整数を使ってビットストリームに読み書きする関数を書きます。リストの書き方は Haskell と同じです。

char :: U8, [bit] <-> [bit]
char = (U8  b7 b6  b5  b4  b3  b2  b1  b0, bs) <-> (b7 b6 : b5 : b4 : b3 : b2 : b1 : b0 : bs)

これで、bit の配列の先頭に U8 を追加する構築子 char と、bit の配列から最初の 8 ビットを読む展開子 char~ が定義されます。

プリミティブ

実用を考えると、U8 は整数型で表現する事になると思います。この場合 U8 はホスト言語で書かれたプリミティブになります。

U8 = (b0, b1, b2, b3, b4, b5, b6, b7) -> {文法考え中}
U8~ = {文法考え中} -> (b0, b1, b2, b3, b4, b5, b6, b7)

可変長文字列

構造体っぽく書くと次のような可変長文字列を考えます。

String8 {
  U8 size;
  U8 content[size];
}

つまり、最初の 8 ビットがサイズで、その後実際のデータが続きます。これをビットストリームに書き込む部品を作ってみます。かなりややこしいので順番に、書き込み側の関数と見なして説明します。

string はメインの関数で、U8 を書き込む char と [U8] を書き込む chars の二つのサブ関数を使います。まず string の左辺で chars を使い文字列の長さを求め、次に string' で長さを書き込みます。ソース上の順序とは逆ですが、ビットストリームには長さ、文字列の順序で書き込まれます。

string :: ([U8], [bit]) <-> ([bit]) -- string とは、文字列(U8 のリスト) をビットストリームの先頭に追加する。
string  = (cs,   bs)    <-> (string' (chars cs bs)) -- 文字列を書き込み文字数を得る。
string' = (size, bs)    <-> (char size bs) -- 文字数を書き込む。

chars は文字列をビットストリームの先頭に追加し、追加した文字数と追加したビットストリームを返します。上の string' 定義の左辺では (size, bs) を使って文字数とビットストリームをパターンマッチし、右辺で書き込んでいます。

chars :: ([U8], [bit])             <-> (U8, [bit])
chars = (charsHead c (chars n bs)) <-> (Succ n, char c bs)
      | ("", bs)                   <-> (0, bs)

charsHead は文字列とビットストリームを受取り、先頭の一文字を分離して返す関数です。上の chars の左辺では、charsHead はやって来た文字列の一文字目を c に束縛し、残りの文字列とビットストリームのタプルを chars に渡します。chars は再帰的に残りの文字列を書き込み、書き込んだ文字数を n に、結果のストリームを bs に束縛します。これが右辺に渡ると Succ n で一文字分も字数を増やし、 char c bs で charsHead によって束縛された文字を書き込みます。

charsHead :: ([U8], [bit]) <-> (U8, ([U8], [bits]))
charsHead = (c:cs, bs)     <-> (c, (cs, bs))

このプログラムはパーサーとして、つまり右辺から左辺へ呼んでも完璧に動作します。

おわりに

バイナリデータの読み書きに便利な、逆実行可能な関数型言語を設計しています。ちょっと思ったよりややこしくなって来たので困っている所です。まだ抽象化が足りなくて、例えば逆転可能コンビネータとかがあればもう少しすっきりするかも知れません。言語の読みやすさという点では、実行順序がはっきりしているので Prolog よりはましかなと思っています。if then や let を導入しなくても、思ったより色々出来るなと感じています。if then が要らないのは | によりケース分けのおかげ、let が要らないのはパターンマッチのおかげです。今実装をどうしようか悩んでいます。とりあえず今日の例は Haskell に手で書き直して実験しました。ソースは https://gist.github.com/748149 です。

言語ゲーム

とあるエンジニアが嘘ばかり書く日記