ClojureのArrayMapにnextした場合の挙動とコンテナ実装の内部構造について #Clojure

Clojure advent calendar 17日目です。遅刻組です。

ClojureのArrayMapをnextした場合の挙動から、Clojureランタイム、各interface、実装の理解を深めたいと思います。

ありがちなLispのコンテナの実装

ありがちな教科書的実装なLispでは、リストは2つのポインタをもった構造体から成り、ベクタはn個のポインタを格納できる配列から成る程度には表現が簡単です。そして、それらを組み合わせて遅延リストやハッシュテーブル、セットなどを作ります。そして、新しく作ったコンテナへのアクセスする関数を新たに定義します(lazy sequenceならlseq-carなど)。例えば、pairだけでなく、lazy sequenceもcarと言う名前の関数で1つめの要素にアクセスしたい場合は、carを新たに再定義して置き換える必要があります。Lispの名前空間の使い方によってはこの方法は難しいことがあります(少なくともR7RS Schemeなどでは)。そんなわけで実装ごとに操作するインターフェースフェースが用意されることがほとんどです。

Clojureのコンテナの実装

Clojureの各コンテナは、Javaのクラスで実装されています。
SequenceやLazySeq、PersistentList、PersistentArrayMap、PersistentVectorなどがあります。遅延シーケンスやリストで共通するfirst、nextのような操作は、それらを持たせたISeqなどのInterfaceをimprementsしています。それから、sequential?やsorted?等の性質の判定のために、PersistentVectorやPersistentListは、Sequentialを(間接的に)imprementsし、 PersistentTreeMapは、Sortedをimprementsしています。

Clojureのコンテナ周りは何を読めばよいのか

まず、map関数などの単純な操作を組み合わせてできるコンテナを操作する関数は、clojure.core(src/clj/clojure/core.clj)を見ればよいです。nextやassocなどの単純なコンテナ操作の関数はRuntime(src/jvm/clojure/lang/RT.java)とsrc/jvm/clojure/lang内の各コンテナの実装を見れば良いです。

PersistentArrayMapのnext

Clojureでは、リストだけでなくmapに対してもfirst,nextすることができます。

user=> (next {:a 3, :b 4})
([:b 4])

clojure.coreのnext関数は、中でRuntimeのnextメソッドを呼び出します。
RT.javaでは、次のような処理になっています。
与えたオブジェクトがISeq(をimprementsしたもの)であれば、そのnextを呼び出し、そうでなければISeqに変換してそのnextを返すようにしています。

static public ISeq next(Object x){
    if(x instanceof ISeq)
        return ((ISeq) x).next();
    ISeq seq = seq(x);
    if(seq == null)
        return null;
    return seq.next();
}

PersistentArrayMapはISeqではないので、seq()してnextします。PersitentArrayMapをseqすると、PersitentArrayMap独自のSeq実装を返します。

user=> (class (next {:a 1 :b 2}))
clojure.lang.PersistentArrayMap$Seq

このPersistentArrayMap$Seqは、first()するとkey,val対を返すようなものになっており、ArrayMapをその場で単純にListに変換するよりもメモリの効率がよくなるようになっています。
これは、ある種の遅延シーケンスのような挙動をしますが、countはArrayMapのもつ要素数から出すことができるので、全部舐めなくてよいという違いがあります。

    public Object first(){
        return MapEntry.create(array[i],array[i+1]);
    }

    public ISeq next(){
        if(i + 2 < array.length)
            return new Seq(array, i + 2);
        return null;
    }

    public int count(){
        return (array.length - i) / 2;
    }

参考までに、ArrayMap$Seqのarrayとは、ArrayMapのkey、value対を格納しているarrayであり、奇数番目がkeyで偶数番目がvalになっています。

終わりに

Clojureのコンテナの実装はとてもおもしろいので一度くらいは見てみるとよいと思います。