Brainfuck 実装で学ぶ TypeScript 型レベルプログラミング

およそ 4 年前に「TypeScript で型レベル Brainfuck」という記事を書きました.

susisu.hatenablog.com

それから 4 年間の間に TypeScript も進化し, 型レベルプログラミングの技法にも大きな変化がありました. 特に顕著な影響があったものでは,

• TypeScript 4.0 のタプル型の改善
• TypeScript 4.1 のテンプレートリテラル型や条件型での再帰
• TypeScript 4.5 の条件型での末尾再帰の除去と, 再帰の上限の緩和

などがあります.

こういった変化も踏まえた上で, いまから TypeScript の型レベルプログラミングに入門する人に向けて改めてまとめ直したものがこの記事です.

内容は記事執筆時点の最新版である TypeScript 5.4.5 で動作を確認しています. ぜひ Playground などを使って, 自分でも手を動かしながら読んでみてください.

Brainfuck とは

Brainfuck についてはみなさんご存知だと思いますので簡単に 3 行で説明すると,

• 難解プログラミング言語の一種で, プログラムは +-.,><[] の 8 種類の文字だけで構成される
• チューリング完全で, 一般的なプログラミング言語と変わらない計算能力を持つ (効率的だったり, インターフェースが整っているということではない)
• 名前もうちょっとなんとかなりませんか

という言語です. 詳しく知りたい場合は Wikipedia などを参照してください.

JavaScript に翻訳すると概ね以下のようになります (mem は十分な長さの数値の配列, getchar と putchar はそれぞれ文字を入出力する関数).

• + = mem[i]++;
• - = mem[i]--;
• . = mem[i] = getchar();
• , = putchar(mem[i]);
• > = i++;
• < = i--;
• [ = while (mem[i]) {
• ] = }

この記事のゴール

この記事では, 以下のように TypeScript の型レベルで動作する Brainfuck インタプリタを作成します.

type Program = ">,[>,]<[.<]"; // 文字列反転
type Input = "Hello, world!";
type Output = Brainfuck<Program, Input>;
//   ^? = "!dlrow ,olleH"

基礎の実装

Brainfuck インタプリタを実装するにあたっては, 以下のようなものが必要になってきます.

• +, - で 1 ずつ加算・減算できる文字
• ., , で 1 文字ずつ読み書きしたりするための文字列
• >, < で 1 つずつ右左に移動できるメモリ
• [, ] でのジャンプを扱ったりするためのリスト

これらは通常のプログラミング言語であれば当然のように扱えるものですが, TypeScript の型で表現する際にはそれぞれについて注目すべき点があります. 以下ではまずこれらの基礎となる部分の実装を作成していきましょう.

文字

一口に文字と言っても, これをどのような型で表すかにはいくつかの選択肢があります.

• 長さ 1 の文字列リテラル型 ("A", "B", ...)
  • 加算・減算は単純にはできず, 表を用意する必要がある
  • 人間にとってわかりやすい (面白い)
• 数値リテラル型 (65, 66, ...)
  • 加算・減算は単純にはできず, 表を用意する必要がある
  • 人間にとって必ずしもわかりやすくはない
• タプル型 ([1, 1, ..., 1], ...)
  • 文字コード N の文字を, 長さ N のタプル型で表す
  • 加算・減算 (タプル型への要素の追加・削除) は単純に行える
  • 人間にとってわかりにくい

本質的にはどれを使っても良いのですが, ここではわかりやすさを重視して長さ 1 の文字列リテラル型を使うことにします.

上述の通り, 残念ながら TypeScript には一般の文字列リテラル型に対して単純に文字コードを加算・減算するような操作は用意されていません. そのため文字に 1 ずつ加算・減算するためには, 文字ごとの演算結果を列挙した表を自分で用意する必要があります.

以下が文字に 1 を加算するための表の定義です. 文字の範囲はハードコードする都合もあるため "\x00" から "\xFF" の間に制限していて, また "\xFF" に 1 を加えたら "\x00" に戻ることにしています. (自分で書くのが面倒な人はここからコードをコピペしてください.)

/** 文字に 1 を加算するための表 */
type Incrs = {
  "\x00": "\x01", "\x01": "\x02", "\x02": "\x03", "\x03": "\x04",
  "\x04": "\x05", "\x05": "\x06", "\x06": "\x07", "\x07": "\x08",
  "\x08": "\x09", "\x09": "\x0A", "\x0A": "\x0B", "\x0B": "\x0C",
  "\x0C": "\x0D", "\x0D": "\x0E", "\x0E": "\x0F", "\x0F": "\x10",
  // 中略
  "\xFC": "\xFD", "\xFD": "\xFE", "\xFE": "\xFF", "\xFF": "\x00",
};

文字から 1 を減算するための表は, 以下のように加算のための表を反転させることで定義できます. これは値レベルのコードでの const decrs = Object.fromEntries(Object.keys(incrs).map((c) => [incrs[c], c])) に相当します.

/** 文字から 1 を減算するための表 */
type Decrs = { [C in keyof Incrs as Incrs[C]]: C };

これらの表を使えば, 文字に対する加算・減算を以下のように実装できます. 想定外の範囲の文字が入力された場合はエラーとして "\x00" を返すことにしておきます.

/** 文字 */
type Char = keyof Incrs;

/** 文字に 1 を加算する */
type Incr<C> = C extends Char ? Incrs[C] : "\x00";

/** 文字から 1 を減算する */
type Decr<C> = C extends Char ? Decrs[C] : "\x00";

ここまでに登場した型:

• リテラル型 (Literal Types)
• keyof 演算子 (Keyof Type Operator)
• 型に対するインデックスアクセス (Index Access Types)
• 型に対するマッピング (Mapped Types)
• 条件型 (Conditional Types)

文字列

文字列についても, 型での表現方法はいくつか考えられます.

• 文字列リテラル型 ("Hello")
• 文字のリスト (["H", "e", "l", "l", "o"] あるいは { car: "H", cdr: { car: "e", cdr: ... } } など)

とはいえ, やはり文字列リテラル型が最もわかりやすくかつ扱いやすいので, これを使うことにしましょう.

インタプリタへの入力の先頭から 1 文字読んだり, 残りの入力を得るためには, テンプレートリテラル型と条件型のパターンマッチ (infer) を使って以下のような実装ができます. 空文字列など想定外の入力がされた場合は, エラーとして never を返すことにしておきます.

/** 文字列の先頭 1 文字 */
type SHead<S> = S extends `${infer C}${infer _R}` ? C : never;

/** 文字列から先頭 1 文字を除く */
type STail<S> = S extends `${infer _C}${infer R}` ? R : never;

またインタプリタの出力として 1 文字書く場合などには, 以下のようにテンプレートリテラル型を使った文字列の結合が使えます.

/** 文字列を連結する */
type SConcat<S, T> =
  S extends string ?
    T extends string ?
      `${S}${T}`
    : never
  : never;

ここまでに登場した型:

• テンプレートリテラル型 (Template Literal Types あるいは Template String Types)
• 条件型内の infer (Inferring Within Conditional Types)

メモリ

メモリは一次元的な文字の列で, その中の 1 つをポインタが指しており, ポインタの位置は 1 つずつ移動できる必要があります.

多くの Brainfuck の説明や実装では, メモリには配列とインデックスが使われます (この記事の冒頭でもそのように説明しました). そのためメモリを型で表現する場合, 最も単純には文字のタプル型と, インデックスを表す数値リテラル型のペアで表す方法が考えられるのですが, これには文字の節でも紹介したように, 数値リテラル型の加算・減算が単純にはできないという課題があります (タプル型に変換して演算をし, 再び数値リテラル型に戻すといった方法もあるにはありますが).

かわりにここでは zipper 的なデータ構造を使って, 一次元的で左右に移動できるメモリを表す型を定義することにします.

まずはメモリを表す型のコンストラクタを以下のように定義します. 例えばメモリ上に ABCDE という文字があり, 現在のポインタの位置が C の位置にあったとすると, このようなメモリの状態は Memory<"BA", "C", "DE"> と表現します (第一引数 L は逆順になっていることに注意).

/**
 * 一次元的なメモリ.
 * H は現在位置の文字, L と R はそれぞれ H の左右に続く文字列を表す
 */
type Memory<L, H, R> = {
  left: L;
  head: H;
  right: R;
};

現在位置に対する読み書きは, 単純に H の部分を読み書きするだけです. 条件型の extends と infer は構文がやや冗長ですが, ただの一般的な言語でいうところのパターンマッチなので特に難しいことはありません.

/** メモリの現在位置の文字を読む */
type Read<M> = M extends Memory<infer _L, infer H, infer _R> ? H : never;

/** メモリの現在位置に文字を書く */
type Write<M, C> = M extends Memory<infer L, infer _H, infer R> ? Memory<L, C, R> : never;

このようなデータ構造を使用すると左右の移動も低コストで実装できて, 例えば左へ移動する時は,

1. 現在位置の文字 H を, 右側の文字列 R の先頭に移動する
2. 左側の文字列 L の先頭を, H に移動する

とすれば良いです. また移動時に左右の文字列が空だった場合は "\x00" を補完することによって, 可変長のメモリを実現しています.

/** メモリを左へ移動する */
type MoveL<M> =
  M extends Memory<infer L, infer H, infer R> ?
    L extends "" ?
      Memory<"", "\x00", SConcat<H, R>>
    : Memory<STail<L>, SHead<L>, SConcat<H, R>>
  : never;

/** メモリを右へ移動する */
type MoveR<M> =
  M extends Memory<infer L, infer H, infer R> ?
    R extends "" ?
      Memory<SConcat<H, L>, "\x00", "">
    : Memory<SConcat<H, L>, SHead<R>, STail<R>>
  : never;

ここまでに登場した型:

• 条件型内の infer (Inferring Within Conditional Types) (再)

リスト

インタプリタの実装の中では, リストは文字に限らないデータの列を保持するために使ったり, あるいは長さ N のリストを自然数 N の代わりとして使用したりします.

例によってリストにも表現方法がいくつかあります.

• タプル型 ([1, 2, 3])
  • 人間にとってわかりやすい
• cons list ({ car: 1, cdr: { car: 2, cdr: { car: 3, cdr: null } } } など)
  • 先頭に要素を追加したり, 取り除いたりする操作が効率的 (と思われる. TypeScript の内部実装次第ではありますが)

ここでは cons list を使う必要があるほど効率が悪化するような巨大なリストを作ることはないはずですので, わかりやすさを優先してタプル型を使うことにします.

リストの先頭の要素と, 先頭を除いた残りの部分は, 以下のようにして取得できます.

/** リストの先頭の要素 */
type Head<XS> = XS extends [infer Y, ...infer _YS] ? Y : never;

/** リストから先頭の要素を除く */
type Tail<XS> = XS extends [infer _Y, ...infer YS] ? YS : never;

反対に, リストの先頭への要素追加は以下のように定義できます.

/** リストの先頭に要素を追加する */
type Cons<X, XS> = XS extends unknown[] ? [X, ...XS] : never;

ここまでに登場した型:

• タプル型 (Tuple Types)

おまけ: 型定義に対するテスト

複雑な型定義を書いているとだんだん動作に自信がなくなってきて, 意図通りの動作をするか確認するためのテストコードが欲しくなってきます.

世の中にはいくつか型定義をテストするためのライブラリがありますが, どれも概ね同じ機能を提供しています. ここでは特定のライブラリの使い方ではなく, 一般的に型定義をテストする方法を紹介します.

まずは以下のような assert 関数を定義します. ここで型引数 T には上限として true を設定しているため, 与えた型引数が true であれば型検査を通過しますが, false などであれば型エラーになります.

