Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2014-02-19

[] 放射線耐性 Quine (1 文字消しても動く Quine)

ref: https://github.com/mame/radiation-hardened-quine

放射線はメモリエラーを引き起こすらしいです。そんな放射線が飛び交う過酷な環境でも、できることなら Quine したい。

ということで、プログラム内の 1 文字をランダムに消しても元のプログラムを出力する、なんともロバストな Quine を書きました。*1

何を言っているかわからないと思いますが、こんなふうに動くものです。

# ランダムに 1 文字消すスクリプト
$ cat mutate.rb
src = $<.read
src[rand(src.size), 1] = ""
print src

# rrquine.rb からランダムに 1 文字消したプログラムを生成する
$ ruby mutate.rb rrquine.rb > broken.rb

# 壊れたプログラムを実行する (!)
$ ruby broken.rb > rrquine2.rb

# 元に戻る (!!)
$ diff rrquine.rb rrquine2.rb # 一致!

正直書けるわけないと思ってましたが、なんと書けてしまった。Ruby 恐ろしいなあ。他に書ける言語があるだろうか。*2

以下コード。もっと賢い方法があったら教えてください。(追記: GitHub のリポジトリも作っておきました。)

eval='eval$q=%q(puts %q(10210/#{1 1 if 1==21}}/.i rescue##/

1 1"[13,213].max_by{|s|s.size}#"##").gsub(/\d/){["=\47eval$q=%q(#$q)#\47##\47

",:eval,:instance_,"||=9"][eval$&]}
exit)#'##'

instance_eval='eval$q=%q(puts %q(10210/#{1 1 if 1==21}}/.i rescue##/

1 1"[13,213].max_by{|s|s.size}#"##").gsub(/\d/){["=\47eval$q=%q(#$q)#\47##\47

",:eval,:instance_,"||=9"][eval$&]}
exit)#'##'

/#{eval eval if eval==instance_eval}}/.i rescue##/

eval eval"[eval||=9,instance_eval||=9].max_by{|s|s.size}#"##"

以下は最初に公開したバージョン。とりあえず動いただけのものなのでいろいろ汚い。

"%\  #{at_exit{eval'(eval q=%(s=%(B%A  C{at_exit{ZGQG##G

}}}ABB.rescue x rescue 42##B

Z=GQG##G

instance_Z=GQG##G

Z Z if Z==instance_Z
).gsub ?Z,%[eval]
7.times{|n|s.gsub! (n+65).chr,(n<1?92:n+33).chr}
puts s.gsub ?Q,%[(eval q=%(]+q+%[))#]
$stdout.flush
exit!0))#'##'

}}}\"".rescue x rescue 42##"

eval='(eval q=%(s=%(B%A  C{at_exit{ZGQG##G

}}}ABB.rescue x rescue 42##B

Z=GQG##G

instance_Z=GQG##G

Z Z if Z==instance_Z
).gsub ?Z,%[eval]
7.times{|n|s.gsub! (n+65).chr,(n<1?92:n+33).chr}
puts s.gsub ?Q,%[(eval q=%(]+q+%[))#]
$stdout.flush
exit!0))#'##'

instance_eval='(eval q=%(s=%(B%A  C{at_exit{ZGQG##G

}}}ABB.rescue x rescue 42##B

Z=GQG##G

instance_Z=GQG##G

Z Z if Z==instance_Z
).gsub ?Z,%[eval]
7.times{|n|s.gsub! (n+65).chr,(n<1?92:n+33).chr}
puts s.gsub ?Q,%[(eval q=%(]+q+%[))#]
$stdout.flush
exit!0))#'##'

eval eval if eval==instance_eval

*1:まあ、実際の放射線によるメモリエラーは除去じゃなくて文字化けですが、さすがにそれは対処不可能だと思う……。

*2:0 バイトで Quine と主張するのはナシで。

2014-02-07

[] クリーネの再帰定理+ Quine が書けることの証明

クリーネの再帰定理プログラマ向け説明(+証明)を書いてみました。何か間違ってたら教えて!

前提

  • 二つのプログラム p と q が完全に同じように振る舞うとき、p 〜 q と書くことにします*2。これは明らかに推移的。

定理

任意プログラム f に対し、p 〜 E(f, p) となるようなプログラム文字列 p が存在する。*3

定理の証明

以下のような 3 つの文字列を考えます。

このとき、

  • 任意の x に対し、E(h, x) 〜 E(x, x)
  • 任意の x に対し、E(e, x) 〜 E(f, E(h, x))
  • p 〜 E(h, e)

が言えます。よって、

  • p 〜 E(h, e) 〜 E(e, e) 〜 E(f, E(h, e)) 〜 E(f, p)

つまり p 〜 E(f, p) 。

Quine が存在することの証明

以下のように f を決めます。

このとき、

が言えます。上で示した定理から、

となるプログラム p が存在する、とわかります。

