TypeScriptで型レベル四則演算

こちらはエムスリー Advent Calendar 2024 9日目の記事です。

こんにちは。4月に新卒でデジスマチームにジョインしたソフトウェアエンジニアの池奥です。先日京都で開催されたTSKaigi Kansai 2024ではコアスタッフとして活動していました。 私の所属するデジスマチームではフロントエンドにTypeScriptが採用されており、型の柔軟性を活かした実装をたびたび見かけます。そこで今回は、TypeScriptの型ともっと仲良くなるべく、型レベルで四則演算のパーサーから実行器まで実装した話をお送りします。

今回作成したプログラムを利用すると、次のような計算を型レベルで行うことができます。

// 四則演算（といいつつ割り算は未実装...ｽﾐﾏｾﾝ）
type Result1 = Eval<"12*3+5*7+(2+45)*2-4"> 
//   ^ 161

// 文字列も扱えます。フォローしてね
type Result2 = Eval<"len('@m3_engineering')">
//   ^ 15

// castやlenなどの組み込み関数、変数も作ってみました
type Result3 = Eval<"word+'の文字数は'+cast(len(word),'str')+'文字です'", { word: "Alice in Wonderland" }>
//   ^ "Alice in Wonderlandの文字数は19文字です"

// 比較演算やブール値ももちろん
type Result4 = Eval<"len('@m3_engineering')<=2*2*2*2">
//   ^ true

実は四則演算だけでなく、比較演算子や優先順位を指定する括弧もサポートしています。ほかにも、文字列やブール値を扱えたり、組み込み関数（len、cast）をサポートしていたり、評価時に変数の値を外部から指定できたりする機能も備えています。なお、割り算は自然数の範囲から外れてしまうためサポート外としました。

はじめに

この記事では、大まかな処理の流れを説明していきたいと思います。実際のコードは GitHub - yuta-ike/ts-type-level-parser に置いてあります。

実際に動かしてみたい場合も、レポジトリのREADMEにTypeScript Playgroundへのリンクがありますのでご利用ください！

github.com

前提知識: 型レベルのパターンマッチ

TypeScript（の型レベル）では文字列のパターンマッチを実装することができます。たとえば次のコードでは、ある文字列（正確には文字列のリテラル型）が与えられたとき、その文字列が@または#から始まる場合に、それ以降に続く文字列を取り出す型となっています。TypeScriptに詳しくなくても、雰囲気は掴んでいただけるのではないでしょうか。

type Example<T extends string> =
  T extends `@${infer Username}` ? Username :
  T extends `#${infer Hashtag}` ? Hashtag : never

type Result1 = Example<"@m3_engineering">    // "m3_engineering"
type Result2 = Example<"#アドベントカレンダー">    // "アドベントカレンダー"
type Result3 = Example<"エムスリー">            // never

@${infer Username} はTemplate Literal Types（テンプレートリテラル型）と呼ばれます。テンプレートリテラル自体はJavaScriptにある文法ですが、その型バージョンという位置付けです。

A extends B ? C : D はConditional Typesと呼ばれ、型レベルで条件分岐を実現できます。A型がB型に代入可能な場合はC型が、そうでない場合はD型が返ります。

infer は extendsの右辺の位置で利用できるキーワードです。マッチした部分を新しい型変数にバインドできるような機能です。TypeScript4.7からは、さらにextendsキーワードを伴うことができ、もう一段細かいパターンマッチを簡単に書けるようになりました。

これを利用すると、次のように、1桁の数字のみを取得する、という処理をシンプルに実現できます。

type DigitValue = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

type Example<T extends string> =
  T extends `+${infer N extends DigitValue}` ? N : never

type Result1 = Example<"+1"> // "1"
type Result2 = Example<"+99"> // never
type Result2 = Example<"+abc"> // never

処理の流れ

