# Brainfuck Compile Time Evaluator

Every 2nd grader knows that the C++ template system is Turing complete. So what? Compile time Brainfuck evaluator that’s what!

It turns out that I’m not the first person who learned me some metaprogramming and thought it would be a good laugh to implement Brainfuck with C++ templates. But in going though this admitidly pointless exercise, what struck me is how similar a Brainfuck C++ template evaluator is to one implemented in a functional-style.

In just around 200 LOC, you can create a fairly reasonable and clear Brainfuck implementation using C++ templates. And, while implementing Brainfuck is certainly not very practical, metaprogramming in the same vein actually does have some interesting applications.

# Overview

This post covers expressing a Brainfuck evaluator from the ground up. The complete source code can be found here.

I’ll start by defining a few helper types and operations that will make the rest of the implementation more clear. Comprehensibility and generality are favored over brevity and cleverness.

Let’s get started.

# I/O Buffers

Before expressing language semantics, we need to encode a compile time character buffer. These buffers will be used as both the actual Brainfuck I/O buffers, and also to hold program source code.

Our buffer type will encode specific characters sequence as unique types. The C++14 addition `std::integer_sequence`

does exactly this, encoding a variadic parameter list of values as a type.

```
using iochar = char;
template <iochar... chars>
using char_string = std::integer_sequence<iochar, chars...>;
// Simple strings encoded as types
using empty = char_string<>;
using one_char = char_string<'x'>;
using abc = char_string<'a', 'b', 'c'>;
```

`std::integer_sequence`

is pretty bare-bones list. It’s useful for unpacks, but inconvenient for our purposes. So let’s write some lisp style style `car`

and `cdr`

operations for `std::integer_sequence`

.

```
template <typename>
struct seq_car;
template <typename T, T x, T... xs>
struct seq_car<std::integer_sequence<T, x, xs...>> {
enum { value = x };
};
```

```
seq_car<one_char>::value; // 'x'
seq_car<abc>::value; // 'a'
seq_car<empty>::value; // Compile time error. `seq_car` is not defined for empty sequences.
```

```
template <typename>
struct seq_cdr;
template <typename T, T x, T... xs>
struct seq_cdr<std::integer_sequence<T, x, xs...>> {
using type = std::integer_sequence<T, xs...>;
};
```

```
seq_car<abc>::value; // 'a'
seq_car<typename seq_cdr<abc>::type>::value; // 'b'
seq_car<typename seq_cdr<typename seq_cdr<abc>::type>::type>::value; // 'c'
```

`std::integer_sequence`

is fundamentally an immuable list of values, so we also need a way to transform a `std::integer_sequence`

. Lisp uses the `cons`

operations for this, which prepends an element onto the head of a list.

```
/// Note the reverse argument order vs. `cons` in lisp.
template <typename seq, typename seq::value_type>
struct seq_cons;
template <typename T, T x, T... xs>
struct seq_cons<std::integer_sequence<T, xs...>, x> {
using type = std::integer_sequence<T, x, xs...>;
};
```

```
using xy = typename seq_cons<one_char, 'y'>::type;
seq_car<xy>::value; // 'y'
seq_car<typename seq_cdr<xy>::type>::value; // 'x'
```

Our evaluator does not actually need `seq_cons`

, but we do need its counterpart, `seq_append`

, to append a value onto a list.

```
template <typename seq, typename seq::value_type>
struct seq_append;
template <typename T, T x, T... xs>
struct seq_append<std::integer_sequence<T, xs...>, x> {
using type = std::integer_sequence<T, xs..., x>;
};
```

```
using xy = typename seq_append<one_char, 'y'>::type;
seq_append<xy>::value; // 'x'
seq_append<typename seq_cdr<xy>::type>::value; // 'y'
```

# Memory Cells

Brainfuck models program memory as an infinite list of cells. Each cell stores a fixed bit number and is initialized to 0. There is no standard cell size, but one byte is the most common.

The `Cell`

type encodes a Brainfuck memory cell storing an eight bit number as a type. A few helpers on the `Cell`

type allow transforming’s cells.

```
using memval = unsigned char;
template <memval val = 0>
struct Cell {
enum { value = val };
using add = Cell<static_cast<memval>(val + 1)>;
using sub = Cell<static_cast<memval>(val - 1)>;
template <memval new_val>
using put = Cell<new_val>;
};
```

A classic Brainfuck implementation maintains a list of around 30,000 cells. But rather than artificially limit the size of our program memory, we can encode an infinite list fairly easily.

`List`

is a lisp style list of types. It encodes a head element and the rest of the list. The `cdr`

operation is how we make the list infinite. Unlike normal `cdr`

, when we encounter the end of the list, as marked by the `Nil`

type, we lazily generate another list element.

