D言語erでも値に依存したい

この記事を書いたきっかけ

OCamlで幽霊型を使う記事を読んでる時にこれD言語でも出来るのではと思ったのがきっかけです。ここでは型安全なリストとそれに対する型安全なインデックスアクセスをやってようと思います。

依存型とは

依存型とは値に依存する型のことです。
実際に依存型が言語機能として入ってる言語にはATS2やAgda2などがあり、ATS2では値に対する不変条件(x>=2, x>0|x<10)などを型に持つことが出来ます。

型安全なリスト

ただのリスト

struct List(T) {
    private T[] arr;
    auto cons(T x) {
        return List!T(arr~x);
    }
    auto hd() {
        return arr[$-1];    
    }
    auto tl() {
        return List!T(arr[0..$-1]);
    }
}
auto nil(T)() {
    return List!T([]);
}

consがリストに値を追加するメソッド、hdがリストの先頭の値を取り出すメソッド、tlが先頭を取り除いたリストを返すメソッドになります。このリストはリストとして最低限の動作をすることは出来ますが、空リストに対しhdやtlを使うことが出来てしまいます。

nil!int.cons(0).cons(1).hd // => 1
nil!int.cons(0).cons(1).hd // => List!int([0])
nil!int.hd // アクセス違反だが実行できてしまう

型安全なhdとtl

先程の例の3番目をコンパイルエラーにするためにはどうすればいいでしょうか。単純で分かりやすい方法としてリストの型に長さの情報を追加するものが考えられます。

struct List(alias N, T) {
	private T[] arr;
}

auto nil(T)() {
	return List!(0, T)();
}

auto cons (L : List!(N, T), alias N, T)(L list, T x) {
	return List!(N+1, T)(list.arr ~ x);
}

auto hd (L : List!(N, T), alias N, T)(L list) {
	static assert (N > 0);
	return list.arr[$-1];
}

auto tl (L : List!(N, T), alias N, T)(L list) {
	static assert (N > 0);
	return List!(N-1, T)(list.arr[0..$-1]);
}

List(T)からList(alias N, T)に変更しました。Nがリストの長さを表します。
consをすると長さを+1、hd, tlで-1、hd、tlをする時に長さを調べる事でコンパイル時に空リストへのhd, tlをコンパイルエラーにすることが出来ました。
ここでList(T)では構造体内にメソッドとして定義していた関数群を構造体の外に出したのは、構造体内に入れてしまうとList!(T, N+1)の構造体を返そうとしてインスタンス化するとList!(T, N).fooだけでなくList!(T, N+1).fooまでインスタンス化され、それがList!(T, N+2).fooを...とテンプレートのインスタンス化が停止しなくなるためです。
OCamlではペアノ算術で型レベル自然数を定義する必要がありましたが、D言語のテンプレートだとコンパイル時にも自然数を使えるので定義がとても楽です。

nil!int.cons(1).tl; // => List!(int, 0)([])
nil!int.cons(1).tl.hd; // コンパイルエラー

ちゃんとコンパイルエラーに出来ています(当たり前ですが)。

リストの連結

auto join(L1 : List!(N1, T), L2 : List!(N2, T), alias N1, alias N2, T)(L1 l1, L2 l2) {
	return List!(N1+N2, T)(l1.arr ~ l2.arr);
}

パラメータがかなり増えましたがやってることは単純です。

型安全なインデックスアクセス

hdやtlが型安全になったと言われたところでhdやtlしか使えないのでは不便です。インデックスアクセス出来るならインデックスアクセスしたいですよね。

auto idx (alias IDX, L : List!(N, T), alias N, T)(L list) {
	static assert (IDX > 0 && IDX < N);
	return list.arr[IDX];
}

nil!0.cons(0).cons(1).idx!1 // => 1
nil!0.cons(0).cons(1).idx!2 // コンパイルエラー

このように使うことが出来ます。

実行時に決まる値でインデックスアクセス

これまででリストに対しコンパイル時定数でインデックスアクセスすることが出来るようになりました。ただコンパイル時処理に慣れているD言語erにとってはこの程度の事は当たり前の事に感じられてしまうかと思います。
今まではコンパイル時定数でインデックスアクセスしていましたが、型安全にインデックスアクセスするのであればインデックスか0以上、リストの長さ未満であることさえ分かれば十分です。最小値と最大値を型に持つ整数を定義します。

import std.algorithm.comparison : max, min;
import std.math : abs;
struct Interger(alias B, alias T) {
	static if (B >= 0) {
		ulong value;
	}
	else {
		long value;
	}

