Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement