マクロツイーター

はてダから移行した記事の表示が崩れてますが、そのうちに直せればいいのに(えっ)

TeX でもっと Quine する話

「TeX で Quine する件」に関する更なる話。

Quine の“出力”って何

Quine とは「自分自身を出力するプログラム」、もう少し厳密にいうと「プログラムのソースコードのテキストと、そのプログラムを実行した際の“出力”のテキストが一致する」ようなプログラムのことである。ここで問題になるのは、“出力”とは何か、ということである。

通常のプログラミング言語の多くにおいて最も基本的な“出力”は標準出力であるので、通常はこれを Quine の“出力”と見なすことが多い(すなわち、「自分自身を“標準出力に出力”するプログラム」が Quine)。さらに通常は“標準出力のテキスト”というのは「標準出力のデータをテキストとして解釈したもの」を指す。しかし世の中にはとっても変な人がいて、画像動画のデータを出力して、「その画像を人間が見た結果のテキスト」を“出力のテキスト”と見なす場合もあることも忘れてはいけない。

TeX で Quine」の“出力”って何

ところが、「TeX で Quine する」場合は、この“出力とは何か”があまり自明でない。確かに TeX 処理系は標準出力にもテキストを出力するが、TeX の通常の使用においては、これは補助的なものと位置づけられていて、生成される DVI や PDF の文書ファイルの方を“出力”と見なすのが普通だろう。Quine を考える場合にはどれを“出力”とするかに選択の余地がある。

  • TeX de Quine!! ー 0番染色体
    この記事では、「DVI や PDF 文書を人間が見た結果のテキスト」を“出力”と見なしている。つまり先述の「画像や動画の Quine」と同様の扱いをしているわけである。
  • もしTeX芸人が遠藤侑介の『あなたの知らない超絶技巧プログラミングの世界』を読んだら ー hak7a3が書き残す何か
    この記事では、「標準出力のデータをテキストと見たもの」を“出力”と見なしている。普通のプログラミング言語の Quine の取扱に近い。
  • 例の texadvent2015 の adventcal.tex の話 ー マクロツイーター
    この記事では、プログラム中で新たに出力ファイルを開いて、そのファイルを“出力”と見なしている。チョット珍しい。
    • 実はこのパターンについても先例が存在する。
      QuinesTEX HACKS
      この記事の Quine プログラムはできるだけ短くなることを目指していて、DVI(PDF)ファイルを出力しない。
    • adventcal.tex はこれを参考にしているが、「DVI(PDF)に意味のあるものを出力する」「ソースの使用文字を空白・改行・英小文字・‘\’・‘@’に制限する」という特徴を備えている。

TeX な PDF」で Quine する件

さらに、これらとは異なる別の“出力”の定義の Quine を考えている人もいる。

そこでは“出力”を「生成される PDF ファイルのデータをそのままテキストと見なしたもの」と扱っている。いや、厳密にいうと PDF ファイルは“テキスト”ではないのでバイナリデータとして扱う必要がある。すなわち、「元の TeX 文書ファイルと生成される PDF ファイルの内容がバイナリで一致する」というのが Quine の定義となる。

この課題は非常に挑戦的で面白いものである。しかしこの PDF(かつ TeX ソース)ファイルがここでの Quine の条件を満たしているかというと、私にはそのようには見えない。((当該の PDF ファイルは、PDF の仕様として必要な幾つかの改行文字を空白文字に置き換える処理を行う(その結果、PDF 仕様としては不正になるが、多くの PDF ビューアでは問題なく扱えるらしい)ことで LaTeX ソースファイルとして通るファイルにしている。PDF 仕様からの逸脱を許容するとしても、pdfLaTeX が出力するファイル自体はこの(不正な)ファイルではなく、“処理前”の正当な PDF ファイルだから、(少なくとも pdfLaTeX を実行器とみる限りは)肝心の Quine の条件を満たしていないことになる。また、当該の TeX 文書は「自分自身をファイルとして読み込む」機能(\pdfobj の file 指定)を利用していて、通常これは Quine としては反則とされる。))

TeX な PDF」で本当に Quine する件

それでは、件の条件を満たす「pdfTeX の Quine」を作ることは果たして可能なのか。これについては非常に厄介な問題がある。PDF の trailer 辞書の中には、「自身を表すユニークなID」を示す /ID というキーがある。

/ID[<dcdc5d2d44f335578dbd94a08ccd231c><dcdc5d2d44f335578dbd94a08ccd231c>]

現在(TeX Live 2015)の pdfTeX では、この ID 値の生成のために「ソースファイルのパス名」と「現在時刻(秒単位)」を利用している。Quine を作るためには ID 値が既知でなければならないが、それには先述の 2 つの要素が“固定”されている必要がある。もちろん本当の現在時刻を固定することは物理的に不可能であるが、普通の単体の PC 上の実行を考えるのであれば、PC 上の内蔵時計の値が変更できればよい。(大抵の OS では管理者権限が必要になる。)

実は、「2 つの要素」が“固定”できる状況であれば、次に示すファイルを“Quine 生成器”として使うことで「pdfTeX の Quine」を作ることができる。

[pdftexqgen.tex]
!\endlinechar=10
\catcode10=13 \let\!\let\!
\relax\!\!\relax\toks0{
\pdfcompresslevel=0 \pdfobjcompresslevel=0
\output{\setbox0\box255 \shipout\hbox{}}
\immediate\pdfobj stream{\endlinechar=10
\catcode10=13 \let\!\let\!
\relax\!\!\relax\toks0{\the\toks0}
\noexpand\the\toks0\noexpand\end\!
}}
\the\toks 0\end\!

予め決めたパス名を P、“現在時刻”を T とする。以下の手順で Quine のファイルを生成できる。

  1. 上掲のファイル pdftexqgen.tex をパス P にコピーする。
  2. 現在時刻を T に固定した状態でパス P のファイルを pdftex コマンドでコンパイルする。(コンパイルが 1 秒以内に終わる PC であれば、スクリプト等を利用して「PC の内蔵時計を T にセットした直後に pdftex コマンドを実行」すれば十分である。)
  3. そこで生成された PDF ファイルが目的の Quine のファイルである。

例えば、Windows 上の TeX Live 2015 を使用し、かつ P = C:\tmp\pdftexquine.texT = 2016/01/05 01:05:00 の場合、以下のような Quine のファイルが得られる。((2 行目の % の後の「????」は実際は「D0 D4 C5 D8」のバイト列。))

[Quine ファイル]
%PDF-1.5
%????
1 0 obj
<<
/Length 341       
>>
stream
\endlinechar =10
\catcode 10=13 \let \!\let \!
\relax \!\!\relax \toks 0{
\pdfcompresslevel =0 \pdfobjcompresslevel =0
\output {\setbox 0\box 255 \shipout \hbox {}}
\immediate \pdfobj stream{\endlinechar =10
\catcode 10=13 \let \!\let \!
\relax \!\!\relax \toks 0{\the \toks 0}
\noexpand \the \toks 0\noexpand \end \!
}}
\the \toks 0\end \!

endstream
endobj
4 0 obj
<<
/Length 0         
>>
stream

endstream
endobj
3 0 obj
<<
/Type /Page
/Contents 4 0 R
/Resources 2 0 R
/MediaBox [0 0 595.276 841.89]
/Parent 5 0 R
>>
endobj
2 0 obj
<<
/ProcSet [ /PDF ]
>>
endobj
5 0 obj
<<
/Type /Pages
/Count 1
/Kids [3 0 R]
>>
endobj
6 0 obj
<<
/Type /Catalog
/Pages 5 0 R
>>
endobj
7 0 obj
<<
/Producer (pdfTeX-1.40.16)
/Creator (TeX)
/CreationDate (D:20160105010500+09'00')
/ModDate (D:20160105010500+09'00')
/Trapped /False
/PTEX.Fullbanner (This is pdfTeX, Version 3.14159265-2.6-1.40.16 (TeX Live 2015/W32TeX) kpathsea version 6.2.1)
>>
endobj
xref
0 8
0000000000 65535 f 
0000000015 00000 n 
0000000583 00000 n 
0000000472 00000 n 
0000000414 00000 n 
0000000622 00000 n 
0000000679 00000 n 
0000000728 00000 n 
trailer
<< /Size 8
/Root 6 0 R
/Info 7 0 R
/ID [<A89DA8EEF61CE04E139AC9208DC1AFFF> <A89DA8EEF61CE04E139AC9208DC1AFFF>] >>
startxref
994
%%EOF

このファイルは「指定の PT の条件を満たす」場合にのみ Quine として振舞う。つまり以下の性質を満たす。

  1. 上掲の Quine ファイルをパス P にコピーする。
  2. 現在時刻を T に固定した状態でパス P のファイルを pdftex コマンドでコンパイルする。
  3. そこで生成された PDF ファイルは、元の(パス Pの)ファイルとバイナリ一致する。

PT の条件が満たされない場合は、/ID の値だけが異なる PDF ファイルが生成される。先に述べた手順が実行できない(したくない)人は、取りあえず「ID 値の違いを無視した Quine」を試してみるといいだろう。Windowsコマンドプロンプトでの手順は以下のようになる。

pdftex pdftexqgen.tex
copy pdftexqgen.pdf pdftexquine.tex
(この pdftexquine.tex が Quine)
pdftex pdftexquine.tex
fc pdftexquine.tex pdftexquine.pdf
(→/IDの行だけが相違するという結果になる)

*1:右サイドメニューの「View raw file」のリンクの先が当該の PDF ファイルである。