C# の型システムで Brainf*ck コンパイラを作ってみた

はじめに、Brainfuck とは？

もともと Brainfuck は、1993 年に Urban Müller 氏が考案した、非常にシンプルなチューリング完全プログラミング言語です。
そのシンプルさはなんと、たった 8 種類の記号だけでプログラムが書けちゃいます。
たとえば C 言語風に表現すると、以下のようになります。

記号	意味
>	++ptr
<	--ptr
+	++*ptr
-	--*ptr
.	putchar(*ptr)
,	*ptr = getchar()
[	while (*ptr) {
]	}

必要なものは、ゼロで初期化されたバイト配列（メモリ）、その配列を指すポインタ、そして入出力用の 2 つのバイトストリームだけ。これで Brainfuck プログラムは実行可能になります。

たとえば、Hello World! を出力するプログラムはこんな感じです。

++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.

今回は、C# の型システムを活用して Brainfuck のコンパイラを作ってみました。

C# の型システムってどういうもの？

さて、今回のコンパイラ作りには C# の型システムをドーンと使います。ここでは主に使っていたその基本的な部分について、ざっくりとお話しします。

ジェネリックシステム

C# の型システムは .NET の上に成り立っていて、.NET は実際にジェネリック型を具現化（インスタンス化）する仕組みになっています。つまり、ジェネリックパラメータは消されずに、各パラメータごとにコードが特化されるんです。

たとえば：

class Foo<T>
{
    public void Print() => Console.WriteLine(default(T)?.ToString() ?? "null");
}

これだと、new Foo<int>().Print() なら 0 が、
new Foo<DateTime>().Print() なら 0001-01-01T00:00:00 が、
new Foo<string>().Print() なら null が出力されます。

さらに、.NET のジェネリックは実行時に型ごとにコードを特化してくれるので、次のようなコードでも安心です。

class Calculator<T> where T : IAdditionOperators<T, T, T>
{
    public T Add(T left, T right)
    {
        return left + right;
    }
}

godbolt で見ると、型ごとに最適化された機械語が生成されるのがわかります。

Calculator`1[int]:Add(int,int):int:this (FullOpts):
       lea      eax, [rsi+rdx]
       ret      

Calculator`1[long]:Add(long,long):long:this (FullOpts):
       lea      rax, [rsi+rdx]
       ret      

Calculator`1[ubyte]:Add(ubyte,ubyte):ubyte:this (FullOpts):
       add      edx, esi
       movzx    rax, dl
       ret      

Calculator`1[float]:Add(float,float):float:this (FullOpts):
       vaddss   xmm0, xmm0, xmm1
       ret      

Calculator`1[double]:Add(double,double):double:this (FullOpts):
       vaddsd   xmm0, xmm0, xmm1
       ret      

このように、異なる型を与えれば、各型に最適化されたコードが自動で生成されちゃいます。

インターフェイスの静的抽象メンバー

もしかすると、「なんで Calculator<T> 内で left と right をそのまま足し合わせられるの？」と思うかもしれません。
それは、.NET がインターフェイスで静的抽象メンバーをサポートしているからです。
実際の IAdditionOperators はこんな感じに定義されています。

interface IAdditionOperators<TSelf, TOther, TResult>
{
    abstract static TResult operator+(TSelf self, TOther other);
}

そして、where T : IAdditionOperators<T, T, T> という制約をつけることで、ジェネリックコード内で型 T を使って operator+ を直接呼び出せるようになっているんです。

じゃあ性能は？

上の知識を踏まえると、.NET のコンパイラがこの型システムを使ってどれほど最適化できるのか、実際にテストしてみたくなりますよね。

まず、Brainfuck コンパイラ作成で必要になるであろう int（32 ビット）を型で表現する方法を見てみましょう。
32 ビットの int は 16 進数にすると 8 桁。そこで、16 進数の各桁を表す型を作り、その 8 つを組み合わせて数字を表現します。

まずは、各桁が実装するインターフェイス IHex を定義します。

interface IHex
{
    abstract static int Value { get; }
}

たとえば、16 進数の桁 0、6、C は以下のように表現できます。

struct Hex0 : IHex
{
    public static int Value => 0;
}

struct Hex6 : IHex
{
    public static int Value => 6;
}

struct HexC : IHex
{
    public static int Value => 12;
}

ここでは数字と桁を区別するため、似た感じのジェネリックなインターフェイス INum<T> を定義し、数字を表す Int 型に実装します。
ちなみにここは将来、浮動小数点数などへ拡張する可能性を考えてジェネリックにしているんです。

interface INum<T>
{
    abstract static T Value { get; }
}

struct Int<H7, H6, H5, H4, H3, H2, H1, H0> : INum<int>
    where H7 : IHex
    where H6 : IHex
    where H5 : IHex
    where H4 : IHex
    where H3 : IHex
    where H2 : IHex
    where H1 : IHex
    where H0 : IHex
{
    public static int Value
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        get => H7.Value << 28 | H6.Value << 24 | H5.Value << 20 | H4.Value << 16 | H3.Value << 12 | H2.Value << 8 | H1.Value << 4 | H0.Value;
    }
}

これで、たとえば 0x1234abcd を表現するには
Int<Hex1, Hex2, Hex3, Hex4, HexA, HexB, HexC, HexD> と書くだけでOK。

ちなみに、ここはメソッドに [MethodImpl(MethodImplOptions.AggressiveInlining)] を付けて、コンパイラにそのメソッドをできるだけインライン化するように要求しています。

godbolt でコンパイル結果を見ても、直接 0x1234ABCD に最適化されているのがわかります：

Int`8[Hex1,Hex2,Hex3,Hex4,HexA,HexB,HexC,HexD]:get_Value():int (FullOpts):
       push     rbp
       mov      rbp, rsp
       mov      eax, 0x1234ABCD
       pop      rbp
       ret      

