2006-05-30

typelist と mem_fun

Prog D言語

Loki の Typelist、誰か実装してくれてないかな〜、と思っていたら、
2004-01-16の方で、やってくれてました。
チェックが足りん。

ん〜、シンプルで美しいですね。
私は、Typelist の中身を型 alias ２つにして、できねぇできねぇ言ってたんですが、これ見ると、変数を実体で持ってるのがミソですね。

でも、実用的には羅列型の TypeArray で十分だし、そっちの方が length と typeAt がメンバになってるから使いやすかも、とか言ってみる。

あと、STLん中でポーティングできないでいるのが、mem_fun 。ヘッダ見ると、->.* とかって怪しげな演算子を使ってますね。D言語の現在の仕様ではポーティングできないかも。

2006-05-29

汎用ファンクタ

Prog D言語

できないと言っていた汎用ファンクタができてしまった。

ArgType の定義で、インスタンス化した TypeArray.typeAt に typeof をかけているのがミソ。
（TypeArray の定義は 5-23 のと同じ）

module doki.functor;

import doki.typearray;

class Functor(R, Args) {
    invariant {
        static assert(is (typeof(Args.length)));
        static assert(
            Args.length >= 10 && is (typeof(Args.typeAt!(9))) ||
            Args.length >=  9 && is (typeof(Args.typeAt!(8))) ||
            Args.length >=  8 && is (typeof(Args.typeAt!(7))) ||
            Args.length >=  7 && is (typeof(Args.typeAt!(6))) ||
            Args.length >=  6 && is (typeof(Args.typeAt!(5))) ||
            Args.length >=  5 && is (typeof(Args.typeAt!(4))) ||
            Args.length >=  4 && is (typeof(Args.typeAt!(3))) ||
            Args.length >=  3 && is (typeof(Args.typeAt!(2))) ||
            Args.length >=  2 && is (typeof(Args.typeAt!(1))) ||
            Args.length >=  1 && is (typeof(Args.typeAt!(0)))
        );
    }

    alias R ReturnType;
    alias Args ArgsType;

    template ArgType(int n) { alias typeof(Args.typeAt!(n)) ArgType; }

    alias ArgType!(0) Arg0Type;
    alias ArgType!(1) Arg1Type;
    alias ArgType!(2) Arg2Type;
    alias ArgType!(3) Arg3Type;
    alias ArgType!(4) Arg4Type;
    alias ArgType!(5) Arg5Type;
    alias ArgType!(6) Arg6Type;
    alias ArgType!(7) Arg7Type;
    alias ArgType!(8) Arg8Type;
    alias ArgType!(9) Arg9Type;

    template callOperator(int n :  1) { abstract ReturnType opCall(ArgType!(0)); }
    template callOperator(int n :  2) { abstract ReturnType opCall(ArgType!(0), ArgType!(1)); }
    ...
    mixin callOperator!(Args.length);

}

で、実行。

import std.stdio;

void main() {
    alias Functor!(bool, TypeArray!(int, char, double)) Arg3Functor;
    writefln(typeid(Arg3Functor.ArgsType));
    writefln(typeid(typeof(Arg3Functor.ArgsType.typeAt!(0))));
    writefln(typeid(typeof(Arg3Functor.ArgsType.typeAt!(1))));
    writefln(typeid(typeof(Arg3Functor.ArgsType.typeAt!(2))));
    writefln(typeid(Arg3Functor.ArgType!(0)));
    writefln(typeid(Arg3Functor.ArgType!(1)));
    writefln(typeid(Arg3Functor.ArgType!(2)));
}
...
TypeArray
int
char
double
int
char
double

ンマー、よかですな。
戻り値の型 bool、引数の型が int, char, double の opCall を持つ、関数オブジェクトの定義は以下のようになる。

    class MyFunctor : Functor!(bool, TypeArray!(int, char, double)) {
        override ReturnType opCall(
            ArgType!(0) arg0,
            ArgType!(1) arg1,
            ArgType!(2) arg2
        ) {
            ReturnType result = false;
            return result;
        }
    }

