近況 2021-02-28

今月の活動 (ミローネ言語、DAPサンプル実装を作った、など)

ミローネ言語

ビルドやテストを待つ時間が気になってきたので、ビルドチェインを直した
- ninja のビルドスクリプトを直して処理を減らしたりした。生成されたCのコードが一字一句同じだったらGCCを起動しないとか (restat)
- テストを別のディレクトリで行うことで、テスト中にソースコードを変更しても壊れないようにとか
最適化を増やした

(リリース……)

次のように1つのバリアントしか持たない判別共用体は newtype と呼ばれている。

type UserId = UserId of int

UserId を他の整数と型レベルで区別することで誤りを防げる。逆にいうと型検査が終わったら UserId と int を区別する理由はない。そのため UserId を使っている部分を int を使うように変換してしまっていい。

    let (UserId n) = UserId 1
// =>
    let n = 1

これにより値を包んで剥がす無駄な操作を省略できる。さらに単相化において K<UserId> と K<int> の2つに分かれなくなるので嬉しい。

実際、ミローネ言語のコンパイラでもこの種の newtype をいくつか使っている。例えば変数の識別子と関数の識別子を分けている。そのせいでマップの実装が多く複製されていた。この最適化を導入したことで、セルフコンパイルで生成されるCのコードが1万行ぐらい減った。

注意点が一つあって、再帰的に使われている newtype は剥がせない。例えば次の Ty 型は newtype だが、再帰的なので剥がすことはできない。

    // 型は型コンストラクタと型引数のペア
    type Ty = Ty of Tk * Ty list

相互再帰の可能性もある。再帰性の判定は閉路検出 (深さ優先探索) のアルゴリズムを使った。それぞれの型定義から出発して、再帰的にそれが含んでいる他の型を訪問していく。処理中の型定義に到達したら、その型は再帰的に使われている。到達しなかったら再帰的に使われていない (剥がせる)。

デバッガの実装を言語側と開発ツール (エディタ) 側で分離するためにDAPというプロトコルがある。 LSPのデバッガ版のようなもの。

日本語の情報が少ない気がしたので、サンプル実装を作った。とはいえ実装だけみても分かりやすくはないから、後で記事も書く予定。

どの場所で公開するか迷っていた。おそらくこのブログに書く。