fork download
copy 
  1. #include<iostream>
  2. #include<typeinfo>
  3. #include<cxxabi.h>
  4.  
  5. template<int N> struct V{};
  6. template<int N,class T> struct args{};
  7. template<int M,int N> struct Var{};
  8. template<bool N,class T> struct either{};
  9. struct nu{};
  10. template<class R,class T> struct lambda;
  11.  
  12. template<class M,class N> struct A{
  13. 	typedef A<M,N> type;
  14. 	template<class T> A<A<M,N>,typename T::type> operator()(T){
  15. 		return A<A<M,N>,typename T::type>();
  16. 	}
  17. };
  18. template<int N> struct ph{
  19. 	typedef V<N> type;
  20. 	template<class T> A<V<N>,typename T::type> operator()(T){
  21. 		return A<V<N>,typename T::type>();
  22. 	}
  23. };
  24.  
  25. template<int N,class T> struct addarg{};
  26. template<int N> struct addarg<N,nu>{
  27. 	typedef args<N,nu> type;
  28. };
  29. template<int N,int C,class T> struct addarg<N,args<C,T> >{
  30. 	typedef args<C,typename addarg<N,T>::type> type;
  31. };
  32.  
  33. template<int N,int C,class T> struct notfound{};
  34. template<int N,int C,class T> struct notfound<N,C,args<C,T> >{
  35. 	static const int value=N;
  36. };
  37. template<int N,int C,int R,class T> struct notfound<N,C,args<R,T> >{
  38. 	static const int value=notfound<N,C,T>::value;
  39. };
  40. template<int N,int C> struct notfound<N,C,nu>{
  41. 	static const int value=-1;
  42. };
  43.  
  44. template<int N,class T,class F> struct format_t{
  45. 	typedef T type;
  46. };
  47. template<int N,int C,class F> struct format_t<N,V<C>,F>{
  48. 	typedef Var<notfound<N,C,F>::value,C> type;
  49. };
  50. template<int N,int C,class F> struct format_t<N,Var<-1,C>,F>{
  51. 	typedef Var<notfound<0,C,F>::value,C> type;
  52. };
  53. template<int N,int T,int C,class F> struct format_t<N,Var<T,C>,F>{
  54. 	typedef Var<T+1,C> type;
  55. };
  56. template<int N,class L,class R,class F> struct format_t<N,A<L,R>,F>{
  57. 	typedef A<typename format_t<N,L,F>::type,typename format_t<N,R,F>::type> type;
  58. };
  59. template<int N,class T,class P,class F> struct format_t<N,lambda<T,P>,F>{
  60. 	typedef lambda<T,typename format_t<N+1,P,F>::type> type;
  61. };
  62. template<class T,class F> struct format{
  63. 	typedef typename format_t<0,T,F>::type type;
  64. };
  65.  
  66. template<class T> struct lambda_t{
  67. 	template<int N> lambda_t<typename addarg<N,T>::type> operator [](ph<N>){
  68. 		return lambda_t<typename addarg<N,T>::type>();
  69. 	}
  70. 	template<class P> lambda<T,typename format<typename P::type,T>::type> operator ()(P){
  71. 		return lambda<T,typename format<typename P::type,T>::type>();
  72. 	}
  73. };
  74.  
  75. template<class T> struct subst{
  76. 	typedef T type;	
  77. };
  78. template<class R,class T> struct subst<lambda<R,T> >{
  79. 	typedef lambda<R,typename subst<T>::type> type;
  80. };
  81. template<class M,class N> struct subst<A<M,N> >{
  82. 	typedef A<typename subst<M>::type,typename subst<N>::type> type;
  83. };
  84. template<int N,int T> struct subst<Var<N,T> >{
  85. 	typedef Var<N-1,T> type;
  86. };
  87.  
  88. template<class T> struct clean{
  89. 	typedef T type;
  90. };
  91. template<class T> struct clean<lambda<nu,T> >{
  92. 	typedef typename subst<T>::type type;
  93. };
  94.  
  95. template<class T,int N> struct upper{
  96. 	typedef T type;
  97. };
  98. template<class L,class R,int N> struct upper<A<L,R>,N>{
  99. 	typedef A<typename upper<L,N>::type,typename upper<R,N>::type> type;
  100. };
  101. template<class R,class M,int N> struct upper<lambda<R,M>,N>{
  102. 	typedef lambda<R,typename upper<M,N>::type> type;
  103. };
  104. template<int L,int N,int R> struct upper<Var<L,N>,R>{
  105. 	typedef Var<L+R,N> type;
  106. };
  107.  
  108. template<int C,int P,class M,class T,int N> struct simple{
  109. 	typedef M type;
  110. };
  111. template<int C,int P,class T,int N> struct simple<C,P,Var<C,P>,T,N>{
  112. 	typedef typename upper<T,N>::type type;
  113. };
  114. template<int C,int P,class R,class M,class T,int N> struct simple<C,P,lambda<R,M>,T,N>{
  115. 	typedef lambda<R,typename simple<C,P,M,T,N+1>::type> type;
  116. };
  117. template<int C,int P,class L,class R,class T,int N> struct simple<C,P,A<L,R>,T,N>{
  118. 	typedef A<typename simple<C,P,L,T,N>::type,typename simple<C,P,R,T,N>::type> type;
  119. };
  120.  
  121. template<class M,class N> struct either_apply{};
  122. template<bool F1,class T1,bool F2,class T2> struct either_apply<either<F1,T1>,either<F2,T2> >{
  123. 	typedef either<F1 || F2,A<T1,T2> > type;
  124. };
  125. template<class M,class N> struct either_lambda{};
  126. template<class R,bool F,class T> struct either_lambda<R,either<F,T> >{
  127. 	typedef either<F,lambda<R,T> > type;
  128. };
  129.  
  130. template<int N,class T> struct beta{
  131. 	typedef either<0,T> type;
  132. };
  133. template<int C,int P,class R,class M,class N> struct beta<C,A<lambda<args<P,R>,M>,N> >{
  134. 	typedef either<1,typename clean<lambda<R,typename simple<C,P,M,N,1>::type> >::type> type;
  135. };
  136. template<int C,class M,class N> struct beta<C,A<M,N> >{
  137. 	typedef typename either_apply<typename beta<C,M>::type,typename beta<C,N>::type>::type type;
  138. };
  139. template<int C,class R,class T> struct beta<C,lambda<R,T> >{
  140. 	typedef typename either_lambda<R,typename beta<C+1,T>::type>::type type;
  141. };
  142.  
  143. template<class T> struct Re{};
  144. template<class T> struct Re<either<0,T> >{
  145. 	typedef T type;
  146. };
  147. template<class T> struct Re<either<1,T> >{
  148. 	typedef typename Re<typename beta<0,T>::type>::type type;
  149. };
  150.  
  151. template<class M,class N> struct lambda{
  152. 	typedef lambda<M,N> type;
  153. 	template<class T> typename Re<typename beta<0,A<lambda<M,N>,T> >::type>::type operator ()(T){
  154. 		return typename Re<typename beta<0,A<lambda<M,N>,T> >::type>::type();
  155. 	}
  156. };
  157.  
  158. template<int N> struct church_t{
  159. 	typedef A<Var<0,27>,typename church_t<N-1>::type> type;
  160. };
  161. template<> struct church_t<0>{
  162. 	typedef Var<0,28> type;
  163. };
  164. template<int N> struct Church{
  165. 	typedef lambda<args<27,args<28,nu> >,typename church_t<N>::type> type;
  166. 	static const type value;
  167. };
  168.  
  169. template<class T> struct count{};
  170. template<int N,class T> struct count<A<Var<N,27>,T> >{
  171. 	static const int value=count<T>::value+1;
  172. };
  173. template<int N> struct count<Var<N,28> >{
  174. 	static const int value=0;
  175. };
  176.  
  177. template<class R,class T> std::ostream& operator<<(std::ostream& os,lambda<R,T>){
  178. 	os<<"(λ"<<R()<<"."<<T()<<")";
  179. 	return os;
  180. };
  181. template<class T> std::ostream& operator<<(std::ostream& os,lambda<args<27,args<28,nu> >,T>){
  182. 	os<<count<T>::value;
  183. 	return os;
  184. };
  185. template<int M,int N> std::ostream& operator<<(std::ostream& os,Var<M,N>){
  186. 	os<<char(N+96);
  187. 	return os;
  188. };
  189. template<class L,class R,class C> std::ostream& operator<<(std::ostream& os,A<L,A<C,R> >){
  190. 	os<<L()<<" ("<<A<C,R>()<<")";
  191. 	return os;
  192. };
  193. template<class L,class R> std::ostream& operator<<(std::ostream& os,A<L,R>){
  194. 	os<<L()<<" "<<R();
  195. 	return os;
  196. };
  197. template<int N> std::ostream& operator<<(std::ostream& os,V<N>){
  198. 	os<<char(N+96);
  199. 	return os;
  200. };
  201. template<int N,class R> std::ostream& operator<<(std::ostream& os,args<N,R>){
  202. 	os<<char(N+96)<<R();
  203. 	return os;
  204. }
  205. std::ostream& operator<<(std::ostream& os,nu){
  206. 	return os;
  207. }
  208. template<int N> std::ostream& operator<<(std::ostream& os,ph<N>){
  209. 	os<<char(N+96);	
  210. 	return os;
  211. }
  212.  
  213. lambda_t<nu> Lambda;
  214. ph<1> a;
  215. ph<2> b;
  216. ph<3> c;
  217. ph<4> d;
  218. ph<5> e;
  219. ph<6> f;
  220. ph<7> g;
  221. ph<8> h;
  222. ph<9> i;
  223. ph<10> j;
  224. ph<11> k;
  225. ph<12> l;
  226. ph<13> m;
  227. ph<14> n;
  228. ph<15> o;
  229. ph<16> p;
  230. ph<17> q;
  231. ph<18> r;
  232. ph<19> s;
  233. ph<20> t;
  234. ph<21> u;
  235. ph<22> v;
  236. ph<23> w;
  237. ph<24> x;
  238. ph<25> y;
  239. ph<26> z;
  240. ph<27> Fu;
  241. ph<28> Va;
  242.  
  243. auto _s=Lambda[x][y][z](x(z)(y(z)));
  244. auto _k=Lambda[x][y](x);
  245. auto _i=Lambda[x](x);
  246.  
  247. #define S (_s)
  248. #define K (_k)
  249. #define I (_i)
  250.  
  251. auto Succ=Lambda[n][Fu][Va](Fu(n(Fu)(Va)));
  252. auto Prev=Lambda[n][Fu][Va](n(Lambda[g][h](h(g(Fu))))(Lambda[u](Va))(Lambda[u](u)));
  253. auto Add=Lambda[m][n][Fu][Va](m(Fu)(n(Fu)(Va)));
  254. auto Mul=Lambda[m][n][Fu][Va](m(n(Fu))(Va));
  255. auto True=Lambda[x][y](x);
  256. auto False=Lambda[x][y](y);
  257. auto And=Lambda[p][q](p(q)(False));
  258. auto Or=Lambda[p][q](p(True)(q));
  259. auto Not=Lambda[p](p(False)(True));
  260. auto If=Lambda[p][x][y](p(x)(y));
  261. auto Cons=Lambda[s][b][f](f(s)(b));
  262. auto Car=Lambda[p](p(True));
  263. auto Cdr=Lambda[p](p(False));
  264.  
  265. int main(){
  266. 	//SKI
  267. 	std::cout<<S<<std::endl;
  268. 	std::cout<<K<<std::endl;
  269. 	std::cout<<I<<std::endl;
  270. 	std::cout<<S K K (a)<<std::endl;
  271. 	std::cout<<S I I (a)<<std::endl;
  272. 	std::cout<<K (a)<<std::endl;
  273. 	std::cout<<K (a) (b)<<std::endl;
  274. 	std::cout<<K I<<std::endl;
  275. 	std::cout<<K I (a) (b)<<std::endl;
  276. 	std::cout<<S(S(K(S))K)(I)<<std::endl; //Bug	Expect:λxy.x(x y)
  277. 	//std::cout<<S I I(S I I)<<std::endl; -- おなじみのアレ コンパイルエラー
  278. 	std::cout<<std::endl;
  279.  
  280. 	//Church 数値で出力するようになってはいる
  281. 	std::cout<<Church<5>::value<<std::endl;
  282. 	std::cout<<Succ(Church<5>::value)<<std::endl;
  283. 	std::cout<<Prev(Church<5>::value)<<std::endl;
  284. 	std::cout<<Add(Church<5>::value)(Church<3>::value)<<std::endl;
  285. 	std::cout<<Mul(Church<5>::value)(Church<3>::value)<<std::endl;
  286. 	std::cout<<std::endl;
  287.  
  288. 	//Logic 出力はそのまま
  289. 	std::cout<<True<<std::endl;
  290. 	std::cout<<False<<std::endl;
  291. 	std::cout<<And(True)(True)<<std::endl;
  292. 	std::cout<<And(True)(False)<<std::endl;
  293. 	std::cout<<Or(False)(True)<<std::endl;
  294. 	std::cout<<Or(False)(False)<<std::endl;
  295. 	std::cout<<Not(True)<<std::endl;
  296. 	std::cout<<Not(False)<<std::endl;
  297. 	std::cout<<If(True)(Church<5>::value)(Church<3>::value)<<std::endl;
  298. 	std::cout<<If(False)(Church<5>::value)(Church<3>::value)<<std::endl;
  299. 	std::cout<<If(And(False)(True))(Church<5>::value)(Church<3>::value)<<std::endl;
  300. 	std::cout<<std::endl;
  301.  
  302. 	//Cons,List 出力はそのまま
  303. 	std::cout<<Cons(a)(b)<<std::endl;
  304. 	std::cout<<Car(Cons(a)(b))<<std::endl;
  305. 	std::cout<<Cdr(Cons(a)(b))<<std::endl;
  306. 	auto tc=Cons(Cons(a)(b))(Cons(c)(d));
  307. 	std::cout<<tc<<std::endl;
  308. 	std::cout<<Car(tc)<<std::endl;
  309. 	std::cout<<Cdr(Car(tc))<<std::endl;
  310. 	auto lt=Cons(a)(Cons(b)(Cons(c)(False)));
  311. 	std::cout<<Car(lt)<<std::endl;
  312. 	std::cout<<Cdr(lt)<<std::endl;
  313. 	std::cout<<Cdr(Cdr(Cdr(lt)))<<std::endl;
  314. 	std::cout<<std::endl;
  315. }
  316.  
Success #stdin #stdout 0s 2836KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(λxyz.x z (y z))
(λxy.x)
(λx.x)
a
a a
(λy.a)
a
(λy.(λx.x))
b
(λz.(λz.y z z z (y z z)))

5
6
4
8
15

(λxy.x)
(λxy.y)
(λxy.x)
(λxy.y)
(λxy.x)
(λxy.y)
(λxy.y)
(λxy.x)
5
3
3

(λf.f a b)
a
b
(λf.f (λf.f a b) (λf.f c d))
(λf.f a b)
b
a
(λf.f b (λf.f c (λxy.y)))
(λxy.y)
https://ideone.com/us66y
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!