TypeScript の型システムでスタックベースの言語を実装する（2）

## はじめに

以下の記事の続きです。

https://qiita.com/SiZK/items/68e3f260bc629253532d

今回は if 文を実装していきます。

## if 文

この記事では、以下のような if 文を解釈できるようにしていきます。

```
{ condition } { true_branch } { false_branch } if
```

これは `condition` の結果が 0 以外であれば `true_branch` を評価し、0 であれば `false_branch` を評価するようなものです。

`{}` で囲まれたブロックを解釈できるように、まずはブロックの実装からしていきます。

### ブロック

以下のような解釈ができるように、ブロックの実装をしていきます。

```ts
type Res = Parse<[1, '{', 2, 3, '+', '}', 4]
// type Res = [1, [2, 3, '+'], 4]
```

ブロックの内部に演算子があっても処理しないようにしているのに注意してください。
これは、ブロック内部を処理するかどうかを後から決められるようにするためです。
例えば、if 文の条件が truthy な時に `false_branch` 内部の処理をするのは無駄がある、というようなところから来ています。

#### 前回の実装からの変更

前回まではスタックに `number` 以外の型は入らないような実装になっていましたが、今回はブロックが入るようになります。
また、ブロックには `number` と演算子を表す文字列型が入ります。
なので、まずはそのように型を定義しておきます。

```ts
type Operator = '+' | '-'
type Block = (number | Operator)[]
type Value = number | Operator | Block
```

また、今ブロックの内部で処理をしているのか、そうでないのかを判断できるように、スタックに追加で情報を持たせるようにします。

```ts
type State = {
  stack: Value[]
  block: Block | null
}
```

ブロックの実装へ入る前に、これらを使って前回のコードを変更しておきます。

<details><summary>前回のコード</summary>

```ts
type _Repeat<T extends number, U extends any[] = []> = _Length<U> extends T
  ? U
  : _Repeat<T, [any, ...U]>
type _Length<T extends any[]> = T['length']
type _Add<T extends number, U extends number> = _Length<
  [..._Repeat<T>, ..._Repeat<U>]
>
type _Sub<T extends number, U extends number> = _Repeat<T> extends [
  ..._Repeat<U>,
  ...infer Remain
]
  ? _Length<Remain>
  : never

type Parse<Words extends any[], Stack extends any[] = []> = Words extends [
  infer Word,
  ...infer Remain
]
  ? Word extends number
    ? Parse<Remain, [...Stack, Word]>
    : Word extends '+'
    ? Parse<Remain, Add<Stack>>
    : Word extends '-'
    ? Parse<Remain, Sub<Stack>>
    : never
  : Stack

type Add<Stack extends any[]> = Stack extends [
  ...infer Remain,
  infer Lhs extends number,
  infer Rhs extends number
]
  ? [...Remain, _Add<Lhs, Rhs>]
  : never

type Sub<Stack extends any[]> = Stack extends [
  ...infer Remain,
  infer Lhs extends number,
  infer Rhs extends number
]
  ? [...Remain, _Sub<Lhs, Rhs>]
  : never
```

</details>

まず、`Add` と `Sub` を型 `State` を利用するように変更します。

```ts
type Add<Vm extends State> = Vm['stack'] extends [
  ...infer Remain extends Value[],
  infer Lhs extends number,
  infer Rhs extends number
]
  ? { stack: [...Remain, _Add<Lhs, Rhs>]; block: Vm['block'] }
  : never

type Sub<Vm extends State> = Vm['stack'] extends [
  ...infer Remain extends Value[],
  infer Lhs extends number,
  infer Rhs extends number
]
  ? { stack: [...Remain, _Sub<Lhs, Rhs>]; block: Vm['block'] }
  : never
```

それにあわせて、`Parse` を変更します。

```ts
type Parse<
  Words extends any[],
  Vm extends State = { stack: []; block: null }
> = Words extends [infer Word, ...infer Remain]
  ? Word extends number | Operator
    ? Parse<Remain, Eval<Word, Vm>>
    : never
  : Vm['stack']

type Eval<Val extends Value, Vm extends State> =
  Val extends '+'
    ? Add<Vm>
    : Val extends '-'
    ? Sub<Vm>
    : { stack: [...Vm['stack'], Val]; block: null }
```

