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文が実現できる:

  1. defer文のブロックを0引数関数としてコンパイルする
  2. その関数で初期化される特別な無名のローカル変数を追加する
  3. このローカル変数がスコープから抜ける際、スタックからポップする代わりに関数を呼び出す

疑似コードで書くと次の通り:

{
    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:原著ではイラストも含めて分かりやすく説明されているからぜひ読もう。自分には絵心が無かった…

日本人優遇とその裏

こういうのとか

こういうのは日本語圏のツイッターエンジニア界隈では概ねいい話*1として受容されているようだ。
しかし、こういった日本人への優遇への裏側には(相対的にしろ)そのほかの人々への冷遇が存在している。
そして、この取り扱いの差は「日本人は金払いが良い」といった先入観に基づいている*2

衣食住とも言われるとおり、住居は人間の生活において重要なファクターの一つである。
居住の自由は広く認められている人権の一つであり*3、また通勤や教育へのアクセス(学区)、その他公共サービスなど幅広い形で生活に関わっている。
それにもかかわらず、上に挙げたような国籍・人種に基づく先入観によって生じる取り扱いの差は不当であり、差別の一例であると私は考える。
さらに、たとえ「日本人は金払いが良い」といった先入観が正しかったとしても、やはりこの取り扱いの差は統計的差別としての問題を含んでいるだろう。

海外だけでなく、日本でも住居の差別は生じている。
例えば、2017年に発表された外国人住民調査では、住居を5年以内に探したことのある外国人のうち約4割の方が「外国人であることを理由に入居を断られ」たり、「日本人の保証人がいないことを理由に入居を断られ」たりしたことがあると述べている。
また、これらの人々の中には「日本人と同程度に会話できる」にもかかわらず断られている人も含まれており、日本に在留する外国人に対する差別が起きているのは間違いない。

もちろん、先入観に基づく判断が常に悪いというわけではない。
例えば、初めて会った人が「金」と名乗ったとき、「韓国人なのかな」「韓国人であるなら韓国語を話せるだろう」といった先入観は多くのケースで正しく、そこから「アニョハセヨ」と挨拶するのは良い歓迎かもしれない。
けれども、大坂なおみさんのような例外は存在している。
また、アメリカやヨーロッパにおけるアジア人に対する差別の文脈を考慮したならば、ツイートの例はそこまで悪いわけではないのかもしれない*4

けれども、これらの日本人優遇は差別的取り扱いと密接に繋がっており、あまり無邪気に喜んでほしくないと思うのだ。

*1:特別な含意は無い

*2:この記事では「取り扱いの差」や「先入観」という語は価値中立的に扱う。また、「先入観」の正誤は問わない。(私による)倫理的非難が込められた語として「差別」や「偏見」を用いる。

*3:例えば、日本弁護士連合会:市民的及び政治的権利に関する国際規約(自由権規約) 条約本文の12条

*4:名誉白人というケースもあるけれど

でっどろっきんぐ・もーにんぐるーてぃん

私は毎朝洗顔を済ませてから着替えることにしている。洗顔時に上着がびしょびしょになってしまうからだ。
今朝は健康も考えて着替えた後に散歩に出かけてみたのだが、不都合な真実に気づいてしまった。
洗顔後に散歩をすると保湿クリームがマスクにくっついて不愉快なのだ!

つまり、我がモーニングルーティンには次の3つの依存関係が存在することとなる。

  1. 洗顔→着替え: 上着が濡れる
  2. 着替え→散歩: 外出着を着ておきたい
  3. 散歩→洗顔(保湿): クリームがマスクでべとべとする

古典的なデッドロックだ。助けてくれ

nitpick 『詳説データベース』

CRDTなデータベースをon-diskで実装してえ…という思いが高まってきたので購入。ストレージエンジンと分散システムというトピックはどっちも興味があるのですごい嬉しいしオライリーだからDRMフリーPDFなのも素晴らしい。
ただ、読んでて筆が滑ったのか自分の読み方が良くないだけなのか不明なところがちょくちょくあるのでメモしたいと思う。ただ、この記事はnitpickであって内容の良しあしとは関係ないのでそこは注意すること。
「ここはこういう意味だよ!」とか「普通に読めるよ!」とかコメントいただけると幸いです。

Bツリーの本質はノード内の二分探索ではない (2.3 ユビキタスBツリー)

曰く、

Bツリーはソートされています。つまり、Bツリーのノード内のキーは、順番に格納されています。それゆえに、検索対象のキーを探すために二分探索のようなアルゴリズムが使用できます。このことは、Bツリーにおける検索は対数オーダーの計算量に従うことも意味します。(太字筆者)

この文章では、Bツリーのノード内で二分探索できることがBツリーの検索の計算量オーダーに効いていると読めると思う*1
しかし、この因果関係の読みは正しくない。なぜならば、Bツリーがもたらす対数オーダーはノード間に構成された完全な木の高さが全要素数の対数に比例することに由来しているからであって、ノード内での探索が二分探索だろうが線型探索であろうが関係は無い。
このことはノードのスプリットやマージを考えると分かりやすいと思う。スプリットやマージではノード内の要素を半分移す必要があるから、それぞれのノードについてノード内の要素数に比例するオーダーの計算量がかかる。
けれども、一回の挿入や削除に伴うスプリットやマージの回数が木の高さ、すなわち全要素数の対数、に抑えられることによってこれらの操作の計算量もまた全要素数の対数オーダーとなるのだ。

おそらく、この文章では強調部分の「ノード内の」というところで筆が滑ってしまったのだと思う。
例えば、

  1. Bツリーは全体としてソートされている(これは1文目と同じだ)。
  2. Bツリーはファンアウトが大きいので二分探索ではないが、しかし似たようなやり方で部分木をたどることができる(3文目)。
  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:自分は最初そう読んだ

『人間失格』

センチメンタルな日々を過ごしており、折角の機会*1だからと『人間失格』を手に取ってみた。
1日もかからずに読める長さなのもうれしい。

主人公と自分に重なる部分を見つけて涙するところもあり*2、主人公の性遍歴・それを支える容姿や機知の部分には距離を覚えるところもあった。
結構身の入った読書体験ではあったと思う。タイミングの妙だろう。

ただ、しかし、「失格」の内容がそれか…という点で最後に拍子抜けしてしまった。
まあ、精神病に対するイメージの変化も大きいのだろう。

*1:BOOK WALKERのコインも余っているし

*2:うまくいかなさの原因が自分のたちの悪さにあってどうしようもなくなってしまうところなんかがそうだ。周囲を蔑視しているところも呆れるやら身につまされるやら。

平井デジタル相は脱PPAPで電話でのパスワード別送を推奨したのか?

要約: していない.記者会見の主眼はPPAP(自動暗号化ZIPファイル)の廃止であり,パスワード別送は限定的な状況を念頭に置いていると思われる(機密性の高い情報).特に電話は別経路の一例に過ぎない.

次のツイートが話題になったことは記憶に新しいでしょう.


このツイートは11月24日に平井デジタル相が開いた記者会見の記事の紹介ツイートですが,「パスワードを電話で教える」という点で急速に拡散しました.
当日の記者会見の書き起こしが内閣府のページにアップロードされたので,この記事ではデジタル相の具体的な発言を見ていきます.

内閣府の対応

記者会見の初めに,デジタル相は次のように述べています(強調引用者).

まず私から、自動暗号化ZIPファイルの廃止について報告します。以前お話ししたとおり、アイデアボックスで投票数が第1位であった自動暗号化ZIPファイルの廃止については、先週17日の会見で、内閣府内閣官房で廃止する方向で検討を進めているとお話ししましたが、明後日26日に廃止をする予定ということになりました。明後日からということですね。内閣府内閣官房で採用していたZIPファイル送付と同じ経路でパスワードを自動で送る方式は、セキュリティ対策の観点からも、受け取る側の利便性の観点からも、適切なものではないと考えています
 一方で、個人情報等の気密性(引用注: 機密性の誤字)の高い情報を含むファイルを送信する際には、例えばファイルにパスワードをかけるとともに、全く別の経路でパスワードを知らせるということが、まずは適切な対応ではなかったのかと思います
 他省庁の状況についても、NISCと連携しながら実態調査を進めており、その結果を踏まえて、ZIPファイル送信、送付と同じ経路でパスワードを自動で送る方式については廃止するということを促したいと思っています。
 このような取組は、政府内だけでなく、民間にも影響のあるものと考えておりまして、民間企業の対応なども注視しつつ、今後どのようなセキュリティ向上策をとっていくことが望ましいのか、これも実際にいろんなところで仕事をされている民間の方々に、イデアボックスの中にでもまたアイデアを送っていただきたいと思います
 このような例は利用者目線でデジタル改革を進める、そして国民の利便性を実現していくという意味では重要ではないかと思っています。ZIPファイルは以上です。

つまり,まず内閣府ではメールの添付ファイルを自動的に暗号化ZIPしてパスワードを同じ経路で伝送するシステムが運用されており,それの利用を取りやめるということが記者会見の主要なメッセージであることが分かります.
そして別経路を用いてパスワードを伝送するのは機密性が高い情報(個人情報等でしょう)を送信する場合の方法の一つとして挙げられています.まだ電話の話は出ていません←ここ大事.
また,より望ましい方法を模索している段階であることが伺えます.

では,電話でパスワードを送るという話はどこで出てきたのでしょうか.それは会見後の質疑応答のタイミングです.

(問)冒頭にあったZIPファイルについてお尋ねしたいと思います。26日から廃止ということですけれども、26日以降内閣府内閣官房からはどういった形式でファイルの送信をされるのでしょうか。
(答)それはまだ決まっていません(引用者注: 今は決まっているのでこの記事も最後まで読むこと)。いろんなやり方を考えなければいけないと思うんですけれども、セキュリティ上、今のZIPファイル、その運用というのは非常にまずいと思います。かえって危険性が高いと思っているので、そこはこれから検討するということですし、お話ししたとおり、実際いろんなファイルのやりとりを民間の方々も頻繁にやっておられますので、民間の方々の知恵も是非投稿していただければありがたいと考えています。

(問)やり方が決まるまで、暫定的にパスワードとかを付けずに送るということになるんですか。
(答)それは、パスワードを送るとしても、要するに今は同じルートで送っていましたよね。さっきお話ししたとおり、それは絶対にやってはだめと。ですから電話で教えるとか、そういうことにならざるを得ないんじゃないですか。

(問)それか、メールで送るとしても、別のメールとかアドレスとか。
(答)御社は専門家なので、是非アドバイスをください

というわけで,電話はパスワードを送る必要がある場合の方法の一つとして挙げられているのにすぎず,例えば大部分をパスワード暗号化 + 電話によるパスワード伝送に移行するという話ではないのだと分かります.
実際,ITMediaの記事によると内閣府は自身の運用するストレージサービスを主に用いるようです.

 内閣府情報化推進室によると、今後は外部へのファイル送信には内閣府のストレージサービスを活用し、ファイルを共有する。外部の事業者などには内閣府のシステムにアクセスするためのURLとログインパスワードを発行。URLやパスワードは1回限りの使い捨てになるという。

 一方、内閣府のシステムにアクセスできない事業者に対しては、メールでファイルを送信するが、プロジェクトの立ち上げ時に決めたパスワードを利用して開封してもらう。単品ファイルの場合は、WordやExcelなどの暗号化機能を使い、複数のファイルを送信する際はZIPファイルでまとめて暗号化する。単発事業の受注者に対しては、例外的な運用として電話などでパスワードを共有するという。

ストレージサービスにアクセスできない事業者*1では暗号化パスワードを別経路で最初に伝えておくという方式とのことです.
あくまでもこれは例外的なケースではないでしょうか.面倒なセキュリティは回避されがち(そして元よりも残念になってしまうもの)なので,パスワード別送が常態化しないようにうまくやってほしいものです.

民間への波及

内閣府の決定は民間にも波及しているようです.うーん残念.
どのような方法を採用するのが良いのかは以下の記事が参考になりました.ぜひご覧ください.
zenn.dev

以降ではセキュリティ対策よりもなぜ皆さんの心の中に「パスワードの電話伝送が使われていくのだ」という信念が宿るようになったのかを少し考えます.

ツイッターの反応

11月24日から「電話 パスワード」という語を含むツイートかつRTが50以上のものをを検索しました.いくつか取り上げてカテゴリ分けします.

メディア

特に産経新聞のツイートが一番最初に来たものであることから,「電話パスワード」の拡散に大きな役割を果たしたように思われます*2
メディアを批判したくなった人には「〇〇はクソ」って言うけれど… - 井山梃子歴史館をどうぞ.

まとめサイト

インターネットアルファ(疑念系)

インターネットアルファ(大喜利系)

「電話パスワード」報道への批判

これらの感想ツイートや上で挙げた電話パスワード採用ツイートから分かるように「電話でパスワードを送るようにするべきだと国は考えている」という信念はある程度広まっているようです.
自分はそんなことないんじゃないかなあと思いますが(実際内閣府もストレージサービスがメインのようです),人間はニュースを読まずにリツイートしてしまう存在なので難しいですね.
幸いにして,インターネットのおかげで一般人でも一次情報にアクセスしやすくなっています.例えば記事冒頭の記者会見要旨へのリンクに飛ぶのは一瞬ですし,平井デジタル相は自身のYouTubeチャンネルにも動画をアップロードしています.
www.youtube.com

表面的な情報に対して瞬発的にいっちょ噛みするのはなかなか楽しいのも分かりますが,具体的に起こったことやニュアンスを確認してみるのも健全だと思います.
例えば

  1. いったん(1-2週間)放置して落ち着いてから続報や公式発表を探してみる*3
  2. (まともな)本を探して読んでみる.教科書が良いですよ
  3. センセーショナルでないやり方で議論・発言してみる*4

ということを自分は心掛けるようにしています.皆さんもぜひ.

*1:これがどういうものなのかが自分はよくわかりません.事業者側で対応できていないということでしょうか?

*2:一応「暫定的」とは書いてありますが

*3:でも内閣府の書き起こしはもう少し早く出てほしい…

*4:皆さんのコメントもお待ちしています