Functor を継承してナニいいことあんのよと言われそうだが、これを継承することによって、ReturnType と ArgType!(0〜n) の型 alias を持つことが保証され、汎用プログラミングがやりやすくなる。STL の関数オブジェクトが unary_function や binary_function を継承しているように。

    writefln(typeid(MyFunctor));
    writefln(typeid(MyFunctor.ReturnType));
    writefln(typeid(MyFunctor.ArgsType));
    writefln(MyFunctor.ArgsType.length);
    writefln(typeid(MyFunctor.ArgType!(0)));
    writefln(typeid(MyFunctor.ArgType!(1)));
    writefln(typeid(MyFunctor.ArgType!(2)));
    writefln(typeid(typeof(MyFunctor.opCall)));
...
MyFunctor
bool
TypeArray
3
int
char
double
bool()

といった具合。

TypeArray の実装が、羅列型のナサケナバージョンから変わる可能性はあるけど、どっちみち length と、typaAt テンプレートはつけるので、変わってもこちらに影響なし。

2006-05-26

型コンテナ(ナサケナVersion)

Prog D言語

Loki の Typelist をD言語にポートし、可変個型引数を実装できないかな〜と思った。
だがやってみると難しく、Length と TypeAt すら実装できずに挫折した。
（誰かやった人はいないのかしら？）

で、代わりに作ったのが以下のような羅列型のテンプレート。

module doki.typearray;

class NullType {}

template TypeArray (
    T0,
    T1 = NullType,
    T2 = NullType,
    T3 = NullType,
    T4 = NullType,
    T5 = NullType,
    T6 = NullType,
    T7 = NullType,
    T8 = NullType,
    T9 = NullType
) {
    class TypeArray {
        const length = (
            !is (T9 == NullType) ? 10 :
            !is (T8 == NullType) ? 9 :
            !is (T7 == NullType) ? 8 :
            !is (T6 == NullType) ? 7 :
            !is (T5 == NullType) ? 6 :
            !is (T4 == NullType) ? 5 :
            !is (T3 == NullType) ? 4 :
            !is (T2 == NullType) ? 3 :
            !is (T1 == NullType) ? 2 :
            1
        );
        template typeAt(int n    ) {                  }
        template typeAt(int n : 0) { alias T0 typeAt; }
        template typeAt(int n : 1) { alias T1 typeAt; }
        template typeAt(int n : 2) { alias T2 typeAt; }
        template typeAt(int n : 3) { alias T3 typeAt; }
        template typeAt(int n : 4) { alias T4 typeAt; }
        template typeAt(int n : 5) { alias T5 typeAt; }
        template typeAt(int n : 6) { alias T6 typeAt; }
        template typeAt(int n : 7) { alias T7 typeAt; }
        template typeAt(int n : 8) { alias T8 typeAt; }
        template typeAt(int n : 9) { alias T9 typeAt; }
    }
}

汎用プログラミングは再起を使うのが一般的なんですけどね〜。
まぁ、動かしてみよう。

debug(typearray) {
    import std.stdio;

    void main() {
        alias TypeArray!(int, char, double) Types3;
        writefln(typeid(Types3));
        writefln(Types3.length);
        writefln(typeid(Types3.typeAt!(0)));
        writefln(typeid(Types3.typeAt!(1)));
        writefln(typeid(Types3.typeAt!(2)));
    //  writefln(typeid(Types3.typeAt!(3)));
    //  writefln(typeid(Types3.typeAt!(9)));
    }
}
...
C:\d\doki>dmd -debug=typearray -run typearray
TypeArray
3
int
char
double

ンマー、動いてますな。
でもこれで例えば可変個型引数の汎用ファンクタを実装しようとしてもできないんだな〜。

2006-05-20

比較関数つきsort

Prog D言語

最近、STLをD言語へポーティングするみたいな作業をしている。
DTLがあるじゃないかと言われそうだが、DTLは bind2nd など足りないものが多い。

D言語組み込みの動的配列と連想配列だけでコンテナはすませようと思ってるので iterator もポーティングする気はしない。
algorithm は大変なので全部やる気はしないが、functional はやりやすかった。

D言語の組み込み配列だけでは足りない機能として、比較関数つき sort がある。
配列の sort プロパティでは比較関数が opCmp しか使えないので、

