B1

京大は入学するとビラロードとかいうクソみたいなところを歩かされるんですが、そこをビラ 1 枚で通り抜けるなどしていました。

プログラミングの記憶はほとんど無いけど、鼻くんとかを使ってプログラムを書いていた気がします。

もしかしてカオスの坩堝はこの学年で作ったんじゃないかと思ったらやっぱりそうでしたね。もうそんなになるのか。もともとは 2017 年の AdC をやるためのブログだったんですが、いまや総記事数が 300 近いサイトになりました。

あと第二外国語でロシア語をとっていました。キリル文字が面白かったので坩堝に記事を書いたりしていました。今でもキリル文字が出てくると頑張って読もうとするけど、ロシア語自体はほとんど忘れてしまいました。

有志で蟻本を読む輪読会をしたり、Linux 講習会をやったりしていました。AtCoder で ABC/ARC とかを解いていたのも多分このころですが、解けなかった問題の解答がコンテスト後に Twitter に流れてくるのが嫌でやめました。メンタルが競プロに向いてない。

GPA ポケモンのサイトを作ったのもこのころです。

2018 年の正月には、ddの出力先を間違えてディスクを吹き飛ばしたりしていました。fsckを振り回してなんとか復旧しました。

割と A+を取れた授業が多くて GPA 4.12 とかでイキってたら、何人か友達をなくしたりしました。みんなは気をつけてください。

あと鮟鱇丼という Mastodon を立てていたのですが、サーバー操作ミスで吹き飛ばしたりしていました。

B2

5 月にセキュリティ・ミニキャンプ in 兵庫に、8 月にセキュリティキャンプ全国大会に@VTb と一緒に参加しました。全国大会の顛末は坩堝にも投稿しました（応募用紙, 開発記）。低レイヤー的なことをやったのはこれが初めてだったのですが、めちゃめちゃに楽しい経験ができました。 aqcc を書いた後に物足りなくなってAQaml というセルフホスト OCaml コンパイラを書いたりもしました。あと Kernel/VM 関西 9 回目で aqcc について発表して、ベストオブ頭おかしいをもらいました。めちゃめちゃ嬉しかったです。

この話をアカデミアのよくしらないおじさんにしたら全否定されたので、アカデミアには絶対に行かないという強い意志を持ったりしました。このあたりの話はいずれまとめて短いエッセイにしたいなぁと思っています。

ちなみにこのおじさんはこの後もちょくちょく私を惑わせています。

ミニキャンプと同時期にわくわく鮟鱇ランドという Mastodon を立てて、身内で遊び始めました。これも若干メンバーを増やしつつ現在まで続いています。ちなみにこの名前は wotto さんが考えてくれたやつです。

初めは Twitter と相補的に使っていたのですが、最近はもうほとんど Mastodon でしか活動していません。Fediverse はいいぞ。みんなも連合しよう。 Mastodon を 1 年半くらいやったときに坩堝にも記事を書きました。ちなみに B3 で本格始動する未踏のチームから参加のお誘いが来たのもこの Mastodon の DM でした。

あとニューラルネットワークの研究を書くプロジェクトに参加して論文を書いて、査読が通らなかったりしていました。

割と A+を取れた授業が多くて GPA 4.12 とかでイキってたら、何人か友達をなくしたりしました。みんなは気をつけてください。

B3

2019 年の 3 月に@VTb と@nindanaoto にいきなり準同系暗号を用いたセキュアなプロセッサ開発に誘われて、急いで応募資料を書いて未踏事業に応募したところ通ったので、B3 の間はずっとそれをやっていました。その顛末は前に坩堝にも書きました（VSP の紹介・未踏体験記）。応募資料と、終わった後の成果報告書はGitHub 上で公開したので良かったら見てください。ちなみに VSP は Virtual Secure Platform の略なんですが、もともとは P は Processor で、後から「プロセッサ以外にも作るもの死ぬほどあるやんけ」といって Platform に変えたという経緯があります。

未踏期間中は、開発をしたいのに試験があったりして、ままならない思いをしていました。

それから、大学の演習で FPGA 上でプロセッサを作るというものがあったのですが、ハードウェアはつらかったのでソフトウェアの勝負に持ち込むべくコンパイラを書いて、当時流行っていた「1000 円でサイゼリヤで最大何 kcal の食事をできるか」という問題を自作プロセッサ上で解いたりしました。これもカオスの坩堝に書いたのですが、思いのほか好評で、初めてはてブにたくさんコメントがついたりしました。あとロボ太さんに言及されたり、ハードウェア実験の主担当の先生に言及されたりもしました。めちゃめちゃ嬉しかったです。

あと世界の真相を知ったりしました。

ちなみにハードウェア実験のソート速度を競うコンテストでは@VTb がぶっちぎりで優勝していました。シングルコアの性能としては歴代トップらしい。

それから応用情報技術者試験を受けて受かったりしていました。普段は自分の好きなことしか知識を得ないので、こういう資格の勉強をすると普段なら絶対に知り得ないような内容（PMBOK とか）を知ることができました。

ISUCON 9 に出て、ボーダーで予選を通過して本戦を欠席したりしていました。これも坩堝に書きました。

VSP以外で作ったものとしては、mattnさんのlongcatコマンドが流行っていたので、それに便乗して「流れてくる音楽で伸びたり縮んだりするlongcat」を作ったりしていましたが、全然ウケませんでした。技術的にはSixelを知れて面白い経験でした。

あと A+を取れた授業が多くて GPA 4.11 とかでイキってたら、何人か友達をなくしたりしました。みんなは気をつけてください。

B4

実は 2020 年のまとめ記事を坩堝に投稿したので、新しく書くことはあんまりありません。

4 月に行われるはずの研究室配属がコロナで 1 ヶ月ずれ込んだりしていたので、その間にカラオケ Web アプリ Damjiroを書いたりしました。

GPA ポケモンがトレンドに載って、4 万 hit を叩き出していました。

USENIX Security っていう学会に VSP の論文が通ったので、ツイートしていいねを稼いだりしていました。

論文は理論的な側面が強くて、@nindanoto にめっちゃ負担をかけたので感謝です。

VSP まわりでいうと、@nindanaoto がセキュリティ・キャンプ 2020 で講師をしていたので、それをサポートするチューターをやったりしていました。その過程で都合 3 回目となる TFHE ライブラリを書いたりしました（aqTFHE3）。@nindanaoto の講義スライドに合わせて書かれていて、世界で一番分かりやすいTFHEライブラリだと自負しています。

ISUCON 10 に出て、学生枠で予選を通過して本戦で fail したりしていました。これは梅さんが坩堝に書いてくれました（予選・本戦）。このときに aquery という Go 用の SQL スロークエリアナライザを開発したり、fgprof という既存のプロファイラのバグを取ったりしていました。

B4 の後半は F*というプログラム検証用プログラミング言語を使って、ブロックチェーン用のストレージライブラリに証明をつけていました。この F*というのが曲者で、だいぶ泣いていました。

泣いた内容をまとめて技術ブログの記事にしたりしました。これは未だにちまちま更新しています。

F#という言語を触って代読 Discord ボットを作ったりしていました。これも技術ブログの方に書きました。 F#は OCaml を.NET 用に Microsoft が改造した言語で、関数型っぽい形で.NET が触れます。個人的にはオフサイドルールが OCaml の文法とこれほどマッチするとは思いもよらなくて面白かったです。 .NET 側の事情に引っ張られて若干型推論が弱いのと、フォーマッタ（fantomas）の完成度が低いのが玉にキズです。

そのあとずっとやってみたかった Erlang/OTP と Elixir を触っていました。Erlang/OTP でalqo というアルゴを遊べる Web アプリを作ったり、 Discord の代読ボットを Elixir で書き直したりしていました。 Erlang と Elixir はかなり良い言語で、アクターモデルがよくハマる Web まわりではとても楽しくプログラミングすることができました。文法としては実は Elixir よりも Erlang のほうが好みなのですが、Elixir のほうが人気があるのでライブラリが充実していて、 Elixir でプログラミングするほうが楽そうな事情が悲しいところです。あと Dialyzer という型をつけるためのツールがあるのですが、あんまり強くないのも若干残念です。

さて今年度はコロナ禍で、大学に行ったのは年度中 5 日程度しかありませんでした。ほとんどすべてのものがリモートになったわけですが、これが意外と快適で、コロナが終わってもこのままであってほしいなぁと思うくらいでした。特に、ひどいときで 1 週間に 1 回なっていた偏頭痛が、今年度に入ってからピタッと止まったのは、リモートになったおかげで睡眠時間がちゃんと確保できたからだろうなぁと本気で思っています。

あと A+を取れた授業が多くて GPA 4.11 とかでイキってたら、何人か友達をなくしたりしました。さて今の私の友達は何人でしょう。

ちなみに、B1 のときに予言したように、彼女は 4 年間できませんでした。

感想とか

書き忘れていることもたくさんありそうですが、大きなところは大体書いたかなと思います。 4 年間あっという間だった気がするのですが、こうして並べてみると意外と色々おもしろいことができたなぁという感じです。今後もこういう生活を続けて行きたいのですが、世知辛い世の中で就活なるものをしないと餓死してしまうようなので、そうも言ってられないかなと思っています。

というわけであんまり締まらないですが終わりです。ツイートを貼りまくって終わってしまいましたが、ここまで読んで頂きありがとうございました。

1 月

未踏で VSP の開発をしていた。KVSP の基幹部分である準同型暗号ゲートの評価エンジン Iyokan を 1 月 13 日あたりから書き始める。当時並行で、ユーザーインタフェースの kvsp コマンドも作っていた。いまの KVSP のベースは、おおよそこのあたりで形作られていく。 @nindanaoto が TFHEpp を書いたのも正月三が日だったはず。

締切が近づくにつれ VSP チームに険悪なムードが漂い始めるが、全員で Factorio マルチプレイを n 時間やり、ギリギリのところで均衡を保っていた。

あと大学の試験勉強とかしてた気がする。覚えてない。

2 月

引き続き VSP を開発した。未踏の発表会が 2 月中旬にあって、この直前にバグが見つかって直したりした。発表会が終わった後も未踏の作業期間が続いていて、Iyokan とか kvsp の改善をやっていた。カーネル/VM 探検隊@関西 10 回目で発表したのもこのころ。

