近況 2019-08-31

今月の活動について (ミローネ言語, 競プロ)

ミローネ言語

F# サブセットのコンパイラ

ミローネ言語の字句解析器をミローネ言語自身でコンパイルしてみた。

次は構文解析器もコンパイルしようとしてる。

単相化の設計的なバグが見つかったので直した (後述)
生成されるC言語の型定義(struct)に問題がある
- 判別共用体がリストやタプルを介して相互再帰してると同じ型定義が複数生成されてしまう
- 型定義の生成部分がやっつけすぎるせい

テストケースとエラーハンドリングが足りていないことが分かってきた。

多相関数の中に関数があると単相化でコードが壊れるバグがあった。例:

let id x =
    let aux () = x
    aux ()

assert (id 1 = 1)
assert (id "a" = "a")

これを単相化すると多相関数 id が2つに複製される。内部にある関数 aux のコピーが2つできてしまう。

let id_int x =
    let aux () = x
    aux ()

let id_str x =
    let aux () = x
    aux ()

assert (id_int 1 = 1)
assert (id_str "a" = "a")

解決策はいろいろあるが、クロージャ変換後に aux を外に移動する方法がある。

// クロージャ変換後

let aux x () = x        // 引数 x はクロージャ変換で追加された
let id x = aux x ()

前回の近況記事や上に書いたlet深度の関係で、aux は多相関数でない。そのため aux は自由な型変数を含む。そのような型変数は aux によって導入するとみなせる。つまり、aux を generalize していい。それで壊れるようなケースは型推論時にエラーとして弾かれているため。

2018-08-19 に投稿した最初の競プロ参戦記から1年たった。当時のレートは 1547 (水)、いまは 1799 (青, +252)。