p は「文字列 p を画面に表示するプログラム」と完全に同じように振る舞う、ということはこれはまさに Quine!

よくわからん、Ruby で説明してくれ

h = '->(x) { "->(y) { eval(eval(%1$s).call(%1$s)).call(y) }" % x.dump }'
e = '->(x) { eval(f).call(eval(h).call(x)) }'
p = eval(h).call(e)
f = '->(x) { "->(y) { puts %s }" % x.dump }'

puts "source:"
puts p

puts "---"

puts "result:"
eval(p).call(nil)

call-by-value 対策で h をイータ展開してますが、ほぼ証明と同じ定義です。

$ ruby kleene.rb
source:
->(y) { eval(eval("->(x) { eval(f).call(eval(h).call(x)) }").call("->(x) { eval(f).call(eval(h).call(x)) }")).call(y) }
---
result:
->(y) { eval(eval("->(x) { eval(f).call(eval(h).call(x)) }").call("->(x) { eval(f).call(eval(h).call(x)) }")).call(y) }

無事 Quine しているようです。

「f とか h とか未定義じゃん!」とか「Proc 返すだけで実行してないじゃん!」とか細かいことを言う人はこちら。

h = '->(x) { "->(y) { eval(eval(%1$s).call(%1$s)).call(y) }" % x.dump }'
e = '->(x) { eval(f).call(eval(h).call(x)) }'
p = eval(h).call(e)
f = '->(x) { "->(y) { puts %s + \".call(nil)\" }" % x.dump }'

e = e.sub("f") { f.dump }
e = e.sub("h") { h.dump }
p = eval(h).call(e) + ".call(nil)"

puts p
$ ruby kleene2.rb > quine.rb
$ cat quine.rb
->(y) { eval(eval("->(x) { eval(\"->(x) { \\\"->(y) { puts %s + \\\\\\\".call(nil)\\\\\\\" }\\\" % x.dump }\").call(eval(\"->(x) { \\\"->(y) { eval(eval(%1$s).call(%1$s)).call(y) }\\\" % x.dump }\").call(x)) }").call("->(x) { eval(\"->(x) { \\\"->(y) { puts %s + \\\\\\\".call(nil)\\\\\\\" }\\\" % x.dump }\").call(eval(\"->(x) { \\\"->(y) { eval(eval(%1$s).call(%1$s)).call(y) }\\\" % x.dump }\").call(x)) }")).call(y) }.call(nil)
$ ruby quine.rb
->(y) { eval(eval("->(x) { eval(\"->(x) { \\\"->(y) { puts %s + \\\\\\\".call(nil)\\\\\\\" }\\\" % x.dump }\").call(eval(\"->(x) { \\\"->(y) { eval(eval(%1$s).call(%1$s)).call(y) }\\\" % x.dump }\").call(x)) }").call("->(x) { eval(\"->(x) { \\\"->(y) { puts %s + \\\\\\\".call(nil)\\\\\\\" }\\\" % x.dump }\").call(eval(\"->(x) { \\\"->(y) { eval(eval(%1$s).call(%1$s)).call(y) }\\\" % x.dump }\").call(x)) }")).call(y) }.call(nil)

*1:C 言語みたいに eval がない言語をイメージしている人は、自力で C インタプリタを書いてください。チューリング完全な言語なら eval が書けるはず。

*2:それぞれに同じ文字列を食わせた時、片方が文字列 s を出力するならもう片方も s を出力する。片方が無限ループに陥るならもう片方もなる。なお、同じ振る舞いをすればよくて、字面上一致している必要はないです。

*3:正確には「クリーネの再帰定理」じゃなくて「ロジャーズの不動点定理」らしい。

*4:本当はこの定義だとまずい。E(h, e) が停止しないので、p が定義できない。正確に議論するならイータ展開して、「入力文字列 x に対し、『入力文字列 y に対し、E(E(x, x), y) の結果を出力するプログラム』を出力するプログラム」と定義すべき。

*5:このプログラムは入力文字列を受け取りますが、使わずに捨てます。

2014-01-05

[][] The 22nd IOCCC: Most tweetable 1-liner のエントリ

http://www.ioccc.org/2013/endoh3/endoh3.c

char a;float b,c;main(d){for(;d>2e3*c?c=1,scanf(" %c%f",&a,&c),d=55-a%32*9/5,b=d>9,d=d%13-a/32*12:1;a=2)++d<24?b*=89/84.:putchar(a=b*d);}

ツイート可能 (137B) なワンライナー

解説

ABC 記譜法 (のサブセット) のサウンドシンセサイザーです。ABC 記譜法とは、外国で使われる MML みたいなものです。

$ gcc -o endoh3 endoh3.c
$ echo "CDEFGABc" | ./endoh3 > /dev/dsp

とやるとドレミファソラシドが流れます。/dev/dsp が使えない人は padsp とか sox とか使って下さい。面倒な人のための動画。(音量注意)

D

