Brainfly: 用 C# 类型系统构建 Brainfuck 编译器

fdfv232

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 3AddPointer<-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     rbppush     r15push     r14push     r13push     rbxlea      rbp, [rsp+0x20]mov      rbx, rsimov      r15, r8movsxd   rsi, ediadd      rsi, rbxadd      byte  ptr [rsi], 49 ; '1'inc      edimovsxd   rsi, ediadd      rsi, rbxadd      byte  ptr [rsi], 50 ; '2'inc      edimovsxd   rsi, ediadd      rsi, rbxadd      byte  ptr [rsi], 51 ; '3'lea      r14d, [rdi-0x02]movsxd   rsi, r14dmovzx    rsi, byte  ptr [rbx+rsi]mov      rdi, r15mov      rax, qword ptr [r15]mov      r13, qword ptr [rax+0x68]call     [r13]System.IO.Stream:WriteByte(ubyte):thisinc      r14dmovsxd   rsi, r14dmovzx    rsi, byte  ptr [rbx+rsi]mov      rdi, r15call     [r13]System.IO.Stream:WriteByte(ubyte):thisinc      r14dmovsxd   rsi, r14dmovzx    rsi, byte  ptr [rbx+rsi]mov      rdi, r15call     [r13]System.IO.Stream:WriteByte(ubyte):thismov      eax, r14dpop      rbxpop      r13pop      r14pop      r15pop      rbpret      这不就是
*(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。
它运行之后会在屏幕上输出：

这段程序编译出来的类型也是非常的壮观：

去掉所有空格之后类型名称足足有 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.658755.59GCC901.022531.03Clang881.717721.01.NET JIT925.159641.06.NET AOT872.228711.00最后 .NET AOT 在这个项目里取得了最好的成绩，当然，这离不开 .NET 类型系统层面的零开销抽象。
项目地址

该项目以 MIT 协议开源，欢迎 star。
项目开源地址：https://github.com/hez2010/Brainfly