人妻夜夜爽天天爽三区丁香花-人妻夜夜爽天天爽三-人妻夜夜爽天天爽欧美色院-人妻夜夜爽天天爽免费视频-人妻夜夜爽天天爽-人妻夜夜爽天天

Brainfuck 簡介#

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

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

然后只需要提供一個(gè)已經(jīng)初始化為 0 的字節(jié)數(shù)組作為內(nèi)存、一個(gè)指向數(shù)組的指針、以及用于輸入輸出的兩個(gè)字節(jié)流就能夠讓程序運(yùn)行了。

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

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

C# 類型系統(tǒng)入門#

既然要用 C# 類型系統(tǒng)來構(gòu)建 Brainfuck 的編譯器，我們需要首先對(duì) C# 類型系統(tǒng)有一些認(rèn)知。

泛型系統(tǒng)#

C# 的類型系統(tǒng)構(gòu)建在 .NET 的類型系統(tǒng)之上，而眾所周知 .NET 是一個(gè)有具現(xiàn)化泛型的類型系統(tǒng)的平臺(tái)，意味著泛型參數(shù)不僅不會(huì)被擦除，還會(huì)根據(jù)泛型參數(shù)來分發(fā)甚至特化代碼。

例如：

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

對(duì)于上面的代碼，調(diào)用 new Foo<int>().Print() 會(huì)輸出 0，調(diào)用 new Foo<DateTime>().Print() 會(huì)輸出 0001-01-01T00:00:00，而調(diào)用 new Foo<string>().Print() 則會(huì)輸出 null。

更進(jìn)一步，因?yàn)?.NET 泛型在運(yùn)行時(shí)會(huì)根據(jù)類型參數(shù)對(duì)代碼進(jìn)行特化，比如：

class Calculator<T> where T : IAdditionOperators<T, T, T>
{
    public T Add(T left, T right)
    {
        return left + right;
    }
}

我們可以前往 godbolt 看看 .NET 的編譯器對(duì)上述代碼產(chǎn)生了什么機(jī)器代碼：

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      

可以看到我代入不同的類型參數(shù)進(jìn)去，會(huì)得到各自特化后的代碼。

接口的虛靜態(tài)成員#

你可能好奇為什么上面的 Calculator<T> 里 left 和 right 可以直接加，這是因?yàn)?.NET 支持接口的虛靜態(tài)成員。上面的 IAdditionOperators 接口其實(shí)定義長這個(gè)樣子：

interface IAdditionOperators<TSelf, TOther, TResult>
{
    abstract static TResult operator+(TSelf self, TOther other);
}

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

性能？#

有了上面的知識(shí)，我想知道在這套類型系統(tǒng)之上，.NET 的編譯器到底能生成多優(yōu)化的代碼，那接下來我們進(jìn)行一些小的測(cè)試。

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

首先我們起手一個(gè) interface IHex，然后讓每一個(gè)數(shù)位都實(shí)現(xiàn)這個(gè)接口。

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

比如十六進(jìn)制數(shù)位 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;
}

這里我們想把數(shù)字和數(shù)位區(qū)分開，因此我們定義一個(gè)跟 IHex 長得差不多但是泛型的接口 INum<T> 用來給數(shù)字 Int 實(shí)現(xiàn)，之所以是泛型的是因?yàn)榻o萬一沒準(zhǔn)以后想要擴(kuò)展點(diǎn)浮點(diǎn)數(shù)之類的做考慮：

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)] 確保這個(gè)方法會(huì)被編譯器 inline。

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

這里我們同樣去 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 了，沒有比這更優(yōu)的代碼，屬于是真正的零開銷抽象。

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

Brainfuck 編譯器#

Brainfuck 編譯分為兩個(gè)步驟，一個(gè)是解析 Brainfuck 源代碼，一個(gè)是產(chǎn)生編譯結(jié)果。

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

這里我們選擇使用類型來表達(dá)一個(gè)程序，因此編譯結(jié)果自然也就是類型。

我們需要用類型來表達(dá)程序的結(jié)構(gòu)。

基本操作#

Brainfuck 程序離不開 4 個(gè)基本操作：

• 移動(dòng)指針
• 操作內(nèi)存
• 輸入
• 輸出

因此我們對(duì)此抽象出一套操作接口：

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

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

首先是移動(dòng)指針，我們用兩個(gè)泛型參數(shù)分別表達(dá)移動(dòng)指針的偏移量和下一個(gè)操作：

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

然后是操作內(nèi)存：

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 不需要什么內(nèi)存邊界檢查，因此這里我用了一個(gè) UnsafeAt 擴(kuò)展方法跳過邊界檢查：

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

接下來就是輸入和輸出了，這個(gè)比較簡單，直接操作 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 種基本操作之后，我們就需要考慮程序控制流了。

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

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