137 バイトのコードの中に ABC 記譜法のパースと波形の生成が詰まってます。以下、実装について、概要だけご紹介。ドキュメントの Spoiler で結構詳細に説明しています。


パース

まず scanf で 1 音符分の音階と長さを持ってきます。

scanf(" %c%f", &a, &c)

これで得られた音階の ASCII コードに以下の謎の変換をかまします。*1

(a % 32 + 5) * 9 / 5 % 13 + a / 32 * 12 - 22

これによって音符を半音ずつ並べた数字 (MIDI ノート番号みたいなの) が得られます。


周波数への変換

この数字を周波数に直すには、pow(2, n/12) みたいな変換をします。が、pow は使えない *2 ので、pow(2, 1/12) を n 回掛け算します。この定数は 89/84. で近似できます。*3


波形の生成

あとは以下で波形を出力。

for(c = 0; c < len; c++) putchar(a = n * D);

n * D は単調増加ですが、char 型の変数に代入することで mod 256 の値になります *4 。これによってめでたく倍音豊かなのこぎり波が出力されます。


で、後はゴルフ。とりあえず 140B を切るまでは頑張りましたが、プロゴルファーならどのくらい削れるもんなんでしょうねえ。

狙いと戦略

これはわりと自信のある方でした。ワンライナーIOCCC の定番枠なので。

2 オクターブに収まり、(なるべく) 黒鍵を使わず、著作権フリーであるサンプル曲を探すのが大変でした。Happy Birthday to You はアメリカではまだ著作権存続中 (?) で去年も裁判起きたらしい、とか、長い休止符は例の曲著作権に抵触する可能性がある、とか。

[][] The 22nd IOCCC: Most solid のエントリ

http://www.ioccc.org/2013/endoh4/endoh4.c

int
**F,**
V,M, N,i;
#ifndef/**/S
#define S 70,23
#endif/* 000-2E5*/
#define/* 2E5-2E5,2E5
*/_POSIX_C_SOURCE 199309
#include/* 2E5XXX*/<time.h>
/* 2E5-2E5X*/#include<stdio.h>
#include<stdlib.h>/* -2E5-2E5XX*/
struct timespec R={0,1E6};int j,k,m,
#define U/* -2E5X*/rand()*2./RAND_MAX-1
#define/* 2E5*/O(p,q,i)(P[p*3+i]-P[q*3+i])
/* IOCCC2013 IOCCC2013*/#define B(p,q,\
r)(O(q,p,0)*O(r,p,1)-O(q,p,1)*O(r,p,     0))
#define A(t,n)( t*)malloc( sizeof     (t)*n)
#define E(p,q,r,s)B(p,q,r)*O(s     ,p,2)+B(\
p,r,s)*O(q,p,2)+B(p,s,q)*O(     /*XX*/r,p,2)
#define D(e,f)(c-a)?s=a,     a=e,e=s,s=f,f=\
d,d=s:0;u=a+.5;m=u+1;     T[01]=91;T[2]=060;
#define C (Q[u]-X)     *a+(Q[u+1]-Y)*b+(Q[u\
+2]-Z)*c,g=e*c-     f*b,h=f*a-d*c,f=c,c=d*b\
-e*a,d=a,a=g     ,e=b,b=h,P[k]=W/2-q/s/p*3*\
W,P[k+1]=     H/2+r/s/p*H/2,T[3]=0x48,*T=033
n,u,v,     w,t,W,H;double*P,*Q,I,J,K,L,x,y,z
,X,     Y,Z,a,b,c,d,e,f,g,h,p,q,r,s ;void o(
     double x){for(p=q=i=0,s=r=1;i<99;s=(s+x
  /s)/2)i%2?q+=r,r=-r:(p+=r),r*=3.14*x/++i;}
     int G(int p,int q,int s,int g,int f){i\
nt*     v=A(int,N),*a,*b,h=-1,r=h;for(F[f]=V
[f]=v;     ++h<f;)if(V[h][p]==q){if(s+1&&E(p
,q,V[h][q     ],s)<1E-4){for(a=F[g],b=F[h];N
>++r;v[r]=q+     1?a[q]-r?q:b[p]-r?p:-1:p)p=
a[r],q=b[r];for     (r=0;r<f;r++)F[r]==a||F[
r]==b?F[r]=v:0;};;     return f;}for(h=0;h<N
;v[h++]=-1)r=h-p&&h-q     &&(r<0||E(p,q,r,h)
<0)?h:r;v[v[v[p]=q]=r]=p     ;return G(r,q,p
,f,G(p,r,q,f,G(p,q,s,g,f+1)     ));}char *T;
int main(void) {H=(W=S)*2;T=A(     char,(H*W
+4));for(srand(t=(int)time(0));i=     scanf(
"%lf,",P=(Q=(double*)realloc(Q,(N+1)     *s\
izeof(double)))+N),i>=0;)i?c+=*P**P,1<N
++%3?o(c),b=b<s?s:b,c=0:0:scanf("%*s");for
(P=A(double,N*2);j<N;)Q[j++]/=b;o(U);I=
p/1E3;J=q/1E3;K=U;L=U;N/=3;F=A(int*,     4*N
);V=F+2*N;for(;u==v;){for(j=u=m=n     =0;j<3
*N;j++)P[j]=Q[j]+(U)/1E5;for(;     m<N;m++)u
=P[u*3]>P[m*3]?m:u;for(v=!u     ;n<N;n++)v=B
(u,v,n)>0?n:v;}for(puts(     "\x1b[2J"),M=G(
u,v,-1,-1,0);;K+=I+0,     L+=J){for(i=4;i<W*
H/2+3;T[++i]=j=0)T     [i]=i%W-3?32:10;for(;
j<M;j++){for(n=     k=0;F[j][m=n]<0;)n++;for
(;u=F[j][m]*     3,o(K=K<-1?K+2:K>1?K-2:K),c
=z=9*p,b=     9*q,o(L=L<-1?L+2:L>1?L-2:L),a=
x=b*q,     y=b*=p,d=x-X,e=y-Y,f=z-Z,o(d*d+e*
e+f     *f),p=C,q=C,r=C,k+=2,m=F[j][m],m-n;)
     ;for(p=n=0;n<k;n+=2)p+=P[n]*(P[(n+3)%k]
  -P[(n+k-1)%k]);for(q=time(0)<t+3;(q||p>=0)
     &&n;){a=P[n%k];b=P[n%k+1];c=P[n-=2];d=P
        [n+1];e=d-b;i=e*e>(c-a)*D(b,c)0>D(c,
           b)for(;c-a&&u<c+.5;0<=w&&w<W-1&&0
              <=m&&m<H?v=m/2*W+w+4,T[v]="',"
                 ";;;,;'"[T[v]%8^m%2]:0)m=v=
                    (d-b)*(u-a)/(c-a)+b+0.5,
                       w=i?m=u++,v:u++,u=u<c
                          &&q?c+0.5:u;}}puts
                             (T);nanosleep(&
                                R,0);X=x;Y=y
                                   ;Z=z;}}/*
                                      IOCCC*
                                         \*/

