Visitor.. What's in a visit anyways...

Recently I was reading Judith Bishop's C# 3.0 Design Patterns. The book has been a good read so far.The Visitor pattern implementation in the book however is implemented "classically" wherein each element of the structure being iterated over has an Accept operation which accepts an instance of a Visitor type. When the client invokes the operation on the Visitor which is supposed to kick start the visiting,the Visitor iterates over each element of the structure in some way and invokes the Accept operation passing in itself as a reference. The element in turn invokes the Visit operation on the Visitor (passing in itself) which in turn accepts an element instance and works with it(double dispatch). But my gut tells me something seems out of place here given that the book's intent is to implement the classic GOF patterns using C# 3.0 features. To put things into perspective, I created a small generic linked list implementation based on the classic Visitor pattern
 
  1. public interface INode<T>  
  2. {  
  3.     T Data { get; }  
  4.     INode<T> Next { getset; }  
  5.     void Accept(IVisitor<T> visitor);  
  6. }  
  7.   
  8. public class Node<T> : INode<T>  
  9. {  
  10.     public Node(T t)  
  11.     {  
  12.         Data = t;  
  13.   
  14.     }  
  15.   
  16.     public Node(T t,Node<T> next)  
  17.     {  
  18.         Data = t;  
  19.         Next = next;  
  20.     }  
  21.  
  22.     #region INode<T> Members  
  23.   
  24.     public T Data { getprivate set; }  
  25.   
  26.     public INode<T> Next  
  27.     {  
  28.         get;  set;  
  29.     }  
  30.   
  31.     public void Accept(IVisitor<T> visitor)  
  32.     {  
  33.         visitor.Visit(this);  
  34.     }  
  35.  
  36.  
  37.     #endregion  
  38.   
  39.     public override string ToString()  
  40.     {  
  41.         return Data.ToString();  
  42.     }  
  43.      
  44. }  
  45.   
  46.   
  47. public class LinkedList<T> : IEnumerable<INode<T>>  
  48. {  
  49.     private  INode<T> _head;  
  50.   
  51.     public INode<T> Head  
  52.     {  
  53.         get  
  54.         {  
  55.             return _head;  
  56.         }              
  57.     }  
  58.   
  59.     public void Add(T data)  
  60.     {  
  61.         if (_head == null)  
  62.         {  
  63.             _head = new Node<T>(data);  
  64.         }  
  65.         else  
  66.         {  
  67.             INode<T> current = _head;  
  68.             while (current.Next != null)  
  69.             {  
  70.                 current = current.Next;  
  71.             }  
  72.             current.Next = new Node<T>(data);  
  73.         }  
  74.     }      
  75.   
  76.     public LinkedList(params T[] elements)  
  77.     {  
  78.         foreach (var ele in elements)  
  79.         {  
  80.             Add(ele);  
  81.         }  
  82.     }  
  83.  
  84.     #region IEnumerable<INode<T>> Members  
  85.   
  86.     public IEnumerator<INode<T>> GetEnumerator()  
  87.     {  
  88.         INode<T> current = _head;  
  89.         while (current != null)  
  90.         {  
  91.             yield return current;  
  92.             current = current.Next;  
  93.         }  
  94.     }  
  95.  
  96.     #endregion  
  97.  
  98.     #region IEnumerable Members  
  99.   
  100.     System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()  
  101.     {  
  102.         return GetEnumerator();  
  103.     }  
  104.  
  105.     #endregion  
  106. }  
  107.   
  108.   
  109. public interface IVisitor<T>  
  110. {  
  111.     void Visit(INode<T> node);  
  112.     void Visit(IEnumerable<INode<T>> nodes);  
  113. }  
  114.   
  115. public class ConsoleVisitor<T> : IVisitor<T>  
  116. {  
  117.     #region IVisitor<T> Members  
  118.   
  119.     public void Visit(INode<T> node)  
  120.     {  
  121.         Console.WriteLine(node);  
  122.     }  
  123.   
  124.     public void Visit(IEnumerable<INode<T>> nodes)  
  125.     {  
  126.         foreach (var node in nodes)  
  127.         {  
  128.             node.Accept(this);  
  129.         }  
  130.     }  
  131.  
  132.     #endregion  
  133. }  
  134.   
  135. public class DebugVisitor<T> : IVisitor<T>  
  136. {  
  137.     #region IVisitor<T> Members  
  138.   
  139.     public void Visit(INode<T> node)  
  140.     {  
  141.         Debug.WriteLine(node);  
  142.     }  
  143.   
  144.     public void Visit(IEnumerable<INode<T>> nodes)  
  145.     {  
  146.         foreach (var node in nodes)  
  147.         {  
  148.             node.Accept(this);  
  149.         }  
  150.     }  
  151.  
  152.     #endregion  
  153. }  
  154.   
  155.   
  156. public class Program  
  157. {  
  158.   
  159.     static void Main(string[] args)  
  160.     {  
  161.         LinkedList<int> list = new LinkedList<int>(1, 2, 3, 4, 5 );  
  162.         ConsoleVisitor<int> consoleVisitor = new ConsoleVisitor<int>();  
  163.         DebugVisitor<int> debugVisitor = new DebugVisitor<int>();  
  164.         consoleVisitor.Visit(list);  
  165.         debugVisitor.Visit(list);              
  166.     }  
  167. }  
I see a number of drawbacks with this approach:
  • No creative use of C# 3.0 features
  • The Node<T> needs to know about the IVisitor interface(interface coupling).
  • If the LinkedList<T> was written by a 3rd party vendor, there would be no way to "pass in" a Visitor implementation
  • Double dispatch can hurt performance
