セキュリティ・ネクストキャンプ 2021 応募課題晒し

小学校6年の頃から趣味でプログラミングを始めた。最初の頃はExcelの関数で遊んでいたおぼろげな記憶がある。たしか、フランス語の動詞を入力すると活用形が出てくるようなものを作っていたりした。気づいたらHTML+JavaScriptでやっていた。当時アメリカに住んでいたので、グリニッジの図書館でHTMLの本を借りコードを書いた記憶がある。JavaScriptの方は http://www.pori2.net/js/ などで勉強した。最初のころはまともな開発環境を知らず、申し訳程度のsyntax highlightingのできるエディタを使い、「try-catchで囲んでアラートが出たら実行時エラー、そうでなければ構文エラー」という知識のもとエラーのある行を二分探索したり、簡易的なプログラミング言語を考えその構文解析器を正規表現と条件分岐の組み合わせで書いたりという、今から考えれば気の遠くなるような無駄な努力を積み重ねていた。Windows Vistaの「ガジェット」はHTML+CSS+JavaScriptなので、それも書いた記憶がある。(残念ながら、そのガジェットはXPにダウングレードしてもらった時にバックアップを取り忘れたので現存しない。)
 そのようにして貧弱な開発環境と貧弱なエラー検出機能のもとJavaScriptに苦しめられていたある時、日本情報オリンピック夏季セミナーに参加し、Haskellという言語の素晴らしさを知った。強力な静的型付けのもと、凡ミスをコンパイル時にほぼ捕らえてくれほとんどバグが出ないという、JavaScriptと正反対の性格に強く惹かれ、以後Haskellもやるようになった。
 日本情報オリンピック夏季セミナーにはその後も3回参加し、情報分野の最新の知見に触れる機会を得ることができた。
 中高(一貫校であった)ではコンピューター部に所属し、1年1回の学園祭に向けてゲームを出したり、情報オリンピックの対策をしたりしていた。
 あとは、Brainf*ck中に出てくる頻出パターンを関数や演算子としてゼロコスト抽象化できるプログラミング言語を自作した。詳しくは https://hsjoihs.hatenablog.com/entry/2019/12/20/202158 にある。これを作り始めたのはもう7年ぐらい前になり、その後「構造体とか実装したいなぁ」と思いつつ、未だに暇とやる気と機会がなく実装できていない。
 また、日本情報オリンピックの予選を3年連続突破し、3回本選に参加することができた。残念ながら本選突破は一度も叶わなかったが、計算量を落とす方法やLinuxの使い方など、学べたことはとても多かったのみならず、数多くの人々と知り合いになれた。
 東京大学スタンフォード大学に併願し、共に合格した。東京大学には最初の3ヶ月間だけ通い、現在休学中である。スタンフォード大学では数学科と物理学科の両方を専攻しているが、コンパイラやグラフィクスなど、一部のコンピュータサイエンスの授業も履修した。コロナ禍で授業が2020年3月からフルリモートとなり、2020年6月からはずっと日本で暮らしている。
 2018年の夏にはセキュリティ・キャンプ全国大会でCコンパイラ自作班に応募した。当時の応募用紙を見る限り、それまでに私は「ハロー "Hello World" OSと標準ライブラリのシゴトとしくみ 坂井弘亮」「新・標準プログラマーズライブラリ C言語ポインタ完全制覇 前橋和弥」「プログラミング言語を作る 前橋和弥」「C言語 入門書の次に読む本 [改訂新版] 坂井弘亮」「ロベールのC++入門講座 ロベール」など様々な書籍を読んでCの仕様については理解を深めていたが、実際にCでコードを書いた経験に乏しかった。それを改善するきっかけになればと思い応募したところ、非常に楽しく有意義な経験をさせていただくことができた。この際、Macに存在する微妙な非互換が面白かったので、それについてまとめて技術書典7で OtakuAssembly Vol.1 というタイトルで共著し頒布した。
 2019年にはセキュリティ・キャンプに携わらなかったが、夏に講師の方とお会いした際に「なぜチューターに応募しなかったのか」と問われた。ということで、その次の年にはチューターに応募しようと決意し、2020年にはセキュリティ・キャンプ全国大会のCコンパイラ自作班でチューターをさせていただくことになった。
 私が得意としていることとして、誤字を素早く検知するというのがある。2020年チューターをやった際に、内田公太さん(uchan_nosさん)の資料を見せていただく機会があったので、素早く眺めて20個ほどのミスを報告させていただいたところ、出版された「ゼロからのOS自作入門」の謝辞に名前を載せていただけた。また、「ハリー・ポッター」シリーズをもとにした二次創作である Harry Potter and the Methods of Rationality の和訳「ハリー・ポッターと合理主義の方法」( https://syosetu.org/novel/160391/ )の査読も担当させていただいている。
 創作活動が好きであるので、過去4年間は主に「架空の伝統を創作する」という活動を複数人で行ってきた。架空世界で伝統的に遊ばれてきたという設定のボードゲーム「机戦;セッカイク」( https://sites.google.com/view/cet2kaik )のオンライン対戦を実装( https://github.com/jurliyuuri/cerke_online_alpha )したり、その民族が用いる言語のコーパスhttp://jurliyuuri.com/spoonfed_pekzep/index.html )だったり、周辺民族で用いる文字のデータセットhttps://github.com/jurliyuuri/linzklar-recognition/ )だったりを整備してきた。スタンフォード大学でコンピュータグラフィックスの自由課題が出たときにも、これを3Dモデル化してレンダリングして提出した( https://twitter.com/sosoBOTpi/status/1209028393863245824 )。これらの創作活動や、歴史言語学(人類の話すそれぞれの言語の音や構造が、どのような変化を遂げてきたかを調べ推論する学問)に関する話題は、https://sozysozbot.github.io/ にリンクを掲載している。この4日間は、上記のボードゲームの作者がそこからスピンオフして新たな架空伝統ボードゲームを作ったので、それに「ケセリマ」という名前を与え(この名前は、この応募課題の一回目の締め切りの際に「無意味なカタカナ4文字」の例としてとっさに思いついて書いたものである)、そこの民族が話している言語を急ピッチで共同で創作し、ルールブックをその言語に訳し、ドメインを取り (keserima.com)、GitHub Pages をセットアップする (https://github.com/keserima/keserima.github.io) などの全体的整備を行っていた。現在、ElmでGUIを実装中である。
 言語が好きであることから、その方面の繋がりも多く、アステカ帝国公用語であったナワトル語の研究者である佐々木充文さんとのご縁もあって、過去1年は現代ナワトル語の授業を履修した( https://hsjoihs.hatenablog.com/entry/2020/09/24/152311 https://hsjoihs.hatenablog.com/entry/2021/04/07/051427 )。スペイン語で行われる授業に英語での通訳が付いているという形で開催されている授業である。それもきっかけに、3ヶ月ほど前からDuolingoというプラットフォームで言語学習の時間を毎日確保するようにしている。今のところ102日連続で学べている( https://www.duolingo.com/profile/vatimeliju )。
 参加できた場合にセキュリティ・ネクストキャンプに期待することは、情熱ある仲間たちと面白い話を交換し合うことである。最近は大学院出願のための各方面との調整などといった楽しくもない作業に悩殺されており、情熱を持てる対象についてもう一度真摯に向き合う時間を持つというのは、今後の人生を考えていく上で欠かせないと思っている。ゆえに参加していきたい。
プログラミング言語Rustにおいては、値は常にムーブ(memcpyしてメモリ空間上の新しい位置に移動)できるという前提がある。ところでこれは自己参照構造体を扱う上で困るので、Pinという仕組みが導入されており、これを使うと自己参照構造体を上手く扱うことができることが知られている。では、このPinという仕組みはどう実現されていて、またなぜ現在の実装のような形になる必要があったのか?という疑問を設定した。

調べる前に念頭にあったのは、原将己さん(qnighyさん)の「?Sizedが十分ややこしいのでもう金輪際あれを増やしたくないという気持ちがあるらしく、結果?Moveは誕生せず、Pinが生まれた」というツイート。このツイートには納得しかけたが、しかしながら、?Sizedというのは「コンパイル時に型のサイズが分かっている保証のない型」というだけの意味であり、それを踏襲すれば?Moveというのは「ムーブできる保証のない型」というだけの比較的シンプルな意味論であるだろう。一方で今採用されているPinという仕組みはそれに輪を掛けてややこしい仕組みであり、?MoveではなくPinという解決策が提示されたきっかけが「ややこしさ」のみであるという主張には強く違和感を覚えた。

ちょうどDiscordでhikaliumさんが主催していた「Writing an OS in Rust輪読会」が一段落つき、かつPinについての解説が間に合わずに終結したので、次週の会合までPinについて調べ、まとめて発表することにした。

まず、C++では「ムーブできない型」というのを簡単に作ることができる。コピーコンストラクタとムーブコンストラクタを潰せばよい。しかしながら、Rustではコピーコンストラクタを明示的に書く方法は用意されているが、ムーブコンストラクタは書く手段がない。「Rustはあらゆるムーブがmemcpyである」という記載はちらほら確認できるが、そのような保証をどこでしているのかを探すのに手間取った。これについて調べるために、?Moveに関する過去の議論を遡ったところ、「Rustの公式サイトのトップのQ&Aに堂々と『Rustにはムーブコンストラクタはない』と保証している」という旨の発言が見つかったが、リンク切れであった。これはRustの公式サイトが一回大きなリニューアルをしていたからであり、旧い内容はprev.rust-lang.orgというURLに移設されていたからである。消さずに残してくれているのはありがたいのだが、リンクが切れないようにしてくれていたらもっとありがたかったのになぁ……とも思った。

旧サイトが保証していた内容は、「どんな型の値であってもmemcpyによりムーブされる。これにより、代入・関数渡し・関数からのreturnなどで副作用がないことが保証され、多相でunsafeなコードを書くのがたやすくなる」という旨であった。なるほど、C++のムーブコンストラクタは例外を投げることができるのか。ということでそれを調べてみたところ、C++ではN2983においてムーブコンストラクタが例外を投げるのを可能としていたことを知った。これは、「例外を投げる可能性がないわけではないが、その可能性が非常に低い」というようなムーブコンストラクタを書けないというのは最適化の機会を妨げることになるからだ、としていた。その代わり、std::move_if_noexceptを用いることで、例外を投げないムーブコンストラクタだけを呼び出すことができるようになった。

さて、前述の通り、Rustにおいてはムーブというのは代入したり関数に渡したり関数から値をreturnしたりするときに気軽に行われる操作である。?Moveに関する過去の議論を遡ったところ、?Moveの明確な欠点はここにあると論じられていた。ムーブができないということはコンストラクタから値をreturnすることができないわけで、つまりは使いたい場所で構造体リテラルとして記述するしか方法がないということである。これではprivateメンバがある際にどうしようもない。ということで、議論は「借用されるまではムーブを許すというのはどうだ」といった複雑化の方向を辿っていったようである。

最終的に?Moveが採用されなかったのは、?Moveが互換性を破壊するという点が原因であった。今まで型変数が暗黙に持っていた前提を破壊するオプションを付けると言うことは、全ての型引数に対して「ここって ?Move 要るかな?」と考える必要を発生させるということである。他にどうしても方法がないならそれを行うしかないのだろうが、Pinという仕組みが発明されたことにより、コンパイラに変更を加えることなく自己参照構造体などの「ムーブするとマズい値」を安全に扱う方法が見つかったので、それを採用し?Moveを採用しないということになったようだ。

さて、?Moveが言語に入らなかったということは、Rustにおいては値は常にムーブできるという前提があるということである。ではPinというのは何かというと、「ある値への参照 Pin<’a, P> (ただし P は参照型であるとする)が誕生したら、それ以降は(その値に対するdropが呼び出されるまでは)参照されている値が動くようなことがあってはなりません」という契約にすぎない。契約を破りうる手段が全てunsafeなAPI(呼び出す際に、プログラマ側が注意して「私は守るべき条件を破っていない」と明示的に確認する必要のあるAPI)として提供されていることによって、動かしてはいけないと契約した値はunsafeなAPIを用いない限り間違ってムーブしてしまう恐れはない、というカラクリであった。

ところで、このPinの契約には一つ例外規定がある。それは、Unpinという性質を満たしている型の値については契約が成立しないと定められていることである。ほとんど全ての型はデフォルトでUnpinという性質を満たしており、Unpinでない型を作るにはstd::marker::PhantomPinnedという型を構造体のメンバに含める必要がある。この点についてあまり深く言及せずに以上の内容を「Writing an OS in Rust輪読会」で説明したところ、hikaliumさんから「なぜそのような仕組みになっているのでしょうか?そんなUnpinなど用意しなくとも、契約は常に成り立つと規定してもPinという仕組みは成立するはずなのに、なぜ例外規定があるのでしょう?答えをご存知でしたら教えてください、そうでなければ一緒に探しに行きましょう」というご質問を頂いた。確証が持てなかったので、輪読会の残りの時間でそれらの疑問を解消しにいくこととなった。これについては、Pinを導入したRFC2349で「ムーブ不可というのはFutureを扱う際などに必要になるわけだが、ムーブ不可であるFutureもほしい一方で、同時に(自己参照などの問題がない値を扱うための)ムーブ可能なFutureもほしい。二種類のFutureなどを作ることでこれを解決するのも可能ではあるが、エルゴノミックではない」と記載されていた。ここからはきちんと追いかけていないので推測となるが、どうやらPin以前のFutureは参照型に可変参照&mut T を用いていて、それをムーブしないようにプログラマが努力するという方針で実装されていたようだ。ということで、「ムーブしても問題ない型に対してはUnpinが実装されているので&mut Tと同等の機能を提供し、ムーブしたらマズい型というのはPhantomPinnedでその旨明記する」という折衷案になったのでは、という仮説を立てた。
「自分の知識をアウトプットしよう」
物事を一旦知ってしまうと、知らなかった状態に戻るのは難しい。「こんなこと、その手の人ならみんな知ってるだろうしわざわざ書くまでもないな」と思いながらもアウトプットしたものに対して、意外なところから「えっそうなんだ、知りませんでした、ありがとうございます」というフィードバックを得られたりする。もちろん、それなりの形でアウトプットするのであればそれなりの責任が伴う。誤った情報をアウトプットしてしまうと、それを読んだ人は「えーじゃあなんでこれ上手くいかないんだ?」となり、益を与えるはずが無駄な時間を食わせてしまうことになる。ということで、必要な情報を列挙し整理し考えてアウトプットする際に、分からなかったところについては恥を忍んで「ここは私は分かりませんでした。ご存知の方がいましたら教えてください」と書いてアウトプットする誠実さが必要であるし、確実でないことであるならばどれほどの確度で言えることであるのかを明言するというアウトプットの仕方が欠かせないであろう。

「形式手法を知ろう」
形式手法に私が初めて触れたのは、中学2年生の時に参加した情報オリンピック夏季セミナーで原将己さん(qnighyさん)がCoqをひたすら広めていたのがきっかけである。ちょうどその夏季セミナーではHaskellを習い、今まで私が触れてきたJavaScriptとかいう「問題のあるコードパスに入るまでバグが発覚せず、しかもそのバグの原因というのが完全に別の行で読むべきフィールド名を間違えたことでundefinedが代入されていたからだ」などといった地獄から解放される手段があるのだということを知った。このときから形式手法には強い興味を持っており、同じ分野に興味のある人を集め、2019年11月からDiscordで毎週「型システム入門 −プログラミング言語と型の理論−」の輪読会を開催してきたりした(これは今でも続いている)。形式手法の福音に毎日助けられながらコードを書いている今、関心のある人々と語り合い学びあうことができれば幸いである。

「低レベルGPUプログラミング」
GPUは、「みんな使っているなぁ」と思いながら私は全然使ってこなかった分野である。そもそも私はあまりグラフィック系のコードを書いてきたことがなく、彩りというものは全てWebブラウザに任せてきた。スタンフォード大学ではコンピュータグラフィックスの授業も取ったが、GPUがどのような計算をやるのかを実感するためにそれをCPU上のプログラムとして実装したり、「この三角形の集合をこうやるとあとはライブラリに隠蔽された部分が全てやってくれるよ」というのを学んだりと、もちろん重要ではあるのだが「GPUの低レイヤ」という側面は全く学んでくることができなかった。CPU側のレイヤを下っていく探索は一通り学んできたが、GPUについてその実なにも知らないというのも面白くないので、楽しみにしている。
 人の話す言語が好きである。人類は言語についてまだ全然なにも分かっていないにもかかわらず、とりあえず意味を伝えることができている。如何なるプロトコルで伝達すべきかというマニュアルがRFCを読みに行けば書いてあるコンピュータの分かりやすい世界と異なり、どこにも網羅的な仕様書が書かれていないのになぜか赤ん坊は言語を学ぶことができるし、大人も十分頑張れば結構上手に言語を学ぶことができる。非常に面白い。コンピュータの言語では0x00から0xFFまで全てを合法として意味を与えることは普通であるが、人間の話す言語はスカスカであり、「ムスビメ」には意味があるが「ケセリマ」には意味が無い。このスカスカさは聞き間違いを減らす役割を果たしていると言われていて、人間が言語を話す際の情報伝達速度はどの言語でも秒速39ビットであると主張する研究もある。面白い。さらに、言語は時間がたつにつれ変化し、ある音が別の音と区別されなくなったりする。しかし、そういう「減る作用」に対して、複合語などの形成による「増える作用」が上手くバランスを取っているのが本当に面白い。

 神の作り出した美しい自然の景観を見て、風景画を描かずにはいられない人というのがいる。風景画をコンピュータに描かせずにはいられない人というのがいる。もちろん、実際の風景というのは、「太陽の中で核融合によって生成されたガンマ線が長い時間を掛けて可視光として放出され、それが膨大な距離を経て地球に届き、クロロフィルの吸収特性により緑が他の色ほど吸収されず、主に緑が多めの反射光が網膜に届き、錐体の吸収特性にしたがって脳に電気信号として入る」といった、気の遠くなるような計算量を世界がやってくれたことに対する帰結である。しかしながら、それよりも遥かに慎ましい計算量によって、風景画を描いたり、風景画をコンピュータに描かせたりできる。

 ということで、山川を見て山川の絵を描くのを好む人がいるように、私は人間の話す言語を眺めるのが好きだし、人間の話す言語を創作し描くのも好きである。