Region-Based Memory Management in Cyclone を読んだ その3

September 24, 2017

続き。

存在型とDangling pointer

例えばクロージャががある言語ではポインタや参照がクロージャによってキャプチャされ、本来のライフタイムを超えて使用される(escapeする)可能性がある。自分がいちばん馴染みのあるSwiftでも同じ。

Cycloneはクロージャこそ持っていないが存在型を持っている。

struct IntFn ∃α { int (*func)(α env); α env;};

存在型は「ある型について〇〇」のように型の一部分を量化することで抽象的に扱うための仕組み。存在型にpackしてしまえば、openして抽象的なまま扱うことはできても元の型が何であったかを知る方法はない。

int read<ρ>(int*ρ x) { return *x; } struct IntFn dangle() {
    L:{int x = 0;
        struct IntFn ans =
<int*ρL>{.func = read<ρL>, .env = &x}; return ans; }
}

例えば上の例でans は 実際にはα = int* ρL である存在型であるが、IntFn という型であることからはαがポインタ型であることはわからなくなってしまう。その状態でα型をもつenv に操作を行うなどすると、Dangling pointerが起こる可能性がある。

これを防ぐためにCycloneでは2つの手法を導入する。

Effect / Capability

Dangling pointerを防ぐためにCycloneでは Effect と呼ばれるその関数がアクセスする可能性のあるリージョンの集合とCapability と呼ばれるその時点で生きているリージョンの集合を考え、関数を呼び出す際にはその関数のEffectに含まれるリージョンがすべてCapabilityに含まれることを確認する。

例えば以下のような関数のEffectは{ρ1, ρ2, ρ3} となる。

int*ρ1 f<ρ1, ρ2, ρ3>(int*ρ2 ,int*ρ1 *ρ3 );

また、多相な関数に対してEffectを表すために regions_of オペレータを導入する。cmp のEffectは型パラメータα に含まれるリージョンによって決まる。

struct Set<α,ρ> {
	list_t<α,ρ> elts;
	int (*cmp)(α,α; regions_of(α));
}

αがポインタであればregions_of(α)はそのポインタが指すリージョンになるし、ポインタ型でなければ空集合になる。

Bound

「あるリージョンがある別のリージョンより長生き」のような制約をかけて、存在型にpackする際に型チェックを行えるようにすることでopen時には安全に操作できることが保証されているようにできる。

struct IntFn<ρ> ∃α:>ρ { ... };

適切な日本語がわからないけど、TaPLの全称型・存在型に対しては有界量化と呼ばれてたので「有界リージョン」みたいな感じだろうか。。実際「長生き」関係はそのままサブタイプ関係になりそうなので同じ考え方をしてもよさそう。

まとめ

  • Dangling pointerのデリファレンス、メモリリークをコンパイル時に防ぐ仕組みとしてリージョンを導入した
  • リージョンを明示的に書くのは大変なので、省略するための仕組みがある。
  • 関数のEffectをチェックしたり、リージョンに制約をかけることで、Escapeされたとしても安全に扱える
このエントリーをはてなブックマークに追加