近況 2019-06-30

今月の活動について

前月分 https://vain0x.github.io/blog/2019-05-31/diary/

ミローネ言語

https://github.com/vain0x/milone-lang

F# のサブセットで書かれた、セルフホスティングを目指しているコンパイラ
Hindley-Milner 型推論の理解に誤りがあって、型推論器にバグがあった

knowbug

スクリプト言語 HSP3 のデバッガ

https://github.com/vain0x/knowbug

HSP/knowbug とは:

Hot Soup Processor (HSP) というスクリプト言語がある
- Windows やスマートフォン向けの GUI アプリが簡単に作れるということで人気がある
デバッガーがある
- 主に実行中に変数の値を表示したり、ステップ実行の操作をしたりする機能を持つ
デバッガーは「特定のインターフェイスを満たす関数を公開する DLL」なので、これを差し替えれば別のデバッガーに切り替えられる
2008 年ぐらいに公式のデバッガーからフォークして、さまざまな機能を追加したのが knowbug
- 最終リリース (v1.22.1) は 2015 年

問題:

文字列エンコーディングの問題がある
HSP は少なくとも2003年ぐらいから存在する古参言語で、UTF-8 ではなく shift_jis (cp932) をベースにしている
UTF-8 版のランタイムもリリースされたが、knowbug は shift_jis 版しかサポートしていない
機能改善の要望もたまに受けていた
コードベースに手を加えるのが難しく、対応できていなかった
特に、変数の値を表示するために文字列を構築する部分と、変数の値をメモリから読み取る部分が結合していたのがつらかった
変数のデータをメモリから読み取るのは、HSP ランタイム側の挙動を知っていないといけない部分が多くて、修正難度が高い
GUI の中に計算やデータが埋め込まれている部分も少なくなかった

作業:

ちまちまリファクタリングを進めた
処理から特定の仕事をクラスや関数に切り離したり
グローバル変数を使うのではなく引数からオブジェクトを受けるようにしたり
誰も使ってなさそうな機能の削除したり

文字列エンコーディング問題:

文字列を char* や string ではなく、エンコーディングごとに異なる型を使うことで混在を防ぐ
Utf8String とか HspString とか
エンコーディング変換を行う関数で型変換を行う
型検査が通ればエンコーディングを正常に変換できているとみなせる

パスAPI:

HSP ランタイムからもらえるオブジェクトをポインタで直接持つと問題がある
- そのオブジェクトが有効かどうか判定できない
- そのオブジェクトのどの部分に情報があるか分かりにくい
- モック化が難しくて、テストできない
「HSP のオブジェクトを指す経路」(オブジェクトパス)を考える
- すべての生存しているオブジェクトにはグローバルからの経路がある
- 例えば「モジュール @foo の配列変数 bar の要素 (1) の値」という感じ
オブジェクトパスを指定して「このオブジェクトに関して、何らかの情報をください」という形式でデータを取得する、という設計に変更した
- 経路を遡ることで、オブジェクトの生存判定を確実に行える
- 情報の取り方を knowbug 側の都合に合わせて設計できる
- 情報を取得する部分と加工する部分が自然に切り離せる
テストもしやすいはず
- HSP ランタイム側のデータは必ずインターフェイス越しに取得されるので、このインターフェイスのテストダブルを作れば HSP ランタイムがなくても knowbug 側のコードを動かせるはず
- まだテストは書いていない
課題もある
- パスの一部である必要がないオブジェクトがけっこうある
  - 「実行位置に対応するスクリプトファイル」とか
- オブジェクトを指定する際に必ずパスを使うのではなく、オブジェクトを指し示すもの (例えば「グローバル変数 (i 番目)」とか) を別に用意して、それをパスの上に配置するというのもありえる
- リファクタリングというよりリライトになってしまった
GoF のデザインパターンの Mediator に近いかもしれない

進捗:

余暇の大半を費やしたおかげで、必要な機能はおおよそ揃った
動作確認がいまいち
上述の通りテストも書きたい

競技プログラミング

週末は AtCoder に参加した。新体制 ABC では安定して E 完を取れていてよい。

その他: Web アプリの開発環境整備

Docker-Compose を使って Web アプリの開発環境を構築できるようにした

開発環境とステージング環境・本番環境で設定が違う (例えばデータベースの名前を分けたい) が、どうすればいいのか迷った
とりあえず docker-compose の設定ファイルを分割して docker-compose -f docker-base.yml -f docker-dev.yml のようなコマンド (のエイリアス) を使う方針にした
Docker 環境内で jest がなぜか動作しなかったので ava に変更した

その他: de Bruijn インデックス

TaPL の実装を読むと、変数の表現に de Bruijn インデックスが使われていてよく分からないので、de Bruijn インデックスの説明の部分を改めて読んだ。分かった気がするので、その内容をここでまとめる。

抽象構文木の上にカーソルを置くと考えると分かりやすい気がする。いま見ているノードより上で束縛される (あるいはどこにも束縛されない) 変数を自由変数である。例えば以下の項を考える。

    \x. \y. (\f. f x) x

どこでもいいが一例として \f. f x の部分に注目しているとする。このとき上で束縛されている x, y は (いま注目している項の視点では) 自由変数である。

自由変数には順番がある。抽象構文木を下から上に向かって辿るときに、束縛に遭遇する順番で並んでいるとみなす。上の例では [y, x] という配列。これを 名前付け文脈 という。

ある変数の出現の de Bruijn インデックスは、その項の名前付け文脈において、その変数が何番目であるかを表している。

形式的な表現ではないが、これで de Bruijn インデックスを定められていると思う。

上の例の \f. f x の内側にある f の de Bruijn インデックスを考える。この項から上に辿ると束縛 f, y, x がこの順で見つかるので、これが名前付け文脈である。f は 0 番目に出現するので、de Bruijn インデックスは 0 である。

x についても同様で、名前付け文脈は同じく f, y, x なので、de Bruijn インデックスは 2 である。

最後にもう1つの例として、1段階外側に出現する x を考える。

    \x. \y. (\f. f x) x
                      ^

これを上に辿ると y, x なので、de Bruijn インデックスは 1 になる。

名前付け文脈の計算は、木を下方向に巡回するとき (DFS でも BFS でも可)、束縛の内側に入るたびに名前付け文脈を伸ばし、出るたびに削る、という操作をすればいい。リストと相性がいい。

その他: クロージャと存在型

TaPL を読んでいたら存在型を使ってクロージャをデコードできるような気がしてきた。

クロージャのある言語で以下のように書いたとする。

    let n = 2
    let inc x = x + n
    let f = inc
    f 3 //=> 5

これをクロージャのない言語に変換したいとする。

クロージャのインターフェイスは「環境」(キャプチャされた値の集合)と「関数」の2つ。環境の型を存在型で隠蔽すればいい。

    let n = 2
    let inc env x = = x + env.n

    let f =
        // 型 X = {n: Nat} を隠蔽する存在型のインスタンス
        {*{n: Nat}, {env = {n = n}, fun = inc}}
        as ∃X, {env: X, fun: X -> Nat -> Nat}}

    // クロージャを呼ぶ
    let {X, {env, fun}} = f
    fun env 3 //=> 5