#include <stdio.h>

// Helpers

template<bool B, typename T1, typename T2>
struct Select {
    typedef T1 Value;
};

template<typename T1, typename T2>
struct Select<false, T1, T2> {
    typedef T2 Value;
};

// Environment

struct Null { };

template<char VAR, typename VAL, typename ENV>
struct Extend { };

// Values

// Number
template<int N>
struct Num { };

// Procedure
template<char PARAM, typename BODY, typename ENV>
struct Proc {
    template<typename ARG>
    struct Apply {
        typedef typename BODY::template Eval<Extend<PARAM, ARG, ENV> >::Value Value;
    };
};

// Expressions

// Literal
template<int N>
struct Lit {
    template<typename ENV>
    struct Eval {
        typedef Num<N> Value;
    };
};

// Variable reference
template<char VAR>
struct Var {
    template<typename ENV>
    struct Eval {
        typedef Null Value;
    };
   
    template<char AVAR, typename VAL, typename ENV>
    struct Eval<Extend<AVAR, VAL, ENV> > {
        typedef typename Select<VAR == AVAR, VAL, typename Eval<ENV>::Value>::Value Value;
    };
};

// Lambda abstraction
template<char PARAM, typename BODY>
struct Abs {
    template<typename ENV>
    struct Eval {
        typedef Proc<PARAM, BODY, ENV> Value;
    };
};

// Application
template<typename OP, typename ARG>
struct App {
    template<typename ENV>
    struct Eval {
        typedef typename OP::template Eval<ENV>::Value Op;
        typedef typename ARG::template Eval<ENV>::Value Arg;
        typedef typename Op::template Apply<Arg>::Value Value;
    };
};

// Printing

template<typename EXP>
struct Printer { };

template<int N>
struct Printer< Num<N> > {
    static void print() {
        printf("%d", N);
    }
};

template<char PARAM, typename BODY, typename ENV>
struct Printer<Proc<PARAM, BODY, ENV> > {
    static void print() {
        printf("<proc>");
    }
};

// Tests

template<typename EXP>
void evalprint() {
    Printer<typename EXP::template Eval<Null>::Value>::print();
    printf("\n");
}

int main() {
    evalprint<Lit<42> >(); // 42
    evalprint<Abs<'x', Lit<42> > >(); // <proc>
    evalprint<App<Abs<'x', Lit<42> >, Lit<666> > >(); // 42
    evalprint<App<Abs<'x', Var<'x'> >, Lit<666> > >(); // 666
    evalprint<App<Abs<'x', Abs<'y', Var<'x'> > >, Lit<42> > >(); // <proc>
    evalprint<App<App<Abs<'x', Abs<'y', Var<'x'> > >, Lit<42> >, Lit<666> > >(); // 42
    evalprint<App<App<Abs<'x', Abs<'y', Var<'y'> > >, Lit<42> >, Lit<666> > >(); // 666
    return 0;
}