2 月末から 3 月頭にかけて大学で試験があったはず。このあとコロナ禍に突入していくため、試験日を最後に大学に来なくなる。

3 月

東京に VSP の紹介発表をしに行ったりしていた。多分これが最後の東京旅行。次に行けるのはいつになるのか。

2 月末から 3 月頭にかけて未踏の成果報告書を書いたりした。全文をGitHub で公開した。未踏期間は 3 月中旬で終わった。

3 月末に VSP チームで温泉旅行の予定だったが、大阪で外出自粛令的なやつが出たので中止。結局今まで行けていない。

3 月 29 日にカオスの坩堝で2020 年春季投稿大会をやった。

4 月

大学が、4 月の講義計画を 3 月末になって白紙に戻したため、めちゃめちゃに暇になった。暇に任せて採点機能付きカラオケ Web アプリ Damjiroを作ったりしていた。

なんだかんだあって研究室配属が第一希望に決まったりした。

5 月

研究室での活動がリモートで始まった。研究会やら輪読やらは全部 Zoom 経由になった。昨年と比べて、朝早く起きる必要がないのでめちゃめちゃに楽になった。昨年までは偏頭痛に悩まされていて、ひどいときには一週間に一回死んでいたが、今年はよく眠れたおかげか、ついに一度もならなかった。

院試で必要な TOEIC がコロナ禍で中止になったりした。最終的には、今年の院試では TOEIC の結果が不要になった。

4 月終わりから 5 月にかけて、VSP を論文にまとめるため動き始めた。動き始めたといってもメインで書いていたのは@nindanaoto で、私は追加で実験をやったり、@nindanaoto の無茶振り機能追加要求に対応したり、 @VTb をせっついて新しいプロセッサを書かせたり、それを KVSP に取り込んでもう一度実験をしたりしていた。未踏期間が終わるとコードを書いてもお金が出ないんだなぁということを認識したりした。

6 月〜7 月

論文を書き上げて USENIX Security に提出した。書くべき英語が全然分からなくて、先生にめちゃめちゃにお世話になるなどしていた。

あとは院試勉強というのをしていた。始めの方は気楽にやっていたが途中から余裕がなくなってきて大変だった。とくにコードを書く時間がなくなってきた。実際 GitHub の contributions のところを見ると、6 月から 7 月にかけてぽっかり空いている。 OS の勉強をすると OS を書きたくなってくるのでつらかった。

8 月

院試を受けるために大学に 2 日行った。実に半年ぶりの大学だった。寒かった京都は暑くなっていた。ちなみにネタバレすると、院試後に次に大学に行くのは 12 月末に一度だけなので、今年度は結局 3 日しか大学に行っていない。

研究室で、OCaml でなにか書かないといけないというタスクがあったので、定理検証器 Qlown を書いた。依存型ベースの、Coq の弱いバージョンみたいなものができた。一応n + m = m + n程度は証明できる。もともと Qiita の記事を参考に書き始めたのだが、雰囲気で拡張したら簡約が良くわからなくなってそのまま放置することになった。

9 月

ISUCON10 に出て、予選を学生枠で突破し、本選で fail（失格）した。どちらもチームリーダーの梅さんが坩堝で記事を書いてくれた（予選、本選）。今年は本当に何もできなくて、メンバーの他二人に終始助けられた。Web は難しい。

VSP 論文の rebuttal が 9 月頭くらいにあって、なんやかんやあって minor revision になって、諸々を修正して accept された。

あと卒業研究が本格的に始まって、F*というプログラム検証用の関数型プログラミング言語をつつきはじめた。

10 月

コロナの流行が若干落ち着いていたので、VSP チームでモツ鍋を食べに行った。その折に@nindanaoto から誕生日プレゼントで Let’s Split というキーボードを貰ったが、ファームウェアの焼付がまずいか何かで片手だけキーの位置が反転していた。直し方がよく分からず、そのまま倉庫に眠っている。

セキュリティキャンプに L トラックチューターとして参加した。講師は@nindanaoto で、チューターは私と@VTb で、TFHE を教えるという内容だった。今年のセキュリティキャンプはリモートな上に 10 月から 12 月まであるという長期戦で、本当にこれで大丈夫かと思っていたが、最終的には結構うまくいったんじゃないかと思う。

11 月〜12 月

F*に苦しめられていた。なかなか思い通りの証明が書けずに苦労している様子がわくわく鮟鱇ランドの#fstarハッシュタグで確認できる。最近ようやく理解してきた。

まとめ

良いお年を。

「クラウド」という言葉が市民権を獲得して久しくなりました。 一口に「クラウド」と言っても様々ですが、その多くは「他者に処理を移譲する仕組み」と 簡潔にまとめられます。例えば、GPUを使う機械学習のプログラムを書いたが手元にはGPUが無い。 そこでGPUが搭載されたクラウド上のマシンを 借りて代わりに実行してもらう、といったケースが分かりやすいでしょう。

（画像は全てクリックで拡大します）

このとき、処理を実行するにあたって必要なプログラムとデータは、 もちろんクラウドに送信する必要があります。しかし、もしこのプログラムやデータを秘匿したいと すればどうでしょうか。そうやすやすとクラウド上に置くことはできません。 「クラウド」というふわっとした言葉ですが、 その実体は地球上のどこかに設置されたコンピュータです。そのマシンの在り処を知っている クラウドの管理者であれば、そのマシンに直接接続して情報を抜き出すことが可能です。 あるいは、そのマシンを構成している機器自体に脆弱性があり、外部の人間がデータを盗聴することを 許してしまうかもしれません。 このように、自分の管理下にないマシンでは「ハードウェアが脆弱であることによる情報の漏洩」が 起こりえます。ハードウェアを信用している限り、この問題は常につきまといます。

この問題を解決するためには「ハードウェアを信用せずにプログラムを実行する」必要があります。 これはつまり「プログラムが実行される際にハードウェア中を流れる電気信号を 読み取ったとしても、実行されている内容が分かることはない」ということです。 このような動作を可能にする一つの手段は、ハードウェア中を流れる信号をすべて暗号化して しまうことです。しかしプログラム自体も電気信号ですから、これはすなわち 「プログラムを暗号化したまま実行し、暗号化された結果を取得する」ということを意味します。 しかし、「プログラムを暗号化したまま実行する」などということは可能なのでしょうか。

これを可能にするのが「準同型暗号」と呼ばれる特殊な暗号です。 準同型暗号を使用すると次の図のような演算が可能になります。すなわち、暗号化した値を〈足し算〉した上で復号化すると、 暗号化する前の値を直接足し算した結果と一致します。同様に〈掛け算〉も行うことができます。

ここで、暗号化した値同士の演算を〈足し算〉・〈掛け算〉と山括弧付きで表記しました。 実は、この〈足し算〉・〈掛け算〉の処理は暗号化していない数値の加算・乗算とは全く異なる操作で、 処理には大変時間がかかります。このことは後ほど詳述します。

さてこの準同型暗号がどのようにプログラムの実行と関係するのでしょうか。 すぐに思いつくことは「プログラム中の演算を準同型暗号の演算に変換すれば、 暗号化したままプログラムを実行できる」というものです。 すなわちプログラム中での数値の足し算を準同型暗号の〈足し算〉に、 掛け算を〈掛け算〉に変換すれば、準同型暗号上でそのままプログラムを実行できるように思えます。 しかしこの手法には重大な欠点があります。現在発見されている準同型暗号で行うことができる演算にはいくらか制限があり、特に「場合分け」をそのまま処理できるような準同型暗号はまだ見つかっていません。というのも場合分けは通常「値が1のときは足し算、2のときは掛け算……」といったふうに値に依存して何を行うか決める必要がありますが、暗号上でこれを行うことはとりもなおさず値を復号化することにつながってしまうからです。

この問題を解決するためには、準同型暗号についてもう少し知る必要があります。ここまで「準同型暗号」という言葉を使いまるで1つの暗号かのように扱ってきましたが、実は準同型暗号には様々な種類があり、扱うことができる演算も各々異なります。その中に論理演算を扱うことができる準同型暗号があります。論理演算というのはいわゆる電気回路を構成する演算でXORやANDといった種類があります。すなわち先程の〈足し算〉や〈掛け算〉のように〈XOR〉や〈AND〉を計算できる暗号というわけです。

さて、通常プログラム（をコンパイルして得た機械語）はプロセッサ（CPU）という大きな論理回路の上で実行されます。 大きい、とはいっても論理回路ですから、論理演算によって構成されることに変わりはありません。 そこでプロセッサ自体を準同型暗号上に構築し、その上でプログラムを実行することで「プログラムを暗号化したまま実行する」ことが可能になります。

上記の構成を概念的に表すと上図のようになります。まずこのシステム自体は通常のCPU上で動作しています（下から1段目）。そのCPU上で〈XOR〉や〈AND〉といった準同型暗号の計算を行います（2段目）。その計算によって、プロセッサの論理回路が準同型暗号上で構築されます（3段目）。このプロセッサは暗号化したプログラムを受け取り、その内容を暗号化したまま実行します（4段目）。

完璧に思える準同型暗号ですが、一つ大きな欠点があります。 それはとてつもなく処理が遅いということです。現在知られている最速の実装でも、 1つの論理演算を評価するのに約0.13ミリ秒（＝13万ナノ秒）かかります。 電気回路で使用する論理ゲートの出力は通常数ナノ秒で行われますから、 およそ10万倍遅いというわけです。

技術的な制約による速度低下も考慮し、 我々は目標とするプロセッサの動作周波数を60Hzとしました。60MHzでも60KHzでもありません。 今私がこの記事を書いているPCにはIntel Core i7-8700が搭載されており 動作周波数は4.6GHzとのことなので、およそ10億倍の差があることになります。 黎明期のコンピュータで1940年ごろに開発された ABC（アタナソフ&ベリー・コンピュータ） の基本動作周波数が60Hzとのことなので、いい勝負かもしれません。

