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 >

Public Functions

template<> CodeAccessor(ProgramIterator &begin_, ProgramIterator const &end_)¶

template<> Instruction &front(void)¶

Return: the next instruction

template<> bool empty(void) const¶

Return: if end-of-program is reached

struct Instruction¶

Instruction to be executed, gets decoded by CodeAccessor from program-stream

Public Types

template<> using Opcode = brainfuck::Opcode ¶

template<> using Data = VM<TapeIterator, ProgramIterator>¶

Public Functions

template<> Opcode fetch(Data &data)¶: Get the opcode for this instruction and update the vm-state (load register).

Public Members

template<> Opcode op¶

template<> std::iterator_traits<ProgramIterator>::difference_type jmp_off¶

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