For sure! At least, so long as your language supports them. For example, Go didn’t support them for most of its existence, and I think that has only recently started to change (pretty sure I caught wind of discussion around that anyway). Of course it doesn’t have pattern matching either, so maybe it isn’t a great example here. I suppose the takeaway here is that, if your language provides better tools for the sort of use cases a visitor makes sense for, definitely use them!

Here is an example from the Python-to-C++ translator in Oils – mycpp

I never liked visitors myself – the main reason this uses visitors is because MyPy does. (We reached into MyPy’s internals and borrowed its structure.)

One thing that bugs me about visitors is that you lose the stack. You end up having to put more stuff in class members instead of params on the stack.

It is kind of like a sync vs. state machine issue – the state machines are harder to write. async/await gives you back the stack.

As some others have pointed out, there is one class SimpleVisitor that has the traversal logic

And then we have an inherited const pass that does a “generic” traversal over all the string literal nodes, at arbitrary depths, wherever they appear

class SimpleVisitor:

    def visit_while_stmt(self, o: 'mypy.nodes.WhileStmt') -> None:
        self.accept(o.expr)
        self.accept(o.body)

    def visit_return_stmt(self, o: 'mypy.nodes.ReturnStmt') -> None:
        if o.expr:
            self.accept(o.expr)

   # ... 30 more methods, for every part of the AST

https://github.com/oils-for-unix/oils/blob/master/mycpp/visitor.py

and then

class Collect(visitor.TypedVisitor):  # subclass of SimpleVisitor

    # no traversal logic in this class

    def visit_str_expr(self, o: StrExpr) -> None:
        raw_string = format_strings.DecodeMyPyString(o.value)
        self.global_strings.Add(o, raw_string)

https://github.com/oils-for-unix/oils/blob/master/mycpp/const_pass.py#L107

So you can have many passes, without repeating the traversal logic on the typed AST.

Using the a preorder iterator like matklad suggested would be very possible here, although I stuck with the structure inherited from MyPy

For other passes, where you need to keep track of some state per subtree, I am not sure if it would be as convenient

Actually I noticed in Siek’s Essentials of Compilation - https://mitpress.mit.edu/9780262048248/essentials-of-compilation/

He says you just need “open recursion”. You just use inheritance without visitors I think. I think that would work for this visit_str_expr() thing:

https://journal.stuffwithstuff.com/2013/08/26/what-is-open-recursion/

Visitors are controversial, and I have seen the exact argument in this thread before:

• “you don’t need visitors if you use pattern matching!”
• “yes visitors are still useful!”

I would like someone to write up some definitive comparison of this, preferably in multiple languages. I think the issue is there are many types of tree traversals, and some are slightly more convenient in one style vs. another.

Mycpp has 6 passes now, and over time the visitors have grown on me, although I would still like to try another style. Again I think it will probably be the case that certain passes are easier in one style vs. another.

It’s certainly possible to use visitors for everything, and that’s what MyPy does!!! It seems very verbose and un-Python-like, but it does work … and it is much more complex than mycpp, being a gradual type checker

Almost every linting tool that supports custom lints implements those through the visitor pattern. Consider Rubocop and ESLint. I’m pretty sure that’s the exact scenario GP is talking about - writing custom rules with pattern matching and without visitors would require each rule to navigate the entire tree.

At the same time, I don’t know if asking for a “simple” example makes the case for whether or not the visitor pattern is useful. Maybe there’s no simple cases, but a lot of really complex ones?

LLVM has a bunch of visitor classes using CRTP. The useful thing versus raw pattern matching is the ability to do more generic things. The clang AST visitors make it trivial to find specific nodes at arbitrary depths, ignoring intermediates. For example, if I want to write a clang-tidy rule about C-style casts (I don’t, it’s there already) I can write a visitor that matches cast expressions. These will typically be ten or more levels deep in the tree, but I don’t need to care about any of the nodes that I need to travers to get there.

For a shallower tree, LLVM’s instruction visitor visits every instruction in a function. The traversal is trivial here (two-deep nested iterators) but the subtyping can be complex. For a simple example, in some cases I care about call instructions (which call non-throwing things and so have no intraprocedural control flow) and may want to handle invokes (which branch to one of two basic blocks to model exception flow) separately, in other cases I care about either and it’s the callee that matters not how it was called. In this case, I can implement the CallSite visitor method and get both via a wrapper type, rather than having to match call and invoke instructions and then dispatch to a common type myself. Similarly, it I care about binary integer arithmetic operations, I can match this in a single method. The visitor also handles priorities, so if I implement the method for binary operations and the method for add instructions, I will get the specific one called for adds and the general one called for everything else.

I could implement the same thing with iterators and pattern matching equivalent code (if (auto Foo = dyn_cast<Thing>()) as the closest approximation) but even with more concise pattern matching syntax it wouldn’t be as good as using the visitors.

Sure, or at least, I can give you a example based on a DSL compiler I worked on awhile back, in Rust:

Let’s say you have an AST, for a language with modules, functions, various global declarations (such as imports of items from other modules, constants, etc.), and expressions consisting of let-bindings, various arithmetic operations, function invocation, comprehensions.

Your AST consists of structs for each node type, something like (intentionally over-simplified here):

pub struct Module {
    name: Symbol,
    functions: BTreeMap<Symbol, Function>,
}

pub struct FunctionIdent {
    module: Symbol,
    name: Symbol,
}

pub struct Function {
    id: FunctionIdent,
    signature: Signature,
    /// `None` indicates this is an imported declaration
    body: Option<Box<Expr>>,
}

pub enum Expr {
    Var(Symbol),
    Lit(Literal),
    BinaryOp(BinaryOp),
    UnaryOp(UnaryOp),
    Let(Let),
    Call(Call)
    Lc(ListComprehension),
}

/// <lhs> <opcode> <rhs>
pub struct BinaryOp {
    opcode: BinaryOperator,
    lhs: Box<Expr>,
    rhs: Box<Expr>,
}

pub enum BinaryOperator {
    Add,
    Sub,
    ...
}

pub struct Call {
    callee: Callee,
    args: Vec<Expr>,
}

pub enum Callee {
    Alias(Symbol),
    Qualified(FunctionIdent),
}

/// let <bound> = <init> in <body>
pub struct Let {
    bound: Symbol,
    init: Box<Expr>,
    body: Box<Expr>,
}

/// <body> for <binding> in <iterable>
/// <body> for (<binding0>, .., <bindingN>) in (<iterable0>, .., <iterableN>)
pub struct ListComprehension {
    bindings: Vec<Symbol>,
    iterables: Vec<Expr>,
    body: Box<Expr>
}

/// snip...

We define the basis of our reusable visitor via a Visit trait, and a set of default functions that implement the traversal details:

use core::ops::ControlFlow;

use crate::ast;

/// Implement this trait to define a visitor.
///
/// By default, all methods will simply traverse the AST.
///
/// # Example
///
/// The following demonstrates the basic usage patterns:
///
/// ```rust
/// use crate::{ast, visit};
///
/// struct PreOrderVisitor;
///
/// impl Visit<()> for PreOrderVisitor {
///     fn visit_expr(&mut self, expr: &ast::Expr) -> ControlFlow<()> {
///         // do stuff here...
///         visit::visit_expr(self, expr)
///     }
/// }
///
/// struct PostOrderVisitor;
///
/// impl Visit<()> for PostOrderVisitor {
///     fn visit_expr(&mut self, expr: &ast::Expr) -> ControlFlow<()> {
///         visit::visit_expr(self, expr)?;
///         // do stuff here...
///         ControlFlow::Continue(())
///     }
/// }
/// ```
pub trait Visit<T> {
    fn visit_module(&mut self, module: &ast::Module) -> ControlFlow<T> {
        visit_module(self, module)
    }
    fn visit_expr(&mut self, expr: &ast::Expr) -> ControlFlow<T> {
        visit_expr(self, expr)
    }
    fn visit_let(&mut self, expr: &ast::Let) -> ControlFlow<T> {
        visit_let(self, expr)
    }
    /// snip...
}