function assert<T extends true>(): void {};

続いて型に対して, 満たすべき条件を満たしていれば true, そうでなければ false を返すような述語を定義します. 中でも最もよく使うと思われる型同士が等しいかどうかの判定は (かなりトリッキーではありますが) 以下のように定義できます (参考).

type Equal<X, Y> =
  (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2 ? true : false;

assert 関数と Equal のような型に対する述語を使うことで, 例えば上記のリストに対する Head のテストは以下のように記述できます. このテストが書かれたファイルに対して tsc -p tsconfig.json --noEmit などで型検査を行い, 型エラーがなければテストは成功ということになります.

// リストの先頭の要素を取得する
assert<Equal<Head<[42]>, 42>>();
assert<Equal<Head<[42, 84]>, 42>>();

// 空リストが与えられたら never を返す
assert<Equal<Head<[]>, never>>();

インタプリタの実装

ようやく基礎が整ったので, ここからは実際に Brainfuck インタプリタを実装していきましょう.

改めて, 完成形としては以下のように Output = Brainfuck<Program, Input> というものを目指します.

type Program = ">,[>,]<[.<]"; // 文字列反転
type Input = "Hello, world!";
type Output = Brainfuck<Program, Input>;
//   ^? = "!dlrow ,olleH"

状態機械

TypeScript の型レベルプログラミングでは, 変数の再代入やオブジェクトの破壊的変更のようなことはできません. したがって, インタプリタの実装でもそれらは使わずに, より宣言的なアプローチをとることになります.

ここではインタプリタを状態機械として設計し,

• インタプリタの 1 ステップの実行を, 現在の状態を引数に取り, 次の状態を返す関数として定義する
• インタプリタ全体は状態を引数に取って, 終了条件を満たしていたら出力を返し, 満たしていなければ 1 ステップ実行した次の状態に自身を再帰的に適用する

とします. 疑似コードで書くと以下のようになるイメージです.

type 実行<S> =
  状態 S が終了条件を満たす ?
    出力<S>
  : 実行<次の状態<S>>;

インタプリタの状態は以下のように定義します. プログラム, メモリ, 入力, 出力を持つことについてはあまり疑問はないでしょう. スタック R とカウンタ K については天下り的に定義していますが, これらについての詳細は後ほど登場します.

/**
 * インタプリタの状態.
 * - P: プログラム (文字列)
 * - M: メモリ
 * - I: 入力 (文字列)
 * - O: 出力 (文字列)
 * - R: ] から対応する [ にジャンプするときに使うスタック (リスト)
 * - K: [ から対応する ] にジャンプするときに使うカウンタ (リスト)
 */
type State<P, M, I, O, R, K> = {
  program: P;
  memory: M;
  input: I;
  output: O;
  return: R;
  skip: K;
};

通常, プログラムと入力が与えられた時に, インタプリタに与える初期状態は以下のようになります.

/** プログラム P, 入力 I の初期状態 */
type Init<P, I> = State<P, Memory<"", "\x00", "">, I, "", [], []>;

1 ステップの実行

インタプリタは 1 ステップの実行と, それを繰り返し適用していく部分に分けられました. まずは 1 ステップの実行を定義しましょう.

ここでは以下の 2 つのどちらかを行うことを 「1 ステップの実行」として定義することにします.

1. +, - といった命令の実行
2. [ から対応する ] にジャンプするまでの命令のスキップ

命令の実行のみを「1 ステップの実行」として定義した方が単純そうにも見えますが, この場合は命令のスキップのための繰り返しが 1 ステップの実行の中に含まれるようになります. 今回は 1 ステップの実行には繰り返しを含まないような定義を選びましたが, これには TypeScript の型レベルプログラミングでは繰り返しに対する制限がややシビアで, できるだけ繰り返しを含む箇所を減らしたいという意図があります.

この定義に基づいて, 1 ステップ実行した次の状態 Next<S> は以下のように実装できます. 命令を実行するかスキップするかは, カウンタ K が 0 (空リスト) かどうかに応じて決定していますが, ひとまずは命令の実行またはスキップが行われるのだということだけ理解しておいて次に進みましょう.

/** 1 ステップ実行した次の状態 */
type Next<S> =
  S extends State<infer P, infer M, infer I, infer O, infer R, infer K> ?
    K extends [] ?
      NextProc<P, M, I, O, R> // 命令を実行
    : NextSkip<P, M, I, O, R, K> // 命令をスキップ
  : never;

命令を実行する部分は以下のようになります.

/** 1 ステップの命令の実行 */
type NextProc<P, M, I, O, R> =
  P extends `${infer C}${infer Q}` ? // 1
    C extends "+" ? State<Q, Write<M, Incr<Read<M>>>, I, O, R, []> // 2
    : C extends "-" ? State<Q, Write<M, Decr<Read<M>>>, I, O, R, []> // 3
    : C extends ">" ? State<Q, MoveR<M>, I, O, R, []> // 4
    : C extends "<" ? State<Q, MoveL<M>, I, O, R, []> // 5
    : C extends "," ? // 6
      I extends "" ?
        State<Q, Write<M, "\x00">, I, O, R, []>
      : State<Q, Write<M, SHead<I>>, STail<I>, O, R, []>
    : C extends "." ? State<Q, M, I, SConcat<O, Read<M>>, R, []> // 7
    : C extends "[" ? // 8
      Read<M> extends "\x00" ?
        State<Q, M, I, O, R, [unknown]>
      : State<Q, M, I, O, Cons<P, R>, []>
    : C extends "]" ? // 9
      R extends [] ?
        never
      : State<Head<R>, M, I, O, Tail<R>, []>
    : State<Q, M, I, O, R, []> // 10
  : never;

この記事中で最も大きい型定義ですが, 怖がる必要はありません. 一つずつ順番に見ていけば, ここまでに用意した基礎を使って各命令の処理を行っているだけということがわかると思います.

1. プログラム (文字列) を先頭 1 文字と残りの文字列に分解する
2. + が来たら, メモリを読み取り (Read), 1 を足して (Incr), メモリに書き込む (Write)
3. - が来たら, メモリを読み取り (Read), 1 を引いて (Decr), メモリに書き込む (Write)
4. > が来たら, メモリを右に移動する (MoveR)
5. < が来たら, メモリを左に移動する (MoveL)
6. , が来たら, 入力を読み取る
   • 入力が空であれば, "\x00" を読み取ったことにしてメモリに書き込む (Write)
   • 入力が空でなければ, 入力を読み取って (SHead) メモリに書き込み (Write), 残り (STail) を次の入力にする
7. . が来たら, メモリを読み取り (Read), それを出力に書き込む (SConcat)
8. [ が来たら, ループまたは対応する ] までのジャンプを開始する
   • メモリを読み取り (Read), "\x00" ならカウンタ K を 1 (長さ 1 のリスト [unknown]) とする (ジャンプを開始)
   • "\x00" でなければ, スタック R に現在のプログラムを保存 (Cons) する (ループを開始)
9. ] が来たら, 対応する [ までジャンプする
   • スタック R が空であれば, 何かがおかしいのでエラー (never)
   • スタック R が空でなければ, 保存されているプログラムを取り出し (Head), プログラムを置き換えることでジャンプする
10. 命令でない文字 (コメント) が来たら何もしない

状態に含まれるスタック R はループ時のジャンプのために使っていて, [ でのループ開始時にその時点のプログラムを R の先頭に保存し, ] でループの先頭に戻るときには R の先頭からプログラムを取り出してその地点に復帰させています. 単一のデータではなくスタックになっているのは, 多重ループでのジャンプ先を正しく扱うためです.

カウンタ K は [ でループを開始せず, 対応する ] までジャンプさせるときに 1 (長さ 1 のリスト) に設定することで, 次の 1 ステップの実行では命令のスキップが行われるようにしています.

続いては命令をスキップする部分の実装を見ていきましょう.

/** 1 ステップの命令のスキップ */
type NextSkip<P, M, I, O, R, K> =
  P extends `${infer C}${infer Q}` ? // 1
    C extends "[" ? State<Q, M, I, O, R, Cons<unknown, K>> // 2
    : C extends "]" ? State<Q, M, I, O, R, Tail<K>> // 3
    : State<Q, M, I, O, R, K> // 4
  : never;

こちらも記述の仕方は命令の実行の場合とほぼ同じです.

1. プログラム (文字列) を先頭 1 文字と残りの文字列に分解する
2. [ が来たら, カウンタ K に 1 を足す (Cons)
3. ] が来たら, カウンタ K から 1 を引く (Tail)
4. それ以外の命令やコメントが来たら何もしない

命令のスキップはカウンタ K が 0 でない場合に行われるので, これで ] までのジャンプが実現できます. [ が来た場合に K に 1 を足しているのは, やはり多重ループでのジャンプ (対応する ] の発見) を正しく扱うためです.

