While toy lang, implemented (stepping version) using c++ template metaprogramming

stepping_while.cpp

/// Our reduce 'function' (eval-one-step)
/// reduce :: AST -> State -> { Result :: AST, State :: State }
template <typename AST, typename State>
struct reduce;

/// class AST where
///     print :: IO ()
///     reduce :: AST -> State -> { Result :: AST, State :: State }
///
/// (internally there are AExpr, BExpr, and Cmd types, but we don't bother enforcing these
/// since everything w/ c++ templates is just duck typed anyways...)
///
/// class State where
///     set_var :: Variable -> Value -> State -> State
///     get_var :: State -> Variable -> AST (Value)
///     print :: IO ()
///
/// (state is a lazy Variable -> Value map implemented as a linked list.
/// it supports construction via set_var (and EmptyState), and values can be
/// extracted from it using get_var)

/// State + variable impl...

/// EmptyState :: State = undefined
/// Note: as such, using undefined variables should result in c++ compile errors, which is pretty cool.
/// (Very cryptic, likely unhelpful compiler errors, but... you can't have everything :P)
struct EmptyState {};

template <typename State>
struct StateHelper;

/// set_var :: Variable -> Value -> State -> State { var :: Var, val :: Value, Next :: State }
template <char variable, int value, typename NextState>
struct set_var {
    enum { var = variable, val = value };
    typedef NextState Next;
    static void print () { printf("[ %c = %d", var, val); StateHelper<Next>::print_elems(); printf(" ]"); } 
}

template <> 
struct StateHelper<EmptyState> { static void print_elems () {} }

template <typename State>
struct StateHelper<State> { 
    static void print_elems () { 
        printf(", %c = %d", State::var, State::val);
        StateHelper<State::Next>::print_elems();
    }
}

/// get_var :: State -> Variable -> AST { result :: Value }
template <typename State, char variable>
struct get_var;

template <char variable, int value>
struct get_var<set_var<variable, value>> {
    enum { result = value };
}

/// Var :: Variable -> AST { var :: Variable, print :: IO () } 
template <char variable>
struct Var {
    enum { var = variable };
    static void print () { printf("%c", var); }
}

/// Assign :: Variable -> AST -> AST { var :: Variable, expr :: AST, print :: IO () }
template <char variable, typename expr>
struct Assign {
    enum { var = variable };
    typedef expr Expr;
    static void print () { printf("%c := ", var); Expr::print(); }
}

/// reduce (Var(x), state) -> (get_var x state, state)
template <char variable, typename S>
struct reduce<Var<variable>, S> {
    typedef Value<get_var<S>::val> Result;
    typedef S State;
};
/// reduce (Assign x (Value a), state) -> (Skip, set_var(x, a))
template <char variable, int val, typename S>
struct reduce<Assign<variable, Value<val>>, S> {
    typedef Skip Result;
    typedef set_var<variable, val, S> State;
}
/// reduce (Assign x expr, state) -> (Assign x result', state')
///     where result', state' = reduce expr state
template <char variable, typename a, typename S>
struct reduce<Assign<variable, a>, S> {
    typedef Assign<variable, reduce<a, S>>::Result Result;
    typedef S State;
}


/// Everything else...

/// Value :: Num -> AST { result :: Num, print :: IO () }
struct Value <int v> { 
    enum { result = v };
    static void print () { std::cout << result; }
};
/// Add :: AST -> AST -> AST { Left :: AST, Right :: AST, print :: IO () } 
template <typename a, typename b>
struct Add {
    typedef a Left;
    typedef b Right;
    static void print () { std::cout << "("; Left::print(); std::cout << " + " << Right::print() << ")"; }
};

/// BConst :: Bool -> AST { result :: bool, print :: IO () } 
struct BConst <bool v> { 
    enum { result = v };
    static void print () { std::cout << (result ? "true" : "false"); }
};

/// Skip :: AST { print :: IO () }
struct Skip {
    static void print () { std::cout << "skip"; }
}

/// Add :: AST -> AST -> AST { Left :: AST, Right, :: AST, print :: IO () }
template <typename a, typename b>
struct Add {
    typedef a Left;
    typedef b Right;
    static void print () { std::cout << "("; Left::print(); std::cout << " + " << Right::print() << ")"; }
};

/// Seq :: AST -> AST -> AST { Left :: AST, Right :: AST, print :: IO () }
template <typename a, typename b>
struct Seq {
    typedef a Left;
    typedef b Right;
    static void print () { Left::print(); std::cout << "; "; Right::print(); }
};

template <typename cond, typename a, typename b>
struct If {
    typedef cond Cond;
    typedef a Left;
    typedef b Right;
    static void print () { std::cout << "if "; Cond::print(); std::cout << " { "; Left::print(); std::cout << " } else { ", Right::print(); std::cout << " }"; }
}

template <typename cond, typename c0, typename body>
struct While {
    typedef cond Cond;
    typedef c0 C0;
    typedef body Body;
    static void print () { std::cout << "while "; Cond::print(); std::cout << " { "; Body::print(); std::cout << " }"; }
}

// Skip => Skip
template <typename S>
struct reduce<Skip, S> {
    typedef Skip Result;
    typedef S State;
    using Result::print;
}

// BCond(true | false) => BCond(...)
template <bool v, typename S>
struct reduce<BCond<v>, S> {
    typedef typename BCond<v> Result;
    typedef S State;
    using Result::print;
}

// Value(v) => Value(v)
template <int v, typename S>
struct reduce<Value<v>, S> {
    typedef typename Value<a> Result;
    typedef S State;
    using Result::print;
}

