使用Rust实现一个Brainfuck解释器

作者: 端碗吹水 | 来源:发表于2022-06-12 11:00 被阅读0次

[TOC]

使用Rust实现一个Brainfuck解释器

brainfuck语法解析

由于 fuck 在英语中是脏话，Brainfuck 有时被称为 Brainfsck，甚至被简称为 BF。它是大多数学生们学习编译器理论知识的好朋友，这一切都是因为它 fuck simple。我们对 JIT 编译器的第一次尝试是如此的简单，甚至有点可笑。不过你想笑就笑吧，很快就会轮到编译器嘲笑你了，你会被告知自己写的解释器有多么的慢。

Brainfuck 是一种简单且最小的图灵完备编程语言。这种语言由八种运算符构成：

字符	含义
>	指针加一
<	指针减一
+	指针指向的字节的值加一
-	指针指向的字节的值减一
。	输出指针指向的单元内容（ASCII码）
,	输入内容到指针指向的单元（ASCII码）
[	如果指针指向的单元值为零，向后跳转到对应的 ] 指令的次一指令处
]	如果指针指向的单元值不为零，向前跳转到对应的 [ 指令的次一指令处

它几乎完全模仿自图灵纸带机，后者则是计算机的理论基础。理论上一切能被计算的问题都能通过 Brainfuck 被计算。

我们常常使用“可计算性”来描述一个问题是否能被计算。任何计算装置: 算盘，计算机，iPhone 等等，都不能超越图灵机模型的计算能力（考虑速度，只考虑可计算性）。这就是“图灵-邱奇论题（Church–Turing thesis）”。这是一个未被证明的假说，但是实践使人们越来越确信这个假说是真的。

一个著名的不可计算的函数是“海狸很忙函数”。该函数接受输入 n，返回具有 n 个状态的图灵机在停机之前所能打印的最大符号数量。找到海狸很忙函数的上限等于解决停机问题，该问题已被确定不能使用图灵机解决。由于海狸很忙函数不能被图灵机计算，邱奇-图灵论题断言该函数不能使用任何方法进行有效计算。

Brainfuck 可以通过解释器实现，也能通过编译器实现。当然本章将先实现一个解释器。我会使用 Rust 来编写这个解释器并省略了一部分无关紧要的代码，以使得核心逻辑清晰。

brainfuck opcode 定义

定义一个枚举类型 Opcode 来代表以上的八种运算符，用ASCII码表示，然后编写一个转换函数将字节转换为 Opcode。由于 [ 与 ] 总是成双成对的出现且互相关联，代码内使用了 jtable 来存储它们之间的位置关系，以便快速决定跳转的目的地址。当然这不是必须的，也可以在解释 [ 和 ] 的时候实时的前向搜索或后向搜索以找到对应的符号位置。

代码示例：

pub enum Opcode {
    SHR = 0x3E,
    SHL = 0x3C,
    ADD = 0x2B,
    SUB = 0x2D,
    PUTCHAR = 0x2E,
    GETCHAR = 0x2C,
    LB = 0x5B,
    RB = 0x5D,
}

impl From<u8> for Opcode {
    fn from(u: u8) -> Self {
        match u {
            0x3E => Opcode::SHR,
            0x3C => Opcode::SHL,
            0x2B => Opcode::ADD,
            0x2D => Opcode::SUB,
            0x2E => Opcode::PUTCHAR,
            0x2C => Opcode::GETCHAR,
            0x5B => Opcode::LB,
            0x5D => Opcode::RB,
            _ => unreachable!(),
        }
    }
}

pub struct Code {
    // 指令数组
    pub instrs: Vec<Opcode>,
    // 存储 [ 和 ] 的位置关系
    pub jtable: std::collections::HashMap<usize, usize>,
}

impl Code {
    pub fn from(data: Vec<u8>) -> Result<Self, Box<dyn std::error::Error>> {
        let dict: Vec<u8> = vec![
            Opcode::SHR as u8,
            Opcode::SHL as u8,
            Opcode::ADD as u8,
            Opcode::SUB as u8,
            Opcode::PUTCHAR as u8,
            Opcode::GETCHAR as u8,
            Opcode::LB as u8,
            Opcode::RB as u8,
        ];
        let instrs: Vec<Opcode> = data.iter()
            .filter(|x| dict.contains(x))
            .map(|x| Opcode::from(*x))
            .collect();
        
        // 借助栈结构来匹配 [ 和 ] 符号，然后存入 jtable 中
        let mut jstack: Vec<usize> = Vec::new();
        let mut jtable: std::collections::HashMap<usize, usize> = std::collections::HashMap::new();
        for (i, e) in instrs.iter().enumerate() {
            if Opcode::LB == *e {
                jstack.push(i);
            }
            if Opcode::RB == *e {
                let j = jstack.pop().ok_or("pop from empty list")?;
                jtable.insert(j, i);
                jtable.insert(i, j);
            }
        }
        Ok(Code { instrs, jtable })
    }
}

brainfuck 解释器实现

创建 res 目录，然后再该目录下创建 hello_world.bf 文件，其内容就是 Brainfuck 语法编写的 hello world：

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

参考：https://en.wikipedia.org/wiki/Brainfuck

然后我们 main 函数里编写一部分代码，这部分代码会从文件中读取字符，然后将它们转换为 Opcode 的数组：

mod opcode;

use opcode::{Opcode, Code};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // 获取命令行参数
    let args: Vec<String> = std::env::args().collect();
    // 第一个参数就是传递的文件路径，例如：brainfuck res/hello_world.bf
    let data = std::fs::read(&args[1])?;
    // 转换为 Opcode 的数组
    let code = Code::from(data)?;
    println!("{:?}", code.instrs);

    Ok(())
}

