Most lazy SKIer

もっとも怠惰なスキーヤー

Line wrap

Highlight

#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/index.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ソルバで求めた。