使い方

動画でどうぞ。

D

解説

端末上で動く凸多面体ビューアです。

1. 3 次元の頂点データを読み込む

2. 凸包を計算する

3. 端末上にレンダリングする

という単純なものです。

凸包計算は 3 次元 gift-wrapping アルゴリズムでやってます。ほぼ同一平面上の面を 1 つの面にマージすることで、四角形以上の面をきちんとサポートしてます (三角形 2 つとかで描かない) 。これのおかげでサッカーボールがサッカーボールらしくレンダリングされます。点が重複しているとか、同一平面上に点があるとか、コーナーケースにもまあまあ堅牢に動作するはずです。*5

3D レンダリングとかは普通です。ちょっとした工夫として、ドットを書くのに

T[v]="',;;;,;'"[T[v]%8^m%2]

という、謎の代入文を使ってます。あと、カメラを球面螺旋の軌道に沿って動かしています。

さらに以下のような小ネタ。

  • 意外にも math.h を使わない (cos と sqrt を自力計算しているだけだけど)
  • コード形状は正四面体の展開図 (入力に使うと正四面体が出てくる)
  • 画面サイズはマクロで調整可能
  • いろんな多面体のデータをつけてみた

狙いと戦略

最近の IOCCC は難しげなアルゴリズムが通りやすい→ロバストな凸包計算って難しいよね、という着想から作ったのですが、あまり変態的な方向に発想が広がらず、小さくまとまってしまいました。これが評価されたっぽいのは正直予想外でした。形状以外、いたって普通の C コードなので。まあ 3D のインパクトなのかなあ。

*1:この式は試行錯誤+総当たりで見つけました。

*2ワンライナーでは #include <math.h> ができない。

*3:この近似値は Stern-Brocot tree を使って見つけました。

*4:厳密にはこれは未定義挙動ですが、まあ大概の環境でこうなるんじゃないですかと……。詳しくはドキュメントを参照。

*5:専門用語で random perturbation という手法でコーナーケースをつぶしています。具体的には点を乱数でずらしているだけ。

2014-01-04

[][] The 22nd IOCCC の結果が公開されました

C 言語のプログラムの汚さで競い合うプログラミングコンテストThe 22nd International Obfuscated C Code Contest の今年の結果が公開されました。

http://www.ioccc.org/years.html#2013

相変わらずの変態ぞろいですのでぜひご覧ください。既報の通り、ぼくは以下の 4 つの賞を貰いました。

それぞれ順次紹介していきたいと思います。

[][] The 22nd IOCCC: Most lazy SKIer のエントリ

ref: http://ioccc.org/2013/endoh1.c

#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

使い方

単体でもコンパイル・実行できるんですが、

