Double-dispatch and alternatives

Question

I am trying to find a better way to handle some growing if constructs to handle classes of different types. These classes are, ultimately, wrappers around disparate value types (int, DateTime, etc) with some additional state information. So the primary difference between these classes is the type of data they contain. While they implement generic interfaces, they also need to be kept in homogeneous collections, so they also implement a non-generic interface. The class instances are handled according to the type of data they represent and their propogation continues or doesn't continue based on that.

While this is not necessarily a .NET or C# issue, my code is in C#.

Example classes:

interface ITimedValue {
 TimeSpan TimeStamp { get; }
}

interface ITimedValue<T> : ITimedValue {
 T Value { get; }
}

class NumericValue : ITimedValue<float> {
 public TimeSpan TimeStamp { get; private set; }
 public float Value { get; private set; }
}

class DateTimeValue : ITimedValue<DateTime> {
 public TimeSpan TimeStamp { get; private set; }
 public DateTime Value { get; private set; }
}

class NumericEvaluator {
 public void Evaluate(IEnumerable<ITimedValue> values) ...
}

I have come up with two options:

Double Dispatch

I recently learned of the Visitor pattern and its use of double dispatch to handle just such a case. This appeals because it would allow undesired data to not propogate (if we only want to handle an int, we can handle that differently than a DateTime). Also, the behaviors of how the different types are handled would be confined to the single class that is handling the dispatch. But there is a fair bit of maintenance if/when a new value type has to be supported.

Union Class

A class that contains a property for each value type supported could be what each of these classes store. Any operation on a value would affect the appropriate component. This is less complex and less maintenance than the double-dispatch strategy, but it would mean that every piece of data would propogate all the way through unnecessarily as you can no longer discriminate along the lines of "I don't operate upon that data type". However, if/when new types need to be supported, they only need to go into this class (plus whatever additional classes that need to be created to support the new data type).

class UnionData {
 public int NumericValue;
 public DateTime DateTimeValue;
}

Are there better options? Is there something in either of these two options that I did not consider that I should?

Erythritol

What could possibly occur in NumericEvaluator's Evaluate method that would operate on a DateTime or a float? – Eustasius

on a mobile right now, so I can't write a proper answer, but try googling the use of dynamic for double dispatch (that reduces greatly the boilerplate required by the visitor pattern) or the implementation of union types in c# (I remember a beautiful implementation by @Juliet somewhere here on SO) – Tichon

@Chris Shain: That's part of the benefit of the double-dispatch solution -- it wouldn't have to. For a DateTime, either the double-dispatch solution ignores it or the variant solution consumes it as a 0 value. – Erythritol

I do not understand the question. (although it appears many others do) From what I can tell, the given code in the question appears to solve the problem. As long as all the different classes implement the same non-generic interface, they can be kept in homogeneous collections, and accessed through that interface. What else is needed? – Sextuplet

Answer 1

