TypeScript で型レベル Brainfuck

TypeScript esolangs プログラミング 小ネタ

2024-04-15 追記: 内容をアップデートした記事を書きました.

susisu.hatenablog.com

TypeScript の型システムはチューリング完全ということが知られていますが, 同じくチューリング完全な言語である Brainfuck のインタプリタを実装することで, その計算能力を確認することができます.

この記事のコードは TypeScript 3.8.3 で動作確認しています.

ゴール

型レベルで Brainfuck のインタプリタを実装します.

type Program = [
  ",", ">", ",", "<",
  "[",
    ">",
    "[",
      ">", "+", ">", "+", "<", "<", "-",
    "]",
    ">",
    "[",
      "<", "+", ">", "-",
    "]",
    "<", "<", "-",
  "]",
  ">", ">", ">", ".", ".", "."
];
type Input = [2, 3];
type Output = Brainfuck<Program, Input>;
// Output = [6, 6, 6]

上記の最終的な形では人間にも扱いやすいように, プログラムと入力をタプル型で与え, 同じく出力もタプル型で得られるようにします.

実装

早速実装していきましょう. 実装方法は TypeScript の型に特別なものというよりは, より一般に不変データ構造を使った方法という趣になっています.

以下では細かい部分の動作確認については省略していますので, 必要に応じて TypeScript Playground で動作確認しながら読んでもらえると良いかもしれません.

状態

まずはインタプリタ実行の各ステップにおける状態を以下の型で定義します. インタプリタの実行は, 現在の状態から次の状態を得るということを繰り返して行います.

type State<P, M, I, O, R, K> = {
  program: P,
  memory: M,
  input: I,
  output: O,
  return: R,
  skip: K,
};

プログラム P は以下で定義するトークン (Brainfuck の命令) の列で記述します.

type Token = "+" | "-" | ">" | "<" | "," | "." | "[" | "]";

メモリ M, 入力 I, 出力 O はバイト列です. 通常バイトといえば 8 ビットで, Brainfuck の実装もそのようになっていることが多いのですが, ここでは簡単のために 4 ビットとします.

type Byte =
  | 0x0 | 0x1 | 0x2 | 0x3
  | 0x4 | 0x5 | 0x6 | 0x7
  | 0x8 | 0x9 | 0xA | 0xB
  | 0xC | 0xD | 0xE | 0xF;

演算についても, Brainfuck の実装に必要なのは +1 / -1 だけなので, 簡単に列挙で定義しておきます.

type Succ<B> =
    B extends 0x0 ? 0x1 : B extends 0x1 ? 0x2 : B extends 0x2 ? 0x3 : B extends 0x3 ? 0x4
  : B extends 0x4 ? 0x5 : B extends 0x5 ? 0x6 : B extends 0x6 ? 0x7 : B extends 0x7 ? 0x8
  : B extends 0x8 ? 0x9 : B extends 0x9 ? 0xA : B extends 0xA ? 0xB : B extends 0xB ? 0xC
  : B extends 0xC ? 0xD : B extends 0xD ? 0xE : B extends 0xE ? 0xF : B extends 0xF ? 0x0
  : never;
type Pred<B> =
    B extends 0x0 ? 0xF : B extends 0x1 ? 0x0 : B extends 0x2 ? 0x1 : B extends 0x3 ? 0x2
  : B extends 0x4 ? 0x3 : B extends 0x5 ? 0x4 : B extends 0x6 ? 0x5 : B extends 0x7 ? 0x6
  : B extends 0x8 ? 0x7 : B extends 0x9 ? 0x8 : B extends 0xA ? 0x9 : B extends 0xB ? 0xA
  : B extends 0xC ? 0xB : B extends 0xD ? 0xC : B extends 0xE ? 0xD : B extends 0xF ? 0xE
  : never;

その他のパラメータ R, K については実装を進める中で説明します.

リスト

さて「トークンの列」や「バイト列」と言ってきましたが, ここでは列を表現する型として, 扱いがシンプルな連結リストを使うことにします. Lisp でお馴染みのアレです.

type Nil = null;
type Cons<X, XS> = [X, XS];

type Car<XS> = XS extends Cons<infer Y, infer _YS> ? Y : never;
type Cdr<XS> = XS extends Cons<infer _Y, infer YS> ? YS : never;

メモリ

プログラムと入出力は基本的に単方向にしか走査しないためリストで十分なのですが, メモリについては双方向の走査が必要になります. そのため以下のような型を定義します.

type Memory<L, H, R,> = {
  left: L,
  head: H,
  right: R,
};

H が現在指し示しているメモリの内容, L, R がそれぞれ「左右」に続くメモリ上のバイト列を表します.