$ gcc -o endoh1 endoh1.c
$ ./endoh1
@@@@@
@
@@@@@
    @
@@@@@

@   @
@  @
@@@
@  @
@   @

@@@@@  @@@   @@@   @@@   @@@
  @   @   @ @   @ @   @ @   @
  @   @   @ @     @     @
  @   @   @ @   @ @   @ @   @
@@@@@  @@@   @@@   @@@   @@@

これは本題ではありません。


このプログラムは、C コンパイラに Lazy K のコードを食わせていじめるためのライブラリです。これがあれば、C コンパイラしかない状況で Lazy K を楽しむことができます。*1

Lazy K ってのは SKI コンビネータ遅延評価で云々という言語なんですが*2、要するに関数 3 つだけ (S と K と I) の難解言語です。見た目はこんな感じ。

K(S(S I(K(S(K(S I I(S(S(K S)K)I))) ... ))))

これの最初と最後に #include <endoh1.c> をくっつける。

#include <endoh1.c>

K(S(S I(K(S(K(S I I(S(S(K S)K)I))) ... ))))

#include <endoh1.c>

これだけで valid な C プログラムになります。この通り。

$ gcc -o hello -xc hello.lazy
$ ./hello
Hello, IOCCC!

変な行入れたら Lazy K じゃなくなるじゃないか!という Lazy K ファンの方もご安心を。Lazy K において # は行コメントですので、そのまま実行できます。

$ lazy hello.lazy
Hello, IOCCC!

つまり、Lazy K と C の polyglot (と言えなくもない) です。

解説

#define S (s)
#define K (k)
#define I (i)

マクロ定義することで

S (K I)

(s) ((k) (i))

となり、冗長な括弧をとると

s(k(i))

あれっこれ普通の C じゃん、というのが肝です。ここから苦労した点はいっぱいあって

結果、C コンパイラいじめの塊になりました。詳細はドキュメントを見てください。

なお、処理系部分は項書き換えっぽいアプローチで実装してます (コードの形状が示す通り) 。おかげでかなり小さくなっていると思う。

狙いと戦略

これは一番頑張った作品で、ネタにもコンパイラいじめ度にも自信ありました。が、掲載順位から察するに、それほど評価されなかった印象です。地味だからですかね。去年の金賞も地味なんだけどなあ。残念。