class C {
    int id;
    char[] name;
}

といったクラスが要素の配列を、id で sort したり、name で sort したりするには、opCmp から function を呼び出す形にして、function を比較する前に切り替えるなどのしかけが必要になってしまう。

しかもその function をインスタンスメンバにすれば、sort 前に配列内の全要素切り替えなければならないし、static メンバにすれば、id で sort したとき name で sort されている配列は「間違った状態」ということになってしまう。

比較関数をクラスまたはインスタンスの「状態」として恒久的に持つというのはよい考えではなく、sort する時点で指定するものだろう。

そのためのコード。

template swap(T) {
    void swap(inout T v1, inout T v2) {
        T tmp = v1;
        v1 = v2;
        v2 = tmp;
    }
}

template sort(T, O) {
    T[] sort(inout T[] array, O comp)
        in {
            static assert(
            /*
                is (O == int function(T, T)) ||
                is (O == int delegate(T, T)) ||
                is (typeof(O.opCall(T,T)) == int())
            */
                is (typeof(O(T,T)) == int())
            );
        }
        body {  // 20年前に専門ガッコで習ったダサいソート
            for (size_t i = 0; i < array.length - 1; ++i) {
                for (size_t j = i + 1; j < array.length; ++j) {
                    if (comp(array[i], array[j]) > 0) {
                        swap(array[i], array[j]);
                    }
                }
            }
            return array;
        }
}

sort のテンプレート型引数と関数引数が２つあるが、これは無関係なものではないので、契約が必要である。
その契約だが、

                is (typeof(O(T,T)) == int())

の１行で、function, delegate, 関数オブジェクトの３つをまとめて面倒見ることができる。
もっともこれだと、これを見た人が function, delegate には思いが至っても、「関数オブジェクトもオッケーよ」ということが見えにくいので、コメントアウトしている律儀なバージョンの契約を使うのも悪くない。

C++ のテンプレートだと、型に対する要求が実装のあちこちにちらばってしまい、インスタンス化したときにわけの解らないメッセージ読まされることがあるが、D言語のだと要求を一箇所に明記できて便利である。STL の中見ると concept クラスをいっぱい定義してがんばってるみたいだけど。

あと組み込み配列のプロパティと同名の関数を定義して、

    array.sort(compFunc);

と呼ばせることができるかな？と心配だったが、ちゃんとディスパッチしてくれとるようです。
でもこれだと

「array」が「compFunc」を「sort」する

みたいに読めるので、

    array.sortBy(compFunc);

とかすべきだべか。

ともあれ実験。

import std.string;

// ソート対象クラス
class C {
    int id;
    char[] name;
    this(int id, char[] name) { this.id = id; this.name = name.dup; }
    char[] toString() {
        return "{" ~ std.string.toString(id) ~ "," ~ name ~ "}";
    }
    static C opCall(int id, char[] name) { return new C(id, name); }
}

// 比較関数群
template CCompare() {
    int cmpId(C lhs, C rhs)     // idでソート
        { return lhs.id - rhs.id; }
    int cmpName(C lhs, C rhs)   // nameでソート
        { return std.string.cmp(lhs.name, rhs.name); }
    int icmpName(C lhs, C rhs)  // nameで大文字小文字を区別しないでソート
        { return std.string.icmp(lhs.name, rhs.name); }
}

// 比較関数を持つオブジェクト
class CComparator {
    // 比較関数群をメンバ関数としてインスタンス化
    mixin CCompare;
    static CComparator opCall() { return new CComparator(); }
}

// 比較関数オブジェクト
class CCompareFunctor {
    int function(C, C) fpCompare;
    this(int function(C, C) fp) { fpCompare = fp; }
    int opCall(C lhs, C rhs) { return fpCompare(lhs, rhs); }
    static CCompareFunctor opCall(int function(C, C) fp) {
        return new CCompareFunctor(fp);
    }
}

// 比較関数をグローバル領域でインスタンス化
mixin CCompare;

ここまでが sort 材料。
結構長いですね。

以下ドライバ

import house.array;
import house.mbs;
import std.stdio;
import std.cstream;

