Most functional compiler

もっとも関数的なコンパイラ

受賞者：Ben Lynn

Line wrap

Highlight

#define x 0/**/
char*v,*y="33Yb59@&iBFApt;[[h3V19\\3<:4cJ!U 2eT18pC,Qqik4J:sh?HUXMrR(-l0R\"!eKZcI!@E(@B,C/*!aogn5LbK/e=2CmReb+6,]kD!iOC9DEOC9Dc1EV6976c?&s)Be;P;E^tl2eUYkg*#Yf:6^d[Mg_P;VGCr823^L_<X+j2,%nD20Ls lmpi&I(*hV=+p aTO`r.b1<i[/R\\t1,KBt)\\%;\\@27H>^#d6B!tb-on27d%i_OS5(W5eV-=M14kYO);Fe7k!N41<iX*T,kHW,&)_l&L)'0:Jj%j7^h+JU /9pZn&Td:&T%'TE<7>LW%m/R\\rON3-=G]^akjT778YCJ7B8e-5E#RX R=Ig8#/pDdAI;=a[ ISbp't+ZLJ;lUO71C)b5[Y)qTWmFJ)G1ehmS<.`n3RnE IG+G_A`CE=?hZU)bScgt7R3GNs+V(HQLL_R)n4;]#cUR.p>5!^4T3pQg^o//WLATCE18mSUme[Q<53e:')Q_%<L$1lKOnFD(R3%*jj85VW+#8Wt*Ud,1D7AKcdh<9r%igC$2</HD7X$K_0Rr/>L.*D2%;[0B+#8UANT1.tSd/^@L$&a6^g@jYNMC7O<rPWO5AfA;C'9WnLn9E:0d:R\\hAZ^m=/09d.R$Jd%:Gp hB-g4&N!VO)$;iED1:F`^`UrnWCSZ!L$Tdma!_hn7H0F$^MT(-Ln9F_Ljfp9*h8Er!<.g.h_7@b0l03?a+]`=dIoY>WCKOk&#[9FCQ#WFoga(tK<[PG6@5k2KY\\ oW':M;e//kd\"[l,_V?UlZ,m(Hh?O81mhM!G18 ]7m?X7e^[7EZYj[;kR,YXD\\X,!k6.HF8Z(V^^nBYea^NIL:]lG0(/\\Ik<m`>jPam;F-A,(tVN+bG@<L'J 1D8dE*hN87:TsccSKVE7KP+k8^5qZIkJG_fH_$MS--5(!*St/1:b+g8(/*",*T,*n=" $6I7H#v Jw	{};	  } }    } 	 } }	 ; } 	 { } 	 } ;	  		 { { 	   } } }   ;  ; 	 } 	 ; 	 } } ; }	 }	 } ; }	  	  	 } ; 	 } {	   	 }	 ; } } 	 ;  ; } 	 } ;  {	 }   { } ; } { ;	 {  ;	 { 	 }  ; ; ;	 { { } } 	 ; 	 ; { 	 }   {}  } } }  {	 ;   {	  	 ; } {	 	 } } } }	    ;} ;	 	 } }	 }	 } }} } } 	 }	 {}  :!#$%&*+./<=>?@\\^|-~			  	   \n	} { {  }  --			 	 ;} ; 	 ; } 	 } 	  ; { {  } }  } { } 	 ; 		 }	 	   \\'\"		} { ; 		 }{  }	} }  	} ; } }}   }} }  :	} 	  } }	 } 	 	 }  {	 	{  ; 	  		  of	 ;	 	 }  {	 }	 }	  	 } } { 	  }  ;	 	 	 {	 {	 } }	 ;} 	} {} ; }  }	 	 }} }    ;	 }} 	 	 {	  ->	 	{ 		{ 	  	 ;	 } ;	 } }} ; 	}  	 }	 } }} 	 	} 		 {} 	  } ; } 	} }} }} }} { }} } } ; }  { }} ;	 ;	 {} ; ;	 } ; } }; {	} { 	 ; ;  	 	}  }} }} }} }} ;} } ; } {	 {} ;  let	;  in		 } ;} } ; } } {} ;  case	; } 	 } 	 ;} } }	 {} { } {	 ;} } ; {	 {} {	 }	 {	  ;	 }} }} } } 		 	} ;} } ;} } } } 		}  		 	 	;  ; 	; 	  } {; {; {; } 	 } } ; } }  ;  }  { ;  {; } } ; {; }; } };  };   };  ; }; ;;  }; ; 	 ;	 }; } } ;}   : <= * + - /	}; { } 	} {} 	} ; } 	 {	} 	} ; }	  data	 	 	} ; }; ;	} { {; 	 {	 	 } ; ;; 	 }	} 	} };  	} ; } ;} {	} {	} } 	 } 	 ; ;	{ 	} } {	  }	} 	} {; 	 ;} }	} 	} {	 {	  	 	 ;; #define x \\";
#include <stdio.h>
typedef unsigned P;
enum{ L=1<<26} ;

P I,C,K=24,M,E

,j[L]={ x},*D=j+L/2,*i=j+L-3;
P w(P _){ return j[_[i]+1]; }
#define X(f,b,y,d) void f(){ D=j+b[i]; *D=y; *++D=d; i+=b; }
X(A,1,w(1),i[1])X(a,2,w(2),w(1))P l(P _,P E){ j[K++]=_; K++[j]=E; return K-2; }
int S;
X(t,1,9,(S=getchar())<0?8:l(l(17,l(1,S)),l(7,0)))P U(P _){ return j[w(_)+1]; }
X(_,2,9,U(1)>U(2)?l(8,9):8)X(b,2,w(2),i[1])P G(P _,P S){ return l(w(_),w(S)); }
#define B(f,o) X(f,2,1,U(1)o U(2))
B(p,*)X(c,3,w(1),G(2,3))X(u,3,G(1,3),w(2))P N(P l,P L,P _){
I=0;
while(*T-I[v])I++;
T++;
return I/6?l:N(l+I/_*L,L*6/_,3-_);
}
X(s,3,G(2,3),w(1))X(m,4,G(4,1),w(2))B(o,-)X(f,3,G(1,3),G(2,3))P Z(){
P _=*T++;
return _-9?l(l(17,l(1,_)),Z()):8;
}
X(d,2,w(1),w(2))X(R,2,l(w(2),printf(E?"%c":"%u,",U(1))),l(23,9))P W(P _){
if(S--); else{ M=0; C=5; while(C--)M=85*M+*y++-32; S=31; }
I=_*2+!!(M&1<<S);
for(_=0; (C=_[n]-9)&&C-I-23; _++);
return C?_?--_<2?C=N(0,1,1),_?l(_,C):C?C<8?C+15:7[D-C]:Z():_:(_=W(0),l(_,W(0))):W(I);
}
B(g,/)B(r,+)X(e,2,9,w(1))X(O,2,w(2),l(w(1),M-8))int main(){
v=12+n;
if(E=*j,E){
D=j+2;
K=E;
} else{
T=v+7;
while((*D=W(0)))D++;
puts(T);
}
*i=l(l(l(*--D,l(7,0)),0),l(23,9));
while(M=*i,M)M<24?(void(*[])()){

 O,b,f,u,s,c,a,t,e,d,_,p,r,o,g,R,A,m

} [M*(M<18)](),7:(*--i=M[j]); return E||puts(y); }

引用元：https://www.ioccc.org/2019/lynn/prog.c

審査員・作者による説明：https://www.ioccc.org/2019/lynn/hint.html

動作

Haskellサブセットのコンパイラ。

コンパイルすると、HaskellからCコード断片を生成するコンパイラになっている。

$ gcc -o prog prog.c

$ (./prog < fib.hs; cat prog.c) > fib.c

生成されたCコード断片とprog.cを連結してコンパイルすると、Haskellコードの意味で動作する。

$ gcc -o fib fib.c

$ ./fib
832040

解説

かなり簡素にしたHaskellサブセットを受理して、独自のバイトコードを出力する。

ややこしい型を排除した
実行を阻害するガベージコレクションはしない
IOモナドを排除し、すべての関数は純粋
演算子を限定しているのでややこしいレイアウトルールは不要
プリミティブの型はIntのみ、他の型はスコットエンコーディングで実現
dataはあるが、タプルなし、リスト内包表記なし、単項演算子なし
mainは[Int] -> [Int]で入出力を表現する

出力のバイトコードはC言語の#defineにくるんで出力し、prog.cと結合してコンパイル・実行することが前提になっている。

セルフホストするコンパイラ、正規表現の文字列列挙、強連結成分分解のサンプルコードが添付されている。