Amazonでよさげなキットをポチった

空けてびっくり組み方を書いてなかったのでちょろちょろ調べながら組み立て

組上がったのでSDカードにOSをインストールする．

https://www.raspberrypi.org/downloads/

ここからラズパイ用のOSインストーラーを拾ってきてよしなにOSを焼くだけ

今回はせっかくなのでUbuntu serverを選択

ケーブルもろもろを繋いで起動

見切れて調節がいりそうな雰囲気なのでとりあえずデスクトップ環境を導入する

$ sudo apt-get install xubuntu-desktop

処理はそこそこ時間がかかったがほっとくといい感じに入ってる

とりあえずログインして日本語化しようとすると

なぜか日本語に設定できなかったので調節

$ sudo apt install language-pack-ja-base language-pack-ja ibus-mozc
$ sudo localectl set-locale LANG=ja_JP.UTF-8 LANGUAGE="ja_JP:ja"

再起動すると日本語化できた

そしてなぜかibusが起動時に実行されるようになっていなかったので設定を変えておくといい感じ

見切れてる問題は調べると/boot/config.txtを弄るといいぞみたいなことが書いてあったが，そんなものはなかったので，config.txtを探すと/boot/firmware/config.txtを発見

中身にこのファイルを弄らず，同じディレクトリにあるusercfg.txtを調節しろって書いてあったので

usercfg.txtに

hdmi_group=1
hdmi_mode=34
hdmi_driver=2

としておくと

いい感じの表示に変わった

(hdmi_groupとhdmi_modeは各自のディスプレイにあわせてくださいな)

https://www.raspberrypi.org/forums/viewtopic.php?f=5&t=5851

とりあえず今回はここで力尽きたのでここまで

なぜか音が出力されないのでそのうち対処しようかなのお気持ち

ちょっと手間がかかってもいい人は、YouTubeのカラオケ風動画を持ってきて、Damjiroの画面の下半分でMIDIファイルと組み合わせると、カラオケ風動画を見ながら歌えます。MIDIファイルを直接再生するよりもこっちのほうが音が（大抵）いいです。詳しいやりかたはGitHubのREADMEに書いてあります。

実装はJavaScriptでReactやらReduxやらMaterial UIやらを使っています。遊んでると不満点がたくさん出てくると思うので、そういうときは修正のコードを書いてGitHubからPull Requestを送ってもらえると助かります。コメントは日本語でも英語でもいいです。家で暇しててコードが書きたいという奇特な人はTODOリストを見てもらえると良いかもしれません。

以上です。お相手は、一日中PCの前に座っている生活に慣れてしまっていて、それほど生活スタイルが変わっていない鮟鱇でした。

「クラウド」という言葉が市民権を獲得して久しくなりました。 一口に「クラウド」と言っても様々ですが、その多くは「他者に処理を移譲する仕組み」と 簡潔にまとめられます。例えば、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で解いてみた。

想定環境

$ uname -srvmo
Linux 5.0.0-arch1-1-ARCH #1 SMP PREEMPT Mon Mar 4 14:11:43 UTC 2019 x86_64 GNU/Linux

$ gpg --version
gpg (GnuPG) 2.2.13
libgcrypt 1.8.4
Copyright (C) 2019 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <https://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Home: /home/anqou/.gnupg
Supported algorithms:
Pubkey: RSA, ELG, DSA, ECDH, ECDSA, EDDSA
Cipher: IDEA, 3DES, CAST5, BLOWFISH, AES, AES192, AES256, TWOFISH,
        CAMELLIA128, CAMELLIA192, CAMELLIA256
Hash: SHA1, RIPEMD160, SHA256, SHA384, SHA512, SHA224
Compression: Uncompressed, ZIP, ZLIB, BZIP2

master keyを作る

$ gpg --full-gen-keys

2048bitのRSA暗号で十分らしい[gnupg_faq-no_default_of_rsa4096]。 master keyの有効期限は無期限でいいらしい[hatsusato]。 gpg --gen-keys とすると無期限の設定ができない。作成中パスワードの入力を求められる画面でエントロピーがどうたらと書いてあるが、現環境では特に操作は必要なかった。 [joemphilips]には失効証明書を手動で作成する方法が書いてあるが、現環境では失効証明書は ~/.gnupg/openpgp-revocs.d/ 以下に保存されるので手動で作る必要はない。

実は暗号化用のsubkeyがここで勝手に作られるのだが、これには有効期限がついていない。仕方がないのでこれは後で削除して、別でsubkeyを作り直す。

