gcc-9 を使うようにした
昨晩の ABC-202 への参加中に、コンパイラが動かないという自体に直面した。先週のコンテストまでは普通に動いていたコンパイルタスクがこういうログを吐いて停止してしまう。
command not found: x86_64-apple-darwin19-gcc-10
コンテスト中は AtCoder のコードテスターを代理の実行環境として使ってことなきをえたが、いったいなんだったのかを一晩明けて考えた。
わかったのはこういうことだった。この記事で設定したやり方がうまくなかった。brew install gcc
でインストールしたのが当時は gcc-10 だったものが、なんとなく brew upgrade したときにそうと気づかず gcc-11 になってしまっていた様子。
要するに、特定バージョンへの依存に無頓着だったというだけのことであった。というかそもそも gcc-10 を使っていたことにも意味はなかった。 AtCoder のコンパイラは gcc-9.2.1 と書いてあるので(執筆時時点)、今後はこれを使うことにした。
こうやって直してみた。まずは dotfiles で gcc-9 のインストールとエイリアスの設定をおこなう。それから atcoder の実行環境でもビルドタスクのコマンドを書き換える。
dotfiles で定義した alias g++='g++-9'
を .vscode/tasks.json
のなかで使おうと思ったのだが、どうしてかうまく読み込まれずに xcode の clang が呼び出されてしまうので、タスク定義では相変わらず g++-9
と不格好にバージョンを指定してしまっている。まあ、インストール側でバージョン固定をしているわけだし、これくらいならいいかとズボラになっている。
Yet Another Scheme Tutorial をやった
大型連休にやっていたことで、大型連休の総括に書かなかったことがひとつある。それは Lisp への挑戦である。
Yet Another Scheme Tutorial というマテリアルを利用した。そしてきょう、それをひとまず一周走り終えた。
どうしていまこれを学ぼうと思ったか? ハッカーたちが口を揃えて勧めるものだから、たしかに何かがあるに違いないと思ったのである。いうなれば直感である。なかでも大きく影響を与えられたエッセイをふたつあげると、それはこれらである。
まずは Steve Yegge の「バベル案内」。お気に入りのパッセージを引用する。
Lispを学ぶのは簡単ではない。大きな飛躍がいるのだ。CみたいなプログラムをLispで書けるというのでは十分でない。そんなのは無意味だ。CとLispはスペクトルの反対の端に位置している。他方が上手く扱えない領域で大きな力を発揮するのだ。
それから Paul Graham の「普通のやつらの上を行け」。同じように引用するがこちらは短く凝縮されたパンチラインだ。
Lispの力は、ライバルがそれを理解できないということによって増幅されるんだ。
こんな熱いアジテーションをされておいて、「やらいでか!?」という熱狂を与えられずにいられようか?
どちらのエントリにしても、 Lisp を学ぶのは容易ならざる道だというのは一致している。しかし、「みんながやっているから」という理由だけで、あの言語つぎはこのフレームワークそれから機械学習チュートリアル...と節操ない消費主義で踊らせてわれわれプログラマを消耗させようとする技術市場にヘキエキしていた僕にとって(このことは年初に今年の意気込みとして書いた)、この揺るがない古典の風格を帯びた言語は救済の光にみえたのである。
これからいっそうこの小さな言語に勤しむことにするか? いや、いまは CS:APP を読み進めることの方を優先したい。このままインテンシブに Lisp の独習コースを催すことはしない。
とはいえ、機をみてとりくみたいマテリアルははっきりしている。ひとつは L-99 。 Lisp 向けの問題集である。いわゆる kata というものと思っている。もうひとつは SICP 、いわゆるウィザード本である。こちらの方が正統かつ王道のおもむきがある。
今回使ったチュートリアルは、後者のウィザード本を読めるようになることをゴールにしているのだという。つまりそれを終えたいまであれば読めるはず。teachyourselfcs.com でも推奨されているので、遅かれ早かれ挑戦することになるだろう。あるいはなんと全文が HTML で公開されているので、いつでもはじめられる。
慌てることはしたくないが、胸は高鳴っている。プログラミングが楽しいと心から思える機会を新しく与え直されていることに感激している。
浮動小数点数のビットレベル表現を print する
浮動小数点数は IEEE-754 という規格で標準化されている。たとえば32ビットで表現するとき、上位1ビットが符号に、次の8ビットが指数部に、残りの下位23ビットは仮数部として割り当てられ、これら3つのフィールドが合同してひとつの浮動小数点数を表現する。
あるいはこの図をみると「ああ、あれね」と思い出すこともあろうかとおもう。
32ビットの整数値を浮動小数点のフォーマットに変換するエクササイズをやっていて、困ったことがあった。それは IEEE-754 に準拠したビット表現を手軽に print する手段が提供されていないことである。たとえばこれは動かない例である。気軽に %x
で16進数を書き出そうとしている。
float f = 1.0; printf("%x\n", f); // warning: format specifies type 'unsigned int' but the argument has type 'float' [-Wformat]
実に、 printf
の %x
オプションは unsigned int
を要求していて1、何も考えずに float
を突っ込んで魔法のようにうまくいくことはない。
かといって、 IEEE-754 に準拠した print を自力で実装することはできない。そもそも標準規格への理解が足らないがゆえに print を欲しているわけで、何かしらうまく動くプログラムを他力本願に望むほかなにもできない。
で、 StackOverflow にてそれに近いものを発見した。リンクはこれである。あらかじめ告白すると、いったいなにをやっているコードなのかはわからない。わからないながらに、少なくとも便利に使えるとは判断できるため、いまの未熟な理解度を記録する目的も込めて書く。
それがこんな関数である。
void print_i3_754(float r) { union { float f; unsigned int u; } f2u = { .f = r }; printf("0x%.8x\n", n); }
使ってみよう。
int main() { int x = 3'510'593; float y = x; printf("0x%.8x\n", x); print_i3_754(y); return 0; } // x = 0x00359141 // y = 0x4a564504
と、期待通りの表現が得られた。
整数オーバーフローをコントロールすることの難しさ
C++ で競技プログラミングをやっていて、整数オーバーフローに泣かされたことのない者はいないだろう。僕とてそうである。ちょっとしたケアレスミスにすぎないのだが、些細なミスであるからこそ、それを繰り返してしまうとことさら不甲斐なく感じる。
オーバーフローを機械的に防ぐ方法はないだろうか?「気をつける」以上のシステマチックなやり方で回避することはできないか? と、まるで障害報告書を書くような気持ちで何度も振り返るも、いつも結論はでないままだった。
いま、 CS:APP を読んでいて、いまいっぽぼんやりしたまま寝かせていた考えに光が当てられた気がするので、今回はそれをまとめようと筆をとった。
あらかじめ述べておくと、結論としてはありきたりな表現にすぎない。クサいところはより大きい幅を表現できる整数型を使おう、というところに着地している。それ以上でもそれ以下でもない。
たとえば愚直に書いたこんな計算を考えてみよう。
int main() { int x, y; cin >> x >> y; int answer = x * y; cout << answer << endl; return 0; }
「x
と y
の定義域をはっきりさせろ!」とみずから苦情を出したくなりつつも、いったんそれはおいておく。いかにもオーバーフローしそうではある。
多くの場合、プログラマを困らせるのは「オーバーフローが起こる」という事象そのものよりも「オーバーフローが起こってもプログラムが止まらないこと」だったりする。オーバーフローが発生するときはランタイムエラーが起こるようになっていれば、見当違いのデバッグ方針を携えて右往左往することもない。
int safe_mult(int x, int y) { int p = x * y; if (x != 0) { assert(y, p / x); } return p; } int main() { int x, y; cin >> s >> y; int answer = safe_mult(x, y); cout << answer << endl; return 0; }
この関数をライブラリとして持っておいて、乗算をしたいときはいつでもこれを呼び出すか? いや、それも片手落ちである。なぜなら結局のところ、ランタイムエラーは出てしまうわけで、それによって誤答ペナルティが与えられてしまう。オーバーフロー時にエラーを吐いて緊急停止するのは、そうでないよりはマシではあるものの、本当にほしいものはこれではない。
となると、結局のところは最初から64ビットを使ってこう書いてしまうのが手堅い。オーバーフローが起こったとして、まず考えられるのはこうして幅を広げることであるから、最初からクサイところはこう書くのが合理的か。逃げの一手でしかないが、僕程度の水準の競技プログラマにとってはこれで十分そうに思える。
int main() { long long x, y; cin >> x >> y; long long answer = x * y; cout << answer << endl; return 0; }
64ビットを使ってもなおオーバーフローするような入力が与えられるときはどうしようか? そういうケースに遭遇したことはいまだないような気がするが、そのときこそこうなるか。
long long safe_mult(long long x, long long y) { long long p = x * y; if (x != 0) { assert(y, p / x); } return p; } int main() { long long x, y; cin >> x >> y; long long answer = x * y; cout << answer << endl; return 0; }
64ビットを費やしてもなおオーバーフローが発生する計算をするなら、このときこそエラーを投げて異常終了する。計算の仕方を見直すべきである。どうしても大きな整数を扱うのであれば、可変長の幅を表現できるライブラリなり言語を使わなければならない。しかし繰り返すが、そんなユースケースは滅多にあるものだろうか?
というわけで、なにか新しいインサイトを提供することはできず、ありきたりな議論に終始した。しかしこれまで書かずにいたものをこうして言語化したことの背後には、僕のなかでの学びがある。それはこういうことである。
整数オーバーフローに関するこの問題意識は、以前は単なる個人的なフラストレーションを動機づけとしていた。それ以上のものではなかったので、表立って公開しようとも思いはしなかった。しかしいま CS:APP を読むことを通して、これが実に普遍的な脆弱性の問題と直結していることを手応えとして知った。
たとえば FreeBSD の getpeername()
が持っていた、符号付き整数と符号なし整数のキャスト時のオーバーフローによって、プログラムが不正なメモリ領域を読み取ることができる状態となっていた脆弱性 CVE-2002-0973。あるいはサンマイクロシステムズの XDR ライブラリが持っていた、同じく整数オーバーフローによって悪意をもってメモリ領域を破壊しうる状態になっていた脆弱性 CA-2002-25。
いずれをとっても、有力な C プログラマをもってすら、整数オーバーフローを排除するのは困難であるし、またそれが単なるバグではなく深刻な脆弱性を生むという観点を得られたのは、怖いながらもおおいに学びとなった。
僕はといえば、競技プログラミングをするだけの気楽な用途であるから、こう考えている。たとえば非負整数であっても int 型で宣言するのと同じような乱暴さで、 long long 型を多用して恥ずかしいことはない。実際、そのやりかたに一抹の恥ずかしさを覚えていたからこそ、 int と long long を使い分けようとしながらもうまく制御できず、不要なオーバーフローを引き起こしてフラストレーションを抱えていたわけである。恥ずかしさでいいプログラムが書けるわけではないから、合理でもって long long 型に活路を見出そうと思っている。
大型連休の振り返り (2021)
2021年の大型連休が終わった。いやすでにこどもの日でもって終わっているという向きもあるが、僕のなかでは今日の日曜日をもって「終わったなあ」という情緒であるので、振り返っておく。
arduino で遊んだ
LED をチカチカさせたり、電圧計の使い方を覚えたりした。
電子工作はまったく初心者だし、電気の知識さえ中学レベルで止まっているあたりが引け目になっていた。
『みんなの Arduino 入門』をウォームアップとして一周した。半日で終わるくらいのちょうどいいボリュームだった。大型連休の初日を楽しませてくれた。
本当は『CPUの創りかた』を読みたかったところ、秋葉原に部品を買いにいくというところがネックになり止めている。そもそも祝日に営業しているものかわからないし、それでも平時であればとりあえず出かけてみるのだが、どうせどこにいってもどこも臨時休業だろうし、と萎縮して出かけるのをやめた。
そのおかげで、これから書く別のトピックにも時間を割くことができたわけでもあるので、怪我の功名というか塞翁が馬というか、まあなるようにしかならない、という気分であった。
Leetcode で連結リストと木構造のレッスンをした
僕がいまの会社の入社面接を受けたときにはコーディング試験というものはなかったのだが、近頃になって導入を図っているらしい。Leetcode の適当な問題を指定して解いてもらう形式と聞いて、自分でもアカウントを取得してやってみることにした。
日曜日の週次コンテストに数回参加した。しかしコンテストというよりはむしろ教育コンテンツがメインのサービスだということがだんだんわかり始めた。
で、連休には Introduction to Data Structure というシリーズをやってみていた。やったのは Arrays 101 と Linked List そして Binary Tree である。
実をいうと、連結リストを自前で実装するのは初めてだった。競技プログラミングであればキューとかスタックを呼び出すだけの話なので、考えてみればそれはそうでしかない。やってみるとまあバグること。思わぬ無限ループをやたらに発生させていた。でも、うまくいかなくてイラつくというよりも、着実にエッセンスを学びとることができているという興奮の方が大きかった。その意味で、練習問題の質はとてもよいと感じた。
Linus が言っていた センスのいい単方向連結リスト のセンスのよさがわかるようになった。僕自身はというとセンスが悪いほうのコーディングをするのがまだ精一杯だが、少なくとも Linus が何を言っているのかがわかったことが嬉しい。
AtCoder で初めて水色パフォーマンスを出した
4月の最後のコンテストで レーティングが緑になった 。
たぶん三日天下で終わるんじゃないかと思っていたのだが、続けて出た5月最初のコンテストでは初めての 水色パフォーマンスを出すことができた 。まあこれも速解きの産物でしかなく、あまり実感はわかないのだが、結果は結果として喜んでいる。
しばらくレーティングが伸び悩んでいたので、このあたりが自分の実力の相場なのだろう、と卑下してしまっていたところがあったが、まだ伸び代はあるなと感じている。おりしも 典型90問 という企画も提供されていて、これも学びになっている。なかなか難しくはあるが、難しくてこそ学びがいがある。
そういう気分であるから、緑色になったことに満足して参加を止めるなんてつまらないことは言わないで、腕試しの参加はまだまだ続けたいとおもう。
DDIA を読了した
昨年末に着手した Designing Data-Intensive Applications を読了した。これは 別のエントリ として投稿した。
消費サイクルが激しい世の中にあって、ひとつの重要な本をじっくり読むというのは贅沢な経験だった。トレンドやマーケティングの波に振り回されずに、自分が重要と信じるものに粘り強く、真面目に向き合おうとする態度は忘れないようにしたい。
放送大学に行ってみようと決めた
これも別エントリにすでに書いているが、大事なことなので再訪する。
どこにも出かけられずに過ごす連休の真ん中あたりで、世の中の息苦しさにあてられていた。海外にでもいきたいなと随筆をした。これを呼水にして、いつかやりたいことと、なりたい自分の像、そしてそのためにいまできること、といった具合に考えが膨らんだのだった。
「理工系の大学で勉強したい」という願望のようなものは以前からぼんやりあったが、学位がほしいわけではないことははっきりとわかった。それよりも、いま仕事でも趣味でも眺めているコンピュータとプログラミングのパラダイムを、いまよりも高い解像度で捉えられるようになりたい、そのための勉強がしたい、という願望に言い換えられるようになった。
コンピュータの勉強であれば自走するだけの体力はすでにあるが、基礎科学的な勉強は独学するよりもまずはレールに乗って学ぶべし。そしてそのニーズを埋める場所として、放送大学はうってつけの環境である。そういう気持ちになっている。
まあ、これは向こう数ヶ月でまたアップデートするトピックではあろうが、いまのアティチュードとしてはこんなところである。
社内勉強会の予習をした
新しい会社にはいり、読書会という(僕にとっては)新しい形態での勉強会に参加することになった。『アルゴリズムとデータ構造』と『マイクロサービスアーキテクチャ』をそれぞれ読むふたつの会にサインアップした。
どちらも自分ひとりで勉強するのであれば手にとることはない本であったようにおもう。そもそも 「新刊本は買わない」というポリシー を掲げているわけで、あるいは書店で見かけていたのかもしれないが、基本的に見向きもしない部類の本である。
「新刊本は買わない」という2021年の目標には反する形になるが、まあこれは別として自分に許してしまうことにする。どちらもそこまで難解な本ではないし、週にそれぞれ1-2時間ほどを割り振ってやる計画で十分読める。
とりあえずは勉強会という新しい学びの形式を楽しめたらなと思っている。
指輪物語を読んでいる
現実に向き合うのがつらいのでフィクションばかり読むようになっている。このあいだまでは SF を多めに読んでいたのだが、だんだん科学よりもファンタジーを求めるようになった。「じゃあやっぱりここからでしょ」と言わんばかりに大古典を 全巻セット で購入し、読み始めた。
映画シリーズはひととおりみているが、原典を読むのは初めてである。しかし読み始めてみると、映画のイメージとは関係なく、とても新鮮な気持ちで読める。いい年してワクワクドキドキしながらページを繰っている。
なにせ壮大な設定が背後に控えているので、読むのも楽しいけど読み終わったら解説やら考察やらを知らずにはおけなくなりそうだし、映画も見直したいし、ホビットの冒険も読み直さなきゃいけないし、ととめどなくなりそうである。
これだけ楽しめるのは幸せとしかいいようがないはずなのだが、そうなるといよいよ時間のやりくりがたいへんになるなあとうれしい悲鳴をあげざるをえない。あのとき買ったビットコインを売らずに握っておけばいまごろはそれを換金してもう1年くらいは無職で好きなことだけやれたのかな...という現実逃避が頭をもたげるが、そういう空想にふけることができるのもファンタジー世界に心を半分持っていかれているからだろうか。ある意味で幸せなことではあるが、お花畑と揶揄されない程度には注意しておきたい。
CS:APP を読みはじめる
Computer Systems: A Programmer's Perspective の日本語訳、『コンピュータ・システム — プログラマの視点から』を購入した。通称は CS:APP というらしい。
値段、重量、厚みすべてにおいてヘビー級の一冊である。16000円だった。消費税で本が一冊買える。
しかしこうやって専門書を買う選択肢を持てるのが社会人のいいところであるよ、と感慨をもつ。しょっちゅうこんな買い物をしたいとはさすがに思わないが、必要を吟味していよいよ心を決めたときには、資本主義的自由の味がした。
情報処理学会の監修というから内容には全幅の信頼がおける。丸善出版というのもいい。この出版社の専門書を買うのは Effective C++ を読んだとき以来となるが、これもいい本であったのを懐かしく思い出している。
英語版にトライすることも検討した。しかしいずれ値段は大きく変わらないこと、加えてその厚み(日本語ですら800ページ超!)をおもうと、いよいよ英語では一年かけてなお通読できるかどうか自信がなかった。とはいえ結局のところ、学会の監修がついているという信頼がここでも効いてくる。翻訳のクオリティが最低であるということはまずないだろう、と安心して訳書を選ぶことができた。
これも teachyourselfcs.com の推薦である。職業プログラマがコンピュータ・アーキテクチャを学びはじめるのにうってつけの一冊とのことである。
これだけのボリュームを読み通して、やっとスタート地点に立てるようになる、というような紹介のされ方であった。「これさえ読めば」式の宣伝文よりはよほど誠実な推薦だとおもう。真実を言っているな、という確信がある。これを推薦してくれる人たちと、これを訳してくれたアカデミズムの人たちの助力のもとに、僕はまだまだ進歩できるという前向きな気持ちで取り組んでいこうとおもう。
Designing Data-Intensive Applications を読み終わった
昨年末に着手して、足掛け5ヶ月で読了した。
5ヶ月というとあまりに時間がかかりすぎているように聞こえる。実際には年末年始とこの GW で集中的に読んだ。しかも、後者の連休ではメモを取りながら読み進めることをやめて、読み終えることそのものを目標化して無理やり終わらせたきらいさえあるので、時間を尺度とすることには(そうでなくても意味はないが)ここではあまり意味はない。
分散システムにおけるデータの流れにフォーカスした著作である。どの章をとっても含蓄ある文章しかないので、要約するには僕の手に余る。無理に一般化して語るよりも、序説を概観した5ヶ月前のエントリをみてもらうほうが話は早そうである。
それから、いくつかのチャプターについては個別のエントリとして要約をポストしている。
- 信頼性、保守性、スケーラビリティ: Designing Data-Intensive Applications 第1章より
- データベースを支えるデータ構造: Designing Data-Intensive Applications 第3章より
- 分散データベースのレプリケーション: Designing Data-Intensive Applications 第5章より
12の章立てのうち3章のみかいつまんだ形である。もちろんこれらのほかの章もとても興味深い話のオンパレードである。本当はすべてを紹介したい、なんなら理解を含める目的で私家版の翻訳すら作成してもよい、というくらいに全編にわたって秀でた情報量をほこっているが、そうまではしなかった。
「なんとなく聞いたことがあるようで、実はよくわかっていない」というあたりの知識領域を包括的に扱って、体系的な知識としてまとめてくれている稀有な本である。僕にとってはデータベースのインデックスアルゴリズムがそうで、ここで B-tree が何者であるのかわかったし、 LSM-tree という新しいデータ構造も知ることができた。
第二部 "Distributed Data" では分散データベースの設計・運用上のプロ・コンおよび落とし穴がこれでもかとカタログ化されていて、大規模分散データベースなんて人類には早すぎるのではないか...と暗澹たる気分になかばされつつも、これを読んだおかげでどれだけの新しい視点を得られたかとおもうとずいぶん成長した気がしている。
末尾を飾る第三部も、つい先ほどまで読んでいたこともあるものの、忘れがたい視点であることは疑いない。とりわけ、非同期のイベントによって派生データを適切に制御するという案件をちょうど業務で扱っているところであったので、示唆を与えられるパッセージはあまりにも多かった。それがいかに難しいトピックであるかを痛いほど知ることになり、これらの知見を持たないまま進めてしまっていたらどうなってしまっていたかをおもうとゾッとする。もっとも、これらを知った上でなお難しい問題であることには変わりがないのだが、学んだことをただちに活かせるかもしれないというのは幸せなことである。
読み始めたときのエントリで、本書が teachyourselfcs.com で強く推薦されていたことを紹介した。それに加えて、ハッカーニュースで見かけた フェイスブックの面接対策の記事 でもやっぱり本書が紹介されていた。いわく、上級エンジニア面接ではコーディング試験と同じくらいかそれ以上にシステム設計の知識が求められ、それの足掛かりとするのにちょうどいい本であるそう。僕自身はいまのところビックテック企業の規模のプロジェクトを遂行するような経験はまだないけれど、そうしたレベルを求める人々にとってさえもこの本が有用なリソースであるというのは心強く感じる。つまり、それだけ信頼のおける本であるということ。
反省点としては、ノートのとり方が非常に乱暴だったところか。重要そうな箇所を適当にピックアップして入念に整理することができず、「やたらにひたすらメモをとる」か「ほとんどメモもとらずに読みすすむ」のいずれかに陥りがちであった。これは仕方のないところもあるとおもう。というのは、前提知識の弱さから、書かれてあることすべてが真新しいパースペクティブと映りがちであったため、「重要でないところを読み飛ばす」ということが原理上不可能であったためである。いちどザッと通読してから、重要なところをインデックスしていく戦略で読んでおけば、より効率的にインプットできたかもしれないが、その読み方ではいま受けているほどの感銘は受けなかったかもしれない。いずれにせよ、高い確率で向こう数年中に再読する予感はあるため、なにも悲観すべきことはない。
英語で通読することができたことも誇らしくおもう。日本語と同等の速度で読み進めることはできないが、そのぶんだけ丁寧に読み進められた。スルスルと読んでいるつもりが、ある箇所で突然読めなくなることがあった。そういうときは、それまでスルスルと読んできた前提を正しく読めていなかったというだけにすぎない。実際、すこし前に戻って読みなおすだけで、たいていの難所は突破できる。この点、日本語で読んでいると、わからないことを翻訳のせいにして放置してしまうところがある。まあ、実際に翻訳が悪いこともあるとはおもうが、せっかくいいことが書いてあっても正しく読めないのは申し訳がない。結局のところ、原典にあたるというのはどこまでいっても有効であるという思いを深めている。