しかし準同型暗号上で動くプロセッサの開発は他にほとんど例がなく、 まさに黎明期と言っていい状態です。我々のプロジェクトではこのアイデアの概念証明（PoC）を行うことを 主目的とし、速度に関しては今後の暗号学の発展に期待したいと考えています。

デモと成果報告会について

2019年度未踏事業における上記のような我々の取り組みは既にある程度成功しており、実際に動作するデモを GitHub上で公開しています（Linux環境等必須）。その利便性や速度の点において課題は山積していますが、残りの未踏期間（及びその後の活動）にて解決できればと考えています。

未踏事業における最終的な成果は、2020年2月に実施される「2019年度（第26回）未踏IT人材発掘・育成事業成果報告会」にて発表予定です。例年YouTubeでのライブ配信が行われるため、ぜひご視聴ください。

参考文献

• TFHE
• Cingulata
• brainfreeze

ISUCON9に参加したので、大会前と大会中と大会後に何やったかを書く。

開催前

@_nemohemと@fplwdが ISUCON9のメンバーを募集していたので「入れて入れて〜」と言って入れてもらう。まともなWebサービスの運営はほぼ経験が無いが、「知識を得ることが目的」とのことだったので、気軽に参加した。

気軽に参加したあと、本戦の開催日にはすでに予定があるので参加できないことがわかり、土下座するなどした。大変申し訳ありませんでした。

Golangを選択するということが予め決まったので“A Tour of Go”を流し読みするなどする。それから、前から気になっていた「みんなのGo言語」の第二版が出ていたので買ってベンチマークのところを読み、そこに書いてあった Profiling Go Programsを読んでpprofを知った。

あと開催の少し前に集まって練習する予定が、偏頭痛でドタキャンして土下座するなどした。その節は大変申し訳ありませんでした。二人のご厚意で、本番2日前にも集まることが出来たので顔合わせをしつつGolangの過去問を解いたりした。その時の感じから、@fplwdがインフラ、 @_nemohemと筆者がGolangアプリという担当に決定した。

開始直前

行きの電車の中で、複数台構成のためのNginxの設定を調べる。 upstream と proxy_pass を使ってよしなにすればいいらしい。ふーん。とりあえず知識だけ仕入れて現場に入る。

10:00 開始

開始。@_nemohemに鯖を立ててもらっている間にマニュアルを読む。ちんたら読みつつ /initialize のレスポンスに謎の Campaign キーが生えていることだけを把握する。このあたりで鯖が立ったので「負荷は自分で決めるらしいよー」「まじー？」という会話をしつつSSHする。 ls に色がついていなかったためキレつつ alias を設定するなどしていた。

今回は初めに動いている言語がGolangだったので、そのままベンチを回す。 2千数百点付いた気がする。過去のISUCONではGolang版は0点スタートというのも珍しくなかったので、わりと取り組みやすいのかなぁなどと考えながらとりあえずコードをgitに載せGitHubのプライベートレポジトリにつっこむ。ついでにpprofも仕込んでプロファイルをとる。 getNewCategoryItems が遅いっぽいのでコードを眺めるとN+1になっているっぽい。解消するためにSQLをゴニョゴニョし始める。

11:00 getNewCategoryItems のN+1を解消

とりあえずitemとuserとcategoryを INNER JOIN すればええやろとばかりにSQLを書き始めるが、 sqlx を知らなかったため、解読とコーディングに時間がかかった。ついでにcategoryは親カテゴリー名を取得するために再帰的なコードが書かれており、 SQLに落とせない。最終的にsqlxをsqlっぽく使う初心者丸出しコードで itemとuserのinner joinだけを書き上げ、投入してベンチを走らせるがSQLが間違っている。ぐだぐだのまま12時台へ。

12:00 N+1の解決と500エラー

結局1時間以上使ってなんとか動かしたが、謎の500エラーが /buy と /sell に出て思ったよりもスコアが伸びない。負荷が足りないのかと Campaign を 1 にセットするがやっぱり伸びない。ついでにToo many connectionsのエラーが出たので@fplwdに対応してもらうなどした。

あとから聞いた話によると、DBのロックのかけかたがまずくデッドロックが起こっていたらしい（？）。結局これには最後まで気づかなかった。

何度かベンチを走らせても伸びないので、諦めてご飯を食べに行く。店に入るほどの余裕はなかったのでローソンで冷やし中華を買って食べた。麺がゴムっぽかったが、お腹も減っていたのでまあまあ美味しかった。タレで味がついていれば大抵の物は食えるんだなぁ。みつを。

13:00 カテゴリをメモリに乗せる

getNewCategoryItems のN+1を解決するためにはcategoryをよしなにしなければいけない。メンバーがcategoryテーブルに変更が加わらない（初期データの呼出しのみ）ことを見つけてくれたので、DBを叩いてcategoryテーブルの中身をダンプし、「categoryのidを与えると必要な情報を出してくれる関数のGolangコード」を出力するスクリプトをRubyで書く。これを使ってようやくN+1を解決した。長かった……。

14:00 遅いbcryptと6000点

このあたりでbcryptがアホ遅いことに気づく。以前Railsのチュートリアルをやったときに「動作時間で情報がもれないように、ハッシュ化されたパスワードの比較はどんな場合でも一定時間で終わるようになっている（≒わざと遅くなっている）」と読んだことを思い出し、これを通常の等号比較で行えないか検討する。しかし「ユーザにしてほしくないことは行いにくくする」というライブラリ作成の原則が bcryptに一貫されていて、脆弱性を仕込むことはできないようになっていた。仕方がないので「この部分は仕方がないんじゃなーい？」などと言いつつ諦める。

ちなみにレギュレーション上は「平分のままDBに保存しないこと」のみが規定されていたため、例えばbcryptのcostを下げるなどすれば対応可能だったようだ。残念。

さてpprofを見ると getUseSimpleID が重いらしいので SELECT 時に取ってくるカラムの数を減らす。またcategoryを全部取ってくる SELECT が遅いらしいので、またまたDBをダンプして関数に変換したりなどした。ベンチをとると、このあたりで6000点を越えた。

わくわくしつつnginxのキャッシュやらgz圧縮などを設定すると 3000点に落ちたり5000点に浮上したりと安定しない。仕方がないのでキャッシュとgz圧縮はなくして、複数台構成にシフトすることで点数を稼ぐことにした。

15:00 複数台でバグる

ベンチがアクセスしてくるサーバ（フロントエンド）で静的ファイルを配信し、 Golangが動く必要がある場合はバックエンド1台目に投げ、さらにDBを動かす必要があればバックエンド2台目に投げる構成に決定する。さっそくNginxを設定するが、そもそもNginxで複数台構成を（練習を含め）経験した人間がチームに一人もいないことに気づく。Golang側のボトルネックがほとんど解消していると感じていたこともあり、朝に upstream を知った筆者が設定することになる。

フロントエンドとバックエンド1台目はわりとすぐに動いてくれたが、バックエンド2台目の設定で詰まる。バックエンド2台目で動いているリバースプロキシ用の NginxとMySQL間の通信がうまくいかない。3人で頭を突き合わせてあーでもないこーでもないと言っているうちに1時間経過する。

16:00 複数台で動く

MySQLはunix domain socketで接続を待ち受けるらしい。知らなかったよね。これに気づいてからは早かった。ベンチを回すと6000点か7000点くらい出た気がする。やったぜ。

top を見るとバックエンド1台目がCPUを使い切ってることが分かったので、フロントエンドにも処理を肩代わりしてもらうことにする。これは upstream に 127.0.0.1 を追加するだけではだめで、フロントエンドとバックエンド1台目のどちらかにアップロードされる画像ファイルに、これらの両方からアクセスできるようにする必要がある。 ISUCON7のfujiwara組が同様の問題を upload/01/ と upload/02/ に画像を振り分けた上で Nginxでスイッチすることで解消していたのでこれを真似る。fujiwara組の nginx.conf は公開されていなかったのだけど、Google検索し続けたらどうにかなった。

「残り30分でも動かなかったら単一構成に戻す」などと言っていたのが杞憂に終わってよかった。

17:00 ラストスパート

残り時間が1時間を切ったのでランキングが見えなくなった。このあたりでベンチを回して9000点台が出た。うれし〜〜。

初めの方に有効化してバグったキャッシュとかgz圧縮とかを復活させる？という話をしていたが、下手にいじって壊すのが怖い。結局ここで最適化は打ち止めにして、ログの出力やプロファイルのコードを消してベンチを回し続けることにした。なぜかベンチが二回に一回failするのでドキドキしながらベンチを回していた。ついでに再起動試験をし忘れていたことに気づいたので慌ててやった。

最終的に17:45に9670点が出て、ここで打ち切りにした。 17:50あたりからポータルサイトが不安定になっていたので、「ここで止めて正解やったなぁ」などと話しながら、夕飯の場所を決めた。

終了後

無事終了。公式が立てた感想戦のDiscordを眺めながら「デッドロックとか起こってたんかへー」「非同期APIはさっさと返してええんやなへー」「bcryptはやっぱり手を入れるべきやったんかへー」などと喋っていた。ついでにボーダー予想もしつつ「ボーダーは1万2千点くらいかなぁ」「いやもうちょっと高くて1万5千点くらいじゃないー？」などと喋っていた。

適当なところで切り上げてモダン焼きを食べに行った。美味しかった。

食べている途中で結果が発表された。残念ながら予選敗退だったが、ボーダーが意外と低くて 1万点くらいだったので「非同期APIに気づいてればなー」「デッドロックに気づいてればなー」「bcryptに手を入れてればなー」などとほざいていた。

今

ISUCON9 オンライン予選 全てのチームのスコア（参考値）が発表され、予選をボーダーで通過したチームのすぐ下に点差210点で自分のチームが付けていたことを知り泣いています。

感想、あるいは来年への備忘録

始まる前に思っていたよりもいいところにつけた（全参加者の上位5.1%）ので個人的には満足した。Webアプリについて実戦経験が無くても、意外と付け焼き刃でできることはいろいろあるのだなぁと実感した。

Golang側の改善がほとんどpprof一本槍だったので、もう少しいろいろなツールを利用すればデッドロックに気づけたのかなぁと思ったり思わなかったり。あとNginxの知識とかDBの知識とか、諸々のWeb周りの知識が欠けているというのも実感としてあるので、どうにかしていきたいですね（ふんわりとした問題意識）。

大変楽しかったので、できれば来年も出たいなぁと思いつつ。

お疲れ様でした。

自作CPU

学校の演習課題としてFPGA上でCPU（プロセッサ）を作成しました。具体的には、PowerMedusaボードを利用し、このボード上にあるFPGAをVerilogを用いてプロセッサとして動作させました。
5段パイプラインや簡易的な分岐予測（不成立）などが実装されています。

この演習では「SIMPLE」と呼ばれるアーキテクチャが予め与えられます。
SIMPLEアーキテクチャは16bit=1wordのワードマシンで、RISC的なISAを持っています¹。基本的にはこの仕様を満たすプロセッサを作成するのですが、必要に応じて自由に仕様を変更しても良いことになっています。私の班ではADDIやCMPIなどの即値演算命令を追加したほか、無条件分岐命令であるB命令のオペランドを8bit幅即値から11bit幅即値に変更するなどしました。

さらなる詳細を知りたい方は演習の説明ページを参照してください。また過去の同一演習について記載されたjoisinoさんのブログ記事も参考になるかと思います²（計算機科学実験及演習3ハードウェア（CPU製作）記）。

サイゼリヤ問題

「サイゼリヤに1000円を握りしめて食事に行ったとき、どの料理を食べれば最大カロリーを摂取できるか」という極めて実用的な問題です。以下では便宜上これを「サイゼリヤ問題」と呼ぶことにします。

単純な問題なだけに様々な解法が考えられ、量子アニーリング計算による解法・
SMTソルバーによる解法・整数計画法ソルバーによる解法・動的計画法による解法などがすでに見つかっています（関連記事も参照）。

この記事では、これらのうち特にShinyaKatoさんの動的計画法による解法を参考にして実装を行います。

実装

まず動的計画法を用いてC言語でこの問題を解きます。後々これを自作CPU上で動かすため、二次元配列などは使用せず、メモリを対象にする操作は全て1次元配列memに対して行うようにします。

さてShinyaKatoさんの実装ではDPテーブルを144×1001要素の（動的）配列として確保していますが、自作CPU上にはメモリが33Kワード程度しか無く、このテーブル全てを保存することは不可能です。そこでテーブルとして1001ワードのメモリ領域を2本確保し、これを交互に利用することで
DPを行います³。ただしこれだけの情報では「最大カロリー」及び「最大カロリーを摂取するために必要な金額」はわかりますが、「最大カロリーを摂取するために頼むべき料理」が分からず片手落ちです。そこでこのテーブルとは別に8192ワードのメモリ領域を2本用意し、
DPのテーブルを更新するのと同時に、どの料理を頼めばそのカロリーに達するかを保存しておきます。メモリ量の上限から7個以上の料理を保存することは不可能ですが、今回の問題では（既存の記事から）3つ程度保存すれば十分であることが分かっているので、これでよしとします。

また自作CPU上には十分な表示機構がないため、とりあえず計算結果はメモリ上の決められた番地に保存することにします。具体的にはアドレス0x0800に金額を、0x801にカロリーを、続くワードに頼むべき料理のIDを連続で格納します。

結果、およそ次のようなプログラムを書くことができます。

#include <assert.h>
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

typedef uint16_t Word;

Word mem[0x5000];

enum {
    SAIZERIYA_CALORIE_ADDR = 0x400,
    SAIZERIYA_PRICE_ADDR = 0x500,
    SAIZERIYA_SIZE = 115,
    SAIZERIYA_BUDGET = 1000,
    P_ADDR = 0x0800,
    Q_ADDR = 0x0C00,
    PATH_P_ADDR = 0x1000,
    PATH_Q_ADDR = 0x3000
};

int lte(Word lhs, Word rhs)
{
    return (int16_t)lhs <= (int16_t)rhs;
}

Word routine()
{
    Word src = P_ADDR, dst = Q_ADDR;
    Word path_src = PATH_P_ADDR, path_dst = PATH_Q_ADDR;

    mem[src + 0] = 0;
    for (int i = 1; i <= SAIZERIYA_BUDGET; i++) mem[src + i] = 0x8000;  // -INF
    for (int i = PATH_P_ADDR; i < PATH_P_ADDR + (0x0400 << 3); i += 8)
        mem[i] = 0;

    for (int i = 0; i < SAIZERIYA_SIZE; i++) {
        for (int j = 0; j <= SAIZERIYA_BUDGET; j++) {
            Word val = mem[src + j];
            Word price_addr = SAIZERIYA_PRICE_ADDR + i;
            Word price = mem[price_addr];
            Word addr = src + j - price;

            for (int k = 0; k < 8; k++)
                mem[path_dst + (j << 3) + k] = mem[path_src + (j << 3) + k];

            if (lte(src, addr)) {
                Word val1 = mem[addr] + mem[SAIZERIYA_CALORIE_ADDR + i];
                if (lte(val, val1)) {
                    val = val1;

                    Word addr = path_src + ((j - price) << 3);
                    for (int k = 0; k < 8; k++)
                        mem[path_dst + (j << 3) + k] = mem[addr + k];

                    Word size = mem[addr];
                    size++;
                    assert(size != 8);
                    mem[path_dst + (j << 3) + size] = i;
                    mem[path_dst + (j << 3)] = size;
                }
            }
            mem[dst + j] = val;
        }

        Word tmp = src;
        src = dst;
        dst = tmp;

        tmp = path_src;
        path_src = path_dst;
        path_dst = tmp;
    }

    Word best_price = 0, best_calorie = 0;
    for (int i = 0; i <= SAIZERIYA_BUDGET; i++) {
        Word calorie = mem[src + i];
        if (lte(best_calorie, calorie)) {
            best_calorie = calorie;
            best_price = i;
        }
    }
    Word best_path_addr = path_src + (best_price << 3);
    Word best_path_size = mem[best_path_addr];
    mem[P_ADDR] = best_price;
    mem[P_ADDR + 1] = best_calorie;
    for (int k = 0; k < 8; k++) {
        if (k >= best_path_size) break;
        mem[P_ADDR + (k + 2)] = mem[best_path_addr + k + 1];
    }

    return P_ADDR;
}

int main()
{
#include "saizeriya.inc"
    uint16_t src_index = routine();
    for (int i = 0; i < 0x4000; i++) {
        printf("%04X : %04" PRIX16 "\n", src_index + i, mem[src_index + i]);
    }
}

なお途中で#includeしているsaizeriya.incには、配列mem上に料理データを読み込むための
C言語コードが次のように記載されています。このデータは「サイゼリヤ1000円ガチャ」さんのGitHubレポジトリ（Saizeriya_1000yen）よりお借りし作成しました。

mem[SAIZERIYA_CALORIE_ADDR + 0] = 0;
mem[SAIZERIYA_CALORIE_ADDR + 1] = 130;
mem[SAIZERIYA_CALORIE_ADDR + 2] = 115;
mem[SAIZERIYA_CALORIE_ADDR + 3] = 134;
mem[SAIZERIYA_CALORIE_ADDR + 4] = 92;
// 中略
mem[SAIZERIYA_CALORIE_ADDR + 111] = 216;
mem[SAIZERIYA_CALORIE_ADDR + 112] = 166;
mem[SAIZERIYA_CALORIE_ADDR + 113] = 162;
mem[SAIZERIYA_CALORIE_ADDR + 114] = 164;

mem[SAIZERIYA_PRICE_ADDR + 0] = 0x7FFF; // INF
mem[SAIZERIYA_PRICE_ADDR + 1] = 299;
mem[SAIZERIYA_PRICE_ADDR + 2] = 349;
mem[SAIZERIYA_PRICE_ADDR + 3] = 299;
mem[SAIZERIYA_PRICE_ADDR + 4] = 299;
// 中略
mem[SAIZERIYA_PRICE_ADDR + 111] = 249;
mem[SAIZERIYA_PRICE_ADDR + 112] = 299;
mem[SAIZERIYA_PRICE_ADDR + 113] = 299;
mem[SAIZERIYA_PRICE_ADDR + 114] = 369;

次に、このC言語コードをSIMPLEアセンブリに変換する必要がありますが、この規模のコードでもハンドアセンブルは骨がおれます⁴。そこで簡易的なコンパイラを作成してアセンブリを生成しました。具体的には、まず上記のコードを次のような形に書き直します。

int SAIZERIYA_CALORIE_ADDR, SAIZERIYA_PRICE_ADDR, SAIZERIYA_SIZE,
    SAIZERIYA_BUDGET;
SAIZERIYA_CALORIE_ADDR = (4 << 8);  // 0x400
SAIZERIYA_PRICE_ADDR = (5 << 8);    // 0x500
SAIZERIYA_SIZE = 115;
SAIZERIYA_BUDGET = (125 << 3);  // 1000

int P_ADDR, Q_ADDR, PATH_P_ADDR, PATH_Q_ADDR;
P_ADDR = (8 << 8);          // 0x0800
Q_ADDR = (12 << 8);         // 0x0C00
PATH_P_ADDR = (0x10 << 8);  // 0x1000
PATH_Q_ADDR = (0x30 << 8);  // 0x3000

int src, dst, path_src, path_dst;
src = P_ADDR;
dst = Q_ADDR;
path_src = PATH_P_ADDR;
path_dst = PATH_Q_ADDR;

int MINF;
MINF = (8 << 12);  // 0x8000 == -INF

{
    // initialize memory
    int i, size;
    mem[src] = 0;
    for (i = 1; i <= SAIZERIYA_BUDGET; i = i + 1) mem[src + i] = MINF;
    size = PATH_P_ADDR + (4 << 11);
    for (i = PATH_P_ADDR; i < size; i = i + 8) mem[i] = 0;
}