经过 cargo build 得到程序的二进制文件后，执行以下命令，打印的内容如下：

PS W:\WorkSpace\Rust\brainfuck> ./target/debug/brainfuck W:\WorkSpace\Rust\brainfuck\src\res\hello_world.bf
[ADD, ADD, ADD, ADD, ADD, ADD, ADD, ADD, LB, SHR, ADD, ADD, ADD, ADD, LB, SHR, ADD, ADD, SHR, ADD, ADD, ADD, SHR, ADD, ADD, ADD, SHR, ADD, SHL, SHL, SHL,
 SHL, SUB, RB, SHR, ADD, SHR, ADD, SHR, SUB, SHR, SHR, ADD, LB, SHL, RB, SHL, SUB, RB, SHR, SHR, PUTCHAR, SHR, SUB, SUB, SUB, PUTCHAR, ADD, ADD, ADD, ADD
, ADD, ADD, ADD, PUTCHAR, PUTCHAR, ADD, ADD, ADD, PUTCHAR, SHR, SHR, PUTCHAR, SHL, SUB, PUTCHAR, SHL, PUTCHAR, ADD, ADD, ADD, PUTCHAR, SUB, SUB, SUB, SUB
, SUB, SUB, PUTCHAR, SUB, SUB, SUB, SUB, SUB, SUB, SUB, SUB, PUTCHAR, SHR, SHR, ADD, PUTCHAR, SHR, ADD, ADD, PUTCHAR]

在拿到 Opcode 数组之后，便可以编写针对 Opcode 解释器。Brainfuck 的解释执行需要首先定义一个无限长的纸带（字节数组），当前指针 SP，Opcode 源代码以及程序计数器 PC，然后通过一个主循环匹配不同的指令并解释执行。代码示例：

mod opcode;

use std::io::Write;
use std::io::Read;
use opcode::{Opcode, Code};

struct Interpreter {
    // 表示无限长的纸带
    stack: Vec<u8>,
}

impl std::default::Default for Interpreter {
    fn default() -> Self {
        // 初始化，提供默认值
        Self { stack: vec![0; 1] }
    }
}

