オブジェクト指向 Advent Calendar というものを見つけたので、Visitor パターンについて書いてみます。
嘘です Visitor パターンについて書きたいけれど、Java Advent Calendar は埋まってしまってるので、それっぽい Advent Calendar に参加しただけです。別に Advent Calendar に参加しないといけない決まりなんてないんですけど。
#デザインパターン
Visitor パターンとは、デザインパターンの一つです。
そもそもデザインパターンとは何かというと、1995 年に Gamma らが "Gang of Four"、俗にいう GoF で提唱した、オブジェクト指向プログラミングによって特定領域の問題を解決しようとする際に頻出するイディオムのようなものです。
GoF で提唱されたデザインパターンは多くありますが、1995 年に発表されたものですから、言語の進化と共に必要なくなり、忘れられていったものも多くあります。一番分かりやすい例は Iterator パターンでしょうか。様々な言語やライブラリでサポートされているため、Iterator パターンをそのまま書くことはないでしょう。逆にいうと、デザインパターンとは、言語やライブラリがうまく解決してくれない問題に対する解答例なわけです。デザインパターンを適用せずに、言語やライブラリを使って素直に解決できるなら、それに越したことはありません。
とはいえ、現代においても必要になるデザインパターンはあります。Visitor パターンはそのようなパターンのうちの一つです。ということで Visitor パターンの話に戻りましょう。
#古典的な Visitor パターン
古典的なオブジェクト指向の仕組みでは、特に Composite パターンで表されるような構造に対する操作を実装するのが難しいという問題がありました。これを部分的に解決するのが Visitor パターンです。
Visitor パターンなんて全く知らない、という人はそんなにいないと思うので、コードを例示してちゃきちゃきと進めていきましょう。とりあえず Composite パターンで二分木を定義しつつ、Visitor パターンを適用します。
public abstract class Tree {
public abstract void accept(TreeVisitor visitor);
}
public class Leaf extends Tree {
public void accept(TreeVisitor visitor) {
visitor.visitLeaf();
}
}
public class Node extends Tree {
public final int value;
public final Tree lhs, rhs;
public Node(int value, Tree lhs, Tree rhs) {
this.value = value;
this.lhs = lhs;
this.rhs = rhs;
}
public void accept(TreeVisitor visitor) {
lhs.accept(visitor);
visitor.visitNode(this);
rhs.accept(visitor);
}
}
public interface TreeVisitor {
void visitLeaf();
void visitNode(Node node);
}
よくあるやつです。accept メソッドがまず一つ目のカスタマイゼーションポイントになっていて、引数に渡される visitor の visitXXX の呼び出しがまたカスタマイゼーションポイントになっていて…所謂ダブルディスパッチというやつです。
まあ兎に角 Tree に対する操作を適当に何か実装してみます。
tree.accept(new TreeVisitor() {
public void visitLeaf() {
System.out.println("Leaf");
}
public void visitNode(Node node) {
System.out.println("Node " + node.value);
}
});
びっくりするほどつまらない例ですね。ところで上記のコードには問題点があります。なんでしょうね。
#Internal Visitor パターンとその問題点
それは、Tree を走査する順番を外部から変更できない点です。
例えば左側の Tree より先に右側の Tree を走査したくなった、とか、そもそも右側は走査しなくてもいいや、とか…そういった場合に問題になります。
こういった、Composite パターンなどにより定義された、再帰的なデータ構造に対する accept メソッドの呼び出しが、accept メソッド内に集約されている Visitor パターンを、Internal Visitor パターンと呼びます。
#External Visitor パターンとその問題点
Internal Visitor パターンの問題点の解決方法は簡単で、accept メソッド内で呼び出すのをやめて Visitor のほうで呼ぶことにすればいいのです。
public void accept(TreeVisitor visitor) {
visitor.visitNode(this);
}
void visitNode(Node node);
差分だけ。使い方としてはこんな感じ。
tree.accept(new TreeVisitor() {
private int depth = 0;
public void visitLeaf() {
printlnWithIndent("Leaf");
}
public void visitNode(Node node) {
printlnWithIndent("(Node " + node.value);
depth += 1;
node.lhs.accept(this);
node.rhs.accept(this);
depth -= 1;
printlnWithIndent(")");
}
private void printlnWithIndent(String str) {
for (int i = 0; i < depth; i++) System.out.print(" ");
System.out.println(str);
}
});
Internal Visitor パターンの時よりはましな出力結果になってるはずです。
External Visitor パターンの問題点は、flexible に構造を走査できる代償に、ちゃんと accept メソッドを呼んでやらないといけないことです。丸儲けはできません。
#Imperative Visitor パターン
さてここまでで、Visitor パターンにも Internal と External というのがあるんだよ、という話をしました。まだあります。
ここまで書いてきた Visitor パターンは Imperative（命令型） Visitor パターンと呼ばれるものです。簡単にいうと visitor や accept メソッドが値を返さない Visitor パターンです。本持ってないので分かりませんが、多分 GoF で提案されたのも Imperative Visitor パターンだと思います。これは 1995 年当時には、まだ Generics のような parametric polymorphism のための言語機能を備えた、オブジェクト指向プログラミングのできる言語があまりなかったからでしょう。
時代は変わりました。Java 5 で導入された Generics を使って Functional（関数型） Visitor パターンを書いてみましょう。Functional といっても、関数型プログラミングがどうこうということではなく、単に visitor や accept メソッドが値を返すだけです。勿論それによって状態や副作用を用いずに実装可能になることもあるので、それっぽいといえばそれっぽいかもしれません。
#Functional Visitor パターン
さくさくいきます。
public abstract class Tree {
public abstract <T> T accept(TreeVisitor visitor);
}
public class Leaf extends Tree {
public <T> T accept(TreeVisitor<T> visitor) {
return visitor.visitLeaf();
}
}
public class Node extends Tree {
public final int value;
public final Tree lhs, rhs;
public Node(int value, Tree lhs, Tree rhs) {
this.value = value;
this.lhs = lhs;
this.rhs = rhs;
}
public <T> T accept(TreeVisitor<T> visitor) {
return visitor.visitNode(this, lhs.accept(visitor), rhs.accept(visitor));
}
}
public interface TreeVisitor<T> {
T visitLeaf();
T visitNode(Node node, T lhs, T rhs);
}
さて、値を返すように変更したことで走査の結果を伝播していくことが可能になりました。Visitor 内で出力したり状態を持つのはダサいので、Doc というドキュメントを表す汎用的なクラスに変換する Visitor を記述してみましょう。Doc の定義はこの記事の本質ではないので、記事の最後に載せます。
Doc doc = tree.accept(new TreeVisitor<Doc>() {
public Doc visitLeaf() {
return Doc.text("Leaf");
}
public Doc visitNode(Node node, Doc lhs, Doc rhs) {
Doc inner = lhs.concat(Doc.line()).concat(rhs);
return Doc.bracket("(Node " + node.value, inner, ")");
}
});
System.out.println(doc.layout());
Visitor から状態がなくなり、だいぶましなコードになりました。Functional Visitor パターンにも Internal, External の違いがあります。上記のコードは Internal なものです。当然 External でも実装できます。
public <T> T accept(TreeVisitor<T> visitor) {
return visitor.visitNode(this, lhs, rhs);
}
T visitNode(Node node, Tree lhs, Tree rhs);
Doc doc = tree.accept(new TreeVisitor<Doc>() {
public Doc visitLeaf() {
return Doc.text("Leaf");
}
public Doc visitNode(Node node, Tree lhs, Tree rhs) {
Doc lhsDoc = node.lhs.accept(this);
Doc rhsDoc = node.rhs.accept(this);
Doc inner = lhsDoc.concat(Doc.line()).concat(rhsDoc);
Doc ret = Doc.bracket("(Node " + node.value, inner, ")");
return ret;
}
});
System.out.println(doc.layout());
この例だと大した違いはないんですが。というか External な実装は Visitor の定義がだるいですね。こういうのは Internal の方が向いています。
#ここまでのまとめと更なる問題提起
Visitor パターンにも種類がある、という話をしました。
- Internal Visitor パターン
- External Visitor パターン
また上の二つとは直交する概念として以下のような種類もある、という話をしました。
- Imperative Visitor パターン
- Functional Visitor パターン
この二つに関しては、副作用バリバリ使って書くんじゃー、という場合でもなければ基本的には Functional Visitor パターンを使っていけばいいでしょう。
しかし Internal, External に関しては、External のほうが flexible ですが、走査順に興味がない場合には単に記述が冗長になるだけであり、また accept メソッドを呼び出すタイミングを誤って記述する可能性が生じる等、どちらが正解ともいえません。
必要に応じて Visitor を定義する段階で、Internal と External を使い分けすることはできないでしょうか？
#Decomposition
結論からいうとできます。Decompose という、走査対象を Visitor が望む形に「分解」する機構を追加することで可能になります。これもコード見せたほうが早いですね。
public abstract class Tree {
public abstract <T, U> T accept(TreeVisitor<T, U> visitor, TreeDecompose<T, U> decompose);
}
public class Leaf extends Tree {
public <T, U> T accept(TreeVisitor<T, U> visitor, TreeDecompose<T, U> decompose) {
return visitor.visitLeaf();
}
}
public class Node extends Tree {
public final int value;
public final Tree lhs;
public final Tree rhs;
public Node(int value, Tree lhs, Tree rhs) {
this.value = value;
this.lhs = lhs;
this.rhs = rhs;
}
public <T, U> T accept(TreeVisitor<T, U> vis, TreeDecompose<T, U> dec) {
return vis.visitNode(this, dec.decompose(vis, lhs), dec.decompose(vis, rhs));
}
}
public interface TreeVisitor<T, U> {
T visitLeaf();
T visitNode(Node node, U lhs, U rhs);
}
public interface TreeDecompose<T, U> {
U decompose(TreeVisitor<T, U> visitor, Tree tree);
}
Node#accept メソッド内で TreeDecompose#decompose メソッドを呼び出しています。ここが新たなカスタマイゼーションポイントになっています。
説明するの面倒なので早速利用例を見てみましょう。
private static Doc internal(Tree tree) {
final TreeDecompose<Doc, Doc> dec = new TreeDecompose<Doc, Doc>() {
public Doc decompose(TreeVisitor<Doc, Doc> visitor, Tree t) {
return t.accept(visitor, this);
}
};
return tree.accept(new TreeVisitor<Doc, Doc>() {
public Doc visitLeaf() {
return Doc.text("Leaf");
}
public Doc visitNode(Node node, Doc lhs, Doc rhs) {
return createNodeDoc(node, lhs, rhs);
}
}, dec);
}
private static Doc external(Tree tree) {
final TreeDecompose<Doc, Tree> dec = new TreeDecompose<Doc, Tree>() {
public Tree decompose(TreeVisitor<Doc, Tree> visitor, Tree tree) {
return tree;
}
};
return tree.accept(new TreeVisitor<Doc, Tree>() {
public Doc visitLeaf() {
return Doc.text("Leaf");
}
public Doc visitNode(Node node, Tree lhs, Tree rhs) {
Doc lhsDoc = lhs.accept(this, dec);
Doc rhsDoc = rhs.accept(this, dec);
return createNodeDoc(node, lhsDoc, rhsDoc);
}
}, dec);
}
private static Doc createNodeDoc(Node node, Doc lhs, Doc rhs) {
Doc inner = lhs.concat(Doc.line()).concat(rhs);
return Doc.bracket("(Node " + node.value, inner, ")");
}
というわけで無事に Internal, External な Visitor パターンを統一的に扱えるデザインができました。良かったですね。
ちなみに Decomposition の仕組みを使うと、一つ前のノードも一緒に扱える Visitor とか定義できるようになります。paramorphism 的なやつです。暇な人は定義してみましょう。
Decompose の合成も多分できると思うんですが、やってないのでちょっと分かりません…が多分できるでしょう。合成できれば、Internal かつ一つ前のノードも見れてかつ…みたいなことが実現できるはずです。
#To reuse than to redo
「もう一度するよりも、もう一度使うほうがよい」
言葉の通りなのですが、必要に応じて Internal Visitor パターンを書いたり External Visitor パターンを書いたりするよりは、どちらも適用可能な API を用意し、うまく使うのが一番です。
デザインパターンとは、最初に書いたとおり「イディオム」でしかありません。こう書くとうまくいく、というものであり、これを適用するのは "redo" です。しかし、適切に抽象化し、ライブラリとして切り出されたものを使うなら、それは "reuse" です。今回は Internal Visitor パターンと External Visitor パターンをうまく抽象化し、Decomposition という概念を加えることで、再利用性を高めることができました。
デザインパターンは、GoF が提唱したものだけでも大変な数があります。いくつあるのか知りません。その中には、大きなものから小さなものまであります。小さなものの場合は "reuse" のために抽象化しても手間が増えるだけ、というようなこともあるでしょう。一方、大きなものの場合は、毎回そのまま書く "redo" ではなく、"reuse" のために抽象化できるなら抽象化し、ライブラリとして切り出して使うべきでしょう。時は 2015 年、GoF によって様々なデザインパターンが提唱された 1995 年から 20 年も経過している今なら、より強力になった言語（の機能）を用いて、うまくライブラリとして切り出せるパターンも多くあるはずです。
デザインパターンに限らず "To reuse than to redo" ということで、どんどんやっていきましょう。
#almost compositional visitors
どんどんやっていってみます。
走査の対象となるクラスのメソッドをオーバーライドすることはできませんが、Visitor のメソッドなら可能です。最初に、決まった順番でノードを「走査するだけ」の、雛形となる External Visitor を定義します。実際に操作を追加する際には、雛形の Visitor クラスを継承し、必要な部分だけオーバーライドして実装する、というような風に実装すれば、External Visitor パターンの問題点である、accept メソッドの呼び出しを何度も書かないといけない問題は、ある程度解決できます。"To reuse than to redo" です。
"A pattern for almost compositional functions" という論文では、AST に対する変換関数（rename とか）や畳込み関数（constant folding とか）などといった、実装の似通った関数を "almost compositional functions" と読んでいます。AST を走査するための汎用的な "compos" と呼ばれる関数を最初に定義することで、必要な部分だけ差し替えることにより、走査のための処理の重複なしに、AST に対する様々な関数の定義をスマートに行えるようにするこの手法は、Visitor パターンにも適用可能というわけです。
これは割と一般的なテクニックだと思います。実コードでもそのような Visitor は結構見かけます。MSDN のサンプルコードにもありますね。雛形となる Visitorと継承した Visitor。
#reuse できてないじゃん
はいすいません、今回のコードは完全に Tree クラスにべったりで、真に汎用的なものではありません。
汎用的なものを実装することもできたのですが、それをするには Java という言語はあまりに貧弱でした。型をメンバとして持つこともできない、当然メンバとしての型に触れることもできない、type constructor polymorphism もない。
色々頑張った結果として、一応できなくはないことは確認したのですが、複雑な型パラメタを沢山持つインターフェースや、インターフェース内インターフェースによるハック等。心底うんざりした。
これは Java ではやるなということだな、ということでなかったことにしました。Scala なら素直に実装できるので Scala 最高ですね…
#未解決問題
ちなみに汎用的な Visitor ライブラリを実装できたとしても、Visitor パターンには良く知られた問題があります。それは "non-intusive" や "non-invasive" と呼ばれる性質を持たないことです。簡単に言うと、accept メソッドが予め適切に定義されてないといけない、ということです。例えば、ライブラリの提供しているような、外部からの変更が不能なクラスに対してパターンを適用できない、という問題のことです。ちなみに C++ の最初の実装者、設計者である Bjarne Stroustrup 先生はこのパターンを大変嫌っており（ボクも正直 non-intrusive でない点は好きではないです）、そのために言語機能を追加しようと目論んでたりしていたようですが、最近は C++ の最新情報を追いかけなくなったため、どうなっているのかは知りません。
ちなみに、この問題を Java くらいの、そこまで強力でない言語で type safety に解決する手法はまだ見つかってないようなので、見つけたら論文にしましょう。Visitor パターンの原理的に、スマートにやるのは無理かなーと思いますが。
#まとめ
まとめるの忘れてた。ということで追記。
Visitor パターンにも色々あるんだよという話と、それらを抽象的な API で統一的に扱う手法を紹介しました。
ここまでちゃんと読んだ人なら、日本語 wikipedia の Visitor パターンの記事にある例が、Internal と External を区別できていないということが分かるはずです。誰か書き直して。
#参考資料
個人的な趣味で Visitor とその周辺については色々調べ回っているんですが、兎に角 Oliveira 先生の博士論文（ページ最下部に pdf があります）を読みましょう。ここに書いたことは全部書いてあります。なんならそのまんまです。この記事の内容は Visitor パターンの深淵をちょっと覗いてみたくらいのものです。
軽い気持ちで書き始めたら日付が変わってしまったー。おしまい。
#Appendix
記事中で本質的でないということで飛ばしていた Doc の定義です。
public abstract class Doc {
public static Doc nil() {
return NilDoc.nil;
}
public static Doc text(String str) {
return new TextDoc(str, nil());
}
private static final LineDoc line = new LineDoc(0, NilDoc.nil);
public static Doc line() {
return line;
}
public static Doc bracket(String start, Doc inner, String end) {
return text(start).concat(line().concat(inner).nest(2).concat(line()).concat(text(end)));
}
public abstract String layout();
public abstract Doc nest(int i);
public abstract Doc concat(Doc other);
}
public class LineDoc extends Doc {
private final int depth;
private final Doc doc;
public LineDoc(int depth, Doc doc) {
this.depth = depth;
this.doc = doc;
}
public String layout() {
StringBuilder sb = new StringBuilder();
sb.append("\n");
for (int i = 0; i < depth; i++) {
sb.append(" ");
}
sb.append(doc.layout());
return sb.toString();
}
public Doc nest(int i) {
return new LineDoc(depth + i, doc.nest(i));
}
public Doc concat(Doc other) {
return new LineDoc(depth, doc.concat(other));
}
}
public class TextDoc extends Doc {
private final String str;
private final Doc doc;
public TextDoc(String str, Doc doc) {
this.str = str;
this.doc = doc;
}
public String layout() {
return str + doc.layout();
}
public Doc nest(int i) {
return new TextDoc(str, doc.nest(i));
}
public Doc concat(Doc other) {
return new TextDoc(str, doc.concat(other));
}
}
public class NilDoc extends Doc {
public static NilDoc nil = new NilDoc();
private NilDoc() { }
public String layout() {
return "";
}
public Doc nest(int i) {
return this;
}
public Doc concat(Doc doc) {
return doc;
}
}
Philip Wadler 先生の A prettier printer を参考にしました。この実装は幅指定とかできないし、全然 pretty じゃないですけど…simple ではある。