1. ホーム
  2. design-patterns

[解決済み] Visitorパターンのaccept()メソッドのポイントは何ですか?

2023-02-11 18:35:27

質問

アルゴリズムをクラスから切り離すことについて、多くの議論がなされています。しかし、1つのことは説明されないままです。

彼らはこのような訪問者を使っています。

abstract class Expr {
  public <T> T accept(Visitor<T> visitor) { return visitor.visit(this); }
}

class ExprVisitor extends Visitor{
  public Integer visit(Num num) {
    return num.value;
  }

  public Integer visit(Sum sum) {
    return sum.getLeft().accept(this) + sum.getRight().accept(this);
  }

  public Integer visit(Prod prod) {
    return prod.getLeft().accept(this) * prod.getRight().accept(this);
  }

visit(element)を直接呼び出す代わりに、Visitorはそのvisitメソッドを呼び出すように要素に要求します。これは、訪問者についてクラスを意識しないという宣言された考えと矛盾しています。

PS1 あなた自身の言葉で説明するか、正確な説明を指し示してください。なぜなら、私が得た2つの回答は、一般的で不確かなものに言及しているからです。

PS2 私の推測:以来 getLeft() は基本的な Expression を呼び出すと visit(getLeft()) を呼び出すと、結果的に visit(Expression) となるのに対し getLeft() と呼ぶ visit(this) を呼び出すと、別の、より適切な、訪問の呼び出しが行われます。ですから accept() は型変換(別名キャスト)を実行します。

PS3 Scalaのパターンマッチング = ビジターパターン on ステロイド は,acceptメソッドなしでVisitorパターンがどれだけシンプルになったかを示しています. Wikipediaはこの記述に を示す論文をリンクしています。 accept() メソッドは不要であることを示す論文をリンクしています。

どのように解決するのか?

ビジターパターンの visit / accept の構成は、C言語ライクな言語(C#、Javaなど)のセマンティクスのために必要な悪である。 ビジターパターンの目的は、ダブルディスパッチを使用して、コードを読んで期待したとおりに呼び出しをルーティングすることです。

通常、訪問者パターンが使用される場合、すべてのノードがベースとなる Node 型から派生したもので、以後 Node . 直感的には、このように書きますね。

Node root = GetTreeRoot();
new MyVisitor().visit(root);

ここに問題があります。 もし私たちの MyVisitor クラスが次のように定義されていたとします。

class MyVisitor implements IVisitor {
  void visit(CarNode node);
  void visit(TrainNode node);
  void visit(PlaneNode node);
  void visit(Node node);
}

もし、実行時に 実際の という型が root である場合、呼び出しはオーバーロードの visit(Node node) . このことは Node . なぜそうなるのでしょうか? なぜなら、Javaや他のC言語ライクな言語では、変数に含まれる 静的型 つまり、どのオーバーロードを呼び出すかを決定する際に、変数が宣言されているパラメータを考慮するからです。 Javaは、実行時に、すべてのメソッド呼び出しに対して、「さて、の動的型は何でしょう? root ? ああ、なるほど。 それは TrainNode . に何かメソッドがあるか見てみましょう。 MyVisitor 型のパラメータを受け付ける TrainNode ..."である。 コンパイル時にコンパイラは、呼び出されるメソッドがどれであるかを決定する。 (Java が実際に引数の動的型を検査した場合、パフォーマンスはかなりひどいものになるでしょう)。

Javaはメソッドが呼び出されたときにオブジェクトの実行時(すなわち動的)型を考慮するための1つのツールを与えてくれます。 仮想メソッドディスパッチ . 仮想メソッドを呼び出すと、その呼び出しは実際には テーブル を呼び出します。 各タイプはテーブルを持っている。 特定のメソッドがクラスによってオーバーライドされた場合、そのクラスの関数テーブルのエントリには、オーバーライドされた関数のアドレスが含まれます。 もしクラスがメソッドをオーバーライドしない場合は、ベースクラスの実装へのポインタが含まれます。 これはまだパフォーマンスのオーバーヘッドを生じますが (各メソッド呼び出しは基本的に 2 つのポインタをデリファレンスします。1 つは型の関数テーブルを指し、もう 1 つは関数そのものです)、パラメータの型を検査するよりもまだ速いです。

ビジターパターンの目標は ダブルディスパッチ -- 呼出し先の型が考慮されるだけでなく ( MyVisitor 仮想メソッド経由) だけでなく、パラメータの型も考慮されます (どのような型が Node がどのようなものなのか)? Visitorパターンでは、これを visit / accept の組み合わせになります。

行をこう変えることで

root.accept(new MyVisitor());

仮想メソッドのディスパッチにより、サブクラスで実装されている正しい accept() を呼び出すことができます。 TrainElement を入力します。 TrainElement の実装は accept() :

class TrainNode extends Node implements IVisitable {
  void accept(IVisitor v) {
    v.visit(this);
  }
}

のスコープ内で、コンパイラはこの時点で何を知っているのでしょうか? TrainNode 's accept ? の静的な型が thisTrainNode . これは、コンパイラが呼び出し元のスコープで認識していなかった重要な追加情報です。 root について知っていることは、それが Node . これでコンパイラは this ( root ) は、単に Node でなく、実際には TrainNode . その結果 accept() : v.visit(this) は、全く別のものを意味します。 コンパイラはここで visit() のオーバーロードを探します。 TrainNode . もし見つからなければ、その呼び出しを Node . どちらも存在しない場合は、コンパイルエラーになります。 object ). このため、実行は最初から意図していたとおりになります。 MyVisitor の実装です。 visit(TrainNode e) . キャストは不要で、最も重要なのはリフレクションも不要であることです。 したがって,この機構のオーバーヘッドはかなり低く,ポインタの参照だけで,他には何もありません.

あなたの質問で正しいのは、キャストを使用して正しい動作を得ることができるということです。 しかし、多くの場合、Node がどのような型であるかさえわかりません。 次のような階層のケースを考えてみましょう。

abstract class Node { ... }
abstract class BinaryNode extends Node { Node left, right; }
abstract class AdditionNode extends BinaryNode { }
abstract class MultiplicationNode extends BinaryNode { }
abstract class LiteralNode { int value; }

そして、ソースファイルを解析し、上記の仕様に準拠したオブジェクト階層を生成する簡単なコンパイラを書くとします。 Visitorとして実装された階層に対するインタプリタを書いていたとします。

class Interpreter implements IVisitor<int> {
  int visit(AdditionNode n) {
    int left = n.left.accept(this);
    int right = n.right.accept(this); 
    return left + right;
  }
  int visit(MultiplicationNode n) {
    int left = n.left.accept(this);
    int right = n.right.accept(this);
    return left * right;
  }
  int visit(LiteralNode n) {
    return n.value;
  }
}

の型がわからないので、キャストしてもあまり意味はないでしょう。 left または right の中に visit() メソッドに含まれています。 私たちのパーサーは、おそらく単に Node というオブジェクトを返すだけでしょうから、これも安全にキャストできません。 したがって、単純なインタープリタは次のようになります。

Node program = parse(args[0]);
int result = program.accept(new Interpreter());
System.out.println("Output: " + result);

オブジェクトの階層構造があれば、その階層を操作するためのモジュール的な操作を、その階層のクラス自体にコードを記述することなく作成することができるのです。 ビジターパターンは、例えば、コンパイラの構築に広く使われている。 特定のプログラムの構文木が与えられると、その構文木を操作する多くのビジターが書かれる。型チェック、最適化、マシンコード放出は通常、すべて異なるビジターとして実装される。 最適化ビジターの場合、入力ツリーがあれば新しい構文木を出力することさえできます。

もちろん、これには欠点があります。新しい型を階層に追加する場合、その型に応じた visit() メソッドを追加する必要があります。 IVisitor インターフェイスに追加し、すべての訪問者にスタブ (または完全な) 実装を作成します。 また accept() メソッドも追加する必要があります。 もしパフォーマンスがそれほど重要でないのなら、訪問者を記述する際に accept() を必要とせずに訪問者を書くための解決策がありますが、それらは通常リフレクションを含み、したがってかなり大きなオーバーヘッドを発生させることができます。