TypeScriptの型システム、実はチューリング完全って知ってましたか？

はじめに

こんにちは！株式会社iimonでフロントエンジニアをしているあめくです！

iimonではフロントエンドにTypeScriptを採用しており、型を用いた開発を行ってます。
私自身、以前はPHPを使っていたこともあり、最初は「型...扱うのが大変そうだな...」と思っていました。

しかし最近はClaudeを使って開発していると、いい感じに型を設定してくれて「こんな使い方があるのか！」と型システムに惹かれていきました。
本日はこの型システムで遊んでみようと思い記事にしてみました。

突然ですが、TypeScriptの型システムはチューリング完全という事を知ってますか？？

チューリング完全とはざっくり言うと「理論上、どんな計算でもできる能力がある」という概念です。

JavaScript、Python、PHPなどのプログラミング言語は基本的に全てチューリング完全です。 (ちなみに正規表現やHTMLはチューリング完全ではないそうです。)

今回はチューリング完全がメインの内容ではなく、TypeScriptの型システムに関する内容ですので、チューリング完全に関してはWikipediaや他の記事を参考にしてみてください。
参考:

• Wikipedia

• MTGのチューリング完全性【要約版】

つまり、TypeScriptの「型システム」もチューリング完全で、型だけで足し算したりFizzBuzzを書いたりすることができます。

今回はTypeScriptの型を用いて計算処理を行い、チューリング完全を体験していきたいと思います。

基礎パーツ作成

タプルのlengthで数値を取得

まずはじめにタプル(固定長の配列型)のlengthで数値を取得します。

type ThreeElements = [unknown, unknown, unknown];
type Three = ThreeElements['length']; // 3

3つの要素を持つタプルのlengthは3になります。

タプルを生成するユーティリティ

次に「N個の要素を持つタプル」を生成する型を作成します。

type Tuple<
    N extends number,
    Result extends unknown[] = []
> = Result['length'] extends N
    ? Result                          // 長さがNになったら完成
    : Tuple<N, [...Result, unknown]>; // 長さが足りない場合、unknownを追加して再帰

処理の流れ

1. 空配列から始まる
2. 長さがNになるまで要素を追加
3. 長さがNになったら完成

実際に数値を入れて試すと下記のようになります。

これで数値からタプルに変換することができるようになりました。

type Zero = Tuple<0>;   // []
type One = Tuple<1>;    // [unknown]
type Five = Tuple<5>;   // [unknown, unknown, unknown, unknown, unknown]

タプルの結合

TypeScriptの型でもスプレッド構文が使えるので、これを用いてタプルを結合していきます。

type Combined = [...Tuple<4>, ...Tuple<1>]  // [unknown, unknown, unknown, unknown, unknown]

type CombinedLength = Combined['length']; // 5

要素が4個のタプルと要素が1個のタプルを結合すると5個の要素をもつタプルが作成されます。

これで足し算ができるようになりました。

足し算の実装

ここまでの内容を組み合わせることで足し算ができるようになりました。

先ほどのタプルを生成するユーティリティを用いて足し算を行う処理を実装していきましょう。

type Add<A extends number, B extends number> = [
    ...Tuple<A>,
    ...Tuple<B>
]['length'];

処理の流れ

1. A個の要素を持つタプルを作成する
2. B個の要素を持つタプルを作成する
3. TupleとTupleを結合する
4. 結合したタプルのlengthを取得する

実際に数値を入れて試すと下記のようになります。

type Result1 = Add<3, 4>;    // 7
type Result2 = Add<0, 5>;    // 5
type Result3 = Add<10, 20>;  // 30
type Result4 = Add<99, 1>;   // 100

引き算の実装

では次に引き算を実装してみたいと思います。

引き算ではinferを用いて「Aの要素からBの要素を取り除いた残り」を取得して実現させてます。
inferについてはこちらご確認ください！

type Subtract<A extends number, B extends number> = Tuple<A> extends [
    ...Tuple<B>,
    ...infer Rest
]
    ? Rest['length']
    : never;

処理の流れ

1. A個の要素を持つタプルを作成する
2. 「B個 + 残り」の形に分解できるかチェック
3. 分解できたら、残り(Rest)のlengthを返す
4. 分解できなかったらneverを返す(A < B の場合)

実際に数値を入れて試すと下記のようになります。

type Sub1 = Subtract<5, 3>;  // 2
type Sub2 = Subtract<10, 4>; // 6
type Sub3 = Subtract<3, 5>;  // never（負の数は表現できない）

負の数は表現できないのでneverになります。

注意点

再帰の深さ

TypeScriptの型には再帰の深さ制限(約1000)があります。

そのため大きな数値は扱えません…

参考:

• How to workaround the max recursion depth in TypeScript

• Increase type instantiation depth limit

// これは動く
type OK = Add<50, 50>;  // 100

// これはエラー
type TooDeep = Add<1000, 1000>;  // 型のインスタンス化は非常に深く、無限である可能性があります。