method 1, using dynamic for double dispatch (credit goes to http://blogs.msdn.com/b/curth/archive/2008/11/15/c-dynamic-and-multiple-dispatch.aspx). Basically you can have your Visitor pattern simplified like this:

class Evaluator {
 public void Evaluate(IEnumerable<ITimedValue> values) {
    foreach(var v in values)
    {
        Eval((dynamic)(v));
    }
 }

 private void Eval(DateTimeValue d) {
    Console.WriteLine(d.Value.ToString() + " is a datetime");
 }

 private void Eval(NumericValue f) {
    Console.WriteLine(f.Value.ToString() + " is a float");
 }

}

sample of usage:

var l = new List<ITimedValue>(){
    new NumericValue(){Value= 5.1F}, 
    new DateTimeValue() {Value= DateTime.Now}};

new Evaluator()
    .Evaluate(l);
       // output:
       // 5,1 is a float
       // 29/02/2012 19:15:16 is a datetime

method 2 would use Union types in c# as proposed by @Juliet here (alternative implementation here)

Tichon

Glad you came back and posted these, I couldn't find them. And thank you for correcting my incorrect use of the term "variant". – Erythritol

I've seen them called variant types too. And sum types and (maybe incorrectly?) algebraic data types. I'm by no means an expert so I wasn't trying to correct you: "union types" just happens to be the way they were called in the answer I was trying to point you to. :) – Tichon

Answer 2

I tell you have I've solved a similar situation - is by storing the Ticks of a DateTime or TimeSpan as double in the collection and by using IComparable as a where constraint on the type parameter. The conversion to double / from double is performed by a helper class.

Please see this previous question.

Funnily enough this leads to other problems, such as boxing and unboxing. The application I am working on requires extremely high performance so I need to avoid boxing. If you can think of a great way to generically handle different datatypes (including DateTime) then I'm all ears!

Crazed

Answer 3

Why not just implement the interface that you actually want, and allow the implementing type to define what the value is? For example:

class NumericValue : ITimedValue<float> {
 public TimeSpan TimeStamp { get; private set; }
 public float Value { get; private set; }
}

class DateTimeValue : ITimedValue<DateTime>, ITimedValue<float> {
 public TimeSpan TimeStamp { get; private set; }
 public DateTime Value { get; private set; }
 public Float ITimedValue<Float>.Value { get { return 0; } }
}

class NumericEvaluator {
 public void Evaluate(IEnumerable<ITimedValue<float>> values) ...
}

If you want the behavior of the DateTime implementation to vary based on the particular usage (say, alternate implementations of Evaluate functions), then they by definition need to be aware of ITimedValue<DateTime>. You can get to a good statically-typed solution by providing one or more Converter delegates, for example.

Finally, if you really only want to handle the NumericValue instances, just filter out anything that isn't a NumericValue instance:

class NumericEvaluator {
    public void Evaluate(IEnumerable<ITimedValue> values) {
        foreach (NumericValue value in values.OfType<NumericValue>()) {
            ....
        }
    }
}

Eustasius

I actually considered using OfType, but I couldn't remember why I didn't go through with it. Digging through notes, I found a case where data of a different type was expected to show up occasionally as a marker. I could enumerate the collection multiple times to account for that, but I'd prefer to avoid the inefficiency (this is a real-time system). – Erythritol

How about values.Where(v => v is X || v is Y)? Though again I ask what you'd possibly what to do with a heterogeneous enumeration of X's and Y's, if they don't have a common base type or interface. – Eustasius

In this case, they were attempting to inject a temporal metric into the data outside of the time stamp that is already present. – Erythritol

Answer 4

Good question. The first thing that came to my mind was a reflective Strategy algorithm. The runtime can tell you, either statically or dynamically, the most derived type of the reference, regardless of the type of the variable you are using to hold the reference. However, unfortunately, it will not automatically choose an overload based on the derived type, only the variable type. So, we need to ask at runtime what the true type is, and based on that, manually select a particular overload. Using reflection, we can dynamically build a collection of methods identified as handling a particular sub-type, then interrogate the reference for its generic type and look up the implementation in the dictionary based on that.

public interface ITimedValueEvaluator
{
   void Evaluate(ITimedValue value);
}

public interface ITimedValueEvaluator<T>:ITimedValueEvaluator
{
   void Evaluate(ITimedValue<T> value);
}

//each implementation is responsible for implementing both interfaces' methods,
//much like implementing IEnumerable<> requires implementing IEnumerable
class NumericEvaluator: ITimedValueEvaluator<int> ...

class DateTimeEvaluator: ITimedValueEvaluator<DateTime> ...

public class Evaluator
{
   private Dictionary<Type, ITimedValueEvaluator> Implementations;

   public Evaluator()
   {
      //find all implementations of ITimedValueEvaluator, instantiate one of each
      //and store in a Dictionary
      Implementations = (from t in Assembly.GetCurrentAssembly().GetTypes()
      where t.IsAssignableFrom(typeof(ITimedValueEvaluator<>)
      and !t.IsInterface
      select new KeyValuePair<Type, ITimedValueEvaluator>(t.GetGenericArguments()[0], (ITimedValueEvaluator)Activator.CreateInstance(t)))
      .ToDictionary(kvp=>kvp.Key, kvp=>kvp.Value);      
   }

   public void Evaluate(ITimedValue value)
   {
      //find the ITimedValue's true type's GTA, and look up the implementation
      var genType = value.GetType().GetGenericArguments()[0];

      //Since we're passing a reference to the base ITimedValue interface,
      //we will call the Evaluate overload from the base ITimedValueEvaluator interface,
      //and each implementation should cast value to the correct generic type.
      Implementations[genType].Evaluate(value);
   }   

   public void Evaluate(IEnumerable<ITimedValue> values)
   {
      foreach(var value in values) Evaluate(value);
   }
}

Notice that the main Evaluator is the only one that can handle an IEnumerable; each ITimedValueEvaluator implementation should handle values one at a time. If this isn't feasible (say you need to consider all values of a particular type), then this gets really easy; just loop through every implementation in the Dictionary, passing it the full IEnumerable, and have those implementations filter the list to only objects of the particular closed generic type using the OfType() Linq method. This will require you to run all ITimedValueEvaluator implementations you find on the list, which is wasted effort if there are no items of a particular type in a list.

The beauty of this is its extensibility; to support a new generic closure of ITimedValue, just add a new implementation of ITimedValueEvaluator of the same type. The Evaluator class will find it, instantiate a copy, and use it. Like most reflective algorithms, it's slow, but the actual reflective part is a one-time deal.

Mishmash