The Art of Computer Programming を読む(1)

今年は、一日少しでも The Art of Computer Programming を読み進める、というのを目標にしようと思う。

The Art of Computer Programming Volume 1 Fundamental Algorithms Third Edition 日本語版

The Art of Computer Programming といえば、TeXや文芸的プログラミングなどで有名な Donald Knuth 先生の名著である。TAOCPと略すようだ。ちなみに複数巻構成で、現在４巻まで出ているが完成していない。

ちなみに、私の本書に対する態度は、「計算機の内部に興味がある人が読む本。全てのプログラマが読む本ではない」というものである。本書は物理的にも大変分厚く、また中身も非常に濃いため１ページ１ページが重たい。全ての計算機科学専攻の学生が読む本ではないと思う。

私は、純粋で理論的なものに興味があるので、本書を読むに至った。

-----

今回は1.3.1 MIXの解説まで。

まず1.1はアルゴリズム、1.2は数学的な基礎の準備にあてられている。
だが、この1.2の数学的な基礎というところが曲者で、1.2に書かれている数学的な内容はかなり高度なものが多く、演習問題に出されている課題も難解なものが大半である。だが、コンピュータプログラミングには直接関係しない内容ばかりなのだ。
はっきり言って、1.2は流し読みした方が良い。Knuth先生は
「本書は前から順番に読むことを意図されている」
などと書いているが、Knuth先生の知能に満たない人がこれを真に受けていると、1.3にたどり着くまでに挫折してしまう。1.2を流し読みして1.3から本腰を入れれば良い。

本書の真価は、当然ながら1.3から発揮される。1.3ではMIXという架空のコンピュータが導入される。MIXは、以下の点で現在普及しているコンピュータと大きく異なる。
・基数が決まっていない。二進数か十進数か、はたまた三進数かは意識せずにプログラムを作成することができる
・情報の基本単位である「バイト」の大きさが決まっていない。ただし、少なくとも64通りの情報を1バイトで区別できること、という要件はある

現在普及しているコンピュータでは、下記のようになっている。
・基数は2（0 or 1の単位を「ビット」と呼ぶ）
・1バイトは8ビットである。したがって2^8 = 256通りの情報を区別できる

これで何が嬉しいかというと、現在のコンピュータで既に決まっている詳細な箇所を、一旦未定として抽象化している点である。アルゴリズムの本質が議論できよう。

しかしこんな具合なので、現在のコンピュータで役立つ知識を求めているプログラマーには、本書は回りくどく感じられよう。そういう人には、パターソン＆ヘネシーの「コンピュータの構成と設計」をおススメしたい。
（私も読みきれていないので無責任なのだが、読者レビューから中身については間違いないと言える）

コンピュータの構成と設計 第5版 上・下電子合本版

次回は、練習問題もしくは1.3.2 MIXアセンブリ言語について書く。