3.2. Writing A Brainfuck Interpreter¶
3.2.1. The Virtual Machine¶
The Complete VM-Implementation weights ~100 lines of readable C++.
The VM consists of an Instruction -type and an Operator, which executes the Instructions. Brainfuck-Instructions are simple, they only need an Opcode (representing ,, ., +, -, <, >, [, ]) and an optional data register for jump-instructions.
First lets define our VM-Opcodes with an enum:
-
enum
brainfuck::
Opcode
¶ Opcodes for the Virtual-Brainfuck-Machine
Values:
-
in
¶ Get character from input and write it to current cell.
-
out
¶ Write current cell as character to output.
-
inc
¶ Increment the current cell.
-
dec
¶ Decrement the current cell.
-
next
¶ Move cell-pointer right.
-
prev
¶ Move cell-pointer left.
-
jmp
¶ Jump unconditionally.
-
jz
¶ Jump, if current cell is zero.
-
Now we need to represent the state of the VM. The neccesary values are members of brainfuck::VM: Tape and Program pointers have templated types and are expected to behave as iterators on a container (e.g. std::array). It contains a struct which defines Instructions. When the Operator (defined later) wants to execute an instruction, the method fetch is called, which updates the VM-State (in this case load the register) and returns the Opcode to be executed. Note that Data is the type for the VM-State. The last thing to do is to get the Instructions. This is done by CodeAccessor.
- template <typename TapeIterator, typename ProgramIterator>
-
class
brainfuck::
VM
¶ Stores the state of the virtual-machine and provides all operations.
Public Functions
-
brainfuck::VM::GIECS_CORE_OPERATOR(Operator, ((Opcode::in, TAPE_FN(std::cin >> * tape )))((Opcode::out, TAPE_FN(std::cout<< (char)* tape )))((Opcode::inc, TAPE_FN(++(* tape ))))((Opcode::dec, TAPE_FN(--(* tape ))))((Opcode::next, TAPE_FN(++ tape )))((Opcode::prev, TAPE_FN(-- tape )))((Opcode::jmp, DATA_FN(std::advance(d.pc, d.jmp_off))))((Opcode::jz, TAPE_FN(if(* tape ==0) std::advance(d.pc, d.jmp_off)))))
Public Members
-
TapeIterator
tape
¶ Pointer to current memory-cell.
-
ProgramIterator
pc
¶ Program counter.
-
std::iterator_traits<ProgramIterator>::difference_type
jmp_off
¶ Register (used by jmp and jz)
-
class
CodeAccessor
¶ Decodes the program-stream to instructions and buffers them. Emulates a queue.
Inherits from boost::circular_buffer< Instruction >
-
struct
Instruction
¶ Instruction to be executed, gets decoded by CodeAccessor from program-stream
Public Types
-
template<>
usingData
= VM<TapeIterator, ProgramIterator>¶
Public Functions
-
template<>
-
Opcode fetch(Data& data)
{
data.jmp_off = this->jmp_off;
return this->op;
}
Now we need to implement the opcodes using an Operator. This generates a class which can be used with giecs::eval.
#define DATA_FN(def) ([](typename Instruction::Data& d){ def ; })
#define TAPE_FN(def) DATA_FN( auto& tape = d.tape; def )
GIECS_CORE_OPERATOR(Operator,
((Opcode::in, TAPE_FN(std::cin >> *tape)))
((Opcode::out, TAPE_FN(std::cout << (char)*tape)))
((Opcode::inc, TAPE_FN(++(*tape))))
((Opcode::dec, TAPE_FN(--(*tape))))
((Opcode::next, TAPE_FN(++tape)))
((Opcode::prev, TAPE_FN(--tape)))
((Opcode::jmp, DATA_FN(_jmp(d))))
((Opcode::jz, TAPE_FN(if(*tape == 0) _jmp(d))))
);
3.2.2. Compiling Syntax for the VM¶
See syntax.hpp