[寝起きIdea] アマゾンのロボット倉庫からユーティリティ関数へ #アルゴリズム

本題に入る前に、Amazonが買収したKiva Systemsの話をしたいと思う。

ご存知、大量のロボットを用いて在庫の 搬入,移動,搬出 までを自動化・省力化する技術だ。箱詰めは人間がやる。詳細はこちらがわかりやすい(youtube)。6月に参加したICAPS 2014のInvited Talkにて、Kivaの技術チーフが公演をしてくれた、その公演の録画だ。(ちなみに、自分もこの部屋で発表した。)

一般の媒体ではその「ロボットを使っている」ところばかりが協調されるが、このプロダクトのすごいところは そこではない。注目すべきなのは、上の動画の12分あたりで紹介される考え方、すなわち、
倉庫全体を、超並列の、ランダムアクセス記憶媒体として考えることだ。

コンピュータのメモリがレジスタ、L1,L2,L3,メインメモリ、ハードディスクと階層的に分かれているのと同様に、Kivaのロボットも階層に分かれており、「遅いがパワフルなロボット」、「速いが積載容量の低いロボット」が混ざっている。速いロボットはレジスタだ。そして、搬出窓口から遠いところにいる遅いロボットは、ハードディスクだ。

まあ言ってしまえば、このシステムは、ロボットをただ動かす技術だけでは到底作れないものだということだ。

ユーティリティ関数

Common Lisp で言われている問題の一つに、ユーティリティ関数がある。
ユーティリティ関数は、なにか特定の機能 (webサーバや画像処理など) ではなく、一般のセマンティクスへの影響があるような、汎用の関数群、あるいはマクロ群だ。
Common Lisp は、そういった汎用の関数を切り出して書くのが簡単であるがゆえに、
lisperは、いわゆる自分向けの「便利関数」を沢山もっている。
そのなかで特に多くの人から使われているものは、 alexandria のようなライブラリとしてまとまっているが、たいていは完全にばらけている。

みんなが自分用のライブラリを持っているというのはちょっと非効率だ。
しかし、lisperは身勝手なので、人のライブラリを見て借りてくるようなことはしない。
そもそも、思いついた時に書けば良い、そう思っているし、そう物事は行われてきた。
実際、以下がその実例だ。quicklispには複数の utility ライブラリが登録されている。

今までの取り組みの中では、この現状を変えようと、quickutils みたいな試みがあった。

http://blog.8arrow.org/entries/2013/06/17
(専用のウェブページもある: http://quickutil.org/submit )

実は、このアイディアにはあまり使おうという感じを受けていなかった。だって、

結局、どの関数がほしいかを記述しておかないといけない
- 確かに、 utilize で保存・再利用することはできる
- しかし本当にやりたいのは手間の最小化

「おれおれパッケージを作ってそこにまとめておく」ことよりも手間が少なくならない限り、
アイディアとしてはいいが、実用できないと思う。実際これは、(この主張は正しくないかもしれないが)quickutilsは他のプロジェクトに利用されていないようだ。

Required by
0 None.

アイディアとしてはいいんだけど。

ユーティリティ関数とストレージのアナロジー

さて、ここで冒頭のKivaの話とつなげよう。
つまり、ユーティリティ関数の有効化(使える状態にすること)は、
データ読み出しと同じだということだ。

関数は、使うたびに自分で書くことも出来る(低い効率)。
特別なパッケージを作ってそこに自分で書き、何度もそこから使うことも出来る(中効率。自分でコードを書く必要あり。その後は自分のパッケージをuseするだけ)。
alexandriaなど共有パッケージから読み出すことも出来る(本来は高効率であるべき)。

注意したいのは、今はソースの局所性ではなく脳内から引き出すためのコストを考えているということ。「あの関数fnを使いたい」と思った時に、fnを今のREPLに引き出すためのコスト。今問題となっているのは、3. のコストが 2. よりも高いということだ。 2. は結局自分で書いているから、本来コストが高くあるべきだ。

そしてこうなっている原因は、キャッシュが自動で出てこないことだ。
CPUのキャッシュのいいところはなんだろう。それは、キャッシュが透過的であることだ。ALUからみれば、データを読みだすのにキャッシュ値が使われたか直にメモリから読みだしたかはわからない。
ユーティリティ関数のインポートをそれと同じ程度の使いやすさにするためには、
いちいち手動で指定するのでは当然満足が行かない。(もちろん、最低限の下準備は必要だろうと思う。)

これを実現するための、一番簡単な方法が 全部入りパッケージ を作ることだ。
一つのパッケージに、alexandriaやらmetabang-bindやら、すべてuse-packageして入れ込んでしまうわけだ。しかし、common lisperなら当然すぐわかるだろうが、この解法は正しくない。common lisp には package conflict があるからだ。

キャッシュは破棄される

ではなぜ、20年来に渡り、lisperはこの問題を乗り越えられなかったのだろうか?
ひとつ確実だと思うのは、lisperがキャッシュのInvalidationを乗り越えられない限り、
根本的な解決は無理だろうということだ。

私が考えていることがわかるだろうか?構想として考えているのは、下のようなものだ。

(enable-auto-import)
(print (symbolicate :a :symbol))
; importing alexandria:symbolicate
A-SYMBOL

quicklisp 中の全関数、マクロを持ってくる。引数リストや型を記憶し、データベース(=キャッシュ)に保存する。
ある機能を有効にすると、コンパイラに追加機能が挿入される。
その追加機能は、コンパイル中にundefined function があれば、データベースを探索し、どの関数が意図したものなのかを推論して、リコンパイルする。それでも失敗するなら、成功するまで別の関数でコンパイルを試みる。

キャッシュのinvalidationとはつまり、引き出された関数が そこでは使えないものだった、つまり キャッシュの内容が間違っていた ということだ。

たまたま、複数のパッケージに同じ名前、同じシグネチャの関数・マクロがあったらどうしようか?
これはtie-breaking(引き分けのときの戦略)とよばれるものである。これにも、いくつかのことを考えることが出来る。

現在のパッケージにその関数が定義されていれば、もちろんそれが使われる。
personal utilities: 個人パッケージをlispグローバルで定義しておく。オレオレ関数はつねに優先される。
global reference count, or popularity: その関数はどれほど幅広く(他のパッケージで)使われているか? -- これは、他人のオレオレパッケージのsymbolicateよりもalexandria:symbolicateが優先されるように条件付けする。実績のある関数は多く使われるだろう。
personal preference: パターンマッチマクロmatchに「cl-matchよりoptimaを使いたい」という人は、lispグローバルなwhitelist/blacklistを作ることができる。結果、例え新しくpopularityが低いパッケージでも、そちらが優先される。
personal reference count: 自分がauthorであるパッケージ中に現れる関数は、高く評価する。
personal relevance count: 4.に当てはまる関数と同じパッケージに属する関数は、高く評価する。
どこにも見つからなかった場合にのみ、undefined-functionを投げる。これは、手元のファイルに書く必要があることを意味する。

このような機能は使い物になる、信頼できるものになるだろうか?
始めは使い物にならないだろう。つまり、予想外のシンボルが使われたりすることがあるだろう。
しかし、ここで重要なのは、使い物にするための努力がquickutilsのような 手作業によるデータベースの充実 ではなくて推論アルゴリズムの改善 や設定の自由度の改善 になされるということだ。この違いは大きい。

両者の考え方の違いは、検索エンジンとしてのyahooとgoogleの違いだ。yahooは、手作業で登録された高品質なデータベースを持ったweb検索エンジンだった。一方googleは、pagerankを用い、クエリの処理はそれにまかせ、逆にpagerank自体を改善していった。

その先にあるもの

このアナロジーを用いてもっと考えることが出来る。

その一つは例えば、階層化だ。コンピュータの記憶媒体は階層化されている。レジスタはL1キャッシュより早く、L2,L3,メインメモリ,スワップと続き,今なら最後にネットワークストレージがくるだろう。
現状、lispにはたった3階層しか無い。本当に必要なのは、たとえこれを増やしても管理が行えるような、そういうシステムだ。

実験が終わりそうだから作業に戻ろう。lispの未来を信じて;;