Back to the Future Award

バック・トゥ・ザ・フューチャー賞

Line wrap

Highlight


  #include   /*recall-the\    /-good--old-\    /IOCCC-days!\    */<unistd.h>
   typedef  unsigned/*int*/  short U;U(main)  [32768],n,r[8];  __attribute__((
  # define  R(x)       A(r[  7-(n       >>x&  7)],       (n>>  x>>3       )%8)
  #define   C(x)       (U*)  ((/*             |IO|             -dpd
  */char*)  main       +(x)  )/*|             |CC|             ll*/
  # define  A(v,       i)(i  ?i<2             ?C(v             ):i\
  -4?v+=2,  C(i-       6?v-  2:v+       *C(v  -2))       :C(v  -=2)       :&v)
  /*lian*/  constructor))U(  x)(){for(;;*r+=  2,*r+=!n?_exit(  write(2,"Illeg"
  "al ins"   "truction ;-"    "(\n",24)),0:     n>>8==001?(      signed char




                 )n*2   :548==n>>    6&&usleep     /**/(10
                 )+n%  64==   4?0*  write  (r[7   /**/],C(
                 *C(*  r)),   *C(*  r+2)   )+4:  /**/ n>>9
                 ==63   &&--r[7-n/   64%8]?n%+  /**/  64*-
                 2:0,         n>>6  ==47   ?*R( 0):n>>12==1?
                 *R(0  )=*R   (+6)  :n>>  12==+       14?*
                 R(0)   -=*R(2*3)    :0)n=*C(*        r);}

引用元：https://www.ioccc.org/2015/endoh3/prog.c

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

動作

[[1984/mullender]]を動かすことに特化したPDP-11エミュレータ。

