もっとも怠惰なスキーヤー
xxxxxxxxxx
#ifndef SKI
#define A(x)B(x##0)B(x##1)B(x##2)B(x##3)B(x##4)B(x##5)
#define B(x)C(x##0)C(x##1)C(x##2)C(x##3)C(x##4)C(x##5)
#define C(x)D(x##0)D(x##1)D(x##2)D(x##3)D(x##4)D(x##5)
#define D(x)Z(x##0)Z(x##1)Z(x##2)Z(x##3)Z(x##4)Z(x##5)
#define p(x)(*(*(*(*(*(*x)())())())())())()
#include <stdio.h>
#include <stdlib.h>
#define S (Y(s+6))
#define K (Y(s+4))
#define I (Y(s+2))
#define Z(x)\
f x;f Y(v);g\
j;f \
x##z( f\
y){y =y?! x?x= y:Y( m(*( w)&\
x,(( g)y) (0)) ):x;return y; /*ab c*/}
/**/ typedef void *v ;int
n=0; typedef v* w;typed\
ef v(*g)();v s[]= {0,0, s+6, s+2,
s+4,s,s+3,s+ 5,s+ 1};w m( v l ,v
r){w e=ma\
lloc (siz\
eof( v)*3
);*e =r;e [1
]=l;return (e[2 ]=s, e);} /*de fghi jk*/ typ\
edef v(p( p(p( p(p( p(p( p(p( p(p(f)))) ))) )))) );A(
x)w u(){ return n --?m (j(0 ),u( )):s+3;}
w z( w e) {w a,b , c,d;for (d =e=m(e,0
);n= (w)d[ 2]-s ,n?* (n>1? n<4? b:a:
c)?n <2?c[ 1]=m (*a, *c), *c=m (*b,
*c):
n>5?
#undef Z
#define Z(x\
) &x ##z,
a[1]= m(
*a,!*d? d[1] =c=m (0,0 ),n= getchar(),n= n<0?
256:n,c [2]= s+6, *d=u ():* d),*a=d[1]: n<5?n<3?n=z(*
a)-s, putchar( 255< +n?( exit (n-4
*64) ,0):n ),fflush (stdout) ,c[1 ]=
*b:((n-3?b:c )[1] =*a) :(2[* a=z(*a)+1,a
]=s+5),d =e:0 :e;d =d[1 ])c=b,b=a,a=
d;a=
*(w*
)e [1
]; ;;
/*lm no*/ return a;}f( *h [])( )={A (x)0};f Y(v x)
{g y =(g) h[n++] ;y(! y? exit( puts ("out of c" ""
"losure" )),x :x );return(f )y/* pq
r*/;}int main () {z(((g )(S S(
j=(g )S(S (K S)K))(K( S I I)) (S(K(S I))( S(
K K) (S(K (S(S(K(Y(s+1 )) )(S( S S(K I)) (K (Y
(s +5)) ))
)) )K)) )(
#endif
#if (!defined(__INCLUDE_LEVEL__) || !__INCLUDE_LEVEL__) && !defined(SKI)
K(I(I(I(S I I(S(K(S(S(K S)(S(S S S(K(S(K S)))(S(S S S(K(S(K S)))(S(K(S(S(K S)(S(S(K S)K)(K(S(S(K S)(S(K(S(S(S I(K K))(K K))))(S(K K)(S(S(K S)(S(K(S(S I(K K))))(S(K K)(S(S(K K))(K(S(S(S(S(K S)K)))I(S(S(K S)K)I)))))))(S(K K)(S(S(K K))(K(S(K(S(S(K S)K)I))(S(S(K S)K)(S I I(S(S(K S)K)I)))))))))))(S(K K)(S(K K)(S(S(K K))(K(S(K(S(S(K S)K)I))(S(S I I)I(S(S(K S)K)I)))))))))))))(S(K K)(S(K K)(S(K(S(S I(K(S(S I(K(K I)))(K S))))))K)))))(K(K(K K)))))(K(K(K(K I))))))))(S(K(S(K K)))(S(S(K S)(S(K K)(S(K S)(S(S(K K))I))))(K(S(K(S(S(K S)(S(K(S I))K))))(S(K K)K))))))(S(S I(K(S I I(S I I(S(S(K S)K)I)))))(K(K K)))S K K K I I I K K K I I I K K K I I I K K K I I K K K K K S K I I I K I K I I I K I K)I I I K I K I I I K I I I K I I S K I I I I I K I I I I I K I K I I I K I I I K I I S K I I)I K I K I I I K I K I I I K I K I I I K I I I K I I S K K K I I I K K K I I I K K K I I I K K K I I K K K K K S S K I I I K S)K I I K S K K K S K I I K S K I I I K S S K K K K K S K I I I I S K K K K K S K S K K K K K(K K))
#define SKI
#endif
#ifdef SKI
(Y(s)))))(0));return 0;}
#else
#define SKI
#endif
引用元:https://www.ioccc.org/2013/endoh1/endoh1.c
審査員・作者による説明:https://www.ioccc.org/2013/endoh1/hint.html
Lazy Kのインタプリタ。
Lazy Kのソースコードを普通に読み込むのではなく、Lazy Kのコードの最初と最後でendoh1.cを#include
してコンパイルすることで、Lazy Kのプログラムを実行する。
たとえば次は、Lazy Kのソースコードの例。
#include "endoh1.c"
K(S(S I(K(S(K(S I I(S(S(K S)K)I)))(S(S(K S)K)(S(S(K S)K)(S(S I I)I(S(S(K S)K)I)))))))(K(S(S I(K(S(S(K S)K)(S(S(K S)K)I(S(K(S(S(K S)K)I))(S(S(K S)K)(S I I(S(S(K S)K)I))))))))(K(S(S(K S)(S(K(S I))K))(S(K K)(S(S(K S)(S(K(S I))K))(S(K K)(S(S(K S)(S(K(S I))(S(K K)(S(S I(K(S(S(K S)K))))(K(S(S(K S)K)(S(S(K S)K)I)))))))(K(K(S(S I(K(S(S(K S)K)(S(S I I)I(S(S(K S)K)I))(S(S(K S)K))(S I I(S(S(K S)K)(S(S(K S)K)I))))))(K(S(S I(K(S(K(S(S(K S)K)I))(S(S I I)I(S(S(K S)K)I)))))(K(S(S I(K(S(S(K S)K)(S(K(S I I(S(S(K S)K)I)))(S(S(K S)K)(S(S(K S)K)(S(S I I)I(S(S(K S)K)I))))))))(K(S(S I(K(S(S(K S)K)(S(K(S(S(K S)K)(S(S(K S)K)I)))(S(S(K S)K)(S(S(K S)K)I(S(S(K S)K)(S I I(S(S(K S)K)I)))))))))(K(S(S(K S)(S(K(S I))K))(S(K K)(S(S(K S)(S(K(S I))K))(S(K K)(S(S(K S)(S(K(S I))K))(K(K(S(S I(K(S(S(K S)K)(S(K(S(S(K S)K)I))(S(S I I)I(S(S(K S)K)I))))))(K(S(S I(K(S(K(S(S(K S)K)I))(S(S(K S)K)(S I I(S(S(K S)K)I))))))(K(S(S I(K(S I I(S I I(S(S(K S)K)I)))))(K S))))))))))))(S(S(K S)K)(S(S(K S)K)(S(S(K S)K)(S(S(S(K S)K))(S I I)(S(S(K S)K)I))))))))))))))))))))(S(K(S I I(S(S(K S)K)I)))(S I I(S(S(K S)K)(S(S(K S)K)I)))))))))
#include "endoh1.c"
普通のLazy Kのインタプリタ、たとえばirori/lazykで実行すると次のようになる(#
で始まる行はLazy Kではコメントなので無視されている)。
$ ./lazyk hello.lazy
Hello, IOCCC!
そして、#include "endoh1.c"
で挟んであるので、C言語コードとしてコンパイル・実行しても同じ動作をする。
$ gcc -o hello -xc hello.lazy
$ ./hello
Hello, IOCCC!
なお、endoh1.c単体をコンパイル・実行すると、次のようなメッセージを表示する。
$ ./endoh1
@@@@@
@
@@@@@
@
@@@@@
@ @
@ @
@@@
@ @
@ @
@@@@@ @@@ @@@ @@@ @@@
@ @ @ @ @ @ @ @ @
@ @ @ @ @ @
@ @ @ @ @ @ @ @ @
@@@@@ @@@ @@@ @@@ @@@
これは、endoh1.cの中に埋め込まれたLazy Kのコードを実行することで出力している(78行目、K(I(I(I(...
で始まる行)。
Lazy Kの詳細はWikipediaの記事を参考のこと。
このプログラムは、SKIコンビネータをcall-by-needで評価する。 抽象構文木に次の規則を繰り返し適用することで、計算を行っていく。
I x
になっていたらx
に書き換えるK x y
になっていたらx
に書き換えるS x y z
になっていたらx z (y z)
に書き換えるコード形状はこの3つの規則をそのまま表現している。
基本的なアイデアは、SKIコンビネータの式をC言語の式として強引に解釈するところ。 次のマクロ定義が肝。
#define S (s)
#define K (k)
#define I (i)
これにより、たとえばS (K I)
という式は(s)((k)(i))
に置き換えられる。
これは普通のC言語で書くとs(k(i))
となる。
関数s
、k
、i
は構文木のノードを構築して返す。
SKIコンビネータをそのままC言語コードとして解釈するアイデアは単純だけれど、実現までには大きく3つの苦労があった。
1つめは、C言語に再帰型がないこと。
たとえばS S S S S ....
という式は、S(S)(S)(S)(S)...
と解釈されるので、先頭のS
は関数ポインタで、返り値が関数ポインタで、その返り値も関数ポインタで、……というのを無限に繰り返す式でないといけない。
しかしC言語ではそういう型はないので、有限回(50段くらい)で我慢することにした。
それで足りない場合は、恒等関数を挟んでI(I(S S S) S S S) S S S ...
とすれば回避できる。
2つめは、C言語でクロージャを表現すること。
S K I
があったとき、s(k)(i)
となるので、s(k)
は呼び出し可能な関数を返さないと行けない。
しかし、決まった関数を返してしまうと、抽象構文木のノードとして区別できなくなってしまうので、一意な関数ポインタを返さなければならない。
どうしたかというと、グローバル変数と関数をたくさん定義しておいて、関数ポインタの配列にしておいて、それを順次取り出すことにした。
足りなくなったら残念だけど異常終了。
3つめは、サイズ制限。
埋め込んだLazy Kのコードが意外と場所をとるので、評価器部分はかなり圧縮されている。
これはhint.textにある通り、s[]={0,0,s+6,s+2,s+4,s,s+3,s+5,s+1};
というテーブルが象徴的。
これを理解するには、抽象構文木の構造を理解する必要がある。
抽象構文木のノードは、(ポインタ, ポインタ, ノードの種類)
という3要素のポインタで表現している。
ノードの種類に応じて、解釈が変わる。
s+0
のとき、関数適用(ポインタ2つはそれぞれ右の項と左の項)s+1
のとき、S
と解釈される(ポインタ2つは無視)s+2
のとき、出力のためのダミーノードになるs+3
のとき、K
と解釈されるs+4
のとき、I
と解釈されるs+5
のとき、数字の0のためのダミーノードになるs+6
のとき、入力のためのダミーノードになるノードの種類の順番が不規則なのは、アリティチェックを簡単にするため。
1は引数3つのノード、2と3は引数2のノード、4と5と6は引数1のノードという順に並んでいるのでチェックが簡単になる。
なお、ノードの種類は実際には数字ではなく、配列へのポインタs
を足した値で表現される。
次に、s[]={0,0,s+6,s+2,s+4,s,s+3,s+5,s+1};
というテーブルを解説する。
このテーブルは、特殊ノードを事前定義したテーブルになっている。
s
は、{ 0, 0, s+6 }
の3要素を指しているため、入力のためのダミーノードになるs+1
は、{ 0, s+6, s+2 }
の3要素なので、出力のためのダミーノードになる(0
とs+6
は無視)s+2
は、{ s+6, s+2, s+4 }
の3要素なので、I
のノードになるs+3
は、{ s+2, s+4, s }
の3要素なので、K I
の関数適用ノードになるs+4
は、{ s+4, s, s+3 }
の3要素なので、K
のノードになるs+5
は、{ s, s+3, s+5 }
の3要素なので、数字の0のためのダミーノードになるs+6
は、{ s+3, s+5, s+1 }
の3要素なので、S
のノードになるということで配列s
の初期値は、3要素の窓をスライドしながら解釈するとすべてのプリミティブがみごとに詰まったものになっている。
K I
がプリミティブとしてあるのは、数字のスコットエンコードで必要になるため。
入力ノードは読み込んだ値をポインタ部に保存するので、空いている必要がある。
数字の0のためのダミーノードは、最初のポインタがs
である必要もあった。
これらの複雑な制約を満たすノードの種類と配列s
の初期値は、SMTソルバで求めた。