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

はじめに

TypeScript の型システムでスタックベース言語のインタープリターを実装していきます。

一つの記事で実装について書いていくと、かなり大きくなってしまうので、複数回に分けて書いていく予定です。
この記事では、逆ポーランド記法での四則演算を解釈できるようにするところまでを書きます。

前準備

TypeScript の型システムでは四則演算を扱えるようにするだけでもかなり面倒なので、今回実装するスタックベースの言語では加算と減算のみを扱うことにします。

とはいえ加算と減算も自分で実装する必要があるので、まずは型システムで加算と減算を扱えるようにしておきます。

この部分はメインではないので、できる限り簡単な実装を採用することにしています。
数値と配列の長さを対応づけるようにして、加算と減算を以下のように定義します。

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

軽く説明を書くと以下の通りです。

• _Repeat: T の長さを持つ配列を返す
• _Length: 配列 T の長さを返す
• _Add: T の長さを持つ配列と U の長さを持つ配列を結合した配列の長さを返す
• _Sub: T の長さを持つ配列から U の長さの分だけ削除した配列の長さを返す
  • T よりも U の方が大きい場合は never を返す

簡単のため、非負整数は扱わないようにしています。

また、型名の接頭辞に _ を付けているのは、メインの実装部分と区別するためです。

これで、加算と減算が定義できたので、スタックベース言語の実装に入っていきます。

逆ポーランド記法

逆ポーランド記法で書かれた数式が処理できるようになることを目指します。
例えば 4 3 + 2 - と入力されたら 5 を返すようにします。

ただ、これを文字列と捉えてパースを行う場合、型 string としての数字と型 number としての数値を対応させる必要があります。
これは少々面倒なので、この記事では楽ができるように、文字列でなく配列を与えるようにします。
つまり、

type Res = Parse<[4, 3, '+', 2, '-']>
// type Res = [5]

となるような型 Parse を実装します。

加算の実装

まずは加算ができるようにします。

スタックから2つの値をポップし、加算した結果をプッシュしたものを返す、

type Res = Add<[1, 2, 3, 4]>
// type Res = [1, 2, 7]

上記のような型 Add を実装します。

ここでは配列の末尾をスタックのトップとして扱っています。

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

スタックから値を2つポップができない場合や、ポップした値が数値でない場合には、加算ができないので never を返すようにしています。

この記事では、基本的にエラーとみなされる状況の場合は never を返すように実装していきます。

これを利用して型 Parse も実装していきます。

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>>
    : never
  : Stack

Words の先頭から見ていって、数値だったらスタックにプッシュする、そうでなければ加算の処理を行う、という型です。

分かりやすい形に変換したコード

少し分かりづらいので、上記のコードで行っていることと同等の TypeScript のコードを以下に示します。

function parse(words: any[]) {
  let stack: any[] = []

  for (const word of words) {
    if (typeof word === 'number') {
      stack.push(word)
    } else if (word == '+') {
      // stack に対して加算の処理をする
    } else {
      return
    }
  }

  return stack
}

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

type Res = Parse<[1, 2, '+', 4, '+']>
// type Res = [7]

問題なく逆ポーランド記法での加算ができていそうです。

減算の実装

次は減算も実装していきます。
とはいっても、先程のコードと大きく変わりません。

まずは減算を行う型 Sub を定義します。

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

これは、型 Add と大して違いはありません。

型 Sub も利用するように型 Parse を変更します。

 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 Res = Parse<[4, 3, '+', 2, '-']>
// type Res = [5]

加算と減算を混ぜた計算もできていそうです。

他の二項演算を解釈できるようにしたい場合も、型 _Sub のように実装さえできていれば(TypeScript ではここが難しいですが)、簡単に追加することができます。

おわりに

ここまでの実装で逆ポーランド記法での加減算ができるようになりました。
数値でなく boolean を扱うようなものであれば、二項演算の追加もそこまで難しくないと思うので、実装してみると面白いかもしれません。

次の記事では if 文を扱えるようにする予定です。