Brainfuck 是由 Urban Müller 在 1993 年创造的一门非常精简的图灵完备的编程语言。正所谓大道至简这门编程语言简单到语法只有 8 个字符每一个字符对应一个指令用 C 语言来描述的话就是字符含义ptr--ptr*ptr---*ptr.putchar(*ptr),*ptr getchar()[while (*ptr) {]}然后只需要提供一个已经初始化为 0 的字节数组作为内存、一个指向数组的指针、以及用于输入输出的两个字节流就能够让程序运行了。比如 Hello World! 程序就可以写成Copy[-] ....... ..------.--------...C# 类型系统入门#既然要用 C# 类型系统来构建 Brainfuck 的编译器我们需要首先对 C# 类型系统有一些认知。泛型系统#C# 的类型系统构建在 .NET 的类型系统之上而众所周知 .NET 是一个有具现化泛型的类型系统的平台意味着泛型参数不仅不会被擦除还会根据泛型参数来分发甚至特化代码。例如Copyclass FooT { public void Print() Console.WriteLine(default(T)?.ToString() ?? null); }对于上面的代码调用new Fooint().Print()会输出0调用new FooDateTime().Print()会输出0001-01-01T00:00:00而调用new Foostring().Print()则会输出null。更进一步因为 .NET 泛型在运行时会根据类型参数对代码进行特化比如Copyclass CalculatorT where T : IAdditionOperatorsT, T, T { public T Add(T left, T right) { return left right; } }我们可以前往 godbolt 看看 .NET 的编译器对上述代码产生了什么机器代码CopyCalculator1[int]:Add(int,int):int:this (FullOpts): lea eax, [rsirdx] ret Calculator1[long]:Add(long,long):long:this (FullOpts): lea rax, [rsirdx] ret Calculator1[ubyte]:Add(ubyte,ubyte):ubyte:this (FullOpts): add edx, esi movzx rax, dl ret Calculator1[float]:Add(float,float):float:this (FullOpts): vaddss xmm0, xmm0, xmm1 ret Calculator1[double]:Add(double,double):double:this (FullOpts): vaddsd xmm0, xmm0, xmm1 ret可以看到我代入不同的类型参数进去会得到各自特化后的代码。接口的虚静态成员#你可能好奇为什么上面的CalculatorT里left和right可以直接加这是因为 .NET 支持接口的虚静态成员。上面的IAdditionOperators接口其实定义长这个样子Copyinterface IAdditionOperatorsTSelf, TOther, TResult { abstract static TResult operator(TSelf self, TOther other); }我们对T进行泛型约束where T : IAdditionOperatorsT, T, T之后就使得泛型代码中可以通过类型T直接调用接口中的静态抽象方法operator。性能#有了上面的知识我想知道在这套类型系统之上.NET 的编译器到底能生成多优化的代码那接下来我们进行一些小的测试。首先让我们用类型表达一下具有int范围的数字毕竟之后构建 Brainfuck 编译器的时候肯定会用到。众所周知int有 32 位用 16 进制表示那就是 8 位。我们可以给 16 进制的每一个数位设计一个类型然后将 8 位十六进制数位组合起来就是数字。首先我们起手一个interface IHex然后让每一个数位都实现这个接口。Copyinterface IHex { abstract static int Value { get; } }比如十六进制数位 0、6、C 可以分别表示为Copystruct Hex0 : IHex { public static int Value 0; } struct Hex6 : IHex { public static int Value 6; } struct HexC : IHex { public static int Value 12; }这里我们想把数字和数位区分开因此我们定义一个跟IHex长得差不多但是泛型的接口INumT用来给数字Int实现之所以是泛型的是因为给万一没准以后想要扩展点浮点数之类的做考虑Copyinterface INumT { abstract static T Value { get; } } struct IntH7, H6, H5, H4, H3, H2, H1, H0 : INumint 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我们就可以用IntHex1, Hex2, Hex3, Hex4, HexA, HexB, HexC, HexD来表达。这里我们同样去 godbolt 看看 .NET 编译器给我们生成了怎样的代码CopyInt8[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 个基本操作移动指针操作内存输入输出因此我们对此抽象出一套操作接口Copyinterface IOp { abstract static int Run(int address, Spanbyte memory, Stream input, Stream output); }然后我们就可以定义各种操作了。首先是移动指针我们用两个泛型参数分别表达移动指针的偏移量和下一个操作Copystruct AddPointerOffset, Next : IOp where Offset : INumint where Next : IOp { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int Run(int address, Spanbyte memory, Stream input, Stream output) { return Next.Run(address Offset.Value, memory, input, output); } }然后是操作内存Copystruct AddDataData, Next : IOp where Data : INumint where Next : IOp { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int Run(int address, Spanbyte memory, Stream input, Stream output) { memory.UnsafeAt(address) (byte)Data.Value; return Next.Run(address, memory, input, output); } }我们 Brainfuck 不需要什么内存边界检查因此这里我用了一个UnsafeAt扩展方法跳过边界检查Copyinternal static ref T UnsafeAtT(this SpanT span, int address) { return ref Unsafe.Add(ref MemoryMarshal.GetReference(span), address); }接下来就是输入和输出了这个比较简单直接操作input和output就行了Copystruct OutputDataNext : IOp where Next : IOp { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int Run(int address, Spanbyte memory, Stream input, Stream output) { output.WriteByte(memory.UnsafeAt(address)); return Next.Run(address, memory, input, output); } } struct InputDataNext : IOp where Next : IOp { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int Run(int address, Spanbyte 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 种基本操作之后我们就需要考虑程序控制流了。首先我们的程序最终毕竟是要停下来的因此我们定义一个什么也不干的操作Copystruct Stop : IOp { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int Run(int address, Spanbyte memory, Stream input, Stream output) { return address; } }然后Brainfuck 是支持循环的这要怎么处理呢其实也很简单模拟while (*ptr) {这个操作就行了也就是反复执行当前操作更新指针直到指针指向的数据变成 0然后跳到下一个操作去。Copystruct LoopBody, Next : IOp where Body : IOp where Next : IOp { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int Run(int address, Spanbyte 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!。Copy[-] ....... ..------.--------...上面这个实现可能不是很直观那我们换一种非常直观的实现Copy ............这段程序很粗暴的分别把内存从左到右写成Hello World!的每一位然后把指针移回到开头后逐位输出