Compile-time lambda calculus calculation http://ideone.com/us66y

lam.cpp

#include<iostream>
#include<typeinfo>
#include<cxxabi.h>
 
template<int N> struct V{};
template<int N,class T> struct args{};
template<int M,int N> struct Var{};
template<bool N,class T> struct either{};
struct nu{};
template<class R,class T> struct lambda;
 
template<class M,class N> struct A{
	typedef A<M,N> type;
	template<class T> A<A<M,N>,typename T::type> operator()(T){
		return A<A<M,N>,typename T::type>();
	}
};
template<int N> struct ph{
	typedef V<N> type;
	template<class T> A<V<N>,typename T::type> operator()(T){
		return A<V<N>,typename T::type>();
	}
};
 
template<int N,class T> struct addarg{};
template<int N> struct addarg<N,nu>{
	typedef args<N,nu> type;
};
template<int N,int C,class T> struct addarg<N,args<C,T> >{
	typedef args<C,typename addarg<N,T>::type> type;
};
 
template<int N,int C,class T> struct notfound{};
template<int N,int C,class T> struct notfound<N,C,args<C,T> >{
	static const int value=N;
};
template<int N,int C,int R,class T> struct notfound<N,C,args<R,T> >{
	static const int value=notfound<N,C,T>::value;
};
template<int N,int C> struct notfound<N,C,nu>{
	static const int value=-1;
};
 
template<int N,class T,class F> struct format_t{
	typedef T type;
};
template<int N,int C,class F> struct format_t<N,V<C>,F>{
	typedef Var<notfound<N,C,F>::value,C> type;
};
template<int N,int C,class F> struct format_t<N,Var<-1,C>,F>{
	typedef Var<notfound<0,C,F>::value,C> type;
};
template<int N,int T,int C,class F> struct format_t<N,Var<T,C>,F>{
	typedef Var<T+1,C> type;
};
template<int N,class L,class R,class F> struct format_t<N,A<L,R>,F>{
	typedef A<typename format_t<N,L,F>::type,typename format_t<N,R,F>::type> type;
};
template<int N,class T,class P,class F> struct format_t<N,lambda<T,P>,F>{
	typedef lambda<T,typename format_t<N+1,P,F>::type> type;
};
template<class T,class F> struct format{
	typedef typename format_t<0,T,F>::type type;
};
 
template<class T> struct lambda_t{
	template<int N> lambda_t<typename addarg<N,T>::type> operator [](ph<N>){
		return lambda_t<typename addarg<N,T>::type>();
	}
	template<class P> lambda<T,typename format<typename P::type,T>::type> operator ()(P){
		return lambda<T,typename format<typename P::type,T>::type>();
	}
};
 
template<class T> struct subst{
	typedef T type;	
};
template<class R,class T> struct subst<lambda<R,T> >{
	typedef lambda<R,typename subst<T>::type> type;
};
template<class M,class N> struct subst<A<M,N> >{
	typedef A<typename subst<M>::type,typename subst<N>::type> type;
};
template<int N,int T> struct subst<Var<N,T> >{
	typedef Var<N-1,T> type;
};
 
template<class T> struct clean{
	typedef T type;
};
template<class T> struct clean<lambda<nu,T> >{
	typedef typename subst<T>::type type;
};
 
template<class T,int N> struct upper{
	typedef T type;
};
template<class L,class R,int N> struct upper<A<L,R>,N>{
	typedef A<typename upper<L,N>::type,typename upper<R,N>::type> type;
};
template<class R,class M,int N> struct upper<lambda<R,M>,N>{
	typedef lambda<R,typename upper<M,N>::type> type;
};
template<int L,int N,int R> struct upper<Var<L,N>,R>{
	typedef Var<L+R,N> type;
};
 
