Visitor Pattern: Separating Algorithms from Object Structures

calendar_today August 22, 2025 schedule 14 min read

Learning Objectives: By the end of this lesson, you will be able to:

Understand how to separate algorithms from object structures using double dispatch

Implement visitors that can operate on complex object hierarchies without modifying them

Design extensible systems where new operations can be added without changing existing classes

Apply the pattern to syntax tree processing, document analysis, and data structure traversal

Evaluate when visitor pattern benefits outweigh its complexity and maintenance overhead

1. Welcome and Introduction (5 minutes)

Icebreaker Activity

Imagine you’re running a museum with different types of exhibits: paintings, sculptures, and historical artifacts. Throughout the year, different specialists visit to perform various operations: art critics write reviews, insurance assessors calculate values, maintenance staff perform upkeep, and tour guides provide descriptions. Each specialist performs different operations on each type of exhibit, but you don’t want to modify the exhibit classes every time a new type of specialist needs to work with them. This scenario perfectly illustrates the Visitor pattern - separating operations from the objects they operate on.

Lesson Overview

Duration: 3 hours
Prerequisites: Understanding of object-oriented programming, polymorphism, and method overloading/overriding
Materials Needed: IDE with Java/C#/Python support, understanding of abstract syntax trees (helpful but not required)

2. Learning Objectives and Session Outline (5 minutes)

What We’ll Cover Today:

Visitor Fundamentals - Understanding double dispatch and operation separation
Object Structure Navigation - How visitors traverse complex hierarchies
Implementation Patterns - Building flexible visitor systems with proper abstraction
Real-world Applications - Compiler design, document processing, and data structure analysis
Design Trade-offs - When visitor pattern helps vs when it adds unnecessary complexity

Success Criteria:

By the end of this session, you should be able to design systems where new operations can be easily added to existing object hierarchies without modifying the existing classes, and understand when this flexibility is worth the added complexity.

3. Foundation Knowledge (15-20 minutes)

Core Concepts

Double Dispatch Mechanism

The Visitor pattern relies on a technique called “double dispatch” - a mechanism that enables method selection based on the runtime types of two objects (the visitor and the element being visited). In most object-oriented languages, method dispatch is single - based only on the receiver object’s type. Double dispatch allows the method to be selected based on both the visitor type and the element type.

Real-World Analogy: Think of a restaurant where the final dish depends on both the chef (visitor) and the ingredients available (elements). A French chef will create different dishes from the same ingredients than an Italian chef would. The combination of chef expertise and available ingredients determines the final outcome.

Why This Matters: This mechanism allows you to add new operations to existing class hierarchies without modifying those classes. Each visitor can provide different behaviors for the same set of objects, and new visitors can be added without changing existing code.

Separation of Concerns

The pattern achieves clean separation by:

Object Structure: Classes focus solely on their data and basic structure
Operations: Visitors contain the algorithms and business logic
Navigation: The structure provides ways to traverse and access elements
Extensibility: New operations are added as new visitors, not new methods

Key Terminology

Visitor: The object that contains operations to be performed on elements
Element: Objects in the structure that can accept visitors
Concrete Visitor: Specific implementations of operations for different element types
Object Structure: The collection or hierarchy of elements that visitors operate on
Accept Method: The method in elements that enables visitor access via double dispatch

4. Detailed Explanation and Examples (25-30 minutes)

Understanding the Visitor Pattern

The Visitor pattern represents an operation to be performed on elements of an object structure. It lets you define new operations without changing the classes of the elements on which it operates. The pattern achieves this by defining operations in separate visitor classes rather than adding them to the element classes themselves.

The key insight is that when you have a stable object structure but need to perform many different operations on it, visitor pattern provides better organization than adding all operations to the element classes. Each visitor encapsulates a related set of operations, making the code more modular and easier to maintain.

When to Use Visitor Pattern

Stable Object Structure: When you have a well-defined object hierarchy that doesn’t change frequently but needs to support many different operations.

Frequent New Operations: When you regularly need to add new operations but rarely add new element types to the structure.

Complex Operations: When operations involve multiple element types and complex traversal logic that would clutter the element classes.

Separation of Concerns: When you want to keep operations separate from data structures for better organization and maintainability.

Common Misconceptions

Misconception: Visitor pattern is always better than adding methods to classes Reality: Visitor adds complexity and is only beneficial when you frequently add operations but rarely add new element types
Misconception: Visitors can only work with tree structures Reality: While commonly used with trees, visitors can work with any object structure including graphs, lists, and complex hierarchies
Misconception: The accept method breaks encapsulation Reality: When properly designed, accept methods provide controlled access while maintaining encapsulation of internal state

5. Live Coding Demonstration (20-25 minutes)

Example 1: Abstract Syntax Tree (AST) Processing

// Element interface - all nodes in our AST implement this
interface ASTNode {
    void accept(ASTVisitor visitor);
}

// Visitor interface - defines operations on AST nodes
interface ASTVisitor {
    void visit(NumberNode node);
    void visit(BinaryOperationNode node);
    void visit(VariableNode node);
    void visit(AssignmentNode node);
}

// Concrete element classes
class NumberNode implements ASTNode {
    private final double value;
    
    public NumberNode(double value) {
        this.value = value;
    }
    
    public double getValue() {
        return value;
    }
    
    @Override
    public void accept(ASTVisitor visitor) {
        visitor.visit(this);  // Double dispatch - this method determines the node type
    }
    
    @Override
    public String toString() {
        return String.valueOf(value);
    }
}

class BinaryOperationNode implements ASTNode {
    private final ASTNode left;
    private final ASTNode right;
    private final String operator;
    
    public BinaryOperationNode(ASTNode left, String operator, ASTNode right) {
        this.left = left;
        this.operator = operator;
        this.right = right;
    }
    
    public ASTNode getLeft() { return left; }
    public ASTNode getRight() { return right; }
    public String getOperator() { return operator; }
    
    @Override
    public void accept(ASTVisitor visitor) {
        visitor.visit(this);  // Visitor will know this is a BinaryOperationNode
    }
    
    @Override
    public String toString() {
        return "(" + left + " " + operator + " " + right + ")";
    }
}

class VariableNode implements ASTNode {
    private final String name;
    
    public VariableNode(String name) {
        this.name = name;
    }
    
    public String getName() {
        return name;
    }
    
    @Override
    public void accept(ASTVisitor visitor) {
        visitor.visit(this);
    }
    
    @Override
    public String toString() {
        return name;
    }
}

class AssignmentNode implements ASTNode {
    private final String variableName;
    private final ASTNode expression;
    
    public AssignmentNode(String variableName, ASTNode expression) {
        this.variableName = variableName;
        this.expression = expression;
    }
    
    public String getVariableName() { return variableName; }
    public ASTNode getExpression() { return expression; }
    
    @Override
    public void accept(ASTVisitor visitor) {
        visitor.visit(this);
    }
    
    @Override
    public String toString() {
        return variableName + " = " + expression;
    }
}

Explanation:

Each AST node implements the accept method that takes a visitor
The accept method calls visitor.visit(this), enabling double dispatch
Visitors can operate on the AST without modifying the node classes

Example 2: Expression Evaluator Visitor

import java.util.HashMap;
import java.util.Map;

// Concrete visitor for evaluating expressions
class EvaluatorVisitor implements ASTVisitor {
    private final Map<String, Double> variables;
    private double result;
    
    public EvaluatorVisitor() {
        this.variables = new HashMap<>();
    }
    
    public EvaluatorVisitor(Map<String, Double> initialVariables) {
        this.variables = new HashMap<>(initialVariables);
    }
    
    @Override
    public void visit(NumberNode node) {
        result = node.getValue();
        System.out.println("Evaluating number: " + result);
    }
    
    @Override
    public void visit(BinaryOperationNode node) {
        // Visit left operand
        node.getLeft().accept(this);
        double leftValue = result;
        
        // Visit right operand
        node.getRight().accept(this);
        double rightValue = result;
        
        // Perform operation
        switch (node.getOperator()) {
            case "+":
                result = leftValue + rightValue;
                break;
            case "-":
                result = leftValue - rightValue;
                break;
            case "*":
                result = leftValue * rightValue;
                break;
            case "/":
                if (rightValue != 0) {
                    result = leftValue / rightValue;
                } else {
                    throw new ArithmeticException("Division by zero");
                }
                break;
            default:
                throw new UnsupportedOperationException("Unknown operator: " + node.getOperator());
        }
        
        System.out.println("Evaluating " + leftValue + " " + node.getOperator() + " " + rightValue + " = " + result);
    }
    
    @Override
    public void visit(VariableNode node) {
        if (variables.containsKey(node.getName())) {
            result = variables.get(node.getName());
            System.out.println("Variable " + node.getName() + " = " + result);
        } else {
            throw new RuntimeException("Undefined variable: " + node.getName());
        }
    }
    
    @Override
    public void visit(AssignmentNode node) {
        // Evaluate the expression
        node.getExpression().accept(this);
        double value = result;
        
        // Store in variables
        variables.put(node.getVariableName(), value);
        result = value; // Assignment returns the assigned value
        
        System.out.println("Assigned " + node.getVariableName() + " = " + value);
    }
    
    public double getResult() {
        return result;
    }
    
    public Map<String, Double> getVariables() {
        return new HashMap<>(variables);
    }
}

Key Points:

The visitor maintains its own state (result, variables)
Complex operations involve recursive visitor calls
Each visit method handles a specific node type appropriately

Example 3: Pretty Printer Visitor

// Another visitor for formatting/printing expressions
class PrettyPrinterVisitor implements ASTVisitor {
    private final StringBuilder output;
    private int indentLevel;
    private final String indentString = "  ";
    
    public PrettyPrinterVisitor() {
        this.output = new StringBuilder();
        this.indentLevel = 0;
    }
    
    @Override
    public void visit(NumberNode node) {
        appendLine("Number: " + node.getValue());
    }
    
    @Override
    public void visit(BinaryOperationNode node) {
        appendLine("BinaryOperation: " + node.getOperator());
        
        indentLevel++;
        appendLine("Left:");
        indentLevel++;
        node.getLeft().accept(this);
        indentLevel--;
        
        appendLine("Right:");
        indentLevel++;
        node.getRight().accept(this);
        indentLevel -= 2;
    }
    
    @Override
    public void visit(VariableNode node) {
        appendLine("Variable: " + node.getName());
    }
    
    @Override
    public void visit(AssignmentNode node) {
        appendLine("Assignment to: " + node.getVariableName());
        indentLevel++;
        appendLine("Expression:");
        indentLevel++;
        node.getExpression().accept(this);
        indentLevel -= 2;
    }
    
    private void appendLine(String text) {
        for (int i = 0; i < indentLevel; i++) {
            output.append(indentString);
        }
        output.append(text).append("\n");
    }
    
    public String getResult() {
        return output.toString();
    }
    
    public void reset() {
        output.setLength(0);
        indentLevel = 0;
    }
}

// Code Analyzer Visitor - demonstrates complex analysis
class CodeAnalyzerVisitor implements ASTVisitor {
    private int nodeCount = 0;
    private int operationCount = 0;
    private int variableCount = 0;
    private int assignmentCount = 0;
    private final Map<String, Integer> operatorFrequency = new HashMap<>();
    private final Set<String> variablesUsed = new HashSet<>();
    
    @Override
    public void visit(NumberNode node) {
        nodeCount++;
    }
    
    @Override
    public void visit(BinaryOperationNode node) {
        nodeCount++;
        operationCount++;
        
        String operator = node.getOperator();
        operatorFrequency.put(operator, operatorFrequency.getOrDefault(operator, 0) + 1);
        
        // Continue traversal
        node.getLeft().accept(this);
        node.getRight().accept(this);
    }
    
    @Override
    public void visit(VariableNode node) {
        nodeCount++;
        variableCount++;
        variablesUsed.add(node.getName());
    }
    
    @Override
    public void visit(AssignmentNode node) {
        nodeCount++;
        assignmentCount++;
        variablesUsed.add(node.getVariableName());
        
        // Analyze the expression being assigned
        node.getExpression().accept(this);
    }
    
    public void printStatistics() {
        System.out.println("=== Code Analysis Results ===");
        System.out.println("Total nodes: " + nodeCount);
        System.out.println("Operations: " + operationCount);
        System.out.println("Variable references: " + variableCount);
        System.out.println("Assignments: " + assignmentCount);
        System.out.println("Unique variables: " + variablesUsed.size());
        System.out.println("Variables used: " + variablesUsed);
        System.out.println("Operator frequency: " + operatorFrequency);
    }
    
    public void reset() {
        nodeCount = operationCount = variableCount = assignmentCount = 0;
        operatorFrequency.clear();
        variablesUsed.clear();
    }
}

Complete Application Demo

