Brainfly: 用 C# 类型系统构建 Brainfuck 编译器
Brainfuck 简介Brainfuck 是由 Urban Müller 在 1993 年创造的一门非常精简的图灵完备的编程语言。
正所谓大道至简，这门编程语言简单到语法只有 8 个字符，每一个字符对应一个指令，用 C 语言来描述的话就是：
字符含义>++ptr+++++++>++++++++++>+++>+.C# 类型系统入门
既然要用 C# 类型系统来构建 Brainfuck 的编译器，我们需要首先对 C# 类型系统有一些认知。
泛型系统
C# 的类型系统构建在 .NET 的类型系统之上，而众所周知 .NET 是一个有具现化泛型的类型系统的平台，意味着泛型参数不仅不会被擦除，还会根据泛型参数来分发甚至特化代码。
例如：
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.对于上面的代码，调用 new Foo().Print() 会输出 0，调用 new Foo().Print() 会输出 0001-01-01T00:00:00，而调用 new Foo().Print() 则会输出 null。
更进一步，因为 .NET 泛型在运行时会根据类型参数对代码进行特化，比如：
class Foo<T>
{
public void Print() => Console.WriteLine(default(T)?.ToString() ?? "null");
}我们可以前往 godbolt 看看 .NET 的编译器对上述代码产生了什么机器代码：
class Calculator<T> where T : IAdditionOperators<T, T, T>
{
public T Add(T left, T right)
{
return left + right;
}
}可以看到我代入不同的类型参数进去，会得到各自特化后的代码。
接口的虚静态成员
你可能好奇为什么上面的 Calculator 里 left 和 right 可以直接加，这是因为 .NET 支持接口的虚静态成员。上面的 IAdditionOperators 接口其实定义长这个样子：
Calculator`1:Add(int,int):int:this (FullOpts):
lea eax,
ret
Calculator`1:Add(long,long):long:this (FullOpts):
lea rax,
ret
Calculator`1:Add(ubyte,ubyte):ubyte:this (FullOpts):
add edx, esi
movzx rax, dl
ret
Calculator`1:Add(float,float):float:this (FullOpts):
vaddss xmm0, xmm0, xmm1
ret
Calculator`1:Add(double,double):double:this (FullOpts):
vaddsd xmm0, xmm0, xmm1
ret 我们对 T 进行泛型约束 where T : IAdditionOperators 之后，就使得泛型代码中可以通过类型 T 直接调用接口中的静态抽象方法 operator+。
性能？
有了上面的知识，我想知道在这套类型系统之上，.NET 的编译器到底能生成多优化的代码，那接下来我们进行一些小的测试。
首先让我们用类型表达一下具有 int 范围的数字，毕竟之后构建 Brainfuck 编译器的时候肯定会用到。众所周知 int 有 32 位，用 16 进制表示那就是 8 位。我们可以给 16 进制的每一个数位设计一个类型，然后将 8 位十六进制数位组合起来就是数字。
首先我们起手一个 interface IHex，然后让每一个数位都实现这个接口。
interface IAdditionOperators<TSelf, TOther, TResult>
{
abstract static TResult operator+(TSelf self, TOther other);
}比如十六进制数位 0、6、C 可以分别表示为：
interface IHex
{
abstract static int Value { get; }
}这里我们想把数字和数位区分开，因此我们定义一个跟 IHex 长得差不多但是泛型的接口 INum 用来给数字 Int 实现，之所以是泛型的是因为给万一没准以后想要扩展点浮点数之类的做考虑：
struct Hex0 : IHex
{
public static int Value => 0;
}
struct Hex6 : IHex
{
public static int Value => 6;
}
struct HexC : IHex
{
public static int Value => 12;
}这段程序很粗暴的分别把内存从左到右写成 Hello World! 的每一位，然后把指针移回到开头后逐位输出。
不过这么看 Hello World! 还是太长了，不适合用来一上来就展示，我们换个简单点的输出 123：
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
{
get => H7.Value << 28 | H6.Value << 24 | H5.Value << 20 | H4.Value << 16 | H3.Value << 12 | H2.Value << 8 | H1.Value << 4 | H0.Value;
}
}表达这个程序的类型自然就是：
Int`8:get_Value():int (FullOpts):
push rbp
mov rbp, rsp
mov eax, 0x1234ABCD
pop rbp
ret 这里为了简洁，我把数字全都带入了数字类型，不然会变得很长。例如实际上 49 应该表达为 Int。
那怎么运行呢？很简单：
interface IOp
{
abstract static int Run(int address, Span<byte> memory, Stream input, Stream output);
}即可。
我们可以借助 C# 的 Type Alias，这样我们就不需要每次运行都打那么一大长串的类型：
struct AddPointer<Offset, Next> : IOp
where Offset : INum<int>
where Next : IOp
{
public static int Run(int address, Span<byte> memory, Stream input, Stream output)
{
return Next.Run(address + Offset.Value, memory, input, output);
}
}那我们上 godbolt 看看 .NET 给我们的 Brainfuck 程序产生了怎样的机器代码？
struct AddData<Data, Next> : IOp
where Data : INum<int>
where Next : IOp
{
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);
}
}这不就是
internal static ref T UnsafeAt<T>(this Span<T> span, int address)
{
return ref Unsafe.Add(ref MemoryMarshal.GetReference(span), address);
}吗？可以看到我们代码里的抽象全都被 .NET 给优化干净了。
而前面那个不怎么直观的 Hello World! 代码则编译出：
struct OutputData<Next> : IOp
where Next : IOp
{
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
{
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);
}
}JIT 编译
如果我们想以 JIT 的形式运行 Brainfuck 代码，那如何在运行时生成类型然后运行代码呢？我们在 .NET 中有完善的反射支持，因此完全可以做到运行时创建类型。
比如根据数字来生成数字类型：
struct Stop : IOp
{
public static int Run(int address, Span<byte> memory, Stream input, Stream output)
{
return address;
}
}同理也可以用于生成各种程序结构上。
最后我们只需要对构建好的类型进行反射然后调用 Run 方法即可：
struct Loop<Body, Next> : IOp
where Body : IOp
where Next : IOp
{
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);
}
}AOT 编译
那如果我不想 JIT，而是想 AOT 编译出来一个可执行文件呢？
你会发现，因为编译出的东西是类型，因此我们不仅可以在 JIT 环境下跑，还能直接把类型当作程序 AOT 编译出可执行文件！只需要编写一个入口点方法调用 Run 即可：
using HelloWorld = struct OutputData<Next> : IOp
where Next : IOp
{
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
{
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);
}
};static void Main(){ HelloWorld.Run(0, stackalloc byte, Console.OpenStandardInput(), Console.OpenStandardOutput());}然后调用 AOT 编译：
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++
<<<<<<<<<<<
.>.>.>.>.>.>.>.>.>.>.>.上面的 /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
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]