[][] The 22nd IOCCC: Most recyclable のエントリ

              /*@@@sssss8]][[[[a#@@sss0['w}8|v}a<{av}a@{av}j>~{v}j8|c[sa?|{8[|#~}
          [j#@ra>~}sa!{>}|#r0l}sao8}[a'f8|r'8[j?x[?@<[j?@[j?@[s?>|;[[[j!>b'8'a@<cb@>?
        c$kg_@<b#0pf<#keab{_b0|c0#d#0#|'o{i<!8dr,f_{#rg{baiderh{er0}|'{0{ic.df?'o|j{lim
       0'{i?#c0b|c#kg!}r!8lp1g!|i_ar<[#0g|h_}ieg>|_ah|sr<|i[[[}s#f@}[{@u~~~r@[|#|{ssss{a
      }|0~{?}|<{?}|qj?}s@[_}j0]][[[[a_@@@sssss<[[?>=sln5+a[so#,g-0aw;#*a>*abwa.*+da9=n?<6
      -'7%71>e_?>a[j;e=;scdet?>shd??a;5&6:=[ch@aw[sf;[#<[[j>k7__?>>d>==n'6+7*abcdnh3a_jhw
     b6;73;b#<ww<7bcw7d+;&i=cn?c>=#d5;8w3;nawn#<;;77__ra?8hi1abcww#>==<[;k7[wn7[=,>ab[a@s[
     ='b,.[8.?>>fdjn(_2$a8c8[[j_8.=B6+b8]]]]]]]]]j1;7_sj<[[af;7sjd][j_<7!=a>d7_j8d.ab[hybm
     ?>=;ei7aws1d!ebn                                                       _,?>0aka[#;5+7
     !?ac;7_wa7{;a3_                                                        bjcna>a<;bs8;7
     j-=cabh?97_sj['                                                  -5*j[!;5+a7[1wb[!wBb7w?0wb
     _?an+&e_|j'4a<7                                                  0v;7d.kd8wa?.=:a-wwm=:;[e5
     *-=fwn7rab[c.j#                                                    eaw#c>>>bml;mtdekssae
     zqtd[39<u_char*                                                      p=$,w[13997],*h=w,
     *q,*r_****_;#in                                                        clude_*ioccc*2
     013*_<stdio.h>_                                                         *--2013-ioc
     cc-2013-ioccc-2        013--                                             *_#define
                           @n(d);c                                              ((d)>
                            >8);c                                                 (
            d
          );*B=             32;B[   y=1]=22 .627400;       B[2]=16;_*-i       occc-2013 -ioccc
        -2013-io           ccc-201  *_int@a,b,d,e,s,t    ,g,z,y;double@f,    B[3],i,j,k,l;void
       @m(int@z){f         or(j=k=  l=y=1;y<99;y+=2+0)  l*=z*z*    .038553  ,k*=-y*(y+1),j+=l_
     k;i*=j;}int@c(        int@d){  return@    putchar (d)_255;    }intmain (){for(    ;*p;p++
    )*p<33?0:(*h++=*p      -32);q=  h;for(p     =w;p<w +823;p++)for(d=*p-56 ,e=-1+     0;++e<(
  d<00?5:d<6?d>4?160:30    :d>35?2  7<<(d-3    6):d_9* 6);q++)*q=d<0?*p>>e& 1:d<6||    q[d>35?
-108:d%9*-12-12];for(q=h   ;g++<61  56;q++)*  q?*q=*p-  4?e=*p+             +,e-32?e:0:r&&*r?g
%108<2?2:*r++:(r=r?p++:w,  2):0;n(  g=8*8187)n(g+8)n(1  6)n(19014)n(18758)   ;for(;s<10;s++)c(
     s<3?s:0)n(g+3)n       (67)for  (;t<65;)c(t++>0)      n(g-24)n(11)c(8      )n(612)n(656)n(
     257)n(4352)n(g+       0-20)n(  5*42);; for(;y          ++<207;)c(      y<3        1?y<19?
     y>6:30-y:y<47?y    <32||y>36?  16:0:y<                                 48?2:y%1  6*16+13-
     y_16)n(64*960)n   (g+5)n(4)n(  1)n(g+2                                 )n(8)n(257)n(0)n(
     2*8064)for(;b<4    04096;b++   ){e=32<                                   a?63-a:a;for(f
     =d=t=s=0;e>t;)e
     -=++t;e=t%2?e:t                                                        -e;;;for(d=a>3
     1?e=7-e,14-t-e:                                                        t-e;s<64;t=f-=
     i*B[!d+!e])z=b_                                                        64%82*8+s_8-4,
     y=b_5248*8+s%8+7                                                      ,i=z<0||z>647||
     y%11>9?1:q[h[z_6+y_11*108]*60+y%11*6+z%6]*2-1,m(s_8*2*d+d),m(s++%8*2*e+e);s=2+t*t;;fo
     r(d=2;s>3;s_=4)d*=2;;s=8<<(a?12:9);s-=d*2<<!!a*4;s|=t>0?t:t-1+d;c(s_256)?c(0):0;c(s)?
     c(0):0;if(a++>62){n(g-8+b_64%8)a=0;}}n(g+1)return@0+0;}*/ /*IOCCC*/#include<stdio.h>
      char*p,w[13997],*h=w,*q,*r;int d,e,g;int main(){for(;e<3583;e++>15&&e<3582&&d>32?*h
       ++=d-95?d:47:0)d=getchar();q=h;for(p=w;p<w+823;p++)for(d=*p-88,e=-1;++e<(d<0?5:d<
        6?d>4?160:30:d>35?27<<(d-36):d/9*6);q++)*q=d<0?*p>>e&1:d<6||q[d>35?-108:d%9*-12
          -12];for(q=h+108;g++<5995;)putchar(g%109<1?10:*q++?*p-36?e=*p++,e-64?e:32:r
              /*IOCCC2013*/&&*r?g%109%108<2?34:*r++:(r=r?p++:w,34):32);return 0;}

使い方

まず普通にコンパイルし、以下のように実行します。

$ gcc -o endoh2 endoh2.c
$ ./endoh2 < endoh2.c > jpeg.c

すると本番のプログラムが出てきます。

char*p="@@@sssss8]][[[[a#@@sss0['w}8|v}a<{av}a@{av}j>~{v}j8|c[sa?|{8[|#~}[j#@ra>~}sa!{>}|#r0l}sao8}[a'f8|r'"
"8[j?x[?@<[j?@[j?@[s?>|;[[[j!>b'8'a@<cb@>?c$kg/@<b#0pf<#keab{/b0|c0#d#0#|'o{i<!8dr,f/{#rg{baiderh{er0}|'{0{"
"ic.df?'o|j{lim0'{i?#c0b|c#kg!}r!8lp1g!|i/ar<[#0g|h/}ieg>|/ah|sr<|i[[[}s#f@}[{@u~~~r@[|#|{ssss{a}|0~{?}|<{?"
"}|qj?}s@[/}j0]][[[[a/@@@sssss<[[?>=sln5+a[so#,g-0aw;#*a>*abwa.*+da9=n?<6-'7%71>e/?>a[j;e=;scdet?>shd??a;5&"
"6:=[ch@aw[sf;[#<[                                                                       [j>k7//?>>d>==n'6+"
"7*abcdnh3a/jhw                                                                             b6;73;b#<ww<7bc"
"w7d+;&i=cn?c                                                                                >=#d5;8w3;nawn"
"#<;;77//ra?                                                                                   8hi1abcww#>="
"=<[;k7[wn7                                                                                     [=,>ab[a@s["
"='b,.[8.?>                                                                                     >fdjn(/2$a8"
"c8[[j/8.=                                                                                       B6+b8]]]]]"
"]]]]j1;7/              sj<[[af;7sjd][j/<7!=a>d7/j8d.ab[hybm?>=;ei7aws1d!ebn/,?>0ak              a[#;5+7!?a"
"c;7/wa7{;             a3/bjcna>a<;bs8;7j-=cabh?97/sj['-5*j[!;5+a7[1wb[!wBb7w?0wb/?a             n+&e/|j'4a"
"<70v;7d.k             d8wa?.=:a-wwm=:;[e5*-=fwn7rab[c.j#eaw#c>>>bml;mtdekssaezqtd[3             9<u/char*p"
"=$,w[1399             7],*h=w,*q,*r/****/;#include/*ioccc*2013*/<stdio.h>/*-                           -20"
"13-ioccc-             2013-ioccc-2013--*/#define@n(d);c((d)>>8);c(d);*B=32;B                           [y="
"1]=22.627             400;B[2]=16;/*-ioccc-2013-ioccc-2013-ioccc-201*/int@a,b,                       d,e,s"
",t,g,z,y;             double@f,B[3],i,j,k,l;void@m(int@z){for(j=k=l=y=1;y<99;y+=                   2+0)l*="
"z*z*.0385             53,k*=-y*(y+1),j+=l/k;i*=j;}int@c(int@d){return@putchar(d)/2               55;}int@m"
"ain(){;;f             or(;*p;p++)*p<33?0:(*h++=*p-32);q=h;for(p=w;p<w+823;p++)for(d=           *p-56,e=-1;"
"++e<(d<0?             5:d<6?d>4     ?160:30:d>35?27<<(d-36):d/9*6);q++)*q=d<0?*p>>e&1         :d<6||q[d>35"
"?-108:d%9*-12-12];for(q=h;g++<       6156;q++)*q?*q=*p-4?e=*p++,e-32?e:0:r&&*r?g%108<2?     2:*r++:(r=r?p+"
"+:w,2):0;n(g=8*8187)n(g+8)n(16)     n(19014)n(18758);for(;s<10;s++)c(s<3?s:0)n(g+3)n(67)f or(;t<65;)c(t++>"
"0)n(g-24)n(11)c (8)n(612)n(656)n(257)n(4352)n(g+0-20)n(5*42);;for(;y++<207;)c(y<31?y<19?y>6:30-y:y<47?y<32"
"||y>36?16:0:y     <48?2:y%16*16     +13-y       /       16)n(64*9            60)n(g+5)        n      (4)n("
"1)n(g+2)n(8        )n(257)n(0)       n(2*                 8064)                for(;                 b<404"
"096;b++){e           =32<a?63-       a:a;                  for       (f=d       =t=                  s=0;e"
">t;e-=++              t);e=t%2       ?e:t       -e;;       ;f        or(d        =a       >31?       e=7-e"
",14-t-e                 :t-e;s       <64;       t=f-=      i*                    B[      !d+!e       ])z=b"
"/64%8                     2*8+       s/8-       4,y=b      /5                    24      8*8+s       %8+7,"
"i=z                        <0|       |z>6       47||       y%1       1>9?1:q[h[z/6+                  y/11*"
"108                         ]*       60+y                  %11                  *6+z                 %6]*2"
"-1,m(s/8*             2*d+d),m       (s++                 %8*2*e               +e);s=2               +t*t;"
";for(d=2;             s>3;s/=4       )d*=       2       ;;s=8<<(a?           12:9);   s-=d*2<<       !!a*4"
";s|=t>0?t             :t-1+          d;c(       s/256)?c(0):0;c(s)?c(0):0;if(a++>62       ){n        (g-8+"
"b/64%8)a=             0;}}           n(g+       1)return@0+0;}",w[13997],*h=w,*q,*r                 /****/;
#include/*             ioccc         *2013       */<stdio.h>/*--2013-ioccc-2013-ioccc-              2013--*/
#define n(             d);c((d)>>8);c(d);*B=32;B[y=1]=22.627400;B[2]=16;/*-ioccc-2013-ioccc-2013-ioccc-201*/
int a,b,d,             e,s,t,g,z,y;double f,B[3],i,j,k,l;void m(int z){for(j=k=l=y=1              ;y<99;y+=2
+0)l*=z*z*             .038553,k*=-y*(y+1),j+=l/k;i*=j;}int c(int d){return putchar(             d)/255;}int
 main(){;;             for(;*p;p++)*p<33?0:(*h++=*p-32);q=h;for(p=w;p<w+823;p++)for(             d=*p-56,e=-
1;++e<(d<0             ?5:d<6?d>4?160:30:d>35?27<<(d-36):d/9*6);q++)*q=d<0?*p>>e&1:d             <6||q[d>35?
-108:d%9*-             12-12];for(q=h;g++<6156;q++)*q?*q=*p-4?e=*p++,e-32?e:0:r&&*r?             g%108<2?2:*
r++:(r=r?p              ++:w,2):0;n(g=8*8187)n(g+8)n(16)n(19014)n(18758);for(;s<10;              s++)c(s<3?s
:0)n(g+3)n                                                                                       (67)for(;t<
65;)c(t++>0                                                                                     )n(g-24)n(11
)c(8)n(612)                                                                                     n(656)n(257)
n(4352)n(g+0                                                                                   -20)n(5*42);;
for(;y++<207;                                                                                 )c(y<31?y<19?y
>6:30-y:y<47?y<                                                                             32||y>36?16:0:y<
48?2:y%16*16+13-y/                                                                       16)n(64*960)n(g+5)n
(4)n(1)n(g+2)n(8)n(257)n(0)n(2*8064)for(;b<404096;b++){e=32<a?63-a:a;for(f=d=t=s=0;e>t;e-=++t);e=t%2?e:t-e;;
;for(d=a>31?e=7-e,14-t-e:t-e;s<64;t=f-=i*B[!d+!e])z=b/64%82*8+s/8-4,y=b/5248*8+s%8+7,i=z<0||z>647||y%11>9?1:
q[h[z/6+y/11*108]*60+y%11*6+z%6]*2-1,m(s/8*2*d+d),m(s++%8*2*e+e);s=2+t*t;;for(d=2;s>3;s/=4)d*=2;;s=8<<(a?12:
9);s-=d*2<<!!a*4;s|=t>0?t:t-1+d;c(s/256)?c(0):0;c(s)?c(0):0;if(a++>62){n(g-8+b/64%8)a=0;}}n(g+1)return 0+0;}

