Resource Polymorphism

社内勉強会用資料です

Transcript

1. Resource Polymorphism @yubessy 0x64 物語 Reboot #13 " 排他|mutex|ownership"
2. ※ 今日の話は ownership 関連です
3. 2018/03/07 突如現れた論文が( 僕の中で) 話題に！
5. Resource Polymorphism Guillaume Munch-Maccagnoni (Inria) GC ベー スのOCaml に所有・ 借用モデルを導入！？ We present a resource-management model for ML-style programming languages, designed to be compatible with the OCaml philosophy and runtime model. ... It builds on the ownership-and- borrowing models of systems programming languages (Cyclone, C++11, Rust) and on linear types in functional programming (Linear Lisp, Clean, Alms). “ “
6. リソー ス ここでは「 コピー や廃棄にコストがかかる値」 のこと 巨大・ 複雑な構造体 ファイルハンドラ ソケット ロック ... これらの組み合わせで構成される値もリソー ス
7. リソー ス管理 リソー スはプログラムの至るところで生成される もしリソー スを適切に解放しなければ？ ヒー プ領域を圧迫してプログラムがOOM で死ぬ ファイルがロックされ他のプログラムが使えない こういった事態を防ぐため、 モダンな言語は 何かしらのリソー ス管理の仕組みをもつ
8. 代表的なリソー ス管理モデル Garbage Collection (GC) 実行中に随時不要なリソー スを検出・ 解放 Java, Go など多くの言語が採用 Ownership and Borrowing (OB) 実行前にプログラムを解析して解放処理を挿入 Rust の他に一部のFP 言語で linear type として採用
9. リソー ス管理モデルの一長一短 Garbage Collection (GC) pros: プログラマがメモリ管理を考えなくて済む cons: ランタイムの肥大化, Stop the World (STW) Ownership and Borrowing (OB) pros: ランタイムが小さい, STW しにくい cons: 一定の知識が必要, 複雑な参照があると大変
10. リソー ス管理モデルの併用は可能か？ 理想: 同じ言語の中でGC, OB を併用したい 単純な値 → OB でコンパイル時に解決 複雑な値 → GC で自動管理 現実: リソー ス管理(RM) モデルはたいてい言語依存 言語の初期設計段階でどちらかを採用 一旦採用したものをあとから変えるのが困難 → 言語の限界 = RM の限界という誤解 (Rust vs. Go)
11. Resource Polymorphism 言語研究者としてはこの問題をなんとかしたい ヒント: リソー スは値であり、 値には型がある アイデア: 値の型によってGC, OB を選択できないか？ GC 型の値はGC モデルで管理 OB 型の値はOB モデルで管理 これを Resource Polymorphism (RP) として提唱
12. Resource Polymorphism Resource Polymorphism の実現における課題 GC, OB の併用が実行の効率に影響しないか？ GC 型とOB 型の複合型をどのようにして扱うか？ 論文の成果: GC ベー スの言語に無理なくOB モデルを導入できる ことをOCaml による実装例とともに示す 以降はほんの触りだけ紹介
13. Resource Polymorphism まず３つの基本型を導入 G 型: GC で管理 O 型: ownership モデルで管理 B 型: borrowing モデルで管理 これだけなら同一ランタイム内で扱うのは難しくない O 型, B 型はコンパイル時に解放処理を挿入 G 型のみGC で管理
14. Resource Polymorphism 問題は異なる基本型同士の複合型 参照 直積, 直和 タプル, リスト, ツリー, ... 複合型は無限に存在 → 個別に扱いを定義できない しかし実は少数のパター ンをだけ考えればよい！
15. Resource Polymorphism 例: G 型とO 型の直積型 G*O はO 型として処理できる = G*O の値も ownership モデルで管理してよい 特にO, B 型と他の型の複合型は O , B , O+B のいずれか これが( たぶん) 一番のポイント
16. ※ 論文はまだまだ続くが・・・
17. まとめ GC とOB の一貫した統合は人類の悲願 RP では型の力でこの実現を目指す 実用上もGC 言語にOB を導入する方法として有力 先史時代 → Java 帝国 → Rust 登場 → RP ？ あと5 年くらいしたらトレンドになってるかも？