template<int C,int P,class M,class T,int N> struct simple{
	typedef M type;
};
template<int C,int P,class T,int N> struct simple<C,P,Var<C,P>,T,N>{
	typedef typename upper<T,N>::type type;
};
template<int C,int P,class R,class M,class T,int N> struct simple<C,P,lambda<R,M>,T,N>{
	typedef lambda<R,typename simple<C,P,M,T,N+1>::type> type;
};
template<int C,int P,class L,class R,class T,int N> struct simple<C,P,A<L,R>,T,N>{
	typedef A<typename simple<C,P,L,T,N>::type,typename simple<C,P,R,T,N>::type> type;
};
 
template<class M,class N> struct either_apply{};
template<bool F1,class T1,bool F2,class T2> struct either_apply<either<F1,T1>,either<F2,T2> >{
	typedef either<F1 || F2,A<T1,T2> > type;
};
template<class M,class N> struct either_lambda{};
template<class R,bool F,class T> struct either_lambda<R,either<F,T> >{
	typedef either<F,lambda<R,T> > type;
};
 
template<int N,class T> struct beta{
	typedef either<0,T> type;
};
template<int C,int P,class R,class M,class N> struct beta<C,A<lambda<args<P,R>,M>,N> >{
	typedef either<1,typename clean<lambda<R,typename simple<C,P,M,N,1>::type> >::type> type;
};
template<int C,class M,class N> struct beta<C,A<M,N> >{
	typedef typename either_apply<typename beta<C,M>::type,typename beta<C,N>::type>::type type;
};
template<int C,class R,class T> struct beta<C,lambda<R,T> >{
	typedef typename either_lambda<R,typename beta<C+1,T>::type>::type type;
};
 
template<class T> struct Re{};
template<class T> struct Re<either<0,T> >{
	typedef T type;
};
template<class T> struct Re<either<1,T> >{
	typedef typename Re<typename beta<0,T>::type>::type type;
};
 
template<class M,class N> struct lambda{
	typedef lambda<M,N> type;
	template<class T> typename Re<typename beta<0,A<lambda<M,N>,T> >::type>::type operator ()(T){
		return typename Re<typename beta<0,A<lambda<M,N>,T> >::type>::type();
	}
};
 
template<int N> struct church_t{
	typedef A<Var<0,27>,typename church_t<N-1>::type> type;
};
template<> struct church_t<0>{
	typedef Var<0,28> type;
};
template<int N> struct Church{
	typedef lambda<args<27,args<28,nu> >,typename church_t<N>::type> type;
	static const type value;
};
 
template<class T> struct count{};
template<int N,class T> struct count<A<Var<N,27>,T> >{
	static const int value=count<T>::value+1;
};
template<int N> struct count<Var<N,28> >{
	static const int value=0;
};
 
template<class R,class T> std::ostream& operator<<(std::ostream& os,lambda<R,T>){
	os<<"(λ"<<R()<<"."<<T()<<")";
	return os;
};
template<class T> std::ostream& operator<<(std::ostream& os,lambda<args<27,args<28,nu> >,T>){
	os<<count<T>::value;
	return os;
};
template<int M,int N> std::ostream& operator<<(std::ostream& os,Var<M,N>){
	os<<char(N+96);
	return os;
};
template<class L,class R,class C> std::ostream& operator<<(std::ostream& os,A<L,A<C,R> >){
	os<<L()<<" ("<<A<C,R>()<<")";
	return os;
};
template<class L,class R> std::ostream& operator<<(std::ostream& os,A<L,R>){
	os<<L()<<" "<<R();
	return os;
};
template<int N> std::ostream& operator<<(std::ostream& os,V<N>){
	os<<char(N+96);
	return os;
};
template<int N,class R> std::ostream& operator<<(std::ostream& os,args<N,R>){
	os<<char(N+96)<<R();
	return os;
}
std::ostream& operator<<(std::ostream& os,nu){
	return os;
}
template<int N> std::ostream& operator<<(std::ostream& os,ph<N>){
	os<<char(N+96);	
	return os;
}
 
