近況 2020-11-30

今月の活動 (ミローネ言語など)

前回 (2020-10-31) https://vain0x.github.io/blog/2020-10-31/diary/

ミローネ言語

動的リージョンベースのメモリ管理の先行研究を探しているが、みつからない (lexical なリージョンや purely functional でない言語の話が多い)
メモリ確保をいちいち calloc するのではなく、適当に実装したメモリプールから取るようにしたら2倍ぐらい速くなってビビった
- メモリプールの実装がほしくて GitHub 等を探したけど、よいのがみつからなかった。探すのは苦手
(単相な) レコード型を実装した
- 型推論と相性が悪いが、とりあえずレコードの型が必要になった時点で推論できていなかったらエラーにしている
- さすがにこれだと F# で通るコードが型エラーになってしまうことが少なくないので、もう少し考える必要がある
- はじめはレコードをタプルに変換する実装だったが、レコードは再帰的になれるのでダメだった (R = { A: R list, B: int } とか)
セルフコンパイルのために、レコードを判別共用体で代用したり (R = { A: int; B: string } → R of int * string とか)、標準の List モジュールを使わないようにしたり (List.map → listMap とか) といった細工をしていたが、そういったコードもコンパイルできるようになってきたので元に戻した
- まるで普通の言語みたいにみえてきた

型シノニムと組み込みの多相型だけを使って多相な再帰型を模倣するトリック

多相な型シノニムを実装して、現実的な手間で多相な木構造を作れるようになった。多相な名前付き型がないので再帰的な構造はジェネリックにできないが、多相な部分を obj 型に押し込むことで、少なくとも API は safe な木構造を作れるようになった。

(任意の値を obj 型に変換する box: 'T -> obj という関数と、それを復元する unbox: obj -> 'T という関数がある。.NET では unbox の際に動的検査されるので安全だが、ミローネ言語の現在の実装では undefined behavior になってしまう。)

// TreeMap.fs

// 単相な判別共用体なので定義できる。キーと値は obj に詰める
type TreeMapRawNode =
  | E
  | T of TreeMapColor * left: TreeMapRawNode * keyValuePair: obj * right: TreeMapRawNode

// 多相な型シノニムを公開しておく。option は単に型変数を維持するためのもので、実際は常に None.
type TreeMap<'K, 'T> = TreeMapRawNode * ('K -> 'K -> int) * ('T option)

ツリーを操作する関数が呼ばれるとき、キーと値の型も同時に渡されるので、それを元に obj を剥がしたり包んだりする。普通に書くと関数の呼び出しの前後で型が変わってしまうので、強制的に単一化するためのデッドコードを仕込んでおくというハックがいる。

let tryFind key (map: TreeMap<_, _>): _ option =
  let node, keyCmp, none = map
  //                ^ これは 'T option 型で、値の型を知っている

  let valueOpt = node |> doTryFind keyCmp key
  //  ^ この値は unbox で得るので、任意の型をつけられてしまう

  let _typeUnifier () = [ valueOpt; none ] |> ignore
  //                      ^         ^
  //                ここで適切な値の型に固定している

  valueOpt

変数や型の ID から実データへのマップを、従来の「500 要素ごとに分割した連想リスト」を赤黒木に置き換えたところ、型検査が4倍ぐらい速くなった。平衡二分探索は速い、というか連想リストが遅い。

現時点の TreeMap の実装

パターンマッチのコンパイルの改善 (一時中断)

パターンマッチのコンパイルを改善しようとしていたが、うまくいっていない。

WIP: https://github.com/vain0x/milone-lang/compare/fb7b652...f22d0a2

いまは一番上の節 (| pat -> body の部分) から順番にマッチするか試して、マッチしなかったら次の節のパターンマッチを行う部分に goto で飛ぶ、というコードになっている。当然ながら効率はよくない。また、goto を使う必要があるので、手続き的な中間表現 (MIR) の上で実装されている。

理想的には、判別共用体のタグの値に関して switch するなどの方法で、節を効率的に絞りこむコードに変換したい。MIR への変換が複雑化するのを避けたいので、関数型の中間表現 (HIR) の上で実装したい。

この記事を参考にやっていくことにした。

方針としては、match 式を完全に消去するのではなく、「完全体のパターンマッチ」を「シンプルなパターンマッチの組み合わせ」に変換する。手続き的な中間表現やターゲット言語(C)に落とす際に、「シンプルなパターンマッチ」を switch などに展開する。シンプルなパターンマッチとは、ようするに switch と同じで、1個の整数に関して分岐するだけのものということにする。束縛やガード節、入れ子のパターンは持たないものとする。

パターンマッチの展開自体はおおむねできつつあるが、課題がある。シンプルなパターンマッチの組み合わせに変換すると、結果として節本体 (-> の後ろ) への入り口が2つ以上に増えてしまうことがある。節本体を2つのコピーするわけにはいかないので、2つ以上の入り口を持つ節本体は事前に関数に分けておいて、関数呼び出しを埋め込むようにするのがよい。

ただし節本体の関数への括り出しをしてしまうと、ミローネ言語の末尾再帰最適化が無効になってしまう。(C言語のコードを生成するという方針の都合上、関数の境界を越えるような末尾呼び出しの最適化は難しい。) GCC が末尾呼び出し最適化をしなかったら、スタックオーバーフローを引き起こしてしまう。(実際、長いリストをソートするときに起こる。)

おそらく HIR の上に関数とは別に、関数のようでありながら、C言語に落とすときは関数ではなくラベルになる、というようなもの (いわゆる合流点) を用意することで、合流点の内部から関数自身への呼び出しを末尾再帰最適化の対象にする、という作業がいりそう…… (続く?)

FFI

ミローネ言語で現実的なコードを何か書くために、特にミローネ言語の LSP サーバーをミローネ言語自身で書けたらと思って、C FFI を考えている。

とりあえず nativeptr とか uint64 とか float は用意した。

バイトストリームの読み書きは最低限必須っぽいが、オブジェクトの変更を絶対禁止する方針と衝突する。動的リージョンベースのメモリ管理のために禁止するだけなら、整数などのポインタを含まないデータの配列は変更できても問題ないが、その方向で緩和してもよいかもしれない。

あるいは、表面上はバッファーを非破壊更新するようなコードを書きつつ、内部的にはバッファーが再利用されていて、その再利用が観測されるような操作は実行時エラーで弾く、みたいな方針もありうる。

また、線形型があるとよいらしい(？)という記事が最近流れてきた: Tweag - Pure destination-passing style in Linear Haskell

NoEquality; NoComparison

milone-lang のほとんどの型に NoEquality; NoComparison 属性をつけた。

判別共用体やレコードにこれらの属性をつけると、(=) などの比較演算のためのコードが生成されなくなる。これでバイナリが 400KB ぐらい縮んで、ビルド時間も少し短くなった。

Char.(+)

F# の char 型 (UTF-16 code unit) は (-) 演算子をサポートしていなくて、c - 'A' とか書けない。同様に (*) や (/) もないが、なぜか c + 'A' は通って謎

ミローネ言語

型シノニムと組み込みの多相型だけを使って多相な再帰型を模倣するトリック

パターンマッチのコンパイルの改善 (一時中断)

FFI

NoEquality; NoComparison

Char.(+)

関連記事