Brainfuck VM instance

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

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

clkipcinimpmvmvi
00++000
11+>011
22>,02\(2^{-1}\)
33,<100
44<[197\(97^{-1}\)
55[1302\(2^{-1}\)
67>+02\(2^{-1}\)
78+.197\(97^{-1}\)
89.<198\(98^{-1}\)
910<198\(98^{-1}\)
1011]02\(2^{-1}\)
1112]7011
127>+011
138+.198\(98^{-1}\)
149.<199\(99^{-1}\)
1510
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: clkmp, 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

Leave a Reply

Your email address will not be published. Required fields are marked *