Writing a BrainFuck interpreter in Golang

Dec 23, 2019 - Hariharan

Introduction

Brainfuck is a turing-complete, esoteric programming language created by Urban Muller in 1993. It consists of only 8 language commands

Character	Meaning
`>`	increment the data pointer (to point to the next cell to the right).
`<`	decrement the data pointer (to point to the next cell to the left).
`+`	increment (increase by one) the byte at the data pointer.
`-`	decrement (decrease by one) the byte at the data pointer.
`.`	output the byte at the data pointer.
`,`	accept one byte of input, storing its value in the byte at the data pointer.
`[`	if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching `]` command.
`]`	if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching `[` command.

Brainfuck was designed to have the smallest possible compiler. Clearly, it was not designed to create the next deep learning framework or to write world class game engines but that has not stopped people from writing amazing programs in brainfuck.

Hello World in BF

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

Fibonacci in BF

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

Text Adventure in Brainfuck

Motivation

Okay, enough plagiarizing Wikipedia. I had heard about brainfuck long back but never bothered looking into it. I was bored over the Christmas vacation and was looking for cool ideas to work on. That is when I came across a post on Reddit about someone trying to implement a brainfuck interpreter. I soon went over to the Wikipedia entry and to my surprise, there was more than enough info to implement the interpreter. So that’s what I did.

I had initially considered writing the interpreter in C, just to potentially have the option of porting it to NodeMCU and maybe with the SD card support, load and run brainfuck programs on-the-go on the NodeMCU. But that would be something for later and so I decided to use Golang to write a simple prototype for testing.

The entire code was written in an hour, so it goes without saying, DO NOT USE THIS IN PRODUCTION. But if you are using brainfuck in production, you already know that.

Architecture and Code

First, I created a CPU interface so that in the future I could also write a compiler that would not affect the calls to the machine.

type CPU interface {
	load(string)
	execute()
	input()
	output()
}

type cpu struct {
	ProgMem []string
	DataMem []int
	pc      int
	dc      int
}

If you have written a VM or an emulator before, you would notice a similar pattern here. The loop and switch-case combo. The interpreter is basically a large switch-case block inside a loop. pc is the program counter, and dc is the data pointer. The ProgMem holds the program with a single character in each slot. DataMem is the memory that is manipulated by brainfuck programs. Only the allowed characters are considered and other characters are simply neglected. This takes care of comments, newlines or spaces in the source code.

func (c *cpu) execute() {
	for c.pc < len(c.ProgMem) {
		opcode := c.ProgMem[c.pc]
		switch opcode {
		case "+":
			c.DataMem[c.dc] += 1
			c.pc++
		case "-":
			c.DataMem[c.dc] -= 1
			c.pc++
		case ">":
			c.dc++
			c.pc++
		case "<":
			c.dc--
			c.pc++
		case ".":
			c.output()
			c.pc++
		case ",":
			c.input()
			c.pc++
		case "[":
			if c.DataMem[c.dc] == 0 {
				c.pc = findMatching(c.ProgMem, c.pc, true) + 1

			} else {
				c.pc++
			}
		case "]":
			if c.DataMem[c.dc] != 0 {
				c.pc = findMatching(c.ProgMem, c.pc, false) + 1
			} else {
				c.pc++
			}
		default:
			c.pc++
		}
	}
	fmt.Println()
}

findMatching is just a utility function to find the matching bracket.

func findMatching(code []string, pos int, dir bool) int {
	count := 1
	if dir {
		for i := pos + 1; i < len(code); i++ {
			if code[i] == "]" {
				count--
				if count == 0 {
					return i
				}
			} else if code[i] == "[" {
				count++
			}
		}
	} else {
		for i := pos - 1; i >= 0; i-- {
			if code[i] == "[" {
				count--
				if count == 0 {
					return i
				}
			} else if code[i] == "]" {
				count++
			}
		}
	}
	return -1
}

Input and output are also just utility functions to do just that. That’s it. I just added support for loading programs and validating the square brackets before execution.

Brainfuck might be one of those few languages where writing the interpreter is much easier than actually using it.

The entire code can be found at goBrainFuck.