Rogue Engineer's Diary / やさぐれ日記

9月8日をもって前 職を離れ、本日より株式会社サルガッソーに て活動することとなりました。関係者の皆様にはこの場を借りて感謝とご挨拶を。ここしばらくの間当日記を含むさまざまな活動も中断していましたが、これら も徐々に復活させていくつもりですので、どうか引き続きよろしくお願いいたします。

■ [Modern Compiler Implementation in ML] レジスタの上書きと"callee save"

前回はprintint()という関数が正常に動くところまで進めたが、今週はこれを使って真面目に動 作確認を行う。まずは配列の初期化と内容の参照は問題なくクリア。続いてレコード型の確認に進む。文字列と整数のメンバをそれぞれ一つずつ持つレコード型 を定義し、正しく値が格納されているかを確認するテストプログラムを用意する。

/* a record type and a record variable */
let function printint(i: int) = (...6月15日の日記参照...)
    type rectype = {name:string, age:int}
    var rec1:rectype := rectype {name="Nobody", age=1000}
in print("rec1.name = ");print(rec1.name);print("\n");
   print("rec1.age = ");printint(rec1.age)
end

こ れをコンパイル後、実行すると…

$ ./a.exe
Segmentation fault (core dumped)

ク ラッシュする（もはや驚くほどのことではないが…）。さらに調べてみると、print()関数を取り除いたり、順序を変更すると正 常に動作することが分かった。どうやら関数呼出し後にレジスタの内容が上書きされているのが問題であるらしい。

IA32 アーキテクチャには、EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESPという名前のついた、合計8つの汎用レジスタがある。これらのうち（スタック上に置いた値の管理に使う）EBPとESPを除いた6つのレジスタをや りくりしながら計算を進めていく。関数の呼び出し前後でレジスタの値が上書きされることも当然発生しうるので、これに対応するためのルールも決められてい る。

今回問題となったのは、"caller save", "callee save"というルールにまつわる部 分であった。簡単にまとめると、ある関数が関数呼び出しを行うときに、

• 呼び出した側の関数 が、レジスタの値を保存しておくのが"caller save"
• 呼び出された側の関数が、レジスタの値を保存 しておくのが"callee save"

である。先に述べたIA32のレジスタのうち、 どれを"caller save"あるいは"callee save"させるかはハードウェア的には決められておらず、OSやコンパイラが決めたルールに従うことになる。ところがIntelの資料を眺めてみてもそ のあたりの手がかりが見つからない。

ということでネット上を探し回ってそれらしい資料を当たる。"Calling conventions for different C++ compilers and operating systems" や"yunoの雑記 帳wiki - IA32"を見ると、どうやらWindows, Linux共にEBX, EBP, ESI, EDIを"callee save"のルールに従い、呼び出された関数で値を保存しておく必要があるらしい。GCCでやや大めなプログラムのアセンブリリストを出力させると、やは りこれら4つのレジスタを退避させていることが分かった。

ということで関数呼び出しの前後を以下のように修正する ことで対応した。修正部分とコメントは赤字で示されている。

_L1:
	pushl	%ebp	 ← EBPは今回の修正前から退避されている
	movl	%esp, %ebp
	pushl	%edi	 ← EBX, ESI, EDIを退避
	pushl	%esi
	pushl	%ebx
	subl	$8, %esp ← 引数とローカル変数の領域分だけESPを補正
	(...)		 ← 関数本体を実行
	addl	$8, %esp
	popl	%ebx	 ← EBX, ESI, EDIを復元
	popl	%esi
	popl	%edi
	leave
	ret

動 作確認の結果も良好。これでなんとかなりそうだ。本当はEBX, ESI, EDIの各レジスタのうち関数本体では使われていないものについては、退避と復元を省略することができる（現にGCCではそのようにしている）のである が、今回は無条件で退避・復元を行っている。これについてはまた改めて考えることにしよう。

■ [Modern Compiler Implementation in ML] 割り算のワナ

テストプログラムを実行して結果を確認しようと思うと、文字列だけでなく数値も表示させたくなる。だが Tiger には数値表示用の組み込み関数がないので、マージソートのサンプルプログラムから以下のような関数を引っ張ってきて使うことにした。

function printint(i: int) =
    let function f(i:int) = if i>0
        then (f(i/10); print(chr(i-i/10*10+ord("0"))))
    in if i<0 then (print("-"); f(-i))
       else if i>0 then f(i)
       else print("0")
    end

掛 け算と割り算、if文、ネ ストした関数定義に、とどめは再帰呼び出しと、"Hello World"の次に試すプログラムとしては複雑・無謀きわまりない…というか、この後に作る予定の（例えば加減乗除といった）単純 なテストプログラムの実行結果を確認するためにこんなものを用意するところからして、手段と目的がひっくり返っているのだが、そこは気にしないことにす る。

…案の定ハマった。落とし穴はいくつかあったのだが、最後に残ったのがこれ。

$ ./a.exe
Floating point exception (core dumped)

浮 動小数点演算は使っていない（というかこのコンパイラでは浮動小数点の計算はできない）のに一体何が起きているのだろうか。

printint()関数の中身を削っていって問題を絞り込んだ結果、最後に残ったのが、割り算であった。上記のエラーを再現できる最小のコードはこんな感じになる。

6 / 2

当 初、このコンパイラは以下のようなアセンブリコードを出力していた（ちなみに、GCCでこのような定数同士の計算をさせると最適化によりアセンブリコード レベルでの割り算は実行されず、"6/2"の計算結果である"3"が直接レジスタに代入されるのだが、このコンパイラではそのような最適化はまだ実装され ていない）

	movl	$6, %eax
	movl	$2, %ebx
	idivl	%ebx

と ころが、このアセンブリコードはきちんと動作しない。

符号付き整数の割り算命令である"idivl"(IDIV) 命令を実行するときには、まず割られる数を64ビットで表現したもののうち、その上位32ビットをEDXレジスタに、下位32ビットをEAXレジスタに置 く。割り算を実行した結果はEAXレジスタに格納されるが、この結果が32ビットに収まらない場合には#DE(divide error)例外が発生する。

上記のアセンブリコードで は、EDXレジスタの値については一切気にしていないため、実行時点でたまたまEDXレジスタに入っていた値が、割られる数の上位32ビットとして使われ てしまっている。そのままIDIV命令を実行しても、ほとんどの場合割り算の実行結果は32ビットに収まらないために、例外が上がる、ということらしい。

解 決の手がかりを得るために、同様の計算をするアセンブリコードをGCCで出力し、それを眺めてみると、"cltd"という命令が使われていることに気がつ いた。ところがIntelの"IA-32 Intel Architecture Software Developer’s Manual"を見ても、 そのような名前の命令は見当たらない。そのまま使ってしまってもいいのだが、何をする命令か分からないままというのも気持ちが悪い。

い ろいろと資料を探したあげく、as(GNU Assembler)のマニュアルにある"Opcode Naming"の項を見たところ、Intel記法（ニーモニック）で"cltd"に相当するのは"CDQ"という命令であることが分 かった。また、説明文に"sign-extend dword in `%eax' to quad in `%edx:%eax'"と書かれているところからしても、今回のような符号付き整数の割り算を実行する前に必 要な命令であることが見て取れる。ということでコンパイラを修正し、以下のようなアセンブリコードが出力されるようにした。

	movl	$6, %eax
	cltd	←コレを追加
	movl	$2, %ebx
	idivl	%ebx

こ れにて一件落着。"Floating Point Exception"も出なくなったし、printint()関数もうまく動作しているようだ…が、それにしても整数の割り算で 「浮動小数点演算の例外」と出るのは一体なぜなのだろう？

■ [Modern Compiler Implementation in ML] 第12章突入、"Hello World"

"Modern Compile Implementation in ML"もついに第12章"Putting It All Together"に突入。ようやくコンパイラの動作確認フェーズに到達することができた。ちなみに今まですっかり書き忘れていたが、僕の使っている作業 環境は以 下の通り：

• Standard ML of New Jersey v110.54
• cygwin on Windows XP(SP2)
• gcc (GCC) 3.4.4（バックエンドに使用）

今回製作したコンパイラは"Modern Compile Implementation in ML"用に設計された教材用言語"Tiger"（Tigerについては2004年2月8日のエントリでも若干説明した）で書 かれたプログラムを入力と する。最初にコンパイルするテストプログラムは（お約束の）"Hello World"である。ファイル名は"hello.tig"。

/* hello world */
print("Hello, World!\n")

"Modern Compile Implementation in ML"のサポートページにあるライブラリ、runtime.cを コンパイルし、現在製作しているコンパイラの出力とリンクすることにより、"print"などの基本的関数がTigerから利用できるようになるのだが、 そのままコンパイル しようとするとこんなエラーが発生する。

$ gcc -c runtime.c
runtime.c:1:8: warning: undefining "__STDC__"
runtime.c:106: error: conflicting types for 'getchar'
/usr/include/stdio.h:190: error: previous declaration of 'getchar' was here

エラーが発生している、runtime.cの該当部分はこんな感じ。

.....
#undef getchar

struct string *getchar()
{.....

ざっと見た限り、（#undef getcharによって）Cの標準入出力ライブラリにある同名の関数/マクロとの衝突回避をしようとしている気配はあるものの、 それがうまく機能していない。いろいろな手を試してみたが、結局runtime.c内の"*getchar()"を"*getchr()"に書き換えると いう姑息な方法を使い、 一旦しのぐことにした。

やっと本番。まずはStandard ML of New Jerseyの対話型環境にて、"hello.tig"をコンパイルする。

- Main.compile "test/hello.tig";
emit tigermain
val it = () : unit

コンパイルされた結果は"hello.tig.s"というファイル名で出力される。中を見るとそれらしいIA32のアセンブリコードが 出来上がっ ているのが分かる：

.globl _tigermain
 .def _tigermain; .scl 2; .type 32; .endef
_tigermain:
 pushl %ebp
 movl %esp, %ebp
 subl $4, %esp
.....

出てきたアセンブリコードの全体像はこ ちらを参照。余計な"movl"や"jmp"が目に付くが、これらは追々取り除いていく予定。

これをgccでコンパイルし、先ほどのruntime.cのコンパイル結果とリンク、そして（やや緊張しつつ）実行：

$ gcc hello.tig.s runtime.o
$ ./a.exe
o, World!
 瑞U牙・ ・・$・右・E・E・} 畿・・UE・ 孔・・畿
（……中略……）
ModuleHandleA P P P P P P P P P P P P P P cygwin1.dll P KERNEL32.dll
Segmentation fault (core dumped)

クラッシュ。派手に散った。

実行直後に"o, World!"と出ているところからして、最初の4バイト(="Hell")が切れていることはすぐに分かる。なにかズレているのかと思いながらアセンブ リコードを眺める…が、よくわからない。

Cで同様の動作をするプログラムを書いて、runtime.oとリンク、実行させると、同じようにSegmentation faultでクラッシュする。コンパイラの問題ではなく、リンクしたライブラリ"runtime.o"に何かあるようだ。

問題のライブラリのソースであるruntime.cを 眺めたところ、原因はあっけなく判明した。TigerではCのようなNULL終端文字列ではなく、Pascal形式、つまり長さ(4バイト)＋文字列本体 という構成の文字列を使っていたので あった。本にも書いてあったようだがすっかり忘れていたよ。

ということで、コンパイラから出力されるアセンブリコード中で

...
L0:
 .ascii "Hello, World!\n\0"

となっていた箇所を、

...
L0:
  .int 14
 .ascii "Hello, World!\n"

と出力するようにプログラムを修正し、再度コンパイル、実行する：

$ gcc hello.tig.s runtime.o
$ ./a.exe
Hello, World!

ついに動いた。

まずは第一歩。でもここからが長い…のだろうな、やはり。

■ [Modern Compiler Implementation in ML] 過去10ヶ月の経過を書き足すことにする

2005年7月3日に最後のエント リを書いてから、とんでもなく間が空いてしまった"Modern Compiler Implementation in ML"であるが、実は少しずつ進行させていた。日付をさかのぼって 2005年の8月あたりから、現在までの経過をこの日記に書き足しておくことにしようと思う。ということで書き足したエントリ一 覧：

• 2005-08-15 テスト用干渉グラフを生成するプログラムを作る
• 2005-09-23 テストケースの用意と"freezeMoves","freeze", "selectSpill"の実装
• 2005-10-23 論文 "Iterated Register Coalescing"
• 2006-03-15 "AssignColor"までを実装
• 2006-05-19 "RewriteProgram"の実装、第11章終わり

