私は何年にもわたって、Java アプリケーションでドメイン・オブジェクトのツリーを使ってきました。最近ではこれらのツリーを Clojure で使うようになりましたが、いずれにしても、データのツリーを操作するには Visitor パターンが信頼できる手段であると実感しています。けれども、関数型言語とオブジェクト指向言語とでは、Visitor パターンが機能する仕組み、そしてこのパターンによってもたらされる結果に違いがあります。

この記事ではドメイン・ツリーと、Java 言語での Visitor パターンについて説明した後、Clojure を使用して実装したいくつかのビジターを順に見ていきます。関数型言語である Clojure は、データの照会と操作に新たな手法をもたらします。特に、関数型 zipper を Visitor パターンに統合することで、効率性が向上するというメリットがもたらされることがわかりました。このメリットについては、記事で詳しく探ります。

シンボリック・ツリーの操作

シンボリック・ツリーの一例は、SQL クエリー・プランの表現です。SQL クエリー・プランには、レコードの抽出、テーブルの結合、クエリーの結合、表示列の選択などの操作が含まれており、これらの操作が組み合わされて、ソース・データからクエリーの実行結果を生成する一連の処理が作られます。

例えば、リスト 1 のクエリーは、Dept テーブルと Employee テーブルの結合を表すクエリーです。このクエリーは部門名が「IT」であるレコードを結果として抽出し、従業員のファースト・ネームとラスト・ネームを連結して返します。その結果は、IT 部門のすべての従業員のフルネームとなるはずです。

SELECT Employee.First || ' ' || Employee.Last
FROM Dept, Employee
WHERE Dept.ID = Employee.Dept_ID
  AND Dept.Name = 'IT'

次に、上記のクエリー・プランに相当する、図 1 のシンボリック・ツリー表現について説明します。概念的には、リレーショナル・データの行 (タプル) はクエリー・プランの操作ノードを下から上へと進んで行きます。そして最上位のノードから、最終的なクエリーの実行結果が取得されます。

このようなノードのツリーを使用する場合には、ツリーでの複数の操作をまとめて 1 つの操作として実行する必要があります。個々の操作としては、以下に挙げる操作が考えられます。

• クエリー・プランで参照されるすべての表を収集する
• サブツリーで使用されるすべての列を収集する
• クエリー・プランの最上位の結合ノードを見つける
• ツリーをパターンと突き合わせて、ツリーを変更する

最後の操作は、ツリーでシンボリック操作を行うために使用できるため、とりわけ役に立ちます。例えば「フィルター・プッシュダウン」というパターンを使用する場合には、まず上記の図でツリーとパターンの突き合わせを行い、マッチする箇所があれば、その箇所でツリーを変更します。突き合わせる「フィルター・プッシュダウン」パターンの内容は以下のとおりです。

• JOIN ノード J の真上にある FILTER ノード F
• F が使用する基準は、1 つのテーブルにしか関連しない
• J は内部結合である

この突き合わせの後に行うツリーの操作では、FILTER ノードを JOIN ノードの下かつ関連する TABLE ノードがある側へ移動することができます。データベース・クエリー最適化プログラムの中核となるのは、このような (適切なリレーショナル理論に裏付けられた) 操作です。図 2 に、ツリー操作を適用した後のツリーを示します。

Visitor パターンはデータ構造 (この例ではツリー) を、そのデータ構造を操作するアルゴリズムから切り離すために使用するのが通常です。記事ではこの後、Java コードでのオブジェクト指向の実装、続いて Clojure での関数型の実装について具体的に説明します。

上に戻る

Java 言語でのビジター

Java で Visitor パターンを実装するとしたら、まず始めにノードを Java クラスで表現する必要があります。基本的な階層は、図 3 に示すように構成することができます。これらのクラスのほとんどは、単純なデータ・ホルダーです。例えば Join クラスには左結合式、右結合式、結合タイプ、結合基準が格納されます。

ドメイン階層を構成するすべてのオブジェクトは共通して、Visitable インターフェースと以下のような acceptVisitor メソッドを実装することに注意してください。

public void acceptVisitor(Visitor visitor) {
  visitor.visit(this);
}

上記の acceptVisitor メソッドは、具象オブジェクトの型だけでなく、ビジターの型にも依存したメソッド呼び出しを選択できるように、「ダブル・ディスパッチ」を実装します。

ビジター・クラスは図 4 に示されています。ベースとなる Visitor インターフェースには、ドメイン内のすべての具象型を対象とした visit メソッドがあります。AbstractVisitor はこれらの visit メソッドの空のバージョンを実装し、具体的なビジターを容易に作成できるようにします。

ビジター・ナビゲーション

ビジターは各ノードにアクセスすることに加え、現在アクセスしているノードの配下にあるどの子ノードにアクセスするかも決定しなければなりません。各ビジターの中にナビゲーションを組み込むことも可能ですが、ナビゲーションと操作は別々の問題として切り分けておくほうが賢明です。実際、ノードの型ごとに子を見つける作業は、ビジターの中にカプセル化することが可能なビジター操作であると考えることができます。そこで、NavigationVisitor にツリーのナビゲーション操作を取り込んで、より軽量なビジターを使えるようにします。

NavigationVisitor に含まれるメソッドを見てください。

public void visit(Join j) {
    visitor.visit(j);
    j.getCriteria().acceptVisitor(this);
    j.getLeft().acceptVisitor(this);
    j.getRight().acceptVisitor(this);
  }

NavigationVisitor は別のビジター・インスタンスに従う一方で、子ナビゲーションを組み込みます。ビジターの一例として、ツリー全体ですべての Column インスタンスを収集するビジターのコードは、リスト 2 のようになります。

package visitors;

import java.util.HashSet;
import java.util.Set;

import visitors.domain.Column;

public class CollectColumnsVisitor extends AbstractVisitor {
  private final Set<Column> columns = new HashSet<Column>();
  
  public Set<Column> getColumns() {
    return this.columns;
  }
  
  @Override
  public void visit(Column c) {
    columns.add(c);
  }
}

このビジターはツリー内で Column を検出するたびに、検出済みのすべての列のセットにそのインスタンスを格納します。ビジターがナビゲーションを完了した時点で、リスト 3 の呼び出しによって、完全な Column 一式を取得することができます。

Node tree = createTree();
CollectColumnsVisitor colVisitor = new CollectColumnsVisitor();
NavigationVisitor v = new NavigationVisitor(colVisitor);
tree.acceptVisitor(v);
System.out.println("columns = " + colVisitor.getColumns());

この基本構造があれば、後は以下のどの最適化を追加することも可能です。

• 事前ナビゲーション、事後ナビゲーション、またはカスタム・ナビゲーションを行うナビゲーション・ビジター
• ツリー全体の探索の回避
• 巡回中のツリーの変形

上に戻る

Java ビジターに伴う複雑さ

Java 言語での Visitor パターンは、Philip Wadler 氏が名付けた「Expression Problem」という古典的な問題をある程度解決します。Expression Problem では、プログラムのデータを一連のケース (型) と、これらのケースに対する一連の操作として定義します。これらの型および操作を 2 次元の表として考えた場合、再コンパイルなしで新しいデータ型と新しい操作を追加し、静的な型を維持することができるのでしょうか？

Visitor パターンのシナリオでは、既存のデータ型のセットに簡単に操作 (新規ビジター) を追加することができますが、Visitor パターンではすべての具象型に visit() メソッドが必要となるため、新しいデータ型 (クラス) をビジターと一緒に追加するのは困難です。この問題は、抽象スーパークラスにすべてのビジターのすべてのメソッドの空の実装を含めることで、ある程度軽減することができます。こうすれば、抽象クラスを変更してコードをコンパイルするだけで済みます。ビジターは、再コンパイルなしの標準を満たしませんが、新しい操作を追加するために必要な変更は最小限になります。さらに、新規データ型を追加するケースが、新しい操作を追加するケースに比べると遥かに少ないことを考えれば、このパターン全体がまずまずの妥協案となります。新しい操作をすべての具象型の新しいメソッドにエンコードするよりは、確実にましです。

Java 言語で Visitor パターンを実装すると、基本的な目標を達成できるとは言え、それには複雑さも伴います。その複雑さとは、すべての具象クラスに、定型の visit() メソッドでナビゲーション・ビジターなどを定義しなければならないことです。JVM 上でプログラミングしつつも、この付随的な複雑さを回避するには、Clojure の関数型プログラミング・ツールを利用して Visitor パターンを実装することが 1 つの方法となります。

上に戻る

Clojure でのツリー

Clojure は、永続的で不変のデータ構造のコア・セットとして、リスト、ベクトル、マップ、セット、およびキューを提供します。ここで言う「永続的」とは、データ・ストレージのことではなく、データの変更に関する性質を表していることに注意してください。

永続的なデータ構造が「変更」された場合には、そのデータ自体が変更されることはなく、代わりに新しい不変のデータ構造が返されます。Clojure の永続的なデータ構造を効率化するために使われている手法は、「構造共有」です。構造共有はデータの不変性を利用して、データの新旧インスタンスの間での共有を可能にします。

不変性があると、並行性についてより単純に考えることや、コストの低い共有データの読み取り操作を行うことも可能になります。データが不変であれば、データを読み取る際にロックを獲得する必要がないからです。他のスレッドがデータを「変更」すると、おそらくほぼ同じ内部構造の別のデータ・インスタンスが生成されます。関数型プログラミング言語では、副次的な影響のない純粋な関数を作成するためにも、永続的なデータ構造が重要となっています。

Clojure の永続的なデータ構造

最も簡単な演習は、基本的なデータ構造の 1 つである連結リストを永続的にすることです。Clojure で作成された以下のリストは、a という変数にバインドされます。

(def a (list 1 2 3))

Clojure は Lisp の方言であるため、式の評価は、最初に式を Clojure データ構造 (通常はリスト) として読み取り、それからデータ構造に含まれる式のそれぞれを評価することによって行われます。そして最後に、リスト内の最初の項目が関数で、残りの項目が関数の引数であるものとして、この関数を呼び出すと、def という特殊な形式により、名前空間付きの変数が作成されます。この変数を識別するのは、先頭の記号とその後に値として続く式です。この連結リストの各値を保持するセルには、値と次のセルへのポインター (リストの最後の値である場合は空) が保持されます (図 5 を参照)。

このリストの先頭に新しい値を追加する操作は、新規リストの作成 (つまり cons) 操作として知られています。値が追加された新しいリストは、元のリストのすべてのセルを共有します。

(def b (cons 4 a))

リストの先頭に追加された値以外の部分にアクセスするには、rest やその他の関数を使用しますが、元のリストから作成された新しいリストは、元のリストの構造を引き継ぐことに変わりはありません。リスト (およびリスト以外の値のシーケンス) を操作するための重要な関数には、first (先頭の項目を返す関数) と rest (残りの項目のリストを返す関数) の 2 つがあります。

(def c (cons 5 (rest a)))

Clojure のデータ構造を使用するときと Java のデータ構造を使用するときの重要な違いは、Clojure ではデータ構造を直接変更しないことです。Clojure では、更新を記述し、その変更内容を反映した不変のデータ構造への新しい参照を受け取ります。ツリーを構成するノードのそれぞれが不変のデータ構造であることを考えると、ツリー全体を変更することなく、ツリー内部のノードを変更する方法を検討しなければなりません。

ツリーのノード

ツリー操作の問題について検討する前に、ツリーの各ノードを定義するために使用するデータ構造について検討してみましょう。まず、ノードの型ごとに明確に定義されたプロパティーのセットが必要です。また、ツリーの各ノードに Clojure で認識できる型が定義されていれば、実行時に関数実装を選択するために利用することができます。

Clojure でキーと値のセットを表すためのデータ構造として当然の選択肢となるのはマップです。このキーと値のペアを格納するマップを作成する方法、マップに値を追加する方法、そしてマップから値を取得する方法をリスト 4 のサンプル・コードに示します。

user> (def alex {:name "Alex" :eyes "blue"})
#'user/alex
user> alex
{:name "Alex", :eyes "blue"}
user> (:name alex)
"Alex"
user> (assoc alex :married true)
{:married true, :name "Alex", :eyes "blue"}
user> alex
{:name "Alex", :eyes "blue"}

マップ内の各キーは、Clojure のキーワードです。Clojure のキーワードは、どこから呼び出しても評価される対象が同じであるため、同一の結果が得られます。キーワードをマップ内のキーとして使用するのは Clojure では慣習的な方法となっています。キーワードは関数でもあります。マップによって呼び出されたキーワード関数は、マップ内で自身を検索し、そのキーワードが持つ値を返します。

マップに項目を追加するには、assoc (「associate (関連付け)」) を使用し、項目を削除するには dissoc (「dissociate (関連解除)」) を使用します。マップを出力すると、マップの各項目がコンマで区切られていることがわかりますが、これは純粋に読みやすさを目的としたものです。Clojure では、コンマはホワイト・スペースとして扱われます。リスト 4 の最後では assoc がリターンして、新しいマップを出力しますが、元のマップは変更されません。この 2 つのマップは同じデータのほとんどを構造的に共有します

型付けされたマップ

リスト 5 に記載するいくつかのヘルパー関数は、お馴染みの :type キーを設定したマップを作成するために使用されます。この型は、後でポリモーフィズムを使用した振る舞いをディスパッチするために使用します。node-type 関数は、:type キーを基準にノードの「型」を抽出します。

(ns zippers.domain
  (:require [clojure.set :as set]))

(defn- expected-keys? [map expected-key-set]
  (not (seq (set/difference (set (keys map)) expected-key-set))))

(defmacro defnode
  "Create a constructor function for a typed map and a well-known set of
   fields (which are validation checked). Constructor will be
     (defn new-&node-type> [field-map])."
  [node-type [& fields]]
  (let [constructor-name (symbol (str "new-" node-type))]
    `(defn ~constructor-name [nv-map#]
       {:pre [(map? nv-map#)
              (expected-keys? nv-map# ~(set (map keyword fields)))]}
       (assoc nv-map# :type (keyword '~node-type)))))

(defn node-type [ast-node] (:type ast-node))

リスト 5 には、これまでに見たことのない新しい拡張機能が多々あるかもしれませんが、慌てないでください。このコードは、Lisp または Clojure の上級プログラマー向けに記載したのであって、細かいところまですべてを理解する必要はありません。このコードのコアとなっているのは defnode マクロです。このマクロが、ノードの型とフィールド名のベクトルを取り、その型のマップを作成するためのコンストラクター関数を作成します。コンストラクターが呼び出されると、コンストラクターは渡されたフィールドをチェックして、期待されるフィールドと一致するかどうかを判別します。期待されるフィールドでない場合には、エラーをスローします。Lisp 方言としての Clojure のメリットの 1 つは、コードとデータが同じ形式で表現されることです (これは、同図像性 (Homoiconicity) とも呼ばれます)。マクロはこのメリットを利用するために、コードをデータとして操作した上で、コードを評価します。

リスト 6 に、Java ドメイン・クラスに相当する Clojure のドメイン・タイプを実装します。

(defnode column [table column])
(defnode compare-criteria [left right])
(defnode concat [args])
(defnode filter [criteria child])
(defnode join [type left right])
(defnode project [projections child])
(defnode table [name])
(defnode value [value])

ツリーの探索

ここで問題となるのは、Clojure マップのツリーを取り、そのツリーをトラバースまたは操作することです。Clojure ツリーは不変のデータ構造であるため、操作する場合には新しく変更されたツリーを返す必要があります。最初のステップとして、Java 言語での Visitor パターンの実装を振り返り、同じような実装を試してみることができます。したがって、ここで必要となる作業は、「マップのツリーを探索し、ツリー内でパターンを検索し、パターンが見つかった箇所でツリー操作を適用する」という操作を定義することです。

例えば、引数のすべてが文字列リテラル値の concat 関数を検索し、これらの引数を 1 つの文字列値に連結するとします (図 8 を参照)。

Java の Visitor ソリューションと同じように、マルチメソッドを使用すれば、ツリー内のすべてのノードの型に対する eval-concat 操作を実装することができます。Clojure でのマルチメソッドは、呼び出しが 2 つのステップに分かれた特殊な関数です。この関数が呼び出されるときには、まず、その引数を使用してカスタム・ディスパッチ関数が評価されます。次に、評価結果の dispatch-value を使用して、選択可能な複数の関数実装のうちの 1 つが選択されます。

(defmulti <function-name> <dispatch-function>)
(defmethod <function-name> <dispatch-value> [<function-args>] <body>)

マルチメソッドを定義するには、defmulti と defmethod という 2 つのマクロを使用します。この 2 つのマクロは <function-name> によってバインドされます。defmulti マクロが指定するのは、最初に呼び出されたときに使用するディスパッチ関数と、その他いくつかのオプション機能です。defmethod には複数の実装があり、そのそれぞれが、実行をトリガーする dispatch-value と、トリガー時に実行する関数の本体を指定します。

型に基づくディスパッチ

Clojure で最もよく使われているディスパッチ関数は、単なる class 関数です。この関数実装は、マルチメソッドに渡された関数の引数の型だけに基づいて呼び出されます。

この例では、ノードのそれぞれがマップなので、node-type 関数を使用して、各ノードを表すマップの型を区別する必要があります。型が区別されるようになったら、処理対象とする型ごとに、defmethod を使用してマルチメソッドの実装を作成します。

ディスパッチ関数でマルチメソッドの型と一致するノードが判別されない場合は、:default ディスパッチ値が呼び出されます (この値が存在することが前提です)。この例では :default 実装を使用して、リストアップされないノードは変更されずにそのまま返されるように指定します。これは、典型的な Visitor パターンでの基底 Visitor クラスと同じく、基本ケースとして役立ちます。

リスト 7 に、eval-concat マルチメソッドの完全な実装を記載します。この例で使用されている new-concat やnew-compare-criteria などの関数は、リスト 5 で呼び出した defnode マクロによって作成されたものです。

(defmulti eval-concat node-type)
(defmethod eval-concat :default [node] node)
(defmethod eval-concat :concat [concat]
           (let [arg-eval (map eval-concat (:args concat))]
             (if (every? string? arg-eval)
               (string/join arg-eval)
               (new-concat {:args arg-eval}))))
(defmethod eval-concat :compare-criteria [{:keys (left right) :as crit}]
           (new-compare-criteria {:left (eval-concat left)
                                  :right (eval-concat right)}))

リスト 8 は、eval-concat マルチメソッドの使用例です。この例では少数のノードからなるツリーを作成した後、これらのノードで eval-concat マルチメソッドを実行して文字列リテラルの concat を見つけ出し、それを連結した文字列で置き換えます。

(def concat-ab (new-concat {:args ["a" "b"]}))
(def crit (new-compare-criteria {:left concat-ab
                                 :right "ab"}))

(eval-concat crit)

リスト 7 の eval-concat は、ここで取り組んでいる問題を部分的にしか解決しないことに注意してください。問題を完全に解決するためには、式を保持する可能性のあるあらゆるクラスに defmethod を作成し、concat ノードを作成する必要があります。これは難しいことではありませんが、面倒な作業です。

具体的に言うと、このソリューションの「重荷」のほとんどは、データ構造のトラバースに関連します。実際にツリーを変更する操作はすべて、:concat defmethod の中に隔離されています。データ構造のトラバースについても、汎用操作として独立させたほうが得策でしょう。

clojure.walk によるデータのトラバーサル

Clojure のコア API に含まれている clojure.walk ライブラリーは、データ構造のトラバース専用のライブラリーです。このライブラリーの機能がベースとしているのは walk というコア関数ですが、walk が直接呼び出されることはめったにありません。それよりも、このライブラリーの機能にアクセスする手段として遥かによく使われているのは、prewalk および postwalk 関数です。この 2 つの関数は、両方ともツリーに対して深さ優先探索を行いますが、親ノードにアクセスした後に子ノードにアクセスするか、それとも子ノードにアクセスしてから親ノードにアクセスするかという点が異なります。いずれのバージョンでも関数を取り、置換ノード (または元のノード) を返す各ノードでその関数を適用します。

一例として、リスト 9 に異種混同のデータからなるツリーを操作する postwalk を記載します。このリストでは、最初にツリーを探索して関数を渡します。この関数は、アクセスしたノードを出力して、そのノードを返すだけに過ぎません。続いて postwalk を呼び出して関数を渡します。この関数は、整数を検索してその値を 1 だけインクリメントし、それ以外はそのままの状態に残す関数です。

user> (def data [[1 :foo] [2 [3 [4 "abc"]] 5]])
#'user/data

user> (require ['clojure.walk :as 'walk])
nil

user> (walk/postwalk #(do (println "visiting:" %) %) data)
visiting: 1
visiting: :foo
visiting: [1 :foo]
visiting: 2
visiting: 3
visiting: 4
visiting: abc
visiting: [4 abc]
visiting: [3 [4 abc]]
visiting: 5
visiting: [2 [3 [4 abc]] 5]
visiting: [[1 :foo] [2 [3 [4 abc]] 5]]
[[1 :foo] [2 [3 [4 "abc"]] 5]]

user> (walk/postwalk #(if (number? %) (inc %) %) data)
[[2 :foo] [3 [4 [5 "abc"]] 6]]

postwalk と prewalk を使用することにメリットがある理由は、この 2 つは Clojure のほぼすべてのコア・データ構造 (ベクトル、セット、およびマップなど。ただし、ソートされたマップおよびレコードは除きます) の探索方法を理解しているためです。clojure.walk を使用する場合、ナビゲーション・コードを指定する必要はありません。ノードを探して変更するために必要なコードを提供するだけでよいのです。

postwalk をリスト 10 の eval-concat の問題に適用してみましょう。このリストでは、:concat 型のノードを見つけたら、そのノードを評価して元の :concat ノードの代わりに新しい値のノードを返せるかどうかを調べます。

(defn eval-concat [node]
  (if (and (= :concat (node-type node))
            (every? string? (:args node)))
     (string/join (:args node))
     node))

(defn walk-example
  [node]
  (walk/postwalk eval-concat node))

遥かに満足のいく実装になりました。トラバーサルはすべて postwalk 内部で処理されるため、ツリーを検索して直接変更する関数を提供するだけで済みます。

Visitor パターンにおける再帰

元の Visitor パターンでも、postwalk を使用した上記の実装でも共通する問題は、パターンが再帰的であることです (図 9 を参照)。ノードで変更関数を評価すると、親ノードのトラバーサルはすべてスタック上に格納されます。これは、Visitor 実装での eval-concat 関数の再帰的呼び出しを見れば明らかです。けれども、これらの再帰的呼び出しのすべてを postwalk の中に隠したとしても、構造は変わりません。

再帰は必ずしも悪いことではありません。再帰は理解しやすく、小さなツリーでは問題にならないはずです。その一方、ツリーの規模が大きい場合には、メモリーを確保するために、反復的なトラバースのほうが望まれます。問題は、再帰のない Visitor パターンを実装できるかどうかです。

Clojure の関数型 zipper

関数型プログラミングでツリーのトラバースおよび変更の問題を解決する方法としてよく知られているのは、Gérard Huet 氏が考案した有名な zipper です (「参考文献」を参照)。zipper は、現行のコンテキストからのナビゲーション (反復処理) や変更のほとんどが一定時間で行われるように、ローカル・コンテキストでデータ構造を表現する方法です。すべての変更はコンテキストに対してローカルで行われます。

ツリーの zipper は一般に、ツリー内でのルートから現在の場所へのパスと、焦点が置かれたノードでのサブツリー・コンテキストで構成されます。「zipper」という名前は、ジッパーのようにツリーを上下に移動することを意味します。焦点ノードから上の部分は、ジッパーが開いている部分、その下のジッパーが閉じられている部分がローカル・ステートとなります。

典型的なツリーでは、一定時間でアクセス可能なのはルート (他のコードによって参照されるノード) からのアクセスだけです。zipper は、焦点ノードをツリー内で移動させて、どの位置に対しても一定時間で (そのノードに到達するまでのトラバーサル時間は含みません) アクセスできるようにします。zipper は一般的に、輪ゴムでできたツリーのようなものとして考えられています。任意のノードでツリーを「つまむ」と、その焦点を当てたノードがルートのようになり、そこから左右のパスと親パスがぶら下がった形になります。

焦点ノードのデータ構造は、一般にロケーション (あるいは「loc」) と呼ばれます。ロケーションには、現在のサブツリーとルートへのパスが含まれます。図 8 の小さなツリー構造を例に、これをマップではなく、ベクトルで単純化する方法を検討してみましょう。

図 10 に、ツリーを下 (常に左にある最初の子)、右、さらにその下へとトラバースするにつれ、ロケーション構造が変化する様子を示します。新しいノードにトラバースすると、そのノードが焦点となり、ツリーの残りのノードはその焦点ノードを基準に左側ノード、右側ノード、親ノードとして表現されます。

ツリーをトラバースする際には、変更は現在の焦点ノードに対してローカルに行われます。つまり、焦点ノードから上のノードを除き、すべての変更は一定時間の操作となります。これが、zipper がもたらす重要なメリットです。

Clojure での zipper

Clojure のコア API には、簡潔な zipper の実装が clojure.zip に含まれています。リスト 11 に、clojure.zip の API を記載します。このリストでは、API の機能をコンストラクション (Construction)、コンテキスト (Context)、ナビゲーション (Navigation)、列挙 (Enumeration)、変更 (Modification) のカテゴリーに分けて記載しています。

コンストラクション (Construction) カテゴリーに分類される関数では、新しい zipper (つまり、ロケーション) を作成することができます。新規 zipper を作成するためのコア関数は zipper です。この関数がベースとする主要な関数には、以下の 3 つがあります。

• branch?: ノードを引数に取り、そのノードが子を持てるかどうかの結果を返します。
• children: ノードを引数に取り、そのノードの子を返します。
• make-node: ノードを引数に取り、新しい子のセットを作成して、新規ノード・インスタンスを返します。

seq-zip、vector-zip、および xml-zip 関数は、それぞれシーケンス、ベクトル、XML ツリーに事前定義された実装を使用して zipper を呼び出すヘルパー関数です (この事前定義された実装は、XML を構文解析しません。というのも、clojure.xml/parse によって出力された、XML を表現するデータ構造を要求するためです)。

;; Construction
(zipper [branch? children make-node root]) - creates new zipper
(seq-zip [root]) - creates zipper made from nested seqs
(vector-zip [root]) - creates zipper made from nested vectors
(xml-zip [root]) - creates zipper from xml elements 

;; Context
(node [loc]) - return node at current location
(branch? [loc]) - return whether the location is a branch in the tree
(children [loc]) - return the children of a location’s node
(make-node [loc node children]) - make a new node for loc with the old node and the new 
   children
(path [loc]) - return a seq of nodes leading to this location from the root
(lefts [loc]) - return a seq of nodes to the left 
(rights [loc]) - return a seq of nodes to the right

;; Navigation
(left [loc]) - move to left sibling or return nil if none
(right [loc]) - move to right sibling or return nil if none
(leftmost [loc]) - move to leftmost sibling or self
(rightmost [loc]) - move to rightmost sibling or self
(down [loc]) - move to the leftmost child of the current location
(up [loc]) - move to the parent of the current location
(root [loc]) - move all the way to the root and return the root node 

;; Enumeration
(next [loc]) - move to the next node in a depth-first walk 
(prev [loc]) - move to the previous node in a depth-first walk
(end? [loc]) - at end of depth-first walk

;; Modification
(insert-left [loc item]) - insert a new left sibling
(insert-right [loc item]) - insert a new right sibling
(insert-child [loc item]) - insert a new leftmost child under current node
(append-child [loc item]) - inserts a new rightmost child under current node
(replace [loc node] - replaces the current node with a new node 
(edit [loc edit-fn args]) - replace the current node with the results of edit-fn
(remove [loc]) - remove the current node and moves to the previous node in a depth-first 
   walk

コンテキスト (Context) カテゴリーに分類される関数は、ツリー内での現在のロケーションに関する情報を提供します。ナビゲーション (Navigation) カテゴリーの関数については、前述の説明から簡単に理解できるはずです。リスト 12 に一例として、コンテキストおよびナビゲーション・カテゴリーの関数を使用して、ツリーを探索して検査する方法を示します。

> (def vz (zip/vector-zip [:compare [:concat "a" "b"] "ab"]))
> (println (zip/node (zip/down vz)))
:compare
> (println (zip/rights (zip/down vz)))
([:concat a b] ab)
> (println (zip/node (zip/right (zip/down vz))))
[:concat a b]
> (println (zip/node (zip/down (zip/right (zip/down vz)))))
:concat

zipper の反復処理

zipper の列挙 (Enumeration) カテゴリーに分類される関数は、ツリー全体を深さ優先順でトラバースするために使用することができます (図 11 を参照)。このトラバーサルの興味深い点は、再帰的ではなく、反復型のトラバーサルであることです。これが、zipper のトラバーサルと前のセクションで説明した clojure.walk 実装との重要な違いです。

zipper を使用したツリー・ビジター

zipper の列挙と zipper edit 関数は zipper ベースのビジターを作成するツールとなり、この zipper ベースのビジターは、ツリーを反復処理して各ノードで visitor 関数を実行します。これらのツールは、リスト 13 のように 1 つに組み合わせることができます。

(defn tree-edit [zipper matcher editor]
  (loop [loc zipper]
    (if (zip/end? loc)
      (zip/root loc)
      (if-let [matcher-result (matcher (zip/node loc))]
        (recur (zip/next (zip/edit loc (partial editor matcher-result))))
        (recur (zip/next loc))))))

tree-edit 関数は、zipper 構造、matcher 関数、そして editor 関数を引数に取ります。この関数はまず Clojure の特殊な loop を開始し、その loop では関数の最後に recur のターゲットを作成します。Clojure での loop/recur は末尾再帰を意味し、他の再帰呼び出しのようにスタック・フレームを使用しません。zip/next 呼び出しは、ツリーの深さ優先探索での次のノードを反復処理します。

zip/end? が true を返すと、反復処理が終了します。その時点で、zip/root は zip/up を実行してツリーの最上部に移動し、それまでに行われた変更を適用してからルート・ノードを返します。反復処理が終了しない場合には、matcher 関数が現在の loc に適用されます。マッチするものが見つかると、そのノードと matcher の結果が editor 関数に渡されて、ノードに対して可能な変更が行われます。そして、変更されたノードから反復処理が続けられます。マッチするものが見つからない場合には、元のノードから反復処理が続けられます。partial 関数は、その引数のサブセットで関数を部分適用し、さらに少ない数の引数を取る新しいサブセットを返します。この例では editor を部分適用し、edit 関数が適切なシグニチャーを持つ新しい関数を受け取るようにしています。

トラバーサルの間に標準的な Clojure データ構造を処理できる zipper 実装も必要です。リスト 14 の tree-zipper が実装する関数は、コアとなる型の集合を有効にして、これらの型から作成されるすべての Clojure データ構造が zipper 関数 (branch?、children、make-node) となるようにすることができます。ここでは、それぞれの zipper 関数ごとにマルチメソッドを使用することにしました。こうすることにより、後から新しい defmethod 実装を追加するだけで、この zipper を他の型にも動的に拡張できるからです。

(defmulti tree-branch? class)
(defmethod tree-branch? :default [_] false)
(defmethod tree-branch? IPersistentVector [v] true)
(defmethod tree-branch? IPersistentMap [m] true)
(defmethod tree-branch? IPersistentList [l] true)
(defmethod tree-branch? ISeq [s] true)

(defmulti tree-children class)
(defmethod tree-children IPersistentVector [v] v)
(defmethod tree-children IPersistentMap [m] (seq m))
(defmethod tree-children IPersistentList [l] l)
(defmethod tree-children ISeq [s] s)

(defmulti tree-make-node (fn [node children] (class node)))
(defmethod tree-make-node IPersistentVector [v children]
           (vec children))
(defmethod tree-make-node IPersistentMap [m children]
           (apply hash-map (apply concat children)))
(defmethod tree-make-node IPersistentList [_ children]
           children)
(defmethod tree-make-node ISeq [node children]
           (apply list children))
(prefer-method tree-make-node IPersistentList ISeq)

(defn tree-zipper [node]
  (zip/zipper tree-branch? tree-children tree-make-node node))

concat の評価

concat 関数を評価するという問題を再考するために、リスト 15 にマッチャー関数 (文字列リテラルの引数を持つ concat ノードを見つけるため) とエディター関数 (concat を評価するため) を作成します。can-simplify-concat 関数がマッチャー関数の役割を果たし、simplify-concat 関数がエディター関数の役割を果たします。

(defn can-simplify-concat [node]
  (and (= :concat (node-type node))
       (every? string? (:args val))))

(defn simplify-concat [_ node]
  (string/join (:args node)))

(defn simplify-concat-zip [node]
  (tree-edit (tree-zipper node) 
             can-simplify-concat 
             simplify-concat))

(simplify-concat-zip crit)

これまでの作業で、本質的な複雑さはリスト 10 の clojure.walk 実装とほとんど同じレベルにまで軽減されています。リスト 10 とリスト 15 の違いの 1 つは、リスト 10 の探索バージョンでは「マッチング」と「編集」の部分が結合されている一方、zipper バージョンではこの部分が分かれていることです。また内部では、zipper バージョンは再帰トラバーサルではなく、データ構造の線形末尾再帰トラバーサルを使用しているという点も異なります。これにより、スタックの深さは一定となり、ツリーの高さによって変わることがないため、反復処理中のメモリー使用量が減ることになります。

ツリー・ビジターのさらなる改善

実際に役立つビジターを調べてみると、ビジターの目標に基づくいくつかの共通したカテゴリーがあることがわかります。

• ファインダー: 何らかの基準に最初にマッチするノードを検索し、そのノードを返します。
• コレクター: 何らかの基準にマッチするノードを検索し、一致するすべてのノードを返します。
• トランスフォーマー: ツリー内でマッチする箇所を検索し、そのポイントでツリーを変更して返します。
• イベント・ジェネレーター: ツリーをトラバースし、イベントを起動します (SAX に対する DOM だと思ってください)。

当然、実際にツリーを使い始めて操作しているうちに、上記のカテゴリーには他にも多くの興味深い組み合わせおよび拡張があることがわかるはずです。現時点での tree-edit 関数では、反復処理を停止すべきか、または状態をトラバーサルで維持すべきかをビジターが指示することができません。そのため、外部の状態ホルダーを使わずにファインダー・ビジターやコレクター・ビジターを作成するのは困難です。

多くのビジターを作成しているうちに、機能の共通部分はビジターの間で再利用する必要があることもわかってきます。例えば、ファインダーとコレクターは両方ともノードで基準を評価し、そのノードが基準とマッチするかどうかを判別します。理想的には、この両方の機能に対応する 1 つの関数を再利用することが望まれます。同じように、次のノードにスキップすることになったり、反復処理を完全にアボートすることになったりするケースをチェックできるビジターを作成するのも有益です。

リスト 16 に、機能強化したビジターを記載します。このビジターは、各ノードで一連のビジターを適用し、反復処理の全体をとおして状態を渡し、ノードまたは反復処理全体の早期終了を可能にします。ここで使用されている以下の 2 つの関数に注目してください。

• tree-visitor: 前に説明した tree-edit 関数と同様に、zipper を使用してツリーを反復処理し、end? で終了します。tree-visitor は各ノードで visit-node (次に説明する関数) を呼び出します。tree-visitor での tree-edit との主な違いは、visit-node 関数が複数の項目 (new-node、new-state、および stop フラグ) を返すことです。stop フラグが true の場合、反復処理は即時に終了します。状態は、ビジター関数が望む任意の方法で操作できるように、initial-state によって準備され、反復処理に渡されます。tree-visitor が終了する時点で、最終的な状態と最終的なツリーの両方が返されます。
• visit-node: この関数は、それぞれにシグニチャー (fn [node state]) を持つビジター関数のリストを引数に取ります。各シグニチャーが返すコンテキスト・マップには、:node、:state、:stop, または :jump のいずれかのキーが含まれます。:node または :state が返された場合、これらのキーが、着信ノードまたは状態に置き換わります。:jump が返された場合、反復処理が今までのノードから次のノードにジャンプし、残りすべてのビジターは今まで対象としていたノードをスキップすることを示しています。:stop が返された場合は、すべての反復処理が停止することを意味します。

(defn visit-node 
  [start-node start-state visitors]
  (loop [node start-node
         state start-state
         [first-visitor & rest-visitors] visitors]
    (let [context (merge {:node node, :state state, :stop false, :next false}
                         (first-visitor node state))
          {new-node :node
           new-state :state
           :keys (stop next)} context]
      (if (or next stop (nil? rest-visitors))
        {:node new-node, :state new-state, :stop stop}
        (recur new-node new-state rest-visitors)))))

(defn tree-visitor
  ([zipper visitors]
     (tree-visitor zipper nil visitors))
  ([zipper initial-state visitors]
     (loop [loc zipper
            state initial-state]
       (let [context (visit-node (zip/node loc) state visitors)
             new-node (:node context)
             new-state (:state context)
             stop (:stop context)          
             new-loc (if (= new-node (zip/node loc))
                       loc
                       (zip/replace loc new-node))
             next-loc (zip/next new-loc)]
         (if (or (zip/end? next-loc) (= stop true))
           {:node (zip/root new-loc) :state new-state}
           (recur next-loc new-state))))))

機能強化されたツリー・ビジター関数の使用方法

この改善された新しいビジターを使って何ができるのでしょうか。リスト 17 に、ツリーで文字列を検索するコレクターの一例を記載します。string-visitor 関数は、文字列ノードを検索し、そのノードを取り込んで更新された状態を返す関数です。string-finder は string-visitor を使用してこの tree-visitor を呼び出し、最終的な状態を返します。

(defn string-visitor
  [node state]
  (when (string? node)
    {:state (conj state node)}))

(defn string-finder [node]
  (:state
   (tree-visitor (tree-zipper node) #{} [string-visitor])))

ファインダーも簡単に作成することができます。特定の型の最初のノードを検索するファインダーを作成してみましょう (リスト 18 を参照)。この matched 関数は、前のビジター関数と似ていますが、最初に検索対象のノード型を取ります。find-first はビジターを呼び出すと、ノード型を matched に部分適用します。それによって、期待される node と state だけを取る関数が作成されます。matched 関数が stop=true を返すと、反復処理が終了することに注意してください。

(defn matched [type node state]
  (when (of-type node type)
    {:stop true
     :state node}))

(defn find-first [node type]
  (:state
   (tree-visitor (tree-zipper node) [(partial matched type)])))

複数の関数を渡す方法

これまでは、まだ実際に複数の関数を渡す機能を使用していません。この場合に鍵となるのは、ビジターの機能を複数の小さな部分に分割し、これらの部分を再び組み合わせて複合機能を作成することです。一例として、リスト 19 に concat エバリュエーターを作成し直しました。このエバリュエーターは、:concat ノードを検索し (関数 1)、すべて文字列のノードを見つけて (関数 2)、concat を評価します (関数 3)。最初の型エバリュエーター・ビジターは、汎用の on 関数の中で生成されます。この関数が返すのは、ノードが該当する型ではない場合には次のノードにジャンプする匿名ビジター関数です。この関数は、オプションで残りのビジター・チェーンを (型に基づいて) 評価する必要があるビジター・チェーンのすべてによって、完全に再利用することができます。2 番目の all-strings 関数も同じように、引数がすべて文字列の concat ノードを検索する条件付きビジターを生成します。

最後に、評価を処理する eval-expr というマルチメソッドを作成します。この例の場合、デフォルトでは単純に引数として渡されたものをそのまま返すことで、すべてのものが評価されます。デフォルトの他に追加されているのは、:concat および :compare-criteria の実装です。このマルチメソッドは、node-eval 関数によってビジターに変換されます。

chained-example の中では、これらのビジターのチェーンを簡単に複合ビジターに組み立てることができます (リスト 19 を参照)。

(defn on [type]
  (fn [node state]
    (when-not (of-type node type)
      {:jump true})))

(defn all-strings []
  (fn [{args :args} _]
    (when-not (every? string? args)
      {:jump true})))

(defmulti eval-expr node-type)
(defmethod eval-expr :default [x] x)
(defmethod eval-expr :concat [{args :args :as node}]
           (string/join args))
(defmethod eval-expr :compare-criteria [{:keys (left right) :as node}]
           (if (= left right) true node))

(defn node-eval [node state]
  {:node (eval-expr node)})

(defn chained-example [node]
  (:node
   (tree-visitor (tree-zipper node)
                 [(on :concat)
                  (all-strings)
                  node-eval])))

この実装のいくつかの部分 (on 関数や node-eval 関数など) は、他のビジター・チェーンでも簡単に再利用することができます。ビジター・チェーンの概念は、ビジターを構造化する方法、そしてツリーでビジターを再利用する方法をさまざまなオプションで変更できる、非常に柔軟なフレームワークとなります。

上に戻る

Clojure ビジターのその他の使用方法

この記事では、Visitor パターンで zipper を使用する方法を表面的に説明しただけに過ぎませんが、記事の核心は、読者の皆さんに、さらに詳しく調査する気持ちを起こさせることです。例えば、リスト 18 の on と all-strings の構造がよく似ていることにお気付きでしょうか。この 2 つは、両方ともフィルターをビジターの中にラップする関数です。フィルターが含まれる関数をチェーンする代わりに、通常の Clojure コネクターを使って構成した条件にフィルター・ビジターをラップすることもできます。これらの条件を作成して結合するカスタム・マクロを追加すれば、コードはさらに作成しやすくなります。

実際、パターン・マッチング・ライブラリー (Clojure の新しい core.match ライブラリーについては、「参考文献」を参照) では、データ構造でマッチさせるパターンを、ワイルドカードを使って指定できるようになっています。パターン・マッチング・ライブラリーをツリー・ビジターに統合して、ビジターがツリー・パターンを利用できるようにするのは難しくありません。これは、問題そのものの言葉で問題について表現し、言語自体は関与させないようにするための強力な一歩となります。

この記事で詳しく説明していない Visitor パターンの側面には、反復処理の順序もあります。Revelytix では、常に zipper 列挙の深さ優先順でノードをトラバースしますが、場合によっては、これらのノードを逆の順序でトラバースし、特定のノードやサブツリーなどをスキップしてもかまいません。反復処理は基本的に、3 つの処理からなります。それは、start (ルート・ノードから start loc を検索)、next (loc を前提に、次の loc を検索)、end? (現在の loc が反復処理の終点であるかどうかを判別) です。これらの関数を現時点の tree-visitor 関数に含めて抽象化し、事前ビルドされたカスタム反復ストラテジーを実現するのは難しいことではありません。

Clojure では、すべてのコードは s 式のツリーとして保管されるデータでもあります。したがって、この記事で説明した手法のすべてを使用すれば、データを変更するだけではなく、コードを変更することもできます。そのいくつかの例は、コア Clojure API のより高度なマクロ・ユーティリティーに見つかるはずです。

皆さんが Clojure やお好みの言語で独自のビジターを作成する際、あるいはデータの構造化や操作の方法を引き続き調べる際に、この記事で紹介した考えが役に立つことを願っています。この記事で使用したコードおよびサンプルはすべて Github に保管されているので、これらをダウンロードするには「参考文献」セクションのリンクを参照してください。

謝辞

まず、この記事に記載したコードと同様のコードを Revelytix 製品用に開発した私の同僚に感謝の意を表します。特に、David McNeil 氏はホワイトボード上でアイデアとソリューションを話し合い、Emacs 上でそれらを結び付けるのに何時間も費やしてくれただけでなく、clojure.walk、clojure.zip、matchure のようなライブラリーを拡張するために大変な作業を引き受けてくれました。

また、帰りがけ順の反復処理を機能強化する必要性を見出し、その実装を行ってくれた同僚の Alex Hall 氏にも感謝いたします。

参考文献

学ぶために

• Clojure の詳細を学ぶには、以下の developerWorks 記事を読んでください。
  • 「Clojure プログラミング言語」(Michael Galpin 著、2009年)
  • 「Clojure と並行性」(Michael Galpin 著、2010年)
  • 「Solving the Expression Problem with Clojure 1.2」(Stuart Sierra 著、2010年)
  • 「Clojure によって CouchDB を使用する」(Ryan Senior 著、2011年)
  
  
• zipper の概要については、Wikipedia の zipper に関する記事および Haskell の資料を読んでください。
  
  
• Gérard Huet は zipper の概念を記事「Functional Pearl: The Zipper」(Journal of Functional Programming, Volume 7、Cambridge University Press、1997年) で発表しました。
  
  
• Clojure zipper の詳細を知るには、Blip.tv の Luke VanderHart 氏によるビデオ・プレゼンテーション (2010年) も見てください。
  
  
• Brian Marick の「'Editing' trees in Clojure with clojure.zip」(Exploration Through Example、2010年) は、clojure.zip の入門者向けチュートリアルです。
  
  
• 「Pattern Matching & Predicate Dispatch」(NYC Clojure Users Group、2011年) で、David Nolen 氏が core.match について紹介しています。
  
  
• Expression Problem は、Haskell の主要な設計者である Philip Wadler 氏が、ベル研究所の研究者であった 1998年に定義しました。
  
  
• 「Ideal Hash Trees」(Philip Bagwell 著、Es Grands Champs, Volume 1195、2001年) では、Clojure の永続的なデータ構造の中核となっているデータ構造について説明しています。
  
  

製品や技術を入手するために

• この記事のソース・コードおよびサンプルをダウンロードしてください。
  
  
• core.match のダウンロード: Clojure 向けに最適化されたパターン・マッチングおよび述部ディスパッチ・ライブラリーです。
  
  

著者について

Alex Miller は、Revelytix 社でフェデレーテッド・セマンティック Web クエリー技術の構築に従事しています。この 2 年間は、Clojure を専門に取り組んでいます。Revelytix に入社する前は、Terracotta の技術主任、BEA Systems のエンジニア、MetaMatrix の主任アーキテクトを経験しました。Java、並行性、分散処理、ソフトウェア設計などに興味を持つ彼は、@puredanger の名前で Twitter にツイートを投稿し、http://tech.puredanger.com でもブログを書いています。Alex は、架空の動的言語を研究する Strange Loop 開発者カンファレンスと Lambda Lounge グループの発足者です。好物はナチョスです。

この記事を評価する

コメント

上に戻る

目次

• シンボリック・ツリーの操作
• Java 言語でのビジター
• Java ビジターに伴う複雑さ
• Clojure でのツリー
• ツリーの探索
• Clojure の関数型 zipper
• zipper を使用したツリー・ビジター
• ツリー・ビジターのさらなる改善
• Clojure ビジターのその他の使用方法
• 参考文献
• 著者について
• コメント