The Visitor Pattern: Double Dispatch, AST Traversal, and Type-Safe Extensibility

The Visitor Pattern is a classic behavioral design pattern that allows developers to define new operations on complex object structures (such as Abstract Syntax Trees, document models, or composite hierarchies) without modifying the classes of the elements on which it operates.

This guide details double dispatch mechanics, AST traversal pipelines, memory safety, and modern pattern matching language alternatives.

---

1. Quick-Reference: Visitor Pattern Structure

Double Dispatch Sequence:
[ Client Code ] ---> `element.accept(visitor)`
                             |
                             v
[ ConcreteElementNode ] ---> `visitor.visit(this)`
                                      |
                                      v
[ ConcreteVisitor ] <--- Executes specific logic for ConcreteElementNode!

---

2. Java Implementation Pattern

// Element Interface
public interface AstNode {
    <R> R accept(AstVisitor<R> visitor);
}

// Concrete Elements
public record BinaryOpNode(AstNode left, String op, AstNode right) implements AstNode {
    @Override
    public <R> R accept(AstVisitor<R> visitor) {
        return visitor.visitBinaryOp(this);
    }
}

// Visitor Interface
public interface AstVisitor<R> {
    R visitBinaryOp(BinaryOpNode node);
    R visitLiteral(LiteralNode node);
}