visitor-experiment

• after reading https://nipafx.dev/java-visitor-pattern-pointless/, decided to question my allegiance to the visitor pattern
• have worked with it a lot as part of going through crafting interpreters, as well as ameba / crystal compiler / larimar
• there may be other ways to build visitors that are easier to understand, use less memory, and are faster
• decided to do a small test / benchmark

Traditional visitor pattern in Crystal:

abstract class Node
  def accept(visitor : VisitorA)
    if visitor.visit(self)
      accept_children visitor
    end
  end

  abstract def accept_children(visitor : VisitorA) : Nil
end

class VisitorA
  def accept(node)
    node.accept(self)
  end
end

New visitor pattern:

abstract class Node
  abstract def each_child(& : Node ->)
end

class VisitorT
  def accept(node : Node) : Nil
    if visit(node)
      node.each_child { |child| accept(child) }
    end
  end
end

And some nodes:

class Fun < Node
  getter name : String
  getter params : Array(Param)
  getter body : Node

  def initialize(@name, @params, @body)
  end

  def each_child(&)
    params.each do |param|
      yield param
    end
    yield body
  end

  def accept_children(visitor) : Nil
    params.each &.accept(visitor)
    body.accept(visitor)
  end
end

class Expressions < Node
  getter body : Array(Node)

  def initialize(@body)
  end

  def each_child(& : Node -> Nil)
    body.each do |element|
      yield element
    end
  end

  def accept_children(visitor) : Nil
    body.each &.accept(visitor)
  end
end

The primary difference being in limiting the amount of code that needs to pass through the node class itself, though it is required to have some sort of method to get a list of the child nodes.

Creating a small visitor to get the list of funs in a complex AST:

class FunVisitor < Visitor
  getter funs : Array(String) = Array(String).new

  def visit(node)
    true
  end

  def visit(node : LM::Fun)
    @funs << node.name

    true
  end
end

The end result is about the same performance wise:

old visitor  12.44k ( 80.39µs) (±32.39%)  955kB/op   1.02× slower
new visitor  12.71k ( 78.66µs) (±29.76%)  742kB/op        fastest

But the benefits come from something that's simpler to understand, and a reduced stack size through not needing to pass the visitor object itself into the node (no double indirection). As well, this is more separated from the node structure itself while also requiring minimal to no changes to the visitors itself.