http://d.hatena.ne.jp/propella/20091115/p2 の続き。Scala の Extractor のおかげでアイデアがまとまって来たのでメモ。逆転パーサーの基礎になる言語について考える。最初のバージョンで言語に欲しい性質は次の通り。
データと構築子と展開子
全てのデータは タグ 内容 内容 ... のように表現します。タグだけのデータもありです。データは data 文で宣言し、例えば 4 ビット整数は次のように書きます。b3 や b2 といった内容の部分はここにデータがあるという事だけを示し、名前はただのコメントです。
data True data False data UInt4 b3 b2 b1 b0
この宣言の後、True False というタグだけのシンボルと、UInt4 という構築子(constructor) と、 UInt4~ という展開子(extractor)、この二つの関数が自動的に定義されます。
> UInt4 True True True True => (15 を表現する何か)
このようにしてプログラムで使う全てのデータを構築して行きますが、実際には数や文字列等はプリミティブで実装されます。プリミティブを作るには構築子と展開子の二つの関数を自前で実装します。構築子はデータの作成に、展開子はデータのアクセスに使います。上記の UInt4 を実装するためのシグネチャはこんな風になります。
primitive data UInt4 UInt4 = <primitive UInt4_construct> -- 構築子(True か False の四組を受取り、四ビット数値を返す) UInt4~ = <primitive UInt4_extract> -- 展開子(四ビット数値を受取り、True か False の四組を返す)
関数と定義
関数は構築子か展開子のどれかです。
- 構築子は パターン, パターン, ... -> 式 の形をして、ゼロ個以上のパターンを引数に一つの値を返します。通常 Tag のように命名します。
- 展開子は パターン -> 式, 式, ... の形をして、一つパターンを引数にゼロ個以上のパターンを返します。通常 Tag~ のように命名します。
パターンとは引数になる展開子と仮引数の組み合わせです。式とは関数適用です。
関数やデータは = を使って変数に束縛出来ます。| で区切っていくつかの関数を組み合わせる事も出来ます。パターンの評価順序は普通と逆に下から上です。これはデフォルトのパターンを書くのを忘れないようにするためと、後からパターンを追加出来るためです。ポリモフィミズムもパターンマッチで対応します。
not = True -> False
| False -> True
and = _ _ -> False
| True True -> Trueパターンの追加には |= を使います。これでソースコードの後からでも追加出来ます。
or = _ _ -> True or |= False False -> False > and True False => False
パターンを使った例です。Pair~ は展開子で、データを部分に分けます。これを以下のように -> の左辺に書くと、結果が変数に束縛されます。
data Pair head tail car = Pair~ x _ -> x cdr = Pair~ _ y -> y > car (Pair 1 2) => 1
ユーザ定義パターンマッチ
引数の数さえ合えばどんな関数でも構築子や展開子として使う事が出来ますが、ややこしくなるので構築子と展開子は常に逆関数になるように設計します。
twice = x -> x * 2
twice~ = x -> if x % 2 == 0 then x / 2
else None
even -> _ -> True
twice~ _ -> False
> twice~ (twice 777) => 777
> even 1 => False
> even 2 => True
例: reverse の実装
リストを逆転する reverse の定義です。
data Nil data Pair head tail reverse xs = reverse_sub Nil xs reverse_sub y Nil = y reverse_sub y (Pair~ x xs) |= reverse_sub (Pair x y) xs
パラメータ付き展開子
上級編として、展開子は パターン, パターン, ... -> 式, 式, ... のように複数の引数を持てます。この場合最後の引数だけがパターンマッチに使われ、後はパラメータとして使います。これはパーサーを実装するのに便利です。
matchFirst~ size s = (substring s 0 size), (substring s (size + 1) (length s - 1)) firstFive = beginsWith~ 5 s rest -> Pair s rest > firstFive "Hello, World!" => Pair "Hello" ", World!"
アクセッサとしての展開子
先日の直行座標極 & 座標変換を Scala で書いた例をこの言語に直すとこんな感じです。
data Cartesian x y + |= (Cartesian ax ay), (Cartesian bx, by) -> Cartesian (ax + bx) (ay + by) > Cartesian 1 2 + Cartesian 3 4 => Cartesian 4 6 Polar = r theta -> Cartesian (r * (cos theta)) (r * (sin theta)) Polar~ = Cartesian x y -> (sqrt x * x + y * y), (atan2 y x) * |= (Polar m p), (Polar n q) -> Polar (m + n) (p + q)
ここで問題点は、 Cartesian を Polar に変換するだけなら良いのですが、その変換結果を Cartesian を戻す時の構築子 Polar の定義で明示的に Cartesian を指定している事です。他にも色々座標を現すデータがあって、変換結果を元の型に戻したい時は引数だけでなく戻り値によってもディスパッチする必要がありますが、その方法は悩み中です。
逆関数の自動生成
関数定義の -> の両辺で使われている関数に全て逆関数が存在し、変数名に増減が無ければ、構築子から展開子もしくは展開子から構築子を自動生成出来ます。自動生成される例を書きます。
swap = Pair x y -> Pair y x swap~ = Pair x y -> Pair y x rotate = UInt4 b3 b2 b1 b0 -> UInt4 b2 b1 b0 b4 rotate~ = UInt4 b2 b1 b0 b4 -> UInt4 b3 b2 b1 b0 parse3 = (x0 : x1 : x2 : []), xs -> (x0 : x1 : x2 : xs) -- [] や : は Haskell と同じ意味とする。 parse3~ = (x0 : x1 : x2 : xs) -> (x0 : x1 : x2 : []), xs
パターンマッチ言語の利点
構築子、展開子の組はそのままオブジェクト指向言語のスロットアクセッサとして考える事も出来ます。このまま継承を使わないでパターンマッチングだけでオブジェクト指向に必要な要素を全て表現出来ると予想しています。副作用の扱いは考え中です。
いわゆるアクセッサ関数を使わないで、データの中身をパターンマッチで取り出す事によってプログラムの見通しが良くなります。関数の読み方は全て、変数束縛 -> データ構築 という一方向の流れに沿って進みます。
他のパターンマッチとの違い
Scala では構築子と展開子は同じオブジェクトの別メソッドという扱いになっていますが、他のやつは二つの間に関係はありません。この言語では逆関数の生成のために関連がある事になっています。
他の言語はそれぞれ強い型付けと型推論を持っていますが、そういうのを自分で実装する自信がないので型無しでも出来そうな仕様を考えてみました。型推論の無い一番の問題は戻り値によるディスパッチが出来ない事じゃないかなーと思っています。
Haskell の View との違い。
Haskell では、
関数名 (展開子 -> パターン) = 関数本体
のように書きます。展開子が入力を分解し、その返り値をネイティブのパターンでさらに分解します。Haskell の ( (展開子 パラメータ) -> (引数, 引数, ...)) を (展開子 パラメータ 引数 引数 ...) に変換するとこの妄想言語と同じになります。
F# との違い
F# では、展開子の定義に
let (|展開子1|展開子2|) = if 条件 then 展開子1(値, 値, ...)
else 展開子2(値, 値, ...) ...のような文を使います。パターンを使う時じゃなくて定義する時に全ての条件を網羅する事が出来るのでエラーチェックに便利らしいです。強いて言うとこの妄想言語の定義は
let (|展開子1|_|) = if 条件 then 展開子1(値, 値, ...) else Nil
と同じになります。パラメータ付きパターンマッチャーの仕様は F# の真似です。
