注:ネタバレを避けようという気持ちは全くありません。むしろ根本的なアイデアを解説してさえいる
『順列都市』を最初に読んだのは確か中学三年生か高校一年生の頃で、当時は塵理論のアイデアを今にして思えば何一つ理解できていなかったし、主人公ダラムが行った実験に関しても、ほとんど何も理解していなかった。ただただ、脳をシミュレートすることで死が撲滅される、という「コピー」のアイデアに魅了されていただけだった。
続きを読む1ヶ月くらい、土日や夜の自由時間を主に使ってGPUを使ったレイトレを書いていた。この話もまとめたいな〜と思いながらダラダラしていたら1週間が経過してしまった。みんなどこから時間をひねり出しているんだ? 私以外の人々はその人生で一切ダラダラしないに違いない。この調子で1ヶ月くらい経過して忘れる前に、その道中で一番理解に苦しんだバグを取り上げておきたい。
レポジトリ自体はここにある。そのバグは直っている。まだ機能は少ないが。
何をしようとしていたかというと、分子モデルを画面に表示しようとしていた。画面に表示するといえばカメラだ。最近のカメラはレンズの後ろにCCDやCMOSといった光センサが並んでおり、そこに当たっている光を検出して画像データを取得し、保存している。プログラムでもこれを真似ることになる。とはいえ光学系全てをシミュレーションするほどの正確性は必要ないので、必要のない部分はばっさり切り落とすことになる。この手の手法は本当に無限に研究されており深入りすると戻ってこれなくなるので、基本的にこの記事ではほぼ全てをばっさりカットすることをご了承いただきたい。
とにかく、GUIでリアルタイムに描画するとなるとレイトレ部分以外をまともに動かすだけで死ぬほど手間なので、レイトレーシングのコードを書く前にまずはモックアップ的なものを作ろうと思った。そのモックアップは以下のように動作する。それぞれのピクセルについて、そのピクセルに入射して来る光線を逆に辿って、最初にぶつかったオブジェクトを探す。そのオブジェクトから光が来たと考えられるので、そのピクセルはそのオブジェクトの色にする。リアルさは欠けらもないが、単純で間違えようがない。これは動いた。陰影はなくのっぺりしているし輪郭もギザギザだが、どこに何があるのかはわかる。
// コードはイメージです color camera::render_pixel(std::size_t w, std::size_t h, const world& wld) { const auto ray = this->cast_ray(w, h); const auto obj = wld.first_hit(ray); return obj.albedo(); }
ではレイトレーシングはどのようにするかというと、最初にぶつかった物体を見つけたら、そこから来る光の強度を計算する。光の強度は、物体に差し込んで来る光の波長毎の強さに波長毎の物体の反射率をかけたものになる。物体自身が光っている場合はそこに物体から出る光の強度が加算される。なので、最初にぶつかった物体を見つけたら、その物体のその点に入射して来る光をサンプリングして、その強さをまた計算することになる。物体のない方向から来た光は、環境を満たしている光(空の色など)がそこに入って来ていたということになる。実際には反射するたびに全天を走査することは不可能なので、ランダムに方向を選んで毎回の反射毎に1本の光線を選び、色を計算することになる。そうなるとたまたま光源にヒットしなかったピクセルが真っ暗になったり、その逆が起きたりするので、一つのピクセル毎に100本も1000本も光線を辿って平均することになる。モンテカルロ積分だ。
// コードはイメージです color camera::render_pixel(std::size_t w, std::size_t h, const world& wld) { auto ray = this->cast_ray(w, h); return this->trace_ray(ray, wld); } color camera::trace_ray(const ray_t& ray, const world& wld) { const auto [obj, collision_point] = wld.first_hit(ray); const auto next_ray = obj.scatter_at(collision_point, ray); return obj.albedo() * trace_ray(next_ray, wld) + obj.emission(); }
この過程で、光が反射するたびに、その光がどこから来たかを辿って、物体から来ていたらまたその物体の前はどこから来たかを……という計算をする。ある物体からきた光の強度を計算するために、その前の物体からきた光の強度を使う。これは再帰だ。だが末尾再帰なので、人間でもループに置き換えることができた。GPUでは特に再帰よりもループの方が早いと思われるので、CUDAカーネルに単純なfor
ループを書いた。すると画面が真っ暗になった。
よくわからなくなってループを消すと元ののっぺりした画像に戻る。完全に脳内を?マークが巡っている中、手元の本でCUDAカーネルでループが書けるか確認したり(当たり前すぎる)、for
と等価なwhile
ループを書いてそれでも動かないことを確認したりした。いよいよもってわからず、カーネルからprintf
を呼んでみた。何も表示されない。for
を消して動くコードに戻すと、ターミナルがprintf
からの出力で埋まる。ここから、コードを間違えたから画面が黒くなっているのではなく、CUDAカーネル自体が実行されていないことがわかる。
そんなことがあるのか? と思って普段は使わないcuda-gdbを取り出し、CUDAカーネルを呼び出す関数にブレークポイントを設置して、カーネルを呼んでから帰って来るまでをステップ実行してみた。すると、CUDAカーネルの呼び出し直後に何も起きずに戻って来てしまった。驚いたが、同時に「cudaLaunch returned (0x7)
」という表示が出たので、呼び出しそのものが失敗していることがわかった。これは、「Launch out of resources」を意味するらしい。指定したCUDAカーネルを指定したブロック・スレッド数で実行するにはGPU上のなんらかの資源が足りないというわけだ。
そこで少しGPUのアーキテクチャについて調べてみた。CUDAカーネルを起動する際はブロックの数とスレッドの数を指定することはよく知られているが、どのようにしてその数を決めればいいかの具体的な指針はあまり見つからない。基本的にはスレッドを遊ばせておくよりも多く起動した方が並列性が上がり、GPUがよく燃えることはわかる。CUDAを書いている際はGPUに負荷をかけて燃やしたいものなので、スレッドはタスクがある限り最大限起動した方がいいだろう(タスクがある限り、というのは、1000要素同士の足し算にスレッドを2000個立ち上げてもしょうがないからだ)。
// CUDAカーネル呼び出しのイメージ const dim3 blocks(...); const dim3 threads(...); cuda_kernel<<<blocks, threads>>>(...);
ハード側の上限は割とリスト化されている。このGPUではブロック毎に立ち上げられるスレッド数はいくつで−−、のような話だ。あと、スレッドはワープ単位(32スレッド)で管理されるため、ワープの倍数で指定した方が良いということも知られている(50スレッドだけ立ち上げようとしても64スレッド立ち上がってしまうので、最初から64スレッド立ち上げると良い)。このあたりの情報からすると、常にスレッドをハード的な上限まで立ち上げ、データの数をそれで割った分のブロックを立ち上げれば良いと思ってしまう。実際、私はそうしていた。
ところがGPU上の資源はコアだけではなく、メモリやレジスタも含まれる。レジスタやシェアードメモリなどの一部のメモリはブロック毎に管理されており、ブロックがスポーンさせるスレッドの全てに均等に分割される(シェアードメモリは共有されるので分割されないが)。なので、スレッドを上限までスポーンさせた場合、意外と簡単にこの上限を超えてしまうようだ。最終的にブロックあたりのスレッド数を制限する(代わりにたくさんのブロックを作った)ことで解決したので、この部分でやらかしていたのは確実だと思う。なんとなく計算してみた限りレジスタが尽きたのかな、と思っていたが(スレッドを上限まで作ると1スレッドあたりint
64個までしか置けなくなる)、レジスタの内容は退避させることもあるとかなんとか(Register Spilling)、よくわからなくなってきたので明言は避けておこう。よくわかりません。みなさん頑張ってください。
よくわからないままどうやって解決したんだ、ということだが、CUDAには便利なAPIがあって、デバイスのハード情報だけではなく、実行するカーネルが消費する資源の情報まで取得できる。これを使うことで回避が可能だ。以下の関数に呼びたいカーネルの関数ポインタを渡して呼び出すことで、カーネルの情報を得ることができる。
帰ってくる情報は以下のようなクラスだ。
class cudaFuncAttributes { public: int binaryVersion; int cacheModeCA; size_t constSizeBytes; size_t localSizeBytes; int maxDynamicSharedSizeBytes; int maxThreadsPerBlock; int numRegs; int preferredShmemCarveout; int ptxVersion; size_t sharedSizeBytes; };
ここにmaxThreadsPerBlock
というものがある。普通に考えるとデバイスのハード情報に思えるが、これは関数の属性だ。関数が消費する資源とデバイス情報から逆算して、ブロックあたりいくつのスレッドを立ち上げられるかの値が入っている。なので、何も考えずにこれを超えない最大の数のスレッドを立ち上げれば良い。ブロックの数はデータの数をスレッドの数で割って計算すると良いだろう。試しに見てみると、動かなかったカーネルでは確かにハード的な上限をわずかに下回る数が入っていた。なるほどね。
というわけで、スレッドの数をこの数までに制限すると動いた。まだまだ30FPS出るかどうかくらいの速度だが、綺麗な画像がインタラクティブに表示されるのは最高だ。みなさんもレイトレやりましょうレイトレ
そういえば最近はC++関連のことに触れていないなと思ったので、今日はまだ日本語の説明があんまりないように見えるContractでも取り上げてみたい。サーベイ不足だったら申し訳ない。提案に関する情報は、
P0542R3: Support for contract based programming in C++
by G. Dos Reis, J. D. Garcia, J. Lakos, A. Meredith, N. Myers, B. Stroustrup
に基づく。ただし、この提案はまだ固まっていないため、今後も変更される恐れはある。
とか言ってたら最新のドラフトにもう入ってる上にちょっと変わってるじゃねーか!!
最後に変更点とか書いたので許して
(2/24追記):{QiitaでN4800に準拠したバージョンの記事を公開した。このブログでは歴史的経緯やどういうことが期待されるかに関する寄り道が多いが、Qiita版はドラフトで何が書かれているかに焦点を当てて書いているので、背景事情などどうでもいいという方はそちらを見ていただいた方がいいかもしれない。C++20 Contract - Qiita}
ちなみに私はContract programmingどっぷりなどということは一切なくて、昔ちょっと触って「ほーん便利だなー、でもBoostとはいえマクロでこんなゴリゴリやるのはつらいなー……やめとこ」となってしまった人間だ。なのでContract Programmingを崇めている人からしたらテキトー言ってるしれないことをdiscraimerしておく。
ちなみに、Boost.Contractに関しては日本語の情報もそれなりに出て来る。Contract Programmingそのものに関してもかなり情報があるので、「Contract programmingとは」の部分は読まずに普通にそっちを見てもらっても構わない。
とはいえ最初から規格の説明をするのではわけがわからなくなるので、先に Contract Programming とはなんぞやという話を(私の主観込みで)やっておこう。だいたい知ってる、という人はスルーしていただきたい。
Contract Programming(契約プログラミング), あるいは Design by Contract (契約による設計)は、雑に言うと関数などを呼ぶ時に満たされているべき制約(事前条件)、返るときに満たされている制約(事後条件)、何回呼んでも変わらない条件(不変条件)などを明示的に書いていくスタイルだ。Contract Programming のための機能を言語側で提供することにより、簡単にチェックを入れることができたり、コンパイルオプションでチェックのレベルを変えたりできる。コンパイラが賢ければ、そのような関数が連なっている時に必ず満たされる制約はチェックを自動で外したり、果ては守りようのない制約をコンパイルエラーで落としたりできるだろう。
事前条件は、関数を呼び出す際に守られているべき条件のことだ。通常は引数について期待される条件になる。簡単な例は、
などだ。Contract programmingをサポートする言語では、これに専用の記法が導入され、コンパイルオプションや実行時フラグなどによってアサートがされたりされなかったりする。
事後条件は、関数が返る時に満たされるべき条件のことだ。通常は返り値について期待される条件になる。簡単な例は、
これも専用の記法によってアサートのレベルを色々といじることができるようになる。関数を実装する時は、条件が複雑すぎてめんどいということはあれど、戻り値が満たしている条件が全くないということはあまりないと思う(そういう関数は、一体何をするのか不明確すぎる気がする)。
不変条件は、プログラムを実行しても変化しない条件のことだ。その関数が変化させないもの、その実行を通して真であるような条件を指す。これをチェックする場所は難しいと思う。任意の瞬間に成り立っているはずの条件がある場合、完璧にチェックするためには1命令ごとにチェックするべきだが、そんなことをするとプログラムが圧倒的に遅くなるのでそういうことは普通しない。大抵は、怪しいところにassert
を入れるという形になる。
どれも、ドキュメントやコメントのような強制力のない媒体に書くよりもコードに入っていた方が圧倒的に良いことは疑いようもない。どの条件が満たされなかったかで、関数の内部にバグがあるか、関数を呼び出した側が下手を打ったが明らかになる(正しい条件を書けていれば)。通常のテストよりも少しだけ情報量が多くなり、問題のある箇所が絞りやすくなる。
さらに、これらの条件に特別な記法が導入されてコンパイラが理解できるようになったなら、十分賢いコンパイラはプログラムの妥当性をより適切に評価でき、またチェックをしつつも回数を最低限に留めることでパフォーマンスと両立することも可能になって来ると期待される。例えば、最初の関数の事後条件で「返り値が必ず偶数になる」と保証されていたとして、その返り値をconst
で受けとった後「引数が偶数であることを期待する」事前条件を持つ別の関数に渡すとする。通常のassert
でContract Programmingを真似ていたなら、2回チェックが挟まるだろう。最初の関数の最後と、2番目の関数の最初だ。だが専用構文が用意されていれば、十分賢いコンパイラは2番目の関数の最初にチェックは要らないことに気づくかもしれない。もしそうなれば、不要な2度目のチェックだけが省略されて、頑健で高速なバイナリが完成する。あるいは、その変数を「引数が偶数でないことを期待する」関数に渡した場合、コンパイラは絶対にそれが動かないことを指摘してくれるかもしれない。これは結構嬉しくないだろうか。
実際にコンパイラがそのレベルまで賢くなるかはわからないが。あるいは、十分賢いコンパイラは普通のassert
でも明らかに通るとわかる時は取り除くかもしれないが。
というわけで提案文書を見ていこう。
条件を書くのには、attributeの構文が用いられる。
int f(int x) [[contract-attribute (contract-level): conditional-expression]] { // function body ... }
Contractはfunction type
に対して適用されるため、ここで示されている位置に来なければならない。
ここで、contract-attribute
は以下のどれかだ。
expects
: precondition(事前条件)ensures
: postcondition(事後条件)
contract-level
の後にidentifier
を書くことができる。その名前で関数の返り値を参照できる。任意の名前をつけてよい。assert
: assertion(関数内に書かれる普通のassertと似たような感じ)contract-level
は省略できる。書く場合は以下のどれかだ。
always
assert
に対してしか使用できない。default
default
、またはaudit
モードで検査される。関数そのものの実行コストと比べると軽い(が本気の最適化の邪魔にはなる程度の)チェック。audit
audit
モードでのみ検査される。関数そのものの実行コストと比べても見劣りしないかより重いチェック。デバッグの時にチェックしたいような条件。axiom
always
に関しては少し揉めたっぽくて、ミーティングで投票などが行われている。
conditional-expression
は、満たされるべき条件式だ。そこにどんな式が許されるかの詳細に入る前に、簡単な例をいくつか提案文書から引用しておこう。
int f(int x) noexcept [[expects audit: x>0]] [[ensures axiom res: res>1]];
関数f
は、引数x
が0より大きいことを期待しており(expects audit: x>0
)、返り値res
が1より大きいことを保証している(ensures axiom res: res>1
)。ただし、事前条件の検査はaudit
モードでないとなされないし、事後条件はaxiom
なのでいかなるモードでも検査されない。
void g() { int x = f(5); int y = f(12); //... [[assert: x+y>0]] //... }
関数g
は、x + y
が正であることを表明している。レベルはデフォルトなので、default
モードとaudit
モードで検査される。
ちなみに、これらの単語(audit
、axiom
など)を別の文脈で使うことは許される。[[expects audit: autit == 0]]
のようにも使える。この構文の中のどこに出現するかによって、パーサーはこのトークンが何を意味しているかわかるはずだからだ。
とまあ、こんな感じだ。ではもう少し深く潜ってみよう。
条件が破られると、violation handlerが呼ばれる。ただし、以下の関数の名前は定められておらず、ユーザーが直接呼んだり、関数ポインタを渡してそれに差し替えるというようなことはできない(のだが、なぜかユーザーが指定した場合の話もされている。意見が分かれているのだろうか)。差し替えることが簡単にできるならセキュリティ的な問題が発生しかねない、と筆者らは主張している。
void _Violation_handler(const std::contract_violation &);
ここで、このstd::contract_violation
は<contract>
ヘッダで定義されている構造体で、以下のようなものだ。
namespace std { class contract_violation { public: int line_number() const noexcept; string_view file_name() const noexcept; string_view function_name() const noexcept; string_view comment() const noexcept; string_view assertion_level() const noexcept; }; }
概ね自明な関数名だが、comment
だけ不明瞭かもしれない。ここには破られた条件を文字列にしたものが入っている。ソースコード内のコメントではない。
条件が破られた時、このクラスは、assert
が失敗した時はその[[assert]]
が書かれていた場所を、関数の事前条件([[expects]]
)が破られた時は条件を破って関数呼び出しを行った場所を、関数の事後条件([[ensures]]
)が破られた時はその関数の定義部分を、それぞれ指すようになる。
さらに、違反時の挙動はもう一段階制御可能で、violation continuation mode
と言うのをビルド時にon/offできる。デフォルトはoffで、その場合ハンドラが呼ばれたのちstd::terminate
によってプログラムは終了する。もしonにしたなら、ハンドラが呼ばれたのち、プログラムは継続して実行される。これは、主にログを取る目的で導入されたようだ。
さて、実際に使用するためにはもう少し情報が要るはずだ。もう一段深く潜ることにしよう。
関数の前方宣言をするとか、inline
関数が入ったヘッダを複数回読み込むとか、関数の宣言が複数回現れることは少なくない。このような場合、その関数の事前・事後条件は、「1. 完全に同じ条件である」か、「2. 完全に省略される」必要がある。
int f(int x) [[expects: x>0]] [[ensures r: r>0]]; // 前方宣言 int f(int x); // OK. 全て省略されている int f(int x) [[expects: x>0]]; // Error. 条件が足りない int f(int x) [[expects: x>0]] [[ensures r: r>0]]; //OK. 同じ条件
こうなると困るのが、「同じ条件」とはどういうことかということだ。まず、条件のレベルが一致している必要がある。そして、順番も等しい必要がある。ここまではいい。では条件式の同一性はどう定義されるのか。文字列レベルで同一である必要があるのか、構文木レベルで同一であれば良いのか?
この提案では、文字列レベルで同一であることを要求すると引数の変数名などに気を配る必要があって窮屈だが、論理的に同じ構造をしているだけで良いことにするとコンパイラ製作者が死ぬので、その中間、変数の名前を変えることのみ許容する、という落とし所を見つけている。
int f(int x) [[expects: x>0]] [[ensures r: r>0]]; int f(int y) [[expects: y>0]] // OK. [[ensures z: z>0]]; // 名前は違うが、構わない
だいたいわかってきた。だがもうちょっと知っておかないと不安になる。もう少し行こう。
条件式には、ほとんどどんな式でも書ける。
int f(std::vector<int>& v) [[expects: v.size() >= 10]] [[ensures: !v.empty()]]; // OK.
ただし、変数を変更した場合、その動作は未定義になる。
int f(int x) [[expects: --x>0]]; // undefined! xを変更した
constexpr関数に対する条件式で、コンパイル時定数でないものを使ってはならない。どのタイミングで実行されるかを考えると当然だろう。
int min=-42; constexpr int g(int x) [[expects: min<=x]] // Error. minはコンパイル時定数ではない {/*...*/}
条件が複数並んでいたら、上から実行される。
void f(int * p) [[expects: p!=nullptr]] [[expects: *p == 0]] // p!=nullptr の後に実行されるのでセーフ(?) { *p = 1; }
これ、violation continuation mode
がon
だとめでたくUBな気がするが……? それとも、p!=nullptr && *p == 0
のような扱いになっていて前半で落ちた場合後半ではviolation_handler
呼び出しは発生しないのだろうか?
std::tuple
などを返す関数の返り値についての条件では、構造化束縛を使える。
std::tuple f() [[ensures [x,y]: x>0 && y.size()>0]]; // OK. std::tuple f() // 使わなくてもよい [[ensures r: get<0>(r)>0 && get<1>(r).size()>0]];
[[ensures]]
で使っている値を、関数の中で変更してはいけない。function body
とあるのでどうやら一切変更してはならないようだ。なぜだろう。処理系はreturn
するべき値をレジスタに載せ終わった直後にチェックを挟むのだと思っていたが違うのだろうか。
int f(int x) [[ensures r: r==x]] { return ++x; // Ill-formed: xが変更された }
クラス内の関数の契約条件は、呼ぶ側がアクセスできない変数や関数を使ってはいけない。「その関数が」アクセスできない変数や関数ではないので注意。これは少しわかりにくい。
class X { public: int v() const; void f() [[expects: x>0]]; // Ill-formed. // f()は外部から呼ばれ得る void g() [[expects: v()>0]]; // OK. v()はpublic protected: int w(); void h() [[expects: x>0]]; // Ill-formed. // h()は継承先から呼ばれ得る void i() [[ensures: y>0]]; // OK. yはprotected void j() [[ensures: w()>0]]; // OK. w()はprotected int y; private: void k() [[expects: x>0]]; // OK. // k()はprivateなので内部からしか呼ばれ得ない int x; }; class Y : public X { public: void a() [[expects: v()>0]]; // OK void b() [[ensures: w()>0]]; // Ill-formed void c() [[expects: x>0]]; // Ill formed protected: void d() [[expects: w()>0]]; // OK void e() [[ensures: x>0]]; // Ill-formed };
また、継承先で関数をオーバーライドする場合、継承元の事前・事後条件も引き継がなければならない。
関数ポインタには事前・事後条件を与えることはできない。ただし、事前・事後条件をもつ関数のアドレスを関数ポインタに代入することは可能で、その場合もチェックが行われる。
typedef int (*fpt)() [[ensures r: r!=0]]; // Ill-formed int g(int x) [[expects: x>=0]] [[ensures r: r>x]] { return x+1; } int (*pf)(int) = g; // OK.
と言うわけで、C++20に入ることになったContractの提案文書の内容をまとめた。
だいたい書き終わって細かい表現とか表記揺れとか統一しようかな、というタイミングで、最新ドラフトN4800にすでにContractが入っており(§9.11.4)、その上少し変更されていることに気がついた。ざっと見た限り、always
は結局なくなっている。あと、violation handlerの設定方法は処理系定義に落ち着いたようだ。
あとは基本的には変わっていない。とはいえ規格なので、超細かい話が追加されている。例外送出やlongjmp
での関数からの脱出では事後条件はチェックされないことや、Contractの条件式が常に同じ値を返す場合は同一性のルールに違反していても警告する必要がない(x < y
がy < x
に入れ替わっているというような場合)、などが追加されている。
ちゃんと最新のドラフトを追っていないと、アホな目に逢うということを痛感した回だった。
ともあれ、すでにドラフトに入っている程度には前向きに検討されているようなので、強化版assert
として今後使っていくことを考えてみる時期ではないだろうか。
(2/24追記)
N4800をちゃんと読んでみたところ、§9.11.4には継承した際のルールが書かれていない。恐らく継承する際のルールはなくなったのだろう。
それと、std::contract_violation
のline_number
が返す値の型がint
ではなくstd::uint_least32_t
になっている。まあ、負の行番号という概念は不思議すぎるので、妥当な変更ではなかろうか。
たまには下調べや引用などをせずに思ったことを適当に書き散らしてみたいと思う(いつもでは?)。なので、この記事には裏が取られた情報や5秒ググればわかることなどは書かれていない。すべて想像で書いている。
昨日Siriに少し話しかけており、ふとこいつはどうやって実装されているのだろうと思った。まず、音声認識から文字列に起こす。これは古典的なものから機械学習まで先行研究がたくさんあるだろう。得られた文字列を形態素解析して構文木的なものを作るのもよく研究されている。だから、この方法を取るなら既存研究をうまく活かして、よく分離されたコードで実装できるだろう。
その後はどうしているのだろう? 「近くの喫茶店を探して」のように命令形のものは形態素解析の結果から動詞(「探す」)と目的語(「喫茶店」)やそれを修飾している語(「近くの」)を取り出して、「探す」だからWebで検索、Googleに「喫茶店 近く GPS座標」を入力、とする……。しかし、これを実装する方法はたくさんあるだろう。自然言語の動詞はあいまいだ。「探す」は目的語によってするべきことが変わってしまう。喫茶店を探すならWebで検索することになるが、IoT家電を導入したので接続できるものを探して、という場合は? あるいは、PCの中にあるはずの家族写真を探して、だったら? テーブル引きにせよswitch
やmatch
にせよ、早晩無理が来るように思える。
まあ、まだPCやiPhoneに関係する仕事だけなら、動詞からありえる操作が入った関数ポインタへのテーブルを作っておくのは不可能ではないだろう。自然言語による表現は揺れるものなので、単に動詞だけを与えられて必要な操作を唯一つ選び出すのは不可能だろうが、操作を意味する関数側が受け取れる目的語を選別できるように実装されていれば、一度テーブル引きをしたあとは総当りでも不可能ではない量になりそうだ。それに、ユーザー個人の履歴を残しておけば、この検索もより高速にできる。データベースを動的に変えていいなら、ユーザーに多少の設定をさせれば、好きな語彙から操作を呼び出すこともできそうだ。
だが、AIアシスタントはIoTの方に向かいつつあるように見える。確かに、人間ならば朝起きて電気のスイッチまで歩くよりも、ベッドの中から「光あれ」と呟いて電気を付けたいものだろう。家を出てから「鍵閉めたかな」と不安にもなるだろうし、実際に鍵が開いていたら遠隔で閉じたい。実際、そういったテクノロジーの断片がかろうじて射程に入り始めた瞬間には既に、こういったアイデアはSF小説や漫画、娯楽雑誌などによってもてはやされていた。
さて、将来的にIoTに対応しようと考えるなら、上記のような実装は少し……というか大分、つらい気がする。素朴に考えるなら、「Hey Siri、暖房付けて」と言ったらSiriがエアコンに対して、リモコンで暖房をつけるときに送られる赤外線信号と同じようにエンコードされたビット列を同じく赤外線で送ればよい、と思ってしまう。確かにこれは動くが、実現可能かと言われれば否だろう。これを実装するには、Siriがありとあらゆるエアコンの赤外線信号と動作の対応表を持ちつつそれを内部のテーブルに保持しておく必要があるからだ。これは単純に不可能である。あるいは、ユーザーがSiriが入っているデバイスを購入したあと、所持しているエアコンの赤外線信号をリバースエンジニアリングし、エンコード方法をSiriに登録する必要がある。これは知識と意欲のあるニンジャ級ハッカーならできるだろう。が、多くの消費者はニンジャ級ハッカーではない。
となると、取り得る戦略はかなり少なくなる。少なくとも、家電側が歩み寄りを見せ、AIアシスタントの中央集権をやめないといけないだろう。家電がIoT対応をして、何らかの方法でそれを操作するインタフェースを提供し、AIアシスタントがそれに則って仲介役を果たすという形なら現実的になってくる。残る問題は、どこでAIアシスタントが処理を止めるか、言い換えると、各家電がどこまでやるかだ。
極論、各家電がそれぞれスマートアシスタントを持っていれば、Siriの仕事はなくなる。「Hey エアコン、暖房22度ね」で済むなら、「Hey Siri, 暖房22度にして」を聞いたSiriは単に同じ文章を、あるいはもう音声信号そのままを周囲の家電全員にブロードキャストすればよい。よくわからなかった家電はSiriにエラーを返し、Siriは全員が失敗したときだけ失敗を伝えればよい。Siriの実装コストは極端に下がる。が、各家電の実装コストは跳ね上がるし、Siriの存在意義が怪しい。
逆の極端として、各家電はシリアライズされたデータを受け取り、それを内部で展開すると考えてみよう。これはリモコンが赤外線信号を送っているのと同じだ。だがそのままだと先述の通りうまく行かないので、ニンジャ級ハッカーがするであろうことを肩代わりする必要が出てくる。つまり、各家電が自身に送ってほしいデータのシリアライズ方法を説明できるようにしておき(例えば、JSONで送ることにしておき、必要なフィールドと型を指定するなど)、それをSiriに先に伝えておくのだ。あるいは、そのような処理をパッケージ化したデバイスドライバを同梱しておき、購入後AIアシスタント側にそれがインストールされるようにする。そうすれば、Siriは自然言語処理をしたあと、iPhone側で行うことと同様の流れで処理ができるようになる。こっちの方が現実的だろう。
この場合に問題になることがあるとしたら、まず全家電と全AIアシスタントが同意したプロトコルを先に決めておく必要があることだ。家電メーカーもAIアシスタントメーカーも、自社のプロトコルをそのままデファクトにしてしまいたいという欲求をちゃんと抑えて、それぞれのプロトコルの長所短所をしっかりと認識して突き合わせ、止揚しなければならない。それを国際規格にして、以降全員が(ある程度拡張はされるだろうが)その国際規格に準拠する。規格制定には時間がかかる気がするが、ちゃんとできればよい方法だ。既存の何かに乗っかってもよいわけだし。あと、この方法だとと、家が巨大になるとスケールしない可能性があるのではないか。というのも、家電が増えるに連れてAIアシスタントが持っている可能な操作のテーブル、あるいはデバイスドライバのリストがどんどん肥大化するからだ。高性能でたくさんの可能な操作を持っている家電を大量に買う富豪の家に買われたAIアシスタントは大変だ。受け付けるべき命令が増え続け、それでも人間を待たせてはいけない。なんだかんだ現実的な範囲では問題にならないかもしれないが、少し不安ではある。これから先、どんな奇妙な家電が増えるかわかったものではないからだ。
先の2つの解決策の中間に、「構文解析を終えた命令文を直接対象の家電に送る」というものがある。Siriは音声認識と構文解析をし、自身がするべき操作(Webで検索、5分計るなど)は今まで通りこなし、自分ができる操作ではないと判断したら、できそうな家電に命令の構文木をそのまま送る。各家電は、構文木を渡されると自分で何をすべきか解釈する。すると、AIアシスタントのするべきことはかなり減る。家電側の実装コストは高くなるが、前処理済みの構文木が渡されるならスマートアシスタントを実装するのに比べるとするべきことは十分少ないだろう。また、このやり方なら家電の数が増えてもSiriがするべき仕事があまり増えないという利点もある。最悪全員にブロードキャストすればよいのだし、関係のありそうな家電にのみ送るにしても、キーワードから家電のIPへのテーブルさえ持っていればよい。家電の種類に線形にテーブルサイズは大きくなるが、家電の機能に比例してテーブルが大きくなる心配はない。いいとこ取りのような気もするが、面倒そうなところも両取りになっており、最終的には手放しで喜べる状況でもなさそうだ。この場合も規格制定は必要で、特に構文木を送るプロトコルを定める必要があり、結構面倒な気がする。家電メーカーも中途半端に賢いドライバを書かないといけない。三方一両損な形だ。やはり、各家電がAIアシスタント用のドライバを持っていて、購入時にインストールされるようにしておくのがよいのだろうか。
しかし、ずっとハッシュテーブルのようなものを持っておくと想定して考えてきたが、ここの速度と精度は性能に聞いてくるので、いろいろ試してみるべきだろう。「構文木から必要な操作を取り出す」というタスクを、「パターンに対応するラベルを貼る」という操作に置き換えることを考えると、流行りの機械学習が強みを発揮しそうな気がする。さらに、ユーザーがある程度アシスタントの動きを訂正してくれるなら、オンザフライでユーザーの癖を学習できるかもしれない。とはいえ、ユーザーが懇切丁寧に子供を育てるようにAIアシスタントに言葉とするべき仕事を教えてくれるとは思えないので、ある程度汎用で機能するような重みを先に学習して持っておく必要もある。どうせテーブル引きの場合でもテーブルを作る必要があるので、教師データを作るのが面倒ということもないだろう。ただ、テーブルがそんなに大きくならず、検索もそう難しくないとかならわざわざ学習をするまでもない。実際どういう実装になっているんだろうか。
というようなことを考えて、「Hey Siri, ソースコード見せて」と聞いてみたが、はぐらかされてしまった。今は色々と話しかけつつ、うまく口説き落とせないか試してみている。
Rust Book 勉強会で発表をしてきた。
これは、結構前にQiitaのC++アドベントカレンダーで書いた内容と、Ben Deane氏によるCppConでの発表"Using types effectively"が下敷きになっている。
あ、この資料にクレジット書き忘れたのを思い出した、やっちまった
さて、その中で以下のRedditで出ていた話も紹介した。
スレ主の質問は、以下のenum
のサイズが20になるのは何故かというものだ。
enum Vector { V2(f32,f32), V3(f32,f32,f32), V4(f32,f32,f32,f32), }
答えは、データのレイアウトが以下のようになっているからだ。
|tag|padding|data region| |u8 |[u8;3] |[u8;16] |
データ領域は最大のものが格納できるサイズになり、どの値が入っているかを示すタグがきて、データ領域のアライメント調整用のパディングが入るというものだ。
さて、これは本当にこれ以上縮まないだろうか。
16バイトで表現できないのか?
できる気がしたので記事を書くことにする。ところでRustのf32
とかf64
ってIEEE754に従うよね?
NaNはご存知だろうか。Not A Numberの略で、値がもはや数値ではない場合に使う。例えば、0.0 / 0.0
の結果などがNaNになる。このNaNは特殊な値で、それとの大抵の演算結果がNaNになり、またNaNに関するあらゆる比較は偽になる。NaN == NaN
すら偽になる。
このNaNはexponentのビットが全て1で、mantissaが非ゼロという定義になっている。つまり、mantissaのほとんどは手付かずのまま残るということだ。mantissaのビットパターンを変えても、NaNのままにしておける。
そして、mantissa
が割と自由に決められるということは、そこに情報を押し込めるということだ。これはNaN Boxingと言われており、言語処理系でたまに使われる。
つまりだ。Rustには、NaN
の値として特別な値を準備しておき、先のenum
でV2
に値が入っていたときに残りのf32
をtagged-NaN
にしておいてV2
であることを表現するという手段が取れるだろう。ではV4(1.0, 1.0, NaN, NaN)
とどう区別するかというと、通常の演算で作られるNaN
とは異なるビットパターンを持つNaN
をtagged-NaN
として使っておけば、区別できるのではないか。
|f32|f32|tagged-NaN|tagged-NaN| |f32|f32|f32 |tagged-NaN| |f32|f32|f32 |f32 |
まあ、これを実現するためにはアーキテクチャが通常の演算から返すNaNのビットパターンが固定されている必要と、NaNの演算結果でNaNのmantissaのビットパターンが変化しないことが保証されている必要がある。
どうなのだろう。そこのところをよく知らない。
とにかく、Rustは未だに上記のenum
のサイズを20バイトにする。ここで書いたことが実はハードウェア的に実装不能なのか、それとも実装がややこしすぎる、あるいは手間に対して利益が少なすぎるとみなされているのか。私が気づくようなことがまだ提案されていないとはあまり思えないが、はて。
Rust業界に詳しくないので既に広く知られているものかもしれないが、昨晩突如として以下のようなトリックを思いついた。
struct X<T> {/* fields omitted */} impl X<f32> { pub fn f32(self) -> Self {self} } impl X<f64> { pub fn f64(self) -> Self {self} } let x = X::new(/* ... */).f64() // ^^^^^^ // 他の関数呼び出しなどからは無理でも、これのおかげでT = f64と推論できる
いや、明示的に型指定しろよ、それかデフォルト型パラメータを使えよ、と思う方が大半であろうが、以下のようなケースで便利になるのではないかと思う。というか困っていたから思いついた。
まず、何らかの物体の三次元座標が入ったファイルがあり、それを読み込みたいと思っているとする。
A 1.00 1.00 1.00 B 2.00 3.00 1.00 ...
これを読み込む際、例えばデータ量が超絶多いとか、可視化できればそれでいいから精度は低くていいとか、あるいはその両方といった理由でf64
ではなくf32
を使いたいケースというのはあるだろう。そういう場合、まあcfg
でビルド時に決めてしまってもいいのだが、ジェネリクスを使って解決することもできる。
struct Particle<T> { name: std::string::String, pos : [T; 3], }
で、これを読み込みたいとき、例えばちょっとLazyにしたかったりするだろう。そういうときはIterator
をimpl
するのがよさそうだ。
struct Reader<R> { /* fields omitted */ } impl<R: std::io::Read> std::iter::Iterator for Reader<R> { type Item = Particle<T>; // ^^^ // この型パラメータTはどうするのか? fn next() -> Option<Particle<T>> { // ... } }
すると、Iterator
のItem
に型パラメータが必要になる。だが、Reader
は今Particle
の型パラメータT
を知らない。なのでT
を決めようがない。
仕方がないので、Reader
にダミーのパラメータを持たせることになるだろう。
struct Reader<T, R> { _marker: std::marker::PhantomData<fn() -> T>, // ... } impl<T, R: std::io::Read> std::iter::Iterator for Reader<T, R> { type Item = Particle<T>; fn next() -> Option<Particle<T>> { // ... } }
さて、このReader
をnew
するとき、どうすることになるだろうか。
理想は、R: std::io::Read
の方は型推論が何とかしてくれて、T: f32 | f64
の方だけユーザーが明示的に指定できるというものだろう。
let reader = Reader::<f32>::new( std::fs::File::open("example.dat").unwrap() );
だがこれは通らない。C++のtemplate
関数は決まっていない型パラメータだけを明示的に指定することを許すが、Rustは許さない。二つパラメータがあるなら二つ書く必要がある。
まあそれでも、「これは型推論しろ」という意思をアンダースコアで表現できるのでまだマシだが。
let reader = Reader::<f32, _>::new( std::fs::File::open("example.dat").unwrap() );
これでいいのでは? いや、考える必要があるのはユーザーのことだ。新規ユーザーがこのサンプルコードを見たら、「おや、このライブラリは柔軟性のために書きやすさと学習コストを犠牲にしているようだぞ? こんな単純なサンプルですら型推論が助けにならないなら、多分この後ずっと、どの型が何個ジェネリクスパラメータを取るか毎回調べないといけなくなるんだろうな、はーめんどくせ。なんのために型推論があると思ってるんだ。Rustやめちまえ」と思うだろう。
このユーザーは私の心の声でもある。昔書いたライブラリの構造体のジェネリクスパラメータの数なんか覚えてねえよ。コンパイラの仕事だろ。コンパイラが数えろ。
で、最初は「仕方ない、たいてい必要になるのはファイルを開いて読み込むことだから、それをするユーティリティ関数でも書いて、そこでf32
とf64
を選べるようにするか」と考えた。
pub fn open<T, P>(path: P) -> Result<Reader<T>> where P: std::convert::AsRef<std::path::Path> { // ... }
ああーっ、また型パラメータ増やしてやがる! お前はいつもそうだ。誰もお前を愛さない。
さて、そうなると、やはりこの関数を呼ぶときにも型パラメータの数を意識しないといけない。
let reader = crate::reader::open::<f32, _>( "example.dat" ).unwrap();
何も簡単になってないじゃないか!
というわけで、冒頭のトリックが有用になったりするわけだ。
impl<R> Reader<f32, R> { pub fn f32(self) -> Self {self} } impl<R> Reader<f64, R> { pub fn f64(self) -> Self {self} }
これを使うとrustc
の型推論を補助することができる。
let reader = crate::reader::open("example.dat").unwrap().f32();
f32()
を呼べるのはReader<f32, R>
だけだから、T = f32
に決定する。そしてopen
ができるのはReader<T, std::fs::File>
だけだから、R = std::fs::File
に決まる。というわけで、明示的に型パラメータを一切指定せずに、全ての型パラメータを決めることができるようになった。
別の行に書いても多分大丈夫だと思う。
if let Ok(reader) = crate::reader::open("example.dat") { let reader = reader.f32(); }
これちょっと格好良くないか? ちょっとビルダーパターンっぽい気もする。動的に型変えられるようになってる感があって面白い。
実際は、動的に変わっているのではなくて、rustc
が型不定のまま1行めを解釈したあとreader
に対してf32()
が呼ばれているのを見てそこで1行めのreader
がReader<f32, File>
だったことを知るのだ。なので実際には遡って型パラメータが決定されていっている。
これで型パラメータに怯えることはなくなった。型パラメータの数をいちいち数える日々から開放された。
安心して今夜も眠れるだろう。
RustのTraitは内部に型を持つことがある。関連型(associated type)だ
trait Hoge { type Value; } impl Hoge for Piyo { type Value = Fuga; }
このValue
型についてトレイト境界を付けたい。
つまり、ある型T
があり、型<T as Hoge>::Value
がOtherTrait
を満たす場合のみ使える関数を使いたい。
以下のように書けたらよいのだが。
fn foo<T: Hoge<Value: OtherTrait>>() -> () { // ... }
残念ながらこれは通らない。
error: expected one of `!`, `(`, `+`, `,`, `::`, `<`, or `>`, found `:` --> src/main.rs:11:21 | 11 | fn foo<T: Hoge<Value: OtherTrait>>() -> () { | ^ expected one of 7 possible tokens here
ではどうやって書くかというと、実は割と素直に書くと通る。
fn foo<T>(x: T) -> () where T: Hoge, // ここではまだ何も言わない <T as Hoge>::Value: OtherTrait // これを足す { println!("hello! {}", x.value().other()); }
トレイト境界の左辺にそれ書けるんかい! と思った。
動くサンプルを置いておく。 play.rust-lang.org
さて、似たような、だが少し違うケースがある。今日実際に困っていたのはこちらだ。
まず、自分のクレートに既にcrate::error::Error
を定義してあり、よくある型についてFrom for Error
を実装しているとしよう。
pub struct Error {/* ... */}; type Result<T> = std::result::Result<T, Error>; impl From<std::num::ParseIntError> for Error { fn from(error :std::num::ParseIntError) -> Error { // ... } }
で、何らかのフィールドを持つジェネリクス構造体があるとする。それを読み込めるようにしたい。
pub struct Hoge<T> {/* ... */}; impl<T> std::str::FromStr for Hoge<T> { type Err = Error; fn from_str(line: &str) -> Result<Self> { // ... } }
このfrom_str
でHoge<T>
のフィールド(T
型)を読むためにparse
を使いたい。そのためには、まずT
がFromStr
を実装している必要がある。
impl<T> std::str::FromStr for Hoge<T> where T: std::str::FromStr { type Err = Error; fn from_str(line: &str) -> Result<Self> { // ... } }
それだけではない。rustc
はすぐに、<T as FromStr>::Err
がcrate::error::Error
に変換可能でないとこの関数はコンパイルできなくなることを見抜く。なので、ここまで話してきたような、関連型に対するトレイト境界が必要になるのだ。
ところで、今回はFrom</*...*/> for Error
を実装していたのだった。とすると、これはError
に対して実装されているので、先程までと同じような書き方はできない。
Error
がトレイト境界From<T as FromStr>::Err
を満たしている必要があるからだ。
これも、そのまんま書くと通る。
impl<T> std::str::FromStr for Hoge<T> where T: std::str::FromStr, Error: From<<T as std::str::FromStr>::Err> // これ { type Err = Error; fn from_str(line: &str) -> Result<Self> { // ... } }
それ左辺に書けるの!?(驚愕)
Error
は普通に定義されたただのstruct
だったので、それに対してトレイト境界を設けられるとは思っていなかった。トレイト境界はジェネリクスの型引数に対して課すものだと思っていたからだ。
まあでも、わかってしまえば結構そのまんまだった。試してみるものだ。
追記(1/22)
当初std::ops::Add
の実装をよくわかっておらず、ジェネリクストレイトの型パラメータと関連型を取り違えていた(該当箇所は混乱を避けるため消した)。
std::ops::Add
の実装は以下のようになっている。
pub trait Add<RHS = Self /* 型パラメータ */ > { type Output; // 関連型 fn add(self, rhs: RHS) -> Self::Output; }
RHS
はあくまで型パラメータであり、Output
が関連型だ。RHS
を書くべき場所に関連型を書けないのは当たり前だし、型パラメータにさらなる型パラメータとそのトレイト境界を書けないのも当然だ。