KOTET'S PERSONAL BLOG

#dlang 所有権と借用をD言語に組み込む【翻訳】

Created: , Last modified:
#dlang #tech #translation #d_blog

これは1年以上前の記事です

ここに書かれている情報、見解は現在のものとは異なっている場合があります。

Ownership and Borrowing in D – The D Blog を 許可を得て 翻訳しました。

誤訳等あれば気軽に Pull requestを投げてください。

ほとんどのプログラムはメモリを確保し、管理します。 プログラムが複雑になり、失敗がより大きな損害を引き起こすようになるにつれて、 メモリ管理を正しく行うことはますます重要になってきています。 一般的には以下のような問題があります。

  1. メモリリーク（使っていないメモリを解放しない）
  2. 二重フリー（複数回メモリを解放する）
  3. use-after-free（すでに開放されたメモリを参照する）

問題は、どのポインタがメモリを解放する責任を持つか（つまり、メモリを所有しているか）、 どのポインタがメモリを参照しているか、どれが（スコープ内で）アクティブかです。

一般に以下のような解決策があります。

  1. ガベージコレクション（Garbage Collection）
    GCがメモリを所有し、時々メモリをスキャンすることで所有するメモリを指すポインタを探します。 ひとつも見つからなかった場合、メモリを解放します。 このスキームは信頼性があり、GoやJavaのような言語でよく使われています。 書き込みゲートが挿入されるため、実際に必要な量より多くのメモリを使用し、 停止し、プログラムの速度を遅くする傾向があります。
  2. 参照カウンティング（Reference Counting）
    RCオブジェクトがメモリを所有し、そのメモリを指すポインタがいくつあるかをカウントします。 カウントがゼロになると、メモリが開放されます。 これも信頼性がありC++やObjectiveCのような言語で使われています。 RCはメモリ効率が高く、カウントのための領域しか必要としません。 RCのマイナス面はカウントのコストが高いことです。 デクリメントが確実に行われるように例外ハンドラを作り、スレッド間で共有されるオブジェクトの場合はロックも必要です。 速度のためにプログラマはチートをして、RCオブジェクトに対してカウントをせずに参照をしてしまうことがあり、 その結果事故が起こるリスクが発生します。
  3. 手動
    手動メモリ管理の例としてCのmallocとfreeがあります。 これは高速でメモリ効率が高いですが、言語の手助けは一切ありません。 完全にプログラマのスキルと努力に依存します。 私はmallocとfreeを35年使ってきた苦く終わりのない経験のために失敗をすることはほとんどありません。 しかし私が「まったく」ではなく「ほとんど」と書いたことからもわかるように、これは信頼できるものではありません。

ソリューション2と3はプログラマーが正しくメモリ管理が出来るという信頼にいくぶん頼っています。 信頼ベースのシステムはスケールせず、メモリ管理の問題は監査が非常に難しいです （難しいため、メモリ確保を禁止しているコーディング規約も存在します）。

しかし4番目の方法があります – 所有権と借用です。 これはメモリ効率が高く、手動管理と同じくらい高速で、機械的監査が可能です。 所有権と借用はプログラミング言語Rustで有名になりました。 これにも欠点はあり、アルゴリズムやデータ構造の構成方法を考え直さなければならないと評判です。

この欠点は対処可能なものであり、この記事の残りでは所有権/借用（ownership/borrowing、OB）システムがどのように動作するか、 そしてそれをDに組み込む提案について話します。 最初私は不可能だと思っていましたが、時間をかけて考えた結果、方法はあるとわかりました。 （推移的イミュータビリティと関数の純粋性によって）関数型プログラミングをDに組み入れたのと同じように。

所有権

誰がメモリオブジェクトを所有するかはバカバカしいほどシンプルです。 ひとつのポインタがメモリを所有するため、ポインタが所有者です。 ポインタはそれが有効であることをやめた後にメモリを解放する責任を持ちます。 当然メモリオブジェクト内のすべてのポインタはそのポインタが指す先のメモリの所有者であり、 データ構造内にそれ以外のポインタは存在せず、したがってデータ構造は木構造のかたちをとります。

ポインタはコピーされず、ムーブされます。

T* f();

void g(T*);

T* p = f();

T* q = p; // pの値はqにムーブされました。コピーされてはいません

g(p);     // エラー。pは不正な値を持ちます

データ構造の外にはポインタをムーブできません。

struct S { T* p; }

S* f();

S* s = f();

T* q = s.p; // エラー。s.pへのポインタを複数持つことはできません

なぜ単にs.pを不正としないのでしょうか？ それは実行時にマークされる必要があり、今はコンパイル時のソリューションを想定しているので、 それは単にエラーになります。

スコープを超えてポインタを所有することもエラーになります。

void h() {

  T* p = f();

} // エラー。pの解放を忘れていますね？

ポインターはどこかにムーブする必要があります。

void g(T*);

void h() {

  T* p = f();

  g(p);  // g()にムーブしたので、これはもうg()の問題です

}

これによりメモリリークとuse-after-freeの問題はきっぱり解決されます （ヒント：わかりやすくするために、f()をmalloc()に、g()をfree()に置き換えてみましょう）。

これは関数内では、 共通部分式 を求めるのに使われているような データフロー解析（DFA） を用いてコンパイル時に追跡できます。 DFAはgotoが何重にも折り重なった中に潜むどんなネズミも見逃しません。

