2014年03月19日

「Oracleを教えているのよ」

研究への予算配分の話が出るたびに、日本でやらなくとも各国の成果が論文として公開されるのだから、それを読めばいいじゃないか、日本は基礎研究に金など出さなくていいのだ、という意見をよく目にする。私は自分の体験から、そうは思えない。

大学院生だった頃、ICPC(国際大学対抗プログラミングコンテスト)の代表選手たちが国外に向かうとき、コーチとして付いていったことがある。暇な時間には他の大学のコーチたち(多くは、計算機科学を受け持つ教授であり、院生は珍しかった)と話していたのだが、ある国の国立大学の講師の人との会話が軽く衝撃だった。

彼女はcomputer scienceのlecturerと名乗った。学生たちのコーチを務めるには数日の間選手に同行せねばならず、まぁ非常勤講師ということはあるまい。セオリー通り、私はこう切り出した。「何の研究をされてるんですか?」「? ああ、Oracleを教えてるのよ」「ええっとoracle... 計算量周りの研究ですか?」「?? えっ」「えっ」

えーとちょっと待った。それ以外でCSでoracleって知らんぞ。工学に同じ名前の別の概念あったっけ? えーとえーと。まさか。「で、データベース?」「そう、Oracle。」なんと、oracleではなく会社のOracleか! まるで「当店のポイントカードはお餅ですか」並のコントだ。

話そのものはその後なんとか繋がったのだが、ものすごく気持ち悪い感覚を覚えたので、なぜそう思ったのか、会話しながら脳内で冷静に分析していた。"Oracle"と最初に聞いた時、自分は「まさかそっちではあるまい」と思った。彼女は"relational database"と言わず、"Oracle"と言った。"Oracle"に「計算量周りですか」と返して、素でわからない顔をされた。

彼女の英語は流暢であったから、単語力に問題があるとは思えない。逆に、単語力に問題があると思われるほど酷い英語をこちらが喋ったわけでもない(たぶん)。しかし、relational databaseという言葉は、その後の会話でも一度も出て来なかった。ついでに会話の中で聞いてみたが、"bags algebra"という単語も知らないようだった。本当に研究はせず、教育だけをしているようだった。

つまり。彼女は"relational database"ではなく、"Oracle"を教えているのだ。国立大学、それもおそらく彼女の国で一番の大学で教鞭を取る講師が、一企業の製品を教えている。これが違和感の原因である。

私の知る限り、現在の日本の国立大学では、データベースとはどういう概念でどう構成するか、という話をし、どうやって使うか、という話はほとんど行われない。海外の大学についてはわからないが、USの大学のうち、講義ノートが公開されている講座ではだいたい同様であるようだ。教育と研究が日本よりよく分かれていて、データベースの講義が研究から完全に分離している、ということもあり得るが、そうだとしても"Oracle"ではなく関係データベース一般の話をし、実例としてOracle DBを紹介したり使わせたりするだろう。"Oracle"を教えていては、Oracleに入社してデータベース自体を改良したり、Oracle DBを超える新たな製品を生み出すことはできない。また、時代の流れに対応することもできない - この会話を交わした7年前には、MongoDBは無く、かろうじてCouchDBがリリースされたばかりだった。

この時、研究をやらない、ということはこういう事なのだ、と悟った。基礎研究をしなくても、研究の果実は外国から持ってこれる。ただし、成果を読んで理解できる人を、教育することができなくなるのだ。常に走り続けている人間を、走り続けているまま雇わなければ、走り続ける人を育てることなどできないのだ。

彼女の国が、専門学校としての大学から脱却し、高等教育のサイクルを回せるようになるには、あとどれぐらい掛かるだろうか。
posted by chun at 23:47| 暴言

2013年08月15日

SMTソルバでプログラムを作る

ICFP programming contest 2013に参加していました(よくわかる解説)。チームの成績は戦略ミスなどもあって散々だったのですが、ちょっと変わったアプローチで問題に取り組んだと思うので、自分のチームのアプローチを紹介しておきます。リポジトリはこちら

続きを読む
posted by chun at 02:55| 日記

