読者です 読者をやめる 読者になる 読者になる

本当は怖い情報科学

情報系大学院生の趣味&実益ブログ。

Clojureにおけるデータ構造の抽象化を理解して独自のデータ構造を実装する Part 0: 導入

Clojureでのボトムアッププログラミングを支援する3つの性質

Lispプログラムを書く上での非常に有用な戦略に「ボトムアッププログラミング」がある。 この言葉の定義はいくつかあるが、ここでは「普通に特定の目的(アプリケーション)を書き下すのでは無く、その目的に有用なように言語自体を拡張していき、その言語を用いてプリケーションを記述する」とする。

ClojureCommon Lispを初めとするLisp系の言語は、以下の2つの特徴によって、プログラミング言語を「拡張」することが容易になっている。

1.S式構文:特別な構文を持たず、ユーザーが構文木を書き下すような文法を持つ。これにより、ユーザー定義のオペレーターが組み込みのオペレーターと同等の地位を持つ。

2.マクロ:構文を拡張することができる。

この議論はOn Lisp 等の書籍で詳しく触れられているので譲る。次に、Clojureボトムアッププログラミングを行おうとすると、もう1つの点を考慮することが重要だ。

3.データ構造の拡張:ユーザー定義のデータ構造が組み込みデータ構造と同等の地位を持つ

なぜなら、Clojureは「データ」を非常に重視したLispだからだ。ここでいう「独自のユーザー構造」とは、単に他の言語で言う「クラスを定義する」という意味ではない。ユーザーが定義したデータ構造が、Clojure組み込みのcollectionやseqと同等に振る舞い、map, filter, assoc, reducersを初めとする組み込み関数群を同等に適用できるという意味だ。

Clojureでのデータ構造の利用

実は、Clojureにおいては、独自の(RubyJavaでいう)クラスを定義することは推奨されていない。

"It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures." - Alan J. Perlis

という言葉からもわかるように、限られたデータ構造を用いて、それらに対する豊富な関数を提供するというのがClojureの方針だ。だから、Clojureでは基本的に、map,set,vector等の組み込み型をそのまま利用することが推奨されている。

とはいえ、独自のデータ構造が必要である場合もある。特にライブラリを書くときには、理想的なのは「独自のデータ構造や特殊な処理を内包したデータ構造でありながら、表面的な振る舞いとしては既存のデータ構造(vector, list, map, etc.)と同等に振る舞うこともできる」というものだ。そうすれば、ライブラリのユーザーの学習コストは低く、また既存の豊富な関数群を適用することができる。

現在のClojureでは、(残念ながら)それは簡単とは言えない。既存のcollection/seqと同等に振る舞うデータ構造を定義するためには、Clojure内部の実装に立ち入って理解をする必要があるからだ。

これから書く一連の記事では、Clojureの組み込みcoll/seqと同等に振る舞うことができるデータ構造の定義の仕方を調べていく。最終的にはそのようなデータ構造を簡単に定義できるライブラリ(マクロ)を定義するところまで進みたい。

プログラムの例

以下のようなプログラムを考える。基本的にはvectorとして定義できるが、一部の属性値については計算が重いためにfutureを用いた遅延評価/並列化をしたい。そのようなデータ構造は普通に定義すれば以下のようになるだろう。

(defn heavy-computation [a]
  (Thread/sleep 10000)
  a)

(defn myfunc []
  [:a
   (future :b)
   (future (heavy-computation :c))
   :d])

(defn -main [& args]
  (time
   (let [v (myfunc)]
     (println (get v 0))
     (println (get v 1))
     (println (get v 2))
     (println (get v 3)))))

=>  :a
    #object[clojure.core$future_call$reify__6736 0x1151e434 {:status :ready, :val :b}]
    #object[clojure.core$future_call$reify__6736 0x2d710f1a {:status :pending, :val nil}]
    :d
    "Elapsed time: 18.88949 msecs"

(defn -main [& args]
  (time
   (let [v (myfunc)]
     (println (get v 0))
     (println @(get v 1))
     (println @(get v 2))
     (println (get v 3)))))
=>  :a
    :b
    :c
    :d
    "Elapsed time: 10013.299227 msecs"

これをユーザーから使う場合、属性:bと:cにアクセスするときはderefをする必要がある。 専用のアクセス関数を提供すれば良いが、しかしそれではデータをvectorとして表現していることの 利点が失われてしまう。そこで、組み込みのvectorと完全に同等に振る舞うが、内部ではfutureを用いた遅延・並行処理が 行われるように改造したい。

これを行うためには、vectorやmapのデータ構造が内部的にどのように実装されているかを知る必要がある

(Part 1に続く)

※書きためはしてないので、のんびり更新です

On Lisp

On Lisp

【広告】