Visitor — 網羅チェックが代わりになる

Visitor が担っていた役割のうち、どこまでを型システムが引き取るかを見ます。

このパターンが解こうとした問題

GoF は Visitor を、アルゴリズムをオブジェクトの構造から切り離し、処理の集まりを 1 つのオブジェクトへ移すパターンとして収録しています¹。

決まった種類のノードからなる構造 (構文木など) に対して、処理を次々に足したい状況を考えます。素朴に書くと、処理を 1 つ足すたびにすべてのノードのクラスへメソッドを足すことになります。Visitor はこれを裏返し、処理の側に「ノードの種類ごとのメソッド」を並べます。

そのために使うのが、accept を経由してノード自身に呼び分けさせる仕掛けです。ノードの静的な型が親クラスであっても、実行時の型に応じたメソッドが呼ばれます。この二段構えが要るのは、多くのオブジェクト指向言語のメソッド呼び出しがレシーバの実行時の型でしか行き先を選べないためです。処理側とノード側の両方で選び分けたいので、accept を挟んで 2 回に分けています。

クラスで素直に書く

数式の評価を題材にします。

interface ExprVisitor<R> {
  visitLiteral(node: LiteralExpr): R;
  visitAdd(node: AddExpr): R;
  visitMultiply(node: MultiplyExpr): R;
}

abstract class ExprNode {
  abstract accept<R>(visitor: ExprVisitor<R>): R;
}

class LiteralExpr extends ExprNode {
  constructor(readonly value: number) {
    super();
  }

  accept<R>(visitor: ExprVisitor<R>): R {
    return visitor.visitLiteral(this);
  }
}

class AddExpr extends ExprNode {
  constructor(
    readonly left: ExprNode,
    readonly right: ExprNode,
  ) {
    super();
  }

  accept<R>(visitor: ExprVisitor<R>): R {
    return visitor.visitAdd(this);
  }
}

class MultiplyExpr extends ExprNode {
  constructor(
    readonly left: ExprNode,
    readonly right: ExprNode,
  ) {
    super();
  }

  accept<R>(visitor: ExprVisitor<R>): R {
    return visitor.visitMultiply(this);
  }
}

class Evaluator implements ExprVisitor<number> {
  visitLiteral(node: LiteralExpr): number {
    return node.value;
  }

  visitAdd(node: AddExpr): number {
    return node.left.accept(this) + node.right.accept(this);
  }

  visitMultiply(node: MultiplyExpr): number {
    return node.left.accept(this) * node.right.accept(this);
  }
}

const tree = new AddExpr(new LiteralExpr(2), new MultiplyExpr(new LiteralExpr(3), new LiteralExpr(4)));
const result = tree.accept(new Evaluator());

処理を足すときは ExprVisitor を実装したクラスを 1 つ書くだけで、ノード側には触れません。処理し忘れは implements が捕まえます — メソッドを 1 つ書き忘れれば、そのクラスの宣言でコンパイルエラーになります。この「網羅の強制」が Visitor の中心的な価値です。

代償は accept です。ノード 3 種類につき 3 つ、内容はほぼ同一の定型句が並びます。

言語機能で置き換える

TypeScript には、網羅を強制する別の道具があります。

The never type is assignable to every type; however, no type is assignable to never (except never itself). This means you can use narrowing and rely on never turning up to do exhaustive checking in a switch statement.²

これを使うと、accept も ExprVisitor も書かずに済む形になります。

type ExprNode =
  | {kind: 'literal'; value: number}
  | {kind: 'add'; left: ExprNode; right: ExprNode}
  | {kind: 'multiply'; left: ExprNode; right: ExprNode};

function evaluateExpr(expr: ExprNode): number {
  switch (expr.kind) {
    case 'literal':
      return expr.value;
    case 'add':
      return evaluateExpr(expr.left) + evaluateExpr(expr.right);
    case 'multiply':
      return evaluateExpr(expr.left) * evaluateExpr(expr.right);
    default: {
      const exhaustive: never = expr;
      return exhaustive;
    }
  }
}

// 処理を足すときは関数を 1 つ書くだけ。型には触れない
function formatExpr(expr: ExprNode): string {
  switch (expr.kind) {
    case 'literal':
      return String(expr.value);
    case 'add':
      return `(${formatExpr(expr.left)} + ${formatExpr(expr.right)})`;
    case 'multiply':
      return `(${formatExpr(expr.left)} * ${formatExpr(expr.right)})`;
    default: {
      const exhaustive: never = expr;
      return exhaustive;
    }
  }
}

const tree: ExprNode = {
  kind: 'add',
  left: {kind: 'literal', value: 2},
  right: {
    kind: 'multiply',
    left: {kind: 'literal', value: 3},
    right: {kind: 'literal', value: 4},
  },
};

const result = evaluateExpr(tree);
const text = formatExpr(tree);

accept の定型句が消え、ノードは素のオブジェクトになりました。種類を 1 つ足すと、evaluateExpr と formatExpr の default が両方ともコンパイルエラーになります。

ただし強制のかかり方は違います。implements は Visitor クラスを宣言した時点で型システムが無条件に効かせます。never への代入は、書き手が default 節を書いたときだけ効きます。後から default のない関数を足すと、そこには保護がかかりません。同じ効果を得るには、書き方を規約として揃える必要があります。

ExprVisitor<R> の型引数に相当するものは、関数の戻り値の型そのものです。evaluateExpr は number、formatExpr は string を返すので、型引数は関数のシグネチャに吸収されています。

本連載の判断

判定: 言語機能で代替できる。 判別可能ユニオンと網羅チェックが揃っている以上、accept の定型句を書く理由が残りません。

これは Composite と同じ軸の話です。あちらでは「操作が増えるならユニオン型」と整理しました。Visitor は「操作が増える」状況そのものを対象にしたパターンなので、判定は片側に寄ります。

switch の連なりは、Visitor のクラスと比べて短いだけでなく、処理の全体が 1 つの関数として読めるという違いもあります。Visitor では処理がメソッドに分かれるので、全体を追うにはクラス内を上下することになります。

この判定が覆る条件

種類が増えるときの手間は、どちらの形でも小さくなりません。ユニオン型ではノードを 1 種類足すと、網羅チェックを書いた関数すべてでコンパイルエラーが出ます。Visitor でも事情は同じか、それ以上です — ノードのクラスと accept を足したうえで、ExprVisitor<R> にメソッドを 1 つ足し、それを実装しているすべての Visitor クラスに実装を足すことになります。触る箇所はユニオン型と同数で、そこにクラスと accept の追加が上乗せされます。

つまり Visitor に乗り換えても、種類の追加が安くなるわけではありません。種類の追加を安くしたいなら、Visitor ではなく Composite で扱った素の多態階層 (ノード自身がメソッドを持つ形) が候補になります。そちらは種類の追加がクラス 1 つで済む代わりに、操作の追加が全クラスに波及します。

もう 1 つ、走査そのものが複雑な場合は、走査の実装が各関数に重複します。上の例では evaluateExpr と formatExpr がそれぞれ子を再帰しており、「深さ優先と幅優先を切り替えたい」「途中で打ち切りたい」「親の情報を子に渡したい」といった要求が加わるとその重複が効いてきます。

これは Visitor に乗り換えなくても解けます。走査だけを 1 つの関数に切り出し、ノードごとの処理を引数で受け取る形にすれば、重複は 1 か所に集まります。

この形は Template Method で扱ったフックの注入と同じ構造です。

既存記事との関係

• 条件分岐 が判別可能ユニオンと網羅チェックの基本を扱っています。本章はそれが Visitor の役割を引き取ることを示す章で、基礎の説明は繰り返していません。
• Composite と判断の軸が共通です。あちらは構造の表し方、本章は構造に対する処理の足し方を扱っています。

Footnotes

1. Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides『Design Patterns: Elements of Reusable Object-Oriented Software』(Addison-Wesley, 1994)。Visitor は振る舞いに関するパターンとして収録されています。意図の要約は本ガイドによるもので、原典とは照合していません。 ↩

2. 出典: Narrowing(TypeScript Handbook)の Exhaustiveness checking。 ↩