今回の処理系は、Tokenizer、Parser、Evaluatorの3つの部分に分かれています。 Tokenizerは文字列のプログラムを受け取り、トークンに変換します。+や&&などの記号、文字列や数字のリテラルなどを扱いやすい形に変換します。

Parserは、受け取ったトークン列を抽象構文木（AST）のツリー構造に変換します。こちらもパターンマッチを多用して実装します。

最後にEvaluatorです。抽象構文木（AST）を元に実際に計算を行います。計算の処理自体はASTを巡回していくだけなのでシンプルですが、計算処理自体も型レベルで行わなければならず、こちらの対応の方が大変でした。

Tokenizer

今回のコードベース全体はGitHubにアップしているのでそちらを見てください。以下はTokenizerの抜粋です。処理はシンプルで、冒頭で説明したような文字列パターンマッチを再帰的に呼び出す形です。Tokenizerに限らず、型レベルでの繰り返し計算は基本的に再帰を使うので、頭の体操に良いです。

type DigitValue = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

type Tokenizer<Program extends string> =
   Program extends "" ? [] :
   Program extends `${infer Num extends DigitValue}${infer Rest extends string}`? [NumLiteral<Num>, ...Tokenizer<Rest>] :
   Program extends `+${infer Rest extends string}` ? [Operator<Plus>, ...Tokenizer<Rest>] :
   Program extends `-${infer Rest extends string}` ? [Operator<Minus>, ...Tokenizer<Rest>] :
   Program extends `*${infer Rest extends string}` ? [Operator<Mul>, ...Tokenizer<Rest>] :
   [Err<never, `Unknown token: ${Program}`>]

ちなみにこちらの実装では、数字は1桁のみとしています。複数桁を受け入れるには追加の処理が必要になりますので、気になる方はGitHubをご参照ください。

Tokenizerを実装すると、次のような出力が得られるようになります。ただの文字列の数式が、後続のParserで扱いやすいようなトークン列に変換されていることが分かります。

type Result = Tokenizer<"3+9*7">

// Result型の推論結果
[NumLiteral<"3">, Operator<typeof plus>, NumLiteral<"7">, Operator<typeof mul>, NumLiteral<"9">]

Parser

続いてパーサーです。処理系の肝となる部分ですね。まずは四則演算のみを考えます。BNF記法っぽく表現すると次のようになります。（実際はいろいろ文法を拡張したため、もっと複雑になっています）

expr   = expr "+" term | expr "-" term | term
term   = term "*" factor | factor
factor = num | "(" expr ")"
num    = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

登場人物は expr（足し算・引き算）、term（掛け算）、factor、numの4つです。それぞれのパーツごとに、Parserを書いていきます。

Termは以下のような形になります。termは、掛け算があるパターンと、factorをそのまま持ってくるパターンの2通りあります。そこで、まず与えられたトークン列をFactorParserに食わせます。そして、factorの次にあるトークンがアスタリスクかどうかで、どちらのパターンに当てはまるかが判断できます。同様の処理をexpr、factor、numの分も実装することでParserが実現できます。

// Term
// 基本仕様: Token[]を受け取り評価する。[評価結果のAST(Ast), 未評価のトークン列(Token[])]のタプルを返す。
type TermParser<Tokens extends Token[]> =
 FactorParser<Tokens> extends [infer Ast extends AstType, [infer Op extends Operator<Mul>, ...infer Rest extends Token[]]] ?
   (
     TermParser<Rest> extends [infer RightAst, infer RightRest extends Token[]] ?
       [
         {
           type: "term",
           left: Ast,
           operator: Op
           right: RightAst
         },
         RightRest
       ]:
       [
         {
           type: "term",
           left: Ast,
           operator: Op
           right: Err<"Error at TermParser 2", TermParser<Rest>>
         },
         Err<"Error at TermParser 2", TermParser<Rest>>
       ]
   ):
 FactorParser<Tokens> extends [infer Ast, infer Rest] ?
   [Ast, Rest]:
   Err<"Error at TermParser", FactorParser<Tokens>>

