ジェネリクスによるVisitorパターン拡張の考察

Java Generics

先日twitterで "Expression Problem" という問題を知った。

静的な型付けの下で、場合分けのデータ構造に対して、新しい場合分けとその場合に対する新しい処理を、元のソースコードに手を加えることなく拡張定義すること

2009-05-16

この問題が意図するところを語るにはまずオブジェクト指向から流れを辿らねばなるまい。

オブジェクト指向のポリモーフィズム

Javaのようなオブジェクト指向の言語で、ある特定のメソッドがあることを抽象クラスHogeで保証するとしよう。

public interface Hoge {
	void hoge();
}

このとき、機能性、つまりメソッドというのは増えることがない固定のものだが、継承して実装されたクラスというのは自由に増やすことができる。そして、抽象型Hogeを扱っている既存コードは修正する必要がない。

これはいわゆる開放/閉鎖原則(OCP: open/closed principle)というやつでJava的OOP言語は機能(提供されるメソッド)が固定で要素(ここではinterfaceの実装クラス)が増えることについてはポリモーフィズムによって容易に行えるというのが特徴だった。

Visitorパターン

これに対して、機能の方を開放/閉鎖原則にのっとり拡張することができるかどうかという問が生まれる。その答えはGoFデザインパターンのひとつ、Visitorパターンである。

このVisitorパターンはGoFの23のデザインパターンのうち、もっとも難解なパターンとも言われる。それは多分、ダブルディスパッチと呼ばれる相互に呼び合う動きが混乱を招くからだろう。

過去に異型のオブジェクト比較という稿でもVisitorについては解説を行なっているが、今一度解説してみよう。

まず、ある型Nodeを継承するA, B, Cのクラスがあったとする。これはList型のようなデータ型にごちゃまぜにして格納することができる。

List<Node> list = new ArrayList<>();
list.add(new A());
list.add(new B());
list.add(new C());

これを順に取り出してそれぞれの型によって処理を分岐したい。

for (Node node : list) {
	if (node instanceof A) {
		// Aに対する処理
	} else if (node instanceof B) {
		// Bに対する処理
	} else if (node instanceof C) {
		// Cに対する処理
	}
}

ダサい。Javaにおいてinstanceofというのはやむを得ない時を除いて使うべきではない演算子だ。こうした型別に処理をしたい場合、ポリモーフィズムに処理をするのがよしとされる。なのでこの条件分岐をポリモーフィズムを用いた分岐に書き換えよう。

そのため、これらA,B,Cの処理を行うメソッドを持ったクラスVisitorを定義する

public class Visitor {
	public void doAの処理() {
		// Aに対する処理
	}
	public void doBの処理() {
		// Bに対する処理
	}
	public void doCの処理() {
		// Cに対する処理
	}
}

このそれぞれのメソッドをA,B,Cの各Nodeからポリモーフィズムを用いて呼び出す作りにしよう。そのためNode型に抽象メソッドを足し、各具象型で次のように実装する

public interface Node {
	void doVisitorへの処理の委譲(Visitor v);
}

public class A implements Node {
	void doVisitorへの処理の委譲(Visitor v) {
		v.doAの処理();
	}
}

public class B implements Node {
	void doVisitorへの処理の委譲(Visitor v) {
		v.doBの処理();
	}
}

public class C implements Node {
	void doVisitorへの処理の委譲(Visitor v) {
		v.doCの処理();
	}
}

こうすると先ほどのfor文は

Visitor v = new Visitor();
for (Node node : list) {
	node.doVisitorへの処理の委譲(v);
}

となる。instanceofの分岐が「doVisitorへの処理の委譲()」メソッドのポリモーフィズムになった。そして、それぞれの箇所で「doAの処理()」「doBの処理()」「doCの処理()」を呼び出すこととなった。

List型にごちゃまぜに詰め込まれていたオブジェクトを具象型別に分岐して処理することができたわけだ。これがVisitorパターンのひとつの機能である。

ここでは簡単のためVisitorクラスを具象型として作った。これをinterfaceと具象型に差し替えよう。

public class Visitor {
	void doAの処理();
	void doBの処理();
	void doCの処理();
}
public class VisitorImpl implements Visitor {
	void doAの処理() {
		// Aに対する処理
	}
	void doBの処理() {
		// Bに対する処理
	}
	void doCの処理() {
		// Cに対する処理
	}
}

すると、このVisitorの実装型を切り替えることでA,B,Cのそれぞれに対して何を行うかという「機能」の部分が差し替え可能となった。機能の方を開放/閉鎖原則にのっとり拡張することができるというわけだ。

Visitorの制約

ところでここでA,B,Cという3つのクラスに新たにDを追加してみよう。

public class D implements Node {
	void doVisitorへの処理の委譲(Visitor v) {
		// ?
	}
}

ここでVisitorにはDに対する処理が存在しないのだった。クラスDはどのようにVisitorへの処理の委譲を行えばいいのか困ってしまう。

このように、Visitorは機能性を追加することは容易だが、要素(ここではA,B,C,D)が追加されると困るのだ。

このVisitorの制約についてはGoF本にも書かれている。古くから知られる「常識」である。

そして、ポリモーフィズムは要素を増やすことは容易だが、機能性を追加する(要するにメソッドを増やす)のは困るのだ。

ここを両立させることは困難だというのが常識であった。

Expression Problem

この両方を既存部分に手を入れることなく増やせるようにする(解放/閉鎖原則)にはどうしたらよいか？というのを問うた一例が"Expression Problem"というわけだ。

Expression Problemは、古くから言われている問題の言い替えに過ぎない。その目的は、静的な型付けの下で、場合分けのデータ構造に対して、新しい場合分けとその場合に対する新しい処理を、元のソースコードに手を加えることなく拡張定義することだ。具体的な例として、式をデータ構造(最初は定数だけ)、式の評価関数を一つの処理と考え、これに足し算と新しい処理(文字列への変換)を加えてみたい。

ある言語がこのExpression Problemを解決できるかどうかは、その言語の表現能力を示す顕著な指標だ。行と列を持つ表を考えると、いうなれば場合分けを行、処理を列と捉えることができる。関数型言語では、列(処理)を加えることは簡単だけれども、行は(データ型宣言により)固定されてしまう。オブジェクト指向言語では、新しい行(サブクラス)を加えることは簡単だけれども、列は(メソッド定義により)固定されてしまう。我々は、行と列の両方を簡単に加えたいのだ。

2009-05-16

この原文は

http://www.daimi.au.dk/~madst/tool/papers/expression.txt

でPhilip Wadler氏(モナドで有名な人らしい)がGeneric Javaに関する議論でメーリングリストに投稿した文章らしい。

この文が投稿された1998年の11月の時代背景だが、まだJavaのバージョンが1.1だった。1998年の12月に1.2がリリースされているから、その直前のあたりの話だ。Javaに実際にジェネリクスが載ったのはJava5からで、2004年9月30日のことである。

なので、この原文はまだ確定していないJavaのジェネリクスの実装についての議論であり、掲載されているソースコードは動かそうとしてもコンパイルすることができないので注意が必要。

このソースコードでは再帰ジェネリクスを用いた上で内部クラスを利用した型変数の共有を行なっている。もっともここでは内部クラスのように内部interfaceを定義して外部クラスの型変数を利用するようなコードとなっているがinterfaceは暗黙にpublicでstaticなため構文的にNGなのである。

とにかく、こういうジェネリクスが使えるならこんな感じで機能と要素と両方を増やすことが出来るんじゃない？という話のようだ。

じゃあ、ジェネリクスが利用できるJava5以降の世界ではそれは実現できるのだろうか？

機能と要素を増やす

Philip Wadler氏のコードはやけに複雑ではあるが、そこまでする必要はない。

Nodeの実装型を増やした場合、既存のVisitorでは対応できなくなることは先に述べたとおりだ。要素が増えたならそれに対応したVisitorを新たに作らなければならない。Nodeの実装型も新たなVisitor型へと切り替える必要が出てくる。

型が変わることに対応するとなれば型変数。ジェネリクスの出番だ。ここではNodeに対して自分自身を処理できるVisitorを型変数で明示するようにしてみよう。

public interface Node<V extends Visitor> {
	void doVisitorへの処理の委譲(V v);
}

Visitorのインターフェースはとりあえずメソッドなしで用意する

public interface Visitor {}

簡単のため最初はNodeはひとつだけとしよう。NodeAクラスである。

public class NodeA implements Node<VisitorA> {
	@Override
	public void doVisitorへの処理の委譲(VisitorA v) {
		v.doAの処理(this);
	}
}

このNodeAだけを処理するVisitorAを作る

public interface VisitorA extends Visitor {
	void doAの処理(NodeA a);
}

この時点でVisitorAの具象型を作ればどんどん機能の方は増やせる状態だ。
では、ここに新しくNodeBを追加するときはどうするのか。

public class NodeB implements Node<VisitorB> {
	@Override
	public void doVisitorへの処理の委譲(VisitorB v) {
		v.doBの処理(this);
	}
}

public interface VisitorB extends VisitorA {
	void doBの処理(NodeB b);
}

新しく追加したNodeBを既存のVisitorAで扱うことは不可能であるから、新たにVisitorAを拡張したinterface VisitorBを作る。VisitorBでは見ての通りBを処理するメソッドが追加される。NodeBはNodeをimplementsする際に自信を処理できるVisitorとしてVisitorBを指定している。そのため、

public void doVisitorへの処理の委譲(VisitorB v)

というように渡されるVisitorがVisitorBになるわけだ。

Visitorの具象型はどうなるだろうか。たとえばSystem.out.println()するだけのVisitor実装を作ってみよう。

public class VisitorAimpl implements VisitorA {
	@Override
	public void doAの処理(NodeA a) {
		System.out.println(a);
	}
}

この実装を利用しつつ、NodeBにも対応したVisitorBimplを作る場合は

public class VisitorBimpl extends VisitorAimpl implements VisitorB {
	@Override
	public void doBの処理(NodeB b) {
		System.out.println(b);
	}
}

といった具合。追加になった分のNodeBの処理だけ書けば済む。

まとめ

古典的Visitorパターンは要素の追加が困難とされてきたがジェネリクスを導入することでこの欠点を克服することが可能だ。

Visitorパターンは構文解析木の処理などに利用されることが多いが言語仕様が変更になって構文の要素が追加になることを想定して言語仕様のバージョンごとに先に挙げたようなVisitorの継承階層を作ると良いかもしれない。

ジェネリクス時代でのGoFデザインパターンの拡張はまとめる必要があるかもしれない。