	auto opBinary(string op, I : Interger!(XB, XT), alias XB, alias XT)(I x) {
		static if (op == "+") {
			enum NEW_B = B+XB;
			enum NEW_T = T+XT;
			return Interger!(NEW_B, NEW_T)(value+x.value);
		}
		else static if (op == "-") {
			enum NEW_B = B-XB;
			enum NEW_T = T-XT;
			return Interger!(NEW_B, NEW_T)(value-x.value);
		}
		else static if (op == "*") {
			enum NEW_B = min(B*XB, B*XT, T*XB, T*XT);
			enum NEW_T = max(B*XB, B*XT, T*XB, T*XT);
			return Interger!(NEW_B, NEW_T)(value*x.value);
		}
		else static if (op == "/") {
			static if (XB == 0 && XT == 0) {
				static assert (false);
			}
			else static if (XB == 0) {
				enum NEW_B = min(B/XT, T/XT);
				enum NEW_T = max(B/XT, T/XT);
			}
			else static if (XT == 0) {
				enum NEW_T = max(B/XB, T/XB);
				enum NEW_B = max(B/XB, T/XB);
			}
			return Interger!(NEW_B, NEW_T)(value/x.value);
		}
		else static if (op == "%") {
			static if (B < 0 && T < 0) {
				enum NEW_B = -max(abs(XB), abs(XT));
				enum NEW_T = 0;
			}
			else static if (B < 0) {
				enum NEW_B = -max(abs(XB), abs(XT));
				enum NEW_T = max(abs(XB), abs(XT));
			}
			else {
				enum NEW_B = 0;
				enum NEW_T = max(abs(XB), abs(XT));
			}
			return Interger!(NEW_B, NEW_T)(value/x.value);
		}
	}
}

Bが最小値、Tが最大値です。

Interger!(0, 10)(4) * Interger!(-2, 2)(-1) // => Interger!(-20, 20)(-4)
Interger!(0, 20)(6) % Interger!(0, 3)(2) // => Interger!(0, 3)(3)

正しく範囲を計算できてそうですね。
これを引数として取るopIndexを定義します。

struct List(alias N, T) {
	private T[] arr;

	auto opIndex(I : Interger!(B, T), alias B, alias T)(in I idx) {
		static if (B >= 0 && T < N) {
			return arr[idx.value];
		}
		else {
			static assert (false, "Out of range");
		}
	}
}

auto i1 = Interger!(0, 2)(1);
auto i2 = Interger!(0, 10)(7);
auto l = nil!int.cons(0).cons(1).cons(2);
auto x = l[i1]; // => 1
auto y = l[i2]; // コンパイルエラー
auto z = l[i2%i1]; // => 0

コンパイル時に値の範囲を明示する必要があるという制限付きですが実行時に着ある値で型安全にインデックスアクセスすることが出来ました。

おまけ

struct IndexRange(alias B, alias T) {
	long idx = B;
	bool empty() {
		return idx > T;
	}

	auto front() {
		return Interger!(B, T)(idx);
	}
	
	void popFront() {
		++idx;
	}
}

auto rng(alias B, alias T)() {
	return IndexRange!(B, T-1)();
}

auto interger(alias N)() {
	return Interger!(N, N)(N);
}

	auto l = nil!int.cons(0).cons(1).cons(2).cons(3).cons(4).cons(5).cons(6);
    //コンパイルエラー
	foreach (i; rng!(-3, 0)) {
		writeln(l[i]);
	}
	foreach (i; rng!(-3, 0)) {
		writeln(l[i+interger!3]);
	}
	foreach (i; rng!(-3, 0)) {
		writeln(i);
		writeln((i+interger!3)*interger!2);
		writeln(l[(i+interger!3)*interger!2]);
	}

型安全にインデックスベースでイテレートすることも出来ます(?)。

まとめ

実行時には必要としない値を型に埋め込む事で値の制約条件を型に埋め込む事が出来ます。ただし型に制約を埋め込んでしまうと配列に入れる時は同じ制約を持つ型でないと同じ配列に入れられないなど柔軟性が損なわれる場合があります。
今回の例はあまり実用性が無さそうですが、Cのライブラリのラッパライブラリに導入すればある程度の型安全性を保証したり出来ると思います。

最後に

この記事は@k3_kaimuさんのD言語erでも純粋に生きたいを参考にして書かれました。
依存型とか幽霊型のあたりは非常に怪しいので優しくマサカリを投げていただけると助かります。
今回のコードはここに置いています。