public class VisitorPatternDemo {
    public static void main(String[] args) {
        // Build an AST: x = (10 + 5) * 2
        ASTNode ast = new AssignmentNode("x",
            new BinaryOperationNode(
                new BinaryOperationNode(
                    new NumberNode(10),
                    "+",
                    new NumberNode(5)
                ),
                "*",
                new NumberNode(2)
            )
        );
        
        System.out.println("Original expression: " + ast);
        System.out.println();
        
        // Use evaluator visitor
        System.out.println("=== Evaluation ===");
        EvaluatorVisitor evaluator = new EvaluatorVisitor();
        ast.accept(evaluator);
        System.out.println("Final result: " + evaluator.getResult());
        System.out.println("Variables: " + evaluator.getVariables());
        System.out.println();
        
        // Use pretty printer visitor
        System.out.println("=== Pretty Print ===");
        PrettyPrinterVisitor printer = new PrettyPrinterVisitor();
        ast.accept(printer);
        System.out.println(printer.getResult());
        
        // Use analyzer visitor
        System.out.println("=== Analysis ===");
        CodeAnalyzerVisitor analyzer = new CodeAnalyzerVisitor();
        ast.accept(analyzer);
        analyzer.printStatistics();
    }
}

6. Hands-On Practice (30-40 minutes)

Exercise 1: File System Visitor (10 minutes)

Objective: Implement visitors for file system operations

Instructions:

Create File and Directory elements that can accept visitors
Implement a SizeCalculatorVisitor that computes total size
Create a FileFinderVisitor that searches for files by extension

Starter Code:

interface FileSystemElement {
    void accept(FileSystemVisitor visitor);
}

interface FileSystemVisitor {
    void visit(File file);
    void visit(Directory directory);
}

class File implements FileSystemElement {
    private String name;
    private long size;
    
    // TODO: Implement constructor and accept method
}

class Directory implements FileSystemElement {
    private String name;
    private List<FileSystemElement> children;
    
    // TODO: Implement constructor and accept method
}

Solution:

import java.util.*;

interface FileSystemElement {
    void accept(FileSystemVisitor visitor);
    String getName();
}

interface FileSystemVisitor {
    void visit(File file);
    void visit(Directory directory);
}

class File implements FileSystemElement {
    private final String name;
    private final long size;
    private final String extension;
    
    public File(String name, long size) {
        this.name = name;
        this.size = size;
        this.extension = getFileExtension(name);
    }
    
    private String getFileExtension(String fileName) {
        int lastDot = fileName.lastIndexOf('.');
        return lastDot > 0 ? fileName.substring(lastDot + 1) : "";
    }
    
    @Override
    public void accept(FileSystemVisitor visitor) {
        visitor.visit(this);
    }
    
    @Override
    public String getName() { return name; }
    public long getSize() { return size; }
    public String getExtension() { return extension; }
}

class Directory implements FileSystemElement {
    private final String name;
    private final List<FileSystemElement> children;
    
    public Directory(String name) {
        this.name = name;
        this.children = new ArrayList<>();
    }
    
    public void addChild(FileSystemElement element) {
        children.add(element);
    }
    
    @Override
    public void accept(FileSystemVisitor visitor) {
        visitor.visit(this);
    }
    
    @Override
    public String getName() { return name; }
    public List<FileSystemElement> getChildren() { return children; }
}

class SizeCalculatorVisitor implements FileSystemVisitor {
    private long totalSize = 0;
    
    @Override
    public void visit(File file) {
        totalSize += file.getSize();
        System.out.println("File: " + file.getName() + " (" + file.getSize() + " bytes)");
    }
    
    @Override
    public void visit(Directory directory) {
        System.out.println("Directory: " + directory.getName());
        for (FileSystemElement child : directory.getChildren()) {
            child.accept(this);
        }
    }
    
    public long getTotalSize() { return totalSize; }
    public void reset() { totalSize = 0; }
}

class FileFinderVisitor implements FileSystemVisitor {
    private final String targetExtension;
    private final List<File> foundFiles = new ArrayList<>();
    
    public FileFinderVisitor(String extension) {
        this.targetExtension = extension.toLowerCase();
    }
    
    @Override
    public void visit(File file) {
        if (file.getExtension().toLowerCase().equals(targetExtension)) {
            foundFiles.add(file);
        }
    }
    
    @Override
    public void visit(Directory directory) {
        for (FileSystemElement child : directory.getChildren()) {
            child.accept(this);
        }
    }
    