lambda_t<nu> Lambda;
ph<1> a;
ph<2> b;
ph<3> c;
ph<4> d;
ph<5> e;
ph<6> f;
ph<7> g;
ph<8> h;
ph<9> i;
ph<10> j;
ph<11> k;
ph<12> l;
ph<13> m;
ph<14> n;
ph<15> o;
ph<16> p;
ph<17> q;
ph<18> r;
ph<19> s;
ph<20> t;
ph<21> u;
ph<22> v;
ph<23> w;
ph<24> x;
ph<25> y;
ph<26> z;
ph<27> Fu;
ph<28> Va;
 
auto _s=Lambda[x][y][z](x(z)(y(z)));
auto _k=Lambda[x][y](x);
auto _i=Lambda[x](x);
 
#define S (_s)
#define K (_k)
#define I (_i)
 
auto Succ=Lambda[n][Fu][Va](Fu(n(Fu)(Va)));
auto Prev=Lambda[n][Fu][Va](n(Lambda[g][h](h(g(Fu))))(Lambda[u](Va))(Lambda[u](u)));
auto Add=Lambda[m][n][Fu][Va](m(Fu)(n(Fu)(Va)));
auto Mul=Lambda[m][n][Fu][Va](m(n(Fu))(Va));
auto True=Lambda[x][y](x);
auto False=Lambda[x][y](y);
auto And=Lambda[p][q](p(q)(False));
auto Or=Lambda[p][q](p(True)(q));
auto Not=Lambda[p](p(False)(True));
auto If=Lambda[p][x][y](p(x)(y));
auto Cons=Lambda[s][b][f](f(s)(b));
auto Car=Lambda[p](p(True));
auto Cdr=Lambda[p](p(False));
 
int main(){
	//SKI
	std::cout<<S<<std::endl;
	std::cout<<K<<std::endl;
	std::cout<<I<<std::endl;
	std::cout<<S K K (a)<<std::endl;
	std::cout<<S I I (a)<<std::endl;
	std::cout<<K (a)<<std::endl;
	std::cout<<K (a) (b)<<std::endl;
	std::cout<<K I<<std::endl;
	std::cout<<K I (a) (b)<<std::endl;
	std::cout<<S(S(K(S))K)(I)<<std::endl; //Bug	Expect:λxy.x(x y)
	//std::cout<<S I I(S I I)<<std::endl; -- Compile Error
	std::cout<<std::endl;
 
	//Church
	std::cout<<Church<5>::value<<std::endl;
	std::cout<<Succ(Church<5>::value)<<std::endl;
	std::cout<<Prev(Church<5>::value)<<std::endl;
	std::cout<<Add(Church<5>::value)(Church<3>::value)<<std::endl;
	std::cout<<Mul(Church<5>::value)(Church<3>::value)<<std::endl;
	std::cout<<std::endl;
 
	//Logic
	std::cout<<True<<std::endl;
	std::cout<<False<<std::endl;
	std::cout<<And(True)(True)<<std::endl;
	std::cout<<And(True)(False)<<std::endl;
	std::cout<<Or(False)(True)<<std::endl;
	std::cout<<Or(False)(False)<<std::endl;
	std::cout<<Not(True)<<std::endl;
	std::cout<<Not(False)<<std::endl;
	std::cout<<If(True)(Church<5>::value)(Church<3>::value)<<std::endl;
	std::cout<<If(False)(Church<5>::value)(Church<3>::value)<<std::endl;
	std::cout<<If(And(False)(True))(Church<5>::value)(Church<3>::value)<<std::endl;
	std::cout<<std::endl;
 
	//Cons,List
	std::cout<<Cons(a)(b)<<std::endl;
	std::cout<<Car(Cons(a)(b))<<std::endl;
	std::cout<<Cdr(Cons(a)(b))<<std::endl;
	auto tc=Cons(Cons(a)(b))(Cons(c)(d));
	std::cout<<tc<<std::endl;
	std::cout<<Car(tc)<<std::endl;
	std::cout<<Cdr(Car(tc))<<std::endl;
	auto lt=Cons(a)(Cons(b)(Cons(c)(False)));
	std::cout<<Car(lt)<<std::endl;
	std::cout<<Cdr(lt)<<std::endl;
	std::cout<<Cdr(Cdr(Cdr(lt)))<<std::endl;
	std::cout<<std::endl;
}