本家「@IT」にはない内容をエンジニアライフで技術紹介するコラム。広く議論する場になることを目指します。

第010回_新説Visitorパターンを適用する状況

»
前回、EBNFデータツリー(構文)をクラス構造に変換できるようになりました。今回からクラスが表現する構造を利用して入力文字列を解析する方法について検討していきます。本コラムではその方法としてGoFのデザインパターンの1つVisitorパターンを利用します。対象読者をJavaのプログラムを書くことができる方と定義していますが、Visitorパターンは使ったことがない方もいるかもしれませんので、今回はVisitorパターンによる実装の妥当性から解説します。

尚、Visitorパターンはツリーを巡回するデザインパターンということをご理解ください。細かい動作は他の解説サイトにお任せします。

EBNFデータツリーをVisitorパターンで実装する際の役割分担

EBNFデータツリーを巡回する方法は「構文解析手法」で述べたとおりLL法(左再帰下降型)とします。

また、ツリーの巡回ということはVisitorパターンが適用できます。Visitorパターンでは訪問者(Visitor)と受け入れ(Acceptor)に役割を大まかに大別できるのでそれぞれについてまとめておきます。

■訪問者(Visitor)側の役割
 ノードを巡回すること
 解析動作を行うこと

■受け入れ(Acceptor)側の役割
 EBNFデータツリーの各ノード(非終端記号や終端記号)を表現すること

上記の整理によって、各ノードクラスの実装内容は次のようにできます。
■ノードクラスの設計
 処理別にノードのクラスを定義していること(クラスの種類)
 Visitorを受け入れること(interfaceの指定)
 子ノードを構築すること(メンバ変数)

ここまで読んでも、「本当に解析できるのか?」という疑問が残るだろうと思いますから、次回からサンプルプログラムを使って説明します。

Visitorパターン

サンプルの中でVisitorパターンを使うためVisitorパターンの有用性について解説します。まず、Javaのデータ構造について考えて見ましょう。

Javaクラスのデータ構造はツリー構造
例えば、次のようにMyDataクラスを作成することを考えましょう。

pulic class MyData
{
    public MyData m_left;
    public MyData m_right;
    
    public MyData()
    {
        m_left = null;
        m_right= null;
    }
    
    public addLeft(MyData left)
    {
        m_left = left;
    }

    public addRight(MyData right)
    {
        m_right = right;
    }
}
MyDataクラスは意図的に2分木のノード(Node)を表すように作ってみましたが、
・フィールド変数名がノードを示すような名前でない(left,rightでなくて、a,b,c、hoge,foo,mogaでも)、
・フィールド変数の数が2つでなく、N個ある
・フィールド変数の型が同じクラスでない(MyDataでなくて、YourDataでも)、
としても、クラスのインスタンスが構成するデータ構造はN分木のツリー構造であるということを示唆しています。
#フィールドが自己再帰したり、循環参照するとツリー構造ではなく
#網目構造になりますが、ここでは除外します。

Javaのデータ構造がクラス型とprimitive型(intやboolean など)で成立しており、あらゆるプログラムがクラス型を使用していることから、Javaのデータ構造はツリー構造とみなせます。
# 独立した1つのクラスデータしかなければそれはルートノード(root node)だけの
# ツリーとみることができます。

このことはこじつけのように感じるかもしれませんが、Javaのcollectionクラスにツリー構造を構築するためのクラスが存在しないことも証左になると思います。

適用範囲
そして、Visitorパターンはツリーを巡回するデザインパターンです。つまり、全てのJavaデータ構造に適用可能なパターンと言えます。

これまで述べてきたように使い勝手がよさそうなパターンなのになぜ使われないのでしょうか?それはVisitorパターンの適用範囲についての説明がおおよそ使いにくそうに述べられているからです。実際に確認していきましょう。

Visitorパターンに関する世の中の認識
Visitorパターンを適用するタイミングは次のような場合と言われています。
・アルゴリズムをデータ構造から分離したい場合
・機能を追加する可能性があるデータ(クラス)に対して後で機能を追加したい場合
しかし、これは間違いでなくても正しくもないと言えます。その理由についての筆者の持論は次のようになります。

アルゴリズムをデータ構造から分離する設計タイミングがない
クラスは、「データとデータを処理する機能(手続き)をまとめたもの」です。そして、クラスの機能の手続きが持つ結果の導出方法--アルゴリズム--はインスタンスの利用者にとって公開されない内容です。このことから、クラスからアルゴリズムを分離するとカプセル化が弱まります。
一方、クラス設計者はクラス設計時にカプセル化を必ず考えますから、Visitorパターンを採用するという設計上のインセンティブが発生しません。
また、アルゴリズムとデータ構造を分離して何がしたいのでしょうか。カプセル化を弱める以外で考えるとアルゴリズムを交換可能にするという目的が思いつきますが、交換可能なアルゴリズムを皆さんはいくつご存知ですか?

筆者が思い付けたのは、
 ・ソート(バブルソート/ヒープソート/マージソート/クイックソート)
 ・コレクション(リンクリスト/アレイリスト
         ハッシュマップ/ツリーマップ etc...)
 ・文字列探索(ブルートフオース/KMP法/BM法)
くらいです。

残りの処理上のアルゴリズムは、基本的にはワン・パターンです。遠回りせずに複数の処理方法があるようなことはほとんどありませんので、やはり、Visitorパターンを採用するインセンティブになりません。

アプリケーションの開発者に、後で機能を追加するという設計タイミングはない
事実として、後で機能を追加するということはあります。しかし、「あるクラスについては仕様が不明確だから、そのまま設計してくれ」という状況は発生しません。

なぜなら、仕様が不明確なアプリケーションは規模も見積れず、予算も確保できません。つまり、設計や製造段階では既に仕様は確定しているものです。もし後から機能を追加するということになれば、それは仕様変更で対応するだけです。

ただし、Visitorを作る側とacceptを実装するノード側の実装者が異なるときだけはこの考え方での設計タイミングがインセンティブを持ちます。そのような状況は、ライブラリの開発者のみが遭遇する状況です。

このように筆者は考えているので、Visitorパターンの説明は、いささかミスリーディングだと感じています。
次に、筆者が考えているVisitorパターンの適用状況について説明します。

Visitorパターンを適用するのはどんなときか?(筆者持論)
先に述べたように、クラスのデータ構造は全てツリー構造であり、Visitorパターンを適用できます。そうは言っても、全てのクラスでVisitorパターンが必要ではありません。設計段階でVisitorパターンを採用するインセンティブは次のような場合、得られると考えます。
ケース1: クラスインスタンスのツリー構造が深いときに、階層の深い位置のデータを取り出したい場合、深い位置のデータを伝播なしに、ノードを巡回して、そのデータを取得することができます。例えば、N層にあるノードのデータを隣接しない層--N-1層でもN+1層でもない層--が必要としたとき、中間ノードに不要な取得・設定メソッドを作る必要がなくなります。
ケース2: ツリーのノード間の状態に合わせた処理をしたい場合、データツリーの状態をデータツリー自体のフィールドに持たせずに、俯瞰するVisitorクラスに保持したほうが処理が明瞭になります。
ケース3: あるデータ構造(Javaのクラスは全てツリーとみなせますからツリー構造)があるときに、この構造に対して異なる処理を実装したい場合にデータ構造に変更を加えずに実装することが可能になります。

#補足:
# 実は、ケース3は「アルゴリズムをデータ構造から分離する」と同義なのですが、
# 処理とデータ構造の関係が、データ構造1 対 処理Nの場合にN個の処理が
# 実装上で混乱しないようにできるという意味になるよう
# に解釈し直しています。
#

EBNFデータツリーにVisitorパターンを適用するのは正しいのか?
EBNFデータツリーで意味のある構文を定義するにはツリー構造が深くなります。さらに各構文のノードごとに処理が必要です。ノード間の状態を俯瞰し、
・構文とトークンのマッチングの正否を判定する
・抽象構文木を生成する
ために、Visitorパターンが適していると言うことができます。

余談/個人の意見
クラス設計における開放/閉鎖原則(The Open-Closed Principle/OCP)を基にすれば上記の議論は成立しません。なぜならクラス設計の原則は、
「機能を追加する可能性があるデータ(クラス)に対して、後で機能を拡張できるようにしなければならず、修正に対しては閉じていなければならない」
であるためです。しかし、21世紀の日本のソフトウェア業界内のコードレビューでOCPの観点が持ち込まれることはまずないと思います。
そして筆者は、先に述べたようにVisitorパターンの解説がミスリーディングになってしまった理由がOCPの観点が持ち込まれない要因とイコールであると思っています。
せっかくなので、OCPが持ち込まれない要因について個人的意見を述べてみようと思います。

■意見1
・ある一定の期間に為しうるクラス設計には限界がある
->クラス設計は、バグを抑制したり、バグの解析を容易にする責任を持つ
->OCPを適用することとバグを増大することは関連性がないが、優先順位は低くなる

■意見2
・機能拡張性はお金にならない
->ソフトウェア開発は今もステップ数見積をしている会社が多く、設計の良し悪しで儲けは決まらない
->製作/拡張するにせよ修正するにせよ、良い設計をすればステップ数は下がるから結果、儲けが減ってしまうか見積精度が悪いという烙印を得る

■まとめ
OCPのインセンティブを持つという現在の論法において、OCPの観点で設計できないソフトウェア業界ではVisitorパターンは利用できません。
しかし、ケース1~3のインセンティブを持つという新しい論法を使うことでソフトウェア業界でもVisitorパターンを導入することが可能だと思います。
Comment(0)

コメント

コメントを投稿する