The Agile Visitor

On April 24, 2010, in Uncategorized, by derekgreer

When working with object structures, you may at times encounter the need to perform some operation across all the elements within the structure. For instance, given a compound piece of machinery, you may want to perform some operation which requires examining each part to create a parts manifest, compute the total price, or determine which parts may need special storage or handling needs.

There may also be a need to easily add new cross-cutting operations across the elements which either aren’t related to the inherent responsibility of each of the elements and/or when no common base object exists allowing inheritance of the new behavior. The Visitor pattern is one approach which aids in facilitating these kinds of needs.

The Visitor Pattern

The Visitor pattern encapsulates common behavior within a single class which is applied to each of the elements of the object structure. The following diagram depicts the pattern structure:


The Visitor pattern is comprised of three main types of participants: the Visitor, the Element, and the Object Structure. The Visitor encapsulates the common behavior needed across different types of elements. Elements are the types within an object structure for which common behavior is needed. The Object Structure is the element container and may take the form of a collection or composite.

Each visitor defines methods specific to each type of element within the object structure while elements define a method capable of accepting a Visitor. When a client desires to apply the visitor behavior to each of the elements, the object structure is used to orchestrate delivery of the visitor to each element. Upon receiving the visitor, each element calls a corresponding method on the visitor, passing a reference to itself as the method parameter. Once invoked, the visitor’s methods are capable of accessing state or invoking behavior specific to each type of element.

Sidebar

When first encountering the Visitor pattern, some may wonder why each element is implemented with an Accept(Visitor) method as opposed to just having the object structure pass each of the elements directly to the visitor. At first, this may seem to unnecessarily couple the elements to the visitor.This approach stems from the fact that many programming languages don’t support dynamic binding for method overloads. That is to say, the method invoked on an object is determined at compile time based upon the reference type of the method parameters, not at run-time based upon the type of the referenced object. When implementing the Visitor pattern in such cases, if an object structure were to pass in each element referenced through a common interface then only a Visitor method defined specifically for that interface type could be invoked.

To overcome this limitation, a technique known as Double Dispatch is used to ensure that the correct Visitor method is statically dispatched.

As of C# 4.0, the dynamic keyword can be used as an alternate strategy to the traditional double dispatch pattern allowing the elements to be free of any coupling imposed by the classic Visitor pattern implementation.

The following is an example application which uses the classic Visitor pattern structure to print a parts manifest and a dangerous goods manifest for a thermostat:

class Program
    {
        static void Main(string[] args)
        {
            var thermostat = new Thermostat();
            var partsManifestVisitor = new PartsManifestVisitor();
            var dangerousGoodsManifestVisitor = new DangerousGoodsManifestVisitor();
            thermostat.Accept(partsManifestVisitor);
            thermostat.Accept(dangerousGoodsManifestVisitor);

            Console.WriteLine("Parts List");
            Console.WriteLine("----------");
            partsManifestVisitor.PrintManifest(Console.Out);

            Console.WriteLine("nDangerous Goods List");
            Console.WriteLine("----------");
            dangerousGoodsManifestVisitor.PrintManifest(Console.Out);

            Console.ReadLine();
        }
    }

    interface IComponentVisitor
    {
        void Visit(Thermostat thermostat);
        void Visit(ThermostatCover thermostatCover);
        void Visit(CircutBoard circutBoard);
        void Visit(MercurySwitch mercurySwitch);
        void Visit(BimetallicStrip bimetallicStrip);
        void Visit(HeatAnticipator heatAnticipator);
    }

    interface IComponentElement
    {
        void Accept(IComponentVisitor visitor);
    }

    class Thermostat : IComponentElement
    {
        readonly IComponentElement[] _elements;

        public Thermostat()
        {
            _elements = new IComponentElement[]
                           {
                                new ThermostatCover(),
                                new CircutBoard(),
                               new MercurySwitch(),
                               new BimetallicStrip(),
                               new HeatAnticipator()
                           };
        }

        public void Accept(IComponentVisitor visitor)
        {
            visitor.Visit(this);

            foreach (var element in _elements)
            {
                element.Accept(visitor);
            }
        }
    }

    class ThermostatCover : IComponentElement
    {
        public void Accept(IComponentVisitor visitor)
        {
            visitor.Visit(this);
        }
    }

    class CircutBoard : IComponentElement
    {
        public void Accept(IComponentVisitor visitor)
        {
            visitor.Visit(this);
        }
    }

    class MercurySwitch : IComponentElement
    {
        public void Accept(IComponentVisitor visitor)
        {
            visitor.Visit(this);
        }
    }

    class BimetallicStrip : IComponentElement
    {
        public void Accept(IComponentVisitor visitor)
        {
            visitor.Visit(this);
        }
    }

    class HeatAnticipator : IComponentElement
    {
        public void Accept(IComponentVisitor visitor)
        {
            visitor.Visit(this);
        }
    }

    class PartsManifestVisitor : IComponentVisitor
    {
        IList<string> manifest = new List<string>();

        public void PrintManifest(TextWriter textWriter)
        {
            manifest.ToList().ForEach(x => textWriter.WriteLine(x));
        }

        public void Visit(Thermostat thermostat)
        {
            manifest.Add("Thermostat");
        }

        public void Visit(ThermostatCover thermostatCover)
        {
            manifest.Add("Thermostat cover");
        }

        public void Visit(CircutBoard circutBoard)
        {
            manifest.Add("Circut board");
        }

        public void Visit(MercurySwitch mercurySwitch)
        {
            manifest.Add("Mercury switch");
        }

        public void Visit(BimetallicStrip bimetallicStrip)
        {
            manifest.Add("Bimetallic strip");
        }

        public void Visit(HeatAnticipator heatAnticipator)
        {
            manifest.Add("Heat anticipator");
        }
    }

    class DangerousGoodsManifestVisitor : IComponentVisitor
    {
        IList<string> manifest = new List<string>();

        public void PrintManifest(TextWriter textWriter)
        {
            manifest.ToList().ForEach(x => textWriter.WriteLine(x));
        }

        public void Visit(Thermostat thermostat)
        {
        }

        public void Visit(ThermostatCover thermostatCover)
        {
        }

        public void Visit(CircutBoard circutBoard)
        {
        }

        public void Visit(MercurySwitch mercurySwitch)
        {
            manifest.Add("Mercury switch");
        }

        public void Visit(BimetallicStrip bimetallicStrip)
        {
        }

        public void Visit(HeatAnticipator heatAnticipator)
        {
        }
    }

Running the application produces the following output:

Parts List
----------
Thermostat
Thermostat cover
Circut board
Mercury switch
Bimetallic strip
Heat anticipator

Dangerous Goods List
----------
Mercury switch

By using the Visitor pattern, the application was able to print a parts list and a dangerous goods list without adding any specific logic to the thermostat components. As new cross-cutting operations come up, a new visitor can be created without modification to the components.

The down side of this example is that if any new components are added, each of the visitors will need to be updated. This violates the Open/Closed principle. Additionally, depending upon the type of behavior encapsulated by the visitor, the behavior for each element type may change for different reasons. In such cases, this would violate the Single Responsibility principle. What would be nice is to achieve a visitor implementation that satisfied both of these concerns.

An Agile Visitor

What if a visitor allowed us to replace the overloaded methods with strategies? Consider the following example:

class Program
    {
        static void Main(string[] args)
        {
            // Declare visitors
            var partsManifestVisitor = new Visitor<IVisitable>();
            var dangerousGoodsManifestVisitor = new Visitor<IVisitable>();

            // Register parts manifest visitor strategies
            partsManifestVisitor.RegisterElementVisitor<Thermostat>(x => Console.WriteLine("Thermostat"));
            partsManifestVisitor.RegisterElementVisitor<ThermostatCover>(x => Console.WriteLine("Thermostat cover"));
            partsManifestVisitor.RegisterElementVisitor<CircutBoard>(x => Console.WriteLine("Circut board"));
            partsManifestVisitor.RegisterElementVisitor<MercurySwitch>(x => Console.WriteLine("Mercury switch"));
            partsManifestVisitor.RegisterElementVisitor<BimetallicStrip>(x => Console.WriteLine("Bimetallic strip"));
            partsManifestVisitor.RegisterElementVisitor<HeatAnticipator>(x => Console.WriteLine("Heat anticipator"));

            // Register dangerous goods manifest visitor strategies
            partsManifestVisitor.RegisterElementVisitor<MercurySwitch>(x => Console.WriteLine("Mercury switch"));

            var thermostat = new Thermostat();

            Console.WriteLine("Parts List");
            Console.WriteLine("----------");
            thermostat.Accept(partsManifestVisitor);

            Console.WriteLine("nDangerous Goods List");
            Console.WriteLine("----------");
            thermostat.Accept(dangerousGoodsManifestVisitor);

            Console.ReadLine();
        }
    }

In this example, the methods normally found on the classic visitor implementation have been replaced with lambda expressions registered for each type to be visited. There are several advantages to this approach:

First, the Visitor type is extensible and thus adheres to the Open/Closed principle.

Second, the Visitor type is generic, thus enabling it to be used for many (all?) types of visitor implementations.

Third, due to the fact that there are no concrete visitors coupled to a given object structure, new elements can be added to a given object structure without requiring that all visitors for that structure be modified to accommodate the new element.

Forth, the behavior associated with each type is encapsulated in a single Visitor strategy, thus adhering to the single responsibility principle.

Fifth, due to the fact that the Visitor isn’t itself coupled to any particular element type, the element types are likewise not coupled to any object structure specific visitor interface. This allows a given element to participate in unrelated object structure/visitor pattern implementations.

There are a couple of drawbacks to this approach however:

First, what happens when the behavior is more complex? For that, we could just add an overloaded RegisterElementVisitor() to accept an IVisitor:

class ThermostatVisitor : IVisitor<Thermostat>
    {
        public void Visit(Thermostat element)
        {
            Console.WriteLine("Thermostat");
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var partsManifestVisitor = new Visitor<IVisitable>();

            partsManifestVisitor.RegisterElementVisitor<Thermostat>(new ThermostatVisitor());

            // snip
        }
    }

That addresses the issue of how we might better encapsulate the more complex behaviors, but a second shortcoming is the loss of encapsulated state. One of the good things the classic Visitor pattern gives us is shared state for accumulating the results of our visitations. There are a few ways we could address this however. The first approach would be to just use closures:

            // snip

            // Register parts manifest visitor strategies
            var partsManifest = new List<string>();

            partsManifestVisitor.RegisterElementVisitor<Thermostat>(x => partsManifest.Add("Thermostat"));
            partsManifestVisitor.RegisterElementVisitor<ThermostatCover>(x => partsManifest.Add("Thermostat cover"));
            partsManifestVisitor.RegisterElementVisitor<CircutBoard>(x => partsManifest.Add("Circut board"));
            partsManifestVisitor.RegisterElementVisitor<MercurySwitch>(x => partsManifest.Add("Mercury switch"));
            partsManifestVisitor.RegisterElementVisitor<BimetallicStrip>(x => partsManifest.Add("Bimetallic strip"));
            partsManifestVisitor.RegisterElementVisitor<HeatAnticipator>(x => partsManifest.Add("Heat anticipator"));

            var thermostat = new Thermostat();
            thermostat.Accept(partsManifestVisitor);

            Console.WriteLine("Parts List");
            Console.WriteLine("----------");
            partsManifest.ToList().ForEach(x => Console.WriteLine(x));

            // snip

A second approach would be to inject a state service when registering IVisitor strategies:

    class Manifest
    {
        public IList<string> Parts { get; private set; }

        public Manifest()
        {
            Parts = new List<string>();
        }

        public void RecordPart(string partName)
        {
            Parts.Add(partName);
        }
    }

    class ThermostatVisitor : IVisitor<Thermostat>
    {
        Manifest _manifest;

        public ThermostatVisitor(Manifest manifest)
        {
            _manifest = manifest;
        }

        public void Visit(Thermostat element)
        {
            _manifest.RecordPart("Thermostat");
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            // Declare visitors
            var partsManifestVisitor = new Visitor<IVisitable>();

            // Register parts manifest visitor strategies
            var manifest = new Manifest();
            partsManifestVisitor.RegisterElementVisitor<Thermostat>(new ThermostatVisitor(manifest));

            // other strategies

            var thermostat = new Thermostat();
            thermostat.Accept(partsManifestVisitor);

            Console.WriteLine("Parts List");
            Console.WriteLine("----------");
            manifest.Parts.ToList().ForEach(x => Console.WriteLine(x));
        }
    }

Things are starting to get strewn about though. Let’s bundle all of this up into a facade:

    class PartsManifestVisitorFacade : IVisitor<IVisitable>
    {
        Manifest _manifest = new Manifest();
        Visitor<IVisitable> partsManifestVisitor = new Visitor<IVisitable>();

        public PartsManifestVisitorFacade()
        {
            partsManifestVisitor.RegisterElementVisitor<Thermostat>(new ThermostatVisitor(_manifest));

            // Register other strategies  ...
        }

        public IList<string> Manifest
        {
            get
            {
                return _manifest.Parts;
            }
        }

        public void Visit(IVisitable element)
        {
            partsManifestVisitor.Visit(element);
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var partsManifestVisitor = new PartsManifestVisitorFacade();
            var thermostat = new Thermostat();
            thermostat.Accept(partsManifestVisitor);

            Console.WriteLine("Parts List");
            Console.WriteLine("----------");
            partsManifestVisitor.Manifest.ToList().ForEach(x => Console.WriteLine(x));

            Console.ReadLine();
        }
    }

Alternately, we could use some DI registration magic to have an open generic visitor get closed-over, configured, and injected into wherever we are going to use it. Such an example is a tad bit beyond the intended scope of this article, however, so I’ll leave that as an exercise for the reader to explore.

By this point, you may be wondering: “So where’s the actual Visitor code”? While I’m sure a better implementation is possible, here’s my working prototype:

    /// <summary>
    /// Defines a visitor.
    /// </summary>
    /// <typeparam name="TElement">the type of element to be visited</typeparam>
    interface IVisitor<TElement>
    {
        void Visit(TElement element);
    }

    /// <summary>
    /// Defines a visitable element.
    /// </summary>
    interface IVisitable
    {
        void Accept(IVisitor<IVisitable> visitor);
    }

    /// <summary>
    /// Represents an open/closed visitor.
    /// </summary>
    /// <typeparam name="T">the type of element to visit</typeparam>
    class Visitor<T> : IVisitor<T>
    {
        readonly IDictionary<Type, IVisitorInfo> _visitorInfoDictionary = new Dictionary<Type, IVisitorInfo>();

        /// <summary>
        /// Visits the specified element.
        /// </summary>
        /// <param name="element">element to visit</param>
        public void Visit(T element)
        {
            if (_visitorInfoDictionary.ContainsKey(element.GetType()))
            {
                IVisitorInfo visitorInfo = _visitorInfoDictionary[element.GetType()];
                object visitor = visitorInfo.Visitor;
                IVisitorInvoker invoker = visitorInfo.Invoker;
                invoker.Invoke(visitor, element);
            }
        }

        /// <summary>
        /// Registers an visitor action delegate for a specific type.
        /// </summary>
        /// <typeparam name="TElement">type of element</typeparam>
        /// <param name="action">the visitor action</param>
        public void RegisterElementVisitor<TElement>(Action<TElement> action)
        {
            RegisterElementVisitor(new VisitorAction<TElement>(action));
        }

        /// <summary>
        /// Registers a <see cref="IVisitor{TElement}"/> strategy for a specific type.
        /// </summary>
        /// <typeparam name="TElement">type of element</typeparam>
        /// <param name="visitor">a visitor</param>
        public void RegisterElementVisitor<TElement>(IVisitor<TElement> visitor)
        {
            var visitorInfo = new VisitorInfo<TElement>(
                visitor, new DelegateVisitorInvoker<IVisitor<TElement>, TElement>((x, y) => x.Visit(y)));

            _visitorInfoDictionary.Add(typeof(TElement), visitorInfo);
        }

        /// <summary>
        /// Nested class used to encapsulate a visitor action.
        /// </summary>
        /// <typeparam name="TVisitor">the type of visitor action</typeparam>
        /// <typeparam name="TElement">the type of element</typeparam>
        class DelegateVisitorInvoker<TVisitor, TElement> : IVisitorInvoker
        {
            readonly Action<TVisitor, TElement> _action;

            public DelegateVisitorInvoker(Action<TVisitor, TElement> action)
            {
                _action = action;
            }

            public void Invoke(object action, object instance)
            {
                _action.Invoke((TVisitor)action, (TElement)instance);
            }
        }

        /// <summary>
        /// Nested interface used as the key to the internal dictionary for associating
        /// visitors with their invokers.
        /// </summary>
        interface IVisitorInfo
        {
            IVisitorInvoker Invoker { get; }
            object Visitor { get; }
        }

        /// <summary>
        /// Nested interface used to encapsulate a visit action invocation.
        /// </summary>
        interface IVisitorInvoker
        {
            void Invoke(object action, object instance);
        }

        /// <summary>
        /// Nested class used to encapsulate visitor actions.
        /// </summary>
        /// <typeparam name="TElement">the type of element to visit</typeparam>
        class VisitorAction<TElement> : IVisitor<TElement>
        {
            readonly Action<TElement> _action;

            public VisitorAction(Action<TElement> action)
            {
                _action = action;
            }

            public void Visit(TElement element)
            {
                _action.Invoke(element);
            }
        }

        /// <summary>
        /// Nested class used as the key to the internal dictionary for associating
        /// visitors with their invokers.
        /// </summary>
        /// <typeparam name="TElement">the type of element to be visited</typeparam>
        ///
        /// <remarks>
        /// This type is used as the internal dictionary key to associate visitors with
        /// a corresponding invoker and enables the specific type information to be
        /// maintained for each visitor/element pair.
        /// </remarks>
        class VisitorInfo<TElement> : IVisitorInfo
        {
            public VisitorInfo(IVisitor<TElement> visitor, IVisitorInvoker invoker)
            {
                Visitor = visitor;
                Invoker = invoker;
            }

            public IVisitorInvoker Invoker { get; private set; }
            public object Visitor { get; private set; }
        }
    }

Conclusion

The structure of the classic Visitor pattern seem to reflect the design sensibilities and capabilities of the mainstream programming languages of its day. While the problem it seeks to address remains relevant, it seems prudent to reconsider such patterns from time to time in light of both the ever-evolving capabilities of mainstream development platforms and design principles of today.

So, is this a better approach? Let me know what you think.

Tagged with:  

Double Dispatch is a Code Smell

On April 19, 2010, in Uncategorized, by derekgreer

If you’re using Double Dispatch in your code, this may be a symptom of an underlying design issue which may impact the maintainability of your application. Due to the fact that Double Dispatch is at times confused with a form of the Strategy Pattern, an overview may be in order to elaborate on this assertion further.

What is Double Dispatch?

Technically, Double Dispatch refers to a technique used in the context of a polymorphic method call for mitigating the lack of multimethod support in programming languages. More simply, Double Dispatch is used to invoke an overloaded method where the parameters vary among an inheritance hierarchy. To explain fully, let’s start with a review of polymorphism.

Polymorphism

In the following example, a hierarchy of shapes are defined with each of the derived types overloading a base virtual Draw() method. Next, a console application is used to define a list of each of the shapes and iterate over each shape in the collection calling the Draw() method of each item in the list:

    class Shape
    {
        public virtual void Draw()
        {
            Console.WriteLine("A shape is drawn.");
        }
    }

    class Polygon : Shape
    {
        public override void Draw()
        {
            Console.WriteLine("A polygon is drawn.");
        }
    }

    class Quadrilateral : Polygon
    {
        public override void Draw()
        {
            Console.WriteLine("A quadrilateral is drawn.");
        }
    }

    class Parallelogram : Quadrilateral
    {
        public override void Draw()
        {
            Console.WriteLine("A parallelogram is drawn.");
        }
    }

    class Rectangle : Parallelogram
    {
        public override void Draw()
        {
            Console.WriteLine("A rectangle is drawn.");
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var shapes = new List<Shape>
                             {
                                 new Shape(),
                                 new Polygon(),
                                 new Quadrilateral(),
                                 new Parallelogram(),
                                 new Rectangle()
                             };

            foreach (Shape shape in shapes)
            {
                shape.Draw();
            }

            Console.ReadLine();
        }
    }

The following lines are printed to the console upon running the application:

A shape is drawn.
A polygon is drawn.
A quadrilateral is drawn.
A parallelogram is drawn.
A rectangle is drawn.

Note that the proper Draw() method is called for each item in the collection. In most object-oriented languages, this polymorphic behavior is achieved through the use of a virtual table consulted at run-time to derive the proper offset address for an object’s method. This behavior is referred to as “Dynamic Dispatch” or “Single Dispatch”. So, how does this relate to Double Dispatch? To answer this question, let’s next review method overloading.

Method Overloading

In the following example, our Shape class is redefined to have two overloaded Draw methods: one with a parameter of type Surface and one with a parameter of type EtchASketch:

    class Surface
    {
    }

    class EtchASketch : Surface
    {
    }

    class Shape
    {
        public void Draw(Surface surface)
        {
            Console.WriteLine("A shape is drawn on the surface with ink.");
        }

        public void Draw(EtchASketch etchASketch)
        {
            Console.WriteLine("The knobs are moved in attempt to draw the shape.");
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var shape = new Shape();
            shape.Draw(new Surface());
            shape.Draw(new EtchASketch());

            Console.ReadLine();
        }
    }

When executed, the following lines are printed to the console:

A shape is drawn on the surface with ink.
The knobs are moved in attempt to draw the shape.

Note that the parameter type determines which Draw() method is invoked.

But what happens if we change the Main() method to the following?

    class Program
    {
        static void Main(string[] args)
        {
            var shape = new Shape();
            Surface surface = new Surface();
            Surface etchASketch = new EtchASketch();

            shape.Draw(surface);
            shape.Draw(etchASketch);

            Console.ReadLine();
        }
    }

Executing this produces the following:

A shape is drawn on the surface with ink.
A shape is drawn on the surface with ink.

What happened? The issue here is that the method to call was determined statically at compile time based upon the reference type, not at run-time based upon the object type. To resolve this issue, another technique is needed … Polymorphic Static Binding.

Polymorphic Static Binding

Polymorphic static binding is a technique where static method invocations are determined at run-time through the use of polymorphism. This can be demonstrated in our example by adding a new Draw(Shape shape) method to the Surface and EtchASketch types which call shape.Draw() with a reference to the current object:

    class Surface
    {
        public virtual void Draw(Shape shape)
        {
            shape.Draw(this);
        }
    }

    class EtchASketch : Surface
    {
        public override void Draw(Shape shape)
        {
            shape.Draw(this);
        }
    }

To invoke the correct Shape.Draw() method, our console application needs to be modified to call the the method indirectly through a Surface reference:

    class Program
    {
        static void Main(string[] args)
        {
            var shape = new Shape();
            Surface surface = new Surface();
            Surface etchASketch = new EtchASketch();

            surface.Draw(shape);
            etchASketch.Draw(shape);

            Console.ReadLine();
        }
    }

Upon executing the application again, the following lines are now printed:

A shape is drawn on the surface with ink.
The knobs are moved in attempt to draw the shape.

This example achieves the desired result by effectively wrapping the static-dispatched method invocation (i.e. Shape.Draw()) within a virtual-dispatch method invocation (i.e. Surface.Draw() and EtchASketch.Draw()). This causes the static Shape.Draw() method invocation to be determined by which virtual Surface.Draw() method invocation is executed.

Although the above example now contains a method invocation using a reference to the current object as the method parameter (often seen with Double Dispatch), it should be noted that Double Dispatch has yet to be demonstrated. Thus far, only one level of virtual dispatching has been used. To demonstrate Double Dispatch, the techniques from both the polymorphism example and the polymorphic static binding example need to be combined as seen in the next section.

Double Dispatch

The following example contains a hierarchy of Surface types and a hierarchy of Shape types. Each Shape type contains an overloaded virtual Draw() method which contains the logic for how the shape is to be drawn on a particular surface. The example console application uses the polymorphic static binding technique to ensure the proper overload is called for each surface type:

    class Surface
    {
        public virtual void Draw(Shape shape)
        {
            shape.Draw(this);
        }
    }

    class EtchASketch : Surface
    {
        public override void Draw(Shape shape)
        {
            shape.Draw(this);
        }
    }

    class Shape
    {
        public virtual void Draw(Surface surface)
        {
            Console.WriteLine("A shape is drawn on the surface with ink.");
        }

        public virtual void Draw(EtchASketch etchASketch)
        {
            Console.WriteLine("The knobs are moved in attempt to draw the shape.");
        }
    }

    class Polygon : Shape
    {
        public override void Draw(Surface surface)
        {
            Console.WriteLine("A polygon is drawn on the surface with ink.");
        }

        public override void Draw(EtchASketch etchASketch)
        {
            Console.WriteLine("The knobs are moved in attempt to draw the polygon.");
        }
    }

    class Quadrilateral : Polygon
    {
        public override void Draw(Surface surface)
        {
            Console.WriteLine("A quadrilateral is drawn on the surface with ink.");
        }

        public override void Draw(EtchASketch etchASketch)
        {
            Console.WriteLine("The knobs are moved in attempt to draw the quadrilateral.");
        }
    }

    class Parallelogram : Quadrilateral
    {
        public override void Draw(Surface surface)
        {
            Console.WriteLine("A parallelogram is drawn on the surface with ink.");
        }

        public override void Draw(EtchASketch etchASketch)
        {
            Console.WriteLine("The knobs are moved in attempt to draw the parallelogram.");
        }
    }

     class Rectangle : Parallelogram
    {
        public override void Draw(Surface surface)
        {
            Console.WriteLine("A rectangle is drawn on the surface with ink.");
        }

        public override void Draw(EtchASketch etchASketch)
        {
            Console.WriteLine("The knobs are moved in attempt to draw the rectangle.");
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Surface surface = new Surface();
            Surface etchASketch = new EtchASketch();

            var shapes = new List<Shape>
                             {
                                 new Shape(),
                                 new Polygon(),
                                 new Quadrilateral(),
                                 new Parallelogram(),
                                 new Rectangle()
                             };

            foreach (Shape shape in shapes)
            {
                surface.Draw(shape);
                etchASketch.Draw(shape);
            }

            Console.ReadLine();
        }
    }

Executing this example produces the following:

A shape is drawn on the surface with ink.
The knobs are moved in attempt to draw the shape.
A polygon is drawn on the surface with ink.
The knobs are moved in attempt to draw the polygon.
A quadrilateral is drawn on the surface with ink.
The knobs are moved in attempt to draw the quadrilateral.
A parallelogram is drawn on the surface with ink.
The knobs are moved in attempt to draw the parallelogram.
A rectangle is drawn on the surface with ink.
The knobs are moved in attempt to draw the rectangle.

In the above example, virtual dispatch occurs twice for each call to one of the Surface references: Once when the Surface.Draw() virtual method is called and again when either calls the Shape.Draw() overloaded virtual method. Note again that while the second virtual dispatch is based on the type of Shape instance, the overloaded method called is still determined statically based upon the reference type.

Consequences

So, what’s wrong with Double Dispatch? The problem isn’t so much in the technique, but what design choices might be leading to reliance upon the technique. Consider for instance the hierarchy of shape types in our Double Dispatch example. What happens if we want to add a new surface? In this case, each of the shape types will need to be modified to add knowledge of the new Surface type. This violates the Open/Closed Principle, and in this case in a particularly egregious way (i.e. Its violation is multiplied by the number of shape types we have). Additionally, it violates the Single Responsibility Principle. Changes to how shapes are drawn on a particular surface are likely to differ from surface to surface, thereby leading our shape objects to change for different reasons.

The presence of Double Dispatch generally means that each type in a hierarchy has special handling code within another hierarchy of types. This approach to representing variant behavior leads to code that is less resilient to future changes as well as being more difficult to extend.

The Matrix: Reloaded

Let’s take another stab at modeling our shape/surface intersection matrix. In the following example, several new concepts have been introduced to facilitate decoupling: line segments, points, and brushes:

    interface ISurface
    {
        void Add(LineSegment segment);
    }

    class Paper : ISurface
    {
        readonly IList<LineSegment> _segments = new List<LineSegment>();

        public void Add(LineSegment segment)
        {
            _segments.Add(segment);
        }
    }

    class EtchASketch : ISurface
    {
        readonly IList<LineSegment> _segments = new List<LineSegment>();

        public void Add(LineSegment segment)
        {
            _segments.Add(segment);
        }
    }

    class Point
    {
        public Point(int x, int y)
        {
            X = x;
            Y = y;
        }

        public int X { get; set; }
        public int Y { get; set; }
    }

    class LineSegment
    {
        public LineSegment(Point point1, Point point2)
        {
            Point1 = point1;
            Point2 = point2;
        }

        public Point Point1 { get; set; }
        public Point Point2 { get; set; }
    }

    interface IShape
    {
        IList<LineSegment> GetLineSegments();
    }

    class Polygon : IShape
    {
        public IList<LineSegment> GetLineSegments()
        {
            var segments = new List<LineSegment>();
            segments.Add(new LineSegment(new Point(0, 0), new Point(0, 9)));
            segments.Add(new LineSegment(new Point(0, 9), new Point(3, 6)));
            segments.Add(new LineSegment(new Point(3, 6), new Point(6, 9)));
            segments.Add(new LineSegment(new Point(6, 0), new Point(6, 9)));
            segments.Add(new LineSegment(new Point(6, 0), new Point(3, 3)));
            segments.Add(new LineSegment(new Point(3, 3), new Point(0, 0)));

            return segments;
        }
    }

    class Quadrilateral : IShape
    {
        public IList<LineSegment> GetLineSegments()
        {
            var segments = new List<LineSegment>();
            segments.Add(new LineSegment(new Point(0, 0), new Point(0, 9)));
            segments.Add(new LineSegment(new Point(0, 9), new Point(4, 5)));
            segments.Add(new LineSegment(new Point(4, 0), new Point(0, 4)));
            segments.Add(new LineSegment(new Point(4, 0), new Point(0, 0)));

            return segments;
        }
    }

    class Parallelogram : IShape
    {
        public IList<LineSegment> GetLineSegments()
        {
            var segments = new List<LineSegment>();
            segments.Add(new LineSegment(new Point(0, 4), new Point(0, 9)));
            segments.Add(new LineSegment(new Point(0, 9), new Point(4, 5)));
            segments.Add(new LineSegment(new Point(4, 0), new Point(4, 5)));
            segments.Add(new LineSegment(new Point(4, 0), new Point(0, 4)));

            return segments;
        }
    }

    class Rectangle : IShape
    {
        public IList<LineSegment> GetLineSegments()
        {
            var segments = new List<LineSegment>();
            segments.Add(new LineSegment(new Point(0, 0), new Point(0, 9)));
            segments.Add(new LineSegment(new Point(0, 9), new Point(9, 4)));
            segments.Add(new LineSegment(new Point(4, 0), new Point(9, 4)));
            segments.Add(new LineSegment(new Point(4, 0), new Point(0, 0)));

            return segments;
        }
    }

    class Program
    {
        static readonly IDictionary<Type, IBrush> brushDictionary = new Dictionary<Type, IBrush>();

        static Program()
        {
            brushDictionary.Add(typeof (Paper), new Pencil());
            brushDictionary.Add(typeof (EtchASketch), new EtchASketchKnobs());
        }

        static void Main(string[] args)
        {
            var surfaces = new List<ISurface>
                               {
                                   new Paper(),
                                   new EtchASketch()
                               };

            var shapes = new List<IShape>
                             {
                                 new Polygon(),
                                 new Quadrilateral(),
                                 new Parallelogram(),
                                 new Rectangle()
                             };

            foreach (ISurface surface in surfaces)
                foreach (IShape shape in shapes)
                {
                    Console.WriteLine(string.Format("Drawing a {0} on the {1} ...", shape.GetType().Name,
                                                    surface.GetType().Name));
                    brushDictionary[surface.GetType()].Draw(surface, shape.GetLineSegments());
                    Console.WriteLine(Environment.NewLine);
                }

            Console.ReadLine();
        }
    }

    interface IBrush
    {
        void Draw(ISurface surface, IList<LineSegment> segments);
    }

    class Pencil : IBrush
    {
        public void Draw(ISurface surface, IList<LineSegment> segments)
        {
            foreach (LineSegment segment in segments)
            {
                Console.WriteLine(string.Format("Pencil used to sketch line segment {0},{1} to {2},{3}.",
                                                segment.Point1.X, segment.Point1.Y,
                                                segment.Point2.X, segment.Point2.Y));
            }
        }
    }

    class EtchASketchKnobs : IBrush
    {
        public void Draw(ISurface surface, IList<LineSegment> segments)
        {
            foreach (LineSegment segment in segments)
            {
                Console.WriteLine(string.Format("Knobs used to produce line segment {0},{1} to {2},{3}.",
                                                segment.Point1.X, segment.Point1.Y,
                                                segment.Point2.X, segment.Point2.Y));
            }
        }
    }

Executing this example produces the following:

Drawing a Polygon on the Paper ...
Pencil used to sketch line segment 0,0 to 0,9.
Pencil used to sketch line segment 0,9 to 3,6.
Pencil used to sketch line segment 3,6 to 6,9.
Pencil used to sketch line segment 6,0 to 6,9.
Pencil used to sketch line segment 6,0 to 3,3.
Pencil used to sketch line segment 3,3 to 0,0.

Drawing a Quadrilateral on the Paper ...
Pencil used to sketch line segment 0,0 to 0,9.
Pencil used to sketch line segment 0,9 to 4,5.
Pencil used to sketch line segment 4,0 to 0,4.
Pencil used to sketch line segment 4,0 to 0,0.

Drawing a Parallelogram on the Paper ...
Pencil used to sketch line segment 0,4 to 0,9.
Pencil used to sketch line segment 0,9 to 4,5.
Pencil used to sketch line segment 4,0 to 4,5.
Pencil used to sketch line segment 4,0 to 0,4.

Drawing a Rectangle on the Paper ...
Pencil used to sketch line segment 0,0 to 0,9.
Pencil used to sketch line segment 0,9 to 9,4.
Pencil used to sketch line segment 4,0 to 9,4.
Pencil used to sketch line segment 4,0 to 0,0.

Drawing a Polygon on the EtchASketch ...
Knobs used to produce line segment 0,0 to 0,9.
Knobs used to produce line segment 0,9 to 3,6.
Knobs used to produce line segment 3,6 to 6,9.
Knobs used to produce line segment 6,0 to 6,9.
Knobs used to produce line segment 6,0 to 3,3.
Knobs used to produce line segment 3,3 to 0,0.

Drawing a Quadrilateral on the EtchASketch ...
Knobs used to produce line segment 0,0 to 0,9.
Knobs used to produce line segment 0,9 to 4,5.
Knobs used to produce line segment 4,0 to 0,4.
Knobs used to produce line segment 4,0 to 0,0.

Drawing a Parallelogram on the EtchASketch ...
Knobs used to produce line segment 0,4 to 0,9.
Knobs used to produce line segment 0,9 to 4,5.
Knobs used to produce line segment 4,0 to 4,5.
Knobs used to produce line segment 4,0 to 0,4.

Drawing a Rectangle on the EtchASketch ...
Knobs used to produce line segment 0,0 to 0,9.
Knobs used to produce line segment 0,9 to 9,4.
Knobs used to produce line segment 4,0 to 9,4.
Knobs used to produce line segment 4,0 to 0,0.

By changing the Shape objects to be defined in terms of line segments, knowledge is removed from the shape concerning how to draw itself on any particular surface. Additionally, the Surface type now encapsulates a collection of line segments to simulate the lines being drawn onto the surface. To handle drawing the line segments onto the surfaces, we’ve introduced a Brush type which “draws” the line segments onto a surface in its own peculiar way. To configure which brushes are to be used with which surface, the console application defines a dictionary matching surfaces to brushes.

In contrast to the Double Dispatch example, none of the existing types need to be modified to add new surfaces, shapes, or brushes.

Conclusion

Since Double Dispatch is a technique for calling virtual overloaded methods based upon parameter types which exist within an inheritance hierarchy, its use may be a symptom that the Open/Closed and/or Single responsibility principles are being violated, or that responsibilities may otherwise be misaligned. This is not to say that every case of Double Dispatch means something is amiss, but only that its use should be a flag to reconsider your design in light of future maintenance needs.

Tagged with:  

Getting Started With Cygwin

On April 8, 2010, in Uncategorized, by derekgreer

With the increasing popularity of the Git version control system, many .Net developers are being introduced for the first time to Unix-like tools for Windows by way of two popular Git client platforms: msysgit and Cygwin. The more substantial of the two, Cygwin is a Linux-like environment for Windows and provides a wide range of useful utilities. The following is a guide for helping newcomers quickly get up and going with the Cygwin environment.

Installation

The first step is to obtain the installer from the Cygwin home page. Upon running the installer, you’ll be presented with a wizard which guides you through the installation process:

 

Upon arriving at the “Select Packages” dialog, you’ll be presented with all the packages available from the selected mirror site(s):

 

The installer allows you to install selected packages, or install by category:

 

At the package level, the rotating arrow icon allows you to cycle through the choices of installing one of the package versions available, skipping the package, or in the event the package is already installed, keeping, reinstalling, uninstalling, or obtaining the source code for the package. At the category level, the rotating arrow icon allows you to cycle through the choices of Default, Install, Reinstall, or Uninstall.

It’s best to only select the packages you really think you’ll want to use or immediately explore. There’s quite a bit of applications available and choosing everything would result in quite a large installation time. The installer can always be run at a later time to pickup up additional packages you want to explore.

By default, Cygwin selects the Base category packages as well as a few other odds & ends. Among the packages skipped by default, you may consider also installing the following:

Category Package Description
Admin cygrunsrv Utility for easily working with Windows services (adding/removing/starting/stopping).  This is beneficial if you’d like to run git daemon or sshd as a windows service for anonymous or authenticated access.
Archive zip, unzip PKZip compatible zip capabilities.
Editors vim An enhanced VI editor.
Net openssh Secure shell client and server programs.
Utils ncurses Terminal utilities (has a clear command for clearing the screen).
Web curl Multi-protocol file transfer tool.  This tool is useful for scripting HTTP interaction.

 

In addition, I personally always install the X11 category packages. While this adds a bit to the download size, it gives you the ability to run your preferred shell (e.g. bash) in an xterm as opposed to the standard terminal window. I’ll cover a bit of X11 installation and customization later in this guide.

When you’re done selecting your packages, click “Next” and the install will begin:

 

 

Once complete, click the Finish button and you’re done with the install.

Bash Shell Customization

If you selected the “Add icon to Start Menu” option during the install then you should have a new shortcut entitled “Cygwin Bash Shell” which will start the bash shell as an interactive login shell (i.e. bash –login -i). If not, you can browse to cygwin.bat file located within the chosen installation folder.

When bash runs for the first time, it checks to see if the home directory (denoted in the /etc/passwd file) exists for your account. If not, it creates the directory and copies over some default config files for your shell:

 

The .bash_profile is used for login shells while the .bashrc file is used for interactive, non-login shells. The default .bash_profile configuration sources the .bashrc file if it exists, so both are sourced for interactive login shells. This effectively allows the .bashrc to serve as the core configuration for both login and non-login shells. The .inputrc file is used to set custom key mappings. Of the three, the .bashrc file will generally be the one you’ll deal with most often.

Go ahead and open up the .bashrc file. (Note: Microsoft Notepad does not display Unix-style line endings correctly. If using a Windows editor, use Wordpad.) After opening the file, you’ll notice that most of the configuration is commented out. The only active configuration are commands to unset the Windows TMP and TEMP variables. You can keep this if you like, but I prefer to keep things a bit more tidy and only have the configuration I actually use. If you want to view the default contents of this file, it can always be viewed from its original source in /etc/skel. The following is a more minimal configuration you might wish to start with:

unset TMP
unset TEMP

PATH=.:~/bin:${PATH}
PATH=${PATH}:c:/Windows/Microsoft.Net/Framework/v3.5/
PATH=${PATH}:c:/Program  Files/Reflector/
PATH=${PATH}:c:/Program Files/Microsoft  SDKs/Windows/v6.1/Bin/

. ~/.alias
. ~/.functions

In this configuration, several folders have been added to the PATH environment variable. The first places a ~/bin folder before the PATH. This ensures any custom scripts found in the users bin folder occur first in the path allowing commands to be overridden. The remaining three lines are example folders you might want to set if you are doing .Net development related tasks at the bash command line.

The remaining two lines assume the existence of two new files, .alias and .functions. I find storing aliases and functions separately to be a bit more tidy, as well as making it easier to share with others.

Now, let’s take a look at the .bash_profile configuration. By default, the only configuration that exists is the sourcing of the .bashrc file. Again, normally the .bashrc file is only sourced for non-login shells, so this ensures the .bashrc settings are picked up for login shells as well.

In this file, let’s replace the contents with the following:

#  source the system wide bashrc if it exists
if [ -e /etc/bash.bashrc ]  ; then
source /etc/bash.bashrc
fi

# source the users  bashrc if it exists
if [ -e "${HOME}/.bashrc" ] ; then
source  "${HOME}/.bashrc"
fi

PS1='[h]: ${PWD##*/} > '
set -o vi
export  DISPLAY=127.0.0.1:0.0

In addition to the existing configuration, we’ve added three additional settings. The first customizes how the prompt appears at the command line by setting the PS1 variable. This prompt is a bit plain, but you can spruce it up with a bit of color by replacing it with the following:

PS1=’\[\033]0;\w\007\033[32m\][\h]: \[\033[33m ${PWD##*/}\033[0m\] > ‘

Next, I’ve issued: “set -o vi”. This tells bash to use a vi-style command line editing interface which let’s you more efficiently issue and edit commands at the command line. You can delete this if you don’t ever plan on learning vi.

Next, I’ve set an X environment variable named “DISPLAY” to my localhost. This tells the xterm and other X applications where to attempt to display. You can delete this if you don’t plan on running an xterm, but leaving it certainly won’t hurt.

This should get you started. Your config files will likely evolve from here if you find yourself working at the command line often.

Aliases

The next step you may want to take is to define some command aliases. The bash alias command allows you to set up aliases for verbose or otherwise undesirable commands. As indicated, I store all of my aliases in a .alias file in my home directory to segregate them away from the rest of my .bashrc configuration. Here is a subset of my current list of aliases you might find useful:

alias programfiles="cd  /cygdrive/c/Program Files"
alias projects="cd /cygdrive/c/projects"
alias  spikes="cd /cygdrive/c/projects/spikes"
alias vs='cmd /c *.sln'
alias  vs9='/cygdrive/c/Program Files/Microsoft Visual Studio  9.0/Common7/IDE/devenv.exe *.sln&amp;'
alias  wordpad='/cygdrive/c//Program Files/Windows  NT/Accessories/wordpad.exe'
alias config='cd  /cygdrive/c/Windows/Microsoft.NET/Framework/v2.0.50727/CONFIG'
alias  mydocs='cd /cygdrive/c/Users/${USER}/Documents'
alias myhome='cd  /cygdrive/c/Documents and Settings/${USER}/'
alias  fusion='fuslogvw.exe'

You’ll be surprised at how fast you’ll start zipping around the system once you’ve got some good navigation aliases in place.

Functions

I don’t tend to write a lot of bash functions, but I’m including this section here for completeness. Like the aliases, I like to segregate any functions I do write away from my main config file to make things a bit cleaner. As an example of what you can do, here is the contents of an example .functions file which allows you to tweet from the command line:

tweet()
{
read -s -p "Password:" password
curl -u  derekgreer:$password -d status="$1"  http://twitter.com/statuses/update.xml
}
Note: If you want to actually use this function then you’ll need to have downloaded the curl package and will need to modify the Twitter id.

Basic Commands

If you’re completely new to the Unix shells, the following are some common commands to get you started with navigating around, creating folders, deleting files, etc.:

Command Description
cd Change to home directory
cd [directory name] Change to a specified directory
cd – Change to the last directory
ls List the contents of the current folder (like dir)
ls -la List the contents of the current folder in long format including all hidden files
cat [filename] Print the context of a file (like DOS type)
![command prefix] Run the last command starting with the specified prefix.
mkdir [directory name] Make a new directory
mkdir -p [directory hierarchy] Make a all directories listed (e.g. mkdir -p a/b/c/d)
rm [filename] Remove a file
rm -rf [filename] Remove recursively with force
find [start folder] -name [regex] -print Starting at the start folder, find a file matching the given regular expression.
grep [regex] [filename] Display all lines matching the regular expression from the given file.

Scripts

Once you start getting comfortable with the available commands, you may wish to start writing your own scripts to help with various everyday tasks. While covering the basics of bash shell scripting is beyond the intended scope of this article, you can obtain an archive of some scripts I’ve written for my own purposes from here. Here’s a list of the contained scripts along with a brief description:

Script Description
clean Cleans up common temp/generated Visual Studio files.
detachfromcvs Removes CVS folders.
detachfromtfs Removes TFS bindings from source files.
diff Overrides the diff command to call WinMerge
git-diff-wrapper.sh Diff wrapper for use with Git.
replaceinfile Replaces string patterns in a file.
replaceinfiles Wrapper for calling replaceinfile for files matching a given pattern.
rgrep Recursive grep (Also greps from .Net assemblies)
unix2dosall Recursive unix2dos

X11 – Using an XTerm

The final portion of this guide is intended for those who would like to explore the X Windows system provided by Cygwin. One of the benefits of running an XServer on Windows is the ability to use an XTerm over the standard terminal provided by DOS. XTerm provides more flexibility over the fonts, colors used, and buffers used, provides dynamic resizing, and provides much more intuitive cut-n-paste capabilities (highlight = cut, middle mouse button = paste). It also displays buffered text which comes in handy when you want to use the tail -f command to follow a log file and queue up a bunch of spaces to visually separate new entries.

Assuming you’ve already installed the X11 packages, locate the Cygwin-X folder in your start menu and execute the “XWin Server” shortcut. By default, the XServer starts a plain white terminal:

 

Since this isn’t likely the style of terminal you’ll want to work with, you can prevent XServer from starting this default xterm by creating an empty .startxwinrc file in your home directory. You can do this by using the touch command:

touch ~/.startxwinrc

Next, you can modify the XTerm shortcut that was created in your start menu’s Cygwin-X folder to start a new xterm with no menu, a custom font, colors, a scrollbar, etc. using the following Target value:

C:Cygwinbinrun.exe -p /usr/X11R6/bin xterm -display 127.0.0.1:0.0 -ls -vb -fn 10×20 +tb -bg gray14 -fg ivory -sb -rightbar -sl 400

This command will launch an xterm similar to the following:

 

From here, you may consider adding the XWin Server shortcut to your startup.

That concludes my guide. Enjoy!

Tagged with: