# パターンマッチのコンパイル

パターンマッチはPythonにも実装されている機能である。
しかし、Ergには型検査があるため、より強力なパターンマッチが可能であり、逆に言うとPythonの機能に頼り切ったパターンマッチングは難しい。
以下には、Ergがパターンマッチをどのようにコンパイルするかを見る。

## 基本的なアルゴリズム

基本的に、すべてのパターンは「平坦化」される。具体的には、

```erg
[i, [j, k]] -> ...
```

は、

```erg
%1 ->
    i = %1[0]
    %2 = %1[1]
    j = %2[0]
    k = %2[1]
    ...
```

となる。

## 変数パターン

変数もパターンである。この場合、パターンに束縛できるかの検査は行わない。`i: Int -> ...`などと型指定されている場合は次項の型指定パターンに該当する。

## 型宣言パターン

`TypedPattern := Pattern: Type`

まず`Type`が単純型である場合を見る。
`i: Int -> ...`などとすれば`isinstance(i, Int)`と同等の検査が実行時に行われる。型がObjとなっている場合は何もしない。全てのオブジェクトがObj型であることは確定しているためである。

TypeがUnion型(e.g. `Int ot Str`)の場合は、`isinstance(i, Int) or isinstance(i, Str)`が行われる。

TypeがIntersection型(e.g. `Int and Str`)の場合は、`isinstance(i, Int) and isinstance(i, Str)`が行われる。

Typeが篩型(e.g. `{I: Int | I >= 0}`)の場合は、中の述語式を評価することで行われる。`{1}`は`{I: Int | I == 1}`の構文糖であったから、`i == 1`が行われる。

最後に、Typeが多相型・依存型(e.g. `List(Int, 3)`)の場合は定義に従って検査するべき属性・メソッドが決定される。

`F(X)`型の検査を考える。定義が`F(A <-> E) = ...`(`E`中に現れる`Self`はオブジェクト自身に置換される)であるとき、`fits(X, E)`で検査される。

```erg
fits X, E =
    if Typeof(X) == Type:
        then := do subtypeof X, E
        else := do X == E
```

`List`の定義は

```erg
List T <-> Union Self.iter().map(Typeof), N <-> Self.__len__() = ...
```

である。なので、`List(Int, 3)`の検査としては`isinstance(i, List) and subtypeof(Int, Union(i.iter().map(Typeof))) and i.__len__() == 3`が行われる。

## リテラルパターン

Ergは型とパターンを融合することによって、パターンマッチの結果を型検査に反映させることができる。
典型的なのはリテラルパターンである。

```erg
match x:
    1 -> log "one"
    "a" -> log "a"
    _ -> log "other"
```

このコードは以下のように脱糖される。

```erg
match x:
    _: {1} -> log "one"
    _: {"a"} -> log "a"
    _ -> log "other"
```

Ergの型は基本的にextrinsic(外在的)であり、型を消去したコードも動的には実行できる(型なしで項が意味を持ちうる)。これは、ErgがPythonとの相互運用性を企図して設計されているためである。
しかしパターンマッチにおいては、Ergの型はintrinsic(内在的)であるといえる。型指定自体がパターンの一つであり、型によって処理が変わるため、型消去をしたコードは最早実行できない。

## タプルパターン

```erg
(True, 1) -> ...
```

↓

```erg
%1: ({True}, {1}) ->
    _ = %1[0]
    _ = %1[1]
    ...
```

## 配列パターン

配列は型情報が平坦化されてしまうので、一工夫が必要である。具体的には、篩型を使う。

```erg
[[True, False], [True, True]] -> ...
```

↓

```erg
%1: {I: ? | } ->
    ...
```

↓

```erg
%1: {I: [[_; ?]; ?] | } ->
    %2 = %1[0]
    ...
```

↓

```erg
%1: {I: [[_; 2]; ?] | I[0][0] == True and I[0][1] == False} ->
    %2 = %1[0]
    _ = %2[0]
    _ = %2[1]
    ...
```

↓

```erg
%1: {I: [[_; 2]; 2] | I[0][0] == True and I[0][1] == False and I[1][0] == True and I[1][1] == True} ->
    %2 = %1[0]
    _ = %2[0]
    _ = %2[1]
    %3 = %1[1]
    _ = %3[0]
    _ = %3[1]
    ...
```