然后，Brainfuck 是支持循環(huán)的，這要怎么處理呢？其實(shí)也很簡單，模擬 while (*ptr) { 這個(gè)操作就行了，也就是反復(fù)執(zhí)行當(dāng)前操作更新指針，直到指針指向的數(shù)據(jù)變成 0，然后跳到下一個(gè)操作去。

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!#

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

我們來看看最基礎(chǔ)的程序：Hello World!。

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

上面這個(gè)實(shí)現(xiàn)可能不是很直觀，那我們換一種非常直觀的實(shí)現(xiàn)：

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
+++++++++++++++++++++++++++++++++
<<<<<<<<<<<
.>.>.>.>.>.>.>.>.>.>.>.

這段程序很粗暴的分別把內(nèi)存從左到右寫成 Hello World! 的每一位，然后把指針移回到開頭后逐位輸出。

不過這么看 Hello World! 還是太長了，不適合用來一上來就展示，我們換個(gè)簡單點(diǎn)的輸出 123：

+++++++++++++++++++++++++++++++++++++++++++++++++
>
++++++++++++++++++++++++++++++++++++++++++++++++++
>
+++++++++++++++++++++++++++++++++++++++++++++++++++
<<
.>.>.

表達(dá)這個(gè)程序的類型自然就是：

AddData<49, AddPointer<1, AddData<50, AddPointer<1, AddData<51, // 分別設(shè)置 1 2 3
AddPointer<-2, // 指針移回開頭
OutputData<AddPointer<1, OutputData<AddPointer<1, OutputData< // 輸出
Stop>>>>>>>>>>> // 停止

這里為了簡潔，我把數(shù)字全都帶入了數(shù)字類型，不然會(huì)變得很長。例如實(shí)際上 49 應(yīng)該表達(dá)為 Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex3, Hex1>。

那怎么運(yùn)行呢？很簡單：

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，這樣我們就不需要每次運(yùn)行都打那么一大長串的類型：

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 程序產(chǎn)生了怎樣的機(jī)器代碼？

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 給優(yōu)化干凈了。

而前面那個(gè)不怎么直觀的 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 的形式運(yùn)行 Brainfuck 代碼，那如何在運(yùn)行時(shí)生成類型然后運(yùn)行代碼呢？我們?cè)?.NET 中有完善的反射支持，因此完全可以做到運(yùn)行時(shí)創(chuàng)建類型。

比如根據(jù)數(shù)字來生成數(shù)字類型：

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

同理也可以用于生成各種程序結(jié)構(gòu)上。

最后我們只需要對(duì)構(gòu)建好的類型進(jìn)行反射然后調(diào)用 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 編譯出來一個(gè)可執(zhí)行文件呢？

你會(huì)發(fā)現(xiàn)，因?yàn)榫幾g出的東西是類型，因此我們不僅可以在 JIT 環(huán)境下跑，還能直接把類型當(dāng)作程序 AOT 編譯出可執(zhí)行文件！只需要編寫一個(gè)入口點(diǎn)方法調(diào)用 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());
}

然后調(diào)用 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。

運(yùn)行編譯后的程序就能直接輸出 Hello World!。

性能測(cè)試#

這里我們采用一段用 Brainfuck 編寫的 Mandelbrot 程序進(jìn)行性能測(cè)試，代碼見 Pastebin。

它運(yùn)行之后會(huì)在屏幕上輸出：

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

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

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

• C 解釋器：C 語言編寫的 Brainfuck 解釋器直接運(yùn)行
• GCC：用 Brainfuck 翻譯器把 Brainfuck 代碼翻譯到 C 語言后，用 gcc -O3 -march=native 編譯出可執(zhí)行程序后運(yùn)行
• Clang：用 Brainfuck 翻譯器把 Brainfuck 代碼翻譯到 C 語言后，用 clang -O3 -march=native 編譯出可執(zhí)行程序后運(yùn)行
• .NET JIT：通過 JIT 現(xiàn)場(chǎng)生成類型后運(yùn)行，統(tǒng)計(jì)之前會(huì)跑幾輪循環(huán)預(yù)熱
• .NET AOT：通過 .NET NativeAOT 編譯出可執(zhí)行程序后運(yùn)行

測(cè)試環(huán)境：

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

運(yùn)行 10 次取最優(yōu)成績，為了避免輸出影響性能，所有輸出重定向到 /dev/null。

得出的性能測(cè)試結(jié)果如下：

最后 .NET AOT 在這個(gè)項(xiàng)目里取得了最好的成績，當(dāng)然，這離不開 .NET 類型系統(tǒng)層面的零開銷抽象。

項(xiàng)目地址#

該項(xiàng)目以 MIT 協(xié)議開源，歡迎 star。

項(xiàng)目開源地址：https://github.com/hez2010/Brainfly

?轉(zhuǎn)自https://www.cnblogs.com/hez2010/p/18696074/brainfly-brainfuck-compiler-built-with-csharp