Brainfuck 编程语言

Brainfuck 只有 8 条指令。假设 mp 为内存指针,mvmp 所指内存单元的值,最初两者都为 0

  • [:如果 mv == 0,则跳转到相应 ] 指令的下一条指令处;否则,执行下一条指令。
  • ]:如果 mv != 0,则跳转到相应 [ 指令的下一条指令处;否则,执行下一条指令。
  • +:当前内存单元值加一,即 mv += 1(模 256)。
  • -:当前内存单元值减一,即 mv -= 1(模 256)。
  • <:内存指针前移,即 mp -= 1
  • >:内存指针后移,即 mp += 1
  • .:输出当前内存单元值 mv
  • ,:从用户输入读取一个字节并将其存储在当前内存单元 mp

例如

+[-]++.
  • +:内存单元值 mv 加一,得到 mv = 1
  • [:因为 mv != 0 ,所以执行下一条指令 -
  • -:内存单元值 mv 加一,得到 mv = 0
  • ]:因为 mv == 0 ,所以执行下一条指令 +
  • +:内存单元值 mv 加一,得到 mv = 1
  • +:内存单元值 mv 加一,得到 mv = 2
  • .:输出当前内存单元值 mv
[+++++]+
  • [:因为 mv = 0,所以跳转到相应 ] 的下一条指令 +
  • +:内存单元值 mv 加一,得到 mv = 1

将 Brianfuck 程序编译为 Brainfuck 汇编程序

Brainfuck 不是一个指令集架构(ISA),因为指令不是自包含的。它们依赖于上下文,即 [] 不包含跳转目标地址。

为了弥补这一缺陷,我们对 [] 指令进行修改,让它们后面跟上跳转目标地址。编译器会跟踪一个栈,该栈存储尚未被匹配的 [。用 c 表示一个计数器,表示到目前位置已经执行了多少条指令。

  • 当遇到 [ 符号时,a) 将 c 压栈,b) 输出指令 [0,其中 0 是跳转目标地址的占位符
  • 当遇到 ] 符号时,a) 出栈,得到 i,b) 将输出序列中位置为 i 的指令 [ 的占位符设置为 i,即改为 [i,c) 输出指令 ]i+1
  • 当遇到其它字符时,直接输出该字符,栈中不进行任何修改。

代码如下:

/// Initialize a Brainfuck Program from an appropriate file
pub fn from(code: &str) -> Result<Program> {
    // keeps track of loop beginnings while (potentially nested) loops are being compiled
    let mut loop_stack = vec![];
    let mut instructions = Vec::new();
    for c in code.chars() {
        // to allow skipping a loop and jumping back to the loop's beginning, the respective start and end positions
        // are recorded in the program
        if c == '[' {
            // placeholder for position of loop's end, to be filled in once position is known
            instructions.push(Instruction::decode_from(c, Some(0)));
            loop_stack.push(instructions.len() - 1);
        } else if c == ']' {
            // record loop's end in beginning
            let start_pos = loop_stack.pop().unwrap();
            instructions[start_pos].op_a = instructions.len() as u32;
            // record loop's start
            instructions.push(Instruction::decode_from(c, Some((start_pos + 1) as u32)));
        } else if c != ' ' && c != '\n' && c != '\r' {
            instructions.push(Instruction::decode_from(c, None));
        }
    }
    Ok(Self { instructions })
}

对于输入 [----],输出为 Program { instructions: [[5, -, -, -, -, ]1] }

Brainfuck 虚拟机

Brainfuck 虚拟机的状态由两种寄存器组成:指令指针 pc 和无限个数据指针 mp ;初始值都为 0。mvmp 中存储的值。

任何虚拟机都定义了一个状态转换函数。运行虚拟机会反复将此函数应用于状态,直到满足终止条件。

在 Brainfuck VM 中,当指令计数器 pc 超出程序长度时终止。

执行一条指令括取指令,执行,指令指针 pc 加一,代码如下:

/// Executes one cycle of the program, returning whether the program has finished.
#[inline]
#[allow(clippy::too_many_lines)]
fn execute_cycle(&mut self) -> Result<bool, ExecutionError> {
    // Fetch the instruction at the current program counter.
    let instruction = self.fetch();

    // Execute the instruction.
    self.execute_instruction(&instruction)?;

    // Increment the clock.
    self.state.global_clk += 1;

    let done = self.state.pc == self.program.instructions.len() as u32;
    Ok(done)
}

program[pc] 表示位置 pc 处的指令

状态转换函数如下:

  • 如果 program[pc]>,则 mp += 1pc += 1
  • 如果 program[pc]<,则 mp -= 1pc += 1
  • 如果 program[pc]+, 先从 mp 中读出值 mv,然后执行mv += 1,最后将新的 mv 写回 mp 中,pc += 1
  • 如果 program[pc]-, 先从 mp 中读出值 mv,然后执行mv -= 1,最后将新的 mv 写回 mp 中,pc += 1
  • 如果 program[pc][dst_pos, 从 mp 中读出值 mv,如果 mv == 0,则进行跳转 pc = dst_pos;否则 pc += 1
  • 如果 program[pc]]start_pos, 从 mp 中读出值 mv,如果 mv != 0,则进行跳转 pc = start_pos;否则 pc += 1
  • 如果 program[pc],,将输入符号写到 mppc += 1
  • 如果 program[pc].,先从 mp 中读出值 mv,然后将 mv 写到输出流,pc += 1

repo:https://github.com/felicityin/zkvm-brainfuck