整数限定

計算処理は整数限定です。小数を渡すと無限再帰になりエラーになります。

type Float = Tuple<3.14>;  // 型のインスタンス化は非常に深く、無限である可能性があります。

これはResult['length']が常に整数(0, 1, 2, 3...)なので、 3.14と永遠に一致せず、再帰が終わらないためです。

チューリング完全について

タイトルにある通り、TypeScriptの型システムはチューリング完全とお伝えしてます。

今回の足し算の実装では、以下の要素を使用しています。

type Add<A extends number, B extends number> = [
    ...Tuple<A>,
    ...Tuple<B>
]['length'];

type Tuple<
    N extends number,
    Result extends unknown[] = []
> = Result['length'] extends N
    ? Result
    : Tuple<N, [...Result, unknown]>;

満たす要素	TypeScriptでの実現方法	今回使った場所
条件分岐	Conditional Types（extends ? :）	Result['length'] extends N
ループ(再帰)	再帰的な型定義	Tuple<N, [...Result, unknown]>
状態保持	ジェネリクスのパラメータ	Result extends unknown[]

TypeScriptの型システムは条件分岐・再帰・状態保持が可能なため、理論上どんな計算でもできる（＝チューリング完全）とされています。 今回の実装でそれを実感できたかと思います。

応用編

掛け算

type Multiply<
    A extends number,
    B extends number,
    Acc extends unknown[] = []
> = B extends 0
    ? Acc['length']
    : Multiply<A, Subtract<B, 1>, [...Acc, ...Tuple<A>]>;

処理の流れ

1. Acc(累積用の配列)を空配列で初期化
2. Bが0かチェック
3. 0でなければ、AccにA個の要素を追加して再帰
4. Bを1減らす(Subtract<B, 1>)
5. Bが0になったらAcc['length']を返す

実際に数値を入れて試すと下記のようになります。

type Mul1 = Multiply<3, 4>; // 12
type Mul2 = Multiply<5, 0>; // 0
type Mul3 = Multiply<7, 6>; // 42

比較

今回は「AがBより大きい」事を判別する処理を書いてみます。

type IsGreater<A extends number, B extends number> = Tuple<A> extends [
    ...Tuple<B>,
    ...infer Rest
]
    ? Rest extends []
        ? false // A === B
        : true  // A > B
    : false;    // A < B

処理の流れ

1. A個のタプルを「B個+残り」に分解できるかチェック
2. 分解できない場合、false (A < B)
3. 分解できた場合、残り(Rest)が空かチェック
4. 残り(Rest)が空の場合、false (A === B)
5. 残り(Rest)が空ではない場合、true (A > B)

実際に数値を入れて試すと下記のようになります。

type Greater1 = IsGreater<5, 3>; // true
type Greater2 = IsGreater<2, 4>; // false
type Greater3 = IsGreater<7, 7>; // false

上記の処理を少し変えれば、同等判定や逆の判定の処理も作成できそうですね！

以上の内容をもとに良ければFizzBuzzの処理をぜひ試してみてください！

参考コード

type FizzBuzz<N extends number> = `${N}` extends `${infer _}${'0' | '5'}`
    ? `${N}` extends
          | `${infer _}${'0' | '3' | '6' | '9'}`
          | `${infer _}${'1' | '4' | '7'}${'2' | '5' | '8'}`
        ? 'FizzBuzz'
        : 'Buzz'
    : `${N}` extends
          | `${infer _}${'0' | '3' | '6' | '9'}`
          | `${infer _}${'1' | '4' | '7'}${'2' | '5' | '8'}`
    ? 'Fizz'
    : `${N}`;

type FB1 = FizzBuzz<1>; // "1"
type FB3 = FizzBuzz<3>; // "Fizz"
type FB5 = FizzBuzz<5>; // "Buzz"
type FB15 = FizzBuzz<15>; // "FizzBuzz"

まとめ

今回はTypeScriptの型システムがチューリング完全であることを、実際の計算処理を実装しながら体験してみました。

実務で使うことはほぼないですが、「型だけでこんなことができるんだ」と細かい部分に目を向けてみると、意外な発見があって面白いなと感じました。

この記事が型システムへの興味を深めるきっかけになれば幸いです。

ちなみに、下記IssueでTypeScriptの型システムがチューリング完全かどうかを議論しており、面白い内容なので覗いてみると良いかもです。

TypeScripts Type System is Turing Complete

TypeScriptの型システムを使った練習問題集みたいなものもあります！👀

Type Challenges

最後に

現在弊社ではエンジニアを募集しています！

この記事を読んで少しでも興味を持ってくださった方は、ぜひカジュアル面談でお話ししましょう！

iimon採用サイト / Wantedly

最後まで読んでいただきありがとうございました！

参考

• Wikipedia
• IT用語辞典
• infer
• MTGのチューリング完全性【要約版】
• TypeScripts Type System is Turing Complete
• Type Challenges