これをまた実行すると

$ gcc -o jpeg jpeg.c
$ ./jpeg > jpeg.jpg

以下のような jpg 画像が出てきます。

それだけ。

解説

qng 画像qif 画像と同じネタです。すみません。

一応、現時点で世界最小の jpeg エンコーダじゃないかと思います。jpeg ってヘッダに色々書かないと行けないし、ジグザグスキャンとか離散コサイン変換とかハフマンエンコーディングとかやることが多くて大変なんです。

それでもサイズ制限を完全にオーバーしたので、チート気味に回避してます。というのは、今回初めてサイズチェッカが審査員から提供されたのですが、それが微妙にバグってた (ルール上はコメント含めて 2KB なのに、チェッカはコメント含めず 2KB になってた) ので、本番プログラムをコメントに埋めて、最初のプログラムはコメントをデコードする感じ。(ちなみに、IOCCC ではチートが推奨されてます)

あと、jpeg のハフマンエンコーディングチートしていて*3、生成される jpeg ファイルは同等な PBM ファイルの 16.4 倍もでかい。(審査員調べ)

一応、正統派の圧縮もがんばっていて、たとえばフォントと形状データには LZ77 風の圧縮をかけてます。

狙いと戦略

1 つくらい Quine ネタをやるかー、と思って作りました。しかし特にひねりがなく、ネタのわりに超巨大。

記念受験のつもりで送ったら意外にも通りましたが、正直あんまし満足な出来じゃないです。次回はもうちょっと頑張りたい。

*1:普通に C で Lazy K インタプリタを書けばいいって?あーあー聞こえない

*2:詳しくは公式サイトを見てください。

*3:ビット処理したくなかったので、コードがバイトにアラインするように巧妙に作ったハフマンテーブルを定義してる。圧縮効果は全くない。

2014-01-01

[] Golgi: ブラウザ上で動く「細胞」風ライフゲームシミュレータ

あけましておめでとうございます。日本のプログラマには古来より「正月はフラクタル」という習わしがあります。正月はフラクタルに触れて心穏やかに過ごそうというものです。

という謳い文句で 2 年前、なめらかライフゲームというのを公開したのですが、今回これをブラウザ上でリアルタイムに体験できる Javascript アプリ Golgi を作ってみました。

http://mame.github.io/golgi/

デフォルトは普通のライフゲームですが、

WebGL をサポートしているブラウザで、画面右下の CELL-VIEW をチェックすると、「細胞」風表示になります。

HashLife を実装しているので、わりと高速に動作します。R ペントミノみたいにパターン化するやつなら 1000000 世代とかでも余裕です。

デモ動画。

D

デモは Chrome ですが、新しめの IEFirefoxOpera でも動くと思います。AndroidChrome でもなんとか動きます。

D

Ring of fire細胞風表示がかなりいい感じです。虫とか嫌いな人はきっと嫌がる。

実際のところ、細胞風表示はいろいろバグってる (2 倍速以上にしたり、パターンを切り替えたりした時に表示がぶっ壊れることがある) んですが、直す気力がなくなってきたので公開。パッチください。