How to pretty-print an AST using Visitor pattern?

Question

I am trying to build a simple interpreter using the Visitor pattern. I'm having a difficult time trying to understand how a task such as pretty-printing the tree can be implemented using this pattern.

The result I am trying to obtain is printing the AST with proper indentation:

Expr
'---Abstr
    |---Id
    '---Expr
        '---App
            '---Atom
                '---Id

I have defined a number of classes representing nodes in the AST:

class ASTNode
    attr_reader :children, :pos

    def initialize(children, pos)
         @children = children
         @pos = pos
    end

    def accept(visitor)
        visitor.visit(self)
        @children.each { |child| child.accept(visitor) } unless @children.nil?
    end
end

class ExprNode < ASTNode
    def initialize(children, pos)
         super(children, pos)
    end
end

...

and a base visitor class performing double dispatch:

class Visitor
    def visit(subject)
        method_name = "visit_#{subject.class}".intern
        send(method_name, subject)
    end
end

Finally, the visitor for printing the AST:

class PrintVisitor < Visitor
    def visit_ExprNode(subject)
    end

    def visit_AbstrNode(subject)
    end

    ...
end

What did you try? I don't see attempts to print to stdout, or mark nodes as visited. — Danilo Cabello
I could try printing to stdout, but the visitor makes operations performed in nodes independent. Printing each node requires additional context to determine the right indentation level. I assume that the printing should be implemented in visit_*Node(subject) methods of PrintVisitor - doing the indenting there is not possible. My understanding of visitor is quite limited and I don't know whether my use of the pattern is correct or not. — Jan Parzydło

sepp2k sepp2k · Accepted Answer · 2019-05-26T10:03:22

There are two versions of the visitor pattern: One version only takes care of the double dispatch and the other also takes care of iteration by automatically visiting a node's children. The latter version is less flexible because you decide what kind of traversal (pre-order or post-order) you want ahead of time instead of leaving that decision to the individual visitor. It also forces you to visit all the nodes exactly once (which you wouldn't want in many cases, such as when implementing an AST interpreter).

In your code you're actually implementing both of those versions: Your Visitor#visit method implements the plain visitor pattern and ASTNode#accept implements the one with iteration. That's a weird use of the accept method because usually the job of the accept method is simply to call a specific visit method (like visit_whatever) on the visitor to get the double dispatch to work. Since you've used reflection to implement the double dispatch, you don't need an accept method at all.

I assume that the printing should be implemented in visit_*Node(subject) methods of PrintVisitor

That is correct.

Printing each node requires additional context to determine the right indentation level.

Also correct. You can keep track of the indentation level by storing it in an instance variable. Then a given visitor method would print its contents with the given amount of indentation, increase the indentation level, visit its child notes, and then decrease the indentation again. Something like this:

def visit_SomeNode(some_node)
    puts "#{@indent * " "}---SomeNode"
    @indent += 4
    some_node.children.each {|child| visit(child)}
    @indent -= 4
end

You could also put some_node.children.each {|child| visit(child)} into its own visit_children(node) method and just call that for the cases where you want to perform the same action for all children (as above).

If you want to avoid that mutable state, you can also adjust your visitor class to allow passing arguments to visit like this:

class Visitor
    def visit(subject, *args)
        method_name = "visit_#{subject.class}".intern
        send(method_name, subject, *args)
    end
end

Then you can add a parameter for the indentation level to your methods and pass an increased indentation level to visit when visiting your children.

How to pretty-print an AST using Visitor pattern?

1 Answers