■ "RewriteProgram"の実装、第11章終わり

最後に残った"RewriteProgram"を実装する。ここまで実装してきた他のアルゴリズムは"Color"モジュール内に作成 していたが、これはRegister Spill、すなわちレジスタ割り付けの処理で「溢（あふ）れた」レジスタをメモリへ退避するべく、アセンブリプログラムを書き直すという処理であるた め、かな り毛色が異なる。二週間ほど考えた結果、"Frame"モジュールの一部として実装（ただし、実際に書き換えるのは"IA32Frame"モジュールであ る）することにした（修正後のプログラムはこち ら）。

上記の図の"Main"に当たる部分は"RegAlloc"モ ジュールと"Color"モジュー ルに分散されたかたちで実装されている。 "RewriteProgram" 部分のテストは面倒くさいので後回し様子を見ながら順次進めていく予定。

これで第11章の実装は一通り完了。次の第12章がコンパイラ作りの仕上げ作業、総決算となる。うまく行けば、動 くコードを近いうちにコンパイラが吐き出してくれるようになるはずである。

■ [NerdTV] クヌース先生がMacPaintのソースコードについて尋ねている動画を見つけた

以前、『[NerdTV] Andy Hertzfeld: クヌースに「ソースコード見せてよ」と頼まれたら…』というエントリにて、MacPaintのソースの公開が 決まった（ただし実際の公開にはまだ至っていない。詳しくはこちらを 参照）いきさつを書いたが、そ のきっかけになった、Computer History Museumでの出来事：

Andy: 今年の1月にComputer History Museumというところで、オリジナルのMacintoshのマーケティングチームが講演をやったんだけど、その場では僕も含め最初の Macintoshにかかわったスタッフの多くも客席に座って話を聞いていた。で、最後の方で質疑応答をやったときに、年配の観客が立ち上がって、 「MacPaintというのはプログラムの歴史上、最も素晴らしい作品だったんじゃないかと私は思うのですが、ソースコードを見せていただくということは 可能なのでしょうか」という質問をしてきたんだ。その質問をした年配の観客というのは、実はドナルド・クヌースだった。

Bob: えーっ！

の実際の様子が記録された動画ファイルを見つけることができた。

Computer History Museumで開催された過去のイベントの一覧の中に、2004年1月24日に開催された"The Macintosh Marketing Story: Fact and Fiction, 20 Years Later"に関するページがあり、そ のときの動画もそこからダウンロードすることが出来る。

問題のクヌース先生の質問はビデオの中の1時間5分55秒あたりから。会場にいた『年配の観客』ことクヌース先生が立ち上がり、他の質問と合わせて

And you mentioned Bill Atkinson. I wanted to meet Bill Atkinson because his program, MacDraw, really blew me away almost any other programs I've ever seen, and I wonder if the source code for that program still exists...

あと、ビル・アトキンソンの話が出ましたが、私自身、彼に会いたいと思っていたのです。というのも、彼のプログラム、 MacDrawは 私が今までにみたどのプログラムも吹き飛んでしまうような存在でしたし、そのソースコードがまだ残っていないのかなと思っている次第です。

と言っているのが確認できる。質問の際には自分の名を名乗ってもいないし、ものすごくラフな格好をしていたので、あれがクヌース先生だ と気がついた人はもしかしたら少なかったのではなかろうか。

このビデオの中には他にも見どころがいくつかあるのだが、

• 8分40秒あたりから始まる、スティーブ・ジョブスのプレゼンテーション。1983年の8月23日にハワイで開催された、 Apple Annual Sales Meetingでの映像である。語りの上手さと壇上でのカッコ良さは圧倒的の一言。
• 12分45秒あたりからはMacintoshの名を初めて世に知らしめたCM、"1984"のフィルムが上映される。
• 25分55秒あたりで、客席にいたAndy Hertzfeld, Bruce Hornが自己紹介。大きな喝采を受ける。

が特におすすめ。興味のある方はぜひご覧いただきたい。

関連エントリ：

• Andy Hertzfeld: クヌースに「ソースコード見せてよ」と頼まれたら…
• Folklore.orgから: MacPaint Evolution
• MacPaintのソースコードは今どこ に?
• MacPaintのソースコード、続報