// Add(Value(v1), Value(v2)) => Value(v1 + v2)
template <int v1, int v2, typename S>
struct reduce<Add<Value<v1>, Value<v2>, S> {
    typedef Value<v1 + v2> Result;
    typedef S State;
    using Result::print;
}

// Add(Value(v1), b) => Add(Value(v1), reduce(b))
template <int v1, typename b, typename S>
struct reduce<Add<Value<v1>, b>, S> {
    typedef Add<Value<v1>, reduce<b, S>::Result> Result;
    typedef S State;
    using Result::print;
}
// Add(a, b) => Add(reduce(a), b)
template <typename a, typename b, typename S>
struct reduce<Add<a, b>, S> {
    typedef Add<reduce<a, S>::Result, b> Result;
    typedef S State;
    using Result::print;
}

// If(true, a, b) => a
template <typename a, typename b, typename S>
struct reduce<If<BConst<true>, a, b>, S> {
    typedef a Result;
    typedef S State;
    using Result::print;
}
// If(false, a, b) => b
template <typename a, typename b, typename S>
struct reduce<If<BConst<false>, a, b>, S> {
    typedef b Result;
    typedef S State;
    using Result::print;
}
// If(cond, a, b) => If(reduce(cond), a, b)
template <typename cond, typename a, typename b, typename S>
struct reduce<If<cond, a, b>, S> {
    typedef typename If<reduce<cond, S>::Result, a, b> Result;
    typedef S State;
    using Result::print;
}

// Seq(a, b) => Seq(reduce(a), b)
template <typename a, typename b, typename S>
struct reduce<Seq<a, b>, S> {
    typedef typename Seq<reduce<a, S>::Result, b> Result;
    typedef typename reduce<a, S>::State State;
    using Result::print;
}
// Seq(skip, b) => reduce(b)
template <typename a, typename b, typename S>
struct reduce<Seq<Skip, b>, S> {
    typedef typename reduce<b, S>::Result Result;
    typedef typename reduce<b, S>::State State;
    using Result::print;
}

// While(false, _) => skip
template <typename _, typename __, typename S>
struct reduce<While<BCond<false>, _, __>, S> {
    typedef Skip Result;
    typedef S State;
    using Result::print;
}
// While(true, body) =>
template <typename c0, typename body typename S>
struct reduce<While<BCond<false>, c0, body>, S> {
    typedef typename While<c0, c0, body> ResetLoop;
    typedef typename Seq<body, ResetLoop> Next;
    typedef typename reduce<Next, S>::Result Result;
    typedef typename reduce<Next, S>::State State;
    using Result::print;
}
template <typename AST, typename State, size_t n, size_t i>
struct eval_and_print_n;

template <typename AST, typename State, size_t i>
void print_step () {
    printf("step %lu: ", i);
    AST::print();
    State::print();
    printf("\n");
}
template <typename AST, typename State, size_t i = 0>
struct eval_and_print_n<AST, State, 0, i> {
    static void run () { print_step<AST, State, i>(); }
}
template <typename AST, typename State, size_t n, size_t i = 0>
struct eval_and_print_n<AST, State, n, i> {
    static void run () {
        print_step<AST, State, i>();
        typedef typename reduce<AST, State> Next;
        eval_and_print_n<Next::Result, Next::State, n - 1, i + 1>::run();
    }
}

template <typename AST, typename State, size_t i = 0>
struct eval_and_print_until_done;

template <typename State, size_t i = 0>
struct eval_and_print_until_done<Skip, State, i> {
    static void run () { print_step<Skip, State, i>(); }
}
template <typename AST, typename State, size_t i = 0>
struct eval_and_print_until_done<AST, State, i> {
    static void run () { 
        print_step<AST, State, i>();
        typedef typename reduce<AST, State> Next;
        eval_and_print_until_done<Next::Result, Next::State, i + 1>::run();
    }
};

// TBD: implement Less, Equal, Not, Or, And, Sub, Mul


// we won't be using while, if, not, etc., anyways, so might as well just override them...
#define while(cond, body) While<cond, cond, body>
#define if(cond, body) If<cond, body>
#define not(expr) Not<expr>
#define or(a, b) Or<a, b>
#define and(a, b) And<a, b>
#define less(a, b) Less<a, b>
#define equal(a, b) Equal<a, b>
#define assign(a, b) Assign<a, b>
#define seq(a, b) Seq<a, b>
#define skip Skip
#define add(a, b) Add<a, b>
#define sub(a, b) Sub<a, b>
#define mul(a, b) Mul<a, b>
#define var(a) Var<a>
#define val(a) Value<a>
#define btrue BCond<true>
#define bfalse BCond<false>

#define empty EmptyState
#define set(var, val, next) set_state<var, val, next>
#define eval_print(expr, state) eval_and_print_until_done<expr, state>::run()

// Run Euclid's GCD algorithm, using while:
template <int A, int B>
void run_gcd () {
    #define a var('a')
    #define b var('b')

    // https://en.wikipedia.org/wiki/Euclidean_algorithm
    using gcd = 
    while(not(equal(a, b)),
        if(less(b, a),
            assign(a, sub(a, b)),
            assign(b, sub(b, a))));

    // run with A, B
    eval_print(gcd, set('a', A, set('b', B, empty)));
}

int main () {
    run_gcd<55, 10>();
    run_gcd<100, 2>();
    run_gcd<100, 50>();
}

update: full implementation available at https://github.com/SeijiEmery/while-rs/tree/master/cpp