Brainfly: 用 C# 范例体系构建 Brainfuck 编译器

Brainfuck 简介

Brainfuck 是由 Urban Müller 在 1993 年创造的一门非常精简的图灵完备的编程语言。
正所谓大道至简，这门编程语言简单到语法只有 8 个字符，每一个字符对应一个指令，用 C 语言来形貌的话就是：
字符寄义>++ptr+++++++>++++++++++>+++>+.[/code]C# 范例体系入门

既然要用 C# 范例体系来构建 Brainfuck 的编译器，我们需要首先对 C# 范例体系有一些认知。
泛型体系

C# 的范例体系构建在 .NET 的范例体系之上，而众所周知 .NET 是一个有具现化泛型的范例体系的平台，意味着泛型参数不但不会被擦除，还会根据泛型参数来分发甚至特化代码。
例如：

1. ++++++++++[>+++++++>++++++++++>+++>+<<<<-]
2. >++.>+.+++++++..+++.>++.<<+++++++++++++++.
3. >.+++.------.--------.>+.>.

复制代码

对于上面的代码，调用 new Foo().Print() 会输出 0，调用 new Foo().Print() 会输出 0001-01-01T00:00:00，而调用 new Foo().Print() 则会输出 null。
更进一步，因为 .NET 泛型在运行时会根据范例参数对代码进行特化，比如：

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

复制代码

我们可以前去 godbolt 看看 .NET 的编译器对上述代码产生了什么机器代码：

1. class Calculator<T> where T : IAdditionOperators<T, T, T>
2. {
3.     public T Add(T left, T right)
4.     {
5.         return left + right;
6.     }
7. }

复制代码

可以看到我代入不同的范例参数进去，会得到各自特化后的代码。
接口的虚静态成员

你大概好奇为什么上面的 Calculator 里 left 和 right 可以直接加，这是因为 .NET 支持接口的虚静态成员。上面的 IAdditionOperators 接口其实定义长这个样子：

1. Calculator`1[int]:Add(int,int):int:this (FullOpts):
2.        lea      eax, [rsi+rdx]
3.        ret      
5. Calculator`1[long]:Add(long,long):long:this (FullOpts):
6.        lea      rax, [rsi+rdx]
7.        ret      
9. Calculator`1[ubyte]:Add(ubyte,ubyte):ubyte:this (FullOpts):
10.        add      edx, esi
11.        movzx    rax, dl
12.        ret      
14. Calculator`1[float]:Add(float,float):float:this (FullOpts):
15.        vaddss   xmm0, xmm0, xmm1
16.        ret      
18. Calculator`1[double]:Add(double,double):double:this (FullOpts):
19.        vaddsd   xmm0, xmm0, xmm1
20.        ret      

复制代码

我们对 T 进行泛型约束 where T : IAdditionOperators 之后，就使得泛型代码中可以通过范例 T 直接调用接口中的静态抽象方法 operator+。
性能？

有了上面的知识，我想知道在这套范例体系之上，.NET 的编译器到底能生成多优化的代码，那接下来我们进行一些小的测试。
首先让我们用范例表达一下具有 int 范围的数字，毕竟之后构建 Brainfuck 编译器的时候肯定会用到。众所周知 int 有 32 位，用 16 进制表现那就是 8 位。我们可以给 16 进制的每一个数位设计一个范例，然后将 8 位十六进制数位组合起来就是数字。
首先我们起手一个 interface IHex，然后让每一个数位都实现这个接口。

1. interface IAdditionOperators<TSelf, TOther, TResult>
2. {
3.     abstract static TResult operator+(TSelf self, TOther other);
4. }

复制代码

比如十六进制数位 0、6、C 可以分别表现为：

1. interface IHex
2. {
3.     abstract static int Value { get; }
4. }

复制代码

这里我们想把数字和数位区分开，因此我们定义一个跟 IHex 长得差不多但是泛型的接口 INum 用来给数字 Int 实现，之所以是泛型的是因为给万一没准以后想要扩展点浮点数之类的做考虑：

1. struct Hex0 : IHex
2. {
3.     public static int Value => 0;
4. }
6. struct Hex6 : IHex
7. {
8.     public static int Value => 6;
9. }
11. struct HexC : IHex
12. {
13.     public static int Value => 12;
14. }

复制代码

这段程序很粗暴的分别把内存从左到右写成 Hello World! 的每一位，然后把指针移回到开头后逐位输出。
不外这么看 Hello World! 还是太长了，不适合用来一上来就展示，我们换个简单点的输出 123：

1. interface INum<T>
2. {
3.     abstract static T Value { get; }
4. }
6. struct Int<H7, H6, H5, H4, H3, H2, H1, H0> : INum<int>
7.     where H7 : IHex
8.     where H6 : IHex
9.     where H5 : IHex
10.     where H4 : IHex
11.     where H3 : IHex
12.     where H2 : IHex
13.     where H1 : IHex
14.     where H0 : IHex
15. {
16.     public static int Value
17.     {
18.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
19.         get => H7.Value << 28 | H6.Value << 24 | H5.Value << 20 | H4.Value << 16 | H3.Value << 12 | H2.Value << 8 | H1.Value << 4 | H0.Value;
20.     }
21. }

复制代码

表达这个程序的范例自然就是：

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

复制代码

这里为了简洁，我把数字全都带入了数字范例，否则会变得很长。例如实际上 49 应该表达为 Int。
那怎么运行呢？很简单：

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

复制代码

即可。
我们可以借助 C# 的 Type Alias，这样我们就不需要每次运行都打那么一大长串的范例：

1. struct AddPointer<Offset, Next> : IOp
2.     where Offset : INum<int>
3.     where Next : IOp
4. {
5.     [MethodImpl(MethodImplOptions.AggressiveInlining)]
6.     public static int Run(int address, Span<byte> memory, Stream input, Stream output)
7.     {
8.         return Next.Run(address + Offset.Value, memory, input, output);
9.     }
10. }

复制代码

那我们上 godbolt 看看 .NET 给我们的 Brainfuck 程序产生了怎样的机器代码？

1. struct AddData<Data, Next> : IOp
2.     where Data : INum<int>
3.     where Next : IOp
4. {
5.     [MethodImpl(MethodImplOptions.AggressiveInlining)]
6.     public static int Run(int address, Span<byte> memory, Stream input, Stream output)
7.     {
8.         memory.UnsafeAt(address) += (byte)Data.Value;
9.         return Next.Run(address, memory, input, output);
10.     }
11. }

复制代码

这不就是

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

复制代码

吗？可以看到我们代码里的抽象全都被 .NET 给优化干净了。
而前面那个不怎么直观的 Hello World! 代码则编译出：

1. struct OutputData<Next> : IOp
2.     where Next : IOp
3. {
4.     [MethodImpl(MethodImplOptions.AggressiveInlining)]
5.     public static int Run(int address, Span<byte> memory, Stream input, Stream output)
6.     {
7.         output.WriteByte(memory.UnsafeAt(address));
8.         return Next.Run(address, memory, input, output);
9.     }
10. }
12. struct InputData<Next> : IOp
13.     where Next : IOp
14. {
15.     [MethodImpl(MethodImplOptions.AggressiveInlining)]
16.     public static int Run(int address, Span<byte> memory, Stream input, Stream output)
17.     {
18.         var data = input.ReadByte();
19.         if (data == -1)
20.         {
21.             return address;
22.         }
23.         memory.UnsafeAt(address) = (byte)data;
24.         return Next.Run(address, memory, input, output);
25.     }
26. }

复制代码

JIT 编译

如果我们想以 JIT 的形式运行 Brainfuck 代码，那如何在运行时生成范例然后运行代码呢？我们在 .NET 中有完善的反射支持，因此完全可以做到运行时创建范例。
比如根据数字来生成数字范例：

1. struct Stop : IOp
2. {
3.     [MethodImpl(MethodImplOptions.AggressiveInlining)]
4.     public static int Run(int address, Span<byte> memory, Stream input, Stream output)
5.     {
6.         return address;
7.     }
8. }

复制代码

同理也可以用于生成各种程序结构上。
最后我们只需要对构建好的范例进行反射然后调用 Run 方法即可：

1. struct Loop<Body, Next> : IOp
2.     where Body : IOp
3.     where Next : IOp
4. {
5.     [MethodImpl(MethodImplOptions.AggressiveInlining)]
6.     public static int Run(int address, Span<byte> memory, Stream input, Stream output)
7.     {
8.         while (memory.UnsafeAt(address) != 0)
9.         {
10.             address = Body.Run(address, memory, input, output);
11.         }
12.         return Next.Run(address, memory, input, output);
13.     }
14. }

复制代码

AOT 编译

那如果我不想 JIT，而是想 AOT 编译出来一个可实行文件呢？
你会发现，因为编译出的东西是范例，因此我们不但可以在 JIT 环境下跑，还能直接把范例当作程序 AOT 编译出可实行文件！只需要编写一个入口点方法调用 Run 即可：

1. using HelloWorld = struct OutputData<Next> : IOp
2.     where Next : IOp
3. {
4.     [MethodImpl(MethodImplOptions.AggressiveInlining)]
5.     public static int Run(int address, Span<byte> memory, Stream input, Stream output)
6.     {
7.         output.WriteByte(memory.UnsafeAt(address));
8.         return Next.Run(address, memory, input, output);
9.     }
10. }
12. struct InputData<Next> : IOp
13.     where Next : IOp
14. {
15.     [MethodImpl(MethodImplOptions.AggressiveInlining)]
16.     public static int Run(int address, Span<byte> memory, Stream input, Stream output)
17.     {
18.         var data = input.ReadByte();
19.         if (data == -1)
20.         {
21.             return address;
22.         }
23.         memory.UnsafeAt(address) = (byte)data;
24.         return Next.Run(address, memory, input, output);
25.     }
26. };static void Main(){    HelloWorld.Run(0, stackalloc byte[16], Console.OpenStandardInput(), Console.OpenStandardOutput());}

复制代码

然后调用 AOT 编译：

1. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
2. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
3. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
4. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
5. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
6. ++++++++++++++++++++++++++++++++>
7. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
8. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
9. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
10. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
11. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
12. +++++++++++++++++++++++++++++++++
13. <<<<<<<<<<<
14. .>.>.>.>.>.>.>.>.>.>.>.

复制代码

上面的 /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。
得出的性能测试效果如下：
[table]项目运行时间（毫秒）排名比例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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。