```
struct Nil { };
template <typename x, typename xs = Nil>
struct List {
using first = x;
using rest = typename std::conditional<std::is_same<xs, Nil>::value,
List<Cell<>>, // Generate next element
xs>::type;
};
```

Two helpers simplify list access.

```
template <typename L>
using list_car = typename L::first;
template <typename L>
using list_cdr = typename L::rest;
```

# Memory

We also need a way to encode a position in a `List`

of cells. Since `List`

is an immutable list of values, a zipper turns out to be a good abstraction for this.

`Zipper`

encodes a context in a `List`

. `focus`

is the element at the current position in the list. `left`

is a list of elements to the left of the focus (stored in reverse-order). And `right`

is a list of elements to the right of the focus (stored in-order).

```
template <typename left, typename focus, typename right>
struct Zipper {
using get = focus;
template <memval T>
using put = Zipper<left, typename focus::template put<T>, right>;
using add = Zipper<left, typename focus::add, right>;
using sub = Zipper<left, typename focus::sub, right>;
using go_left = Zipper<list_cdr<left>, list_car<left>, List<focus, right>>;
using go_right = Zipper<List<focus, left>, list_car<right>, list_cdr<right>>;
};
```

`get`

, `put`

, `add`

, and `sub`

all manipulate the focus. `go_left`

shifts the context left by one cell, while `go_right`

shifts the context right by one cell.

This also has the advantage of allowing us to encode bi-directionally infinite memory. Again, not a strict requirement of Brainfuck, but certainly an interesting feature.

`Memory`

encodes the initial state of program memory.

```
using Memory = Zipper<List<Cell<>>, Cell<>, List<Cell<>>>;
```

# State

The complete state of our Brainfuck interpreter is captured in a 3-tuple of memory, input buffer, and output buffer.

```
template <typename TMem, typename TIn, typename TOut>
struct State {
using mem = TMem;
using in = TIn;
using out = TOut;
};
```

Helpers are used to transform states more easily.

```
template <typename state, typename mem>
using state_set_mem = State<mem, typename state::in, typename state::out>;
```

For some given program input, the initial state is:

```
template <iochar... input>
using initial_state = State<Memory, char_string<input...>, char_string<>>;
```

# Basic Semantics

With our data structures and operations defined, we can now express the semantics of Brainfuck.

The `Semantics`

type maps program source code to a `eval`

templated type that encodes the semantics of the input program. The `eval`

template type takes a `state`

and outputs a new `state`

.

`Semantics<>`

is the specialization for empty program input, with `eval`

acting as the identity function.

```
template <iochar... prog>
struct Semantics;
template <> // no more input
struct Semantics<> {
template <typename state>
using eval = state;
};
```

The helper `eval`

evaluates a semantic type with a given state.

```
template <typename semantics, typename state>
using eval = typename semantics::template eval<state>;
```

The semantics of the `+`

, `-`

, `<`

, and `>`

operations are straightforward. Each maps a state to a new state by modifying the memory using our previously defined state operations.

`+`

- Increments value of current cell.`-`

- Decrements value of current cell.`>`

- Move memory pointer right one cell.`<`

- Move memory pointer left one cell.

Evaluation is continued on the rest input with the new state.

```
template <iochar... rest>
struct Semantics<'+', rest...> {
template <typename state>
using eval = eval<
Semantics<rest...>,
state_set_mem<state, typename state::mem::add>>;
};
template <iochar... rest>
struct Semantics<'-', rest...> {
template <typename state>
using eval = eval<
Semantics<rest...>,
state_set_mem<state, typename state::mem::sub>>;
};
```

```
template <iochar... rest>
struct Semantics<'>', rest...> {
template <typename state>
using eval = eval<
Semantics<rest...>,
state_set_mem<state, typename state::mem::go_right>>;
};
template <iochar... rest>
struct Semantics<'<', rest...> {
template <typename state>
using eval = eval<
Semantics<rest...>,
state_set_mem<state, typename state::mem::go_left>>;
};
```

# I/O Semantics

Input and output is also easily expressed using the previously defined operations.

The output operation `.`

reads the value held in memory at the current location, and appends this value to the output buffer.

```
template <iochar... rest>
struct Semantics<'.', rest...> {
template <typename state>
using eval = eval<
Semantics<rest...>,
State<
typename state::mem,
typename state::in,
typename seq_append<typename state::out, state::mem::get::value>::type>>;
};
```

The input operation `,`

reads a value from the input buffer, and stores this value at the current location in memory. The input buffer is also advanced by one. It is a compile time error if the input buffer is empty.

```
template <iochar... rest>
struct Semantics<',', rest...> {
template <typename state>
using eval = eval<
Semantics<rest...>,
State<
typename state::mem::template put<seq_car<typename state::in>::value>,
typename seq_cdr<typename state::in>::type,
typename state::out>>;
};
```

# Loop Semantics

Looping is the only somewhat complicated part of the evaluator, as it involves matching symbols in the program source.