impl Interpreter {
    fn run(&mut self, data: Vec<u8>) -> Result<(), Box<dyn std::error::Error>> {
        // 将源文件中的内容转换为 Opcode 数组
        let code = Code::from(data)?;
        let code_len = code.instrs.len();
        // Program counter，程序计数器
        let mut pc: usize = 0;
        // Stack Pointer，栈指针，也就是表示在纸带的哪个位置
        let mut sp: usize = 0;

        // 解释器的主循环
        loop {
            if pc >= code_len {
                // 代码已经执行完了
                break;
            }

            // 匹配相应的指令并解释执行
            match code.instrs[pc] {
                Opcode::SHR => {
                    sp += 1;
                    // 如果达到了纸带的长度就进行填充，延长纸带的长度
                    if sp == self.stack.len() {
                        self.stack.push(0)
                    }
                }
                Opcode::SHL => sp = if sp == 0 { 0 } else { sp - 1 },
                Opcode::ADD => {
                    // 允许溢出
                    self.stack[sp] = self.stack[sp].overflowing_add(1).0;
                }
                Opcode::SUB => {
                    self.stack[sp] = self.stack[sp].overflowing_sub(1).0;
                }
                Opcode::PUTCHAR => {
                    // 将字符打印到标准输出
                    std::io::stdout().write_all(&[self.stack[sp]])?;
                }
                Opcode::GETCHAR => {
                    let mut buf: Vec<u8> = vec![0; 1];
                    // 从标准输入读取字符
                    std::io::stdin().read_exact(&mut buf)?;
                    // 将字符写到纸带上
                    self.stack[sp] = buf[0];
                }
                Opcode::LB => {
                    // 如果指针指向的单元值为零，向后跳转到对应的 ] 指令的次一指令处
                    if self.stack[sp] == 0x00 {
                        pc = code.jtable[&pc];
                    }
                }
                Opcode::RB => {
                    // 如果指针指向的单元值不为零，向前跳转到对应的 [ 指令的次一指令处
                    if self.stack[sp] != 0x00 {
                        pc = code.jtable[&pc];
                    }
                }
            }
            // 移动计数器，执行下一个指令
            pc += 1;
        }

        Ok(())
    }
}

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let args: Vec<String> = std::env::args().collect();
    let data = std::fs::read(&args[1])?;
    let mut interpreter = Interpreter::default();
    interpreter.run(data);

    Ok(())
}

编写完以上代码后，和之前一样，通过 cargo build 得到程序的二进制文件后，执行以下命令会输出 Hello World! ：

PS W:\WorkSpace\Rust\brainfuck> ./target/debug/brainfuck W:\WorkSpace\Rust\brainfuck\src\res\hello_world.bf
Hello World!
PS W:\WorkSpace\Rust\brainfuck>

测试

经过了以上小节的学习，希望你能自己独立编写好完整的 Brainfuck 解释器！当你完成时，可以尝试运行以下程序，它能在屏幕上输出斐波那契数列。虽然不太清楚上古的程序员们是如何写出这份代码的，不过我也不在乎…毕竟代码和人有一个能跑就算成功，不是吗？

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

使用中间表示

使用中间表示优化运行速度

目前为止，我们已经有了一个能正常跑的解释器，但我对上面的代码并不满意，如果你仔细观察，可以发现 Brainfuck 源代码中存在着大量冗余。将 Hello World 的代码以 Opcode 的形式打印出来：

[
    ADD,     ADD,     ADD,     ADD,     ADD,     ADD,     ADD,     ADD,
    ADD,     ADD,     LB,      SHR,     ADD,     ADD,     ADD,     ADD,
    ADD,     ADD,     ADD,     SHR,     ADD,     ADD,     ADD,     ADD,
    ADD,     ADD,     ADD,     ADD,     ADD,     ADD,     SHR,     ADD,
    ADD,     ADD,     SHR,     ADD,     SHL,     SHL,     SHL,     SHL,
    SUB,     RB,      SHR,     ADD,     ADD,     PUTCHAR, SHR,     ADD,
    PUTCHAR, ADD,     ADD,     ADD,     ADD,     ADD,     ADD,     ADD,
    PUTCHAR, PUTCHAR, ADD,     ADD,     ADD,     PUTCHAR, SHR,     ADD,
    ADD,     PUTCHAR, SHL,     SHL,     ADD,     ADD,     ADD,     ADD,
    ADD,     ADD,     ADD,     ADD,     ADD,     ADD,     ADD,     ADD,
    ADD,     ADD,     ADD,     PUTCHAR, SHR,     PUTCHAR, ADD,     ADD,
    ADD,     PUTCHAR, SUB,     SUB,     SUB,     SUB,     SUB,     SUB,
    PUTCHAR, SUB,     SUB,     SUB,     SUB,     SUB,     SUB,     SUB,
    SUB,     PUTCHAR, SHR,     ADD,     PUTCHAR, SHR,     PUTCHAR,
]

如果希望解释器执行的稍微快一点，可以对相邻的相同操作符进行折叠操作，我们已经知道一个 ADD 操作符执行的是加 1 操作，那么如果相邻着十个连续的 ADD，便可以 ADD(10) 来表示。为此定义如下的中间语言表示。