/// Automatically implement `Visit` for references to a `Visit` impl.
///
/// Primarily useful for allowing the use of `dyn Visit` in place of a concrete type.
impl<'a, V, T> Visit<T> for &'a V
where
    V: ?Sized + Visit<T>,
{
    fn visit_module(&mut self, module: &ast::Module) -> ControlFlow<T> {
        (**self).visit_module(module)
    }
    fn visit_expr(&mut self, expr: &ast::Expr) -> ControlFlow<T> {
        (**self).visit_expr(expr)
    }
    fn visit_let(&mut self, expr: &ast::Let) -> ControlFlow<T> {
        (**self).visit_let(expr)
    }
    /// snip...
}

/// These functions allow resuming traversal of a given node type from within `Visit`
/// when one has overridden the method for that node type. They are exported for
/// use by `Visit` implementations. 

pub fn visit_module<V, T>(visitor: &mut V, module: &ast::Module) -> ControlFlow<T>
where
    V: ?Sized + Visit<T>,
{
    for function in module.functions.values() {
        visitor.visit_function(function)?;
    }
    ControlFlow::Continue(())
}

pub fn visit_function<V, T>(visitor: &mut V, function: &ast::Function) -> ControlFlow<T>
where
    V: ?Sized + Visit<T>,
{
    match function.body.as_ref() {
        None => visitor.visit_function_declaration(function),
        Some(body) => visitor.visit_expr(body),
    }
    ControlFlow::Continue(())
}

pub fn visit_expr<V, T>(visitor: &mut V, expr: &ast::Expr) -> ControlFlow<T>
where
    V: ?Sized + Visit<T>,
{
    match expr {
        ast::Expr::Var(var) => visitor.visit_var(var),
        ast::Expr::Lit(lit) => visitor.visit_literal(lit),
        ast::Expr::Let(r#let) => visitor.visit_let(r#let),
        // snip...
    }
}

// snip..

So that’s the boilerplate, let’s look at what that actually amounts to in practice. As an example, let’s write a semantic analysis pass that verifies that all callees of a Call expression are valid symbols in scope:

#[derive(Default)]
pub struct VerifyCallTargets {
    current_module: Symbol,
    scope: BTreeSet<ast::FunctionIdent>,
}

impl VerifyCallTargets {
    pub fn verify(&mut self, module: &ast::Module) -> Result<(), SemanticAnalysisError> {
        match self.visit_module(module) {
            ControlFlow::Continue(_) => Ok(()),
            ControlFlow::Break(err) => Err(err),
        }
    }

    fn verify_callee(&self, callee: FunctionIdent) -> ControlFlow<SemanticAnalysisError> {
        if self.scope.contains(&callee) {
            ControlFlow::Continue(())
        } else {
            ControlFlow::Break(SemanticAnalysisError::UndefinedFunction(callee))
        }
    }
}

impl Visit<SemanticAnalysisError> for VerifyCallTargets {
    fn visit_module(&mut self, module: &ast::Module) -> ControlFlow< SemanticAnalysisError > {
        self.scope.clear();
        self.scope.extend(module.functions.values().map(|f| f.id));
        visit::visit_module(self, module)
    }

    fn visit_call(&mut self, call: &ast::Call) -> ControlFlow<SemanticAnalysisError > {
        match call.callee {
            Callee::Alias(name) => self.verify_callee(FunctionIdent { module: self.current_module, name }),
            Callee::Qualified(id) => self.verify_callee(id),
        }
    }
}

I’d like to reiterate that this isn’t the actual implementation I was working with, just a vastly simplified example based on a real implementation, so I’m just trying to illustrate the gist of it without getting too deep in the weeds on ancillary stuff that isn’t important (i.e. you’d ideally do a bunch of related checks in a single traversal, you’d want to gather all errors you can rather than short-circuiting the traversal at the first error, and so on).

Happy to answer any questions about this, but hopefully this was helpful in illustrating how this can solve problems in practice, even when you have pattern matching in your toolbox.