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

## はじめに

以下の記事の続きです。

https://qiita.com/SiZK/items/cb0fce466decbae34fa6

今回は if 文をネストできるようにしていきます。

## ブロックのネスト

if 文をネストできるようにするため、ブロックのネストを実装します。
つまり、以下のような解釈ができるようにします。

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

新しい文法を取り入れるため、前回のコードの `Parse` を変更する必要があります。
同様に、それを解釈できるように `Eval` も変更します。

他にも細々とした修正は必要ですが、メインは上記二つの変更です。

<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 Operator = '+' | '-' | 'if'
type Block = (number | Operator)[]
type Value = number | Operator | Block

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

type Parse<
  Words extends any[],
  Vm extends State = { stack: []; block: null }
> = 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>
  : Val extends 'if'
  ? If<Vm>
  : { stack: [...Vm['stack'], Val]; block: null }

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

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

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
```

</details>

### `Block` の修正

まず、ブロックの中にブロックを保持できるように `Block` を修正します。

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

補足すると、`type Value = number | Operator | Block` です。

### `State` の修正

次に、ネストに対応できるように `State` を変更します。

```diff_typescript
  type State = {
    stack: Value[]
-   block: Block | null 
+   blocks: Block[]
  }
```

従来の `block` は、現在処理中のブロックを一つだけ保持していました。
これをネストに対応させるため、配列 `blocks` に変更し、ネストの深さと配列の長さを対応させます。

また、この変更に合わせて `Add` や `Sub` も、`block` ではなく `blocks` を用いるように修正します。

```diff_typescript:Add の変更

  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'] }
+   ? { stack: [...Remain, _Add<Lhs, Rhs>]; blocks: Vm['blocks'] }
    : never
```

`Sub` も同様に `blocks` に変更しておきます。
他にも追加している `Operator` があれば、それも変更しておきます。

:::note info
`stack` に `Value` を追加した `State` を返す型 `Push` を定義すると、変更箇所が減り、修正が多少楽になります。

```ts:example
type Push<Val extends Value, Vm extends State> = {
  stack: [...Vm['stack'], Val]
  blocks: Vm['blocks']
}
:::

### `Eval` の修正

次に `Eval` を修正し、ネストされたブロックを正しく処理できるようにします。

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

現在ブロックの内部を処理中かどうかの判定は、配列 `blocks` が空かどうかの判定に変更しています。
また、ブロックに `Val` を追加する処理は、`blocks` の最後の要素 `TopBlock` に `Val` を追加するよう修正しました。

### `Parse` の修正

文法上、ネストを許容するために `Parse` を修正します。

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

`{` を処理する際、これまではネストを許容していなかったため、ブロック内部の処理中かどうかを判定する条件分岐が必要でした。
しかし、今回の修正でネストを許容するようになったため、その分岐が不要になり、単純に `blocks` に空の `Block` を追加するだけで済むようになりました。

また、`}` を処理する際は、一番深いネストのブロックを取り出し、それを `Eval` へ渡す形に変更しました。
これによって、ブロックのネストが正しく評価されるようになっています。

## if 文のネスト

ブロックのネストができるようになったら、実はほとんど完了です。
`State` に合うように `If` の変更をします。

```diff_typescript
  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 {
+   ? EvalBlock<Condition, { stack: Remain; blocks: Vm['blocks'] }> extends {
        stack: [...infer NextStack extends Value[], infer Top extends number]
-       block: infer NextBlock extends Block | null
+       blocks: infer NextBlocks extends Block[]
      }
      ? Top extends 0
-       ? EvalBlock<FalseBranch, { stack: NextStack; block: NextBlock }>
-       : EvalBlock<TrueBranch, { stack: NextStack; block: NextBlocks }>
+       ? EvalBlock<FalseBranch, { stack: NextStack; blocks: NextBlock }>
+       : EvalBlock<TrueBranch, { stack: NextStack; blocks: NextBlocks }>
      : never
    : never
```

ただ単に、変更した `State` への対応をしただけの修正です。

そして `EvalBlock` を、ネストのあるブロックへの対応ができるように修正します。

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

これで、ネストのある if 文の解釈ができるようになりました。

実際にネストのある if 文が正しく計算できるかどうかを試してみます。

```ts
type Res = Parse<[
  '{', 0, '}', // condition (1)
  '{', 1, '}', // true branch (1)
  '{',         // false branch (1)
    '{', 2, '}',         // condition (2)
    '{', 3, 4, '+', '}', // true branch (2)
    '{', 5, '}',         // false branch (2)
    'if',
  '}',
  'if'
]>
// type Res = [7]
```

if 文がネストされていても、再帰的に解釈して正しく計算できていそうです。

また、ネスト内部で無駄に計算が行われていないかも確認してみます。

```ts
type Res = Parse<[
  '{', 0, '}', // condition (1)
  '{', 1, '}', // true branch (1)
  '{',         // false branch (1)
    '{', 2, '}',         // condition (2)
    '{', 3, 4, '+', '}', // true branch (2)
    '{', 5, '}',         // false branch (2)
    // 'if',             // Remove!
  '}',
  'if'
]>
// type Res = [[2], [3, 4, "+"], [5]]
```

再帰的に解釈を行うようになっても、不必要なブロック内の計算は行われていないことも確認できました。

## おわりに

ここまでの実装で、ネストされた if 文の処理ができるようになりました。

コードが徐々に複雑なものになってきましたが、これは、ブロックの中身を必要なタイミングでのみ計算する仕組みにしているためです。
一方で、`+` や `-` 等の `Operator` を見つけた時点で即座に計算を行う実装にすれば、コードはかなりシンプルになると思います。
それぞれの方法で実装して、比較してみると面白いかもしれません。

次回は、変数を扱えるようにする予定です。