Go to Qiita Advent Calendar 2024 Top
LoginSignup
8
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

TypeScriptAdvent Calendar 2020

Day 16
@n4o847

型レベル TypeScript の esolang としての展望について

Posted at

この記事は TypeScript Advent Calendar 2020 の 16 日目です。

また急遽 TSG Advent Calendar 2020 の 16 日目にもなりました。

さて先月 11 月 19 日、TypeScript 4.1 の安定版がリリースされました。

Announcing TypeScript 4.1 | TypeScript

追加された機能の中でも一際賑わったのが Template Literal Types なのではないでしょうか。

TypeScript Advent Calendar 2020 でも 11 日目 todesking さんによる TypeScript 4.1による型レベルパーサコンビネーター や 13 日目 dqn さんによる TypeScript で実装する型レベル電卓 で色々なテクニックが紹介されており、この機能を使うと文字列を使った様々な型レベルプログラミングが捗ることが知られています。

この記事はそんな TypeScript の型レベルプログラミングに関する実用性皆無の記事です。

型レベルプログラム実行ツール

型レベルで様々な計算ができるようになった以上、それは新たなプログラミング言語であると言えます。そこで TypeScript の型をプログラムとして実行するツールを作りました。

$ npm install -g compile-time-typescript

n4o847/compile-time-typescript - GitHub

なぜこれを作る必要があったのかは私事になるので最後に書きます。

使い方としては、まず「入力文字列を型パラメータとして受け取って文字列リテラル型を作るジェネリクス型」をデフォルトエクスポートするスクリプトを書きます。

hello.ts
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$ に分解したら、それぞれの末尾が奇数かどうか見れば良いです。

abc086_a.ts
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 通りしか無いので列挙しても良いですが……。）

abc081_a.ts
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$ を並べて表示しなさい。

入力を分解して足し算するだけですが、問題はその足し算が難しい点です。

が、必要な処理を外部モジュールにしてインポートすることで、以下のような抽象化ができます。

practice_1.ts
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 では、度々「コードゴルフ大会」というイベントが開かれています。

image.png

コードゴルフ、すなわちコードの短さを競うことで陣地を広げていく戦いなのですが、画像の通り多数の言語が登場し、中には esolang (esoteric language, 難解プログラミング言語) と呼ばれる「書くのも読むのも難しい言語」たちが多く含まれています。

Template Literal Types が話題になったとき、ここで型レベル TypeScript を使えるようにしようと思ったのがこれを作った動機でした。（各言語は Docker イメージ上で動いているので、動くものを作ってプルリクを出すことで言語が追加できます。）

ところで先駆者として compile-time C++ が存在したのですが、色々抜け穴があったらしく真面目な方法で解かれていません（ある意味真面目な方法ですが）。

ここで追加した型レベル TypeScript はまだ運用されておらず、再帰制限などもあってそもそも問題を解くのに十分な能力があるのかが不明ですが、今後が楽しみです。

補足: コードゴルフ大会の問題も解いてみる

……実はこっちがメインです。

上で紹介した大会の過去の問題をいくつか解いてみます。この大会の問題の特徴として、そもそも esolang での解答を前提としているので、必要な処理が基本的に esolang に優しくなっています。

大体は https://susisu.hatenablog.com/entry/2020/09/12/214343 に出てくる再帰制限を緩和する方法を使っています。

五月祭2019 Live Codegolf Contest day1

連長圧縮を展開せよ

mayfes2019-day1.ts
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を検出せよ

komabasai2018-day2.ts
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

入力された数値列のアップダウンを求めよ

hackathon2018.ts
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せよ

mayfes2018-day1.ts
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
8
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
8
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?