翻訳:"Inside Clojure's Collection Model"

The original article is written by Alex Miller (@puredanger). Translated by Keisuke Fukuda (@keisukefukuda)

この記事は,”Inside Clojure’s Collection Model”の日本語訳です.原著者のAlex Millerさんの許可を得て公開しています.翻訳に関する指摘は翻訳者まで.(athosさんありがとうございました)

Alex Millerさんは,Clojureの主要な開発者の一人であり,リリースマネージャの役割もされ,メーリングリストにおける活動量も非常に多い方です.また,Clojure Applied: From Practice to Practitionerの著者でもあります.

Clojureのコレクションについて,私(翻訳者)の記事「Clojureにおけるデータ構造の抽象化を理解して独自のデータ構造を実装する」も参照してください

Inside Clojure’s Collection Model

Clojureのコレクション型には何があるでしょうか?ほとんどのClojurianは,list, vector, map, setで十分だと言うと思います.seqを加えてもいいかもしれません.Seqは,コレクションの抽象化(View)で,コレクションを使って実装することもできるし,別の何かを使って実現することもできるものです.(この点についてはSequencesを見てください.)

しかし,Clojureにはsorted map, sorted set, queue, 組み込み型の配列,Javaの配列,Javaのコレクションなどなど,そしてもちろん deftype によるユーザー定義の型があります.ここまでくると,だいぶ話が込み入ってくるでしょう.そして,判定関数(sequential?, seq?, coll?)がこれらのコレクション型に対して返す値は,わけがわからないように見えるかもしれません.

少し調べるとわかりますが,コレクションには,一見してわかるよりも,込み入った事情があります.Clojureは,日々使われる基本機能を提供するために,いくつかの異なる層を提供しています.最も優れた点は,Clojureの機能(コンパイラ,ランタイム,標準ライブラリ)はコレクションの実装には全く依存せず,拡張可能な抽象化層の上に 構築されているという点です.Clojure初心者のうちはこれらの拡張機能に触ることはほとんどないでしょうが,より洗練されたプログラムを書くためにこれらの機能が有用だということが徐々にわかってくることでしょう.

Traitと判定関数

Clojureのコレクション・ライブラリの中で最も重要な層は,おそらくTraitでしょう(Traitというのは私独自の用語です).TraitはClojureのProtocolの機能を用いて実装されているのが理想ですが,これらの機能はProtocolの導入よりも前に遡るので,Javaのインターフェースとして定義されています.

重要なtraitクラスをいくつか紹介しましょう(すべてclojure.langパッケージにあります):

  • Counted - 数え上げ可能(加算*1)なコレクション
    • count()
  • Indexed - Countedをextendしていて,インデックスによる参照が可能
    • nth(int i)
    • nth(int i, Object notFound)
  • Sequential
    • シーケンシャルなコレクションのためのマーカーインターフェース
  • Associative (ILookupをextend)
    • containsKey(Object key)
    • entryAt(Object key)
    • assoc(Object key, Object val)
    • ILookup経由:
      • valAt(Object key)
      • valAt(Object key, Object notFound)
  • Sorted - 並べ替え済みコレクションのためのマーカー
  • Seqable*2 - sequenceを生成することができるコレクション
    • seq()
  • Reversible - 逆向きsequenceを生成できるコレクション
    • rseq()

それぞれのインターフェースは,コレクションが持ちうる特性・属性の一部を示しています.そして,ほとんどの判定関数は,それぞれのインターフェースをimplementしているかどうかをチェックしているに過ぎないということがわかります.

  • counted? - Countedをimplementしているか
  • indexed? - Indexedをimplementしているか
  • sequential? - Sequentialをimplementしているか
  • associative? - Associativeをimplementしているか
  • sorted? - Sortedをimplementしているか?
  • reversible? - Reversibleをimplementしているか

上の表で欠けているのはILookupSeqableです.ILookupは,Associativeの非常に小さなサブセットで,Associativeの方が汎用です.Seqableは少し厄介で,文字列や配列をseqableと判定するために,Clojureはちょっといろいろなことをやっています.もし当時Protocolが存在していれば,このような「閉じた型」についてもSeqableが直接的に実装されていたでしょう*3.これについては「Sequences」という記事を読んでください.

重要な事は,clojure.coreclojure.lang.RTにある集合関数のほとんどは,これらのtraitを操作するのであって,具体的なコレクションの型や,コレクションのインターフェースを操作するわけではないということです.

これを追いかけるのは少々大変です.ほとんどの標準のコレクション関数(count,nth, get, assoc, seq)は上記のインターフェースと明示的に対応しています.Clojureのcore関数のソースコードを見ると,それらのメソッドの殆どがRTクラスへ転送されていることがわかります.そしてRT.count()をみると,まず第一の実装として上記のインターフェースの関数が起動されています(そして,いくつかの特殊ケースについては特別な実装がされています).もう一度書きますが,もしProtocolを使えばこれらの実装はより綺麗になるはずです.

この実装の利点は,これらのtraitをいくつか実装した型を作れば,既存のClojureの実装に手を加えることなく,協調して動作することができるということなのです

Collections

Clojureのコレクションも,Javaインターフェースの実装が最初に行われています.大半のインターフェースは,コレクションがどのようなtraitsを持つかどうかを定義するものです. (実は,詳細については少し誤魔化しています.これらの実装が行われている実際のクラス階層は少々ややこしいからです).わかりやすい例は,IPersistentVectorで,これはAssociativeSequentialReversibleIndexedをextendしています.似たようなインターフェースとして,IPersistentSetIPersistentMapIPersistentListと,より上位レベルのIPersistentCollectionがあります.ここで説明はしませんが,それ以外にもclojure.corepeekpopを通して使用できるIPersistentStackがあります

最後に,多くの具体型があります(実際には,型ごとに複数存在しています)

  • IPersistentList
    • PersistentList - 普通のリスト
    • PersistentList$EmptyList - 特別な場合(空リスト)
    • PersistentQueue - キューの実装
  • IPersistentVector
    • PersistentVector - 普通のベクタ
    • MapEntry - 2要素のpersistent vectorとして振る舞うmapの要素
    • SubVector - subvecを通して生成される,元のベクタのview
    • clojure.core/Vec - 組み込み型のベクタの実装
  • IPersistentSet
    • PersistentHashSet - 普通のset
    • PersistentTreeSet - 並べ替え済みset
  • IPersistentMap
    • PersistentArrayMap - 0〜8要素の時に使われる配列ベースのmap
    • PersistentHashMap - 普通のhash map
    • PersistentTreeMap - 並べ替え済みmap
    • PersistentStructMap defstructから生成される(現在は実質的に廃止)
    • defrecordは,すべてIPersistentMapインスタンスを実装する

しかし,シーケンスについてはどうなのでしょう?ここでどのような役割を果たしているのでしょうか?ここから,話が少しややこしくなってくるのです

シーケンス

シーケンスは,論理的なイミュータブルコレクションを表します.シーケンスがコレクションから生成された時は,コレクションの上に構築されたシーケンスということになりますが(私はこれらのシーケンスを「コレクションのView」だと考えています),一方で関数から必要に応じて生成することもできますし,それ以外のデータから生成することもできます(文字列,配列,イテレータなど)

ここで重要なのは,シーケンスもまたJavaのインターフェースによって実装されているということです

  • ISeq - シーケンスの抽象化で,seq?判定関数でチェックできる
  • Seqable - (前述)シーケンスを生成することができるもの

ここでややこしいのが,ISeqIPersistentCollectionを実装しているということです.よって,シーケンスは実質的にコレクションとして扱うこともできますが,IPersistentListではありません.紛らわしいのは,シーケンスとリストはどちらも括弧を用いて表示されるということです.

コレクションの時の同じように,シーケンスの実装はたくさんあります

  • LazySeq 遅延シーケンス
  • Cons cons呼び出しの結果
  • ChunkedCons mapfilterなどのチャンクされた遅延シーケンスの結果
  • ArraySeq - 配列上のシーケンス
  • StringSeq - 文字列上のシーケンス
  • 他にもたくさん!
等価性

Clojureのコレクションは,等価性における種別(Equalily Partition*4)(sequential, map, set)に基づいて定義されています.等価性は,常に値の比較によっています:コレクション同士が等価性における同じ種別かどうか,そして同じ値を含むかどうか?ということです.

ここが,Clojureが他の言語と大きく異なる点です.Clojureのコレクションは 1) immutableであり 2) 値によって等価性が判定されます.この結果,Clojureのコレクションを値の合成として扱うことができ,イミュータブルで単純な値を使うことの利点を享受できるのです.

シーケンシャルなコレクション(list, vector, シーケンス,そしてsequentialであるとマークされたものであれば何でも)では,比較は先頭から末尾へ要素ごとに行われます.シーケンシャルなコレクションは,比較の際にコレクションの種類をチェックしません.

これは,場合によっては欲しい挙動ではないでしょう(例えば戻り値のテストをするときなど).しかし,比較においてシーケンシャルなコレクションを同一視することは,Clojureにおける利便性のための実用的で優れた選択で,特にシーケンスとコレクションの境界線を曖昧にすることに効果を発揮します.

Setは,完全に同一の集合で,互いに余計な要素を持たない時に等しいと判定されます(ここで「同一」といっているのは 「= 演算子trueを返す」という意味で,オブジェクトの同一性を指しているわけではありません).

Mapは,互いに同一のキーを持っていて,それぞれのキーが互いに同一の要素を返すときに等しいと判定されます.

まとめ

Clojureのコレクションが水面下でどのように実装され,抽象化を用いてどのように統合されているかということの概要を理解するのに,この記事が役立てば幸いです.これらの抽象化は,追加のコンポーネントを組み込むために使うことができますので,これは次の記事のテーマで扱うかもしれません.

2016年3月16日

Originally post written by Alex Miller Translated by Keisuke Fukuda

*1:訳注:Countableを直訳すると「加算」となるかもしれませんが,これだと数学の集合論の加算と紛らわしいので迷いました.

*2:訳注:「しーかぶる」と発音するらしいです

*3:訳注:Javaのインターフェースは,既存の型に後からインターフェースを追加で実装することはできません.これが,「閉じた」型と呼ばれています.一方,ClojureのProtocolは,既存の型(Javaの型であっても)を後から拡張することができます.これが「開かれた/拡張可能な」型ということです

*4:訳注:Equality Partitionの適切な邦訳はわかりません.どなたかご教授ください