F#に入門したので正規表現エンジンを書いてみた

[『F#を知ってほしい』](https://qiita.com/cannorin/items/59d79cc9a3b64c761cd4)を読んでF#に興味が湧いてきたので、F#を始めてみた。チュートリアルをやるだけだと面白くないので、手頃な習作として正規表現エンジンを作りながらF#の機能を学んでみることにした。

## 作るもの

ごく簡単な正規表現エンジンを作る。使えるメタ文字は以下の４つのみとする。

- `.` 任意の一文字にマッチ
- `*` 0回以上の繰り返しにマッチ
- `|` 左右どちらかにマッチ
- `()` グルーピング

効率は一切考えない。計算に時間がかかってもいいし、メモリを大量に使ってもいい。

## ファーストステップ

正規表現を表す型 `Pattern` を書いていく。最初から完全なものを作るのは大変なので、まずは `.` か特定の一文字（例えば `a`) を表すものを定義する。

```fsharp
type Pattern =
    | Char of char
    | AnyChar
```

`Pattern` は[判別共用体](https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/discriminated-unions)として定義される。正規表現 `.` は `AnyChar` として表現され、正規表現 `a` は `Char 'a'` と表現される。

次に与えられた文字列から `Pattern` にマッチする部分を取り出す関数を書こう。任意の場所にマッチさせる関数を考えるのは大変なので、**文字列の先頭から始まる部分文字列** にマッチする場合のみに限定して考える。また、一般に正規表現にマッチする部分は複数個あるので、戻り値はひとつの値ではなく、値の列になる。

また、戻り値として部分文字列そのものを返す必要はない。先頭から始まる部分文字列であることはわかっているのだから、部分文字列の長さだけ返せば情報としては十分だ。

したがって、マッチ関数のシグネチャは以下のようになる。

```fsharp
// s の先頭から始まる部分文字列の中で pattern にマッチするものの長さを返す
let matchLengths (pattern: Pattern) (s: string) : seq<int> =
    ...
```

`seq` という見慣れないものが出てきたが、これは C# でいうところの `IEnumerable` だ。`IEnumerable` があるということは `yield` もある。後で出てくるのでお楽しみに。

では関数本体を書いていこう。

```fsharp
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` を試してみよう。

```fsharp
matchLengths (Char 'a') "a"
|> Seq.toList
|> printfn "%A" // [1] が出力される

matchLengths (Char 'a') "b"
|> Seq.toList
|> printfn "%A" // [] が出力される
```

無事期待通りの結果になった。`|>` はパイプ演算子というらしい。これは左辺の値を右辺の関数に渡す演算子で、これを使うと Ruby のメソッドチェインのような雰囲気でコードを書くことができる。

## Alternation

次に `|` を含む正規表現を使えるようにしよう。`Pattern` の定義を以下のように拡張する。

```fsharp
type Pattern =
    | Char of char
    | AnyChar
    | Alter of Pattern * Pattern
```

`Alter` は `Pattern` を２つ取るような再帰的な定義になっている。

`Alter lhs rhs` にマッチする文字列 `s` の部分文字列は、`lhs` にマッチする部分文字列と `rhs` にマッチする部分文字列の和集合だ。これを `matchLengths` に実装すると以下のようになる。

```fsharp
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 { ... }` は[コンピュテーション式](https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/computation-expressions)と呼ばれるものらしい。（私はまだコンピュテーション式をいまいちよく理解できていない）

`seq { ... }` の中では `yield` や `yield!` といった構文が使える。例えば `seq { yield 1; yield 2 }` を評価すると `seq [1; 2]` が返る。

一方、`yield!` は `yield` と似ているが一回 flatten する。例えば

```fsharp
let s1 = seq [1; 2]
let s2 = seq [3; 4]
seq { yield! s1; yield! s2 }
```

は `seq [1; 2; 3; 4]` を返す。

したがって、

```fsharp
seq {
    yield! matchLengths lhs s
    yield! matchLengths rhs s
}
```

は `lhs` にマッチした部分文字列と `rhs` にマッチした部分文字列を連結した列になる。

また、`seq { ... }` は C# の generator と同じように、値が要求されるまで計算が遅延させられる。これを使うと無限シーケンスを定義したりもできるらしい。（今回の例では有限のシーケンスしか登場しない）

## Concatenation と Repeat

残るは連結と`*`だ。さらに空文字列にマッチするパターンも必要だ。`Pattern` の定義に `Zero`, `Repeat`, `Concat` を加えよう。

```fsharp
type Pattern =
    | Zero
    | Char of char
    | AnyChar
    | Alter of Pattern * Pattern
    | Repeat of Pattern
    | Concat of Pattern * Pattern
```

`matchLengths` の実装は以下のようになる。`Repeat` は空文字列にマッチする場合の処理が微妙にいやらしい。それ以外は結構直観的な実装になっていると思う。

```fsharp
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` を使ってフィルタすることもできるらしい。

これで正規表現のマッチャーは完成した。試してみよう。

```fsharp
// <(.*)> を表す 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文字なので正しく動いているようだ。やったね :tada: 

## 次回コンパイル編？

現状では正規表現を使うためには `Pattern` を直接組み立てないといけない。これは不便だ。そこで `ab*|c.d` のような馴染みのある表記から `Pattern` にコンパイルするコードを書いたので、モチベが続けば次回紹介したい。