This blog is the learning note for Brainfuck VM
The Instructions
Brainfuck is tiny. It consists of eight different instructions. These instructions can be used to manipulate the state of the Brainfuck machine:
>– Increment the memory pointer by 1.<– Decrement the memory pointer by 1.+– Increment the value in the current cell (the cell the memory pointer is pointing to).-– Decrement the value in the current cell..– Take the integer in the current cell, treat it as an ASCII char and print it on the output stream.,– Read a character from the input stream, convert it to an integer and save it to the current cell.[– This always needs to come with a matching]. If the current cell contains a zero, set the instruction pointer to the index of the instruction after the matching].]– If the current cell does not contain a zero, set the instruction pointer to the index of the instruction after the matching[.
That’s all of it, the complete Brainfuck language.
Even though these instructions look archaic, they’re just identifiers. Replace + with PLUS, - with SUB, . with PRINT and [ with LOOP and suddenly Brainfuck starts to look more like Brain-oh-wow-wait-a-second-I-can-actually-read-that.
Now that we know what the machine should look like and what it has to do, let’s get started with building it.
Example Program
++>,<[>+.<-]
Execution table
clk: clock
ip: instruction pointer
ci: current instruction
ni: next instruction
mp: memory pointer
mv: memory value
mvi: memory value inverse
++>,<[>+.<-]
| clk | ip | ci | ni | mp | mv | mvi |
| 0 | 0 | + | + | 0 | 0 | 0 |
| 1 | 1 | + | > | 0 | 1 | 1 |
| 2 | 2 | > | , | 0 | 2 | \(2^{-1}\) |
| 3 | 3 | , | < | 1 | 0 | 0 |
| 4 | 4 | < | [ | 1 | 97 | \(97^{-1}\) |
| 5 | 5 | [ | 13 | 0 | 2 | \(2^{-1}\) |
| 6 | 7 | > | + | 0 | 2 | \(2^{-1}\) |
| 7 | 8 | + | . | 1 | 97 | \(97^{-1}\) |
| 8 | 9 | . | < | 1 | 98 | \(98^{-1}\) |
| 9 | 10 | < | – | 1 | 98 | \(98^{-1}\) |
| 10 | 11 | – | ] | 0 | 2 | \(2^{-1}\) |
| 11 | 12 | ] | 7 | 0 | 1 | 1 |
| 12 | 7 | > | + | 0 | 1 | 1 |
| 13 | 8 | + | . | 1 | 98 | \(98^{-1}\) |
| 14 | 9 | . | < | 1 | 99 | \(99^{-1}\) |
| 15 | 10 | |||||
| 16 |
Tables
Processor table
sorted by cycle register column, contains the values of all the registers.
Goal: each instruction transforms the state as defined in the VM.
memory table
sorted by memory pointer. Memory table consists of three rows: clk, mp, and mv. That is: cycle count, memory pointer, and memory value.
Goal:memory values are consistent.for example that all memory values are initialized to zero and that when a memory value is accessed again, it has not changed since the last cycle in which this memory value was accessed.
Instruction table
sorted by instruction pointer first and cycle second. The instruction pointer ip, the current instruction ci, and the next instruction ni. The rows are formed by first concatenating the entire program with the execution trace and then sorting the resulting rows by instruction pointer. So the instruction table is always longer than the processor table by the size of the program.
Goal: expected program is read into the instruction registers
input and output table
They are formed from the subset of rows in the execution trace which read from input or write to output, respectively. Concretely, for every executed ,, there is one row in the Input Table. Likewise, for every ., there is one row in the Output Table.
Goal: The input table proves that the correct values are read into memory. The output table proves that the program writes the correct values to output.
The constraints
Boundary constraints
Consistency Constraints
Transition Constraints
Processor table
\(\prod\limits_{op’ \neq op}(ci-a_{op’})\) is the deselector for operation \(op\), evaluates to zero at any opcode that is not \(op\). [when \(ci\) is not \(a_{op}\), it is one of other \(op’\) and it will evaluate \(ci-a_{op;}\) to be zero]
\(instr_{op}^i (\overrightarrow{r_n},\overrightarrow{r_{n+1}})\).
This polynomial is a part of a constraint modeling the transition for only a single instruction, namely \(op\). For every instruction, there are 3 transition polynomials, as \(1 \leq i \leq 3\), they define the constraints for \(ip, mp, mv\) respectively.
The polynomials for each of the 8 instructions are listed below
Memory table
Instruction Table
Terminal constraints
Extension Columns
Goal: proving that each table is either a permutation or a subset of another table, namely, link the tables.
Running Product for Permutation
The randomness \(\beta, d, e, f\) combines the values in one row together, if the permutation of two tables holds. the two table should have the same terminal value.
Running evaluation for sub-list
