はじめに

以下の記事の続きです。

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

if 文

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

{ condition } { true_branch } { false_branch } if

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

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

ブロック

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

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

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

前回の実装からの変更

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

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

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

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

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

前回のコード

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

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

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

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 では、ブロック内部であればブロックに値を入れるようにし、それ以外の場合は今までと同じ処理をするようにします。

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 }

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

if 文の実装

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

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

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

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

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 を実装します。
ブロックの中身を前から見ていって、スタックに詰めていく処理をします。

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 を実装します。

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

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

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 文の処理ができるようになりました。
本当はブロックをネストさせる処理まで書くつもりだったのですが、思ったより長くなったので次回にしようと思います。

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