まさに「ゼロオーバーヘッド抽象」の良い例です！

性能に自信が持てたところで、いよいよ Brainfuck コンパイラ作りに取り掛かりましょう。

Brainfuck のコンパイラ作り

Brainfuck をコンパイルするには、大きく分けて 2 つのステップに分かれます。
ひとつは Brainfuck ソースコードのパース（解析）、もうひとつはコンパイル結果の生成です。

パースは文字列を左から右に走査するだけなので、とてもシンプルで実装できます。
ここでは詳しくは触れず、今回は「どうやってコンパイル結果を作るか」に着目します。

今回はプログラムそのものを「型」で表現してしたいと思います。
つまり、コンパイル結果がまさに型になるというわけです。

基本操作

Brainfuck で必要な基本操作は、次の 4 つです。

• ポインタの移動
• メモリの操作
• 入力
• 出力

これらを抽象化するため、まずは操作用のインターフェイスを定義します。

interface IOp
{
    abstract static int Run(int address, Span<byte> memory, Stream input, Stream output);
}

これを基に、各操作を型として作っていきます。

ポインタの移動

ポインタの移動は、移動量（Offset）と次に実行する操作（Next）をジェネリックパラメータで表現します。

struct AddPointer<Offset, Next> : IOp
    where Offset : INum<int>
    where Next : IOp
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Run(int address, Span<byte> memory, Stream input, Stream output)
    {
        return Next.Run(address + Offset.Value, memory, input, output);
    }
}

メモリの操作

次は、メモリ上のデータ操作です。

struct AddData<Data, Next> : IOp
    where Data : INum<int>
    where Next : IOp
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Run(int address, Span<byte> memory, Stream input, Stream output)
    {
        memory.UnsafeAt(address) += (byte)Data.Value;
        return Next.Run(address, memory, input, output);
    }
}

Brainfuck は性質上、メモリ境界チェックは省略していますので、ここで拡張メソッド UnsafeAt を使って高速化します：

internal static ref T UnsafeAt<T>(this Span<T> span, int address)
{
    return ref Unsafe.Add(ref MemoryMarshal.GetReference(span), address);
}

入出力

入力と出力はとてもシンプルに実装できます。

struct OutputData<Next> : IOp
    where Next : IOp
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Run(int address, Span<byte> memory, Stream input, Stream output)
    {
        output.WriteByte(memory.UnsafeAt(address));
        return Next.Run(address, memory, input, output);
    }
}

struct InputData<Next> : IOp
    where Next : IOp
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Run(int address, Span<byte> memory, Stream input, Stream output)
    {
        var data = input.ReadByte();
        if (data == -1)
        {
            return address;
        }
        memory.UnsafeAt(address) = (byte)data;
        return Next.Run(address, memory, input, output);
    }
}