複数ステップの実行

1 ステップの実行ができたら, 今度はそれを使って複数ステップの実行を定義できます.

以下のように, 複数ステップの実行を再帰的に定義します.

/**  終了条件を満たすまで 1 ステップの実行を繰り返す */
type Run<S> =
  S extends State<infer P, infer _M, infer _I, infer O, infer R, infer K> ?
    P extends "" ? // 1
      R extends [] ? // 2
        K extends [] ? // 3
          O
        : never
      : never
    : Run<Next<S>> // 4
  : never;

1 は終了条件を満たしているかのチェック, 2 と 3 はエラーがないかのチェックです. 基本的にはプログラム P が空になれば終了ですが, もしその時点で R や K が空でない場合は [ と ] の対応がとれていないのでエラー (never) とします. エラーがなければ出力 O を結果として返します.

もし終了条件を満たしていなければ, 4 のように 1 ステップの実行 (Next<S>) を行って, 自身を再帰的に適用します. これによって, 終了条件を満たすまで繰り返し実行が行われることになります.

完成

最後にインタプリタに使いやすいインターフェースを被せて完成としましょう.

/** Brainfuck プログラムを実行する. P はプログラム, I は入力 */
type Brainfuck<P extends string, I extends string = ""> = Run<Init<P, I>>;

