问题描述：

最近我们朋友间流传起一个神秘的比赛（赛题如下）：
image1129×1215 176 KB
这么好玩的比赛，必须参加啊

而且，必须拉坨 大 的

于是，决定选择解释器赛道。不是不会写编译器，是不会用Brainfuck写编译器…这玩意工作量疑似有点不是人了
但是，使用Brainfuck写个解释器我还是有把握的。

所以，开干！
接下来这里就慢慢更新>w<

第一部分：技术路线

首先，全部手写，进行到底！

对于路线，我一开始就很清晰：选我极其擅长和熟悉的C系语言做跳板。
然后在C和C++中，毫不犹豫地选了C。

总体分成下面几步：

• 挑选语法，设计一个C的子集。
• 使用这个子集完成BF解释器逻辑的编写。
• 编写一个C子集 → BF的编译器。
• 编译后手动优化目标BF代码。

这个C子集姑且就叫它bfrtc吧，BrainFuck RunTime C。
bfrtc → bf的编译器就叫它bfrtcc。

为什么要这么做呢？

• 解释器是使用C子集编写的，这样可以直接使用C编译器编译，生成的解释器是较快的，便于调试
• 只要写好bfrtcc，就可以直接把它构建成bf版，颇有一种LLVM多后端的感觉（？
  我怎么感觉我在写IR呢
• C系语法和技巧熟悉，对我自己来说很方便

具体怎么做呢？这里说说我自己的做法：
首先，这是个小项目，所以各种管理程序什么的就免了。
然后开始设计bfrtc：

1. 类型系统

目标语言是bf，所以我们当然要选择一些适应于bf的类型。
我们打开stdint.h，从里面拿出这两个类型：

• uint8_t：bf原生，永远的神。
• uint32_t：这个也必要，因为解释器需要“指针”，只有u8完全不够。

注：在我的设备上，这俩宏分别展开为unsigned char和unsigned int。

选好这两个之后，定义一下相关的类型名和宏。

这是我的第一个小巧思，一些操作在这段代码被作为C编译时作为宏展开，但作为bfrtc编译时，其会被当作built-in functions，这是为了保证良好的指令映射。
显然，这些宏定义是作为一个类似bfrtc到C的适配层的东西，在被bfrtcc编译时，它们会被忽略掉。

typedef uint8_t u8; typedef uint32_t u32; #define U8(x) ((u8)(x)) #define U32(x) ((u32)(x))

名字起短点，后面bfrtcc方便写，何乐而不为呢

有了这两个类型，一个是BF唯一原生类型，另外一个是指针专用，完全够了。
所以我们接下来的代码，里面就只会用到u8和u32
不用u64，太慢了，而且这个比赛总不能有那么逆天的寻址吧…

2. 内存布局

对于bfrtc的内存布局，首先就得明确我们得按照bf来设计。
还记得磁带吗，就是那个用来存储极大量冷数据数据的磁带！
运行bf程序的机器天生就适合把磁带作为存储器

磁带有什么特点？最显著的一点就是顺序访问不错，随机访问必炸。
所以我们要设计的内存模型，是要根据顺序访问这个特质来设计的。

先看看我们需要什么：

• 指令段.text，用于存下整个待解释的bf程序。
• 模拟段.simu，用于给我们解释的bf程序提供一个tape。
• 运算寄存段.reg，用于给很多运算提供一堆统一且快捷的中间变量。
• 状态段.state，用于存下所有的状态数据（如当前bfrtc本身tape指针位置，被解释的bf的tape指针位置，被解释的bf的PC位置等。
• 输入输出缓冲段.iobuf，用于输入输出数据的承接，同时也作为每次循环指针的归位处。（其实就一个cell）
• 循环栈段.lpstk，用于在进入循环时存循环首部的地址。

说到这里，有些人可能会疑惑：为什么需要指令段？为什么要预先存下整个程序？
因为，标准bf只有一个IO口

一开始，我是这么想的：
[.iobuf][.state][.reg][.lpstk][.simu][.text]最简单粗暴的一个。
[.simu][.state][.iobuf][.reg][.lpstk][.text]访问更快。

然后，我就发现一个问题：
你没有办法在不破坏变量的情况下，随机移动指针。
这里的“随机”和“随机访问”里面的“随机”是一个意思，指任意去自己想去的地方。并且这里限制更强，因为是“运行时随机”，意味着无法通过硬编码>和<的个数来解决。

显然，如果要可控，动态计算地移动指针，我们需要让变量跟着指针走，我们才能让指针在每个循环中仅根据硬编码的固定偏移量来读取控制变量。

于是，最终决定采用这样的“固定-浮动”内存模型：

• .simu和.text（较为）固定在bfrtc所运行的tape上（这里不是被模拟的tape，是bfrtc本身运行在的tape）
• .iobuf，.state，.lpstk和.reg（在bfrtc的原子操作层面上）严格跟随指针移动，两侧预留padding cell，下称为.pdc段，移动时，把头部遇到的固定数据移动到尾部。
• 具体的排布方式：
  • 初始状态[.text][.pdc][.state][.iobuf][.reg][.lpstk][.pdc][.simu]
  • 固定段高低位<-[.text]-| 0 |-[.simu]->即：.text段的高位是代码的低位，.simu的低位是模拟tape的低位（这样能极大减小指针来回移动的幅度）