ついでに、命令列を解釈する部分の `Parse` と、スタックを用いた処理を行う `Eval` に分けています。

これをブロックの解釈ができるように変更をしていきます。

#### ブロックの実装

`Parse` では、`{` があればブロックを作成するようにし、`}` があればスタックにブロックを渡すようにします。
また `Eval` では、ブロック内部であればブロックに値を入れるようにし、それ以外の場合は今までと同じ処理をするようにします。

```diff_typescript
type Parse<
  Words extends any[],
  Vm extends State = { stack: [] }
> = Words extends [infer Word, ...infer Remain]
+  ? Word extends '{'
+    ? Vm['block'] extends Block
+      ? never
+      : Parse<Remain, { stack: Vm['stack']; block: [] }>
+    : Word extends '}'
+    ? Vm['block'] extends Block
+      ? Parse<Remain, Eval<Vm['block'], { stack: Vm['stack']; block: null }>>
+      : never
    : Word extends number | Operator
    ? Parse<Remain, Eval<Word, Vm>>
    : never
  : Vm['stack']

type Eval<Val extends Value, Vm extends State> =
+  Vm['block'] extends Block
+    ? { stack: Vm['stack']; block: [...Vm['block'], Val] }
    : Val extends '+'
    ? Add<Vm>
    : Val extends '-'
    ? Sub<Vm>
    : { stack: [...Vm['stack'], Val]; block: null }
```

:::note warn
分かりやすさのため、変更箇所に diff を付けていますが、正確なものではありません。
:::

### if 文の実装

ブロックの実装ができたので、これを用いて if 文を実装していきます。

まずは、型 `Operator` に `if` を追加します。

```ts
type Operator = '+' | '-' | 'if'
```

`Eval` にも `if` を処理できるように追加をします。

```ts
type Eval<Val extends Value, Vm extends State> =
  Vm['block'] extends Block
    ? { stack: Vm['stack']; block: [...Vm['block'], Val] }
    : Val extends '+'
    ? Add<Vm>
    : Val extends '-'
    ? Sub<Vm>
    : Val extends 'if'
    ? If<Vm>
    : { stack: [...Vm['stack'], Val]; block: null }
```

そして、ブロックを後から処理できるようにする `EvalBlock` を実装します。
ブロックの中身を前から見ていって、スタックに詰めていく処理をします。

```ts
type EvalBlock<Values extends Block, Vm extends State> = Values extends [
  infer Val extends number | Operator,
  ...infer Remain extends Block
]
  ? EvalBlock<Remain, Eval<Val, Vm>>
  : Vm
```

後は `EvalBlock` を使って `If` を実装します。

```ts
type If<Vm extends State> = Vm['stack'] extends [
  ...infer Remain extends Value[],
  infer Condition extends Block,
  infer TrueBranch extends Block,
  infer FalseBranch extends Block
]
  ? EvalBlock<Condition, { stack: Remain; block: Vm['block'] }> extends {
      stack: [...infer NextStack extends Value[], infer Top extends number]
      block: infer NextBlock extends Block | null
    }
    ? Top extends 0
      ? EvalBlock<FalseBranch, { stack: NextStack; block: NextBlock }>
      : EvalBlock<TrueBranch, { stack: NextStack; block: NextBlock }>
    : never
  : never
```

これで実装がうまくできているか試してみます。

```ts
type Res1 = Parse<['{', 1, '}', '{', 1, 2, '+', '}', '{', 4, 3, '-', '}', 'if']>
// type Res1 = [3]

type Res2 = Parse<
  ['{', 1, 1, '-', '}', '{', 1, 2, '+', '}', '{', 4, 3, '-', '}', 'if']
>
// type Res2 = [1]
```

条件が True のときも False のときも、正しく計算できていそうです。

## おわりに

ここまでで、ブロックの概念を実装して if 文の処理ができるようになりました。
本当はブロックをネストさせる処理まで書くつもりだったのですが、思ったより長くなったので次回にしようと思います。

というわけで、次の記事ではブロックのネストを扱えるようにする予定です。

(追記)以下は次回の記事です。

https://qiita.com/SiZK/items/21ea9d8599dd6d87147d