2012年12月17日

SML#をLLVMに変換する

この記事はLL/ML アドベントカレンダーの記事です。なごやに向かって不用意な発言をすると勝手に登録されるので皆さん気をつけましょう。

SML#の0.90リリース以来、私はSML#の美しさに魅せられ……ることは別になく、もっぱらその低レベルプログラミングとの相性からSML#の使い方を妄想するなどの健全な遊びをしておりました。
SML#はなかなか楽しい言語です。特に怪しいC/C++のライブラリをwrapするのには、SML#は極めて強力な道具となることが期待されます。
こうした処理を、ストレスなく書ける処理系として、私はSML#に密かに期待しておりました。

が。

SML#を使うにあたって、そこには大きな問題があります。

x86では動くけど、ARMで動かない! POWERで動かない! SPARC64VIIIfxとかで動かない! せめて、x86_64で(32-bit libsなしで)動いて欲しい! 今時x87命令とかありえない!

あすてりずむさんも書かれていますが、やっぱりARM用コンパイラほしいですよね!
http://d.hatena.ne.jp/aster_ism/20121207/1354806769

SML#コンパイラを読み解くとわかりますが、SML#のアセンブラコード出力は血のにじむような努力の末に達成されています。
これを書き換え、ARMやx86_64向けに出力するには、おそらく1出力先ごとに1ウエノ(単位)相当の生贄を捧げねばならないと言われております(ません)。
これは大変な作業なので、おいそれと要求できるものではありません。また東北大のコアデベロッパーの方々には、レジスタ割付や命令列の並び替え、変換などよりも、むしろ彼らにしかできない言語側の仕事を頑張って欲しいものです。

……ということで、無いものは自分で作れという声を聞きまして、SML#からさまざまな他アーキテクチャに向けてコードを出力しようと思い立ちました。今考えるとC言語で出力しても別によかったかなと思うのですが、ジャンプや例外の処理を考えると、C言語よりもう少し柔軟な出力先を選びたくなります。今回やってみたのが、LLVM (Low Level Virtual Machine)での出力です。LLVMはコンパイラを作るための共通基盤として作られた抽象VMで、LLVMのアセンブラとして記述されたコードは様々なアーキテクチャのコードに変換が可能です。LLVMはLLVMをC言語として出力する機能もあるので、いざとなればC言語での出力も可能です。万一SX-9でプログラムを走らせることになっても、大丈夫。そう、LLVMならね。

コードはこのへんです。READMEに書きましたが、言語の最小セットの部分しか実装していません。具体的には、追加された例のminimal.smlしかコンパイルできません。

https://github.com/shunsakuraba/smlsharp/tree/llvm

実装ですが、SML#コンパイラでは、AbstractInstruction2という抽象マシンコードから、ターゲットアーキテクチャの言語に変換を行います。このAbstractInstruction2はかなり抽象度が高いコードになっており、無限レジスタ上での逐次命令列が記載されています。この命令はほぼ1対1でLLVMの命令に対応します。ですから、ほとんどただ逐語訳するだけで変換はOKです。

ね、簡単でしょ?

「ほとんど」ではなかった点は以下の通りになります。
・LLVMに於いて、グローバル定数はデータではなくデータへのポインタとして扱われる。AbstructInstruction2では、グローバル定数はデータとして扱われる。このため扱いが面倒である。
・LLVMでは関数を異なる引数型で再定義することはできないので、何かの関数を異なる型で呼びたい場合はcastにより実装する。具体的にはprintfの書式違いとかな!
・AbstructInstruction2ではポインタにあたるものは何でもBOXED型だが、LLVMでは「それが何のポインタか」まで問われるため、変換しようとすると多くの場合情報が不足する。たとえばC-stringのようなものは、SML#ではBOXEDだが、LLVMではi8*型である。内部の処理の都合上、i32*型などにキャストして置かなければならない。
・上記と合わせ、基本的にAI2では型情報がいくつか抜け落ちている。真面目にやるなら間に1枚新たな構文木を挟んで、型を復活させてから変換したほうが筋が良さそうである。

