『F#を知ってほしい』を読んでF#に興味が湧いてきたので、F#を始めてみた。チュートリアルをやるだけだと面白くないので、手頃な習作として正規表現エンジンを作りながらF#の機能を学んでみることにした。
作るもの
ごく簡単な正規表現エンジンを作る。使えるメタ文字は以下の４つのみとする。
-
.任意の一文字にマッチ -
*0回以上の繰り返しにマッチ -
|左右どちらかにマッチ -
()グルーピング
効率は一切考えない。計算に時間がかかってもいいし、メモリを大量に使ってもいい。
ファーストステップ
正規表現を表す型 Pattern を書いていく。最初から完全なものを作るのは大変なので、まずは . か特定の一文字（例えば a) を表すものを定義する。
type Pattern =
| Char of char
| AnyChar
Pattern は判別共用体として定義される。正規表現 . は AnyChar として表現され、正規表現 a は Char 'a' と表現される。
次に与えられた文字列から Pattern にマッチする部分を取り出す関数を書こう。任意の場所にマッチさせる関数を考えるのは大変なので、文字列の先頭から始まる部分文字列 にマッチする場合のみに限定して考える。また、一般に正規表現にマッチする部分は複数個あるので、戻り値はひとつの値ではなく、値の列になる。
また、戻り値として部分文字列そのものを返す必要はない。先頭から始まる部分文字列であることはわかっているのだから、部分文字列の長さだけ返せば情報としては十分だ。
したがって、マッチ関数のシグネチャは以下のようになる。
// s の先頭から始まる部分文字列の中で pattern にマッチするものの長さを返す
let matchLengths (pattern: Pattern) (s: string) : seq<int> =
...
seq という見慣れないものが出てきたが、これは C# でいうところの IEnumerable だ。IEnumerable があるということは yield もある。後で出てくるのでお楽しみに。
では関数本体を書いていこう。
let matchLengths (pattern: Pattern) (s: string) : seq<int> =
match pattern with
| Char ch ->
if s.StartsWith ch then seq [ 1 ] else Seq.empty
| AnyChar ->
if s <> "" then seq [ 1 ] else Seq.empty
今のところ Char と AnyChar しかないのですごく簡単だ。Char の場合、s の先頭が所定の文字で始まっているならば、長さ１の文字列にマッチしたことになるので、列 [ 1 ] を返す。そうでないなら何にもマッチしないので Seq.empty を返す。AnyChar の場合、空文字列でなければ長さ１の文字列にマッチする。空文字列であれば何にもマッチしない。（等しくないことを判定する演算子は <> らしい)
（ところで、何故かこの関数は REPL ではコンパイルできなかった。s.StartsWith ch の部分で型が合わないと言われてしまう。REPL ではない普通のコンパイルではちゃんとコンパイルできた。s.StartsWith がオーバーロードされていることと関係がありそうな気がするがよくわからない。）
matchLengths を試してみよう。
matchLengths (Char 'a') "a"
|> Seq.toList
|> printfn "%A" // [1] が出力される
matchLengths (Char 'a') "b"
|> Seq.toList
|> printfn "%A" // [] が出力される
無事期待通りの結果になった。|> はパイプ演算子というらしい。これは左辺の値を右辺の関数に渡す演算子で、これを使うと Ruby のメソッドチェインのような雰囲気でコードを書くことができる。
Alternation
次に | を含む正規表現を使えるようにしよう。Pattern の定義を以下のように拡張する。
type Pattern =
| Char of char
| AnyChar
| Alter of Pattern * Pattern
Alter は Pattern を２つ取るような再帰的な定義になっている。
Alter lhs rhs にマッチする文字列 s の部分文字列は、lhs にマッチする部分文字列と rhs にマッチする部分文字列の和集合だ。これを matchLengths に実装すると以下のようになる。
let rec matchLengths (pattern: Pattern) (s: string) : seq<int> =
match pattern with
| Char ch ->
if s.StartsWith ch then seq [ 1 ] else Seq.empty
| AnyChar ->
if s <> "" then seq [ 1 ] else Seq.empty
| Alter (lhs, rhs) ->
seq {
yield! matchLengths lhs s
yield! matchLengths rhs s
}
seq { ... } はコンピュテーション式と呼ばれるものらしい。（私はまだコンピュテーション式をいまいちよく理解できていない）
seq { ... } の中では yield や yield! といった構文が使える。例えば seq { yield 1; yield 2 } を評価すると seq [1; 2] が返る。
一方、yield! は yield と似ているが一回 flatten する。例えば
let s1 = seq [1; 2]
let s2 = seq [3; 4]
seq { yield! s1; yield! s2 }
は seq [1; 2; 3; 4] を返す。
したがって、
seq {
yield! matchLengths lhs s
yield! matchLengths rhs s
}
は lhs にマッチした部分文字列と rhs にマッチした部分文字列を連結した列になる。
また、seq { ... } は C# の generator と同じように、値が要求されるまで計算が遅延させられる。これを使うと無限シーケンスを定義したりもできるらしい。（今回の例では有限のシーケンスしか登場しない）
Concatenation と Repeat
残るは連結と*だ。さらに空文字列にマッチするパターンも必要だ。Pattern の定義に Zero, Repeat, Concat を加えよう。
type Pattern =
| Zero
| Char of char
| AnyChar
| Alter of Pattern * Pattern
| Repeat of Pattern
| Concat of Pattern * Pattern
matchLengths の実装は以下のようになる。Repeat は空文字列にマッチする場合の処理が微妙にいやらしい。それ以外は結構直観的な実装になっていると思う。
let rec matchLengths (pattern: Pattern) (s: string) : seq<int> =
match pattern with
| Zero ->
seq [ 0 ]
| Char ch ->
if s.StartsWith ch then seq [ 1 ] else Seq.empty
| AnyChar ->
if s <> "" then seq [ 1 ] else Seq.empty
| Alter (lhs, rhs) ->
seq {
yield! matchLengths lhs s
yield! matchLengths rhs s
}
| Concat (head, tail) ->
seq {
for n1 in matchLengths head s do
for n2 in matchLengths tail (s.Substring n1) do
yield n1 + n2
}
| Repeat inner ->
seq {
for n1 in matchLengths inner s do
if n1 = 0 then
yield 0
else
for n2 in matchLengths pattern (s.Substring n1) do
yield n1 + n2
yield 0
}
seq { ... } の中では for .. in .. do .. という構文が使える。ネストもできる。この関数では使っていないが、if を使ってフィルタすることもできるらしい。
これで正規表現のマッチャーは完成した。試してみよう。
// <(.*)> を表す Pattern
let p = Concat (Char '<', Concat (Repeat AnyChar, Char '>'))
let s = "<hello>world</hello>"
matchLengths p s
|> Seq.toList
|> printfn "%A"
実行すると [20; 7] が出力された。<hello>world</hello> が20文字で <hello> が7文字なので正しく動いているようだ。やったね 
次回コンパイル編？
現状では正規表現を使うためには Pattern を直接組み立てないといけない。これは不便だ。そこで ab*|c.d のような馴染みのある表記から Pattern にコンパイルするコードを書いたので、モチベが続けば次回紹介したい。