大規模なウェブサービス、そしてそれらを構築するプログラミング言語 Peter Norvigによって行なわれたプレゼンテーションの写し どうすればウェブ上ですぐに金持ちになれるかついて多くの話があった。それ で、それをするために何が必要なのか? 最初に、有用で金になるアイディアが 必要である。それから、利用可能な何らかのソフトウェアが必要である - そ して、利用可能と有用は異なる。有用とは何かよいことを行なうことを意味し、 利用可能とは使用が容易でなければならないことを意味する。また、それは何 らかの点で競合よりもよくなければならない。次に、それにともなって何らか のハードウェアを必要とするだろう -- そして、それがウェブベースである場 合、週に7日24時間動作し、必要なトラフィックをサポートしなければならな い。最後に、人々が必要である - それがもっとも重要な部分である - エンジ ニアとマーケティングのような全ての技術以外のスタッフの両方が。 いくつかの独自のアイディアの例がある: Junglee, BeOS, ITA Software, (残 念ながらもはや我々といっしょではない)Whizbang Labs, そしてGoogleである。 今日は、私はGoogleに焦点をあて、ほとんどはソフトウェアについて、ハード ウェアについて多少話そうと思っている。 ハードウェア Googleでは、我々は10000以上のサーバボックスをもっており、なおも加え続 けている。この写真の中では、マシンルームの床の上に特別のファンがあるこ とを見ることができる. Googleが与えられた共同空間に対してどのくらいの 電力が必要かに関する規則を破ったので、それはそこにあるのだ。 おもしろいことの一つは、いったん10000ものサーバを得ると、メインフレー ムの時代にほとんど戻ることである。以前はコンピュータはとても高価でプロ グラマは本当に安価だったので、あらゆることはこれらの巨大なメインフレー ムの利益になるように行なわれた。それから、我々はワークステーション時代 に入り、そこでは経済は逆転した。10000ドルで素晴らしいワークステーショ ンを入手でき、プログラマはもっとずっと高価だった。 現在では、10000のサーバとともに、我々は経済を再び以前のように切り替え た。以前は、開発者の速度を二倍にできるならそれは本当にすごいことで、ハ ードウェアのコストがどれくらいかはそれほど問題ではなかった。これは Googleでは真ではない。我々のコードが2倍遅く動作するなら、数千万ドル分 の費用がかかるだろう。 個々のマシンの故障は同様に避けがたい問題である。Googleの一'日'は一つの マシンの27年以上と等価である。それはあなたのマシンが一年に一度故障する 場合、一時間に少なくとも一つのGoogleマシンが故障するだろうということを 意味する。だからレッスン番号1は冗長性、そして冗長性である。我々はこれ らのシステムが動作することを確実にしたい。 どのくらい多くのマシンがダウンするか見積もるために使えるいくつかの指標 があり、もっとも普通のものは平均故障間隔(mean time between failures)で ある -- それは何かが故障する前に費やす平均時間である。Berkeleyの Pattersonのような人々は、現在ではより適切な統計値である平均復旧時間 (mean time to recovery)について話している -- 一度故障になってから、直 るまでにどのくらい長くかかるかである。 Googleでは、もっとも重要な因子は平均ページ間隔であり、我々は故障は始終 発生するが動作し続けるシステムを構築した。サイトの停止は選択肢にはなく、 我々はけっしてダウンさせたことはない。これは重要である。なぜなら、ポケッ トベルを身に付けている場合、あなたは朝の3時に眠ろうとしているかぎり単 一のディスクがクラッシュするかどうかをあまり気にしないだろうから。 さて、検索エンジンとは何か? 検索エンジンはユーザの問い合わせに関係する 情報を表示する。我々はもう少し後でどのような種類の情報、関連、問い合わ せかについて話すつもりである。私はWebとAIについて、そして、誰もが興味 があるからGoogleについて話すつもりである。Lispとプログラミングについて も話すつもりである。 AIを使う 知識ベースとコーパスベースのアプローチの間の区別について話したいと思う。 AIは知識ベースの努力であり、本当に世界について知っているあらゆることを 努力して書き下そうとすることになっていた。それはたいへん時間がかかる困 難な仕事だった。人は多くの過ちを犯し、それからそれらをデバッグしなけれ ばならなかった。 現在では別の選択肢 - コーパスベースのアプローチ - がある。それは人は一 群のテキストを分析し、その結果テキストの著者が全ての仕事を行なっている ことを示す。自身でデータベースを構築するのに十人年を費やす代わりに、誰 か他の人によって作られたウェブ上の30億ページがその情報のいくらかを取り 戻すようにさせる。そして、1パーセント、0.1パーセント、あるいは0.01パー セントしか取り戻せない場合ですら、手で知識をエンコードすることに対比し て、全体的にはなおも大きな利益を与えるだろう。 私はAssociation for Computational Linguistics Conferenceで話をし、計算 機言語学者はこの方法論を使っている。彼らは、文法学者が座り、知っている ことを書き下し、それからそれを行なうプログラムを書くような知識ベースの アプローチを用いて始めた。何年かの間、統計に基づくアプローチの方向にずっ と移っている。 私はこの一例を与えたかった。Eugene Charniakは、私は彼からLispを習った のだが、Wall Street Journalからのコーパスを用いることで、括弧に入って いる句 -- 名詞句や動詞句など -- で90%の正しさに達するパーサを書いた。 この数値は以下のようにしてマークされた - 人々は手で名詞、動詞、その他 を識別し、彼はそのデータに関する問い合わせ的な知識を用いずにプログラム を訓練し、90%の正確性を達成できた。それで、これは何を意味するのか? こ れは、彼は辞書、存在論、あるいは知識ベースやその他のものをもたなかった ことを意味する。そして、それらを得るための全ての困難を通過した場合です ら、彼は最高でも10%の改善だけしか得られなかっただろう。だから、アイディ アは、どこが10%であるかではなく、どこが90%であるかを探すことに我々の時 間を費やすことである。 これを行なうための別の方法は、より多くのテキストを得ることである。言語 学のコミュニティは多くのテキストをまとめてきた。あるプロジェクトは当時 は巨大だった百万語のコーパスを用いて1961年にBrownで始まり、それ以来、 他のプロジェクトは数千万語にまで達している。現在では全てのテキストはイ ンターネット上で利用可能である。 ここに、Doug Lenatによる知識に基づくアプローチを例証する一例がある。彼 は、人々が知っているがほとんど話さないこのようなものが全てにおいてある と言う。たとえば、彼は"水は低い方に流れる"や"生きているものは病気にな る"を引用する。彼は百科辞典の中の全ての資料をエンコードしようと最初に 決心した; しかし、彼は真に重要な情報は百科辞典にはけっして入らないよう なもの - 後になってではなく幼稚園で学ぶもの - であることを理解した。 私は、手でこれらの情報全てを入力することが本当に必要かどうか疑問に思っ ていた。私は検索エンジンに向かい、フレーズ"水は低い方に流れる"をタイプ して、1200の結果を得た。これは実際にLenatが言ったこと、人々はある種の 重要な事柄についてほとんど話さないということのものすごい検証である。彼 は99.9996%正しかった。しかしそれでも、30億ページをもっている場合、曖昧 なクエリーに対してすら結果はそこにある。次に、私は答えを前もって知って いることなしにどのように結果を得られるかを示したいと思ったので、"生き ているものは得る"とタイプし、生きているものが得るものは何かを知るため に最初の10個の結果を見た - 結果は酸素、食物そして水、などだと述べる。 全体で、365の結果があった。おもしろいことに、'病気'は十位までにはなかっ たが、他の365の結果を見ればどこかにあっただろう。 だから、これらは、情報はそこにあり、誰かがしなければならない全てのこと はそれを得ることについてより賢くなることだという種類の問題である。我々 はGoogleでこれを行なった。それらのいくつかは自動的であり、我々は単に単 語をタイプして、その単語自身が十分によい手がかりである。我々は、どのよ うに単語が相互に関連するかを示すモデルを構築しようとするある仕事も行なっ た。 我々は"labs.google.com"と呼ばれるページをもっているが、それはメインの 検索エンジンの中には入れられていない実験的なもののいくつかを表している。 そこには"Google Sets"と呼ばれるツールがある。そのアイディアは、一つの 単語またはフレーズあるいはそれらを複数タイプすると、他の何がその概念に 関係するかや群がっているかを示すというものである。だから、"猫"や"犬"を タイプすると、"馬"や"兎"を戻す、等々。人々がもちだしてきた問題の一つは、 単語が一つより多くの意味をもつときの曖昧さである。だから、これらの単語 の一つを変更し、異なる単語を入力して他の結果を得ることができる。たとえ ば、私は二つの完全に正しい単語 - "cat"と"more" - を入力し、ある奇妙な 言語での検索結果を得た - それはUnixコマンドの言語だとわかる: ls, rm, mkdir, mvなど。 ここに別の重要な機能 -- 質問に答えること -- がある。私の友人である James Jurafskyは、ちょうどMacArthur Fellow Awardを獲得したが、それを行 なった最初の計算機言語学者である。当然、彼は朝の3時に記者から質問の電 話を受けた。起こされてすぐに自分の仕事を説明することは難しいが、彼は言っ た。「私は質問に答えることを行なっています。現在では、検索エンジンに向 かっていくつかの単語をタイプしていくつかのページを得られます。しかし、 本当に行ないたいことは、本当の質問をタイプして結果を得ることです。たと えば、大量のページを読み通さなければならないよりも、"誰がAbraham Lincolnを撃ったか"とタイプ入力して答え"John Wilkes Booth"を得たいでしょ う。」 そして、朝の3時の舌先に最良の質問を常にもっているわけではないので、そ の例は用いるのにより良いものの一つではないことがわかった。我々は、ちょ うど彼が行なったように、Googleに正確な質問をタイプし、きわめて良い結果 を得た。一番の返答は"Boothが計画した通りに暗殺された"だった。現在では、 我々は完全にJurafskyが望んだような単純な文で質問に答えているわけではな い。しかし我々は、やっかいな言語学を用いることなく、それに近付きつつあ る。 政府が後援する質問応答のための競技会がいくつか開かれてきた。彼らが用い る質問の一例は、"宇宙に行った最初のアメリカ人は誰だったか?" 我々は二 番目の結果の中にきわめて良い答を得るが、一番目にではない。だから、ここ でも我々はすぐに最良の答を与えるという点でまさにその場所にいるわけでは ない。しかし、我々は近付きつつある。 ある人々は我々がすでにもっていると考えている我々が開発中の一つの機能は、 無関係な単語を発見する自然言語モデルである。クエリーの小さな割合に対し て、スパム送信者が検索結果の中で高く評価されるウェブページを得ようとす る問題を抱えている。彼らはそれを行なわせるためにあらゆる種類の狡猾なト リックを用いる。彼らが最近行なっていることの一つは、別のウェブサイトの テキストの中に彼らのキーワードを点在させることである。たとえば、スパム 送信者が"Athlon dual processors"に対するクエリーで高い得点をとろうとし ている場合、彼は新たなサイトから盗んだテキストのこれらの普通のパラグラ フの中に単語を挿入する。そのようにして、彼はページの中にその単語を隠そ うとしているのだ。これは、我々がずっと扱っており、解決するために作業し ている挑戦である。 ソフトウェア さて、ソフトウェアについて話そう。Googleでは、サイトの主な部分はC++で 書かれ、PythonやJavaで書かれたかなりのコードもあり、Perlも多少ある。 この聴衆に対する最初の質問は、なぜLispは誰もが大好きな言語ではないのか? なぜ誰もが全てに対してLispを使うわけではないのか? なぜLispはGoogleでは 使われていないのか? 以下は私自身の経験から取り出したいくつかの理由であ る: メモリ管理 私はさきほど、とても大きな例の集合でパーサを訓練することで大きな成功を 収めたEugene Charniakに言及した。彼は、メモリ管理の問題のためにC++へ切 り替えたと言った。彼の感覚は、彼が行なっている操作はそれほど複雑ではな い --- 一ページかそこらで数式を書き下せるが、彼が本当に関心があること はこれらの巨大な行列を整形し、それを効率よく行なうことだというものだっ た。彼は、C++ではそれに対するより良い制御をもつと感じた。私にはそれが 正しいかどうか確信がないが、Lispで処理性能を二倍にするためには、Lispの 抽象能力を捨て去り、自分でメモリを管理し、語の配列その他を割り当ててそ の上で直接作業しなければならない。Charniakの選択は、C++を用いることは 彼の問題にはよりふさわしいものだというものだった。 コンパイル時の型チェック 多くの人々は、これらのウェブサービスがほしいがクラッシュしてほしくはな い、また、網羅的なケース分析を行なっていないことをわかっていると言う。 Dick WatersはLisp用のケース分析とコードカバレッジのための素晴らしいツ ールをもっていたと思う - しかし、その種のツールは広く使われてはおらず、 人々は、それらの間違いのいくつかを捕らえるために強いコンパイル時の型 チェックを行なう言語をもつと安心すると感じている。それは信頼性があるソ フトウェアを作るための唯一の要因ではないが、一つの要因ではある。 文化的な偏り Lispコミュニティは、二つの点でいくぶん孤立している。一つは、JavaやC++ プログラマと同じくらい多くのLispプログラマがいないという点である。もう 一つは、Lispコミュニティは外部への全てのインターフェイスを最新にしてお くことをあまり行なわない - HTTP, SMTP, FTP, XMLやそれらのパッケージ全 てを用いてウェブタイプの物事を行ないたい場合、PerlまたはPythonのための 正準のサイトへ行ってすぐにそれをダウンロードできる。一方、Lispでそれを したい場合、くまなく探し回らなければならず、選択肢はわずかであり、パッ ケージが保守されていくことを保証しているものはさらにわずかである。 最後に、Lispはより激しい競争があったために痛手を被った。十年前には、存 続可能な競争はなく、Lispは多くの問題のクラスに対して明らかに最良の言語 だった。それについてもう少し注意深く見てみよう。 私のLispの本へのイントロダクションで、私はLispを独自なものにしている八 つの機能について話した。1992年、Lispはこれらの機能をサポートする唯一の 主要な言語だった。2002年には、これらの優位の多くはなくなった。ガーベジ コレクションは多くの言語に普及している。動的な型づけは他の言語の多くに 現れている。いくつかの言語で対話的な環境(read-eval-printループ)を得ら れる。 まだ独自のLispの利点はいくつかある。一様なシンタックスはその他のいずれ でも不可能な方法でマクロを書くことを可能にするので、それはLispがなお勝っ ている場所の一つである。残念ながら、それは明らかに現在ではあまり重要で はなくなってきていると見られている。拡張性はまた別の領域である。Lispは、 オブジェクト指向パラダイムをサポートするために、とてもシームレスかつ容 易に移行を行なえたが、他の言語でそれを行なえたものはほとんどなかった。 多くの言語では、コンパイラを作り直すことなしに、Lispほどシームレスにオ ブジェクト指向のコードを付加することはできない。別の利点はアスペクト指 向プログラミングである。Lispでは、アスペクト指向のプログラミングを行な いたい場合、多くのマクロ作成を行なうだけである。Javaでは、Gregor Kiczalesに出ていって新たな会社を始めてもらい、数年と数ヶ月を費やして動 作するようにしてもらわなければならない。 第二の質問は、"Lispはみんなの一番好きな言語ではないなら、みんなの二番 目に好きな言語になるべきではないのか?" あるいは、少なくとも他の全てを 結合するための一番好きな"接着剤言語"になるべきではないのか? その答えは、Lispはそのためにはとても良いが、他の選択肢もあるというもの である。人々はPythonを好むが、Pythonはスローガン"バッテリー込み"をもつ。 これは先に述べた一つの問題 -- 全てのライブラリがそこにあること -- であ る。そして、彼らはそれを経済的にすることを好む。経済的とは、このライブ ラリを使う場合、誰か他の人も同様に使おうとしていることを知ることができ、 より相互作用が可能なように標準の配布についてくるという意味においてであ る。それはLinuxでもうまくいっている。Linuxは我々の会社で使っているもの であり、これらのC++への標準のインターフェイスをもつ。 これはある種のことを物語る: Lispの世界では、Lispの外部とインターフェイ スをとるときには外部関数呼び出しと呼ばれる。Javaの世界では、それはネイ ティブ呼び出しと呼ばれる。その視点は反対であり、これらの言語のいくつか は移植可能な方法でそれを行なうことを容易にしている。 Perlの全体の来歴はPythonに似ており、同じくPerlには正規表現をサポートす る第一の言語であるという種類の偏りがある。あなたがテキストを扱う何かを 行なっており、正規表現を作りたい場合、Perlを見る傾向がある。 Javaは、その人の位置に依存して、ほとんどC++であり単純化しただけに見え るという長所あるいは短所をもつ。それは安定した言語環境をもつ可能性を提 供するので、素早いアプリケーション開発用と同様にプロセッサを酷使する仕 事のためにJavaを使える。Javaはおそらく二兎を追い損なっている - 二つの 頂点を目的としている場合、おそらく二つの頂点の谷間に陥ることになる -- しかし、人々はなおも両方に対して使おうとしている。 Lispを知らない人々のために、彼らは何を必要とするのか? 人々はより遅いス クリプト言語を使い続け、私は多くの場所で問題の一つとしてそのことに気づ いた。そこでは、人々はログファイルの整形やレポート作成のような何か単純 なことのためにPerlあるいはPythonスクリプトを書き始める。それはうまく動 作し、みんながそれを使って幸せである。しかし、数キロバイトから数ギガバ イトへ、後には数テラバイトに達するログファイルを扱うようになるかもしれ ず、そうなると、そのためのPythonのプログラムを書くことはもはや楽しくは ない。あなたは速度に関して一つか二つの大きさの次数を見落としているので ある。 他の問題として、特殊目的の言語を定義できるようにすることがある。Lispプ ログラマにとっては、これはまさにどのように行なうかを知っていることであ るが、他の言語から来た人々が自動的に考えることではない。実際、インタプ リタを書いたり、あるデータ型のインタプリタとしてそのデータ型の処理を定 義したりするというアイディアは、Lispの背景をもたない人々にとっては理解 することが難しい。だから、Lispを知ることは、Lispでプログラムしていない ときですらあなたをより良いプログラマにするのである。 Lispだけしか知らないプログラマも問題である。彼らはメモリ管理を行なうた めには他の方法もあることを理解する必要がある。C++では、呼び出している 手続きの中で割り当てを行ない、その解放を自動的に行なわせる、呼び出し側 に基づくタイプの割り当てがある。正しく行なわれたときには、正しい種類の データ構造に対しては、とても効率的で使いやすいものになり得る。 以下は私にとっては意外な新事実だった -- あまり重要なことではないが、そ れぞれの文化の間に違いが見られる -- それは行指向のデバッグの概念を理解 していることではない。私はそれによって何を意味しているのか? あなたが Lispプログラマである場合、改行を何か特別なものとは考えない - 単なる空 白である。それらはタブまたは空白文字と同じで良いだろう。しかし、あなた がPythonプログラマである場合、シンタックスは改行が意味をもつものとして 書かれるので注意しなければならない。あなたがJavaまたはC++プログラマで ある場合、改行はシンタックスを決定しないが、ツールは改行を用いるとわか るだろう。だから、エラーメッセージはどの行にそれがあるかを報告し、デバッ ガは行ごとに動作し、そして、そのような物事は本当に重要であり、プログラ ムについてのあなたの考え方を変える。 私は、埋め込みに対して人間の記憶には制限があると理解することがここでは 重要だと考える。たとえば、"猫が見たコウモリが追いかけた鼠はチーズを食 べた。"のような文を考えよう。あまりに多くの埋め込みのレベルがあるので、 人々は容易にはその文をパースできない。しかし、三つの別々の行として、行 ごとに別々にそれを書いた場合、容易に理解できるだろう: その猫が見たコウモリがいる。 そのコウモリが追いかけた鼠がいる。 その鼠はチーズを食べた。 私は同じことが関数プログラミングで起こると考える。関数プログラミングで は、関数呼び出しの中であまりに多くの埋め込まれたメッセージのレベルを得 る可能性がある。これは数学的には問題ないが、人間的な観点からは、記憶に 負担をかける可能性がある。行指向のアプローチはこの問題を軽減し得る。 私はいくつかの個人的な考えを述べることで話を終えたいと思っていた。Paul Grahamは、Lispは彼の秘密兵器だったとつねに語っている。彼は、まさにLisp を知っていたために、彼の会社を作成でき、製品を市場に導入できたと感じて いた。私は、彼は唯一Lispを用いることができただろうという点で正しいと考 えるが、他の言語に熟達した他の人々も同じことを行なえただろう。 それが私の印象である。彼は、対話的なトップレベル、HTMLを生成するための マクロをもつこと、ウェブページ上のコールバックのための継続をもつことな どのような、彼がそう感じた機能はLispに独自だと述べた。しかし、これらの 物事全てに対して、他の言語には別のテクニックがある。 Erann Gatは、NASAとGoogleの両方に関係があるという光栄に浴した人だが、 「私は、他の言語で私がLispで行なうのと同じくらい生産的な人々を初めて見 た。そしてさらには、私自身がより生産的になっていくことに気づいた」と言っ た。だから、ここには世界のもう一方の側を見たケースがある。彼はそのとき Lispが唯一の道ではないことを理解した。ITAソフトウェアのCarl de Marcken は、アルゴリズムの博士号をもつがITAの問題について働くことには興味がな いC++やLispの導師よりも、Visual Basicで多くのコードを実際に書いた人を 雇うだろうと私に話した。彼にとって、進んで塹壕に入って仕事をすることが より重要であり、どのような経験があるか、あるいは、どのようなツールを使 うかはそれほど重要ではない。 ある意味では、私はLispを用いずにLispの全ての長所をもつものとしてGoogle を見ている。なぜか? まあ、一つには我々は適切な人材をもっていることがあ り、それは決定的なことである。また、我々は、他の多くが滑って転んでいた ときに上昇していたのはとても幸運だった。他の誰も雇わなかったので、我々 は多くの良い人々を得た。それは我々にとってはとてもうまく機能した。我々 の人々はLisp, Smalltalk, DylanやPython, そしてC++のバックグラウンドを もっている。 我々の目標はつねに動いており、徐々に変更していくことが可能である。Paul Grahamにとって重要だったことは我々にとっても重要であるが、我々は多少異 なったやりかたで物事を行なう。一つのリスナーに対してLisp関数の更新され た定義をコンパイルするようなものをもつのではなく、我々は10,000のサーバ をもち、一度に一つずつダウンさせて更新する。だから、我々はつねに実行中 であるが、異なるレベルと粒度で行なっている。C++を用いると、実行中のプ ログラムを大きくしていくことはできないが、実行中のプログラムを大きくし ていく必要はない - 我々は実行中のサーバのシステムを大きくしていく必要 があるのであり、単一のプログラムを大きくしていく必要があるわけではない。 対話的なトップレベルに関しては、ある意味においては全てのウェブサーバで 十分である - ウェブサーバは一つの要求を受けとってそれを戻す。そして、 HTMLに対するマクロのような物事のためには、我々は汎用目的のアプローチを とるのではなく、我々が必要なもののためにそれ専用の方法で実装するだけで ある。 Local Variables: version-control: t kept-old-versions: 0 kept-new-versions: 0 end: