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

はじめに

以下の記事の続きです。

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

ブロックのネスト

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

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

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

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

前回までのコード

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

Block の修正

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

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

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

State の修正

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

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

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

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

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 があれば、それも変更しておきます。

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

example

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

Eval の修正

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

- 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 を修正します。

  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 の変更をします。

  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 を、ネストのあるブロックへの対応ができるように修正します。

  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 文が正しく計算できるかどうかを試してみます。

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 文がネストされていても、再帰的に解釈して正しく計算できていそうです。

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

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 を見つけた時点で即座に計算を行う実装にすれば、コードはかなりシンプルになると思います。
それぞれの方法で実装して、比較してみると面白いかもしれません。

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