BT

最新技術を追い求めるデベロッパのための情報コミュニティ

寄稿

Topics

地域を選ぶ

InfoQ ホームページ ニュース TeXのアルゴリズムの再実装 - プログラミングの30年間を振り返る

TeXのアルゴリズムの再実装 - プログラミングの30年間を振り返る

原文(投稿日:2015/01/09)へのリンク

LivingSocialでエンジニアリングディレクタを務めるGlenn Vanderburg氏は,先のClojureConjカンファレンスで,自身がTeXのアルゴリズムをClojureで実装した際の興味深い記録を公開した。そのプロセスの中で氏は,過去30年の間に,プログラミングがどれほど変化したのかを実感した,というのだ。

TeX略史

TeXの重要性について説明するためには,その歴史が役に立つだろう。Donald Knuth氏がTeX 1.0をリリースしたのは1982年だが,32年が過ぎた現在もなお,TeXはコンピュータ組版の最先端にあるとGlennは言う。さらにTeXは,学習可能なソースコードの形式で長く提供され続けている大規模プログラムという,数少ない例のひとつでもある。

TeXはまさに傑作です – 動作速度が速く,ポータブルで,その出力も優れています。30年を経た今でも幅広く利用されている上に,過去に発見されたバグも驚くほど少ないのです。

逸話として氏は,Knuth氏がTeXの開発を決意したのが,自身の代表的な著書である “The Art of Computer Programming”の最初の校正刷りを受け取った時,その出来が“がっかりするほどひどい”ものであったからだ,という話を紹介している。そこでKunth氏は,自分の著作を納得できるものにするために,プログラムを書き始めた。TeXが公開されると,クイックソートで有名なTony Hoare氏が,学生のためにソースコードを公開するようにKnuth氏に勧めた。1982年当時にはインターネットが普及していなかったので,ソースコードのサンプルはそれほど多くなかったのだ。この目標を端緒としてKnuth氏は文芸的プログラミング(literate programing)を始め,TeXのソースコードが1986年,最終的に出版されることになった。Linuxカーネルが世に現れるまでは“世界で最も広く読まれた大規模プログラム”だった,とGlennは表現している。

TeXの内側

TeXのアーキテクチャは,テキストを処理するパイプラインである。ページやパラグラフ,行,単語など数種のオブジェクトに分割した上で,最終的にDIVファイルを生成する。TeXが世に出てから30年以上過ぎたが,今改めて見ていると,その“単純”さには本当に驚かされる,とGlennは言う。

TeXのソースコードは,現在では好ましいプログラミングスタイルとは見なされないような例に満ちている。例えば,

  • グローバル変数
  • 1文字の変数
  • goto文
  • 数百行に及ぶプロシージャ
  • 多数のマクロ
  • 重複したコード
  • ローカル変数の再利用
  • シングルスレッドを前提とする記述が“至るところ”に
  • 可変性はまさに“蔓延”

コードを読んでいると,あたかも違う時代にやって来たようです [...] 書籍が出版された1986年当時でも,すでに多くの面で,時代遅れなプログラミング例であったことは疑いありません。

これらはすべて,乏しい計算能力や限られたメモリなど,当時利用可能であったハードウェアの制限によるものだ。Glennの指摘によるとKnuth氏は,時間を要する関数呼び出しを最小限にするために努力していたのだ。このためTeXのコードベースは,高度に統合されて,“一部分を切り離して使うことが不可能なほど,複雑に絡み合った”ものになっている。

TeXは,今日ならばまさに嘲笑の的になるようなテクニックを駆使して,徹底的にハンドオプティマイズされています。とは言っても,私たちがそれらのテクニックを鼻で笑うことができるのは,30年間に及ぶMooreの法則,あるいは言語実装技術,そういったものの賜物に他なりません。

ClojureによるTeXの再実装: C16

このようにTeXは,今日の新しいプログラマに提供する最良の教材とは言えないかも知れない。それでもGlennは,TeXの再実装を通じてプログラミング技術の変遷を示すと同時に,手続き型から関数型への転換によってアルゴリズムが変更される,その実例を提供できると考えている。

Glennによると,前述したような簡潔性と極度の最適化のために,TeXのコードは,どこで何をしているのかを把握することが非常に難しくなっている。氏は当初,自身の設計をできる限りTeXの設計に近いものにしようとしていた。前述したように,TeXは厳密にシングルスレッドである。そして,今日のコンピュータ界における目標のひとつは,容易に入手可能になったマルチコアハードウェアを最大限に活用することなのだ。Clojureの機能のおかげで,TeXの基本となるパイプラインを関数のシーケンスとして実装することができた。それによって,スレッディングマクロを置き換えるだけで,シーケンスを並行実行モデルに切り替えることが可能になった。“おかげで私は,リンゴとリンゴを比べる作業に着手することができました。” Clojureによる実装は,当然ながらTeXよりも低速だったが,並列実行することで,“実用的なメリット”の確保が可能になったのだ。

Glennが学んだもうひとつの興味深い点は,TeXで使われているものと同じような最適化を,何らかの方法で実装しなければならないと感じたことだ。しかしながら,やがて氏はそれが,関数パラダイムを採用することで自然発生的に獲得できる,優れた抽象化機能を阻害するものであることに気付いた。問題は思った以上に複雑だったのだ。これは同時に,TeXのAPIがプログラム言語のパラダイムに大きく影響されている,ということに気付く原因にもなった。具体的には,全体的な可変性(mutability)と,シングルスレッドが前提となっていることだ。

Glennにとって最も熟慮を要したのは,プログラミング技術の進化をどの程度まで反映するか,という点だ。 1982年当時のプログラミングがどのようなものだったのかを振り返ると,次のようなことが分かる。

  • コンピュータは非常に遅く,メモリは少なかった。
  • ほとんどのプログラマはマルチプロセッサを見たことがなく,ワードやバイトのサイズはCPUによって異なっていた。
  • 浮動小数点演算のIEEE標準が存在しなかった。
  • ポータビリティとは,40種類近いOSをサポートする,という意味だった。それぞれ異なるファイルシステムやパス構文を持ち,I/OとアロケーションAPI,文字セットも違っていたのだ。
  • コードのダイナミックロードができなかった。
  • 最適化コンパイラはまだ研究プロジェクト段階だ。
  • オープンソースやフリーソフトといったものは存在せず,極めて基本的で共通的なデータ構造やルーチンを,スクラッチから実装しなければならなかった。
  • ソースコントロールはあったとしても,ごく初期段階のものだった。
  • 自動テストは聞いたこともなかった。
  • 今日のツーリングは,数十年に及ぶ小さな進歩で可能になった贅沢なのだ。

つまり,Glennはこの開発を通じて,プログラミングの分野でいまだ向上の余地を残すもののため,前人たちが残してくれた現在の境遇を多いにエンジョイしよう,と誘っているのだ。

この記事に星をつける

おすすめ度
スタイル

BT