以降 KEYID と書くとき、ここで生成したmaster keyや後で作成するsubkeyなどのkeyidを指定することを意味する。ハッシュ値（fingerprint）をそのまま書いても良いが、名前やメールの一部でも問題ない（場合がある）。 GPGはそのあたりに「寛容」らしい[archwiki-gpg]。

公開鍵を一覧する

$ gpg --list-keys

ここで表示されるハッシュはfingerprint。

秘密鍵を一覧する

$ gpg --list-secret-keys

ここで表示されるハッシュはfingerprint。

subkeyを作る

暗号化・署名の片方のみができるsubkeyを作成する場合

$ gpg --edit-key KEYID
gpg> addkey
### RSA (暗号化のみ) を選択する。
### 2048bitを選択する。
### 鍵の有効期間として2yを選択する。
### パスワードを打ち込む。
### 諸々出力されてsubkeyができる。

gpg> save

その他のsubkeyを作成する場合

$ gpg --edit-key --expert KEYID
### 持たせたい機能を選択する。
### 以下同じ。

認証機能（Authenticate）はSSH鍵として使用する場合に必要らしい[archwiki-gpg]。

subkeyには有効期間を定めておく。期限が近づいたら更新しなければならない。期限が切れたあとでも更新できるらしい[riseup_bestpractices_set-calendar]。勢い余ってsubkeyを消してしまうと、これで暗号化したファイルを復号化できなくなるらしい[archwiki-gpg]。どうせ忘れるのでスケジュールに追加しておくと良いらしい[riseup-bestpractices-set_calendar]。

subkeyを削除する

$ gpg --edit-key KEYID
gpg> key 1  ### 何番目のキーを削除するのか指定する。ただし一番上のmaster keyは0番目と見なす。
### 削除したいキーに*印が付く。
### ちなみにすでに付いていた場合は*印が消える。すなわち非選択になる。

gpg> delkey
### 選択されていたキーが消えたリストが出る。

gpg> save

key KEYID とはできないので注意[stackexchange-how_to_delete_subkey]。

master keyを取り除く

$ cp -r ~/.gnupg /where/you/wanna/save/keys ### バックアップを取る。
$ gpg --with-keygrip --list-key anqou ### master keyのkeygripを表示する。以下KEYGRIP。
$ rm ~/.gnupg/private-keys-v1.d/KEYGRIP.key ### master keyを削除。
$ gpg --with-keygrip --list-secret-key anqou   ### うまく消えていれば当該のmaster keyの部分に`sec#`と表示される。
$ rm ~/.gnupg/openpgp-revocs.d/KEYID.rev ### ついでに失効証明書も消しておく。

このやり方はGPG2.1以降らしい[joemphilips]。 [hatsusato]でもこのやり方が紹介されている。失効証明書を削除しているサイトは見つからないが[archwiki-gpg]によれば「無効化証明書にアクセスできれば誰でも鍵を無効化して、利用できなくすることができてしまいます」とあるので、バックアップがあるなら消しておいたほうがよさそう[要出典]。

~/.gnupg 以外の場所にあるmaster keyを使用する

$ GNUPGHOME=/where/master/key/exists gpg ### 以下省略

要するに GNUPGHOME を指定すればよい。

fingerprintを表示する

gpg --fingerprint --fingerprint

オプションを2つ重ねることでsubkeyについてもfingerprintを表示する。

subkeyを失効させる

gpg --edit-key KEYID
gpg> key 失効させたいsubkeyの番号（1-origin）
gpg> revkey
gpg> save

動作未確認。重要なことはsubkeyには失効証明書などないということ。失効証明書はmaster keyのみに存在する。ただしsubkeyを失効させるときにはmaster keyが必要（多分）。

失効周りはテストしてないので詳細不明。一生使いたくない。

GPG鍵を他のマシンに移す

$ gpg --export KEYID > public.key
$ gpg --export-secret-key KEYID > private.key
### ここで他のマシンにpublic.keyとprivate.keyを移す
$ gpg --import public.key
$ gpg --import private.key
$ gpg --edit-key KEYID trust quit
### 「究極的に」信用する

[stackexchange-import_secret]より。最後のコマンドで鍵の状態を「不明」から「究極」にする。

gpg-agentにssh-agentの代わりをやらせる

.zshrc （乃至それに類するもの） に以下を追加。

export GPG_TTY=$(tty)
gpg-connect-agent updatestartuptty /bye >/dev/null
unset SSH_AGENT_PID
if [ "${gnupg_SSH_AUTH_SOCK_by:-0}" -ne $ ]; then
  export SSH_AUTH_SOCK="$(gpgconf --list-dirs agent-ssh-socket)"
fi

[archwiki-gpg]より。 ~/.gnupg/gpg-agent.conf を編集する必要は （これだけをやるためには）特に必要ない。

gpg-agent.conf のオプションである enable-ssh-support は [man-gpg_agent]によると SSH_AUTH_SOCK 環境変数を設定するだけのようなので、このように手動で指定する場合は、おそらく必要ない。 また write-env-file は少なくとも2.2.13では意味を為さないオプションになっている。

これによって ssh-add を使用できるようになる。GPG鍵もSSH鍵として使用できる（後述）。鍵を確認する場合は ssh-add -l とすればよい。 ssh-agent とは異なり、一度追加してしまえば再度追加する必要はない。実際にSSH鍵を使用するときにパスワード入力を求められるのみである。

gpg-agentにSSH鍵として使用するGPG鍵を伝える

$ gpg --list-keys --with-keygrip ### 使用したいGPG鍵のkeygripを確認。以下KEYGRIP。
$ echo KEYGRIP >> ~/.gnupg/sshcontrol

~/.gnupg/sshcontrol にkeygripを書き込まなければGPG鍵をSSH鍵として使用することはできないらしい[qiita-macos_gnupg_ssh]。

GPG鍵からSSH公開鍵を作成する

$ gpg --export-ssh-key KEYID! ### GPGを直接使用する場合

末尾の ! に注意。これを指定しない場合、指定したKEYIDのGPG鍵の内、認証機能を持つ最も最近に作成したsubkeyのSSH公開鍵を出力する[man-gpg]。すなわち認証機能を持つ特定のsubkeyのSSH公開鍵を作成したい場合は、まずそのsubkeyのfingerprintを取得した後、それをKEYIDとして指定し、最後にエクスクラメーションマークをつける必要がある。 subkeyのfingerprintは --fingerprint を二回重ねることで出力できるが、この表示では4桁ごとにスペースが入ってしまうため以下のようにして取り除く必要がある。

### subkeyの一部にXXXXを含むとする
$ gpg --fingerprint --fingerprint | grep XXXX | sed 's/ //g'
### 当該subkeyのfingerprintがスペース無しで出力される

なお gpg-agent にGPG鍵をSSH鍵として登録した後ならば ssh-add を使用しても確認可能：

$ ssh-add -L

ここで作成したSSH公開鍵を適当なサーバの ~/.ssh/authorized_keys に追加すればGPG鍵を用いてSSH認証を行うことができる。

ここで作成したSSH公開鍵はあくまでsubkeyに紐づくものであることに注意。 master keyとsubkeyを使い分けるメリットとして、subkeyが流失した際にsubkeyを失効させることで信頼を担保するというものがあるが、SSH認証では接続相手のSSH秘密鍵が失効しているかなどを検査しないため、失効手続きを行った後でも、流失したsubkeyでSSH認証が可能のはずである（未確認）。

gpg-agentをリロードする

$ gpg-connect-agent reloadagent /bye

[archwiki-gpg]より。

gpg-agentからSSH鍵を削除する

$ vim ~/.gnupg/sshcontrol ### 適当なエディタでsshcontrolを開く
### 削除したいSSH鍵のkeygripを削除する。あるいは行頭に!を追加する。

GPG鍵をSSH鍵として使用する場合のみならず、 ssh-add で追加したSSH鍵もこの方法で保存される。 ssh-add -d は Identity removed の表示が出るにも関わらず、 sshcontrol からは削除されないため、効果がないようである[stackexchange-gpg_delete_ssh_key]。

gpg-agentへのパスワード入力方式を変更する（pinentry）

$ vim ~/.gnupg/gpg-agent.conf ### 適当なエディタでgpg-agent.confを開く
# PIN entry program
# pinentry-program /usr/bin/pinentry-curses
# pinentry-program /usr/bin/pinentry-qt
# pinentry-program /usr/bin/pinentry-kwallet
pinentry-program /usr/bin/pinentry-gtk-2

[archwiki-gpg]より。

GitにGPG鍵を追加する

$ git config --global user.signingkey KEYID

~/.gitconfig の [user] に signingkey の項が追加される。

Gitのcommit時に署名する

$ git commit -S

[git-gpg]より。常に署名したい場合は git config commit.gpgsign true とする。 これには普通 --global をつけないらしい[stackoverflow-autosign]。

Gitのtag作成時に署名する

$ git tag -s v1.5

[git-gpg]より。

GitHubにGPG鍵を追加する

$ gpg --export --armor KEYID | pbcopy
### クリップボードにGPG公開鍵がコピーされる。
### GitHubの適当な位置に貼り付ける。

参考文献

• [gnupg_faq-no_default_of_rsa4096] https://www.gnupg.org/faq/gnupg-faq.html#no_default_of_rsa4096
• [hatsusato] https://gist.github.com/hatsusato/1d5f0267bc9d02bb24c60bd7acc5a59a
• [joemphilips] http://joemphilips.com/post/gpg_memo/
• [archwiki-gpg] https://wiki.archlinux.jp/index.php/GnuPG
• [riseup-bestpractices-set_calendar] https://riseup.net/en/security/message-security/openpgp/best-practices#set-a-calendar-event-to-remind-you-about-your-expiration-date
• [stackexchange-how_to_delete_subkey] https://superuser.com/questions/1132263/how-to-delete-a-subkey-on-linux-in-gnupg
• [stackexchange-import_secret] https://unix.stackexchange.com/a/392355
• [man-gpg_agent] man gpg-agent
• [qiita-macos_gnupg_ssh] https://qiita.com/sira/items/d61caf237fed95090455
• [man-gpg] man gpg
• [stackexchange-gpg_delete_ssh_key] https://unix.stackexchange.com/questions/185393/gpg-agent-doesnt-remove-my-ssh-key-from-the-keyring
• [git-gpg] https://git-scm.com/book/ja/v2/Git-%E3%81%AE%E3%81%95%E3%81%BE%E3%81%96%E3%81%BE%E3%81%AA%E3%83%84%E3%83%BC%E3%83%AB-%E4%BD%9C%E6%A5%AD%E5%86%85%E5%AE%B9%E3%81%B8%E3%81%AE%E7%BD%B2%E5%90%8D
• [stackoverflow-autosign] https://stackoverflow.com/questions/10161198/is-there-a-way-to-autosign-commits-in-git-with-a-gpg-key

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²⁵

「おすすめ記事」にはプログラミング言語の紹介サイトがよく現れる。有り体に言えば「今年学ぶべきプログラミング言語5選！」のようなものである。開いてみると、有名なプログラミング言語が薄っぺらい説明とともに数種類載っている。私なんかはひねくれているから、「お前がそう思うんならそうなんだろう　お前ん中ではな」などと口走りつつページを閉じるのである。そしておっぱいを見る。

ところで、私が中学2年か3年のときに、和田裕介さんの『Webサービスのつくり方 〜「新しい」を生み出すための33のエッセイ』という本を本屋で立ち読みした。Amazonのサイトに行くとこの本の目次が読めるのであるが、その第4章に「いかにして大量のおっぱい画像をダウンロードするか」という項目がある。中学生の私は大いに興奮しながらそのページを読んだ。記憶が確かなら、そこにはプログラミングを使っておっぱい画像をダウンロードしてくる話が書いてあったのである。この話は和田さんの（あるいは「ゆーすけべー」さんの）ブログにも公開されていて、これを行うためのプログラムを入手することができる。このプログラムはPerlというプログラミング言語で書かれていた。こうして私はPerlという言語を知った。今から考えるとひどい出会い方である。

さてそんなおっぱい言語、もとい病的折衷主義のがらくた出力機、もとい実用データ取得レポート作成言語Perlで書かれた画像ダウンロードプログラムを、中学生の鮟鱇少年はわくわくしながら改造するのである。「まともな」（婉曲表現）おっぱい画像を集めるためにクエリをいじってみたり、より多くののおっぱいを集めるべく取得件数を多くしてみたり。そのためにはPerlのことを知らなければならないから、俗に言う「ラクダ本」を図書館から借りてきて読みふけったし、あるいは画像検索のAPIの仕様をネットで調べたりもした。心底楽しかったのを覚えている。その後わたしはRubyと出会って、おっぱいプログラムをRubyで書き直したりもするのだが、それは別の話。

プログラミングを学ぶって畢竟こういうことなんじゃないだろうか。自分がやりたいことがあって、それを達成するための道具としてプログラミングをやる。中学生の私には、たまたまそれがPerlであったわけで、それがPerlであったことそのものが重要だったわけではない。もちろん職としてプログラミングをやるならある程度「トレンド」のようなものがあるのかもしれないけれど、趣味としてやるなら「どのプログラミング言語を選べばよいか」よりもむしろ「プログラミングで何をやりたいか」のほうが重要なのだろうと思う。

中学の頃から足掛け9年ほどプログラミングをやってきた経験からいえば、メジャーなプログラミング言語を1つ知っていれば、他のものでもある程度検討がつく。薄く広く知っていれば、自分がやりたいことをどのようにやればいいかも自然と分かることが多い。少なくとも趣味としてはこれで十分なんだろうなと、おっぱいを見ながら思うのである。