私は処理系にはあまり詳しくないのですが、四則演算で多く用いられる再起下降構文解析というアルゴリズムを利用しています。インターネットを検索するとたくさん実装が見つかるのですが、多くの実装では「今何トークン目まで処理が終わっているか」をindexなどのint型の変数で管理しています。しかし、型レベルでの実装では一時変数を使う方法が難しいです。 そこで今回は、常に再帰関数が[評価結果のAST(Ast), 未評価のトークン列(Token[])]というタプルを返すような実装にしています。未評価のトークン列(Token[])を保持しておくことで、indexがなくてもどこまで処理が終わっているかを判断することができます。

Parserまで実装すると、次のような出力が得られます。無事、数式を構文木の形に変換することができました。

type Result = Parser<Tokenizer<"3+7*9">>

// Result型の推論結果
{
   type: "expr";
   left: NumLiteral<"3">;
   operator: Operator<typeof plus>;
   right: {
       type: "term";
       left: NumLiteral<"7">;
       operator: Operator<typeof mul>;
       right: NumLiteral<"9">;
   };
}

Evaluator

最後に実行部分を実装していきます。通常のTypeScriptの実装であれば、構文木を走査して実際の四則演算を実行していけば結果が求まります。しかし、同様の処理を型レベルで行おうとするとぶち当たる問題が、Number型の演算ができない問題です。

たとえば、単に1+2を計算したくとも、素直にはできません。

type One = 1
type Two = 2
type Result = One + Two // NG: 型レベルでは"+"は使えない

そこで、配列の長さを利用して計算を行うことを考えます。数字の1は長さ1の配列、数字の2は長さ2の配列に変換し、スプレッド演算子を利用して配列をマージします。スプレッド演算子はJavaScriptの機能ですが、TypeScriptでも型レベルで同様の操作が可能です。

type One = [true]        // 長さが数字を表す
type Two = [true, true]

type Result = [...One, ...Two]  // Result型は [true, true, true] と推論される
type ResultNumber = Result["length"]  // Result型のlengthを読み出すことで、数字に変換できる

この辺りはデジスマチームの堀田さんが過去にTechBlogなどで紹介していますので、ご参照ください！今回の私の実装は非常にナイーブなものですが、もっと工夫のしがいがありそうです。 https://www.m3tech.blog/entry/2022/05/27/110916 https://hrtyy.dev/anything/typed-circuit/

配列の形に変換さえしてしまえば、足し算はもちろん、引き算や掛け算も簡単です。例えばA-Bの引き算は、AとBから1づつ引いていく操作を繰り返し、Bが0になるまで再帰します。 とはいえ、number型を使えないために、自然数やその演算を、その名の通り0から定義していくことになり、少し大変です。

declare const n:unique symbol
type N = typeof n
type Num = N[]
type DigitToNat<Digi extends DigitValue> =
 Digi extends "0" ? [] :
 Digi extends "1" ? [N] :
 Digi extends "2" ? [N,N,] :
 Digi extends "3" ? [N,N,N,] :
 Digi extends "4" ? [N,N,N,N,] :
 Digi extends "5" ? [N,N,N,N,N,] :
 Digi extends "6" ? [N,N,N,N,N,N,] :
 Digi extends "7" ? [N,N,N,N,N,N,N,] :
 Digi extends "8" ? [N,N,N,N,N,N,N,N,] :
 Digi extends "9" ? [N,N,N,N,N,N,N,N,N,] : never
type NatToNum<Nat extends N[]> = Nat["length"]

type NatAdd<A extends N[], B extends N[]> = [...A, ...B]
type NatSub<A extends N[], B extends N[]> =
 [A, B] extends [[any, ...infer RestA extends N[]], [any, ...infer RestB extends N[]]] ?
   NatSub<RestA, RestB>:
 B extends [] ?
   A:
   never
type NatMul<A extends N[], B extends N[]> =
 B extends [any, ...infer Rest extends N[]] ? [...A, ...NatMul<A, Rest>] : []

最後に、Parserが出力した抽象構文木を、実際に走査しながら計算していくフェーズになります。こちらも木構造を再帰的にたどりながら地道に計算していきます。現段階では主に演算子を見ながら実際の計算を適用していくだけです。

type EvaluatorRec<Ast extends AstType> =
 Ast extends {type: "num"} ? DigitToNat<Ast["value"]> :
 Ast extends {type: "term", operator: Operator<Mul>, left: infer Left extends AstType, right: infer Right extends AstType} ? (
   [EvaluatorRec<Left>, EvaluatorRec<Right>] extends [infer L extends Num, infer R extends Num] ? NatMul<L, R> : never
 ):
 Ast extends {type: "expr", operator: Operator<Plus>, left: infer Left extends AstType, right: infer Right extends AstType} ? (
   [EvaluatorRec<Left>, EvaluatorRec<Right>] extends [infer L extends Num, infer R extends Num] ? NatAdd<L, R> : never
 ):
 Ast extends {type: "expr", operator: Operator<Minus>, left: infer Left extends AstType, right: infer Right extends AstType} ? (
   [EvaluatorRec<Left>, EvaluatorRec<Right>] extends [infer L extends Num, infer R extends Num] ? NatSub<L, R> : never
 ):
 never

type Evaluator<Ast extends AstType> = EvaluatorRec<Ast> extends infer Result extends N[] ? NatToNum<Result> : never

実装の概観は以上となります。

最後に、Tokenizer、Parser、Evaluatorを組み合わせて実行すると、数式の答えを得ることができました！

type Y = Evaluator<Parser<Tokenizer<"8-4+3">>>
//   ^ 1

テスト

型レベルであっても、テストは欠かせません。今回は、Type Challengeの正誤判定で利用されているExpect型、Equal型を利用しました。この実装はnpmでも公開されており、今回の開発環境であるTypeScript Playground内で直接importして利用しました。

import type { Equal, Expect } from '@type-challenges/utils'

type cases2 = [
 // 複雑な演算ができる
 Expect<Equal<Eval<"4*3+2">, 14>>,
 Expect<Equal<Eval<"4+3*2">, 10>>,
 Expect<Equal<Eval<"4*3-2">, 10>>,
]

æ‹¡å¼µ

主に以下の拡張を行いました。

• 複数桁の自然数も扱えるようにする
• Bool値の処理を追加し、比較演算子（=、!=、<、>、<=、>=）、論理演算子（&&, ||）を追加しました。Number型と違い、Bool型は型レベルでの計算が容易なので実装は簡単でした。
• 文字列リテラル・文字列の演算（+）を実装。+が自然数と文字列の両方で利用されるためポリモーフィックになります。
• 関数呼び出しの構文を追加。2種類の組み込み関数（文字列の長さを返すlenと、文字列と自然数の変換を行うcast）を追加。()が数式の優先順位の指定と関数呼び出しの両方で利用されるためポリモーフォックになります。
• 変数を追加。外部から環境変数を入力できる仕組みを追加。{a: 3} のようなオブジェクト型を与えることで、式中のaという変数に3がバインドされます。

特に関数呼び出しは一部先読み的な実装が必要だったりと大変でした。今の実装が果たして本当に適切なのか分からないので、後日しっかり調べてみたいと思います。

まとめ

大学で習った言語処理系の知識とTypeScriptの型力、そして再帰力をフルに使う良い問題でした！皆さんも年末年始でチャレンジしてみてはいかがでしょうか！

We are hiring!!

エムスリーでは絶賛エンジニアを募集中です！ TypeScriptでワイワイしたい方、TypeScriptの型で一緒に遊んでくれる方は是非こちらからお願いします！

jobs.m3.com

もちろん新卒・インターンも募集中です！！

open.talentio.com