制御フローの実現

基本操作ができたので、あとはプログラムの制御フローを考えましょう。

まず、プログラムは最終的に止まらないといけないので、何もしない Stop 操作を作ります。

struct Stop : IOp
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Run(int address, Span<byte> memory, Stream input, Stream output)
    {
        return address;
    }
}

そして Brainfuck にはループ構造があります。
これは C 言語での while (*ptr) { ... } と同じように、ポインタが指す値が 0 でない間はループ内の処理を繰り返し、最後に次の操作に進むというものです。

struct Loop<Body, Next> : IOp
    where Body : IOp
    where Next : IOp
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Run(int address, Span<byte> memory, Stream input, Stream output)
    {
        while (memory.UnsafeAt(address) != 0)
        {
            address = Body.Run(address, memory, input, output);
        }
        return Next.Run(address, memory, input, output);
    }
}

さあ、実際にプログラムを作ってみよう！

Brainfuck プログラムを型で表現できるようになったので、例を見ていきましょう。

Hello World!

よく知られた（多分） Hello World! のコードは以下の通りです。

++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.

が、上のコードは一見してわかりにくいので、もっと直感的な実装で書き直しました：

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++
<<<<<<<<<<<
.>.>.>.>.>.>.>.>.>.>.>.

このプログラムは、左から右へと各セルに Hello World! の各文字を順番にセットし、
ポインタを先頭に戻してから出力していくという動きをしています。

でもやはり Hello World! は長すぎるので、今回はシンプルに 123 を出力する例もご紹介していきましょう。

+++++++++++++++++++++++++++++++++++++++++++++++++
>
++++++++++++++++++++++++++++++++++++++++++++++++++
>
+++++++++++++++++++++++++++++++++++++++++++++++++++
<<
.>.>.

このプログラムの型での表現は、例えば次のようになります。

AddData<49, AddPointer<1, AddData<50, AddPointer<1, AddData<51, // それぞれ 1, 2, 3 をセット
AddPointer<-2, // ポインタを先頭に戻す
OutputData<AddPointer<1, OutputData<AddPointer<1, OutputData< // 出力
Stop>>>>>>>>>>> // 停止

※ ここでは簡潔にするため、数値は直接記述しています。実際には 49 は Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex3, Hex1> と表現するのが正しいです。

実行方法

実行もとても簡単！以下のように書けば動きます。

AddData<49, AddPointer<1, AddData<50, AddPointer<1, AddData<51, AddPointer<-2, OutputData<AddPointer<1, OutputData<AddPointer<1, OutputData<Stop>>>>>>>>>>>
    .Run(0, stackalloc byte[8], Console.OpenStandardInput(), Console.OpenStandardOutput());

さらに、C# の Type Alias を使うと毎回長い型名を打つ手間も省けます。

using Print123 = AddData<49, AddPointer<1, AddData<50, AddPointer<1, AddData<51, AddPointer<-2, OutputData<AddPointer<1, OutputData<AddPointer<1, OutputData<Stop>>>>>>>>>>>;

Print123.Run(0, stackalloc byte[8], Console.OpenStandardInput(), Console.OpenStandardOutput());

godbolt で生成されたマシンコードを見ると、こんな感じです。

push     rbp
push     r15
push     r14
push     r13
push     rbx
lea      rbp, [rsp+0x20]
mov      rbx, rsi
mov      r15, r8
movsxd   rsi, edi
add      rsi, rbx
add      byte  ptr [rsi], 49 ; '1'
inc      edi
movsxd   rsi, edi
add      rsi, rbx
add      byte  ptr [rsi], 50 ; '2'
inc      edi
movsxd   rsi, edi
add      rsi, rbx
add      byte  ptr [rsi], 51 ; '3'
lea      r14d, [rdi-0x02]
movsxd   rsi, r14d
movzx    rsi, byte  ptr [rbx+r14d]
mov      rdi, r15
mov      rax, qword ptr [r15]
mov      r13, qword ptr [rax+0x68]
call     [r13]System.IO.Stream:WriteByte(ubyte):this
inc      r14d
movsxd   rsi, r14d
movzx    rsi, byte  ptr [rbx+r14d]
mov      rdi, r15
call     [r13]System.IO.Stream:WriteByte(ubyte):this
inc      r14d
movsxd   rsi, r14d
movzx    rsi, byte  ptr [rbx+r14d]
mov      rdi, r15
call     [r13]System.IO.Stream:WriteByte(ubyte):this
mov      eax, r14d
pop      rbx
pop      r13
pop      r14
pop      r15
pop      rbp
ret      

C 言語で書くとこんな感じのコードと同じです。

*(ptr++) = '1';
*(ptr++) = '2';
*ptr = '3';
ptr -= 2;
WriteByte(*(ptr++));
WriteByte(*(ptr++));
WriteByte(*ptr);

つまり、C# の型システムで表現した抽象は、.NET のコンパイラが最適化してくれるので、実行時に余計なオーバーヘッドは一切ありません。

ちなみに、前述の「直感的でなかった」Hello World! のコードは、コンパイルすると以下のような非常に長い型に展開されます。

AddData<8, Loop<
    AddPointer<1, AddData<4, Loop<
        AddPointer<1, AddData<2, AddPointer<1, AddData<3, AddPointer<1, AddData<3, AddPointer<1, AddData<1, AddPointer<-4, AddData<-1, Stop>>>>>>>>>>,
        AddPointer<1, AddData<1, AddPointer<1, AddData<1, AddPointer<1, AddData<-1, AddPointer<2, AddData<1,
            Loop<AddPointer<-1, Stop>,
            AddPointer<-1, AddData<-1, Stop>>
        >>>>>>>>>
    >>>,
    AddPointer<2, OutputData<AddPointer<1, AddData<-3, OutputData<AddData<7, OutputData<OutputData<AddData<3, OutputData<AddPointer<2, OutputData<AddPointer<-1, AddData<-1, OutputData<AddPointer<-1, OutputData<AddData<3, OutputData<AddData<-6, OutputData<AddData<-8, OutputData<AddPointer<2, AddData<1, OutputData<AddPointer<1, AddData<2, OutputData<Stop>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

JIT コンパイルで動かしてみる

もし Brainfuck コードを JIT 形式で実行したい場合、実行時に型を生成して、その型の Run メソッドをリフレクションで呼び出せばOKです。
.NET のリフレクション機能はかなり充実しているので、実行時に型を作るのも難しくありません。

たとえば、数字から数字型を生成するコードは次の通りです。

var type = GetNum(42);

static Type GetHex(int hex)
{
    return hex switch
    {
        0 => typeof(Hex0),
        1 => typeof(Hex1),
        2 => typeof(Hex2),
        3 => typeof(Hex3),
        4 => typeof(Hex4),
        5 => typeof(Hex5),
        6 => typeof(Hex6),
        7 => typeof(Hex7),
        8 => typeof(Hex8),
        9 => typeof(Hex9),
        10 => typeof(HexA),
        11 => typeof(HexB),
        12 => typeof(HexC),
        13 => typeof(HexD),
        14 => typeof(HexE),
        15 => typeof(HexF),
        _ => throw new ArgumentOutOfRangeException(nameof(hex)),
    };
}

static Type GetNum(int num)
{
    var hex0 = num & 0xF;
    var hex1 = (num >>> 4) & 0xF;
    var hex2 = (num >>> 8) & 0xF;
    var hex3 = (num >>> 12) & 0xF;
    var hex4 = (num >>> 16) & 0xF;
    var hex5 = (num >>> 20) & 0xF;
    var hex6 = (num >>> 24) & 0xF;
    var hex7 = (num >>> 28) & 0xF;
    return typeof(Int<,,,,,,,>).MakeGenericType(GetHex(hex7), GetHex(hex6), GetHex(hex5), GetHex(hex4), GetHex(hex3), GetHex(hex2), GetHex(hex1), GetHex(hex0));
}

制御フローなどのやり方も同じです。

あとは、生成した型の Run メソッドをリフレクションで呼び出すだけです。

var run = (EntryPoint)Delegate.CreateDelegate(typeof(EntryPoint), type.GetMethod("Run")!);
run(0, memory, input, output);

delegate int EntryPoint(int address, Span<byte> memory, Stream input, Stream output);

AOT コンパイルで作ってみる