中间语言（英语：Intermediate Language，IR），在计算机科学中，是指一种应用于抽象机器（abstract machine）的编程语言，它设计的目的，是用来帮助我们分析计算机程序。这个术语源自于编译器，在编译器将源代码编译为目的码的过程中，会先将源代码转换为一个或多个的中间表述，以方便编译器进行最佳化，并产生出目的机器的机器语言。

我们定义一个新的枚举类型，用于表示 brianfuck 中几种指令的中间表达形式：

#[derive(Debug)]
pub enum IR {
    SHR(u32),
    SHL(u32),
    ADD(u8),
    SUB(u8),
    PUTCHAR,
    GETCHAR,
    JIZ(u32), // Jump if zero, alias of "["
    JNZ(u32), // Jump if not zero, alias of "]"
}

然后我们需要编写一个转换器，以便将原始代码翻译为中间代码。这很简单，代码如下：

use crate::opcode::Opcode;

pub struct Code {
    pub instrs: Vec<IR>,
}

impl Code {
    pub fn from(data: Vec<Opcode>) -> Result<Self, Box<dyn std::error::Error>> {
        // 存储匹配到的指令，遇到相同且相邻指令时进行折叠
        let mut instrs: Vec<IR> = Vec::new();
        // 借助栈结构来匹配 [ 和 ] 符号
        let mut jstack: Vec<u32> = Vec::new();

        for e in data {
            match e {
                Opcode::SHR => {
                    // 如果最后一个元素是 IR::SHR 则将其计数值加一，也就是折叠起来，否则就添加新元素
                    match instrs.last_mut() {
                        Some(IR::SHR(x)) => {
                            *x += 1;
                        }
                        _ => {
                            instrs.push(IR::SHR(1))
                        }
                    }
                }
                Opcode::SHL => {
                    match instrs.last_mut() {
                        Some(IR::SHL(x)) => {
                            *x += 1;
                        }
                        _ => {
                            instrs.push(IR::SHL(1))
                        }
                    }
                }
                Opcode::ADD => {
                    match instrs.last_mut() {
                        Some(IR::ADD(x)) => {
                            // 允许溢出
                            let (b, _) = x.overflowing_add(1);
                            *x = b;
                        }
                        _ => {
                            instrs.push(IR::ADD(1))
                        }
                    }
                }
                Opcode::SUB => {
                    match instrs.last_mut() {
                        Some(IR::SUB(x)) => {
                            // 允许溢出
                            let (b, _) = x.overflowing_add(1);
                            *x = b;
                        }
                        _ => {
                            instrs.push(IR::SUB(1))
                        }
                    }
                }
                Opcode::PUTCHAR => {
                    instrs.push(IR::PUTCHAR)
                }
                Opcode::GETCHAR => {
                    instrs.push(IR::GETCHAR)
                }
                Opcode::LB => {
                    instrs.push(IR::JIZ(0));
                    // 将 IR::JIZ 符号所在的索引位置压入栈中
                    jstack.push((instrs.len() - 1) as u32)
                }
                Opcode::RB => {
                    let j = jstack.pop().ok_or("pop from empty list")?;
                    // IR::JNZ 所存储的值是对应 IR::JIZ 指令在 instrs 中的索引位置
                    instrs.push(IR::JNZ(j));
                    let instrs_len = instrs.len();
                    match &mut instrs[j as usize] {
                        IR::JIZ(x) => {
                            // 同样，IR::JIZ 所存储的值是对应 IR::JNZ 指令在 instrs 中的索引位置
                            *x = (instrs_len - 1) as u32
                        }
                        _ => unreachable!()
                    }
                }
            }
        }

        Ok(Code { instrs })
    }
}

经过中间语言优化后的 Hello World! 代码如下所示，它大概减少了 60% 左右的大小：

[
    ADD(10),  JIZ(12),  SHR(1),  ADD(7),  SHR(1),  ADD(10),  SHR(1),  ADD(3),
    SHR(1),   ADD(1),   SHL(4),  SUB(1),  JNZ(1),  SHR(1),   ADD(2),  PUTCHAR,
    SHR(1),   ADD(1),   PUTCHAR, ADD(7),  PUTCHAR, PUTCHAR,  ADD(3),  PUTCHAR,
    SHR(1),   ADD(2),   PUTCHAR, SHL(2),  ADD(15), PUTCHAR,  SHR(1),  PUTCHAR,
    ADD(3),   PUTCHAR,  SUB(6),  PUTCHAR, SUB(8),  PUTCHAR,  SHR(1),  ADD(1),
    PUTCHAR,  SHR(1),   PUTCHAR
]

