Brainfly: 用 C# 類型系統構建 Brainfuck 編譯器

Brainfuck 簡介

Brainfuck 是由 Urban Müller 在 1993 年創造的一門非常精簡的圖靈完備的編程語言。

正所謂大道至簡，這門編程語言簡單到語法只有 8 個字符，每一個字符對應一個指令，用 C 語言來描述的話就是：

字符	含義
`>`	`++ptr`
`<`	`--ptr`
`+`	`++*ptr`
`-`	`--*ptr`
`.`	`putchar(*ptr)`
`,`	`*ptr = getchar()`
`[`	`while (*ptr) {`
`]`	`}`

然后只需要提供一個已經初始化為 0 的字節數組作為內存、一個指向數組的指針、以及用于輸入輸出的兩個字節流就能夠讓程序運行了。

比如 Hello World! 程序就可以寫成：

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

C# 類型系統入門

既然要用 C# 類型系統來構建 Brainfuck 的編譯器，我們需要首先對 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 看看 .NET 的編譯器對上述代碼產生了什么機器代碼：

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);
}

我們對 T 進行泛型約束 where T : IAdditionOperators<T, T, T> 之后，就使得泛型代碼中可以通過類型 T 直接調用接口中的靜態抽象方法 operator+。

性能？

有了上面的知識，我想知道在這套類型系統之上，.NET 的編譯器到底能生成多優化的代碼，那接下來我們進行一些小的測試。

首先讓我們用類型表達一下具有 int 范圍的數字，畢竟之后構建 Brainfuck 編譯器的時候肯定會用到。眾所周知 int 有 32 位，用 16 進制表示那就是 8 位。我們可以給 16 進制的每一個數位設計一個類型，然后將 8 位十六進制數位組合起來就是數字。

首先我們起手一個 interface IHex，然后讓每一個數位都實現這個接口。

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

比如十六進制數位 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;
}

這里我們想把數字和數位區分開，因此我們定義一個跟 IHex 長得差不多但是泛型的接口 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;
    }
}

這里我們給 Value 加了 [MethodImpl(MethodImplOptions.AggressiveInlining)] 確保這個方法會被編譯器 inline。

如此一來，如果我們想表達一個 0x1234abcd，我們就可以用 Int<Hex1, Hex2, Hex3, Hex4, HexA, HexB, HexC, HexD> 來表達。

這里我們同樣去 godbolt 看看 .NET 編譯器給我們生成了怎樣的代碼：

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

可以看到直接被編譯器折疊成 0x1234ABCD 了，沒有比這更優的代碼，屬于是真正的零開銷抽象。

那么性能方面放心了之后，我們就可以開始搞 Brainfuck 編譯器了。

Brainfuck 編譯器

Brainfuck 編譯分為兩個步驟，一個是解析 Brainfuck 源代碼，一個是產生編譯結果。

對于 Brainfuck 源代碼的解析，可以說是非常的簡單，從左到右掃描一遍源代碼就可以，這里就不詳細說了。問題是怎么產生編譯結果呢？

這里我們選擇使用類型來表達一個程序，因此編譯結果自然也就是類型。

我們需要用類型來表達程序的結構。

基本操作

Brainfuck 程序離不開 4 個基本操作：

移動指針
操作內存
輸入
輸出

因此我們對此抽象出一套操作接口：

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

然后我們就可以定義各種操作了。

首先是移動指針，我們用兩個泛型參數分別表達移動指針的偏移量和下一個操作：

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);
}

接下來就是輸入和輸出了，這個比較簡單，直接操作 input 和 output 就行了：

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);
    }
}

控制流

有了上面的 4 種基本操作之后，我們就需要考慮程序控制流了。

首先，我們的程序最終畢竟是要停下來的，因此我們定義一個什么也不干的操作：

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

然后，Brainfuck 是支持循環的，這要怎么處理呢？其實也很簡單，模擬 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);
    }
}

Hello World!

有了上面的東西，我們就可以用類型表達 Brainfuck 程序了。

我們來看看最基礎的程序：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 看看 .NET 給我們的 Brainfuck 程序產生了怎樣的機器代碼？

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+rsi]
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+rsi]
mov      rdi, r15
call     [r13]System.IO.Stream:WriteByte(ubyte):this
inc      r14d
movsxd   rsi, r14d
movzx    rsi, byte  ptr [rbx+rsi]
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

這不就是

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

嗎？可以看到我們代碼里的抽象全都被 .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 編譯

如果我們想以 JIT 的形式運行 Brainfuck 代碼，那如何在運行時生成類型然后運行代碼呢？我們在 .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 編譯出來一個可執行文件呢？

你會發現，因為編譯出的東西是類型，因此我們不僅可以在 JIT 環境下跑，還能直接把類型當作程序 AOT 編譯出可執行文件！只需要編寫一個入口點方法調用 Run 即可：

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_brainfuck

這段程序編譯出來的類型也是非常的壯觀：

mandelbrot_brainfuck_type

去掉所有空格之后類型名稱足足有 165,425 個字符！

這里我們采用 5 種方案來跑這段代碼：

C 解釋器：C 語言編寫的 Brainfuck 解釋器直接運行
GCC：用 Brainfuck 翻譯器把 Brainfuck 代碼翻譯到 C 語言后，用 gcc -O3 -march=native 編譯出可執行程序后運行
Clang：用 Brainfuck 翻譯器把 Brainfuck 代碼翻譯到 C 語言后，用 clang -O3 -march=native 編譯出可執行程序后運行
.NET JIT：通過 JIT 現場生成類型后運行，統計之前會跑幾輪循環預熱
.NET AOT：通過 .NET NativeAOT 編譯出可執行程序后運行

測試環境：

系統：Debian GNU/Linux 12 (bookworm)
CPU：13th Gen Intel(R) Core(TM) i7-13700K
RAM：CORSAIR DDR5-6800MHz 32Gx2

運行 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 在這個項目里取得了最好的成績，當然，這離不開 .NET 類型系統層面的零開銷抽象。

項目地址

該項目以 MIT 協議開源，歡迎 star。

項目開源地址：https://github.com/hez2010/Brainfly

posted @ 2025-01-31 23:27 hez2010 閱讀(1829) 評論(6) 收藏舉報

刷新頁面返回頂部

hez2010