■ 元々は 「平和利用」のために開発された？（インターネット）ワーム

「ワーム」と言えば、1988年のインターネット・ワーム事件に始まり、Code Red, Nimdaなど、過去二十年近くにわたりインターネット上で数多くの深刻な問題を起こしているプログラムの代表格であるが、その「ワーム」が元々は破壊目 的では なく、分散コンピューティングの一手法として（大げさに言えば「平和利用」のために）開発されたと言ったら信じられるだろうか。

■IEN(Internet Experiment Note)

インターネットの前身となったネットワークであるARPANETが、現在のインターネットへと変化していった時期、すなわち 1970年代後半から1980年代初頭にかけては、IEN(Internet Experiment Note)という名前の技術文書が作成されていた。

Vint CerfとBob Khanによって1974年に提案されたプロトコルのコンセプトの実現に向け、ARPAは1977年に『イン ターネット』と呼ばれる研究プロジェクトへの資金の提供を開始した。当時、RFCはARPANETの研究プログラムの産物という位置づけであったため、イ ンターネットプロジェクトではRFCに似た形式の技術ノート、Internet Experiment Notes (IEN)を新たに作ることを決定した。IENのシリーズのエディタには、従来よりRFCの編集を行っていたJon Postelが就任した。

IENのインデックスリストには、1977年の3月から1982年の9月までに発行された204件のIENが登録されている。その 後、全てのARPANETとInternet関連のドキュメントはRFCへ統合されることとなった。

（"RFC Editor: Internet Experiment Notes", 福盛秀雄訳）

例えばTCP/IPの仕様を定めた"RFC 791 - Internet Protocol"や、"RFC 793 - Transmission Control Protocol"の"Replaces:"という項を見ると、合わせて 20個近くのIENが、これらRFCの原型、あるいはドラフトとして使われていることが分かる。IENはインターネットの成立にかかわる重要な技術文書が 多く含まれたドキュメント集なのである。

■IEN 159 - "Notes on the 'Worm' programs"

その中の一つ、1980年の5月に発行された、IEN 159 "Notes on the 'Worm' programs -- some early experience with a distributed computation"が、インターネット上でのワームについて、世界で最初に言及したドキュメントだ。

「ワーム」プログラムは分散コンピューティング(distributed computation)実現のための一手法である -- このプログラムは複数のマシンにまたがり存在し、アイドル状態のマシンにおいて自己増殖を行う。「ワーム」は複数の「セグメント」と呼ばれる部分から 構成され、セグメントは別々のマシン上で動作する。ワームには、自身を維持するためのメカニズムが備わっている -- 具体的には、別のプログラムが稼動していないマシンを必要に応じ発見し、セグメントを追加するためにプログラムを複製するといったものである。ワームをコ ントロールする方式を作成する際には慎重な設計が要求されるが、このメカニズムにより、ワームは非常にダイナミックかつ堅牢なプログラムを実現している。

これらのテクニックは複数のマシンからなる単純なテストプログラムに始まり、多数のマシンを活用した、リアルタイムのアニメーションシステムに至る、実ア プリ ケーションの構築に利用された。
（……）

（IEN 159 "Notes on the 'Worm' programs -- some early experience with a distributed computation", 福盛秀雄訳）

このIEN159だが、実体は1980年の12月に開催された"Workshop on Fundamental Issues in Distributed Computing, ACM/SIGOPS and ACM/SIGPLAN"というワークショップ向け原稿のアブストラクトを流用したものである。

■Communications of the ACM - "The 'Worm' Programs"

ワー クショップの原稿は残念ながら見つけられなかったが、その改訂版に当たる"The 'Worm' Programs -- Early Experience with a Distributed Computation"が1982年3月の Communications of the ACMに掲載されていた。（実のところ論文の本体は、ACM のDigital Libraryに加入していないと読めないのだが、Digiral Libraryに加入していない人もこ ちらのリンクから「一応」参照は出来るみたいである。ただし、いつまでも読めるかどうかは無保証）その内容をかいつまんで説明してみ ることにしよう：

・ワームの概要