• 所有浮动段都是可读可写的。

注：上面说的“较为固定”，是因为当浮动段经过固定段时，固定段被经过的单元格会有整个浮动段大小的左右位移，但除此之外不会有其余的移动。

举个栗子

(0) {X} {Y} {Z} (0) [1] [2] [3] [4] [5] [6] [7] [1] (0) {X} {Y} {Z} (0) [2] [3] [4] [5] [6] [7] [1] [2] (0) {X} {Y} {Z} (0) [3] [4] [5] [6] [7] [1] [2] [3] (0) {X} {Y} {Z} (0) [4] [5] [6] [7] [1] [2] [3] [4] (0) {X} {Y} {Z} (0) [5] [6] [7]

上面的 中，指针进行了4次连续右移，里面展示了每个格子的具体作用是如何发生改变的。例中，(0)代表.pdc段的格子，[num]代表固定段的格子，{X}代表浮动段的格子。

于是，我们就有了一套还行的内存结构，为后面的流程控制，以及u32的实现等等提供了有力的支持。

3. 控制语句

1章3节·未完待续>w<

4. 原子操作

1章4节·未完待续>w<
这两节还没写是因为在实现的时候有很多东西要根据情况来回头调整设计，所以准备等稳定了再写

第二部分：程序设计

第二部分前言

既然要开始写了，不妨看看前面bfrtc运行需要什么：

• 一个空的浮动段（包括了.pdc段），里面有很多变量，初始化值是可以在bfrtc程序开头自己设定的。
• 一个完全空的，向右延伸的.simu段
• 一个.text段。

佬友们一定能一眼看出，.text是最特殊的一段：

• 它是唯一一个只读段。
• bfrtc程序运行时，其余段都可以是空的，但.text段要填满待执行的程序。
  其实可以不填满，使用bfrtc把指令读入一并写了，但一想到这种情况下要带着一个完全没有用的浮动段到处跑，就感觉会有很大的overhead
• （依赖于前面的设计）.text段是唯一一个与bfrtc运行其上的tape（非.simu段）方向相反的“重型”段。（后面会解释，这个设计也和这一节的内容有关）
• 它是唯一一个单元格内可以通过简单的设计保证完全不取到0的段，因为总共只有8种指令。（这一点也比较重要）

第一章好像提到过，bf只有一个IO口，意味着我们要把程序和程序的输入同时塞入I口，显然，先塞入程序是方便的。

再来说说为什么先塞入程序是个很妙的决定：
这个解释器运行在bf上，意味着它的内存是线性的，就像这样：
b563d1a5-8519-4ec4-8d61-bc2a34c202f7778×217 2.16 KB

通过预先设定.text段的大小，加上上一章的内存布局设计，我们可以把左右拼起来，变成两个维度（浮动段做了简化处理，画在了指针下面，表示其与指针位置绑定并易于访问）：
159ac12e-4f31-45fe-a542-d4a7e261bc991081×217 3.41 KB

发现没有？没有地方可以放下输入，除非你愿意带着你可能大于64B的浮动段穿越几百KB甚至几MB的.simu段或者.text段，只为了读一个输入再回来。

—— 我们只有两个维度，吗？

—— 不，我们有三个，这就是设计的力量。

我们考虑需要的三个维度的特性：

• .text和输入流只读，.simu可读可写。
• .text和.simu可随机访问，输入流只能顺序访问，绝不回头。

我们不需要更改输入流的值，也不需要折返访问。（因为我们要运行的bf程序的输入流也是这样的）

所以，当我们做出这样的内存布局设计时，我们其实已经有了三个维度：
48c8894e-617f-45e3-bb53-d1fd7088170a847×541 7.08 KB

这样，我们在访问每一个区段的速度都已经到了极限（吧，至少我自己是这么认为的，说不定有更好的设计呢？）

因为读入的方法，就只有先读入输入流和先读入程序两种。根据上面的分析，我们要在运行时读入输入流，所以先输入程序在内存上更优。

这样我们就说明了：先塞入程序，不仅在流程上是独立的一块，在内存布局上也会带来好处。

所以，我决定把这个加载，预处理程序段，以及设置一些东西让bfrtc程序可以直接开始运行的程序分离出来。

就叫它引导程序boot.bf吧

除了引导程序，还需要实现几个东西：

• 使用bfrtc编写的bf解释器。
• bfrtc到bf的编译器。
• bfrtc的内建操作对应的bf实现。
• bfrtc引入的扩展类型u32的bf实现及其配套设施。

这一章就是关于怎么实现这些部分的。

1. 引导程序boot

这一个程序使用bf手写，它会：

• 读取指令直到指令终止符。
• 重新编码指令以加速后面的运行。
• 将指令逆序写入.text段。
• （有可能）做点指令折叠什么的优化 咕咕咕咕咕

明确了它会干什么，我们就可以开始实现它了。

2章1节·未完待续>w<

全文·未完待续>w<

网友解答：

---

--【壹】--：

占个位，学习一下

---

--【贰】--：

有点意思，占个位，坐等更新

---

--【叁】--：

！？强强？！

---

--【肆】--：

牛逼，在学计组刚好提到这个brainfuck

---

--【伍】--：

何意味，完全看不懂了

---

--【陆】--：

好强欸w