When the `[`

symbol is encountered, we check if the value stored at the current memory cell is zero. If it is, then we skip to the next instruction after the matching `]`

in the source code. Otherwise, we enter the body of the loop, and when the matching `]`

is encountered, jump back to execute the original `[`

operation again.

First off, let’s determine the extent of a loop in source code. `LoopDelimiter`

breaks program source code into a `body`

section for the loop body between `[`

and `]`

and an `after`

section for everything after the closing `]`

.

```
template <bool end, size_t depth, typename loopBody, iochar... prog>
struct LoopDelimiter;
```

The `end`

flag tracks if we found the matching `]`

yet. `depth`

stores the number of subloops we have entered.

```
/* Base case, we found end */
template <size_t depth, iochar... body, iochar... prog>
struct LoopDelimiter<true, depth, char_string<body...>, prog...> {
using body = Semantics<body...>;
using after = Semantics<prog...>;
};
```

The real logic for `LoopDelimiter`

is this rather ugly partial specialization. It examines the next character in the program and determines if the end of the loop has been found. `[`

means that we found an inner loop and must continue matching at the next depth. `]`

means we found the end of a loop. If the depth was also 1, then it was the end of the outermost loop.

```
template <size_t depth, iochar... b, iochar x, iochar... xs>
struct LoopDelimiter<false, depth, char_string<b...>, x, xs...> {
using inner = LoopDelimiter<
(depth == 1 && x == ']'), // Found end?
(x == '[' ? (depth + 1) : (x == ']' ? (depth - 1) : depth)),
char_string<b..., x>,
xs...>;
using body = typename inner::body;
using after = typename inner::after;
};
```

When first entering a loop, we branch on whether or not the value of the current memory cell is zero. `LoopBranch`

handles this logic, while also automatically reinvoking the loop (since `]`

is treated as the unconditional jump) after evaluating the consequent.

```
/* Evaluate `A` then `B` */
template <typename A, typename B>
struct Then {
template <typename state>
using eval = eval<B, eval<A, state>>;
};
template <typename consequent, typename alternate>
struct LoopBranch {
template <typename state>
using eval = eval<
typename std::conditional<state::mem::get::value == 0,
alternate,
Then<
consequent,
LoopBranch<consequent, alternate>>>::type,
state>;
};
```

Using `LoopDelimiter`

and `LoopBranch`

, we can clearly express the semantics of a loop:

```
template <iochar... rest>
struct Semantics<'[', rest...> {
template <typename state, typename loop = LoopDelimiter<false, 1, char_string<>, rest...>>
using eval = eval<
LoopBranch<typename loop::body, typename loop::after>,
state>;
};
```

# Finishing Touches

Brainfuck treats any character besides `+-<>.,[]`

as a comment. One final partial specialization of `Semantics`

makes all other character noops.

```
template <iochar other, iochar... rest>
struct Semantics<other, rest...> {
template <typename state>
using eval = eval<Semantics<rest...>, state>;
};
```

`evaluate`

runs a program and extracts the result (the output buffer).

```
template <typename prog, iochar... input>
using evaluate = typename prog::template eval<initial_state<input...>>::out;
```

# Hello World!

Here is ‘Hello World!’ in Brainfuck.

```
using hello_world = Semantics<
'+', '+', '+', '+', '+', '+', '+', '+', '+', '+',
'[', '>', '+', '+', '+', '+', '+', '+', '+', '>',
'+', '+', '+', '+', '+', '+', '+', '+', '+', '+',
'>', '+', '+', '+', '>', '+', '<', '<', '<', '<',
'-', ']', '>', '+', '+', '.', '>', '+', '.', '+',
'+', '+', '+', '+', '+', '+', '.', '.', '+', '+',
'+', '.', '>', '+', '+', '.', '<', '<', '+', '+',
'+', '+', '+', '+', '+', '+', '+', '+', '+', '+',
'+', '+', '+', '.', '>', '.', '+', '+', '+', '.',
'-', '-', '-', '-', '-', '-', '.', '-', '-', '-',
'-', '-', '-', '-', '-', '.', '>', '+', '.', '>',
'.'>;
```

Passing this type into `evaluate`

produces a type encoding the output of this program.

```
evaluate<hello_world> x { }; // Perhaps the most useless variable ever
```

This type is not very useful on its own, but we can use a helper function `print_seq`

to print the type (the sequence of characters in the output buffer) to stdout.

```
template <typename T, T... xs>
void print_seq(std::integer_sequence<T, xs...>) {
bool Do[] = { (std::cout << xs, true)... };
(void) Do;
std::cout << std::endl << std::flush;
}
```

So that we can evaluate `hello_world`

at compile time and print the result.

```
int main(int, const char*[]) {
print_seq(evaluate<hello_world>{});
}
```

```
Hello World!
Program ended with exit code: 0
```