ワームは、Xerox Palo Alto Research Center内の、Ethernetによりネットワーク接続された合計100台のAlto（1970 年代初頭に開発された、世界最初のパーソナルワークステーション）を対象に製作された。ワームの実装はBCPL（C の祖先に当たるプログラミング言語）により記述されている。通常、夜間にはAltoは空き（ユーザが使用していない）状態となり、その時間帯にはメモリ診 断プログラムが動いていた。これら100台のAltoをマルチプロセッサマシンとして活用する方法の一つとして、ワームは開発されている。

・ワームの実装

各マシンに置かれたワームの構成要素のことをセグメントと呼ぶ。 セグメントは互いに通信を行い、（何らかの原因により）あるセグメントが停止したことを感知すると、他のセグメントが、空きマシン（ユーザが使用していな いマシン）を探し、初期化した後にワームの一部分として加える。

空きマシンが発見されると、ワームのセグメントはそのマシンに対し、標準のネットワークブート処理を行うよう指示するが、そのときに ブートされるプ ログラムとして、ワームのセグメントを指定する。これにより新たなマシンがワームの構成要素として追加されることになる。ワームの実行処理が 完了した場合には、再びネットワークブート処理を行い、ワームが稼動する前に実行されていたプログラム（メモリ診断プログラム）をロード・実行することに より、元の状態に復帰する。

ワームが移動した先のマシンにはディスクがマウントされていない可能性があるため、（ワーム上で稼動する）プログラムはディスクへのア ク セスを行わないことが要求された。また、ディスクがマウントされた状態のマシンが仮にあった場合でも、ワームによるディスクへの書き込みは「反社会的活動 (profoundly antisocial behavior)」であると考えられていた。Xerox内のネットワークにワームを展開するに当たっては、プログラム内にはディスクドライバが一切含ま れていないことを示し、Altoを利用している他のユーザの理解を受けるなどの配慮が行われた。

・ワームの制御にまつわる課題

ワームの制御は大きな課題であった。実験の初期には、ネットワークでの転送処理に失敗し、不完全な状態で実行されたワーム上のプログラ ムが、実行先 のマシンをクラッシュさせるという現象が発生した。この現象はワームの無制限な増殖を招き、さらに増殖先となるマシンがすべてクラッシュするという結果に つながった。ワーム内にあらかじめ非常停止用のメカニズムを用意していたためにワームの活動はなんとか停止させることが出来たが、問題が収束した頃には、 Xeroxの建物の各所にクラッシュした100台のマシンが散らばるという状況となっていた。

しかし初期のテスト期間に発生した、こういった問題の原因究明と解決を進めた結果、ワーム上でのプログラムは安定して実行されるように なり、数週間以上連続して稼動させることも可能となった。

・ワーム上で動作するアプリケーション

実運用においては、ワームを利用したアプリケーションが数種類、製作・利用された。具体的には、画面上にメッセージやグラフィックス画 像を表示する "The Billboard Worm"、ネットワーク上にある複数台のマシン上にて展開・稼動し、指定された時間が来ると外部ターミナル接続用のサーバ経由で、ユーザに電話をかける "The Alarm Clock Worm"、実時間で三次元アニメーションを生成する"Multimachine Animation Using a Worm"、ワーム間で相互に通信し、ネットワークの診断を行う"A Diagnostic Worm for the Ethernet"などがある。

・ワーム以前に存在した分散アプリケーションについて

ここで紹介された「ワーム」は1980年前後に行われた実験であるが、それよりも古くから、ARPANET上には分散コンピューティン グのさきがけと呼ぶべきアプリケーションがいくつも存在していた。 ARPANETのルーティングアルゴリズムはそれ自体、多数のマシンを使った分散コンピューティングと言える。ARPANETの主要な構成要素の一つであ り、現在のルータの原型ともいえるInterface Message Processor(IMP)はネットワークを経由して絶え間なく情報を交換しており、ネットワーク上でIMPが欠けたり、または増えたりしても対応可能 であった。さらに、それぞれのIMPは近隣のIMPから（システム）ソフトウェアをロードして起動することが出来た。IMPの（システム）ソフトウェアは ARPANET上でマイグレーション（移動）を行いながら活動するプログラムであったと言える。