単体で実行してもIllegal instruction ;-(というだけ。

$ gcc -o prog prog.c

$ ./prog
Illegal instruction ;-(

次のように、mullender.cと一緒にコンパイルすると動く。

$ clang -o prog prog.c mullender.c

$ ./prog
          :-)

[[1984/mullender]]は顔文字が画面右端に向かって移動していくアニメーション作品だったことが確認できる。

解説

[[1984/mullender]]はmainをshortの配列として機械語の列を直接書いた、伝説のIOCCC作品。必然的にPDP-11という当時の計算機に特化している作品だった。そしてこのプログラムは、__attribute__((constructor))というGCC拡張の関数属性を使って、main()関数より前に呼ばれる関数を定義し、mainをPDP-11の機械語の配列として解釈実行するエミュレータもどきとなっている。 mullender.cを動かすことに特化しているので、mullender.cが使用している命令だけをサポートしている。アドレッシングも同様に必要最小限。

BR: 分岐
MOV: レジスタへの代入
SOB: 1引いて非ゼロならば分岐する
SUB: 引き算
TRAP 4: writeのシステムコール
TST: 値のテスト（ただしフラグはサポートされていない）

コード形状は”IOCCC 1984”。遊びとしては、pdp-11を逆さ文字にした”ll-dpd”をコメントに含めたり、”recall the good old IOCCC days!”（古き良きIOCCCの日々を思い出せ！）というメッセージを入れたりしている。

IOCCC 1984の作品をIOCCC 2015で引っ張り出すというのは、ほぼ『バック・トゥ・ザ・フューチャー』の時系列と同じ（1985年から2015年にタイムトラベルするシーンがある）なので、この賞名となった。 hint.textで言及されるMartyとDocは同作品の登場人物で、Deloreanは同作品に出てくるタイムマシンの名前。

hint.textの末尾に巨大なshort main[]={5568,1,...};が付記されている。これをmullender.cと同様に実行すると、tar.gzが出力される（tar.gzにはタイムスタンプが記録できるので、IOCCC 1984の締切であるApr 11 1984に合わせてある）。

$ gcc -o hint prog.c hint.c

$ ./hint > fun.tar.gz

$ file fun.tar.gz
fun.tar.gz: gzip compressed data, was "fun.tar", last modified: Wed Apr 11 00:00:00 1984, max compression, from Unix, original size modulo 2^32 20480

これを展開すると、おまけのデータが出てくる。

$ tar tf fun.tar.gz
README.markdown
pi.c
koch.c
quine.c
bf2pdp11.c
fib.b
hello.b
fizzbuzz.b

README.markdownには、この作品の背景が書かれている。もともとの目的は、IOCCCの1番目のルールである”Your entry must be a complete program.”（あなたの作品は完全なプログラムでなければならない）に挑戦することだった（mullender.cがないと無意味なプログラムなので完全でない）が、予想に反してこの極小のエミュレータはチューリング完全だとわかったとのこと。命令SOB（1を引いて、その結果がゼロでないなら分岐する）が、単体でチューリング完全になる強力な命令だった。デモとして、いくつかのプログラムが添付されている。

pi.cは、円周率を計算するプログラム。マクロのNを変えることで任意の桁が計算できる。

$ cat fun/pi.c
#ifndef N
#define N 50
#endif
short main[32768] = { 5568, N*8+1, 257, 281, 32258, 5570, 256, 5578, -2, 3042, 5578, 3, 5571, 256+N*2, 5579, -38, 5571, N+2, 5568, 1, 4744, 3026, 58824, -48, 35076, 1, 1, 32458, 0, 3024, 32256, 57409, 5570, 256, 4739, 3027, 4298, 5570, N*2, 3026, 32384, 257, 258, 32386, 291, 3042, 4099, 57604, 259, 32512, 32451, 257, 32452, 58818, -256, 4739, 3027, 32448, 257, 57601, 32450, 3025, 32320, 57604, 5571, 11, 57669, 259, 32578, 32322, 259, 32451, 32512, 502, 57994, 57674, 58818, 256, 57601, 471, 5570, N*2+2, 3026, 32384, 257, 258, 32386, 289, 3042, 3025, 32320, 57604, 4099, 3027, 32448, 57669, 259, 32578, 32322, 259, 32451, 32512, 501, 57665, 57413, 57409, 57665, 57665, 57665, 57665, 57665, 5571, 254+N*2, 57475, 58059, 57611, 3027, 57669, 58053, 57665, 473, 3040, 5575, 4 };

$ gcc -o pi fun/pi.c prog.c

$ ./pi
3.1415926535897932384626433832795028841971693993750
Illegal instruction ;-(

なお、正常終了する命令がないので、”Illegal instruction ;-(“で終了するのは仕様。

koch.cはコッホ曲線を描く。

$ cat fun/koch.c
#ifndef N
#define N 3
#endif
short main[32768] = { 262, -2, 2, 4, 2, -2, -4, 5575, 130, 3046, 3042, 4227, 32448, 275, 4558, 5575, 18, 58816, -5, 4558, 5575, 18, 58816, -2, 4558, 5575, 18, 58816, -5, 4558, 5575, 18, 282, 32468, 4099, 3027, 32448, 5572, 12, 271, 3044, 32453, 269, 3044, 32453, 266, 3044, 32453, 263, 3044, 32453, 260, 3044, 32453, 257, 32452, 58113, 5577, 42, 3026, 3030, 4995, 3027, 3027, 4295, 5573, 1, 4419, 5569, N, 260, 57604, 57668, 57605, 57605, 32325, 57344, 57664, 57664, 57347, 57347, 4297, 4293, 57349, 5572, 1024, 4353, 57665, 32258, 4418, 5580, 32, 3028, 32388, 32454, 57667, 57667, 5572, 2, 57548, 3028, 57548, 57538, 5572, 8, 57484, 3028, 57484, 5570, N*2+4, 5574, 1022, 4558, 5575, 18, 3024, 4558, 5575, 18, 3024, 4558, 5575, 18, 57539, 4801, 5568, 1, 4418, 3030, 5003, 35076, 0, 1, 32390, 5579, 10, 35076, 0, 1, 32334 };

$ gcc -o koch fun/koch.c prog.c

$ ./koch
                           *
                        * * * *
                     *   *   *   *
                  * * * *     * * * *
                   *               *
                  * *             * *
         *           *           *           *
      * * * *     * *             * *     * * * *
   *   *   *   *   *               *   *   *   *   *
* * * *     * * * *                 * * * *     * * * *
 *                                                   *
* *                                                 * *
   *                                               *
* *                                                 * *
 *                                                   *
* * * *                                         * * * *
   *   *                                       *   *
      * *                                     * *
         *                                   *
      * *                                     * *
   *   *                                       *   *
* * * *                                         * * * *
 *                                                   *
* *                                                 * *
   *                                               *
* *                                                 * *
 *                                                   *
* * * *     * * * *                 * * * *     * * * *
   *   *   *   *   *               *   *   *   *   *
      * * * *     * *             * *     * * * *
         *           *           *           *
                  * *             * *
                   *               *
                  * * * *     * * * *
                     *   *   *   *
                        * * * *
                           *
Illegal instruction ;-(

quine.cはQuine。

$ cat fun/quine.c
short main[32768] = { 5568, 1, -30460, 126, 22, -8127, 5572, 2, 5189, 4416, 5571, -32768, 259, 32578, 32512, 259, 32452, -8189, 4288, 5573, 158, -6720, -1, -7997, 5570, 11, 5581, 47, -6707, -1, 258, 32260, 259, 32387, 32448, 500, 3029, -8000, -6717, -1, 32468, 258, 5589, 45, 32515, 3044, 5568, 1, 6476, -30460, -2, 1, 4419, -6717, 153, 32456, 4162, -6718, 155, 32438, -30460, 148, 6, 26739, 29295, 8308, 24941, 28265, 13147, 14130, 14390, 8285, 8253, 8315, 13364, 32032, 2619, 32, 44 };

$ gcc -o quine fun/quine.c prog.c

$ ./quine
short main[32768] = { 5568, 1, -30460, 126, 22, -8127, 5572, 2, 5189, 4416, 5571, -32768, 259, 32578, 32512, 259, 32452, -8189, 4288, 5573, 158, -6720, -1, -7997, 5570, 11, 5581, 47, -6707, -1, 258, 32260, 259, 32387, 32448, 500, 3029, -8000, -6717, -1, 32468, 258, 5589, 45, 32515, 3044, 5568, 1, 6476, -30460, -2, 1, 4419, -6717, 153, 32456, 4162, -6718, 155, 32438, -30460, 148, 6, 26739, 29295, 8308, 24941, 28265, 13147, 14130, 14390, 8285, 8253, 8315, 13364, 32032, 2619, 32, 44 };
Illegal instruction ;-(

チューリング完全の証明として、brainfuckのコードからshort main[] = { ... };に変換するプログラムも添付されている。