借用

上で説明した所有権システムは堅実ですが、制約が厳しすぎます。 以下のようなコードを考えてみましょう。

struct S { void car(); void bar(); }

struct S* f();

S* s = f();

s.car();  // sはcar()にムーブされました

s.bar();  // エラー。sは不正です

これを動作させるためには、s.car()から戻ってきたときにムーブしたポインタをsに返す方法が必要です。

ある意味、これは借用の仕組みそのものです。 s.car()はs.car()が実行される間sのコピーを借用します。 sはこの実行の間不正になり、s.car()から返ってきたときふたたび有効になります。

Dにおいて、構造体のメンバ関数はthisを参照としてとるため、エンハンスメントを通して借用に適応できます。 つまり、引数をrefでとるとそれは借用されます。

Dはscopeポインタもサポートしているため、これも借用に自然と適応します。

void g(scope T*);

T* f();

T* p = f();

g(p);      // g()はpを借用します

g(p);      // g()から返ってきた後はまたpを使用できます

（ 関数が引数をrefまたはscopeポインタとしてとるとき、refやポインタから脱出することはできません。 これは借用セマンティクスに適合します。 ）

この方法で借用を実現すれば、 あるメモリオブジェクトを指すポインタは同時にただひとつ存在するという保証ができるため、動作します。

ミュータブルなポインタが存在せず、変更できないポインタだけが複数あるという状況でも所有権システムは安全なままである、 という小さな洞察によって借用は更に強化できます。 （constポインタはメモリの解放も変更もしません。） これはメモリを所有しているミュータブルなポインタがアクティブでない間であれば、 複数のconstなポインタがそのポインタの指すメモリを借用できるということを意味します。

例えば以下のようになります。

T* f();

void g(T*);

T* p = f();  // pは所有者になります

{

  scope const T* q = p; // constなポインタを借用

  scope const T* r = p; // もうひとつ借用

  g(p); // エラー。qとrがスコープ内にある間はpは不正です

}

g(p); // ok

原理

上記はメモリオブジェクトが2つのうち1つの状態をとるかのように振る舞うという概念に蒸留できます。

  1. メモリオブジェクトへのミュータブルなポインタがただ1つ存在する
  2. メモリオブジェクトへのconstポインタが1つ以上存在する

注意深い読者は私が書いた「かのように」という言葉に気づいたことでしょう。 わざと曖昧な言葉遣いをしたのはなぜでしょうか？ なにかごまかしが行われようとしていたのでしょうか？ そうです、これはごまかしです。 コンピュータ言語は「かのように」でいっぱいであり、裏側では銀行に預けたお金が実際には銀行に存在しないのとおなじように （だれかショックを受けた人がいたなら謝罪します）ダーティなことが行われています。 読んでいきましょう！

でもまずは、少々解説が必要でしょう。

Dに所有権/借用を組み入れる

このスキームは人々が普通に書いているDのコードと互換性がありません。 既存のDプログラムをすべて壊してしまわないといけないのでしょうか？ そして簡単に修正ができなかった場合、アルゴリズムを再設計しなければいけないのでしょうか？

まあ、そうなります。 ただしそれはDの隠し玉（別に隠してはいませんが）、関数属性がない場合の話です。 所有権/借用（OB）システムのセマンティクスは通常のセマンティック解析が実行された後に関数単位で行えることがわかりました。 注意深い読者は新しい構文の追加が不要で、既存のコードに制約を課すだけでいいということに気づくでしょう。 Dには関数属性を関数のセマンティクスを変化させるために使ってきた歴史があります。 例えば、pure属性を追加すると関数は純粋であるかのように振る舞います。 OBセマンティクスを関数に適用するには、@live属性を追加します。

つまりOBは、必要に応じて、そして時間とリソースに応じてDのコードにインクリメンタルに追加できます。 プロジェクトを完全に機能し、テストされ、リリース可能な状態に保ちつつOBを追加できるようになります。 プロジェクトのどれくらいがこの規則の上でメモリ安全化を機械的に監査可能です。 これはDのさまざまなメモリセーフ保証（スタックを脱出するポインタが存在しない、のような）のリストに加わります。

「かのように」

リファレンスカウントされるメモリオブジェクトのような、厳格なOBの重要な要素がまだできていません。 なんといってもRCオブジェクトの本質は複数のポインタが存在することにあります。 RCオブジェクトは（正しく構築された場合）メモリ安全であるため、メモリ安全との悲劇的衝突をせずにOBと同居できます。 OBの上でRCの構築はできないというだけなのです。 ソリューションとして、Dには他にも@systemのような関数に対する属性があります。 @systemでは様々な安全性チェックが切られます。 もちろん、OBも@systemコードでは無効化されます。 これによりRCオブジェクトの実装をOBチェッカーから隠すことができます。

しかしOBコードの中で、OBチェッカーの目にはRCオブジェクトがルールに従っているように見えます。 これで問題ないですね！

数多くのライブラリがOBを使えるようになるでしょう。

結論

この記事はOBの基礎の概観をしました。 私はさらに総合的な仕様について作業をしています。 なにかを見逃しており水面下に穴があるという可能性は常にありますが、これまでのところ大丈夫そうです。 このDのとてもエキサイティングな開発が実装されるのが楽しみです。