ARPANET上で自律的に移動した最初のプログラムは、BBN(Bolg Beranek and Newman)のB.Thomasが製作した"Creeper"であった。 これはTenex オペレーティングシステム上で動作し、ファイルを印刷した後、ネットワーク上の別のTenexシステムを探して外部状態や ファイルを含めて自らを転送・実行するというプログラムであった（プロセスマイグレーションの元祖と呼んでも良いかも知れない）。後に"Creeper" の発展形は、ネットワークを移動するだけでなく、複製処理によってネットワーク上で増殖する機能を持つようになった。これに合わせネットワーク上を徘徊 し、"Creeper"を発見したらそれをログアウトさせるという"Reaper"というプログラムも製作された。

■「ワーム(worm)」という名前の由来は？

以上、論文"The 'Worm' Programs -- Early Experience with a Distributed Computation"の概要を説明してきたが、実は上記の中で一 点説明を省いたところがある ― 「ワーム(worm)」という名前が、そもそもどこから来たか、というお話だ。

元論文の冒頭部分を読むと分かるのだが、"worm"という名前はJohn Brunnerの"The Shockwave Rider" というSF小説（1975年）に登場する、"tapeworm"に由来している。論文の中には"The Shockwave Rider"からの引用がいくつか登場するが、現在インターネット上で起きている出来事と照らし合わせると非常に興味深い内容が含まれている。"The Shockwave Rider"は先日入手したので、中身については折を見て、改めて紹介できればと思っている。

関連エントリ:

• [NerdTV] Bob Kahn: TCP/IPの父、インターネットの前身であるARPANETを語る
• [NerdTV] Bob Kahn: ARPANETからインターネットへ、TCP/IPの登場
• [NerdTV] Bob Kahn: TCP/IPの父いわく、「IPアドレスを32ビットにしたのは……」

■ "オープンソースカンファレンス2006"参加予定

今週の土曜日に以下のセッションを聴講するつもり。（ちなみに昨 年はこんな感じだった）

• 10:00〜 オー プンソース環境における翻訳作業 - 翻訳支援ツールOmegaT
• 13:30〜 出 張カーネル読書会（前半）
• 15:00〜 出 張カーネル読書会（後半）

15:00からのセッションでは他に「翻訳BOF」というのもあるようなのだが、噂の「カーネル読書会」も見てみたいということで、ま ずは上のような感じとなった。（実はまだ迷っている）

あと、懇親会にも参加する予定。

■ [NerdTV] Bob Kahn: TCP/IPの父いわく、「IPアドレスを32ビットにしたのは……」

前々回、前回に続き、NerdTVによる、TCP/IPの 父、Bob Kahnへのインタビューの翻訳の第3弾をお送りする。今回はIPアドレスの設計にまつわるお話。一つの山場と言っても良いであろう。インタビューでは 33分45秒あたりから始まる一節である。

Bob Cringely: TCP/IPプロトコルの開発の歴史を振り返ってみて、ここはもしかしたら今とは違っていたかもしれない、あるいはここはこうした方が良かったんではない か、と思ったりするところなどはありますか？

Bob Kahn: そのタイプの質問というのはしょっちゅう受けるんですが、歴史はどう変わっていただろうかというたぐいの質問ですし、なかなか答えられるものではありませ んよ。だって、例えば1900年に半導体とレーザーが発明されていたら、ラジオとテレビはどのようになっていたと思います？実際にはそのような状況を 再現することは出来ないですよね。

Bob Cringely: まぁ確かにそうなんですけれども、意地悪(unfair)な質問をするというのが、私の商売でもありますので。

Bob Kahn: 今とは違ってるであろうこと は間 違いないでしょうが、状況はまったく異なりますし、あまり現実的な話はできないと思いますよ。私たちは全般的に見て、かなり良い仕事をしたと思っていま す。まぁ確か に、もっといいやり方があったかも知れない、と思う部分もありますけれどもね。 当時やっていたことの中で、今考えてみると、あれはバカみたいだったなぁと思うような話というのを少し挙げましょうか。ARPANETでは16ビットのア ドレ スを使っていました。通信したい相手を指定するには、行き先のマシンを16ビットで表現していたんです。みんな一つのネットにつながっているし、 それで別に困ることはなかったわけです。いいですよね？

具体的には、行き先のネットワークはどこか、そのネットワーク上のどのノードであるか、そのノードの先のどの線につなぐか、という 情報を組み合わせて指定します。（一つのノードには）4本の線があって、4台のマシンをそこへつなげることが出来ます。基本的な仕組みはそんな感じです。 4つのワイヤのうちの どれを使うかで2ビット、確かその上に6ビットあって、最大で64台のノードを指定することが出来る、これで16ビットのうち8ビットが埋まります。他の 細かい用途のためにあと2,3ビットくらい必要かもしれないと思っていた。ARPANETでは、まずはそんな感じだったわけです。当時、「もっと大きな ネットワークを作ろうとしたら、もっとビット数が必要になるだろうな」と私たちは考えたので、（インターネットでは）一気に32ビットを用意することにし ました。自分たちの目論見としては --

Bob Cringely: それでもう十分だろう、と。

Bob Kahn: -- 半永久的に使えるはずだと思っていたんですよね。実のところ、私たちは32ビットのアドレスを用意して、最初の8ビットがどのネットワークを指すかを指定 する、という設計をしたんです。8ビットあれば256通りの組み合わせになる。AT&Tには専用のネットが必要だろうし、国防総省も同様 かな、これ で2つ。 ヨーロッパに1つ用意するとして、これで3つ。多分日本というか、アジア太平洋地域あたりでも1つ必要だろう、これで4つ。それを2倍して、8になる。さ らに2倍すると16。さらに2倍して32。どう計算しても、256という数字は、はるか彼方にあるように見える。ところが私たちがすっかり見落としていた ものがあった。パーソナルコンピュータの出現というものを全然予想していなかったんです。たとえば一つの建物の中にローカルエリアネットワークがあって、 そこに沢山のコンピュータがつながっている姿というのは考えていなかった。ところが間もなく、そこらへんの話が一気に現実的になってきたわけです。 XeroxがAltoとEthernetというものを出してきて、（こういうのが普及すると）8ビットでは足りなくなるだろうということが私たちにもすぐ 分かった。これに対処するために、仕組みを考え直す必要があったわけです。でも32ビットのアドレスというのはそのまま残りましたし、現在でも32ビット のアドレスが使われていますよね。これはIPプロトコルのバージョン4、略してIPv4と呼ばれるものです。今はそれをIPv6と呼ばれる、128ビット のアドレスを使うバージョンに移行させるべく、いろいろな人たちが活動していますが、移行作業というのはなかなか難しいですね。全てが一体となって動い ている世界で、一部分を取り替えようとすると、後方互換性の問題がついて回りますし、スムーズに移行するにはどうしたらいいかというのが課題になります。 ともかく、この件は最初ではかなりのヘマをやったけれども、システムの柔軟性を十分に確保しておいたおかげで乗り切ることができた、という話の一例である と言っ ても良いかと思います。

Bob Cringely: そうですね。確かに、実際のところ私たちはまだ --

Bob Kahn: （IPv4を）使い続けていますよね。

Bob Cringely: -- 32ビットのアドレス空間でなんとかやっている、と。

Bob Kahn: でも、8ビットではまずいというのは、最初の設計をした後、半年から1年くらいですぐに気がついてしまったんです。

Bob Cringely: そうなんですか？

Bob Kahn: ところが、設計している時には、8ビットあればもう十分、完璧だろうと本気で信じていた。

Bob Cringely: （笑い）

（NerdTV #12: Bob Kahn by Robert X. Cringely and PBS、福 盛秀雄訳）

これで、ARPANETに始まり、インターネット、TCP/IPの登場と、そしてその設計の背景までの話が一通り出揃っ た。改めて一覧を出しておくことにしよう。

• TCP/IPの父、インターネットの前身 であるARPANETを語る
• ARPANETからインターネットへ、 TCP/IPの登場
• TCP/IPの父いわく、「IPアドレスを32ビット にしたのは……」（本エント リ）

「昔からそういうものがあったのが当たり前」と感じてしまいそうな技術にも、それを作った人というのは必ず存在していて、ちょっと話を 聞いてみると、驚くほどの知恵や、いろいろな失敗の物語を見つけることが出来る。一 年ほど前にも書いたが、「過去の発掘」というテーマは、機会がある限り、この日記上でも引き続き、積極的に取り上げて行きたいと思 う。

本エントリの内容はクリエイ ティブ・コモンズ・ライセンスの下に公開されています