    public List<File> getFoundFiles() { return new ArrayList<>(foundFiles); }
    public void reset() { foundFiles.clear(); }
}

Exercise 2: Shopping Cart Visitor System (15 minutes)

Objective: Create visitors for different pricing and analysis operations on shopping cart items

Requirements:

Support different item types (Book, Electronics, Clothing) with different properties
Implement visitors for: tax calculation, discount application, shipping cost calculation
Handle complex business rules (e.g., books have no tax, electronics have warranty, clothing has size/color)

Hints:

Consider how different item types have different pricing rules
Think about how visitors can accumulate results across all items

Exercise 3: Document Processing System (15 minutes)

Objective: Build a document visitor system for processing structured documents

Challenge: Implement a system that supports:

Document elements: paragraphs, headers, lists, images, tables
Visitors for: word count, spell checking, formatting conversion, content extraction
Hierarchical document structure with nested elements

Extension Ideas:

Add support for document styling and formatting
Implement document validation visitors
Create export visitors for different formats (HTML, PDF, plain text)

7. Common Pitfalls and Troubleshooting (10 minutes)

Frequent Mistakes

Problem: Forgetting to implement the accept method properly Cause: Not understanding that accept method enables double dispatch Solution: Ensure accept method calls visitor.visit(this) where this is the specific element type
Problem: Adding new element types breaks existing visitors Cause: Visitor interface requires methods for all element types Solution: Consider using default methods in interfaces or abstract base visitors for optional operations
Problem: Circular dependencies between elements and visitors Cause: Elements importing visitor types directly Solution: Use dependency inversion - elements should only depend on visitor interfaces, not concrete implementations
Problem: Performance issues with deep object structures Cause: Recursive visitor calls on large hierarchies Solution: Implement iterative traversal or use stack-based approaches for very deep structures

Debugging Tips

Visitor Call Tracing: Add logging to visit methods to trace traversal patterns
Type Safety: Use generics or type checking to ensure visitor compatibility
State Management: Be careful with visitor state when processing multiple structures
Exception Handling: Implement proper error handling for malformed structures

8. Best Practices and Professional Tips (5 minutes)

Industry Standards

Interface Segregation: Create focused visitor interfaces for related operations
Default Implementations: Use abstract base visitors to provide default behavior
State Management: Design visitors to be stateless when possible, or clearly document state behavior

Performance Considerations

Visitor Reuse: Design visitors to be reusable across multiple traversals
Lazy Evaluation: Implement lazy evaluation for expensive visitor operations
Memory Management: Be mindful of memory usage when visitors accumulate large amounts of data

Next Steps in Your Learning Journey

Interpreter Pattern: Study how visitor and interpreter patterns work together
Compiler Design: Learn about more sophisticated AST processing techniques
Tree Processing Algorithms: Explore advanced tree traversal and analysis algorithms

9. Summary and Review (5 minutes)

Key Takeaways

Operation Separation: Visitor pattern cleanly separates algorithms from object structures
Double Dispatch: The pattern uses double dispatch to enable type-safe operation selection
Extensibility: New operations can be added without modifying existing element classes

Quick Review Questions

How does the visitor pattern achieve double dispatch in single-dispatch languages?
When would you choose visitor pattern over simply adding methods to element classes?
What are the trade-offs between visitor pattern and alternative approaches like strategy pattern?

For Instructors

Teaching Tips

Visual Diagrams: Use UML diagrams to show the relationships between elements and visitors
Interactive Examples: Build ASTs interactively and show how different visitors process them differently
Real-World Context: Discuss actual applications like compilers, static analysis tools, and document processors

Common Student Questions and Responses

“Why not just use instanceof and casting?” - Explain how visitor provides type safety and better organization than type checking
“This seems overly complex for simple operations” - Discuss when complexity is justified by flexibility and maintainability
“How does this compare to functional programming approaches?” - Show how visitor pattern and functional approaches solve similar problems differently

Assessment Ideas

AST Processor: Have students build complete expression evaluators or code analyzers
Document System: Implement comprehensive document processing with multiple visitor types
Performance Analysis: Compare visitor pattern performance with alternative approaches

Adaptation Notes

For Beginners: Start with simple two-element hierarchies before moving to complex structures
For Advanced Students: Discuss advanced topics like visitor composition, generic visitors, and distributed processing
Language-Specific: Adapt examples to leverage language-specific features (pattern matching, multiple dispatch, etc.)