この記事は TypeScript Advent Calendar 2020 の 16 日目です。
また急遽 TSG Advent Calendar 2020 の 16 日目にもなりました。
さて先月 11 月 19 日、TypeScript 4.1 の安定版がリリースされました。
追加された機能の中でも一際賑わったのが Template Literal Types なのではないでしょうか。
TypeScript Advent Calendar 2020 でも 11 日目 todesking さんによる TypeScript 4.1による型レベルパーサコンビネーター や 13 日目 dqn さんによる TypeScript で実装する型レベル電卓 で色々なテクニックが紹介されており、この機能を使うと文字列を使った様々な型レベルプログラミングが捗ることが知られています。
この記事はそんな TypeScript の型レベルプログラミングに関する実用性皆無の記事です。
型レベルプログラム実行ツール
型レベルで様々な計算ができるようになった以上、それは新たなプログラミング言語であると言えます。そこで TypeScript の型をプログラムとして実行するツールを作りました。
$ npm install -g compile-time-typescript
なぜこれを作る必要があったのかは私事になるので最後に書きます。
使い方としては、まず「入力文字列を型パラメータとして受け取って文字列リテラル型を作るジェネリクス型」をデフォルトエクスポートするスクリプトを書きます。
type Main<Input extends string> = `Hello, ${Input}!\n`;
export default Main;
これを実行して、標準入力を与えると、標準出力が返ってきます。
$ echo -n "world" | ctts hello.ts
Hello, world!
これを作るために TypeScript Compiler API をいじくる必要があったのですが、情報が少なすぎる……。
AtCoder Beginners Selection のいくつかを解いてみる
新しい言語を見つけたら AtCoder Beginners Selection を解いてみるという風潮があるので、解いてみます。
（過去に解かれた言語は AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ から見ることができます。）
ABC086A - Product
シカのAtCoDeerくんは二つの正整数 $a, b$ を見つけました。 $a$ と $b$ の積が偶数か奇数か判定してください。
文字列を $a$ と $b$ に分解したら、それぞれの末尾が奇数かどうか見れば良いです。
type Odd = `1` | `3` | `5` | `7` | `9`;
type Main<Input extends string>
= Input extends `${infer A} ${infer B}\n`
? [A, B] extends [`${infer _}${Odd}`, `${infer _}${Odd}`]
? `Odd\n`
: `Even\n`
: never;
export default Main;
$ echo -ne "3 4\n" | ctts abc086_a.ts
Even
ABC081A - Placing Marbles
すぬけ君は $1, 2, 3$ の番号がついた $3$ つのマスからなるマス目を持っています。 各マスには
0か1が書かれており、マス $i$ には $s_i$ が書かれています。すぬけ君は1が書かれたマスにビー玉を置きます。 ビー玉が置かれるマスがいくつあるか求めてください。
0 を長さ 0 のタプル、1 を長さ 1 のタプルにして展開してみます。（何なら 8 通りしか無いので列挙しても良いですが……。）
type ToTuple<A extends string>
= A extends `0` ? []
: A extends `1` ? [unknown]
: never;
type Main<Input extends string>
= Input extends `${infer A}${infer B}${infer C}\n`
? [...ToTuple<A>, ...ToTuple<B>, ...ToTuple<C>] extends [...infer Sum]
? `${Sum['length']}\n`
: never
: never;
export default Main;
$ echo -ne "101\n" | ctts abc081_a.ts
2
……簡単に解けるのはこの 2 問だけです。正直ここから先を解く気力と能力がありませんでした。将来腕に自身のある誰かが「AtCoder に登録したら解くべき精選過去問 10 問を型レベル TypeScript で解いてみた」を投稿してくれる日を待っています。
とはいえこれだけでは Template Literal Types の計算力が伝わらないので、一応足し算が必要な例もやってみます。
PracticeA - Welcome to AtCoder
高橋君はデータの加工が行いたいです。整数 $a, b, c$ と、文字列 $s$ が与えられます。 $a+b+c$ の計算結果と、文字列 $s$ を並べて表示しなさい。
入力を分解して足し算するだけですが、問題はその足し算が難しい点です。
が、必要な処理を外部モジュールにしてインポートすることで、以下のような抽象化ができます。
import { Encode, Decode, Add } from '../lib/num';
type Main<Input extends string>
= Input extends `${infer A}\n${infer B} ${infer C}\n${infer S}\n`
? `${Decode<Add<Encode<A>, Add<Encode<B>, Encode<C>>>>} ${S}\n`
: never;
export default Main;
$ echo -ne "1\n2 3\ntest\n" | ctts practice_1.ts
6 test
ちなみに上記の ../lib/num の中身は examples/lib/num.ts にあります。
展望
お気持ちパートです。
人はチューリング完全なものを見つけたときそれで計算をしたくなります。あるいは Brainfuck や Unlambda などを始め難解な言語を生み出して様々な問題を解こうとします。
自分自身そういう営みが好きなので、型レベル TypeScript がその一員になったらいいなという展望を持っています。まあ、すでにそんな感じの賑わいを見せていますが……。
また、PracticeA の例で足し算の処理を外に押しやりましたが、これが型レベル TypeScript をプログラミング言語として見る上で将来性のある点かなと思っています。数値演算などの汎用的な処理はモジュール化してしまえば、なんなら誰かが型レベルで色々な演算を行うライブラリを作って公開してしまえば、それをインポートすることで色々な問題が解きやすくなります。
補足: なぜこれを作ったのか？
話は変わりますが、自分が所属しているサークル TSG では、度々「コードゴルフ大会」というイベントが開かれています。
コードゴルフ、すなわちコードの短さを競うことで陣地を広げていく戦いなのですが、画像の通り多数の言語が登場し、中には esolang (esoteric language, 難解プログラミング言語) と呼ばれる「書くのも読むのも難しい言語」たちが多く含まれています。
Template Literal Types が話題になったとき、ここで型レベル TypeScript を使えるようにしようと思ったのがこれを作った動機でした。（各言語は Docker イメージ上で動いているので、動くものを作ってプルリクを出すことで言語が追加できます。）
ところで先駆者として compile-time C++ が存在したのですが、色々抜け穴があったらしく真面目な方法で解かれていません（ある意味真面目な方法ですが）。
- 第5回東大京大コードゴルフ大会 Writeup - Compile-time C++ (Clang, C++11)
- 第6回東大京大コードゴルフ大会 Writeup - Compile-time C++ (Clang, C++11)
ここで追加した型レベル TypeScript はまだ運用されておらず、再帰制限などもあってそもそも問題を解くのに十分な能力があるのかが不明ですが、今後が楽しみです。
補足: コードゴルフ大会の問題も解いてみる
……実はこっちがメインです。
上で紹介した大会の過去の問題をいくつか解いてみます。この大会の問題の特徴として、そもそも esolang での解答を前提としているので、必要な処理が基本的に esolang に優しくなっています。
大体は https://susisu.hatenablog.com/entry/2020/09/12/214343 に出てくる再帰制限を緩和する方法を使っています。
五月祭2019 Live Codegolf Contest day1
連長圧縮を展開せよ
type RecurseSub<T>
= T extends { __rec: never } ? never
: T extends { __rec: { __rec: infer U } } ? { __rec: RecurseSub<U> }
: T extends { __rec: infer U } ? U
: T;
type Recurse<T>
= T extends { __rec: unknown }
? Recurse<RecurseSub<T>>
: T;
type Solve<S extends string, C extends string, T extends string>
= T extends `2${infer Tail}\n` ? { __rec: Solve<`${S}${C}${C}`, ``, `${Tail}\n`> }
: T extends `3${infer Tail}\n` ? { __rec: Solve<`${S}${C}${C}${C}`, ``, `${Tail}\n`> }
: T extends `4${infer Tail}\n` ? { __rec: Solve<`${S}${C}${C}${C}${C}`, ``, `${Tail}\n`> }
: T extends `5${infer Tail}\n` ? { __rec: Solve<`${S}${C}${C}${C}${C}${C}`, ``, `${Tail}\n`> }
: T extends `6${infer Tail}\n` ? { __rec: Solve<`${S}${C}${C}${C}${C}${C}${C}`, ``, `${Tail}\n`> }
: T extends `7${infer Tail}\n` ? { __rec: Solve<`${S}${C}${C}${C}${C}${C}${C}${C}`, ``, `${Tail}\n`> }
: T extends `8${infer Tail}\n` ? { __rec: Solve<`${S}${C}${C}${C}${C}${C}${C}${C}${C}`, ``, `${Tail}\n`> }
: T extends `9${infer Tail}\n` ? { __rec: Solve<`${S}${C}${C}${C}${C}${C}${C}${C}${C}${C}`, ``, `${Tail}\n`> }
: T extends `${infer X}${infer Tail}\n`
? { __rec: Solve<`${S}${C}`, X, `${Tail}\n`> }
: `${S}${C}`;
type Main<Input extends string> = Recurse<Solve<``, ``, Input>>;
export default Main;
$ echo -ne "j5y2h8pf6l7rq7e9t8m9n8i6w7r2z5m2t2y3r6x7smd2k3v3s5t6e7i7j5o4p8h9b3uyg8l3q2y3f4c9a3e5o6z7o7b2u5\n" | ctts mayfes2019-day1.ts
jjjjjyyhhhhhhhhpfffffflllllllrqqqqqqqeeeeeeeeettttttttmmmmmmmmmnnnnnnnniiiiiiwwwwwwwrrzzzzzmmttyyyrrrrrrxxxxxxxsmddkkkvvvssssstttttteeeeeeeiiiiiiijjjjjoooopppppppphhhhhhhhhbbbuygggggggglllqqyyyffffcccccccccaaaeeeeeoooooozzzzzzzooooooobbuuuuu
駒場祭2018 Live Codegolf Contest day2
与えられた単語列から575を検出せよ
type RecurseSub<T>
= T extends { __rec: never } ? never
: T extends { __rec: { __rec: infer U } } ? { __rec: RecurseSub<U> }
: T extends { __rec: infer U } ? U
: T;
type Recurse<T>
= T extends { __rec: unknown }
? Recurse<RecurseSub<T>>
: T;
type Solve<S extends string, T extends string>
= T extends `${infer A0}${infer A1}${infer A2}${infer A3}${infer A4}${infer B0}${infer B1}${infer B2}${infer B3}${infer B4}${infer B5}${infer B6}${infer C0}${infer C1}${infer C2}${infer C3}${infer C4}${infer Tail}\n`
? [A0, B0, C0, Tail] extends [`1`, `1`, `1`, `1${infer _}` | ``]
? { __rec: Solve<`${S}1`, `${A1}${A2}${A3}${A4}${B0}${B1}${B2}${B3}${B4}${B5}${B6}${C0}${C1}${C2}${C3}${C4}${Tail}\n`> }
: { __rec: Solve<`${S}0`, `${A1}${A2}${A3}${A4}${B0}${B1}${B2}${B3}${B4}${B5}${B6}${C0}${C1}${C2}${C3}${C4}${Tail}\n`> }
: T extends `${infer _}${infer Tail}\n`
? { __rec: Solve<`${S}0`, `${Tail}\n`> }
: S;
type Main<Input extends string> = Recurse<Solve<``, Input>>;
export default Main;
$ echo -ne "10001101001110000000110011101001011011001011111000\n" | ctts komabasai2018-day2.ts
00000000000000000000000000001000000000000000000000
DIY Language Contest 2018
入力された数値列のアップダウンを求めよ
type RecurseSub<T>
= T extends { __rec: never } ? never
: T extends { __rec: { __rec: infer U } } ? { __rec: RecurseSub<U> }
: T extends { __rec: infer U } ? U
: T;
type Recurse<T>
= T extends { __rec: unknown }
? Recurse<RecurseSub<T>>
: T;
type CharToTuple<C extends string>
= C extends `0` ? []
: C extends `1` ? [unknown]
: C extends `2` ? [unknown, unknown]
: C extends `3` ? [unknown, unknown, unknown]
: C extends `4` ? [unknown, unknown, unknown, unknown]
: C extends `5` ? [unknown, unknown, unknown, unknown, unknown]
: C extends `6` ? [unknown, unknown, unknown, unknown, unknown, unknown]
: C extends `7` ? [unknown, unknown, unknown, unknown, unknown, unknown, unknown]
: C extends `8` ? [unknown, unknown, unknown, unknown, unknown, unknown, unknown, unknown]
: C extends `9` ? [unknown, unknown, unknown, unknown, unknown, unknown, unknown, unknown, unknown]
: never;
type LessThanOrEqualTo<A extends string, B extends string>
= ((...xs: CharToTuple<A>) => void) extends ((...xs: CharToTuple<B>) => void) ? 1 : 0;
type Solve<S extends string, T extends string>
= T extends `${infer X}${infer Y}${infer Tail}\n`
? { __rec: Solve<`${S}${LessThanOrEqualTo<X, Y>}`, `${Y}${Tail}\n`> }
: S;
type Main<Input extends string> = Recurse<Solve<``, Input>>;
export default Main;
$ echo -ne "76720263929876543210356929483103180240696765792986012538389832979578530374570123456789210847329354846\n" | ctts hackathon2018.ts
0100110101000000000111101010001010110110100110100011101011000101011000110110111111111000101001010101
五月祭2018 Live Codegolf Contest day1
入力された文字列のn文字目ををROT-nせよ
type RecurseSub<T>
= T extends { __rec: never } ? never
: T extends { __rec: { __rec: infer U } } ? { __rec: RecurseSub<U> }
: T extends { __rec: infer U } ? U
: T;
type Recurse<T>
= T extends { __rec: unknown }
? Recurse<RecurseSub<T>>
: T;
type RotateSub<C extends string, N extends unknown[]>
= N extends [unknown, ...infer M]
? ( C extends `A` ? { __rec: RotateSub<`B`, M> }
: C extends `B` ? { __rec: RotateSub<`C`, M> }
: C extends `C` ? { __rec: RotateSub<`D`, M> }
: C extends `D` ? { __rec: RotateSub<`E`, M> }
: C extends `E` ? { __rec: RotateSub<`F`, M> }
: C extends `F` ? { __rec: RotateSub<`G`, M> }
: C extends `G` ? { __rec: RotateSub<`H`, M> }
: C extends `H` ? { __rec: RotateSub<`I`, M> }
: C extends `I` ? { __rec: RotateSub<`J`, M> }
: C extends `J` ? { __rec: RotateSub<`K`, M> }
: C extends `K` ? { __rec: RotateSub<`L`, M> }
: C extends `L` ? { __rec: RotateSub<`M`, M> }
: C extends `M` ? { __rec: RotateSub<`N`, M> }
: C extends `N` ? { __rec: RotateSub<`O`, M> }
: C extends `O` ? { __rec: RotateSub<`P`, M> }
: C extends `P` ? { __rec: RotateSub<`Q`, M> }
: C extends `Q` ? { __rec: RotateSub<`R`, M> }
: C extends `R` ? { __rec: RotateSub<`S`, M> }
: C extends `S` ? { __rec: RotateSub<`T`, M> }
: C extends `T` ? { __rec: RotateSub<`U`, M> }
: C extends `U` ? { __rec: RotateSub<`V`, M> }
: C extends `V` ? { __rec: RotateSub<`W`, M> }
: C extends `W` ? { __rec: RotateSub<`X`, M> }
: C extends `X` ? { __rec: RotateSub<`Y`, M> }
: C extends `Y` ? { __rec: RotateSub<`Z`, M> }
: C extends `Z` ? { __rec: RotateSub<`A`, M> }
: ``
)
: C;
type Rotate<C extends string, N extends unknown[]> = Recurse<RotateSub<C, N>>;
type Solve<S extends string, T extends string, N extends unknown[]>
= T extends `${infer C}${infer CS}`
? { __rec: Solve<`${S}${Rotate<C, N>}`, CS, [unknown, ...N]> }
: S;
type Main<Input extends string> = Recurse<Solve<``, Input, [unknown]>>;
export default Main;
$ echo -ne "SFBMPCVCSHDKARZHSCTVXSYGST\n" | ctts mayfes2018-day1.ts
THEQUICKBROWNFOXJUMPSOVERT