自分のコードを出力するプログラム

「プログラミング言語なんて何でも同じ」っていうのはチューリングの意味では正しいのかもしれないけど。

数年前、スタンフォード大学の学生たちは、自分自身を印刷する最短のFORTRANプログラムを見つけようと張り切ったこともあります。（中略）こうしたことは時間の浪費ではないと私は考えます。さきほど引用したベンサムも、こうした遊びのもつ｢有用性｣を肯定しております。彼は次のように述べています：「それどころか、これ以上に明白な有用性は何もない。もし喜びの源となるのでなければ、有用性の特徴は何に基づいたらよいのであろうか。」—Donald E. Knuth, ACM Turing Award Lecture

アイディア

プログラムは2つの部分A,Bからなる。Aのコードを<A>、Bのコードを<B>とする。

  1. Aは<B>を記録する。
  2. BはAの記録から<B>を知り、
  3. <B>を出力するようなプログラム（つまりA）のコード（つまり<A>）を求め、
  4. <A><B>を出力する。

<A>と<B>を書き下す過程は循環しない。２つは同時にできあがる。

次の文に対してコピーを二つ書き、二つ目のコピーは、かぎ括弧で囲め。
『次の文に対してコピーを二つ書き、二つ目のコピーは、かぎ括弧で囲め。』

（参考：「Michael Sipser著, 渡辺治ほか訳. 計算理論の基礎. 共立出版, 2000」の第6章。原著は改訂されている）

実装

Mathematicaでの実装

> b=Hold[b=#;b[b]]&;b[b]
Hold[b = Hold[b = #1; b[b]] &; b[b]]
> ReleaseHold[%]
Hold[b = Hold[b = #1; b[b]] &; b[b]]

別の方法：

> f=#[Hold[#]]&;
> f[f]
Hold[Function[{x}, x[Hold[x]]]][Hold[Hold[Function[{x}, x[Hold[x]]]]]]
> ReleaseHold[f[f]]
Hold[Function[{x}, x[Hold[x]]]][Hold[Hold[Function[{x}, x[Hold[x]]]]]]

Lispでの実装

Common Lispの場合は次のような関数を定義しておくか、fsetの部分を書き換えること。

(defun fset (a b) (setf (symbol-function a) b))

Emacs Lispならそのまま動く。

> (progn
    (setq b (lambda (x) `(progn
                           (setq b ,x)
                           (fset 'b b)
                           (b b))))
    (fset 'b b)
    (b b))
(progn (setq b (lambda (x) (\` (progn (setq b (\, x)) (fset (quote b) b) (b b))))) (fset (quote b) b) (b b))

別の方法もある。（KAMIOさんの改良）

(progn
  (setq b '(list 'progn (list 'setq 'b (list 'quote b)) '(eval b)))
  (eval b))

`を使うともう少し簡単になる。

(progn (setq b '`(progn (setq b ',b) (eval b))) (eval b))

さらに別の方法：

> (setq f '(lambda (x) `(,x ',x)))
(LAMBDA (X) `(,X ',X))
> (fset 'f f)
(LAMBDA (X) `(,X ',X))
> (f 'x)
(X 'X)
> (f f)
((LAMBDA (X) `(,X ',X)) '(LAMBDA (X) `(,X ',X)))
> (eval (f f))
((LAMBDA (X) `(,X ',X)) '(LAMBDA (X) `(,X ',X)))

Perlでの実装（KAMIOさんによる）

$prog=q(
$prog="\$prog=q(".$prog.");";
print $prog;
print "\neval \$prog;\n";
);
eval $prog;

C++での実装

1-4行目が<A>、5行目が<B>である。赤字の部分が<A>の中に書かれた<B>である。

エスケープ文字の扱いに注意しなければならない。上のアイディアをコーディングするときに、エスケープ文字を含んだ文字列をそのまま出力しようとするとうまくいかない。命令中の文字列は表示したい文字列よりも長くなってしまうからである。関数chによって文字列中のエスケープ文字を普通の文字（コーディングに使える文字）に変換することでこの問題を回避できる（このコードの中で使っているエスケープ文字は\n(10),\"(34),\\(92)の3種類である）。

5行目を見ると、<A>の中の<B>を得るためにAの実行結果(string s)が利用されていることがわかる。

  1. #include<iostream>
  2. #include<string>
  3. using namespace std;string ch(string s){string p;char t;t=34;p+=t;for(unsigned int i=0;i<s.length();++i){if(s[i]==10){t=92;p+=t;t=110;p+=t;}else if(s[i]==34){t=92;p+=t;t=34;p+=t;}else if(s[i]==92){t=92;p+=t;p+=t;}else p+=s[i];}t=34;p+=t;return p;}
  4. int main(){string s="string p=\"#include<iostream>\\n#include<string>\\nusing namespace std;string ch(string s){string p;char t;t=34;p+=t;for(unsigned int i=0;i<s.length();++i){if(s[i]==10){t=92;p+=t;t=110;p+=t;}else if(s[i]==34){t=92;p+=t;t=34;p+=t;}else if(s[i]==92){t=92;p+=t;p+=t;}else p+=s[i];}t=34;p+=t;return p;}\\nint main(){string s=\";p+=ch(s);cout<<p<<\";\"<<\"\\n\"<<s;}\n";
  5. string p="#include<iostream>\n#include<string>\nusing namespace std;string ch(string s){string p;char t;t=34;p+=t;for(unsigned int i=0;i<s.length();++i){if(s[i]==10){t=92;p+=t;t=110;p+=t;}else if(s[i]==34){t=92;p+=t;t=34;p+=t;}else if(s[i]==92){t=92;p+=t;p+=t;}else p+=s[i];}t=34;p+=t;return p;}\nint main(){string s=";p+=ch(s);cout<<p<<";"<<"\n"<<s;}

このコードはindentを使っても読み易くはならない。

Vlad Taeerov & Rashit Fakheyevによる次の実装はみごと（標準的な記法ではないがこのままコンパイルできる。gcc3.4.2で確認済み）

main(a){printf(a,34,a="main(a){printf(a,34,a=%c%s%c,34);}",34);}

BASICでの実装

何のインスピレーションも得られないかもしれないけれど。

10 LIST

発展

UNIXの開発者であるKen Thompsonはこのアイディアを発展させ、次のようなCコンパイラ（のバイナリ。つまりソースには証拠が残らない）を実装したという

  1. ログインコマンドをコンパイルしようとすると、Thompsonのパスワードを受け付けるようなログインコマンドを生成する
  2. Cコンパイラをコンパイルしようとすると、そのコードに1,2の性質を追加してからコンパイルする

なんとこのことは1983年のチューリング賞受賞講演で暴露されたのである。

参考

YABUKI Taro