purityから導き出される特性

(以下は正式な言語仕様の決定ではなく、単なる私的なメモです)

# おさらい

pure属性は、ある関数がグローバル変数にアクセスしないことを保証(厳密には仮定)できる。ただし、D言語のpureは以下の点が特徴的であり、よく知られている関数言語的な純粋性とは必ずしも同じではない。

- コードでは同じpureが付いた関数でも、暗黙にstrong purity、constant purity、weak purityの3つの区別が存在する。
- weak purityはmutableな要素を指す配列などを引数に取るpure関数が分類される。

    ```d
    int func(int[] arr) pure;
    ```

    funcの本体は、`arr[n]`にアクセスしてそこにある値を書き換えることができる。

- constant purityは同じく間接参照を持つが、その参照先がconstであるもの

    ```d
    int func(const(int)[] arr) pure;
    ```

    たとえ同じ配列のスライスでfuncを呼んでも、間接参照先はアプリケーションの別の箇所で書き換わっている可能性があるのでこのタイプは同じ値で関数を呼び出した時同じ値が返ってくる、という参照透明性が保証できない。

- strong purityは、引数が値で渡されるか、あるいは間接参照があってもそれがimmutableであるもの

    ```d
    int func(int n, immutable(int)[] arr) pure;
    ```

    このタイプは引数を通して呼び出し側の値を書き換えることができないし、また引数が同じなら同じ結果しか返せないので参照透明性が保証できる。メンバ関数もpureにすることができるが、この場合暗黙のthisを引数の1つとして考えれば上記の分類が適用できる。

----

# 本題

たとえば

```d
T getNth(T)(T[] array, size_t index) pure { return array[index]; }
```

という関数がある場合、この関数を使用する側は以下の様なコードを書ける

```d
int[] arr = [1,2,3];
immutable(int) first_elem = getNth(arr, 0);
```

戻り値をimmutable intとして変数に保持している。当たり前のようだが、これがなぜ可能かという理由はなかなか深い。たとえばintの代わりに以下の様な構造体を使ってみよう。

```d
struct MyArray { int[] arr; }
auto arr = [MyArray([1,2,3]), MyArray([4,5,6])];
immutable(MyArray) first_elem = getNth(arr, 0);  // compile error!
```

今度はfirst_elemの初期化がコンパイラによって弾かれる。理由は以下のとおりである。

- getNthから返される値は、array[index]の浅いコピーである(MyArrayはpostblitを持たないので)
- MyArrayはmutableなint配列への間接参照を持っているため、immutableへの変換を許すとコピー元のMyArrayが持つint[]をimmutable(MyArray)が参照する状態が作れてしまう。

つまり、間接参照の共有が発生することが問題なのだ。

----

さて、ここでpure関数について今一度考えてみる。pure関数はグローバル変数にアクセスできないので、関数がアクセス可能な「入力」についての情報は全て仮引数に表現されている。これを戻り値、つまりは「出力」と突き合わせると、実は「入力が出力と間接参照を共有しない場合」というケースを静的に判断できる。次に例を挙げる。

```d
int[] foo(const(int)[] arr) pure;
```

fooの「入力」はarrであり、その型はconst(int)[]だ。「出力」はint[]である。このfooは入力と出力の間で間接参照を共有するだろうか。答えは「不可能である」。以下の様なfooの本体を書いてみればそれがわかる。

```d
int[] foo(const(int)[] arr) pure { return arr; }  // compile error!
```

当たり前だがconst(int)[]はint[]に暗黙変換できないので、int[]を返すには

- 新しくヒープに配列を確保する

しかない(ここではfooが`cast(int[])arr`のような安全でない操作を行わないことを前提としている)。もちろんfooはpure関数なので、新しい配列をグローバル変数に格納しておくようなことはできない。つまりこの時点で、fooが返す配列は「配列要素への間接参照を他の場所に持っていない」ことが保証できるのだ。

これは注目に値する保証だ。fooが返す値はどこかの変数に束縛されるまで「孤立した」値なのだ。つまりたとえその型がmutableであっても、immutableへの暗黙キャストは問題を起こさない！

```d
// 入力と同じ長さの配列を確保し、それを返す
int[] foo(const(int)[] arr) pure { return new int[](arr.length); }

int[] arr1 = [1,2,3];
immutable(int)[] arr2 = foo(arr1);  // OK!
```

もうちょっと複雑な例を見てみよう。

```d
struct Array { int* ptr; size_t length; }
Array bar1(int[] arr) pure;
```

bar1の返す値は孤立しているだろうか？　答えは「No」である。たとえばこのようなbar1の実装が書ける。

```d
Array bar1(int[] arr) pure { return Array(arr.ptr, arr.length); }
```

Array.ptrはint*であり、これはarr.ptr(あるいは&arr[n])を束縛可能なので、bar1の出力は入力と間接参照を共有しうる。従ってその戻り値をimmutableに暗黙キャストすることはコンパイラが許さない。
※注意してほしいのは、bar1の関数本体のコードは何であるかは「孤立可能かどうか」には関係ないという点だ。D言語は分割コンパイルを可能としているので、何かを静的に保障したい場合、それらは基本的に型に現れる。この場合はbar1というpure関数のシグネチャ全体が「孤立可能かどうか」という特性を計算するための元手になっている。pure関数の本体を解析して特性を計算するようなことはD言語は基本的にはしない。
※さらに、Arrayがどんなメンバ関数を持っているかも関係ない。それらがArrayのフィールドにどのような操作を施そうと、間接参照を保持しうるのはArrayオブジェクトのフィールドだけだからだ。

さて、bar1のシグネチャをちょっと書き換えてみる。

```d
Array bar2(const(int)[] arr) pure;
```

もうお分かりだろうが、今度は戻り値が孤立した値になる。関数の入力であるarrはconst(int)[]なので、そこから取得可能なポインタもconst(int)*であり、int*には暗黙変換できない。従ってbar2の入力は出力と間接参照を共有しえない。

----

以上がD言語のpurityが保証可能な特性の解説になる。この特性についての初出は[Issue 5081](http://d.puremagic.com/issues/show_bug.cgi?id=5081)だが、それ自体にはまだ(コミュニティ内部でも)正式な名前がついてないようなので、私はこれをそのまま"isolated"と呼んでいる。

この特性を限定的に実装するための[変更](https://github.com/D-Programming-Language/dmd/pull/1110)が2.061にはマージされており、またより根本的な実装を現在新しい[Pull request](https://github.com/D-Programming-Language/dmd/issues/1519)として提出中である。

この特性はimmutableな値を構築するとき、値の汎用的なコピー操作を定義するとき(e.g. ライブラリによる`arr.dup`、`Range.save`)などに役立つと思われるが、そのうちの1つとしてpostblitの定義と実装の改善を現在想定している(実は今日そっちのうまいsyntaxが思いついたのでこれを書いた)。
これについてはまた別の投稿を行う予定である。