東京大学理学部情報科学科のパンフレットがすごい

先日の「ぜひ押さえておきたいコンピューターサイエンスの教科書」というエントリでは、東京大学理学部情報科学科の講義で使われていた教科書を中心に紹介しました。では、実際の授業の様子はどうなのでしょうか？

タイミングの良いことに、情報科学科のカリキュラムのパンフレットがウェブで公開されています。

東京大学理学部 情報科学科 パンフレット

かなりの力作で感動しました。なにせ今まで外向けの色気があまりにない学科だったので。。。 （苦笑）

理学部情報科学科と工学系の学科との一番の違いは、パンフレットにもありますが、コンピューターの原理や理論的背景も押さえ（ここが重要）かつ最先端の技術やモノも作り上げていくところでしょうか。そんな雰囲気を、カリキュラムや実際の講義・演習の様子、教授陣のメッセージなどから、感じ取ってもらえることと思います。

一点だけ補足。このパンフレットには普通の学科紹介でよく見かける卒業生の就職状況の話がさらっとしか書かれていません。というのも、９割近くの人が大学院の修士課程（情報理工学系研究科コンピュータ科学専攻）に進学するのですが、僕の観測範囲内で、ここを出て就職先に困ったという人に出会ったことがありません。修士１年でまったく就活してなくても、修士２年の９月頃に内定が決まる強者とか。巷の就職苦労話と比べると相当浮世離れしている感じです。これは諸先輩方の功績の賜物なのでしょう（パンフレットにも第一線で活躍されている卒業生の方々が紹介されています）

ぜひ押さえておきたいコンピューターサイエンスの教科書

僕はバイオインフォマティクスという生物と情報の融合分野で研究を行っています。東大の理学部情報科学科にいた頃は同僚のマニアックな知識に驚かされたものですが、そのような計算機専門の世界から一歩外に出ると、それが非常に希有な環境だったことに気が付きました。外の世界では、メモリとディスクの違いから、オートマトン、計算量の概念など、コンピューターサイエンスの基礎知識はあまり知られていませんでした。コンピューターサイエンスを学び始めたばかりの生物系の人と話をしているうちに、僕が学部時代に受けた教育のうち、彼らに欠けている知識についても具体的にわかるようになってきました。

バイオインフォマティクスに限らず、今後コンピュータを専門としていない人がコンピューターサイエンスについて学ぶ機会はますます多くなると思われます。そこで、これからコンピューターサイエンスを学ぼうとする人の手助けとなるように、基礎となる参考書をまとめることにしました。

ここで紹介する本は主に英語のものですが、初学者でも読みやすいように配慮されているもの選びました。ただし、ここに挙げた書籍を合わせると、生物学系の定番教科書「Molecular Biology of the Cell」(1392ページ！)よりも分量がはるかに多く、ただ情報を吸収するだけではなく、自ら頭や手を動かして能動的に考えないと理解できないため壁も高めです。挫折しないためには、一度きちんと勉強した研究者のガイドを受けながら読むか、大学の情報系の講義に参加して科目の全体像、重要なポイントを知った上で読むことを「強く」お勧めします。もちろん、自力で読みこなせればそれに越したことはありませんのでぜひ頑張ってみてください。

この分野にこれから入ってこようとしている人をdiscourageさせないようにあらかじめ断っておくと、実はここに紹介してある本の内容を完全に理解していなくても実用上はさほど困らないかと思われます。東大の理学部情報科学科でも、教科書を全部読むような教え方ではなく、本の中の重要なエッセンスを取り出したレジュメをもとに講義が行われています。このように分野の雰囲気、全体像を知ることは大切です。というのも、本当に困るのは、必要なときにどこに必要な知識があるかわからなかったり、目の前の問題を解決するためにどのような考え方をすべきかを知らない場合だからです。僕自身の経験でも、大学の講義を受けているときにはちっとも身が入らずほとんど理解していなかったことが、数年後、キーワードを知っていたおかげで、本を通して読まずとも読むべき場所がわかり、内容がすいすい頭に入ってくることが多々ありました。授業のありがたみはこんなときに実感できます。

まずはOSから コンピューターサイエンスは、理論的なものから実用に近いものまでとても応用範囲の幅広い分野です。その基礎として、まず第一にデータ構造やアルゴリズムの知識をまず学ぶべきだと思っていたのですが、それよりも先に、コンピュータを動かしているOSそのものの知識が必要だったのです。情報屋さんは日頃OSに慣れ親しんでいるので、ここが情報系以外の人に理解されていないのが盲点でした。例えば、コンピューター上でプログラムがどう実行されるのか？１つしかないCPUで、複数のアプリケーションがどうして同時に動いているように見えるのか？（プロセス、スレッド、CPUスケジューリング）、データがメモリやファイルにどのように保存されているか。システムコールとは何か。オペレーティングシステムについて学ぶには、Silberschatz先生による「 Operating System Concepts」が定番で俗に恐竜本とも呼ばれています。アルゴリズムを学ぶ前に、それを動かす大前提となるシステムがどのように動き、どのような性質をもっているのか。情報科学科では、実際にプロセスやスレッドを生成してシェルを実装してみたり、ファイルの読み書きなどを演習しながら、これらの知識を身につけていきます。

計算の理論 計算の数学的な性質について学ぶことは、計算できるものと、できないものの違いを知るために必要です。また、どのくらいの速さ、メモリ量で計算できるか？ それらがどのような計算の仕方で計算できる問題なのか？について学びます。具体的にはオートマトン、正規表現、文脈自由文法、チューリングマシン、計算の複雑さ(computational complexity, NP完全問題など)、判定可能性（アルゴリズムの限界、アルゴリズムで解けない問題というのがある）などが含まれます。MITの屈指の名講義と呼ばれるSipser先生の講義を教科書にした「Introduction to the Theory of Computation」がとても読みやすいのでお勧めです。この本に限っては、日本語訳版も対応の英語付きで丁寧に訳されているので日英での用語の違いに戸惑うこともないでしょう。（注：上記のリンクは初版の日本語訳に張ってありますが、第二版の日本語訳も内容を３冊に分けて出版されています。）計算のクラスを考える必要がある例を挙げると、例えば、正規表現の限界（参考：Leo's Chronicle 「正規表現に見切りをつけるとき」)を考える理由がよくわからなかった場合は、この本の内容が参考になります。



計算理論に関しては、Garey and Johnson本「Computers and Intractability: A Guide to the Theory of Np-Completeness (Series of Books in the Mathematical Sciences)」も定番中の定番です。読みやすく（易しいという意味ではなく、簡潔という意味です）、NP完全であることの証明パターンや、そのための巻末のNP完全問題のリストが役に立ちます。この本の「Coping with NP-Complete Problems（難しい問題といかに付き合っていくか）」という章のタイトルは非常に有名で、コンピューターサイエンスという学問を如実に表している表現です。




データ構造とアルゴリズム 離散数学とも呼ばれるこの分野。日本語で平易に書かれた教科書もあるのですが（例えば、データ構造とアルゴリズム (新・情報 通信システム工学)や、計算とアルゴリズム (新コンピュータサイエンス講座)など）、やはり、list、hash、red-black tree, ネットワークフロー、グラフ、木構造など主要なデータ構造をカバーしつつ、NP完全性や集合論などの数学的な基礎知識も巻末に儲けられている「Introduction to Algorithms, Third Edition」が便利です。今月には第３版も出るようです。ただし、内容が豊富で記述も多いため、初学者が通して読む目的には向かない本だとは思います。上に挙げたデータ構造について学んだあと、一通りの手法（Greedy（貪欲）アルゴリズム、分割統治法、Dynamic Programming(DP)、近似、Randomizedアルゴリズムなど）を身につけたい場合は、「Algorithm Design」の方が講義用に構成されている分読みやすいかと思います。

