Blog 2023‐08‐13 - qnighy/umo GitHub Wiki

近況

ミニマルなVMができたので、ASTからVMへのloweringを実装中。

今後の予定

  • branch, loop のloweringを同様に実装
  • パーサーを実装
  • function pointer type を定義してクロージャー(capturing無し)を実装
  • クロージャーのcapturingを実装
  • 原始的なモジュールシステムを実装
  • 原始的なユニットテストを実装

インタプリタV1の設計について

Umoのパフォーマンスに関するポリシーは以下の通り:

  • 最終的にSafe Rustと同等の最適化ができるように、最適化を阻害する要因をあらかじめ排除しておく。
  • 実行オーダーは最終形に近い形で実装する。
  • 定数倍の速度については、現時点では改善に取り組まず、安全性や他の言語機能の実装しやすさを優先する。

以上のことから、データ構造をどうするかが問題になる。わかりやすいケースとして、構造体が別の構造体をフィールドに持つケースを考える。 (構造体構文自体は未定)

struct A { ... }
struct B {
  field: A,
}

このとき、BからAの参照方法にはいくつか考えられる。

  • 変更が共有される
    • Gc<T>
    • Arc<Mutex<T>> / Rc<RefCell<T>>
  • 変更が共有されない
    • T
    • Box<T>
    • Arc<T> / Rc<T>

Umoでは堅牢なプログラムを書かせることや最適化のしやすさを考えて、デフォルトでは変更が共有されないようにしたい。

実はこのとき、いくつかの仮定のもとで、 T / Box<T> / Arc<T> の振る舞いは同等とみなせる。

  • Box<T> は T の中身をヒープ上に切り出しただけで、共有形態や生存期間などは同じ。
  • Arc<T> と Box<T> は一見異なるように見えるが、Weakを無視すれば Arc<T> を Box<T> のcopy-on-write版とみなすことができる。したがって共有にかかるコストと共有によって削減される計算量を除けば Arc<T> と Box<T> は同等。

そこで、Rubyなどのオブジェクト指向言語ユーザーの期待に近づける形で、 Arc<T> をデフォルトにすることを考える。以下のようにアノテーションをすることでパフォーマンス特性を切り替えることを考えている。

struct B {
  #[inline]
  field: A,
}

struct B {
  #[unique]
  field: A,
}

struct B {
  #[cow] // default
  field: A,
}

さて、この前提のもと、インタプリタV1では内部的には必ずサブフィールドを Arc<T> で保持することを考えている。その理由は、この方法であればRustの 参照相当の仕組みを Weak<T> で安全にシミュレートできる から。

Rustの参照が安全なのはボローチェッカーによって事前に静的に検査されているからだが、同じことをRust上で実装されたインタプリタ上で行ってもその保証をRustにうまく伝えるのは難しい。一番簡単なのはunsafeを使うことで、それは悪い方法ではないのだが、現時点では言語自体が発展途上なのでなるべく安全な状態で開発していきたい。というわけで、参照が生きているかどうかをランタイムでもう一度チェックすることを考えると、実はそれはArcとWeakがやっていることだということがわかる (参照が死んでいたらupgradeに失敗する)。というわけで、インタプリタV1ではサブフィールドを Arc<T> で保持し、イミュータブル参照は Weak<T> で保持する。

ミュータブル参照のユースケースは、当面の間は明示的にState monadのように展開した形でも困らないので、ミュータブル参照という形での実装は後回しにする。かわりに、所有権については気を遣う必要がある。たとえば配列の更新は以下のように行いたい。

array = set(array, index, new_value);

このとき、 set には array の所有権を渡したい。

なお、Umoではデフォルトでは所有権がない場合に暗黙にコピーを挿入することを考えている。この仕様により、インタプリタV1では Arc<T> のレイヤでコピーが起きるが、続く set 内でcopy-on-writeによって配列コピーが発生する。

一方、所有権がある場合は Arc<T> がコピーされないことで、続く set 内の Arc::make_mut ではコピーせずにそのまま内部参照が返される…… ということを期待したいが、そのためにはローカル変数内に Arc<T> の実体が残っていてはいけない。

この対策として、インタプリタV1では実行前に制御フローグラフ(CFG)を生成して、ローカル変数の生存解析を行う。このとき以下を行う。

  • 読み取ろうとした変数が後続で利用されていないときはムーブ (ローカル変数スタックから所有権を削除)し、後続で利用されているときはコピーする。
  • 書き込もうとして変数が後続で利用されていないときはその場でdrop (ローカル変数スタックから所有権を削除) する。

逆に、これ以上の最適化は現時点では必要ないので実装していない。たとえばSSAは生成しない。

⚠️ **GitHub.com Fallback** ⚠️