あとは、単に作業です。未実装部分をraise NotImplementedで埋めておいて、引っかかるたびに延々とパターンマッチを書く簡単なお仕事! 今後はGCや例外を実装したいところです。

追記:llvm 2.9では動いていたのですが3.0では動かない模様なので今度fixします。
posted by chun at 00:02| 関数型

2011年12月19日

面白CS論文紹介

この記事は、今年読んだ面白CS論文紹介カレンダー( http://bit.ly/vKrdxq )6日目の参加記事です。CSの中でも、ちょっと数値系に偏った記事になります。

Quasi-Newton Methods for Markov Chain Monte Carlo


http://homepages.inf.ed.ac.uk/csutton/publications/hmcbfgs.pdf

これはなに?



メトロポリス法(ボルツマンサンプリング)はCSにいたら一度ぐらいは聞いたことがあるかとおもいます。TopCoderのマラソンマッチに出たことがある人にはこれを用いた焼き鈍し法がおなじみではないでしょうか。また、機械学習タスクを楽しまれる淑女紳士の皆さんには、メトロポリス法は非常になじみ深いものかと思います。メトロポリス法は、構造空間を広くサンプルし、かつ目的関数の値が充分に低い場所をまとめて拾ってくるには便利な方法です。

しかし、メトロポリス法は、対象が高次元だったり目的関数の異方性が強かったりする場合には、なかなか効率よく空間をサンプル出来ません。この論文で紹介するHMCBFGS法は、こうした問題に対処する新しいサンプラーを提唱しています。

アイディア



異方性が問題になるなら、異方性が消えるように空間をねじ曲げてスケールしてしまえばいいじゃないか……というのが答えになるわけですが、単純に目的関数をスケールして正しいサンプラーを組み立てることは非常に難しい作業です。著者はHamiltonian Monte Carloという力学系を用いたサンプラーの先行研究をまず紹介します。実は、統計力学では、質量をどんなに適当にいじっても、無限時間が経った後の系の確率密度は同じであることが保証されていますから、質量に異方性を入れてスケールすれば、異方性をうまく消しながら空間をサンプルすることが可能になります。あとは、良い質量の決め方を探すだけです。

出会い



この論文は、NIPS2011のaccepted papersを眺めていたときに出会いました。タイトルで一目惚れした論文です。

なんでそんなに気に入ったのか



一つには今の自分の研究が力学系だし良いサンプラーを必要としている、というのがあります。もう一つ、単純ながら置き換えの効かないメトロポリス法を倒せる可能性のある候補である、というのがあります。メトロポリス法が作られたのは実に1953年ですから、50年も生き延びている優秀なアルゴリズムなわけです。これに勝てるかもしれない、って聞くと、みなさんワクワクしませんか?

Fixed block compression boosting in FM-indexes


http://arxiv.org/pdf/1104.3810

これはなに?



FM-indexという、文字列を圧縮したまま検索したり、元の文を復元したりできる不思議なデータ構造があるのですが、そのきわめて簡単で且つ圧縮率の高いな実装方法を見つけたよ、という話です。FM-indexの実装においては、文字の出現頻度だけを見て圧縮するwavelet treeという高速で実装も単純な方法が知られています。しかし、この手法では文字の出現頻度しか見ないため、文章のなかでたとえば頻出単語が存在する場合、圧縮率がもっと伸ばせるのに……という事態が起こりえます。

アイディア



この論文では、まずFM-indexを構成する要素であるBurrows-Wheeler Transform(BWT)を適切にぶった切れば圧縮率が理論上界まで伸ばせることを示し、しかる後に適当にぶった切っても圧縮率が大して悪化しないことを示します。

中身については、PFI社の岡野原さんもちょっと触れていますのでご参考まで。
http://www.slideshare.net/pfi/succinct-data-structure-for-analyzing-document-collection

出会い



同じくSPIRE2011のaccepted papersを眺めていたときに見つけました。Juha Karkkainen, Gonzalo Navarro, Veli Makinen その他の各先生の著作はストーキング対象です。

なんでそんなに気に入ったのか



「やぁみんな。複雑な方法で今まで、k次経験エントロピーサイズまで圧縮する面倒な手法を実装してただろう? もうそんなことは必要ない。今日からは、BWTの文字列を、ただぶった切れば良いんだ(意訳)」って言われたら、そりゃ惚れますよ。

Accelerating nearest neighbor search on manycore systems


http://people.kyb.tuebingen.mpg.de/lcayton/papers.html

これはなに?



「点の集合が与えられたとき、その点に一番近い点を求めなさい。」はい、よくある最近点・最近点対問題です。この問題を解くのには、k-D treeなどといった木のデータ構造を作成するのが普通です。これは確かに効率は良いのですが、並列化向きでないという問題があります。

アイディア



点の中からランダムに、代表点を複数抽出します。代表点の近くにある点を、順番に決まった個数取り出し、最長距離を覚えておきます。この処理はきわめて容易に並列化できます。これをインデックスとしましょう。

クエリが来たら、代表点との距離をまず測り、最長距離を用いて枝狩りをして生き残った候補との距離を測ります。この処理もまた、きわめて容易に並列化できます。これで近い順に点を出力すれば終わりです。

出会い



この問題を解く、state-of-artな方法を探していたときに見つけました。

なんでそんなに気に入ったのか



原理単純、実装単純、それでいて理論的にも実際にも優秀な性能のためです。SIMD命令を手で加えて高速化したANNとの速度比較を実際に行ってみましたが、シングルコア・マルチコア共に本手法の方が高速だったので、惚れました。行列積さえ実装できれば良いのでGPGPUでも動かせます。また、手法が単純なため容易に拡張できる点も素晴らしいです。ちょっと考えれば代表点を階層的にしてvan Emde Boas tree作ったりとか、面白そうな遊びを思いつきますよね?



ちょっと連続系的な話に偏ってしまいました。次は @kmizu さん、よろしくお願いします。/h2
posted by chun at 22:50| 日記

2011年07月25日

Hello, javascript

あなたはホームページを運用するうちに、ページ来訪者と大いに語らう場を作りたくなりました。そこで、ブラウザ上で動くチャットルームを作ることにします。チャットルームには発言者の名前と、最新から20個の発言が順に表示されます。
まずはデータの格納先を定義しましょう。ユーザーの名前と、投稿テキストを格納する先を作ります。

// chatは投稿者名とテキストからなる
db /chat : {name: string; text: string}


Opaのデータベースは、実はデータベースに格納された過去値をすべて覚えています。そのため、これだけで「最新のn件」が取得可能です。この辺の仕様は誤って上書きしたデータを簡単に復元できるなど便利なことがある反面、データ容量や個人情報保護などの観点から問題が起きることもありますので、運用の際には注意してください。

  recents = Db.history(@/chat, 0, -num_print)


これで最新のnum_print件が取得できます。

ではまず、これを使い、チャットの表示更新のところを書いてみましょう。まず、得られたrecentsをxhtmlに変換します。

update_chat() = 
// 最新の20件を取得
recents = Db.history(@/chat, 0, -num_print)
// 発言をxhtmlに変換
lines = List.map((x -> <div class="line">
<
div class="user">{x.name}:</div>
<div class="text">{x.text}</div>
</div>), recents)
// 表示!
Dom.transform([#chat <- lines])


あとはDom.transformで<div id=#chat>に書き出すだけです。

「え、この処理はどこで実行されるの?」と疑問に思う方もいるかと思います。答えは、ブラウザとwebサーバー両方です。Dom.transformなどの処理はブラウザでjavascriptとして実行され、Dbアクセスはwebサーバーで実行されます。Dbアクセスはブラウザ側のjavascriptからRPCとして呼び出され、実行されます。プログラマはこのRPCを個別に書く必要が全くありません! これはOpaの非常によい特性であると思います。この機能を使う際にはCSRFに注意してください。見知らぬ人に「こんにちはこんにちは!」などと書かれることのありませぬよう。

最後に、ページを表示し、ボタンを押したら発言を更新するようにしましょう。これでとりあえず、手動更新のチャットの完成です。

// chatは投稿者名とテキストからなる
db /chat : {name: string; text: string}

num_print = 20

update_chat() =
// 最新の20件を取得
recents = Db.history(@/chat, 0, -num_print)
// 発言をxhtmlに変換
lines = List.map((x -> <div class="line">
<
div class="user">{x.name}:</div>
<div class="text">{x.text}</div>
</div>), recents)
// 表示!
Dom.transform([#chat <- lines])

submit_chat() = (
name = Dom.get_value(#name)
text = Dom.get_value(#text)
// textが空でなければ発言
do (
if text != "" then
do /chat <- {~name; ~text}
Dom.clear_value(#text))
// textの中身にかかわらず更新はする
update_chat()
)

show_page() =
<div>
<
input id=#name />
<
input id=#text onnewline={_ -> submit_chat()}/>
<
button type="button" onclick={_ -> submit_chat()}>投稿・更新</>
</>
<div id=#chat onready={_ -> update_chat()}></>

server = Server.one_page_bundle("Chat",
[@static_resource_directory("resources")],
["resources/css.css"], show_page)


(次回に続く)
posted by chun at 02:30| OPA

2011年07月19日

Hello, CSS

こうしてできたページを見てみると、微妙にweb0.9感が漂い、web1.0には何かが足りないことに気づきます。いったい何が不足しているのでしょう?

そうだ、web1.0時代はフォントの色やサイズを変えて遊ぶのが流行っていたのでした。黒背景に白文字・センタリング・フォントサイズ+4。早速これを実装してみましょう。

Opaでは、cssなどのファイルも、できるだけ実行ファイルに含めるような設計になっています。これは、scpなどで1ファイルだけコピーすれば設置が終わるようにという配慮です。細かいことですが、大量のサーバーに配置する際も設置に失敗して404ということが無くなりますし、テストサーバーから本番系に移設する際にも移行途中でのミスは起きません。代わりに、設置時にcssを書き上げておかねばならず、変更に伴い再コンパイルが必要になります。もちろん、開発中のことも考え、cssをon-the-flyで記述したり、ディスクから読むようにしたり、といったことも可能になっています。

server = 
Server.one_page_bundle("Hello",
[@static_resource_directory("resources")],
["resources/css.css"], hello)


/*
resources/css.css
*/
body {
background-color: #000000;
color: #FFFFFF;
}

p {
text-align: center;
font-size: 32pt;
}


無事にソウルフルなページになりましたでしょうか? これで<marquee>タグあたりを付けるとさらにweb1.0っぽくなりますが、悪ノリはとりあえずこの程度にとどめておきます。

#ところで上のCSSを適用すると、Opera11.50でタブ全体ではなく文章の部分だけが黒背景になるのですが、この原因をご存じの方はいらっしゃいませんでしょうか……?

(次回に続く)
posted by chun at 00:48| OPA

2011年07月14日

Hello, transaction

さて今回初めてデータベースを使ったわけですが、このカウンタには問題があります。ユーザーがきわめて多くなると、並列実行の問題から正常にカウントアップされないかもしれません!
このページが1000ページビュー/秒を達成したときに備え、トランザクションを用いてプログラムを書き直しましょう。

トランザクションを用いるには、2つの操作が必要です。
・DBに名前を付ける
Db.transactionを用いてDBにアクセスする

DBに名前を付けるには、database文を使います。
database counter = @local("./hogehoge")
この場合、webサーバーを実行した際のカレントディレクトリ上に、hogehoge_から始まる一連のファイルを作成し、データベースをそこに保存する、という意味になります。

トランザクションを用いるには、トランザクション処理の開始から終了までをまとめた関数を作る必要があります。以前のincr_countをそのままリネームしてatomic_incrとしてしまいましょう。後はDb.transactionにDB名と、トランザクション処理関数を与えるだけです。
  result = Db.transaction(counter, atomic_incr);
トランザクションの実行が成功すると、実行結果が{ some=結果 }という値になって返ってきます。一方、トランザクションの実行途中に別のプロセスがDBの同じ値を書き換えてしまった場合、トランザクションの実行は失敗し{ none }という値が返ってきます。この値を取り出すには、match文を使います。
  match result with
| { none } -> incr_count() // トランザクションをやり直す
| { some = result } -> result

なお、{ some = result } -> result なんて書くのはかったるい! という人のために、~{some} -> someという構文が用意されています。~{some}{ some = some }の糖衣構文です。

これで、あなたのカウンタの1000ページビュー/秒対応が完了しました。あとは中身を充実させるだけですね?

database counter = @local("./counter") // DBに名前を付ける
db /counter/cnt : int // DBの"/counter/cnt"はint型

incr_count() =
(
result = Db.transaction(counter, atomic_incr);
match result with
| { none } -> incr_count() // トランザクションをやり直す
| { some = result } -> result
)

atomic_incr() =
(
c = /counter/cnt;
do /counter/cnt <- c + 1;
c + 1
)

hello() =
<p>
あなたは{
incr_count()}番目のお客様です。
<
/>

server =
Server.one_page_server("Hello", -> hello())


(次回に続く)
posted by chun at 00:16| OPA

2011年07月11日

Hello, counter

Web1.0時代は、「あなたは○○人目の来訪者です」というカウンタをつけるのが流行っていました。
このチープ感あふれる仕組みを含むページを作ってみましょう。

OPAには組み込みのデータベースがあり、dbの後に続けてパスを指定することでデータベースの構造を定義できます。データベースには「型」を指定する必要があります。カウンタはどう考えても整数ですから、整数を表すint型を指定しましょう。

incr_countは、データベースの値を取ってきて、1増やした値をデータベースに入れ、増やした後の値を返す手続き(opaではこれを関数と呼びます)です。あとは、incr_count()を呼ぶたびカウンタ増えるよぽぽぽぽ〜んという寸法です。簡単ですね?

データベースの初期値はどうなるか、気になる人も居ると思います。データベースの初期値は、型によって決まります。intの場合は0が入りますので、このdbの値は0からスタートします。1増やした後の値を返していたのはこういう理由からです。

あとは、ソースファイルをコンパイルすれば、サーバーができあがります。繰り返しますがopaのデータベースは組み込みですので、ライブラリを持って行ったり、DBの設定をする必要はありません。

この実装を見て「あれ、ロックは?」と思った方。ごもっともです。次の回で詳しく説明します。


db /counter : int

incr_count() = (
c = /counter
do /counter <- c + 1;
c
)

hello() =
<p>
あなたは{
incr_count()}番目のお客様です。
<
/>

server =
Server.one_page_server("Hello", -> hello())


(次回に続く)
posted by chun at 23:32| OPA

Hello, OPA

プログラミング言語を遊ぶ以上、まずは何はともあれHello, Worldです。OPAで書かれたプログラムはコンパイルされ、単体でサーバーとして動作する実行プログラムを出力します。

// hello.opa
hello() =
<h1>
Hello, World!
<
/>

server =
Server.one_page_server("Hello", -> hello())


このファイルをhello.opaとして保存し、
$ opa hello.opa
$ ./hello.exe

とするとlocalhost:8080にwebサーバーが起動します。ページが見れましたでしょうか。Web0.1時代の開幕です。

(次回に続く)
posted by chun at 23:17| OPA

Web1.0で遊ぶOPA

OPAをご存じでしょうか? OPAはMLstateという会社が開発したweb開発用の言語です。
わたしはこのOPAがかなり気に入ってしまったので、これから数回にわたり、ちまちまと紹介記事を書こうかと思います。
といっても、わたしはあまりwebページの作成経験がないので、どちらかというとWeb 1.0的なテーマをネタに、サンプルを作ることになりそうですが。
わたしの思う、OPAの良いところリストは以下の通りです。
・パターンマッチ
・パターンマッチ
・パターンマッチ(大事なことなので3回言いました)
・代数型と、それと親和性の良いDB
・型検査(+推論)
・サーバー側とクライアント側を同一の言語で書ける
これからのシリーズで、この特徴をいくつか見ていければ良いかなと思います。よろしくお願いします。

posted by chun at 22:59| OPA