連続系アルゴリズム 工学的には、離散値だけではなく、実数データを扱ったり、固有値問題や、偏微分方程式をCG法(共役勾配法）で解く、波形データの解析のために高速フーリエ変換(FFT)を使う、統計量の計算、検定など、計算機が活躍する場面が多々存在します。これらの計算は並列化して高速に計算する需要も大きく、そのような連続系の計算を理解するのに役立つのが「Numerical Recipes 3rd Edition: The Art of Scientific Computing」です。計算を手法とソースコードの双方向から学習できるので、演習向けです。大学の線形代数の内容も、ここにあるような実際の計算までやってみるともっと楽しくなるように思います。最新版ではSVM（Support Vector Machine）やHMM(Hidden Marcov Model)まで言及されているとか。



ハードウェア レジスタとは何か知っていますか？ マシン語は？ 計算機の中で整数や小数点以下の数はどう表現されているの？などなど、JavaやRubyなど現代の便利なプログラミング言語しか使っていないと見えなくなってしまうハードウェアの世界を学ぶためには「コンピュータの構成と設計~ハードウエアとソフトウエアのインタフェース 第3版 (上), (下)」が良いでしょう。（注：通称パタヘネ本です。ヘネパタはまた別の本のことです）計算機科学はハードウェアとともに進化してきました。最新のCPUの内部構成を理解するには、レジスタ、計算のパイプライン化、割り込み、キャッシュなどの知識が不可欠ですし、これらを学べる本も、他には見当たらなくなってきました。同じメモリアクセスでもキャッシュに載っている場合とそうでない場合（localityの有無）で相当の性能差があるので、CPUの中身でどのように演算が行われているかを知らないと、CPUの性能を最大限引き出したプログラムは決して書けません。一度は目を通しておくべき本だと思います。

情報論理 アルゴリズムを設計したとき、それが正しい結果を出すこと(soundness)、そしてそのアルゴリズムがすべての答えを見つけ出すこと(completeness)を検証します。このようなsoundness/completenessの概念や、述語論理でロジックの等価性を証明したり、逆に背理法などで矛盾を導きだす技術もどこかで学ぶべきだと思います。萩谷先生の情報論理の講義資料が手軽に学べて良いと思っていますが、まとまった英語の教科書があればぜひ教えてください（識者の方）


プログラミング言語　といってもC++やJavaなどの言語の仕様のことではなく、λ計算、型情報などを用いてプログラムやその意味を数学的に表記する（操作的意味論を用いる）ことで、言語の仕様を正確に定義するのに使えたり、プログラムの意味を変えずに最適化（等価変換）する、また、プログラムが安全に実行されるかどうかを検証できるようにもなります。Pierce先生の書いたTypes and Programming Languages（TAPL）が非常にわかりやすく必要な知識がまとめられた本だと思います。

蛇足ですが、近年日本のインターネット界隈でSICPがプログラミング言語を理論的に学ぶ本として話題になっているのですが、コメント欄で住井先生が指摘されているように、SICPとTAPLではカバーしている世界が違います。僕自身も、この本をベースにした演習をしたり、最後の章にあるようなSchemeでSchemeコンパイラまで作った経験から、SICPだけで関数型言語の勉強をした気になってしまうと視野が狭くなるように思います。関数型言語に慣れたり内部の仕組みを知るにはSICP、操作意味論や型について学ぶにはTAPLが良いでしょう。

(注：このプログラミング言語に関する部分は僕の説明や用語の使い方が悪い書き方になっていたため、住井先生の指摘を受けて書き直しました。そのため、下の方にある住井先生のコメントが指していた内容がわからなくなってしまいました。すみません。）



コンパイラ テキストデータを解析するには書かせない技術です。字句解析、構文解析に始まり、構文木から実行したいコードを作成。コード内で変数の生存範囲を見て最適化を施すなどなど。プログラミング言語を作る以外にも、独自データを表現しやすくするためのデータフォーマットを作ったり、ミニ言語を作って日頃の作業を効率化するなり、身につけると非常に強力な武器になります。Compilers: Principles, Techniques, and Tools (2nd Edition)、通称Dragon Bookが一応教科書的なポジションを占めているのですが、最初から読むと構文解析すらできないうちに挫折する可能性が高いので注意。おすすめの読み方は、実際に使うツールに合わせて読むこと。例えば、ANTLRを使うならLL(1)文法を、Lex/Yacc（Flex/Bison）を使うならLALR(1)文法を知らないとデバッグすらままならないので、必要に迫られて本の該当箇所を読む使い方が良いように思います。てっとり早く内容を把握するには、萩谷先生のコンパイラの講義資料を参考に。簡潔にまとまっていて、本を読み解くのに役立ちます。



データベースシステム Webやユーザーからデータを集めて管理、表示するWebアプリケーションでは、データベースの存在が必要不可欠になってきました。バイオインフォマティクスでは、毎日テラバイト規模のデータを扱う技術が必要になってきています。データベースに関する教科書は、以前 Leo's Chronicle:ぜひ押さえておきたいデータベースの教科書で紹介しました。Raghu本 Database Management Systemsがお勧め。ストレージ管理、データベースの同時更新をさばくためのトランザクション管理、これらの技術は年々重要度を増してきていますし、Google File Systemに代表される分散ストレージや、SSDの登場による時代の変化などに対応していくためにも、データベースシステムの仕組みはぜひ押さえておきたい知識です。


ここに紹介した他にも、コンピューターグラフィックス、自然言語処理、機械学習、データマイニング、ウェブ情報処理、ゲノム配列用の文字列検索、索引、圧縮データ構造、Information Retrieval (IR)など、ここでは紹介しきれないほど、コンピューターサイエンスの応用は多岐に渡っています。そして、教科書にある知識を身につけることも大切ですが、より大事なのは、それらを活用して、コンピューターの力を応用できる分野を切り開いていくことだと思います。

（このエントリを書いているうちに、自分の知識の浅さや分野の広さにくらくらしてきました。他にもコンピューターサイエンスの基礎として勉強すべき分野、良い教科書があるよ、という情報を教えていただけると幸いです）

関連

• 東京大学 理学部情報科学科のカリキュラム （このカリキュラムの２〜３年次の内容はカバーしたいと思ったのですが、これだけ並べてもまだ覆いきれてない気がします…）
  

正規表現に見切りをつけるとき

Perl, Rubyなど手軽に使えるプログラミング言語に慣れてくると、あらゆるテキストデータの処理に正規表現(regular expression)を使ってしまいがちです。

けれど実は、正規表現の処理能力を超えるフォーマットというのが存在します。その典型的な例が、XMLやJSONのように、入れ子になったデータフォーマットです。

例えば、

(a, b, (c, d))

(a, b, (c, (d, e)))

というように、括弧がどんどん入れ子になっていく構造は、括弧のネストの深さを数えないと正しく解釈できません 。正規表現でも、一番外側の括弧の対応をとらえるために、/\(.*\)/、/\([^)]*\)/ などとはは書けますが、常に正しい括弧の対応をとっているとは限りませんし、もしうまくいったとしても、さらに内部の括弧をとらえるために、外側の括弧を取り除き、また同様の正規表現を内部の文字列に対して繰り返して適用する必要があります。

そして問題なのが、

(a, (b, c)), d, (e, f)

という文字列の場合。/\(.*\)/という正規表現では、以下のように色のついた範囲を拾ってしまいます。

(a, (b, c)), d, (e, f)

正規表現では、このようにちょっとしたデータ構造すら上手く構文解析できません。したがって、正規表現だけで文字列を処理する場合は、何らかの方法で括弧が2重、3重にならないように工夫する必要があります。（あるいは括弧内を再帰的に処理するプログラムを書くなど。）バイオ系のデータフォーマットでも、この正規表現の能力の限界を知らないがために、正規表現で処理できない入れ子になったデータを平気で書いてしまう人が多いので、手軽に処理したい場合は要注意です。（他にも2重引用符で囲まれた文字列の扱いも、正規表現では面倒な例です）

構文解析

では、正規表現の能力を超えるデータはどう扱えばいいのか？一番のお勧めは、ANTLRを使って字句解析(lexer)、構文解析(parser)するプログラムを生成する方法です。一昔前なら、lex/yacc、flex/bison, JavaCCなどしか選択肢がなかったのですが、今は断然ANTLRが便利です。ここでは、JSONを例にとって説明します。以下は、JSONで書かれた配列の中に配列がある構造です。

[0, [1, 2]]

字句解析では、これを、

LBracket([), Number(0), Comma(,), LBracket([), Number(1), Comma(,), Number(2), RBracket(]), RBracket(])

というようにトークン（文字列の単位, lexer ruleとして記述）に分解していきます。そして、これらのトークンにマッチする文法（parser rule)を定義します（以下の例は、説明のために他のデータ型については省いて簡潔に書きました）

array: LBracket Value (Comma Value)* RBracket;

value: Number | array;

ここでは、括弧 [ ] の中に、ValueをComma(,)でつなげて複数個書けるルールを定義しています。Valueとしては、数字(Number)以外に配列(array)も使えるので、配列の中に配列があるような入れ子になったデータ構造もこれで解析できます。

参考までに、僕がANTLRで作成したJSONの文法を紹介します。ANTLRの記述を覚えるコストはかかりますが、1ページ分の記述量でJSONのように構文が複雑なものも処理できるようになります。以下に挙げるのは、ANTLRのリファレンス（英語）と、その背景にある理論の教科書で、コンピューターサイエンスの学科では講義によく使われていてどれもお勧めです。Aho, Ullman先生らのドラゴンブック第2版（Ullman先生の息子さんがCGで表紙を作ったとか）は読みごたえ十分ですし、Apel先生の本ではVisitorパターンの使いどころのような、実装に近い話題にも触れられていて読みやすいです。稲葉君絶賛のParsing Techniquesなどもあります。

構文解析の実践としては、ANTLRをダウンロードするとサンプルの文法がたくさん付いてくるので、それを真似して書くのも習得への早道かと思います。一度ANTLRで文法を書くと、Perl/Ruby/C/C#/Javaなどの言語用のlexer/parserを生成できるようになるので、どの言語を使っている人にもお勧めです。しかし、まだ日本語のリファレンスがないのが構文解析の敷居を高くしている原因でしょう。この記事が素晴らしき構文解析の世界への足がかりになればいいなと思います。

（実用上の補足）

正規表現の中に自己を含めて循環定義できるRubyやPerlなどの処理系なら、入れ子もなんとか処理できるみたいです。以下はPerlのコード例。(「詳細 正規表現 第3版」を参考にしました）

$str = "(a (b, c)), (d), (e, f)";
$paren = qr/\([^()]*(?:(??{$paren})[^()]*)*\)/;
while ($str =~ /($paren)/g) {
print $1, "\n";
}

実行結果

(a (b, c))
(d)
(e, f)

括弧のパターンにマッチすると、その都度中身の正規表現がlazyに変わっていくというトリッキーな技です。このような正規表現は以下に述べるような形式言語理論上の正規表現の定義には含まれないのでご注意あれ。ただ、Perlで処理できるとしても、二重引用符とか、様々な括弧の種類に対応するように再帰型正規表現を書いていくと、ANTLRのparser ruleを書くのと似た状況になるとは思います。(追記）Perl6のRulesという機能では、ANTLRのような文法定義を書けるとか！ 入れ子が必要なときは、これを使いましょう、ということですね。

(コンピューターサイエンス的な補足）

細かい話をすると、正規表現は文脈自由文法というクラスのサブセットで、入れ子の構造をもった文法は、文脈自由だけれど正規表現ではありません。これは、pumping lemmaを使って証明できます。情報系の学科なら、計算量理論などの講義で習うはず。オートマトンにスタックをつけたプッシュダウンオートマトン（文脈自由文法と同じ表現能力を持つ）なら、このような入れ子をうまく処理できます。このあたりの話は「計算理論の基礎」という教科書に丁寧に書かれてあって（大学院入試の勉強のときにかなりお世話になりました）、コンピュータサイエンスの基礎のうち、オートマトン、NP完全問題など計算量にかかわる部分について学ぶのに優れた本です。（最近は第2版もでているようですが、3冊に分かれてしまって少々買いにくくなってしまいました。分けた方が持ちやすいのかな？）

学校でしか教えてくれないプログラミング言語のこと

Scheme（スキーム）というプログラミング言語について初めて知ったのは、大学2年生のときです。理学部情報科学科に進学し（東大には進学振り分け（通称：進振り）という制度があって、大学2年生の前半までは一般教養を学び、それ以降から専門課程に進みます）萩谷先生担当のプログラミング演習がSchemeとの出会いでした。（当時のものとは大分違いますが、参考までにSchemeの講義資料へのリンクです。http://www-ui.is.s.u-tokyo.ac.jp/~hara2001/scheme/)

おそらく、ここで学ばなかったらSchemeのように一般に知られていない言語には触れることもなかっただろうし、Emacs Lispのプログラム（Schemeと同様の構文です）を自分で書くこともなかったように思います。Emacsというテキストエディタは、自分好みの機能をLispを用いて実装することが醍醐味です。今でも、簡単な計算はLispで書いて、Emacsを電卓代わりにしています。（以下は、階乗の計算をちょこっとLispで書いてみた例。xのn乗を再帰で計算する関数pow(x, n)）：

括弧が多くて「何だこれは？」と思われそうですが、括弧の対応付けはエディタが視覚的にサポートしてくれるので、式そのものの見た目ほど入力は大変ではありません。

実用性という意味では、Schemeは非常にマイナーな言語だと思います。けれど、再帰であったり、リスト構造であったり、環境（変数などの状態を運ぶもの。継続とかもそう）であったり、λ関数（クロージャと言ったほうが良いかな？）など、プログラミングで重要な概念を学ぶのには良い言語だと思います。型を学ぶにはOCamlなどML系の言語の方が適しているので、そちらを授業に使う大学も多いようです。

Schemeに関しては思い入れが深く、僕にとってはEmacs（Windows版はMeadow）を使い始めたきっかけでもあるし、情報科学科のCPU実験で、Scheme言語を使って、Scheme言語のコンパイラ(自分達で作るCPU用のアセンブリを生成します）を作ってしまうくらい深く関わった言語でもあります。言語の仕様書（当時はR5RS）もそれなりに読みました。

それを最後に、久しくSchemeから離れていたのですが、思い出させてくれたのが以下の公開質問：

「プログラミングに詳しい人に質問です。大学でプログラミング経験の学部一年生向けにプログラミングを教えることを想定しています。週１コマ×半年程度の限られた時間で、プログラミングとはどういうものかという本質を教えたいのですが、どの言語を使うのが適切でしょうか。」

ここでは、プログラミング言語の種類をあまり知らない人を解答対象からはじくために、以下のような質問肢が用意されています。一般の人よりは僕はSchemeを知っていると踏んで、これを読んだときの僕の思考過程（赤文字）も併記しました。

* Schemeは1.5からオートボクシングの機能をサポートした
auto-boxingってJava…
* Schemeはインデントによってブロックを表現する
そんなわけない。括弧だよ
* Schemeは多くのレンタルサーバに標準でインストールされている
もしそうだったら凄い！
* Schemeでは関数がファーストクラスのオブジェクトである
Schemeで言うオブジェクトって何？単にデータという意味だとすると'A (文字を表すsymbol)とかあるし…。(cons 1 2)だと、関数が１と２のペア表すデータ型（オブジェクト）と捕らえることができるけど。。。
* Schemeの文の終わりはセミコロンである
違う違う。
* Schemeは純粋関数型言語であり、副作用はモナドでくるむ必要がある
副作用がない関数型言語って、関数の外側の変数を変更できないってことだよね。そんなことはなかったような、、そもそも、モナドって何？と焦りグーグル検索。。これHaskellに出てくるのか。。
* Schemeは型に厳格なため整数の加算と浮動小数点数の加算の演算子が異なる
そういえばSchemeで型を意識したことがない。。。
* Schemeは関数の呼び出し時に括弧を省略することが出来る
そんなsyntaxあったかなぁ。。。たぶんない。
* Schemeのマクロ定義には#defineを使う
C/C++だよ、それ。(define f (x) ...)はあるけど。
* Schemeの言語仕様はキューマシンとしての実装に適しているため並列化が容易である
キューマシン -> 並列化が容易というロジックにとっても飛躍を感じるなぁ。副作用無しの純粋関数型の範囲なら、Googleのmap-reduceの概念のベースになっているように簡単に分散できるけど。。。
* Schemeのブロックはbeginで始まりend.で終わる
これは違う。
* SchemeのコンパイラとしてはGHCが有名である
GHCって何?聞いたことない。Googleで検索…またHaskellですか。。。知らないよ（涙）

と、まぁ、大変でした。なぜって外部情報で補完しないと正解が出せない質問がたくさんあるから！「多くのレンタルサーバーに」って。。。「多くのレンタルサーバー」の現状を知らないとわからないし。本格的なSchemeの使用例が見当たらないって理由で推測はできるけれど。他にもSchemeにはまだ僕の知らない構文があるのかも…とか不安に思ったり。それでも、Googleで検索すればそれぞれ1分と経たずにわかる程度のことだと思います。とても懐かしく、かつ、知らないことも多くあったので知的な刺激になりました。

プログラミング教育用としての関数型言語

こと、教育のためのプログラミング言語の選択に関しては、ネットワークに接続したり、データベースを使ったプログラミングが必要なら、現時点では迷いなくJavaを選択します。動作させやすいこと、使っている人が多いためEclipseのような使いやすい開発環境が整っていることが選択の理由になります。

Scheme, Lispのような関数型言語の肝は、副作用がないという点だと思っているのですが。たとえば、Googleが超並列計算に使用しているMapReduceのフレームワークでは、

map(入力を2倍にする関数f, {1, 2, 3, 4, 5}) => {f(1), f(2), f(3), f(4), f(5)} = {2, 4, 6, 8, 10}

reduce(入力を足し合わせる関数h, {2, 4, 6, 8, 10}) => 30

というmap, reduceという２つの手続きで計算を行います。map部分をScheme(Lisp)的に書くと、

上のようになります。map関数では、入力リストの先頭(car)から順に関数fを適用していきます。たとえば、以下のような式

の結果は、{2, 4, 6, 8, 10} になります。関数の引数に関数f（lambda文を使ってxを2倍する関数を定義している）を渡して、内部では{(* 1 2), (* 2 2), (* 3 2), ... }を計算しています（+演算は前置記法）。ここで大切なのが、map関数内で、関数fの実行順に制約がないということです。つまり、個々の関数fの実行では副作用がない（！）ので、どの順番で実行してもよく、この部分を言語の実装次第で並列化することができます。

GoogleのMapReduceではこのような副作用がないというプログラムの意味(semantics)を活用して、個々のmap操作を別々のノードに計算させて超並列化を可能にしています。関数型言語を用いるとこの副作用のない部分を明確に記述できますし、驚くほど多くの計算がmap-reduceの組で書けるようです。例えば、forループで先頭から順に辿らなくても良い場合が見つけやすいと思います。Googleは並列化を促進するために、入力listのコピーをいつくかのノードに分散して配置する工夫も行っています。検索エンジン用の索引構築なども、このMapReduceのフレームワークで再実装したとMapReduceの論文には書かれています。

再帰の概念は他言語でもよく見かけますが、関数型言語の特徴である副作用がない（データすら関数で表現されている）コードの書き方というのは、手続き型言語であるJava, C/C++など、実際の開発現場でよく使われるプログラムの書き方から入った人には、とても気付きにくいものだと思います。関数に関数を渡すという概念も、何十年も前の関数型言語の研究から、他に移殖されたものです。

これらの通常では気付きにくい概念や、既に一般に当たり前のように使われていることの裏にある理論を教えるのが大学のあるべき姿であると考えます。特に、簡潔な記述で速く動くことに主眼に置くcomputer scienceの分野では、プログラミングの授業も、言語を問わず、一般の技術者向けの勉強本では深く触れられていないような、本質の部分をカバーすべきでしょう。そうすることで、近い将来、新しいプログラミング言語が出てきても、プログラミングの歴史と比較して、新しい部分、重要な技術などをはっきりと認識できるようになり、言語を使いこなす能力をもったプログラマを育てることにつながるのではないでしょうか。

（追記）

そもそもプログラミングの本質って？

プログラミングの本質をどこに据えるかで言語の選択は変わりますね。省メモリ・並列化が主眼なら副作用、同期などが重要なのでアセンブリ、C/C++などlow levelに近いもの。オブジェクト指向ならJavaなどデザインパターンの威力が見せられる言語が良いと思う。簡潔さ、手軽さが大切ならPerl, Rubyとか。関数型という意味では、Scheme, Lispも面白いけれど、Ocamlも良さそう。Python, Haskellとかは詳しくないので…。

教育で大切なこと

実際、講義の中や在学中に本質を理解しきる必要はないと思うのです。僕自身、関数型言語とMapReduceの関係なんて、卒業した後に初めて理解したものです。気付く人もいれば、数学と同じでまったく使わない人もいる。ただ後になってもう一度学習しようと思ったときに、入り口の部分を見せてもらっているのとそうでないのとでは、学習効率（学ぶことへの抵抗感）が相当違います。だから、1から10までを教えるのではなくて、1を見せることが「教育」で本当に大切な事だと感じています。

SIGMOD 2008 Repeatability Assessment

今年のSIGMOD 2008から始まったRepeatability Assessment。論文中にある実験結果が第三者によって再現できるかどうかを確認する趣旨のものです。

実行可能なバイナリやソースコードを送り、実験結果を相手方のマシンで検証してもらいます。並列分散計算とか、マシン環境がないと再現しにくいものもあると思いますが、scalabilityとか、result sizeなどなら、傾向として一致することは確認してもらえます。

論文誌と同時に公開されるであろうコードを使って、比較実験がしやすくなるだろう、という期待はあります。他人のアルゴリズムを実装するのは常に大変なので。ただ、コードが入手しやすくなると言っても、フェアな比較になるように気をつけて（実装言語、applicationの違いとか）、かつ性能差の定性的な原因を明らかにしないと、研究としては面白くならないと思います。

ちなみに今回の評価は簡単なものでした。以下、抜粋。
-----
Overall repeatability : Strong Accept

Summary: Figures 16,17 and 19 were successfully repeated.

Details: Output (truncated because of the conference tool editing limits):
synth.tab
query fanout scale mode trial time
q5 2 1 0 1 0.125
q5 2 1 0 2 0.125
...

Were you able to install the software? : Yes
Were you able to run experiments? : Yes, all of them
Were you able to repeat experimental results? : Yes, all
Was the submission well-formed (valid and meaningful XML file etc.)? : Yes
----

実は、このfeedbackを得る前に、「プログラムが動かないよ」、という返事が来て、原因を調査したら、送ったコードに、Visual Studio C++ 2005 (SP1)の配布用DLLが含まれていなかったようです。慌てて返信したところ、無事プログラムが動いたようです。Visual Studioが入っていてもだめみたいで、SP1のDLLが必要だったところが盲点。今度から、仮想マシンで実験しておかないとだめですね。Javaだとこの類いの問題が少ないので楽なのですが。


実験を再現するためのMakefileやら、スクリプトを書くのは割と面倒だったのですが、意外なことにその努力の結果は自分に返ってきました。追加実験をするときに同じスクリプトが使えました。自分のプログラムの使い方の備忘録にもなっているし、後々になってわかる良いところが多数。

今度から、実験結果はSQLiteのDBにでも入れて、平均や標準偏差を取ったり、グラフを書く作業もgnuplotを使って、自動化できるようにしておきたいなと思いました。（今回は楽をしてExcelで書きましたが、自動化してなかったので書き直すのはやはり手間だった）

SIGMOD 2008に通りました！

今朝から興奮しっぱなしです。

2月16日が結果発表だったはずなのですが、アメリカ時間で17日になっても返事がこないまま、今日、朝一で見たメールがこれ。

Congratulations! Your paper:

Paper#: 7 Title: Relational-Style XML Query

has been accepted for SIGMOD 2008.
Altogether there were 435 papers submitted and only
78 accepted.


Author Feedback時のReviewerのコメントが良い感じだったので、このまま行くかな、と思っていたのですが本当に通ってくれて一安心です。

435 papersという数字。最近のSIGMOD, VLDBなどのデータベースのtop conferenceは通常600本近くの投稿があるのですが、今回のSIGMODからソースコード（or バイナリ）の添付が求められたので、これで、数が減ったのかもしれません。僕は実装好きなので、運も味方したのかな？Registration時の登録番号も７だったし縁起が良かったです。

SIGMODは学部時代、研究室に入ったときからの目標だったので、実に6年越しの夢がかないました。日本人グループで、SIGMODに通るのっていつ以来なんだろう？ 櫻井さんという方が海外のチームと共同で2005年に採択されているみたいですが、本当に日本人のみのグループを探してみたところ、1998年の喜連川先生のチーム以来みたいです（間違っていたらごめんなさい）。

これで、日本でも頑張れるんだ！って日本のDB業界が発奮してくれるといいなと思います。僕自身も、DBもXMLもまだまだ使いやすくなっていないので、研究者としての仕事はたくさん残っています。ようやくスタート地点に立てたような気分でもあります。

僕を支えてくれた妻と子供、そして家族に感謝。
論文のパラグラフごとに、細かい表現の修正につきあっていただいた先生に感謝。
博士論文の審査で貴重な意見をくださった先生方に感謝。
この研究につながる強い動機をくれた研究室の同僚に感謝。

今日、研究を続けるモチベーションという、とてもいい栄養をもらうことができました。
ゴールはここではありません。今後も、DBの発展のために貢献していきたいと思います。

修士論文発表会

昨日、修士論文の発表会を覗いて来ました。写真は大学時代のサークルの後輩でもある阿部君と西川君。二人ともきちんと動くものを作っているあたりがとっても優秀な人です。

さらっと発表してしまった内容でも、同じ場をくぐりぬけてきた経験から、その裏側には相当な努力があったことを察することができます。関連研究を調査して、研究テーマを絞り、独自の貢献を考え、それを形にする。言うのは簡単ですが、実現するのは大変なことです。

でも、そんな優秀な2人でも、攻撃されてしまうのが、修士論文発表の場。目の前で聞いているのが学部生のころからの師匠ともいうべき先生方なのですから、当然ですね。そんな先生と言えども、研究の内容を発表する側より理解しているということはまずありません。だから、うまく攻撃を交わすコツは、きっと、聞いている先生の目をみて、内容の理解を確認しつつ、対話するように順次プレゼンを進めていくことなんだと思います。

「ここまでは大丈夫ですか？」などと確認することで、質問する側も的外れなことを言っている不安から開放されてポイントを絞った攻撃になるので、答える方も対処しやすくなるのかと。 勉強になりました。

今後、それぞれの道に進む2人ですが、自分の魅力を最大限に発揮できるように、頑張ってもらいたいですね。

[TeX] 論文執筆のサイクル短縮

いろいろためしてみたけれど、どうやら、TeXで論文を作成するときは、PDF形式でpreviewするのが最速のようです(Windows環境において）。

こんな発見があったのも、今まで使っていたMikTexのYap(DVI viewer)が、最新版のものでは過去のものより処理が遅くなってしまって、版を確認するのに時間がかかるようになってしまったから。

texを書いてはdvi形式で確認していたところを、代わりにPDFを生成するようにしたら、かなり快適になりました。キー１つでtexをコンパイルして、PDFを一発表示できます。

ポイントは、

• pdflatexで、texからpdfの生成
• pdflatexはeps形式の画像ファイルを扱えないので、epstopdfを使うか、distill（角藤さん作成）でコマンドラインからAcrobat Distillerを呼び出して、eps->pdfへの変換をする
• というか、画像は最初からPDF形式で作ればいい
• eps、pdfの画像形式を両刀で使えるようにするには、\includegraphics{filename} と書けば、latexのときはfilename.epsが、pdflatexのときはfilename.pdfが読まれます。
• Acrobat Readerは、ファイルを開くとロックしてしまうので、pdfopen, pdfcloseコマンドでpdfファイルの開け閉めをする
• pdflatex, bibtex, pdflatex, pdflatexというサイクルを1度実行したら、次回は、pdflatex一回で済ませる
  
• これらの作業をまとめて行うMakefileを書く
• PDFを閉じる - pdflatex - PDFを開く
• 以前見ていたページに戻るために、Acrobat Readerの方で、以前表示したページを開く、という設定にする
• Emacsを使っているなら、smart-compile.elなどを活用して、makeコマンドを簡単に呼び出せるようにする。
• TexnicCenterなどを使うともっと簡単に、使用するコマンドの定義ができるでしょう。

tex file -> latex -> dvipdfm -> PDF fileという流れ（10秒以上はかかるかも）よりは、もちろん高速。2秒くらいでPDFを表示できます（数十ページの文章なら）。ただし、dvipidfmを使ったほうがコンパクトなPDFができます。

これでWISYWIG(What You See is What You Get)でないTeXの欠点が補えます。dvioutやyapは、画像の表示が遅いし、gsviewはPDFも表示できるけれど、viewew自体があまり使いやすくないのです。

長年の悩みの種がようやく解決して、とっても快適になりました。おすすめの方法です。