{
    int i;
    for (i = 0; i < SAIZERIYA_SIZE; i = i + 1) {
        int j;
        for (j = 0; j <= SAIZERIYA_BUDGET; j = j + 1) {
            int val, price_addr, price, addr, dst_path_addr_base;
            val = mem[src + j];
            price_addr = SAIZERIYA_PRICE_ADDR + i;
            price = mem[price_addr];
            addr = src + j - price;
            dst_path_addr_base = path_dst + (j << 3);

            {
                int k, src_path_addr_base;
                src_path_addr_base = path_src + (j << 3);
                for (k = 0; k < 8; k = k + 1)
                    mem[dst_path_addr_base + k] = mem[src_path_addr_base + k];
            }

            if (src <= addr) {
                int val1;
                val1 = mem[addr] + mem[SAIZERIYA_CALORIE_ADDR + i];
                if (val <= val1) {
                    val = val1;

                    int addr, k;
                    addr = path_src + ((j - price) << 3);
                    for (k = 0; k < 8; k = k + 1)
                        mem[dst_path_addr_base + k] = mem[addr + k];

                    int size;
                    size = mem[addr] + 1;
                    mem[dst_path_addr_base + size] = i;
                    mem[dst_path_addr_base] = size;
                }
            }

            mem[dst + j] = val;
        }

        int tmp;
        tmp = src;
        src = dst;
        dst = tmp;

        tmp = path_src;
        path_src = path_dst;
        path_dst = tmp;
    }
}

{
    int i, best_price, best_calorie;
    best_price = 0;
    best_calorie = 0;
    for (i = 0; i <= SAIZERIYA_BUDGET; i = i + 1) {
        int calorie;
        calorie = mem[src + i];
        if (best_calorie <= calorie) {
            best_calorie = calorie;
            best_price = i;
        }
    }

    int best_path_addr, best_path_size;
    best_path_addr = path_src + (best_price << 3);
    best_path_size = mem[best_path_addr];
    mem[P_ADDR] = best_price;
    mem[P_ADDR + 1] = best_calorie;
    int k;
    for (k = 0; k < 8; k = k + 1) {
        if (k < best_path_size) {
            mem[P_ADDR + k + 2] = mem[best_path_addr + k + 1];
        }
    }
}

{
    // set the result to registers
    //__builtin_output(mem[P_ADDR]);
    int res0, res1, res2, res3, res4;
    res0 = mem[P_ADDR + 0];
    res1 = mem[P_ADDR + 1];
    res2 = mem[P_ADDR + 2];
    res3 = mem[P_ADDR + 3];
    res4 = mem[P_ADDR + 4];
    __builtin_load(R3, res0);
    __builtin_load(R4, res1);
    __builtin_load(R5, res2);
    __builtin_load(R6, res3);
    __builtin_load(R7, res4);
}

__builtin_halt();

およそ先程のコードと同じですが、コンパイラデザインを極力簡単にするため、一部冗長な書き方をしています⁵。また、このコードの末尾では__builtin_load()を連続して用いることで、得た結果をレジスタに読み込んでいます。これによりデバッグ用の7SEG
LEDに結果を表示することができます（後述します）。

さて、次にこれを受理してアセンブリを生成するためのコンパイラを作成します⁶。そのコンパイラにこの入力を与えて、以下のようなアセンブリを出力として得ることができます⁷。

    define SP R0
    LI SP, 0
    LI R1, 4
    SLL R1, 8
    ST R1, 0(SP)
    LI R1, 5
    SLL R1, 8
    ST R1, 1(SP)
    LI R1, 115
    ST R1, 2(SP)
## 中略
    LD R1, (R1)
    ST R1, 39(SP)
    LD R1, 4(SP)
    LI R2, 4
    ADD R1, R2
    LD R1, (R1)
    ST R1, 40(SP)
    LD R3, 36(SP)
    LD R4, 37(SP)
    LD R5, 38(SP)
    LD R6, 39(SP)
    LD R7, 40(SP)
    HLT

先程述べたコード末尾の__builtin_load()がLD命令として展開されていることがわかります。

最後にこの生成されたアセンブリコードをマクロアセンブラとアセンブラに通し、次のようなMIF
(Memory Initialization File)形式として出力させます。

0000 : 8000;
0001 : 8104;
0002 : C188;
0003 : 4800;
0004 : 8105;
-- 中略
0141 : D100;
0142 : 0900;
0143 : 4828;
0144 : 1824;
0145 : 2025;
0146 : 2826;
0147 : 3027;
0148 : 3828;
0149 : C0F0;

これを命令メモリに書き込んでFPGAを始動させると、プロセッサがサイゼリヤ問題を解決してくれます⁸。

結果

実際に実行すると、次のように表示されました。

上記画像にもあるように結果は次のようになりました。

• 最大カロリー　1940kcal
• 使用金額　992円
• 頼む料理　3品
  • ポテトのグリル　199円　366kcal
  • アーリオ・オーリオ(Wサイズ)　574円　1120kcal
  • ラージライス　219円　454kcal

イメージ画像

せっかく計算したので、実際にサイゼリヤ百万遍店で注文してみました。

「ポテトのグリル」のみ現行のメニューには記載されていなかったため頼めず「アーリオ・オーリオ(Wサイズ)」と「ラージライス」のみを注文しました。それでも計1486kcalで793円です。全部食べきって場所を移し、いまこの記事を書いています。とりあえず私から言えることは、二度と同じようなチャレンジをしたくありません。体を大切に^9,10。

感想など

本文中につけた脚注を見てください。

コードなど

サイゼリヤ問題のために作成したコードと、それを動かすためのコンパイラ・マクロアセンブラ・アセンブラ・エミュレータなどはここから入手することが出来ます。プロセッサのコードは演習が終わり次第どこかに上げたり上げなかったりするかも知れません。

関連記事

• サイゼリヤ1000円ガチャをつくってみた(Heroku + Flask + LINEbot) – Qiita
• 「サイゼリヤで1000円あれば最大何kcal摂れるのか」を量子アニーリング計算(Wildqat)で解いてみた。
  – Qiita
• 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をSMTソルバー(Z3)で解いてみた。
  – Qiita
• 「サイゼリヤで1000円あれば最大何kcal摂れるのか」を整数計画法ソルバー(PuLP)で解いてみた。
  – Qiita
• 「サイゼリヤで1000円あれば最大何kcal摂れるのか」を動的計画法で解いてみた
• 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をマルコフ連鎖モンテカルロで解いてみた。
• 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をExcel
  のソルバーでで解いてみた。
• 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をなでしこでDPで解いてみた。
• 【Excel】サイゼリヤ1000円で摂れるカロリーの最大値をVLOOKUP関数だけで求める方法
• 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をTeX言語で計算する
  ～TeX言語で動的計画法(DP)～
• 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をSQLで解いてみた。

私は今、さっき目撃した驚くべき現象をこの女性に伝えたいと思っている。といっても私はもうかなりの回数それを見てきたのだが、何度見てもそれは視界に入った途端に命の危険や、理解しがたいことに対する恐怖を感じさせるものだった。すぐに逃げ出したいという焦燥感に駆られたとしても、その現象に遭遇した時は逃げ出さず、そこに近づいて耳を澄まさなければならない。

昨日の雨でぬかるんでいる地面の部分を避けながら、彼女に近づいてこう言った。

「こんにちは。驚かせてしまってすみません。怪しいものではないのです。どうか話を聞いてもらえませんか。」

彼女は警戒しているようだった。ボーイフレンドがなかなか戻ってこなくて不安に思っているところへ、いきなり知らない人間に話しかけられたのだから当然ではある。もともと私は他人とコミュニケーションを取ることが苦手なので、彼女の警戒心に怯み挫けそうになったが、勇気を出して言った。

「あなたは私の話を馬鹿馬鹿しい戯言、あるいは狂人の妄想として聞き流そうとするかもしれませんが、私はあなたにそれを話す義務があるし、あなたはそれを聞く義務があるのです。先ほどあなたと一緒にいた男性、彼はあなたのボーイフレンドでしょう？そう、彼に関するお話です。」

ベンチから立ち上がり、歩き去ろうとしていた彼女は、私の最後の一言で振り向いた。顔の横に持っていきかけていたスマートフォンを下ろして、私に向き合った。

「私たちを見ていたんですか？あなたが彼に何かしたの？どうして彼は戻ってこないんですか？」

「順番にお答えしましょう。一つ目の質問の答えはイエスです。私はあなたたちを見ていました。なぜならばこの公園は私の散歩コースにあって、この公園で一休みするのが私の習慣であり、ここで遊んでいる子供たちを見てくつろぐのが私の日課だからです。今日は子供たちはいないようですが、日課を変えることはしません。したがって必然的にあなたたちを観察することになります。二つ目の質問の答えはもちろんノーです。私が彼に何かしたわけではありません。傍観していたという意味では間接的にそうかもしれませんが、しかし状況は私が介入できるようなものではなく、また未然に防ぐことができるような性質のものでもありませんでした。三つ目の質問の答えは少し長いお話になるので、ベンチに座っていただけませんか。」

「ここで聞いてもいいですよね？ベンチに座って聞かなければいけませんか？」

彼女はいつでも通報できるように握りしめたスマートフォンを、それとなく強調するような仕草をした。

そんなに私は怪しい風体をしているだろうか？いや、口調が原因で私を怪しいと思っているのかもしれない。こうして知らない人に話しかけるのは私の性質上苦手で、しかも話の内容が内容だけに、緊張して早口で喋ってしまった。安心させるために論理的に話そうとしたのもあだになり、冗長な表現によってかえって言い訳じみた印象を与えたのではないだろうか。

私はストーンヘンジの外周から５メートルほど北に位置する時計台をちらりと見た。私は時間が分かるものを持ち歩かない。雲が太陽にかかり、にわかに暗くなる。暗くなったせいで時計の文字盤がよく見えなかった。

「いえ、すみませんでした。そこで結構ですから、どうぞ話を聞いてください。」

「三つ目の質問の答えは？」

私の言葉を聞き終わるより早く彼女は言った。そうとう不安らしい。この調子だと、私の話を聞いた後、彼女は怒り出すに違いない。

「彼が戻ってこないのは、ブージャムに食べられてしまったからなのです。」

「は？ブージャム？食べられた？」

「そうです。ブージャムに食べられたのです。おそらくブージャムについては何もご存じないでしょうから、初めから説明します。」

「知ってますよ。ルイス・キャロルの詩に出てくる怪物でしょう。スナークの一種でしたっけ。架空の生き物に食べられただなんて冗談はやめてください。」

いまや彼女は敵意さえ私に向けているようだ。敵意を向けるべきなのは私ではなくブージャムの方なのに。彼女の誤解を解くべく、私は笑顔を浮かべジェスチャーを交えて話し始めた。

「よくご存じですね。そう、確かにブージャムはルイス・キャロルの『スナーク狩り』に登場する架空の生物です。しかし私が言ったブージャムは『スナーク狩り』に由来する現実の生物の名称です。私はその生物の名前を知らないので、仮にそう名付けているのです。」

彼女は私に対する不信感をさらに募らせているようだ。ジェスチャーはまずかったか。顔をしかめ露骨に嫌悪感を示す彼女に、私はなおも続けた。

「私はこの町で育ち、この広い公園でよく遊びました。小さいころから、この公園で不可解なことが起こるのを、というより不可解な生物をよく目にしたのです。」

私は、あの生物を初めて見たときの恐怖を思い出していた。忘れようのないあの気味の悪い見た目、そしてなによりあの大きさが私を恐れさせた。移動する音はぶつぶつ呟いているようにも聞こえ、後ろ姿は姿勢の悪い禿頭の酔っぱらいにも見える。

「どこを調べても分からなかったので、その気味の悪い生物を私はスナークと名付けました。『スナーク狩り』の不可解さとその生物の不気味さがよくマッチしていたためです。」

彼女はスマートフォンを操作していた。私の話を聞く気がないのだろうか、と憮然としていると、彼女は言った。

「写真を撮らせてくれます？」

「なぜです？」

「警察に連絡するときに必要になるかもしれないから。」

「お断りします。警察への出頭が必要ならば自分で出向きます。それより私の話を聞いていただけますか。」

彼女は私のことを変質者、良くて害のない狂人と思っているらしい。まあ、こういう反応が返ってくることは分かっていた。今回こそうまく説明できると思ったのだが。

「あなたが私の話を信じられないのは分かりますが、あれを目撃し真相を唯一知る私としては、これをあなたに話さないわけにはいかないのです。」

彼女はなおもスマートフォンを操作し続け、器用にもぬかるみを避けながら１，２歩あとずさり、面倒そうにこう言った。

「もっと手短に話してくれます？あなたの妄想に付き合っている時間はないんです。彼がどこへ行ったか聞いても無駄でしょうから、こう訊きますが、彼はどこでブージャムに食べられたんですか？」

「ストーンヘンジの向かいのあの御手洗いの中です。私は子供がブージャムに食べられないようここへ毎日……ちょっと待ってください。話は最後まで聞いてください。危険なんですよ。通常ブージャムは人間を食べた後スナークになり人間を襲わなくなりますが、彼を食べたブージャムは『まだ』と言っていました。そういうブージャムは危険なんです。まだ人間を欲している可能性がありますから。」

「はいはい分かりました。近づかないでください。警察を呼びますよ。」

彼女はスマートフォンを脅すように掲げて言った。彼女が後ずさり日が少し落ちたことで、彼女の影がストーンヘンジ外縁の北西の石にかかっている。

「妄想じゃありません。私は何度もブージャムが人間を食べるのを目撃しているんです。危険だからあなたに忠告しているんです。ストーンヘンジに近づかないでください。早く離れて。ほらもうそこに…」

私が言い終わる前にブージャムは彼女の後ろに迫っていた。いや、スナークと言うべきか。私の懸念とは裏腹に、その怪物は彼女を捕食しなかった。そして、やはり彼女はその怪物のことをボーイフレンドだと思い込んでいた。そのスナークは捕食したボーイフレンドの顔をしていたのだ。

「…」

「雨降りそうだし早く帰ろう。」

私を睨みながら、彼女はスナークにそう言った。

ブージャムの頭部は目や口のくぼみだけのあるノッペラボウであり、人間を食べるときにのみ顔の中心を収縮させて大きな穴を作り、背後からそっと近づいて人間を音もなくその穴に吸い込む。その直後、ブージャムは顔を元に戻すが、徐々に食べられた人間の顔がそこに浮かび上がってくるのだ。彼女がそのスナークをボーイフレンドと勘違いするのも無理はない。だが、私には分かるのだ。それがスナークであることが！

彼女はスナークとともに歩き去った。私はその後ろ姿を見送ることしかできなかった。追いかけてさらなる忠告をするか、諦めて無力感に苛まれながら家路につくか逡巡しているまさにその最中に、日が陰り雨が降り出したまさにその最中に、彼女は突然静かに消えうせた。

そう、そのスナークはブージャムだった。

読んでくれてありがとう．この小説の舞台はかつて僕が旧融合不定期に投稿した『ブラボー』の最後の場面の広場です． 主人公の気持ち悪さがこの小説のかなめ． 例によって，僕が実際に見た夢に着想を得て書きました．人を食べる生物が登場するのは同じですが，元々の夢は小説とは違って食人生物はペットでした．そこから飼っているのか飼われているのかという話に発展させようとしたのですが，うちで飼っている猫について妹とそういう会話をしたことを思い出したのでやめました．夢ではブージャムはもっと見るも悍ましい外見ですが，うちの猫は非常に可愛いので，関連付けるようなことはしたくなかったのです．ちなみにジャバウォックやバンダースナッチはスナークの固有名詞として出てくる予定でした．

僕は小説が書けません．最初に書こうと頭でイメージしているものが，書いているうちにどうしたことかどんどん方向が逸れていってしまう．セリフはぎこちないし，情景描写はできないし，ストーリーもおよそ筋と言うものがなく行き当たりばったりになってしまうことが多いのです．それでも，見た夢を小説にすれば何とか形にならないこともない．僕のメモ帳に書かれている，小説にできそうな夢は以下の４つでした．

• 内に広がり続ける虚無(穴)を抱える王国の城 (モデル：ユダヤ、ソロモン王)
• 思索によってしか他者を見つけられない哲学者(モデル：ウィトゲンシュタイン)
• 気持ち悪い食人生物のペット 相貌を持つ 飼われているのはどちらか
• あまりにも速い話 空を飛ぶ車 速度に命を懸けた男の話

このうち３つ目がこの小説になりました．たいして面白くないって？そうですね，本当に面白い夢は起きたとたんに忘れてしまうものですから．さてどうでしょう，だれか残りの３つを小説にしてくれませんか？人に小説を書く労力を押し付けるなんて厚かましい話ですし特に期待はしていませんが，筒井康隆の『天狗の落し文』みたいな感じでアイデアだけここに投げておきます．このアイデアたちを面白くするのはあなたです！

それはさておき，小説とは何なのでしょう？この小説を書いているとき，僕は小説という文学の一形態のもつあまりの自由さに，小説が一体何なのか分からなくなりました．僕がストーリーのある文章を書くとき，初めに全体の構造と大まかなあらすじ，一部の印象付けのためのセリフを用意しますが，書いているうちに必ず体裁が保てなくなって想定していたものと別物になってしまいます．たった3000字あまりのこんな短いものでさえ！頭の中にある映像をそのまま絵にすることはできないように（できる人はできるのでしょうが），頭の中の世界を文章に落とし込むことは到底不可能です．それは私の感覚では何というか，かなりねじ曲がった行為なのです．小説では何でも書けます．どんな方向にねじ曲がってもそれは小説だと言い張ることができます．だから僕も，この文章を小説だと主張できるのですが，実際にできあがったものは偶然の産物以外の何物でもありません．着想からして夢から拝借したものですし．あえて言うならこの小説はダダイズム的な何かなのかもしれませんね．

僕は小説が書けないので，かつてタクシャカと約束した『入れ子』の小説は誰かに託したい，いやリレー形式にしてそういう企画にするのも悪くないかもなと思っています．そう，それはまさに連歌のような．連歌的ジレンマ再び．

さあ始まりましたカオスの坩堝2019年春季投稿大会。

中略

私もとても楽しみです。

後略

2月前半はおおよそMioのことで頭がいっぱいだった。 MioはイントロクイズゲームができるWebアプリである。「イントロ」と銘打っているが、実は曲の途中からでもランダムに再生ができるので「中トロ」か「ラントロ」のほうが実態には合っている。出題者が居て、問題にする曲をアップロードし、回答者はそれを聞いてクイズの答えを送信する。出題者が各参加者からの解答の正誤を入力すると、自動的に正誤数がカウントされるようになっている。シンプルなゲームだ。行ったことがないけれど、きっとハッカソンとかだと1日で完成するんじゃないかな。わたしは3週間かかったけど。

Mioでは「サーバ」と呼ばれる中枢のコンピュータを用意して、出題者と回答者側――「クライアント」という ――がサーバと協調して動作することにより、イントロクイズを行っている。さっきの仕組みと合わせると、まず出題者が問題の曲をサーバに対してアップロードする。サーバはそれを受け取って、クライアント ――この場合は回答者だ――に送信する。回答者が答えを入力すると、これもまたサーバを経由して出題者に送信される。きょうび、他人と一緒に遊ぶタイプのゲームやツールは、おおよそこの仕組みで動いている。

この手のアプリケーションは作るのが難しい、と思う。大抵なんでも「協調して動く」というのが難しいのは、国際社会を見ていればよく分かる（ここは笑うところ）。プログラムだって例外ではない。途中で回答者が居なくなったらどうするか。出題者が居なくなったらどうするか。そもそもサーバが不具合で止まってしまったらどうするか。回答者が悪巧みをして、サーバに攻撃を仕掛けてくるかもしれない。そうなったときサーバはどのように動くのが良いのか――考え出せばキリがない。

ところで「プログラミングには数学が必要だ」というのは（プログラマの間では）よく話題にのぼるトピックだけれども、わたしはむしろ「プログラミングには論理が必要だ」のほうが正確に物事を捉えていると思う。実際（命令的な）プログラムは「まずこれをして、この場合には次にこれをして、そのあと これこれという条件になるまではこれをして、それが終わったら始めに戻る」みたいなものだから、これを正しく書くには論理の力がプログラマに無いとダメだというのはある意味当然だろう。Mioのようなプログラムをつらつら考えていると、まるでプログラミングが論理パズルのように思えてくる。「もしここで回答者の接続が切れていて、出題者も接続が切れていて、しかしゲームは続行中という状況がありえるだろうか？」

数学とか論理パズルとか、実はあまり好きではない。少なくとも熱狂的な支持者ではない。できれば避けて生活したい。大学というのは、そういう意味では不便な場所で、「単位」という名のもとに数学の授業を受けなければならない。無駄に負けず嫌いだから、試験があるなら勉強しなくては気がすまない。つくづく損な性分だと思うが、それでGPA芸人ができているから、損ばかりでもない。試験期間には呪詛の念を吐きながら数学の授業ノートに向かっている。こんなところからおおよそ予想がつくかもしれないが、勉強した数学の知識の8割くらいは試験が終わると頭から抜け落ちてしまう。「ラプラシアンってなんだっけ？」つまり学期の9割くらいは数学ができない。数学ができないということは、まぁ、論理の力もあんまり無いということである。

こう考えてくると、自分はどうにもプログラマには向いて無さそうだなと感じることになる。実際、数学や論理をフル回転させる競技プログラミングは、性に合わなくてやめてしまった。勘違いをしてプログラムにバグを埋め込んだり、論理的に考えれば絶対にできないことを可能だと思いこんだりしたことは数え切れない。そのたびに「賢い人はこんなことで悩まないんだろうな」などとぼんやり考える。どうしてこんな物を好きになったんだろう。

現代には集合知たるWWWが存在する。要するにGoogleである。最近はプログラミングを嗜む人が増えてきたこともあって、自分が悩んでいることを「ググれ」ば、解決法が見つかることも多くなった。それから、足掛け9年もプログラミングをやっていれば、頻出する論理――この場合アルゴリズムともいう―― は否が応でも覚えることになる。結局やっていることは「コピペプログラマ」みたいなものだ。ここまで「論理が大事！」と書いておいてひどい話だけれど、こうやってずっとプログラムを組んできたのだろうし、いまも組んでいるし、これからも組んでいくのだろう。

何かプログラミングで作品を作っていると、おおよそ一日中そのことを考えている。プログラミングが好きだからだ、というのも一つあるけれど、そこまで考えないと良いプログラムを書けないから、というのも大きい。これは割合に負担が大きくて、作品が一応の完成を見た次の日に偏頭痛で吐いたりするのはこの習慣のせいだろうと思わなくもない。ずっとこれを「まぁプログラム書くのが好きだし、ちかたないね」で済ませてきたのだが、学部生活も残り少なくなってきて、ふと就職のことが気になった。 Twitterでよく見る「適当に手を抜かないと自分が体を壊す」言説にピタリと一致している。職業プログラマには向いていないなと、こんなところでも感じる。

ところで、このあいだMioを（とりあえず）作り終わって、暇になった。こんなこともあろうかと、ブックマークの「あとで読む」フォルダを見ると “Learn You Some Erlang for Great Good!”が入っていたので、一昨日から読み始めた。英文だが、げらげら笑いながら楽しく読んでいる。やっぱり技術文書はこうじゃなきゃなぁ。自分もこういう文章を書きたいものだ、などと思いつつ特段オチのない鬱記事を終わる。

https://github.com/ushitora-anqou/mio

友だちに「イントロクイズ作って欲しいんだけど」と打診を受けて作りました。 Webアプリはこれまでほとんど作ったことが無かったので暗中模索でしたが、 3週間程度でとりあえず形になりました。

サーバにはNodeJS・Express・Sequelize・Dockerを使用し、クライアントにはReactを使いました。サーバ・クライアント間の通信にはSocket.IOを使用しました。レポジトリのREADMEの冒頭に「Deploy to Heroku」ボタンがついていて、これを押すと簡単にHerokuに展開できるようになっています。ぜひ使ってみてください。

動かし方などはREADMEにおおまかに書きましたが、もしMioを動かしたい奇特な方で「どうしても動かしたいけど動かないんだー」という方が居れば Twitterの@ushitora_anqouまでリプライをくださるか、あるいはここのコメント欄に書くか、いっそのことGitHubのIssueを投げて頂ければ、嬉しさのあまり涙を流しながらお答えいたします。

ところで

去年の夏からaqccや AQamlなど、どちらかといえば低レイヤーのコードを書いてきましたが、一転して高いレイヤーのコードを書きました。もちろんどちらが良い・悪いではないのですが、強く思ったのは：

ところでここ数日Webアプリもどきを作っているのですが、本当に冗談でも何でも無くて、Webアプリ作るよりも言語処理系書くほうが簡単だと思いました。

— 艮 鮟鱇／うしとら あんこう (@ushitora_anqou) 2019年2月12日

例えばNode.jsでの開発ひとつとっても、HTML・JS・CSSをそれなりに知った上で、Reactとかのフレームワークをある程度把握して、Web周りのセキュリティもおさえて、もちろんデータベースの知識も持って、諸々のツールを把握して、それでやっとスタートラインなわけでしょ。つらいどころの騒ぎじゃない。

— 艮 鮟鱇／うしとら あんこう (@ushitora_anqou) 2019年2月12日

フレームワーク的なやつは、うまく使えれば便利なんだろうけど、いかんせん自分が作ったものじゃないから、慣れるまでは「振り回される」部分が大きい気がする。まぁこれはWebアプリだけにとどまる話じゃないけど。

— 艮 鮟鱇／うしとら あんこう (@ushitora_anqou) 2019年2月12日

Webアプリは需要が大きい分開発も楽だろうと勝手にイメージしていました。実際フレームワークやツールなどが充実しているのは事実で「なんでもかんでも自分で作らないといけない」という状況に陥りにくいのですが、その一方で、そのフレームワークの使い方に振り回されたり、それらを組み合わせたときにどのように動かすべきかなどを理解するのは、そこそこ骨が折れました。それからCSSを用いたページのデザインも、私が今まで扱ってきたプログラミング言語と大きく異なっていて、結局よくわかりませんでした。このあたりはBootstrapを使えばある程度解消するのかもしれませんが、途中から導入するのも面倒だったので、そのままで押し切りました。

JavaScriptのスコープ

JavaScriptと言えば言語仕様が複雑怪奇なことで有名ですが[要出典]、少なくともES6に従って書く分にはそれほど不都合を感じませんでした。ただ、JavaScriptのスコープについてはすこし混乱しました：

JavaScriptのこの挙動でちょっと悩んだ。 pic.twitter.com/67V0eWZohd

— 艮 鮟鱇／うしとら あんこう (@ushitora_anqou) 2019年2月18日

CやC++、および類似の言語では、同様のコードを書くと正常に実行され、「ABC（改行）DEF」と表示されます。一方でJavaScriptではそもそも参照エラーとして実行が為されません。これはconstやletの変数宣言はブロックの先頭に「引き上げ」られる一方で、ブロックの先頭から実際の変数宣言までの間はこの変数が使用できないというECMAScriptの仕様によるものです。 MDNでは“Temporal dead zone”として参照されています¹。

音声の取り回し

音楽の再生・通信にはWeb Audio APIとlamejsを利用しました。送信クライアント側で音楽ファイルをデコードし、OfflineAudioContextを使用して始めの15秒を切り出してMP3にエンコードした後（trimMusic）、 Socket.IOを通してサーバ経由で各参加クライアントに送信し、各々のクライアントで再びデコードするという方式を取っています。ただしこれをそのまま行うと音楽によってはクリッピング（音割れ）が生じるため、送信側でDynamicsCompressorNodeを経由させています。これ1つでクリッピングがほとんど無くなるのは、かなり衝撃的でした。

ところで一応クライアント側ではバカでかいファイルを送信できないように制限を掛けているのですが、もちろん野良クライアントからサーバに向けて大きなデータを送信される可能性があります。これを防ぐためにはSocket.IOのServer に渡すオプションでmaxHttpBufferSizeを適当に設定してやると、勝手に通信を切ってくれます。 Mioではserver/config.jsで 500KBに制限しています。手元で実験した範囲では、普通送信される音楽ファイルは300KBを超えることは無いようです。さすがMP3といったところでしょうか。

HerokuとDockerと’Deploy to Heroku’ボタン

以前からHerokuでDockerコンテナを動かすことは可能でしたが、コンテナのビルド自体はローカルで行う必要がありました。ところが2018年の暮れにHeroku上でコンテナのビルドが可能になったため、 Deploy to Herokuボタンを押すだけでDockerを用いたデプロイができるようになりました。Mioではこれを活用しています。

詳細はHeroku公式ドキュメントに譲ることにして、 Mioでの仕組みを簡単に説明します。まずビルド及び実行に必要なDockerfileを作成します。Herokuで使用できるDockerのコマンドには制約があるので注意が必要です。次いでデプロイ時にDockerのビルドを走らせるためにheroku.ymlを作成します。heroku.ymlのsetupに、ソフトウェアが必要とするアドオンについて記載しておく必要があります。最後にapp.jsonを作成して、 README.mdに Deploy to Herokuボタンをくっつければ出来上がりです。 Mioの場合は特に指定すべきパラメタもないので意外と簡単でした。

押すとすぐにHerokuに遷移してデプロイの確認画面になります。ところで、私にとってこれがはじめての「’Deploy to Heroku’ボタンを押す」経験だったのですが：

Deploy to Herokuボタンって、押したら本当にHerokuにDeployされるんですね（真顔

— 艮 鮟鱇／うしとら あんこう (@ushitora_anqou) 2019年2月20日

名前の長さ

サーバ側ではhapijs/joiを用いてクライアントから送られてくるデータのバリデーションを行いました。その際、ユーザが設定する名前の長さを決めることが必要でした。私が知る限り最も長い日本の名前は「寿限無」なので：

// $ echo "寿限無寿限無五劫の擦り切れ海砂利水魚の水行末雲来末風来末食う寝る処に住む処藪ら柑子の藪柑子パイポパイポパイポのシューリンガンシューリンガンのグーリンダイグーリンダイのポンポコピーのポンポコナーの長久命の長助" | wc -m
// 104
// # Therefore the length of 128 is enough :)
schema.name = Joi.string().max(128)

としておきました。

いまのおきもち

注：以下ポエムです。

自分が「コンテンツ主義」だと言われて少し動揺しました。確かにaqccとかAQamlとかMioを作って、それを中心に記事を書いたり資料を作成したりしているので、そう見えるのかも知れません。もう少しアウトプットの量を増やせばいいのかもしれませんが、中身の薄いものを執筆したところで意味がなく、面白くないものを書いてもやっぱり意味がありません。そういう意味で、なにかモノを作ってそれについて書くというのは、自分の経験に基づいた文章を作成できるので、中身が薄くなりにくいのかもしれません。この記事が薄くないのかと言われると少し言葉に困りますが。

話は変わりますが、むかし家に『手が脳を鍛える 作って遊べ!』（かざま りんぺい、誠文堂新光社、2004）という本があって、よく眺めていました²。この本の中に印象深い文言があって、正確なところをちゃんと覚えていませんが「明日は何を作ろうか　と思いを馳せていると、人生退屈することはない」みたいなことが書いてありました³。当時は「そんな簡単に新しい工作が思いつくものだろうか」と子供心に思ったのですけれど、 Mioを作っている最中に、今まさに自分がそういう状況だと気づきました。対象は工作ではなくてプログラミングですが、「明日は何を作ろうか」「ここをこうすればもっと上手く書けるんじゃないだろうか」「こういう機能を足そう」等々、なにか作品を作っているときにはずっと考えています。

さいごに

Webアプリ初心者が作ったので、Mioにはおそらく脆弱性とか死ぬほどたくさんあると思います。脆弱性でなくても「普通こんな書き方はしない！」とか「ここがおかしい！」など、IssueやPull request大歓迎です。ぜひお願いします。そこまで詳しく見る余裕が無い方も、せっかくここまで読んでいただいたので GitHub右上のStarボタンをポチッと押して頂けると私が喜びます。もう一度レポジトリを貼っておきます。

https://github.com/ushitora-anqou/mio

以上艮鮟鱇でした。ここまで読んでいただきありがとうございました。

はりぼて自作OCamlコンパイラを書いてセルフホストを達成しました²。コミットログによると、11月から開発を始めて³およそ2ヶ月くらいかかったようです。レポジトリはこちら⁴：

https://github.com/ushitora-anqou/aqaml

文字列・リスト・タプル・レコード・バリアント・参照などの基本的なデータ構造⁵と、 if・for・パターンマッチ・let・相互再帰関数・クロージャなどの基本的な制御構造⁶が実装されています。

セルフホストに必要な機能のみを実装したので、もちろんOCamlの全てを実装したわけではありません。例えばGC⁷・カリー化⁸・クラスなどのOCamlの重要な機能が無い他、型推論⁹もありません。 GCが無いのでセルフコンパイルに数百MBのメモリを要しますが、まぁそれはそれです。

OCamlってなに

一言では説明できないのでググってください。

きっかけ

これをやっとけば、2回生後期のプログラミング言語、3回生前期のプログラミング言語処理系と実験3が楽になること間違いなしだ! https://t.co/gpvCEmiwYj

— Atsushi Igarashi (@50storms) 2018年8月23日

英語の勉強にもなるやから、うちの二回生と三回生はやったらいいんじゃないかなと思う。 https://t.co/Xw2AFUJy97

— Kohei Suenaga (@ksuenaga) 2018年8月23日

うちの学部の名物教授・准教授がおすすめしていた MOOCのOCaml講座を受講し始めたのがきっかけ。それまでOCamlはSATySFiの実装言語という認識しかありませんでした。言うまでもなく大学生は単位の奴隷¹⁰なので、 0.01でもGPAを上げるためなら寸暇を惜しみません¹¹。

始めてみると、今まで私が触れてきた言語とは異なるパラダイム・文法を持っていて、その仕組みが気になりました。ということで、コースを半分ほど終えたところで勝手にコースアウトしてOCamlコンパイラをOCamlで書き始めました。これが楽しくなってどんどん書いているうちに、いつのまにかOCaml学習コースは未履修のまま期日を迎えていました。残念。

実装

AQamlを作成するにあたって次のような方針をとりました¹²：

• 必要になるまで作らない。
• インクリメンタルに作る。
• 入力は正しいと仮定する。
• テストでバグ混入を防ぐ。
• パーサは全て自前で書く。
• スタックマシンでの実装。
• 出力の最適化は行わない。

これらの方針に基づいて作ると、ソースコード中に大量のTODOが入ったり、出力アセンブリの効率が悪かったり、拡張性が無かったり、OCamlの基本的で重要な機能が無かったりすることになりますが、セルフホストという大きな目標の前では些細な問題です¹³。とにかく、簡単にセルフホストすることを目標にして、できるだけ最短経路を通るようにしました。もちろんはじめて行うことですし、aqcc¹⁴のときと異なり相談できる相手も居ないため、「自分が最短経路だと思う方向」に進んでいくわけですが¹⁵、意外とどうにかなります。

aqccのときと同様に、最初は「入力として整数値を受け取って、その整数値を戻り値とするようなアセンブリを出力するコンパイラ」から始めました。その後四則演算を作ったりなんだかんだしていると、壁にぶつかりました。

クロージャはつらいよ

OCamlなどの言語では関数の中で関数を定義することができます。この場合、外側で定義された変数を内側の関数で使うことができるため、変数の生存期間をよしなに判断してやる必要があります。 OCamlの場合、内側で定義された関数と、その部分で使用されているけれども外部で定義されている変数をひっくるめて「クロージャ」というものを作ります。こうすることによって関数そのものを引数として別の関数にわたしたり、あるいは関数そのものを関数の戻り値とすることができたりします¹⁶。

さてOCamlコンパイラを書くからには、このクロージャを実装しなければなりません。面倒そうに見えますが、アイデアは単純です。すなわち、外部で定義された変数を関数本体と一緒にひっくるめてクロージャを作成しておき、そのクロージャを呼び出す際には、そのひっくるめておいたクロージャを紐解いて、外部で定義された変数の情報も一緒に関数にわたしてやればよいのです。基本的にはこれで構わないのです――基本的には。

ところで世の中には再帰関数と言って、関数の中で自分自身を呼び出すような関数が存在します。こいつがクロージャになった場合を考えてみましょう。まずこの関数を外から呼び出すときには、先述のような手順で外部定義の変数情報が与えて呼び出します。次にこの関数を再帰呼び出しする際には、外部から与えられた変数情報をもとに予め自分自身のクロージャを作成しておき、これを呼び出すことになります。面倒そうですね。

ところで世の中には相互再帰関数と言って、複数の関数がぐるぐると再帰的に呼び合う関数が存在します¹⁷。こいつがクロージャになる場合、この関数が外から呼ばれた時に与えられた外部定義の変数情報をもとに、関連する全ての相互再帰関数のクロージャを作成しておき、これを呼び出すことになります。ますます面倒そうですね。

ところでOCamlでは先述のように関数を返す関数を作成することがクロージャの存在により可能ですから、関数を返す関数の戻り値にさらに引数を与えることができます。OCamlにおいて関数適用は左結合ですからこの括弧は省略できます。何を言っているのかといえばつまり

f a b c d e

というような、関数fに引数a,b,c,d,eを与えるような関数呼び出しは、もちろん関数fは5引数関数であるかもしれませんが、ひょっとするとfは3引数関数を返すような2引数関数である（すなわち「(f a b) c d e」）かもしれませんし、あるいは1引数関数を返すような2引数関数を返すような2引数関数（すなわち「((f a b) c d) e」）かもしれないのです。そこでクロージャを呼び出す際には、それぞれに応じた呼び出しを行う必要があります。恐ろしく面倒そうですね。

ところで、そもそも「関数fをクロージャとして扱う必要がある」すなわち「関数fは外部で定義された変数を内部で使用している」ことを、どのように知ることができるのでしょうか。対象の関数が再帰関数である場合、「関数が外部で定義された変数を使用している」という情報を、再帰呼び出しをする際に使用します。従って関数内部を解析する際にはこの情報が必要です。しかしその情報は関数を解析するまで分かりません。まるで鶏と卵です¹⁸。 AQamlでは、最初に関数を解析する際にはひとまず「その関数は外部で定義された変数を内部で使用していない」と仮定して解析を行います。もし途中で外部で定義された変数を使用している箇所があれば、一番最初に戻り、今度は「その関数は外部で定義された変数を内部で使用している」として解析します¹⁹。なんとも面倒ですね。

一事が万事この調子で、クロージャを正しく動かすのにはかなり手間取りました。時間があれば、また何かの機会にまとめたいと思います²⁰。

第二世代バグが起こらない

さてaqccを作成したときには「第二世代バグ」というものを踏み抜き、このバグを潰すのに心底苦労しました²¹。すなわち「gccでコンパイルしたaqcc」にはバグが見つからないけれども、「gccでコンパイルしたaqccでコンパイルしたaqcc」がなぜかバグるというものです。

AQamlでもこのバグ取りに時間を費やすだろうと思っていたのですが、意外とスムーズに動いたので驚きました。理由はよく分かりませんが、OCamlの強い型推論機構のおかげだったりするのかもしれません²²。

今後の展望

他にもいろいろと書きたいことがあった気がするのですが、思い出せないのでとりあえずここまで。また思い出したら個別に記事にしたいと思います²³。

AQamlの今後の方向としては次のような機能を追加していきたいなと思っています：

• カリー化
• 完全なモジュール
• レジスタ割り当て
• GC
• 型推論

――思ってはいるのですが、そろそろ言語処理系に飽きてきた感じがないでもないので、もしかしたら全く別のことに手を出すかもしれません。あと最近肩こりと偏頭痛がひどくて²⁴、パソコンばっかり触っている生活を見直す時期に来ているのかなと思ったりしています。

ここまで読んでいただきありがとうございました。

できる！ OCamlコンパイラ作成資料

AQamlを作成した際に参考にした資料一覧です。OCamlコンパイラを作りたい方におすすめです。

• ocaml/ocaml: The core OCaml system: compilers, runtime system, base libraries
• The OCaml system release 4.07
  • 特にChapter 7 The OCaml language
• 速攻MinCamlコンパイラ概説
• Real World OCaml
  • 特にChapter 20. Memory Representation of Values
• Native code notes · ocamllabs/ocaml-multicore Wiki
• Règles de grammaires²⁵