無駄なあがきの記録：2001-2005

自分のウェブサイト用にとったドメイン名の廃止を機に、この9年間の無駄なあがきについて書いてみる。無駄に評伝形式。あと文献の出現順はいくらなんでもあんまりなので後で直します。
若干イントロを足しました(2010/7/6)

有限を超えた先にあるもの

2001年頃買った『数学基礎論講義』[1]という本に、超限順序数(transfinite ordinal)とヒドラゲーム(Kirby-Paris' hydra game)の停止性の話が書いてあった。当時は自分の理解力を遥かに超えていたこの本の、しかも特にこの部分が以後9年間にわたって自分の人生を方向付けたのだが、ただし、あまり良い方向にではなかったかもしれない。
超限順序数、特に第二級の順序数(second number class)というのは、集合論で定義される無限大(infinity)の一種である。第一級の順序数(first number class)は、単に自然数 0, 1, 2, .. の別名で、超限順序数はその先、つまり「有限」を「超えた」ところにあるのでそう呼ばれている。最小の第二級の順序数(the first transfinite ordinal, ω)とは自然数全部を集めたものであり、自然数と第二級の順序数全てを集めたものが最小の第三級の順序数(the first uncountable ordinal, $\omega_1$ )である。
計算機科学における整礎半順序(well-partial-order, wpo)、つまり整礎(well-founded)な半順序集合(partially ordered set, poset)の性質とは、具体的なMPUのレジスタ長やメモリの量に依存しない任意の大きさのツリー構造(ノードにさらに別のツリーが際限なくぶらさがっていてもよい)を意味するが、超限順序数は整礎半順序集合の「同型を除いて」一意な「番号」になっている。特に、構造帰納法によるプログラムの停止性証明では現在も順序数表記が用いられることがある。ちなみに、枝の合流を許すものは擬順序(quasi-order)と呼ばれ、こちらも計算機科学ではよく使われる。
ヒドラゲームについては本筋を外れるので詳しくは説明しない。順序数のセマンティクスを与える操作的モデルである。詳しくは[1]を参照。
自分は必要となるいっさいの数学的知識を欠いた状態から、これらが何であるか、何でないかを知るために9年間を空費した。最終的にたどりついたのはほとんど自分にとって現実的な意味を持たない、100年前のフランスの数学[2]であった。

XML、正規表現、順序数

2002年、勤務先でプログラマとしての職業適性が無いことが判明し、以後人事担当者に多大な迷惑をかけながら、社内で部署を点々とすることになる。当時の師匠は構文解析系のツールを作っていた。しばらく転職、自営などを考えていたが、2003年10月、家庭の事情により白紙となる。
2004年1月に、bloxsomでやろうとしていた自分のブログを諦めて、サービス開始からちょうど1年目の「はてな」に id:hubris として登録(現在は消滅)。当時、勤務先ではシステム監視の仕事をしていて、LinuxのマルチホームホストのARP情報の扱いなどに直面していた。
テックバブルが崩壊して数年経っていたが、当時世間ではXMLに対する期待感が大きく、あらゆる業務について瞬く間にDTDあるいはXML スキーマが定義されそうな機運があった。
だが必ずしもプログラマではなく、従って文脈自由言語が何であるかを理解していない作業者が編集するとXMLはしばしば壊れる。Tomcatのserver.xmlを壊したせいで起動しない、というトラブルを何度も見たので自分はXMLの実用性を疑っていた。bloxsomのテンプレートのカスタマイズを実体験して、やりづらいと思ったことも大きかった。
この問題を解消しない限り、XMLは運用の現場で問題を起こしまくるだろう。だから直接XMLを取り扱わないでXMLを編集する安全な方法が必要だと考えていた。
当時、正規表現エンジンをKernighan and Pikeの新しい方そのままにPerlで実装したものが手元にあった[3]。2005年6月、はてなの質問に触発されて、その正規表現エンジンをベースに簡易XMLのパーザを書いた[4]。ネストした要素の名前は、Halabiの本で学んだCisco IOSにおけるBGP4のASパスのように[5]、正規表現のマッチ対象になった。「生け垣オートマトン」の論文[6]も見たことがあったので、当時これを regular hedge expression と呼んでいた。このときはじめて、プログラマ見習い時代の師匠のやっていたことが少し理解できた気がした。
XMLはツリーであり、従って超限順序数と何らかの関係があるはずだ、という着想がどのような契機で湧いたかはいまや定かではない。簡易XMLのパーザでネストしたツリーの構文解析を理解していて、ヒドラゲームを知っていたのだから当然の発想ではあった。例によって何も理解できていないのだが、優れた解説を当時読んだ覚えもある[7]。
2005年秋頃には、超限順序数は要素をソートした後のXMLの「形」に対応するものであって、DOMとかXPathのようなXMLのポインタとしては全く使い物にならないことを悟るに至った。
2004年4月に親を亡くしたので、当時の仕事を続ける動機はなくなってしまっていた。身の振り方を考えたが、自分の競争優位は勤勉さではなく知識量と学習意欲にあるのに、計算機科学の理論的知識が欠けていることは今後の職業生活で致命的だと思った。運用の仕事からはこれ以上何かを学べる気がしなかったので、遺産を頼りにともかく会社を辞めて学べる限りのものは学ぼうと思った。学生に戻るとか大学院に行くことは最初から考えておらず、プログラミングやシステム運用・構築の半端仕事で生活費を稼ぎながら独学するつもりだった。これが間違いのもとだったのだが、今となっては遅すぎる。
JavaScriptがλ計算を世界中のWebブラウザに爆発的に広めつつあった2005年11月、それとはあまり関係なく、計算現象の本質的な「何か」を理解したつもりになった自分は、ひっそりと個人事務所の開設をアナウンスして、会社を辞めた。(続く)

References:

[1] 田中他, 『数学基礎論講義—不完全性定理とその発展』, 日本評論社, 1997
[2] Emile Borel, Leçons sur la théorie des fonctions, 4/e, Gauthier-Villars, 1950
[3] カーニハン, パイク, 『プログラミング作法』, アスキー, 2001
[4] http://q.hatena.ne.jp/1119119220
[5] Bassam Halabi, Internet Routing Architecture, New Riders, 1997
[6] 村田真, 「生け垣オートマトン: XML スキーマの形式的モデル」, http://www.xml.gr.jp/relax/hedge_nice_ja.html
[7] 著者不明, 「計算できない問題・関数について」, http://web.archive.org/web/20060111143714/www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/undecidable.html