Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Compile Time Brainfuck C++ Metaprogramming Evaluator
#include <utility>
using iochar = char;
using memval = unsigned char;
/* BF Memory Cell */
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>;
};
/* String of characters */
template <iochar... chars>
using char_string = std::integer_sequence<iochar, chars...>;
/* Append a character onto a sequence */
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>;
};
/* Get the head of a 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 };
};
/* Get the rest of a sequence */
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...>;
};
/* End of list marker */
struct Nil { };
/* Infinite List */
template <typename x, typename xs = Nil>
struct List {
using first = x;
using rest = typename std::conditional<std::is_same<xs, Nil>::value, List<Cell<>>, xs>::type;
};
/* Get head of list */
template <typename L>
using list_car = typename L::first;
/* Get rest of list */
template <typename L>
using list_cdr = typename L::rest;
/* Zippered list of values */
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>>;
};
/* State */
template <typename TMem, typename TIn, typename TOut>
struct State {
using mem = TMem;
using in = TIn;
using out = TOut;
};
template <typename state, typename mem>
using state_set_mem = State<mem, typename state::in, typename state::out>;
/* Semantics */
template <typename semantics, typename state>
using eval = typename semantics::template eval<state>;
/* Evaluate `A` then `B` */
template <typename A, typename B>
struct Then {
template <typename state>
using eval = eval<B, eval<A, state>>;
};
template <iochar...>
struct Semantics;
template <>
struct Semantics<> {
template <typename state>
using eval = state;
};
template <iochar other, iochar... rest>
struct Semantics<other, rest...> {
template <typename state>
using eval = eval<Semantics<rest...>, state>;
};
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>>;
};
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<
typename state::mem,
typename state::in,
typename seq_append<typename state::out, state::mem::get::value>::type>>;
};
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>>;
};
/* Semantics for a loop */
template <bool end, size_t depth, typename loopBody, iochar... prog>
struct LoopDelimiter;
template <size_t depth, iochar... b, iochar... xs>
struct LoopDelimiter<true, depth, char_string<b...>, xs...> {
using body = Semantics<b...>;
using after = Semantics<xs...>;
};
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 == ']'),
(x == '[' ? depth + 1 : (x == ']' ? depth - 1 : depth)),
char_string<b..., x>,
xs...>;
using body = typename inner::body;
using after = typename inner::after;
};
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>;
};
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>;
};
/* Brainfuck memory */
using Memory = Zipper<List<Cell<>>, Cell<>, List<Cell<>>>;
/* Initial program state */
template <iochar... input>
using initial_state = State<Memory, char_string<input...>, char_string<>>;
/* Evaluate a brainfuck program at compile time */
template <typename prog, iochar... input>
using evaluate = typename prog::template eval<initial_state<input...>>::out;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment