本『実力も運のうち』
『実力も運のうち』を第一章まで読んだ。
まず、能力主義の道徳的問題の指摘はするどい。
自分の才能のおかげで成功を収める人びとが、同じように努力していながら、市場がたまたま高く評価してくれる才能に恵まれていない人びとよりも多くの報酬を受けるに値するのはなぜだろうか？
マイケル サンデル. 実力も運のうち 能力主義は正義か？ (p.39). 株式会社 早川書房. Kindle 版.
つまり、他の人が評価してくれるような実力を手に入れられるかはまさに運しだい、というわけだ。 この事実を迂回して能力主義の正当化をするのは難しいと思う。
一方で、能力主義がもたらす政治的問題の部分は納得がいっていない。すなわち、能力主義が共通善を貧相なものにし、社会におごりと屈辱を生むことで分断をもたらしポピュリズムの糧となる。 このプロセスには正当化が足りておらず、どうしても陰謀論めいて見えてしまう。第二章でこの話題を取り扱いそうなので今後に期待。
また、サンデルの取り上げる共通善が一体何なのか分からない。そのうち取り上げられるだろうからこれも今後に期待。
Lox (Crafting Interpreters)にdefer文を追加する
Crafting InterpretersはRobert Nystromによるインタプリタ方式のプログラミング言語処理系の作り方の解説本である。
ハードカバー・電子書籍が発売されているほか、著者のページでWeb版が無料公開されており、自作言語界隈では人気を博している。
Crafting Interpretersでは著者が考案したLox言語のインタプリタを実装していくこととなる。本の前半部分ではAST評価器を扱い、後半部分ではバイトコードVMを用いたインタプリタを実装する。
Lox言語はシンプルとはいえ、クロージャやクラスの継承といった高度な機能も備えたオブジェクト指向スクリプト言語であり、読者は小さなインタプリタからステップ・バイ・ステップでだんだんと完全な処理系を構築していく。
Crafting Interpretersの素晴らしいところには次の点が挙げられるだろう:
- 平易な文章に加えて豊富な例とイラストによってインタプリタの実装を分かりやすく伝えることに成功している
- それにもかかわらず、自前のGCやNaN Boxingのような高度な話題も提供している
- 公式のGitHubリポジトリで網羅的なテストケースを公開しており、読者が自分の実装の完全性を確かめられる
大変教育的な本なので言語処理系に興味のある人はぜひ一度挑戦してみるのがよい。
さて、私は先月ごろCrafting InterpretersのバイトコードVMのRust実装に挑戦しており、公式のテストケースが全て通るところまで完成していた*1。
この記事ではVMのコード実装に手を加えることでGo言語のdefer文をLoxに導入してみる。
まずは例を見るのが分かりやすいだろう。
{
var i = 100;
defer {
print i; // expect: 300
}
i = 300;
}
このプログラムでは、deferの直後に指定したブロックが、スコープの終わりまで遅延して実行され、結果としてprint文が300を出力する。（本来Go言語でのdeferは関数末尾で実行されるのだが、今回の記事ではスコープの終わりで実行することにした。理由は読めば分かる）
実はLoxにdeferを追加するのは非常に簡単である。LoxのバイトコードVMはスタックマシンであり、またローカル変数はスタック上の位置で表現される*2。
例えば、
fun f() {
var a = "foo"; // "foo"がスタックの1番目に積まれる
{
var b = "bar"; // "bar"がスタックの2番目に積まれる
print(a + b); // expect: foobar
// "bar"がpop
}
// "foo"がpop
}
というプログラムでは、ローカル変数aがスタックの1番目に、bがスタックの2番目に対応している。
実はスタックの0番目も存在し、それは関数fに対応する。
ローカル変数に対応するスタック上の位置は静的に決定できるため、生成されたバイトコードには変数名はもはや存在せず、必要なのは計算した位置だけというわけだ。
このローカル変数とスタック上の位置の対応を維持するため、スコープの終了時にはそのスコープに含まれている変数の数だけスタックから値をポップしてあげる必要がある。
言い換えれば、LoxのバイトコードVMにはすでにスコープの終わりに任意の処理を実行する仕掛けが搭載されているのである！
実際、Crafting Interpretersではこの仕掛けを使うことで、クロージャのキャプチャする変数がスコープから抜ける際に参照がダングリングしないよう繋ぎ変える処理を行っている。
この仕掛けを再利用してやると、次のようにdefer文が実現できる:
- defer文のブロックを0引数関数としてコンパイルする
- その関数で初期化される特別な無名のローカル変数を追加する
- このローカル変数がスコープから抜ける際、スタックからポップする代わりに関数を呼び出す
疑似コードで書くと次の通り:
{
var i = 100;
var __defer = fun() {
print i; // 無名関数はローカル変数iへの参照をキャプチャする
}
i = 300;
// __deferがスコープから抜けるので、関数として呼び出す: __defer()
// iがスコープから抜けるのでpop
}
この実装のためには、バイトコードコンパイラでローカル変数を扱う際にdeferで生成された特別なローカル変数かどうかを表すフラグを追加してさえあげればよい。
スコープの終了時に、変数のフラグが立っていたらdefer関数とみなして関数呼び出し命令を発行し、そうでなければ単にポップ命令を発行することで実装が完了する。
関数呼び出し命令はリターン時に関数をスタックからポップしてくれるのでそれもちょうどよい。
実は、関数を呼び出すためにはスタックを調整する必要があるのだが、deferのケースではその必要も無い。
上でスタックの0番目が関数に対応していると述べたことを覚えているだろうか？
deferを実行するタイミングでは、deferで呼び出す関数がスタックのトップに来ており、またこの関数は0引数なのでスタックの調整をせずにそのまま呼び出せるのだ。
ということを昨晩ベッドの中で思いついたので今日実装してみたというわけ。実装も30分ぐらいで済んだ割にはdeferという非自明な機能が実現できたのでとても満足だ。
実装のdiffはこんな感じ:
github.com
まあ、この処理系ではファイル等のリソースが存在しないのでdeferが活躍する場も無いのだけれど…
*1:ソースコードは https://github.com/pandaman64/rlox で公開している
*2:原著ではイラストも含めて分かりやすく説明されているからぜひ読もう。自分には絵心が無かった…
日本人優遇とその裏
今のアパートもありえないほどの掘り出し物件かつwaiting listの7人目だったらしいんだけど、後に分かったところによると大家が日本贔屓かつテック産業大好きで、僕のプロフィールをみてwait list一番上に引き上げてくれたらしい。その日のうちに契約した。先人が築いてくれた信頼に感謝したいね😘
— しろやま (@fushiroyama) 2021年9月12日
こういうのとか
ドイツから帰国する時にマンションを引き払った際、大家さんから『交代の社員が来るんでしょ？紹介してよ』と。
— 海外 浩平｜KaiGai Kohei🌻 (@kkaigai) 2021年9月15日
どうやら日本人は
・金払いが良い、遅れない
・部屋を綺麗に使う（靴を脱ぐので）
という事でwelcome属性なんだそうな。
そういう無形の資産はまぁ、大切にしていきたい。 https://t.co/pTkhuck2bU
こういうのは日本語圏のツイッターエンジニア界隈では概ねいい話*1として受容されているようだ。
しかし、こういった日本人への優遇への裏側には（相対的にしろ）そのほかの人々への冷遇が存在している。
そして、この取り扱いの差は「日本人は金払いが良い」といった先入観に基づいている*2。
衣食住とも言われるとおり、住居は人間の生活において重要なファクターの一つである。
居住の自由は広く認められている人権の一つであり*3、また通勤や教育へのアクセス（学区）、その他公共サービスなど幅広い形で生活に関わっている。
それにもかかわらず、上に挙げたような国籍・人種に基づく先入観によって生じる取り扱いの差は不当であり、差別の一例であると私は考える。
さらに、たとえ「日本人は金払いが良い」といった先入観が正しかったとしても、やはりこの取り扱いの差は統計的差別としての問題を含んでいるだろう。
海外だけでなく、日本でも住居の差別は生じている。
例えば、2017年に発表された外国人住民調査では、住居を5年以内に探したことのある外国人のうち約4割の方が「外国人であることを理由に入居を断られ」たり、「日本人の保証人がいないことを理由に入居を断られ」たりしたことがあると述べている。
また、これらの人々の中には「日本人と同程度に会話できる」にもかかわらず断られている人も含まれており、日本に在留する外国人に対する差別が起きているのは間違いない。
もちろん、先入観に基づく判断が常に悪いというわけではない。
例えば、初めて会った人が「金」と名乗ったとき、「韓国人なのかな」「韓国人であるなら韓国語を話せるだろう」といった先入観は多くのケースで正しく、そこから「アニョハセヨ」と挨拶するのは良い歓迎かもしれない。
けれども、大坂なおみさんのような例外は存在している。
また、アメリカやヨーロッパにおけるアジア人に対する差別の文脈を考慮したならば、ツイートの例はそこまで悪いわけではないのかもしれない*4。
けれども、これらの日本人優遇は差別的取り扱いと密接に繋がっており、あまり無邪気に喜んでほしくないと思うのだ。
nitpick 『詳説データベース』
CRDTなデータベースをon-diskで実装してえ…という思いが高まってきたので購入。ストレージエンジンと分散システムというトピックはどっちも興味があるのですごい嬉しいしオライリーだからDRMフリーPDFなのも素晴らしい。
ただ、読んでて筆が滑ったのか自分の読み方が良くないだけなのか不明なところがちょくちょくあるのでメモしたいと思う。ただ、この記事はnitpickであって内容の良しあしとは関係ないのでそこは注意すること。
「ここはこういう意味だよ！」とか「普通に読めるよ！」とかコメントいただけると幸いです。
Bツリーの本質はノード内の二分探索ではない (2.3 ユビキタスBツリー)
曰く、
Bツリーはソートされています。つまり、Bツリーのノード内のキーは、順番に格納されています。それゆえに、検索対象のキーを探すために二分探索のようなアルゴリズムが使用できます。このことは、Bツリーにおける検索は対数オーダーの計算量に従うことも意味します。（太字筆者）
この文章では、Bツリーのノード内で二分探索できることがBツリーの検索の計算量オーダーに効いていると読めると思う*1。
しかし、この因果関係の読みは正しくない。なぜならば、Bツリーがもたらす対数オーダーはノード間に構成された完全な木の高さが全要素数の対数に比例することに由来しているからであって、ノード内での探索が二分探索だろうが線型探索であろうが関係は無い。
このことはノードのスプリットやマージを考えると分かりやすいと思う。スプリットやマージではノード内の要素を半分移す必要があるから、それぞれのノードについてノード内の要素数に比例するオーダーの計算量がかかる。
けれども、一回の挿入や削除に伴うスプリットやマージの回数が木の高さ、すなわち全要素数の対数、に抑えられることによってこれらの操作の計算量もまた全要素数の対数オーダーとなるのだ。
おそらく、この文章では強調部分の「ノード内の」というところで筆が滑ってしまったのだと思う。
例えば、
- Bツリーは全体としてソートされている（これは1文目と同じだ）。
- Bツリーはファンアウトが大きいので二分探索ではないが、しかし似たようなやり方で部分木をたどることができる（3文目）。
- その結果として、計算量は対数オーダーとなる（4文目）。
と2文目を無視して読めばその通りだ。もしくは「ノード内の」という部分だけ落としても良いと思う。
それとも普通は引っかからずに正しく読めるものなのだろうか？（純粋な疑問）
Kは何？ (2.3.3 Bツリーの検索の計算量)
曰く、
転送回数の観点から見ると、対数の底はN（ノードごとのキーの数）になります。それぞれの新規レベルにはK 倍のノードがあり、子ポインタをたどるごとに検索範囲は係数N ずつ減少します。検索時には、最大でもlog_K M（この場合のMはBツリー内の項目の総数）のページが、検索対象のキーを検出するために調べられます。また、ルートからリーフへのパスでたどる必要のある子ポインタの数は、レベルの数、言い換えればツリーの高さhとも等しくなります。
このKってNとは違うんですか？定義が分からない…
AとBの間にあるC (3.6 セルのレイアウト)
曰く、
キーセルには、セパレータキーと2 つの隣接するポインタの間にあるページへのポインタが保持されます。
保持されるのは
- セパレータキー
- 2 つの隣接するポインタの間にあるページへのポインタ
の組であって、ページが「セパレータキー」と「～隣接するポインタ」の間にあるわけではない。
すべてのセル (3.6 セルのレイアウト)
曰く、
前提として、ページ内のすべてのセルは均一です。たとえば、すべてのセルがキーのみ、またはキーと値の両方の、いずれかを保持できます。
これは、全てのページにおいて
- （ページ内の）すべてのセルがキーのみを保持している
- （ページ内の）すべてのセルがキーと値の両方を保持している
のいずれかが成立することを意味しているが、「たとえば～」の文だけだとちょっと曖昧。自分だったらどう書くかなあ。
追加ポインタは何？ (3.8 可変長データの管理)
曰く、
局所性を改善するために、特にキーのサイズが小さいときには、一部の実装ではキーと値がリーフレベルで個別に格納されます。キーをまとめて格納したほうが、検索時の局所性を改善できます。検索対象のキーが検出された後で、その値は対応するインデックスを持つ値セルで検出できます。可変長キーでは、これによって、値セルの追加ポインタを計算して格納することが必要になります。
全体的に文章がこなれていないのはおいておいて、「追加ポインタ」とぽんと書かれても良く分からなかった。値セルへのポインタを追加で計算して格納することが必要になる、という意味？
ページが破損してたらどうするんだろう (3.10 チェックサム)
ページごとにチェックサムを計算する手法が紹介されているが、破損を検知したとして実際はどうしているのだろう。
エラーを出力してユーザにバックアップから復旧してもらうのかしら。
対応関係 (4.1.2 兄弟（Sibling）リンク)
曰く、
一部の実装では、前方および後方へのリンク、すなわち、左右の兄弟ページ（同じレベルでとなり合うページ、Siblingリンクとも言う）をポイントするものを格納します。
ここで対応しているのは
- 「前方および後方へのリンク」 = 「Siblingリンク」 = 「左右の兄弟ページをポイントするもの」
- 「左右の兄弟ページ」 = 「同じレベルでとなりあり合うページ」
である。ちなみに、兄弟リンクによって追加のロックが必要になるのにBlinkツリーのような並行性を持つ実装で有効になるという話が逆説的ですごい気になる。早くそこまで読み進めたい。
max_payload_sizeは何？ (4.1.5 オーバーフローページ)
曰く、
大半のBツリーの実装では、そのBツリーのノードに直接格納できるペイロードのバイト数は一定で、それを超えた残りはオーバーフローページに格納されます。この値は、ノードサイズをファンアウトで割って求められます。このアプローチを使用すると、ページに空き領域がなくなるという状況に陥ることがありません。少なくともmax_payload_size のバイトは常に確保されているからです。
max_payload_size = 「ノードサイズをファンアウトで割って求め」た値 = 「Bツリーのノードに直接格納できるペイロードのバイト数」で合ってますか？
また、この文章はノード内の各セルについて少なくともmax_payload_size分の領域が確保されている、と読めば良いですか？
C-ism (4.2 二分探索)
曰く、
二分探索アルゴリズムでは、ソートされた項目の配列と検索対象のキーを受け取り、数値を返します。返された数値が正である場合には、検索対象のキーが検出されたことを示し、入力配列内での検索対象の位置がその数値で指定されます。戻り値が負である場合には、検索対象のキーが入力配列内に存在しないことを示し、挿入位置がその数値で指定されます。
戻り値の正負に意味を込めるのがCっぽいなと思った（感想）。
ユースケースとして独立しているので (4.4 リバランシング)
曰く、
バランシングを行うと、コードが複雑になることがありますが、ユースケースとして独立しているので、最適化の一環として実装できます。
バランシングとユースケースの関係が分からない。バランシングがユースケース（Bツリーへの検索・挿入・削除といった操作のインターフェース）から独立しているということ？
例えば"Balancing can make the code complex, but it can be implemented as an optimization since it is independent of the use case."みたいな。
今後は読みながら更新していくつもり。
*1:自分は最初そう読んだ
