Life Goes On

まあまあだけど楽しんでる方です

世界一短い自己紹介

R 教授による S 大学での講義録。

はじめに

かねてから話していたとおり、今回はクワインについて講義する。
そもそもクワインとは何か?自分自身と同一の文字列を出力するプログラムのことである。自己言及のパラドックスに絡めて語られることもあるが、あくまでも、自身の「表現」つまり文字列を出力するだけなので、プログラマの諸君はそれほど混乱することもないだろう。
コンビネータ計算でクワインというと、以前に fumi 氏が記事を書いている。基本的な考え方はそこに書かれている通りである。
まず「関数の表現」を得るために、「関数」を何らかの方法でコード化(符号化)する。この「コード」を入力として「関数の表現」と「コードの表現」を出力できれば、関数(コード)= 関数の表現 ++ コードの表現 ≒ 関数(コード)の表現、となりクワインの完成である。

符号化その1(16161)

fumi 氏はチャーチ数のリストによって符号化を実現としている。たとえば、`sk という「関数」であれば、[0, 1, 2] = ``s``si`k`sk`k ... `kk という「コード」になる。この場合、入力した「コード」をもとに、「関数の表現」である [96, 115, 107] というチャーチ数のリストと、「コードの表現」である [96,96,115,96,96, ... ,96,107,107] というリストを構築できればよい。
この方針で fumi 氏は 25677 bytes のプログラムを得た。
さらに以下のような手法を適用することで、16000 bytes 程度まで短縮できることを確認している。

  • 「コード」を表すために 0 から 3 までのチャーチ数を利用しているが、以前に解説した 51b 数をさらに false = SK の関数と捉えることにより、それぞれ 0 = K, 1 = I, 2 = SS, 3 = S(K(SS))(SS) という関数に置き換える。
  • `, i, k, s を表す 96, 105, 107, 115 というチャーチ数を 96 + f 9 と捉え、それぞれ λx. 0, λx. x, λx. x+2, λx. x+(x+1) といった関数に置き換える。
  • 文字列を連結する (++) などの関数は、何度も使うので共通化する。

ここでボトルネックとなるのが、リストである。リストに要素を一つ追加するごとに cons x y = ``s``si`kx`ky として 10 文字程度のオーバーヘッドが発生してしまうため、リストを使うと「コード」のサイズが大きくなり、最終的には本体の「関数」の 10 倍以上の長さとなってしまうのだ。
そこでリストを使わずに「コード」を表現することを考える。

符号化その2(2792)

実は Lazy K の処理系に、2792 bytes のクワインのプログラムが付いている。このプログラムには基となる scheme のプログラムが付属していないため、Lazy K のプログラムそのものを解析する必要がある。仕方がないので、心眼や第6感を駆使してプログラムを読み進めると、このプログラムではどうやら、`, s, k それぞれが s, ks, kk という「コード」として符号化されていることに気付く。
Lazy K の Unlambda 記法では適用演算子 ` がプログラムの約半分を占める。したがって、` に 1 文字、k と s に 2 文字を割り当てる符号化は「コード」の短縮に有効だと考えられる。
さらに「コード」を「関数」に与える際、リストにせず複数の引数を直接与えている。これは「コード」のサイズを抑えるうえで極めて有効である。ただし、再帰を止めるために、「コード」の終了を検知する仕組みが必要となる。

もっと短く(1283)

さらに簡潔なプログラムを得るためには、どのような手法が考えられるだろうか。
私は以下の手法を採用した。

チャーチ数による再帰

前回解説したチャーチ数による再帰が、クワインでも有効である。
これにより終了判定が不要となり全体的に短くなるが、決められたチャーチ数に合わせて引数の数を調整することが必要となる。
たとえば今回は 512 (2^9) 回再帰することにしたが、そのためにプログラム先頭の適用演算子 '`' の数を調整している。

差分リスト

与えられたコードからプログラムの表現とコードの表現を再現するわけだが、それらの文字列=リストを作ってしまうと、ほしい結果を得るためには、リストを逆順にしたり連結したりする必要があり、プログラムが大きくなってしまう。これを避けるためには、途中結果を差分リスト≒継続の形で持つのがよい。
そうすれば、引数が与えられる度に継続を合成して最後に適用するだけで、望みどおりの結果を得ることができる。
たとえば A, B, C というコードから"abcCBA"という表現を得る方法は、それぞれ以下のようになる。
(簡単のため、引数のコードは逆順で与えるものとする)
リストの場合

-- 途中結果を (プログラムの表現, コードの表現) という形で持つ
f ("" , "") C B A
=> f ("c", "C") B A
=> f ("bc", "BC") A
=> f ("abc", "ABC")
-- コードの表現を逆順にしてプログラムの表現と連結する
=> "abcCBA"

差分リストの場合

-- 途中結果を差分リストの形で持つ
f id C B A
=> f (('c':).id.('C':)) B A
=> f (('b':).('c':).id.('C':).('B':)) A
=> f (('a':).('b':).('c':).id.('C':).('B':).('A':))
-- 引数の差分リストを "" に適用するだけでいい
=> "abcCBA"
SKから真偽値への変換

引数が S であるか K であるかによって場合分けが必要となる。私は以下のような関数を定義した。
sk2bool K = K = True, sk2bool S = S K = False となり、条件分岐が実現できる。

sk2bool x = S S S x (S K x) K
関数の構成

これまでのテクニックを踏まえて具体的な関数を構成する訳だが、引数の型や順序、ロジックの共通化など、どう構成すれば簡潔になるかという明確な指針は得られていない。私は以下のように定義した。

-- f は自分自身、k は差分リスト、x と y は引数で与えられたコード
quine f k x y =
  if sk2bool x
    then f (('`':) . k . g x) y
    else f (g y . k . g x . g y)
  where
  g x = if sk2bool x then ('K':) else ('S':)

abstraction elimination の振る舞いをどれだけ具体的に想像できるかが、短縮の鍵である。

おわりに

これらの手法を採用したことより、1283 bytes のクワインが得られた。
短くなったとはいえ、1000 bytes を超えるサイズである。さらなる短縮の可能性はまだあるのではないだろうか。諸君の積極的な挑戦を期待している。