ユユユユユ

webエンジニアです

ctran/annotate_models に PR を送った

 これまで従事したいくつかのプロジェクトにおいて高い採用率(個人の感想)を観測している ctran/annotate_models にプルリクエストを送った。

get_loaded_model_by_path is supposed to be nil-safe by sato11 · Pull Request #883 · ctran/annotate_models

 たまたま開発中のバージョンで動かしてみて振る舞いの変更=バグに気づくことができたが、そうでなければパッチアップデートで破壊的変更がリリースされるところだった。まあ、まだマージされていないわけで、安心できたとは言えないのだが...。

 エンバグしたパッチとそのレビューをみていて、いちおうそこそこ名の通ったライブラリであっても、わりと杜撰なやり方で開発がおこなわれているのだなと驚いた。というか、ソースコード全体がなかなかにはちゃめちゃなことになっていて、わりとやばいなって感じだった。

 とはいえ、平均的な OSS のパッチの精度は恐ろしく低いというようなことを a_matsuda さんが述べていたことも去来して、「まあそんなものか」ともおもった。なにはともあれ、そこそこ名の知れたライブラリにパッチを送るというのが僕にとっては珍しいことなので、生活の記録として残しておこうとおもう。マージされるといいなあ。

算術右シフトを正しく丸めるためにバイアスを加算する

 マシンがどのように乗算・除算を最適化するについて。二の累乗による乗算は左シフト演算を用いて行うことができる。同じように、二の累乗による除算は右シフト演算を用いで行うことができる。符号なし数であれば論理右シフトを用いるし、二の補数(符号あり数)であれば算術右シフトを使う。

 非負整数に対する算術右シフトは、とりもなおさず論理右シフトを意味するので深く考える必要はない。例えば x = 12340 とおくと、下図のように、結果は切り下げられる。

k x>>k (binary) x>>k (decimal) x/2k
0 0011000000110100 12340 12340.0
1 0001100000011010 6170 6170.0
4 0000001100000011 771 771.25
8 0000000000110000 48 48.203125

 同じように、 x = -12340 とおいて、負数について算術右シフトを適用すると、こちらも同じく切り下げられる。

k x>>k (binary) x>>k (decimal) x/2k
0 1100111111001100 -12340 -12340.0
1 1110011111100110 -6170 -6170.0
4 1111110011111100 -772 -771.25
8 1111111111001111 -49 -48.203125

 しかしこれは求められる動作ではない。というのは、整数の除算は常に0に丸めたいからである。つまり、正数であれば切り下げ、負数であれば切り上げる。いずれも0の方向に丸める。

 無策に算術右シフトを実施すると、一様に切り下げが実施される。これは0方向に丸める要件を満たさないので、戦略が必要である。

 とはいえ、なんのことはない。算術右シフトの計算対象が負数のときは、除算に先立って 除数 - 1 をバイアスとしてあらかじめ加算すればよいだけの話である。ここでいうと (2^k) - 1 をあらかじめ加算してから、割る。整数一般について、除算の結果を切り上げるテクニックと変わらない。

k bias x + bias (x+bias)>>k (binary) (x+bias)>>k (decimal) x/2k
0 0 1100111111001100 1100111111001100 -12340 -12340.0
1 1 1100111111001101 1110011111100110 -6170 -6170.0
4 15 1100111111011011 1111110011111101 -771 -771.25
8 255 1101000011001011 1111111111010000 -48 -48.203125

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-99Lisp 向けの問題集である。いわゆる kata というものと思っている。もうひとつは SICP 、いわゆるウィザード本である。こちらの方が正統かつ王道のおもむきがある。

 今回使ったチュートリアルは、後者のウィザード本を読めるようになることをゴールにしているのだという。つまりそれを終えたいまであれば読めるはず。teachyourselfcs.com でも推奨されているので、遅かれ早かれ挑戦することになるだろう。あるいはなんと全文が HTML で公開されているので、いつでもはじめられる。

 慌てることはしたくないが、胸は高鳴っている。プログラミングが楽しいと心から思える機会を新しく与え直されていることに感激している。

浮動小数点数のビットレベル表現を print する

 浮動小数点数IEEE-754 という規格で標準化されている。たとえば32ビットで表現するとき、上位1ビットが符号に、次の8ビットが指数部に、残りの下位23ビットは仮数部として割り当てられ、これら3つのフィールドが合同してひとつの浮動小数点数を表現する。

 あるいはこの図をみると「ああ、あれね」と思い出すこともあろうかとおもう。

単精度浮動小数点数の32ビットワード表現 (画像はウィキメディア・コモンズによる)

 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;
}