The following implementation uses C# 3.0 features
 
  1. public interface INode<T>  
  2.     {  
  3.         T Data { get; }  
  4.         INode<T> Next { getset; }  
  5.     }  
  6.   
  7.     public class Node<T> : INode<T>  
  8.     {  
  9.         public Node(T t)  
  10.         {  
  11.             Data = t;  
  12.   
  13.         }  
  14.   
  15.         public Node(T t,Node<T> next)  
  16.         {  
  17.             Data = t;  
  18.             Next = next;  
  19.         }  
  20.  
  21.         #region INode<T> Members  
  22.   
  23.         public T Data { getprivate set; }  
  24.   
  25.         public INode<T> Next  
  26.         {  
  27.             get;  set;  
  28.         }  
  29.  
  30.         #endregion  
  31.   
  32.         public override string ToString()  
  33.         {  
  34.             return Data.ToString();  
  35.         }  
  36.          
  37.     }  
  38.   
  39.     public class LinkedList<T> : IEnumerable<T>  
  40.     {  
  41.         private  INode<T> _head;  
  42.   
  43.         public INode<T> Head  
  44.         {  
  45.             get  
  46.             {  
  47.                 return _head;  
  48.             }              
  49.         }  
  50.   
  51.          public void Add(T data)  
  52.         {  
  53.             if (_head == null)  
  54.             {  
  55.                 _head = new Node<T>(data);  
  56.             }  
  57.             else  
  58.             {  
  59.                 INode<T> current = _head;  
  60.                 while (current.Next != null)  
  61.                 {  
  62.                     current = current.Next;  
  63.                 }  
  64.                 current.Next = new Node<T>(data);  
  65.             }  
  66.         }  
  67.   
  68.         public LinkedList(params T[] elements)  
  69.         {  
  70.             foreach (var ele in elements)  
  71.             {  
  72.                 Add(ele);  
  73.             }  
  74.         }  
  75.  
  76.         #region IEnumerable<T> Members  
  77.   
  78.         public IEnumerator<T> GetEnumerator()  
  79.         {  
  80.             INode<T> current = _head;  
  81.             while (current != null)  
  82.             {  
  83.                 yield return current.Data;  
  84.                 current = current.Next;  
  85.             }  
  86.         }  
  87.  
  88.         #endregion  
  89.  
  90.         #region IEnumerable Members  
  91.   
  92.         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()  
  93.         {  
  94.             return GetEnumerator();  
  95.         }  
  96.  
  97.         #endregion  
  98.     }  
  99.   
  100.     public static class Extensions  
  101.     {  
  102.   
  103.         public static void ForEach<T>(this IEnumerable<T> enumerable,Action<T> action)  
  104.         {  
  105.             foreach (var item in enumerable)  
  106.             {  
  107.                 action(item);  
  108.             }  
  109.         }  
  110.     }  
  111.   
  112.     public class Program  
  113.     {  
  114.         static void Main(string[] args)  
  115.         {  
  116.             LinkedList<int> list = new LinkedList<int>(1, 2, 3, 4, 5 );  
  117.             list.ForEach( e => Console.WriteLine(e));  
  118.             list.ForEach(e => Debug.WriteLine(e));             
  119.     
  120.         }  
  121.    
  122.     }  
  • The structure being iterated over has no knowledge of a Visitor
  • The iteration logic is encapsulated away into the ForEach extension method which can be reused for iterating over any IEnumerable<T>
  • The ForEach extension method accepts an Action<T> which represents the Visitor.
  • The client is free to pass in any lambda representing the visiting logic; it could very well request an Action<T>from some factory(not shown).
  • No double dispatch
  • No proliferation of Visitor class hierarchies.Less code, more readabiliy and ease of maintenance
I prefer this mechanism much more over the interface based approach.With the functional programming features that C# provides, I need a compelling reason to use interfaces for tasks such as this.

kick it on DotNetKicks.com

Print | posted @ Wednesday, November 12, 2008 10:48 PM

Comments on this entry:

Gravatar # re: Visitor.. What's in a visit anyways...
by joe at 11/14/2008 3:51 AM

Nice post. I have a slightly-off-topic comment.

I have similar extention methods in my code: I use "ForEachElement", which pretty much matches your "ForEach" exactly, and I have a "ForEach", which is the same thing except that it returns IEnumberable<T> for "chaining" capability. My comment is that with all of the additions in .Net 3.5, why do we have to write these extensions just to perform an action on an element of an enumberable collection. I keep reading the documentation and trying to find the missing framework classes/methods/etc - because it just feels like this should be in the framework, already, and I just did not find it.

Gravatar # re: Visitor.. What's in a visit anyways...
by Abhijeet P at 11/15/2008 5:36 PM

Hi Joe,
I totally agree with your comment.My take is that since Action<T> was introduced in .NET 2.0, the framework team also introduced a static ForEach on Array
and on List<T> for performing actions using delegates at the time, since there was no notion of extension methods then.
If Extensions methods had been introduced in .NET 2.0, it would've made a lot of sense to have a ForEach on IEnumerable<T>.
Now, it would get a little ugly if the BCL team decides to include a ForEach on IEnumerable<T> going forward, we would then have an overloaded
ForEach on Array and List<T> and they would in essense be doing the same thing.
The situation get trickier particularly for List<T> since ForEach is defined as in instance method on List<T> which means that one would have to be careful and
understand the way overload resolution works for instance vs extension methods.Just my 2 cents....
Gravatar # re: Visitor.. What's in a visit anyways...
by web development company at 8/19/2009 12:05 PM

Hey, that was interesting,
I check your code carefully it works absoultely fine and I love your article writing skill

Anyway, thanks for the post
Gravatar # re: Visitor.. What's in a visit anyways...
by Abhijeet at 8/23/2009 4:07 PM

Thanks. Glad you liked it.
Post A Comment
Title:
Name:
Email:
Comment:
Verification: