(ネタ) TypeScript 型パズルで作るmini interpreter

TypeScript 4.1に Template String Typesという機能を追加するPRが上がっていて、新しいおもちゃを与えられた犬となって色々遊んでしまった。

Template String Types is 何

Template String Typesで何ができるか的な話については、まぁhttps://github.com/microsoft/TypeScript/pull/40336 を見るなりしてもらえばいいんだけど、端的にいうとJSのTemplate stringよろしくLiteral TypeをTemplateで合成した結果を型として扱えるようになる機能。

type GetterName<T extends string> = `get${capitalize T}`;
type T10 = GetterName<'foo'>;  // 'getFoo;

あと、同じPRに “Mapped Type as Clauses” ってfeatureも追加されていて、これは上記のTemplate String TypesとMapped Typesを合せ技で使うためのもの。

これらの機能を真面目に使うとどんなことできんの？って点については、まぁ割とありそうではあるんだけど、Camel Case と Snake Case の変換とか、

Playground - An online editor for exploring TypeScript and JavaScript

何かしかの文字列テンプレートからの構造情報の抽出とか。

他にも色々あるだろうけど、今回はそういう真面目な話は忘れる。

ミニ電卓作り

遊びで、「非負整数の和算・積算を行う」というのを型演算でやってみた。こんな感じ。

実際の挙動は以下の Playground のリンクから辿ってみて。ちなみに、TSの再帰呼び出し制限にすぐ引っかかるので、計算結果が15くらいが限界なのはご愛嬌ね。

Playground - An online editor for exploring TypeScript and JavaScript

コードの全量は次のとおり。

この手のインタープリタの実装は色々な言語で良くサンプルとして挙げられると思うのであんまり細かくは語らないけど、愚直に

• トークナイズ
• 構文木の構築
• 評価

を型演算で実装している。

自然数の内部表現をどうするか少し考えたんだけど、再帰系のコードで取り回しやすそうだったので、 ペアノの自然数公理における Successor 形式にしてみた。

type N0 = null;
type N1 = { s: null };
type N2 = { s: { s: null } };

Template String Typesが活躍するのはトークナイズの部分ですね。それ以降のパースだったり評価の部分は既存のTypeScriptの機能だけでもできるんだけど、パーサーの実装をConditional Typesベースの再帰下降パーサーで書く都合上、https://github.com/microsoft/TypeScript/pull/40002 の “Recursive Conditional Types” 対応のお陰で割と書きやすくなったと思う。

それでもすぐ “Type instantiation is excessively deep and possibly infinite.” のエラーになったりするので、評価を意図的に遅延する目的だけのために冗長な記述をせざるを得ない箇所も多かったのだけど、従来の Object Index Signature 頼みのハックに比べれば大分マシ。以前に「型だけで作る一次元セルオートマトン」というのをやったことがあるけど、index signatureだらけで大変だったし。