近況 2020-01-31

 2020年1月31日 投稿 日記

今月の活動について (CPS 中間表現、静的契約、HSP3 フォージェリ、競プロなど)

CPS 中間表現

https://github.com/vain0x/languages/tree/fc3998a/phancie-lang

“Compiling with Continuations” を読みつつ CPS を中間表現とする処理系を書いている。雰囲気は分かってきた。

上の実装に使った F# だけでなく、Rust でも CPS 変換をやろうと試みて、その結果のコードが以下にある。

https://github.com/vain0x/hsp3-ginger/blob/7a0e4a5ed311320ca76fb6bae261901e57a6956b/hsp3-forgery/hf_core/src/kir/gen.rs

所有権の関係で Rust はクロージャの取り回しが難しく、よくあるクロージャを使う CPS 変換は煩雑になりそうだった。そこで、スタックマシン向けのコードを生成して逆向きに解釈することで組み立てようとした。

結局、このプロジェクトにはまだ CPS 中間表現は不要と気づいたので、小さいケースしか試せていない。実はうまくいかないケースがあるかもしれない。

ファントムシステム

昨年の振り返りと次の自作言語に関して、以下の記事を投稿した。

ミローネ言語コンパイラ・HSP3開発ツール群の振り返りと今後の構想

自作言語に持たせたい機能の1つとして 静的契約システム がある。

先行研究の調査が不足しているし実装もできていないので詳述する段階ではないかもしれない点には注意。

静的契約システムは、関数の事前条件を静的に検査し、関数の事後条件を後続の条件検査に活用するというもの。

例えば「is_valid() メソッドが true を返したのを確認した後に execute() メソッドを呼ぶこと」といった利用規約がしばしばある。これは一般的に好ましくない設計とされている。

より良いアプローチは次のように型システムを使うものである。

  • is_valid を持つオブジェクト Foo と、execute を持つオブジェクト ValidatedFoo を別の型にしておく
  • is_valid が Option<ValidatedFoo> を返すようにする

こうすると execute の前に必ず is_valid を呼んで返り値を検査することが必須 になる。

実際のケースではこのアプローチで OK。

とはいえ理想をいうと、Option や ValidatedFoo をスタック上に確保できないケースでオーバーヘッドが生じる点が気になるし、型を分けることで問題を解決すると型がどんどん増えていくし、そのたびにフィールドの値を受け渡すだけのコードを書く必要があって煩わしい。

そこで、TypeScript などが持つスマートキャストを参考に、以下のような仕組みを考える。最終的には is_valid の返り値が true だと分かっているコードパスにおいてだけメソッド execute の呼び出しが型検査を通るようにしたい。

変数の呼べるメソッドが途中で変わるということは、言い換えると 変数の型が途中で変わる ということ。しかしオブジェクトのメモリレイアウトを動的に変えるわけにはいかない。そのため、ここで変わっている型というのは、 オブジェクトのメモリレイアウトに影響していない型 でなければいけない。

オブジェクトのメモリレイアウトに影響していない型検査のためだけの型を、ここでは仮に ファントム と呼ぶ。

例えばポインタ型 T* は、型 T に関係なく、実行時には特定のビット長の数値 size_t に等しい。ポインタであるという型情報は型検査等にのみ使われていて、メモリレイアウトに影響していない。そのためポインタはファントムとみなせる。

上の例でいえば、メソッド execute を持つ型を Execute という名前のファントムとして定めておく。(構文は適当。)

phantom Execute: Foo;

impl Execute {
    fn execute(&self) {}
}

is_valid の事後条件として、返り値が true なら Execute ファントムを得る、と書いておく。

impl Foo {
    fn is_valid(&self) -> bool
        ensures(result) {
            result => self as Execute
        }
    {
        false
    }
}

後は foo.is_valid() の返り値 (result) が true のときスマートキャスト self as Execute が走って foo: Execute という型がつき、execute が呼べる。

    // foo.execute() はここでは呼べない。

    if foo.is_valid() {
        foo.execute(); // ここでは呼べる。(is_valid の事後条件のため)
    }

ふるい型 (refinement type) に似ているが、型自体が条件を持つのではなく、ファントムでは条件を満たした結果として型を得る。(もしかしたらこれもふるい型の一種に含まれるかもしれないが……) 加えて、ファントムはオブジェクトの可変性を前提としている。

問題はまさにその可変性との兼ね合いで、例えば is_valid の返り値を確かめた後にオブジェクトの状態を変更すると、is_valid = false になる可能性がありるため、ファントム Execute を持ったままにするべきではない。

    if foo.is_valid() {
        modify(&mut foo);
        foo.execute(); // foo.is_valid() == true とはいえない
    }

「可変操作の後では is_valid の事後条件が崩れた可能性があるから Execute を失う」と保守的に判断してしまうと、事後条件を使える場面が大幅に制限される。可変操作が is_valid を false にするかどうかを指定する、煩雑ではない手法が必要になる。

難しそうなので、一旦ここまで。いちおうメモにまとめてある。

https://github.com/vain0x/languages/blob/061a4d5/phancie-lang/memo.md

HSP3 フォージェリ

https://github.com/vain0x/hsp3-ginger/tree/5929d789824f8293f7940f07515997fb0fda6126/hsp3-forgery

静的型検査されないコードを書くのはつらみがあり、HSP3 で書いている knowbug クライアントの実装もややつらみがある。書くのは楽しいけど、読み返す、追う、直すのが難しい。

そういうわけで HSP3 の型検査ツールを作ろうとしている。せっかくなので、以前作った雑な LSP を置き換えるために、LSP として動くようにしたい。

そのためにいまは構文解析器を作っている。進捗はまだまだ。

競プロ

週末は AtCoder に参加。

F# の LSP 型定義の作成

https://github.com/vain0x/fsharp-language-toolkit

F# の LSP/DAP の型定義の作成を進めている。主にゲームの待ち時間にやっているので進捗は芳しくないが、いつかは終わるはず。

自作言語の一覧

https://github.com/vain0x/languages

自作言語の一覧用のリポジトリを作った。中途半端に打ち捨てられてるコードも放り込んでおいた。

その他

自分の発信で気になった部分。

他の人の発信で気になった部分。

関連記事