void main() {

    C[] array = Array!(C)(
        C(3, "bbb"),
        C(2, "ccc"),
        C(1, "aaa"),
        C(6, "BBB"),
        C(5, "CCC"),
        C(4, "AAA")
    );
    writefln(array);

    dout.writeLine(_T("function でソート"));
    writefln(array.sort(&cmpId));
    writefln(array.sort(&icmpName));
    writefln(array.sort(&cmpName));

    dout.writeLine(_T("delegate でソート"));
    writefln(array.sort(&CComparator().cmpId));
    writefln(array.sort(&CComparator().cmpName));
    writefln(array.sort(&CComparator().icmpName));

    dout.writeLine(_T("関数オブジェクト でソート"));
    writefln(array.sort(CCompareFunctor(&cmpId)));
    writefln(array.sort(CCompareFunctor(&cmpName)));
    writefln(array.sort(CCompareFunctor(&icmpName)));
}

実行結果。

C:\d\test>dmd ..\house\mbs -run sort
[{3,bbb},{2,ccc},{1,aaa},{6,BBB},{5,CCC},{4,AAA}]
function でソート
[{1,aaa},{2,ccc},{3,bbb},{4,AAA},{5,CCC},{6,BBB}]
[{1,aaa},{4,AAA},{3,bbb},{6,BBB},{5,CCC},{2,ccc}]
[{4,AAA},{6,BBB},{5,CCC},{1,aaa},{3,bbb},{2,ccc}]
delegate でソート
[{1,aaa},{2,ccc},{3,bbb},{4,AAA},{5,CCC},{6,BBB}]
[{4,AAA},{6,BBB},{5,CCC},{1,aaa},{3,bbb},{2,ccc}]
[{4,AAA},{1,aaa},{6,BBB},{3,bbb},{5,CCC},{2,ccc}]
関数オブジェクト でソート
[{1,aaa},{2,ccc},{3,bbb},{4,AAA},{5,CCC},{6,BBB}]
[{4,AAA},{6,BBB},{5,CCC},{1,aaa},{3,bbb},{2,ccc}]
[{4,AAA},{1,aaa},{6,BBB},{3,bbb},{5,CCC},{2,ccc}]

よかじゃないですか。

ちなみに、icmp による文字の大小無視 sort 結果が２通りあるが、これは「安定ソート」なので、同一カテゴリ内の前後関係が sort 以前のものを保持しているためです。
組み込み配列プロパティの sort は残念ながら安定ソートではないようです。

こうなると比較関数だけでなく、アルゴリズムも sort に渡したいが、比較関数はアルゴリズムが呼び出すものなので、

    array.sort(algorithm(compfunc));

というコール形式になってしまう。

sort に比較関数を渡したい状況は多々あるかもだが、アルゴリズムを渡したい状況はそんなにないのよね。だが上記の形式だと、デフォルト(型)引数を使ってアルゴリズムを省略してコールすることはできない。
とすると、STL にならって、

    array.stable_sort(compfunc);
    array.merge_sort(compfunc);
    array.bubble_sort(compfunc);

とやるべきなのでしょうね。

2006-05-13

連想配列の同一性

Prog D言語

奇妙な現象に遭遇したので報告。

配列へのユーティリティ的なテンプレートをいろいろ書いていたが、連想配列についてはあまり追加したいほどの機能はあまり見当たらない。連想配列は辞書的な使い方が殆どだから、挿入、取出し、検索ができれば十分なので、組込みの opIndex と、in 式、remove メソッドがあれば十分だからである。

まぁ、配列にあって連想配列にないのは dup ぐらいかなぁと思い、以下のバカみたいなテンプレートを作成。

template dup(K, V) {
	V[K] dup(V[K] map) {
		V[K] new_map;
		foreach (K key, V value; map)
			new_map[key] = value;
		return new_map;
	}
}

で、実行。

import house.tostring;
import std.stdio;

unittest {
	int[char[]] map1;
	map1["A"] = 1;
	map1["B"] = 2;
	map1["C"] = 3;

	int[char[]] map2 = map1.dup();
	map1.ToString().writefln();
	map2.ToString().writefln();
}
...
[(A:1),(B:2),(C:3)]
[(A:1),(B:2),(C:3)]

よかたい、よかたい。

値の同一性をチェックしてみよう。

	writefln(map1 == map2);

...
false

ハイ？
なんで？？？

あわてて、式 - プログラミング言語 D (日本語訳)の「等値式」を見てみると、

・整数かポインタはビットパターンで
・浮動小数点の場合は複雑
・クラスや構造体オブジェクトであれば、opEquals で
・静的/動的な配列の等しさは、配列の長さが等しく、かつ、全ての要素が等しければ

と書いてあるがなるほど、連想配列の等値に関する記述はない。

念のため、

template equals(K, V) {
	bool equals(V[K] lhs, V[K] rhs) {
		return (
			lhs.length == rhs.length &&
			lhs.keys == rhs.keys &&
			lhs.values == rhs.values
		);
	}
}

というテンプレートを書いて

	writefln(map1.equals(map2));

とやってみたら

true

となった。

げ〜、どう見ても等値なのだがなぁ。

これは例えば、名前やIDをキーとした、２つの辞書の等値比較ができないということになる。
２つの連想配列を大小比較するのは意味がないけど、等値比較はできた方がいいと思うがなぁ。

2006-05-11

配列にメソッド追加

Prog D言語

id:kurimura さんとこの
2006-02-08

の第1引数が配列の関数は、配列のメソッドのように扱えるというの。
これがなんと template でもできた。
しかも ver0.149 から template の暗黙のインスタンス化がサポートされたので、記法もシンプル。

template max(T) {
  T max(T[] array) 
    in {
      assert(array.length != 0);
    }
    body {
      T maxValue = array[0];
      foreach (T elm; array) {
        if (maxValue < elm) maxValue = elm;
      }
      return maxValue;
    }
}

とかいうのが、

unittest {
  {
    static int[] array = [1, 2, 3];
    int maxval = array.max();
    writefln(maxval);
    foreach (int i; array) assert(maxval >= i);
  }

  writefln("OK unittest of max!(int)()");
}

といった使い方ができる。

但し、プロパティよろしく "()" を省略することはできない。
が、第1引数が配列の関数テンプレートを書くと、言語組み込みの配列にメソッドを追加した感じになっていい気分。
配列のユーティリティ的な関数テンプレートがみんなメソッド扱いにできる。

C++ の STL 的なものを作ってみたけど、D言語にはスライス式が使えるのでイテレータ的なものが欲しくなることはあまりない。あと、copy や for_each、transform もいらない感じ。
D言語はライブラリでなく言語でサポートしてる範囲が広いのでえぇなぁ。

2006-05-10

interface と Object

Prog D言語

なんのことはない。
interface は Object に(明示的に) cast できた。

2006-3-20 に書いた interface は Object として扱えないという問題も cast すれば殆ど問題にならない。

それにともない、もう変えないと言っていた文字列化関数を更新した。
interface の事前条件がなくなり、interface は無条件で文字列化可能になった。

template ToString(T) {
  char[] ToString(T value)
    in {
      static assert (!(
         is (T == function)  &&
        !is (T == char[](*)())
      ));
      static assert (!(
         is (T == delegate)  &&
        !is (T == char[] delegate())
      ));
      static assert (!(
         is (T == union)     &&
        !is (typeof(T.toString))
      ));
      static assert (!(
         is (T == struct)    &&
        !is (typeof(T.toString))
      ));
    }
    body {
      static    if (is (T : char[]))
        return value;

      else static if (is (T == char[](*)()))
        return value();

      else static if (is (T == char[] delegate()))
        return value();

      else static if (is (T == interface))
        return (cast(Object)value).toString();

      else static if (is (
        typeof(T.toString) == typeof(Object.toString)
      ))
        return value.toString();

      else static if (is (typeof(T.init.keys)))
        return MapToString!(
          typeof(T.init.keys[0]),
          typeof(T.init.values[0])
        )(value);

      else static if (is (typeof(T.init)[(T).length]))  
        return ArrayToString!(
          typeof(*T.ptr),
          (T).length
        )(value);

      else static if (is (typeof(T.init.ptr)))
        return ArrayToString!(typeof(*T.ptr))(value);

      else
        return std.string.toString(value);
    }
}