メモリの読み書きは以下のように定義できます.

type Read<M> = M extends Memory<infer _L, infer H, infer _R> ? (
  H
) : never;
type Write<M, B> = M extends Memory<infer L, infer _H, infer R> ? (
  Memory<L, B, R>
) : never;

また左右への移動は以下のように定義します. 左右のリストが空だった場合には適宜 0x0 を補完することで, 任意長のメモリを実現します.

type MoveLeft<M> = M extends Memory<infer L, infer H, infer R> ? (
  L extends Nil
    ? Memory<Nil, 0x0, Cons<H, R>>
    : Memory<Cdr<L>, Car<L>, Cons<H, R>>
) : never;
type MoveRight<M> = M extends Memory<infer L, infer H, infer R> ? (
  R extends Nil
    ? Memory<Cons<H, L>, 0x0, Nil>
    : Memory<Cons<H, L>, Car<R>, Cdr<R>>
) : never;

ステップ実行

さていよいよ実行です. まずは初期状態を以下のように決めます.

type Init<P = Nil, I = Nil> = State<P, Memory<Nil, 0x0, Nil>, I, Nil, Nil, Nil>;

ステップ実行, つまりある状態から次の状態への遷移を, 以下のようにして定義します.

type Next<S> = S extends State<infer P, infer M, infer I, infer O, infer R, infer K> ? (
  K extends Nil
    ? NextProc<P, M, I, O, R>
    : NextSkip<P, M, I, O, R, K>
) : never;

K によって条件分岐が入っていますが, まずは K が空の場合の NextProc を見てみましょう.

type NextProc<P, M, I, O, R> = P extends Cons<infer T, infer Q> ? (
    T extends "+" ? State<Q, Write<M, Succ<Read<M>>>, I, O, R, Nil>
  : T extends "-" ? State<Q, Write<M, Pred<Read<M>>>, I, O, R, Nil>
  : T extends ">" ? State<Q, MoveRight<M>, I, O, R, Nil>
  : T extends "<" ? State<Q, MoveLeft<M>, I, O, R, Nil>
  : T extends "," ? I extends Nil
    ? never
    : State<Q, Write<M, Car<I>>, Cdr<I>, O, R, Nil>
  : T extends "." ? State<Q, M, I, Cons<Read<M>, O>, R, Nil>
  : T extends "[" ? Read<M> extends 0x0
    ? State<Q, M, I, O, R, Cons<Nil, Nil>>
    : State<Q, M, I, O, Cons<P, R>, Nil>
  : T extends "]" ? R extends Nil
    ? never
    : State<Car<R>, M, I, O, Cdr<R>, Nil>
  : State<Q, M, I, O, R, Nil>
) : never;

これは Brainfuck の命令の実行です. まず以下の 6 つは見たままです.

  • +: メモリの値をインクリメント
  • -: メモリの値をデクリメント
  • >: メモリを右に移動
  • <: メモリを左に移動
  • ,: 入力を読み取ってメモリに書き込み
  • .: メモリの値を出力

ループを扱う [, ] は少し複雑になります.

  • [: メモリを読み取る
    • もし 0x0 ならばスキップ用のカウンタを 1 (Cons<Nil, Nil>) にする
    • そうでなければ, ループ終了時に現在の位置から再実行するために, プログラムを R の先頭に保存する
  • ]: R の先頭にあるプログラムを復元する

ここで状態のパラメータ R は, ループを実現するためのスタックとして使っています.

つづいて K が空でない場合の NextSkip を見てみます.

type NextSkip<P, M, I, O, R, K> = P extends Cons<infer T, infer Q> ? (
    T extends "[" ? State<Q, M, I, O, R, Cons<Nil, K>>
  : T extends "]" ? State<Q, M, I, O, R, Cdr<K>>
  : State<Q, M, I, O, R, K>
) : never;

これは以下のような処理をしています.

  • [: カウンタをインクリメント (Cons<Nil, K>) する
  • ]: カウンタをデクリメントする (Cdr<K>)
  • それ以外の命令はスキップ

カウンタ K が空でない間はスキップしつづけることで, ネストしたループをまとめてスキップするようにしています. カウンタが空になった場合は Next にあるように通常の実行に戻ります.

実行

ステップ実行ができたので, 今度はステップ実行を繰り返してプログラム全体を実行してみましょう.

まずは素朴に以下のように書いてみます.

type Run<S, H extends "__hack" = "__hack"> =
  S extends State<infer P, infer _M, infer _I, infer O, infer R, infer K> ? (
    P extends Nil
      ? (R extends Nil ? K extends Nil ? O : never : never)
      : { [H0 in H]: Run<Next<S>> }[H]
  ) : never;

プログラム全体を実行完了したとき, つまり P が空の場合は出力 O を返し, そうでない場合は Next で 1 ステップ進めることを繰り返します. ただし P が空であっても R または K が空でない場合は, 異常終了として never を返します.

さてこれは正しいのですが, これではプログラムを実行しているとすぐに TypeScript の再帰の上限に当たってしまい, 実用的ではありません. 型レベルで Brainfuck を実装するのがそもそも実用的かはさておき.

というわけで, まずは問題を切り分けるために, 以下のように定義し直します.

type Run<S> = Flatten<RunSub<S>>;
type RunSub<S> = S extends State<infer P, infer _M, infer _I, infer O, infer R, infer K> ? (
  P extends Nil
    ? (R extends Nil ? K extends Nil ? O : never : never)
    : { next: RunSub<Next<S>> }
) : never;
type Flatten<T, H extends "__hack" = "__hack"> =
  T extends { next: infer U }
    ? { [H0 in H]: Flatten<U> }[H]
    : T;

RunSub はステップ実行を繰り返すのですが, { next: ... } というオブジェクト型に結果をラップして返します. このようにすると TypeScript からお目溢しがもらえるので, ひとまず再帰の上限の問題は解決できます.

もちろんこれでは結果を見るためにステップ数だけ next を辿っていかなくてはならないので, Flatten を使って結果を取り出します. この時点ではまだ再帰の上限の問題は解決していませんが, 場所は Flatten の側に移りました.

さらに Flatten を工夫して以下のようにします.

type Flatten<T, H extends "__hack" = "__hack"> =
  T extends { next: unknown }
    ? { [H0 in H]: Flatten<FlattenSub<T>> }[H]
    : T;
type FlattenSub<T> =
    T extends { next: { next: infer U } } ? { next: FlattenSub<U> }
  : T extends { next: infer U } ? U
  : T;

FlattenSub は 1 個ずつ next を辿るのではなく, 一度にに全体の深さを 1 / 2 にします. これによって Flatten の再帰の回数は元の対数のオーダーになり, 少なくとも小規模なプログラムを扱うあいだは上限を無視できるようになります. やったね.

人間向けインターフェース

最後に人間にも扱いやすいように, 連結リストではなくタプル型を使ったインターフェースを整えて完成です.

type Brainfuck<P extends Token[] = [], I extends Byte[] = []> =
  FromRevConsList<Run<Init<ToConsList<P>, ToConsList<I>>>>;

ここで ToConsList, FromRevConsList はそれぞれタプル型から連結リストへの変換と, 連結リストから順序を反転させたタプル型への変換です. NextProc の定義で出力を Cons を使って先頭に追記していたので, 先頭から見た場合は順序が反転していたことに注意.

type ToConsList<XS extends unknown[]> =
    XS extends [] ? Nil
  : ((...xs: XS) => unknown) extends (y: infer Y, ...ys: infer YS) => unknown ? [Y, ToConsList<YS>]
  : never;
type FromRevConsList<XS, YS extends unknown[] = [], H extends "__hack" = "__hack"> =
  XS extends Nil
    ? YS
    : { [H0 in H]: FromRevConsList<Cdr<XS>, Unshift<Car<XS>, YS>> }[H];
type Unshift<X, XS extends unknown[]> =
  ((x: X, ...xs: XS) => unknown) extends (...ys: infer YS) => unknown ? YS : never;

ためしに適当なプログラムを実行してみましょう. 以下は最初の例でも使っていた, 2 つの入力を受け取って, それらの積を 3 回出力するプログラムです.

type Program = [
  ",", ">", ",", "<",
  "[",
    ">",
    "[",
      ">", "+", ">", "+", "<", "<", "-",
    "]",
    ">",
    "[",
      "<", "+", ">", "-",
    "]",
    "<", "<", "-",
  "]",
  ">", ">", ">", ".", ".", "."
];
type Input = [2, 3];
type Output = Brainfuck<Program, Input>;
// Output = [6, 6, 6]

😈

コード全体はこちら.

まとめ

というわけで TypeScript の型システムはチューリング完全なので, 思いついた遊びは大抵できてしまうのでした.

もちろんこのような遊びが直ちに実用的ということはないですし, むしろ複雑なことをやりすぎるのは避けるべきという向きもあるとは思いますが, 自分が扱っている型システムで実現可能な範囲や, システムの細かい特性を知っておくのは悪いことではないのではないでしょうか. しらんけど.

以前の型遊びはこちら:

susisu.hatenablog.com susisu.hatenablog.com

2020-04-11 追記: npm パッケージとして公開したのでご自由にお遊びください. www.npmjs.com

リポジトリはここ. github.com