インタプリタにはプログラム P と入力 I のみを与えることとして, 初期状態 Init<P, I> はここで組み立てます. また, ここまでの型定義では型引数に制約 (extends) を書いていませんでしたが, ここでは間違った種類の引数を渡すとエラーになるように制約を付与しています.

これを使って冒頭のサンプルを動かしてみると, 無事に Brainfuck のプログラムを実行できていることが確認できます.

type Program = ">,[>,]<[.<]"; // 文字列反転
type Input = "Hello, world!";
type Output = Brainfuck<Program, Input>;
//   ^? = "!dlrow ,olleH"

まとめ

ということで TypeScript の型レベルプログラミングで Brainfuck インタプリタを実装する方法を紹介してきました.

一般的なプログラミング言語と比べると, TypeScript での型レベルプログラミングは基礎的なデータや演算に制限があったり, 構文に癖があったりします. 一方でそこを除けば, 不変データ構造や再帰といった, 普通の宣言型の (あるいは純粋関数型の) 技法を使った, ごく普通のプログラミングの世界が広がっています.

型パズルなどと呼んで必要以上に敬遠したり, あるいはパズルだと決めつけて必要以上に複雑なコードを許容したりせず, ぜひ普通のプログラミングの技法を使った普通のコードを読み書きしてみてください.

---

この記事で実装した Brainfuck インタプリタは, 以下のリポジトリで公開しているものの簡易版です (とはいえ, 省略したのはごく一部です). より発展的な内容が知りたい方や, また継続的に更新していますので最新の状況が知りたい方はリポジトリもチェックしてみてください.

github.com