もし JIT ではなく、AOT コンパイルで実行ファイルを作りたいなら、
コンパイル結果が型で表現されているおかげで、その型をエントリーポイントにすれば簡単です。
例えば、以下のようにエントリーポイントを作れば良いです。

using HelloWorld = AddData<8, Loop<
    AddPointer<1, AddData<4, Loop<
        AddPointer<1, AddData<2, AddPointer<1, AddData<3, AddPointer<1, AddData<3, AddPointer<1, AddData<1, AddPointer<-4, AddData<-1, Stop>>>>>>>>>>,
        AddPointer<1, AddData<1, AddPointer<1, AddData<1, AddPointer<1, AddData<-1, AddPointer<2, AddData<1,
            Loop<AddPointer<-1, Stop>,
            AddPointer<-1, AddData<-1, Stop>>
        >>>>>>>>>
    >>>,
    AddPointer<2, OutputData<AddPointer<1, AddData<-3, OutputData<AddData<7, OutputData<OutputData<AddData<3, OutputData<AddPointer<2, OutputData<AddPointer<-1, AddData<-1, OutputData<AddPointer<-1, OutputData<AddData<3, OutputData<AddData<-6, OutputData<AddData<-8, OutputData<AddPointer<2, AddData<1, OutputData<AddPointer<1, AddData<2, OutputData<Stop>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;

static void Main()
{
    HelloWorld.Run(0, stackalloc byte[16], Console.OpenStandardInput(), Console.OpenStandardOutput());
}

AOT コンパイルは次のコマンドで実行できます。

dotnet publish -c Release -r linux-x64 /p:PublishAot=true /p:IlcInstructionSet=native /p:OptimizationPreference=Speed

ここで、/p:IlcInstructionSet=native は C++ の -march=native と同じ意味で、
OptimizationPreference=Speed は -O2 と同等です。
これで生成された実行ファイルを実行すれば、直接 Hello World! が出力されます。

パフォーマンス測定

実際に Brainfuck で書かれた Mandelbrot プログラム（コードは Pastebin を参照）を使って、性能測定にも挑戦してみました。
実行すると、以下のような Mandelbrot フラクタルが描かれます：

さらに、このプログラムを型で表現した結果、全ての空白を取り除くと、型名は 165,425 文字にもなるという壮大な出来栄えに！

今回は以下の 5 つの方法で実行し、性能を比較しました。

• C インタプリタ
  → C 言語で実装した Brainfuck インタプリタ をそのまま実行

• GCC
  → Brainfuck を C 言語にするコンパイラ で Brainfuck コードを C 言語に変換し、
  gcc -O3 -march=native でコンパイルして実行

• Clang
  → 同様に、clang -O3 -march=native でコンパイルして実行

• .NET JIT
  → 実行時に型を生成して JIT 実行（事前に数回ウォームアップを実施）

• .NET AOT
  → .NET NativeAOT を使って実行ファイルとしてコンパイルして実行

テスト環境は以下の通りです。

• OS: Debian GNU/Linux 12 (bookworm)
• CPU: 13th Gen Intel® Core™ i7-13700K
• RAM: CORSAIR DDR5-6800MHz 32G×2

各手法とも 10 回実行し、最速の結果を採用します。
出力による性能低下を防ぐため、すべての出力は /dev/null にリダイレクトしています。

結果は以下のとおり。

手法	実行時間（ミリ秒）	順位	比率
C インタプリタ	4874.6587	5	5.59
GCC	901.0225	3	1.03
Clang	881.7177	2	1.01
.NET JIT	925.1596	4	1.06
.NET AOT	872.2287	1	1.00

驚くほど .NET AOT が C 言語を上回り、一位になってしまいました。
これも、C# の型システムによるゼロオーバーヘッド抽象のおかげと言えるでしょう。

プロジェクトの紹介

今回作ったプロジェクトは、MIT ライセンスのもとオープンソースとして公開しています。
興味を持っていただけたら、ぜひ GitHub で Star を押してもらえると嬉しいです！

プロジェクトの GitHub リポジトリ: https://github.com/hez2010/Brainfly

おわりに

いかがでしたか？C# の型システムを使うことで、普段は難しそうな Brainfuck コンパイラも、まるでおもちゃ感覚で作れてしまうんです。

何か質問や感想があれば、ぜひコメントで教えてください！