Compile Time Brainfuck C++ Metaprogramming Evaluator

gistfile1.cpp

#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;