xy の定義域をはっきりさせろ!」とみずから苦情を出したくなりつつも、いったんそれはおいておく。いかにもオーバーフローしそうではある。

 多くの場合、プログラマを困らせるのは「オーバーフローが起こる」という事象そのものよりも「オーバーフローが起こってもプログラムが止まらないこと」だったりする。オーバーフローが発生するときはランタイムエラーが起こるようになっていれば、見当違いのデバッグ方針を携えて右往左往することもない。

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 を読むことを通して、これが実に普遍的な脆弱性の問題と直結していることを手応えとして知った。

 たとえば FreeBSDgetpeername() が持っていた、符号付き整数と符号なし整数のキャスト時のオーバーフローによって、プログラムが不正なメモリ領域を読み取ることができる状態となっていた脆弱性 CVE-2002-0973。あるいはサンマイクロシステムズの XDR ライブラリが持っていた、同じく整数オーバーフローによって悪意をもってメモリ領域を破壊しうる状態になっていた脆弱性 CA-2002-25

 いずれをとっても、有力な C プログラマをもってすら、整数オーバーフローを排除するのは困難であるし、またそれが単なるバグではなく深刻な脆弱性を生むという観点を得られたのは、怖いながらもおおいに学びとなった。

 僕はといえば、競技プログラミングをするだけの気楽な用途であるから、こう考えている。たとえば非負整数であっても int 型で宣言するのと同じような乱暴さで、 long long 型を多用して恥ずかしいことはない。実際、そのやりかたに一抹の恥ずかしさを覚えていたからこそ、 int と long long を使い分けようとしながらもうまく制御できず、不要なオーバーフローを引き起こしてフラストレーションを抱えていたわけである。恥ずかしさでいいプログラムが書けるわけではないから、合理でもって long long 型に活路を見出そうと思っている。

大型連休の振り返り (2021)

 2021年の大型連休が終わった。いやすでにこどもの日でもって終わっているという向きもあるが、僕のなかでは今日の日曜日をもって「終わったなあ」という情緒であるので、振り返っておく。

arduino で遊んだ

 LED をチカチカさせたり、電圧計の使い方を覚えたりした。

f:id:jnsato:20210509112743j:plain

 電子工作はまったく初心者だし、電気の知識さえ中学レベルで止まっているあたりが引け目になっていた。

『みんなの 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 を読了した。これは 別のエントリ として投稿した。

 消費サイクルが激しい世の中にあって、ひとつの重要な本をじっくり読むというのは贅沢な経験だった。トレンドやマーケティングの波に振り回されずに、自分が重要と信じるものに粘り強く、真面目に向き合おうとする態度は忘れないようにしたい。

放送大学に行ってみようと決めた

 これも別エントリにすでに書いているが、大事なことなので再訪する。

 どこにも出かけられずに過ごす連休の真ん中あたりで、世の中の息苦しさにあてられていた。海外にでもいきたいなと随筆をした。これを呼水にして、いつかやりたいことと、なりたい自分の像、そしてそのためにいまできること、といった具合に考えが膨らんだのだった。

「理工系の大学で勉強したい」という願望のようなものは以前からぼんやりあったが、学位がほしいわけではないことははっきりとわかった。それよりも、いま仕事でも趣味でも眺めているコンピュータとプログラミングのパラダイムを、いまよりも高い解像度で捉えられるようになりたい、そのための勉強がしたい、という願望に言い換えられるようになった。

 コンピュータの勉強であれば自走するだけの体力はすでにあるが、基礎科学的な勉強は独学するよりもまずはレールに乗って学ぶべし。そしてそのニーズを埋める場所として、放送大学はうってつけの環境である。そういう気持ちになっている。

 まあ、これは向こう数ヶ月でまたアップデートするトピックではあろうが、いまのアティチュードとしてはこんなところである。

社内勉強会の予習をした

 新しい会社にはいり、読書会という(僕にとっては)新しい形態での勉強会に参加することになった。『アルゴリズムとデータ構造』と『マイクロサービスアーキテクチャ』をそれぞれ読むふたつの会にサインアップした。

f:id:jnsato:20210509112806j:plain

 どちらも自分ひとりで勉強するのであれば手にとることはない本であったようにおもう。そもそも 「新刊本は買わない」というポリシー を掲げているわけで、あるいは書店で見かけていたのかもしれないが、基本的に見向きもしない部類の本である。

「新刊本は買わない」という2021年の目標には反する形になるが、まあこれは別として自分に許してしまうことにする。どちらもそこまで難解な本ではないし、週にそれぞれ1-2時間ほどを割り振ってやる計画で十分読める。

 とりあえずは勉強会という新しい学びの形式を楽しめたらなと思っている。

指輪物語を読んでいる

 現実に向き合うのがつらいのでフィクションばかり読むようになっている。このあいだまでは SF を多めに読んでいたのだが、だんだん科学よりもファンタジーを求めるようになった。「じゃあやっぱりここからでしょ」と言わんばかりに大古典を 全巻セット で購入し、読み始めた。

 映画シリーズはひととおりみているが、原典を読むのは初めてである。しかし読み始めてみると、映画のイメージとは関係なく、とても新鮮な気持ちで読める。いい年してワクワクドキドキしながらページを繰っている。

 なにせ壮大な設定が背後に控えているので、読むのも楽しいけど読み終わったら解説やら考察やらを知らずにはおけなくなりそうだし、映画も見直したいし、ホビットの冒険も読み直さなきゃいけないし、ととめどなくなりそうである。

 これだけ楽しめるのは幸せとしかいいようがないはずなのだが、そうなるといよいよ時間のやりくりがたいへんになるなあとうれしい悲鳴をあげざるをえない。あのとき買ったビットコインを売らずに握っておけばいまごろはそれを換金してもう1年くらいは無職で好きなことだけやれたのかな...という現実逃避が頭をもたげるが、そういう空想にふけることができるのもファンタジー世界に心を半分持っていかれているからだろうか。ある意味で幸せなことではあるが、お花畑と揶揄されない程度には注意しておきたい。