Visitors and Multiple Dispatch

Monday, March 10, 2008

The visitor pattern is an elegant solution to a specific class of problems, but also comes with drawbacks in mainstream programming languages. There are various techniques one can us to minimize the drawbacks, however. This weekend I found some old but good articles harnessing the power of visitor while removing some of the pain:

Both Brad and Kzu use reflection to effectively achieve multiple dispatch. The typical multiple dispatch mechanism used to implement the visitor pattern is a drag on maintenance and forces the pattern implementation to bleed into the visitor's targets – Brad's post shows all the gory details before he goes on the show a solution using reflection. Multiple dispatch isn't just a problem in C#, C++, and Java – it's also a problem in dynamic languages like Python and Ruby. Only a handful of languages inherently use multiple dispatch, or multimethods, with Common Lisp being the most notable.

I tried a dispatch mechanism using Expression<T> today, but (in case you don't want to read any further) did not get a satisfactory result. If you keep reading, maybe you can think of something I missed. 

Given these classes:

public class Employee
{
    
public string Name { get; set; }
}

public class Manager : Employee
{
}

How can you write a class like the following?

public class EmployeeReport
{
    
public void Generate(IEnumerable<Employee> employees)
    {
        
foreach (Employee employee in employees)
        {
            Visit(employee);
        }
    }

    
void Visit(Employee employee)
    {
        
// employee specific work ...
        Console.WriteLine("Visiting employee {0}", employee.Name);
    }

    
public void Visit(Manager manager)
    {
        
// manager specific work ...
        Console.WriteLine("Visiting manager {0}", manager.Name);
    }
}

The compiler will lay down code to invoke the Visit method that accepts an Employee reference, even when we really are referencing a Manager object at runtime. We need some mechanism that will thunk us into the best method based on the runtime type of the parameter, preferably without using a switch statement. A naïve try might look like the following:

public void Generate(IEnumerable<Employee> employees)
{
    
foreach (Employee employee in employees)
    {
        DispatchVisit(employee);
    }
}

void DispatchVisit(Employee visitee)
{
    
Expression<Action<Employee>> expression = e => this.Visit(e);
    expression.Compile().Invoke(visitee);
}

Even though this code is generating IL at runtime via Compile, it still invokes the wrong method when we reach a Manager object. At compile time the compiler generates an expression tree to invoke the Visit accepting an Employee reference. We could go into the expression and make modifications to the Body before we call Compile, or we could build an expression tree manually. Either way, we need to pick out the exact method we need at runtime using the type of the parameter and a call to GetMethod:

void DispatchVisit(Employee visitee)
{
    
MethodInfo methodInfo = this.GetType().GetMethod(
                                
"Visit", new Type[] { visitee.GetType() });
    
    
ParameterExpression e = Expression.Parameter(visitee.GetType(), "e");
    
LambdaExpression expression =
        
Expression.Lambda(
            
Expression.Call(
                
Expression.Constant(this, typeof(EmployeeReport)),
                methodInfo,
                e),
             e);

    
    expression.Compile().DynamicInvoke(visitee);
}

This code works, because we are now getting a MethodInfo object that will reference Visit(Manager employee) when we have a manger object at runtime. But, the code is starting to look just as hairy as any other code generation technique, and we haven't even tried to address caching the compiled expression for performance, or moving up to an Expression<T>. 



Comments
Jonathan Allen Monday, March 10, 2008
I think it's kinda funny that not only has VB.NET has had this all along, but it was there for compatibility with VB6.

Anyways, most of your multiple dispatch needs can be covered by this function.

Microsoft.VisualBasic.Interaction.CallByName
spleenboy Monday, March 10, 2008
Am I being naive by saying this will work?

Visit(employee as Manager ?? employee as Employee);
scott Monday, March 10, 2008
@spleenboy:

Unfortunately, no, because the compiler has already selected the [void Visit(Employee e)] method at compile time.

@Jonathan:

I just tried CallByName and it appears to have the opposite problem.

Interaction.CallByName(this, "Visit", CallType.Method, visitee);

wants to invoke Visit(Manager) everytime, resulting in an invalid cast execption. How to handle overloads with CallByName?
Kalpesh Monday, March 10, 2008
Wouldn't it be better to have separate class for Report? i.e. EmployeeReport & ManagerReport

Have visit as virtual method for EmployeeReportWriter & override it for ManagerReportWriter. Also, there could be a base interface for ReportWriter, which can be attached to specific class. So, Employee could have default reportwriter as EmployeeReportWriter and Manager could have ManagerReportWriter.

Hope I am not being stupid in presence of experts :)
scott Monday, March 10, 2008
Kalpesh:

It all depends on the scenario. In my simple example I used only Employee and Manager. Imagine maybe 12 or 120 more types involved. I don't want a report class dedicated for each type, but I need to iterate through a collection of all those different types and produce slightly different behavior for each (print the manager in bold, for example). I don't want to modify the employee based classes at all. Like I say, depends on the scenario.
Michael Koeller Thursday, March 13, 2008
Hm, what about employing polymorphism? The major drawback is that you need an additional interface and modifications/additions to the Employee class. Nevertheless it should work, shoudn't it?

Note: I'm typing the code directly here in the comment text area, so please forgive me the typos and syntax errors. I hope the basic idea comes through anyway. And I also hope that the code example I'm going to type may stay formatted in a way that it's readable.



public class Employee
{
public string Name { get; set; }

accept(EmployeeVisitor v) {
v.Visit(this);
}
}

public interface EmployeeVisitor {
void Visit(Employee e);
void Visit(Manager m);
}

public class EmployeeReport implements EmployeeVisitor
{
public void Generate(IEnumerable<Employee> employees)
{
foreach (Employee employee in employees)
{
employee.Visit(this);
}
}

public void Visit(Employee employee)
{
// employee specific work ...
Console.WriteLine("Visiting employee {0}", employee.Name);
}

public void Visit(Manager manager)
{
// manager specific work ...
Console.WriteLine("Visiting manager {0}", manager.Name);
}
}



What do you think?
admin Thursday, March 13, 2008
Michael:

Yep, that approach works. It's a tradeoff you have to evaluate, and in scenarios where there re a large number of 'visitable' types mutiplied by vsitor types - you might prefer an approach with less maintenance like the reflection approach.

Both valid alternatives.
Hector Contreras Monday, March 24, 2008
I need to design a higher-level Windows Communication Foundation (WCF) service that controls lower level WCF services. Would the Visitor design pattern be a good fit for this? Is it possible to implement the Visitor design pattern in WCF? Is there a better solution? Are you the author of "Programming Windows Workflow Foundation?"
scott Monday, March 24, 2008
Hector: yes that's me the author.

Re: WCF - I'm not sure if visitor is a good fit without some more details, but visitor is technology agnostic.
Hector Contreras Monday, March 24, 2008
Then I have your book! I read it a lot in between my past two jobs. Unfortunately, where I'm at we're not implementing Windows WF yet, only WCF, but maybe soon. I have trouble deciding what should be done in Windows WF and what should be done in BizTalk. But that's another topic.

Back to the topic at hand ... I want to take a higher level call to a service like CreateOrder, and break it up into the following lower level subservices: SaveOrder, PrintOrder, SendOrderNotification. I thought the CreateOrder service would be the central controller (Visitor) with the other subservices being the Elements.
gravatar Kannan Sunday, May 2, 2010
Hi Scott,

Can you tell me what is the difference between single dispatch, Multiple dispatch, dynamic dispatch in .NET
Comments are now closed.
by K. Scott Allen K.Scott Allen
My Pluralsight Courses
The Podcast!