之后我们便可以针对此中间语言编写解释器，其实整体逻辑与之前并没什么太大差别。代码示例：

mod opcode;
mod ir_code;

use std::io::Write;
use std::io::Read;
use ir_code::IR;

struct Interpreter {
    // 表示无限长的纸带
    stack: Vec<u8>,
}

impl std::default::Default for Interpreter {
    fn default() -> Self {
        // 初始化，提供默认值
        Self { stack: vec![0; 1] }
    }
}

impl Interpreter {
    fn run(&mut self, data: Vec<u8>) -> Result<(), Box<dyn std::error::Error>> {
        // 将源文件中的内容转换为 Opcode 数组
        let opcode_code = opcode::Code::from(data)?;
        // 将 opcode 转换为 ir code
        let code = ir_code::Code::from(opcode_code.instrs)?;
        let code_len = code.instrs.len();
        // Program counter，程序计数器
        let mut pc: usize = 0;
        // Stack Pointer，栈指针，也就是表示在纸带的哪个位置
        let mut sp: usize = 0;

        // 解释器的主循环
        loop {
            if pc >= code_len {
                // 代码已经执行完了
                break;
            }

            // 匹配相应的指令并解释执行
            match code.instrs[pc] {
                IR::SHR(x) => {
                    sp += x as usize;
                    // 如果超过了纸带的长度就进行扩充
                    if sp >= self.stack.len() {
                        let expand = sp - self.stack.len() + 1;
                        for _ in 0..expand {
                            self.stack.push(0);
                        }
                    }
                }
                IR::SHL(x) => sp = if sp == 0 { 0 } else { sp - x as usize },
                IR::ADD(x) => {
                    // 允许溢出
                    self.stack[sp] = self.stack[sp].overflowing_add(x).0;
                }
                IR::SUB(x) => {
                    self.stack[sp] = self.stack[sp].overflowing_sub(x).0;
                }
                IR::PUTCHAR => {
                    // 将字符打印到标准输出
                    std::io::stdout().write_all(&[self.stack[sp]])?;
                }
                IR::GETCHAR => {
                    let mut buf: Vec<u8> = vec![0; 1];
                    // 从标准输入读取字符
                    std::io::stdin().read_exact(&mut buf)?;
                    // 将字符写到纸带上
                    self.stack[sp] = buf[0];
                }
                IR::JIZ(x) => {
                    // 如果指针指向的单元值为零，向后跳转到对应的 ] 指令的次一指令处
                    if self.stack[sp] == 0x00 {
                        pc = x as usize;
                    }
                }
                IR::JNZ(x) => {
                    // 如果指针指向的单元值不为零，向前跳转到对应的 [ 指令的次一指令处
                    if self.stack[sp] != 0x00 {
                        pc = x as usize;
                    }
                }
            }
            // 移动计数器，执行下一个指令
            pc += 1;
        }

        Ok(())
    }
}

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let args: Vec<String> = std::env::args().collect();
    let data = std::fs::read(&args[1])?;
    let mut interpreter = Interpreter::default();
    interpreter.run(data);

    Ok(())
}

同样，对以上代码使用 cargo build 得到程序的二进制文件后，执行以下命令将会输出 Hello World! ：

PS W:\WorkSpace\Rust\brainfuck> ./target/debug/brainfuck_ir W:\WorkSpace\Rust\brainfuck\src\res\hello_world.bf
Hello World!
PS W:\WorkSpace\Rust\brainfuck>

在测试中，基于中间语言的解释器大概要比原始解释器快 5 倍左右。但请记住本文设计的 IR 并非最优化的，其仍然有优化空间，例如，可以进一步融合连续的 ADD 和 SUB 以单个 ADD 或 SUB 替代。

下一篇文章将会介绍如何针对该中间语言编写 JIT 编译器。其核心思想是：将中间语言翻译为语义等价的汇编代码。

参考

[1] 中间语言，维基百科，https://zh.wikipedia.org/zh-hans/中間語言
[2] 邱奇-图灵论题，维基百科，https://en.wikipedia.org/wiki/Church-Turing_thesis

使用Rust实现一个Brainfuck解释器

使用Rust实现一个Brainfuck解释器

brainfuck语法解析

brainfuck opcode 定义

brainfuck 解释器实现

测试

使用中间表示

使用中间表示优化运行速度

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读