Visitor Pattern Notes

I have been working on building a new domain-specific programming language for graph applications. In the process, I am building a compiler, and really learned the importance of visitor patter. Here is a post summarizing some of the things I learned on visitor pattern.

This post is heavily based on an undergraduate course I took at Rice University (Comp 310) and my experience working in compilers.

Why do I need Visitor Pattern? 

Visitor Pattern allows updating the functionalities of data structures without modifying the implementation of data structures, decoupling algorithms from data structures.

The visitor pattern is very useful for a variety of reasons

  1. Decoupling of data structure and algorithms: In large production codebase, you might want to add new behaviors to existing objects, but you don’t want to frequently modify the object implementations. Good examples are included here https://www.delphix.com/blog/delphix-engineering/accepting-visitors (The alternative to visitor pattern is to add a class specific methods to every object)
  2. Improved Reusability: There are code that can be reused across the implementations of different objects. For example, in compiler implementation, often you can reuse significant portion of code for AddExpression and SubExpression’s print, parse, optimization methods (both binary expressions). In this case, it makes sense to put all the implementations in the same class to reuse helper methods.

 

What is Visitor Pattern?

There are two major components of the visitor pattern, Host and Visitor

  • Host: The Object (data structure)
  • Visitor: The Object Logic (algorithm)

Host

  • accept (Visitor vis) {vis -> visit(this);}
    • Implements an accept method that basically invokes the visitor’s relevant visit method for this instance of Host.

Visitor 

  • visit (HostType host) {… the algorithm …}
    • Implements the algorithm behavior for the host object

Full example (stolen from Wikipedia)

namespace Wikipedia
{
  using System;
  using System.Text;

  interface IExpressionVisitor
  {
    void Visit(Literal literal);
    void Visit(Addition literal);
  }

  interface IExpression
  {
    void Accept(IExpressionVisitor visitor);
  }

  class Literal : IExpression
  {
    internal double Value { get; set; }

    public Literal(double value)
    {
      this.Value = value;
    }
    public void Accept(IExpressionVisitor visitor)
    {
      visitor.Visit(this);
    }
  }

  class Addition : IExpression
  {
    internal IExpression Left { get; set; }
    internal IExpression Right { get; set; }

    public Addition(IExpression left, IExpression right)
    {
      this.Left = left;
      this.Right = right;
    }

    public void Accept(IExpressionVisitor visitor)
    {
      visitor.Visit(this);
    }
  }

  class ExpressionPrinter : IExpressionVisitor
  {
    StringBuilder sb;

    public ExpressionPrinter(StringBuilder sb)
    {
        this.sb = sb;
    }

    public void Visit(Literal literal)
    {
      sb.Append(literal.Value);
    }

    public void Visit(Addition addition)
    {
      sb.Append("(");
      addition.Left.Accept(this);
      sb.Append("+");
      addition.Right.Accept(this);
      sb.Append(")");
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      // emulate 1+2+3
      var e = new Addition(
        new Addition(
          new Literal(1),
          new Literal(2)
        ), 
        new Literal(3)
      );
      var sb = new StringBuilder();
      var expressionPrinter = new ExpressionPrinter(sb);
      e.Accept(expressionPrinter);
      Console.WriteLine(sb);
    }
  }
}

 

This is the classic compiler example of using a visitor pattern to print the expression nodes. If you like a toy example, again this blog is a good source https://www.delphix.com/blog/delphix-engineering/accepting-visitors.

 

The Hosts in this case are Expressions, specifically, Addition and Literal. The Visitor is Expression Printer, which extends IExpressionVisitor. One way to implement this would be to add a print function to Addition and Literal classes. But now, all the print logic are stored in the ExpressionPrinter class.

 

Interesting Technical Details 

Why do you need an accept method in every Host class?  (Can’t we

Most programming languages are single dispatch (Java, C++). As a result, we need to have the specific type of visitor and host to figure out the right method. As a result, in the accept method, we pass the “this” into the “visit” method. As a result, inside the visitor’s visit method, we know the concrete type of “host”(e.g. Addition) and “visitor” (e.g. PrintVisitor). This way, we simulate “double dispatch” in Object Oriented Languages.

Good references

  1. Comp 310 Rice https://www.clear.rice.edu/comp310/s17/lectures/lec19/
  2. Alumni from the class https://www.delphix.com/blog/delphix-engineering/accepting-visitors
  3. https://sourcemaking.com/design_patterns/visitor
Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s