Monday, July 26, 2010

C# Specializations by Traits IV


C# Specializations by Traits IV


Geometry

In last three blogs (I'm productive these days in blogs, instead of klocs) I explained how to to specializations in C#. This blog only explains how it begon, give different possibilities to design things, and wraps it up.


Towards specializations

Developing Boost.Geometry, in C++, and doing some more C# this year as well, I wondered how a generic geometry library in C# would look like. Ideally it would be as Boost.Geometry, of course... But Boost.Geometry is based on traits and C++ specializations, partial specializations, tag dispatching. All modern C++ generic programming stuff. Not easily doable in C#.

Calculating the distance between two arbitrary point types would already be something. I tried many methods, and discussed them with my collegue Paul den Dulk, and he helped me, suggesting more methods and some essential pieces. Putting it together, adding the dictionary as the runtime register instead of the compiletime C++ specializations, the point distance function is looking exactly the same as Boost.Geometry now!

Some notes

There are still many differences from this system with C++ specializations, of course.
  • in C++ it is compile-time and checked at compile-time
  • therefore in C++ it is very fast
  • in C# the dictionary is runtime and checked at runtime
  • because the dictionary lookup and necesary cast it is slower in C#
  • C++ has partial specializations, don't know (yet) how to do that in C#
  • C++ has type calculations, the whole template metaprogramming is based on that. 
  • in C# it is only the methods
  • because in C# it is runtime, it gives some advantages as well: you can register different traits classes when needed
  • and so, e.g. the ORM can handle the same model in different ways

Timings

As said the dictionary consultation, together with the cast, take some time. Using the geometry case distance, I timed it and it is certainly measurable.

Ten million distance calculations on my computer:
  • Using interfaces: 0.10 seconds
  • Using delegates: 0.15 seconds
  • Using traits: 0.13 seconds
  • Using a register: 0.42 seconds
So, in fact 4 times slower. It is much in this case, but this is compared to a small calculation (Pythagoras). If applied using GUI, database, disk io, or occasionally (and not 10 million times), the lookup will probably fall away.

Complete program

The program to research, with 10 possible implementations, with interfaces, wrappers, delegates, traits, registers and lambdas, is shown below.

using System;
using System.Diagnostics;

using System.Collections.Generic;


namespace GenericGeometry
{
    interface IPoint
    {
        double x();
        double y();
        void increase();
    }

    delegate double get_x<Point>(Point p);
    delegate double get_y<Point>(Point p);

    public interface ITraitsBase {}

    public interface ITraits<Point> : ITraitsBase
    {
        double get_x(Point p);
        double get_y(Point p);
    }

    class TraitsRegister
    {
        public static IDictionary<Type, ITraitsBase> register;

        public static void Register<PointType>(ITraits<PointType> t)
        {
            if (register == null)
            {
                register = new Dictionary<Type, ITraitsBase>();
            }
            register[typeof(PointType)] = t;
        }
    }

    class LambdaRegister
    {
        public static IDictionary<Type, Tuple<object, object>> register;

        public static void Register<Point>(get_x<Point> gx, get_y<Point> gy)
        {
            if (register == null)
            {
                register = new Dictionary<Type, Tuple<object, object>>();
            }
            register[typeof(Point)] = new Tuple<object, object>(gx, gy);
        }
    }


    // The generic library, with functions as "Distance", working on IPoint or on any point
    class Algorithm
    {
        // (1) Using an interface to access coordinates
        public static double Distance(IPoint p1, IPoint p2)
        {
            double dx = p1.x() - p2.x();
            double dy = p1.y() - p2.y();
            return Math.Sqrt(dx * dx + dy * dy);
        }

        // (7) use delegates to access coordinates of not interfaced point type
        public static double Distance<Point>(Point p1, Point p2,
            get_x<Point> gx,
            get_y<Point> gy)
        {
            double dx = gx(p1) - gx(p2);
            double dy = gy(p1) - gy(p2);
            return Math.Sqrt(dx * dx + dy * dy);
        }

        // (8) use traits/accessor to access coordinates of not interfaced point type
        public static double Distance<Point>(Point p1, Point p2, ITraits<Point> traits)
        {
            double dx = traits.get_x(p1) - traits.get_x(p2);
            double dy = traits.get_y(p1) - traits.get_y(p2);
            return Math.Sqrt(dx * dx + dy * dy);
        }

        // (9) use traits/REGISTER accessor to access coordinates of not interfaced point type
        public static double DistanceTR<Point>(Point p1, Point p2)
        {
            ITraits<Point> traits = TraitsRegister.register[typeof(Point)] as ITraits<Point>;
            double dx = traits.get_x(p1) - traits.get_x(p2);
            double dy = traits.get_y(p1) - traits.get_y(p2);
            return Math.Sqrt(dx * dx + dy * dy);
        }

        // (10) use (tupled) lambda/REGISTER accessor to access coordinates of not interfaced point type
        public static double DistanceLR<Point>(Point p1, Point p2)
        {
            var pair = LambdaRegister.register[typeof(Point)] as Tuple<object, object>;
            get_x<Point> gx = pair.Item1 as get_x<Point>;
            get_y<Point> gy = pair.Item2 as get_y<Point>;
            double dx = gx(p1) - gx(p2);
            double dy = gy(p1) - gy(p2);
            return Math.Sqrt(dx * dx + dy * dy);
        }
    }


    // (1) implement IPoint
    class MyPoint1 : IPoint
    {
        private double m_x, m_y;
        public MyPoint1(double x, double y)
        {
            m_x = x;
            m_y = y;
        }
        public double x() { return m_x; }
        public double y() { return m_y; }
    }


    // Non-interfaced class...
    class MyPoint2
    {
        public double x { get; set; }
        public double y { get; set; }
    }

    // (2) Create a wrapper (implementing IPoint)
    class PointWrapper : IPoint
    {
        MyPoint2 m_point;
        public PointWrapper(MyPoint2 p)
        {
            m_point = p;
        }

        public double x() { return m_point.x; }
        public double y() { return m_point.y; }
    }

    // (3) Create a generic wrapper using delegates, implementing IPoint
    class DelPointWrapper<Point> : IPoint
    {
        Point m_point;
        get_x<Point> m_gx;
        get_y<Point> m_gy;

        public DelPointWrapper(Point p, get_x<Point> gx, get_y<Point> gy)
        {
            m_point = p;
            m_gx = gx;
            m_gy = gy;
        }

        public double x() { return m_gx(m_point); }
        public double y() { return m_gy(m_point); }

        public void increase()
        {
            //m_x += 0.000001;
            //m_y += 0.000001;
        }

    }

    // (7) define delegates in a static class
    static class Accessor
    {
        public static get_x<MyPoint2> getX = p => p.x;
        public static get_y<MyPoint2> getY = p => p.y;
    }


    // (8,9) use a sort of Traits class
    class Traits : ITraits<MyPoint2>
    {
        public double get_x(MyPoint2 p)
        {
            return p.x;
        }
        public double get_y(MyPoint2 p)
        {
            return p.y;
        }
    }

    class Program
    {
        const int n = 10000000;

        static void Timed<Point>(String header, Point a, Point b) where Point : IPoint
        {
            double d = 0.0;
            Stopwatch st = new Stopwatch();
            st.Start();
            for (int i = 0; i < n; i++)
            {
                d += Algorithm.Distance(a, b);
            }
            st.Stop();
            System.Console.WriteLine(header + " " + d + " " + st.Elapsed.ToString());
            System.Threading.Thread.Sleep(500);

        }

        // Creating the delegates
        static double point_get_x(MyPoint2 p)
        {
            return p.x;
        }
        static double point_get_y(MyPoint2 p)
        {
            return p.y;
        }

        static void Main(string[] args)
        {

            int option = args.Length > 0 ? Int32.Parse(args[0]) : 10;
            System.Console.Write("{0} ", option);

            // Point without interface
            MyPoint2 p1 = new MyPoint2();
            p1.x = 3;
            p1.y = 5;
            MyPoint2 p2 = new MyPoint2();
            p2.x = 6;
            p2.y = 9;

            switch (option)
            {
                case 1:
                    {
                      // Option 1, point with interface
                      MyPoint1 ip1 = new MyPoint1(3, 5);
                      MyPoint1 ip2 = new MyPoint1(6, 9);
                      Timed("Using interface", ip1, ip2);
                    } break;
                case 2:
                    {
                      // Option 2a:
                      PointWrapper pw1 = new PointWrapper(p1);
                      PointWrapper pw2 = new PointWrapper(p2);
                      Timed("Using wrapper", pw1, pw2);
                    } break;
                case 3:
                    {
                      // Option 2b:
                      DelPointWrapper<MyPoint2> dpw1 = new DelPointWrapper<MyPoint2>(p1, point_get_x, point_get_y);
                      DelPointWrapper<MyPoint2> dpw2 = new DelPointWrapper<MyPoint2>(p2, point_get_x, point_get_y);
                      Timed("Using delegate-wrapper", dpw1, dpw2);
                    } break;
                case 4:
                    {
                      // Option 2c: with inline delegates
                      DelPointWrapper<MyPoint2> idpw1 = new DelPointWrapper<MyPoint2>(p1
                      , delegate(MyPoint2 p) { return p.x; }
                      , delegate(MyPoint2 p) { return p.y; }
                      );
                      DelPointWrapper<MyPoint2> idpw2 = new DelPointWrapper<MyPoint2>(p2
                      , delegate(MyPoint2 p) { return p.x; }
                      , delegate(MyPoint2 p) { return p.y; }
                      );
                      Timed("Using inline delegate-wrapper", idpw1, idpw2);
                    } break;
                case 5:
                    {
                      DelPointWrapper<MyPoint2> ldpw1 = new DelPointWrapper<MyPoint2>(p1, p => p.x, p => p.y);
                      DelPointWrapper<MyPoint2> ldpw2 = new DelPointWrapper<MyPoint2>(p2, p => p.x, p => p.y);
                      Timed("Using lambda-wrapper", ldpw1, ldpw2);
                    } break;
                case 6:
                    {
                      double d = 0.0;
                      Stopwatch st = new Stopwatch();
                      st.Start();
                      for (int i = 0; i < n; i++)
                      {
                      d += Algorithm.Distance(p1, p2, p => p.x, p => p.y);
                      }
                      st.Stop();
                      System.Console.WriteLine("Using delegate-algorithm+lambda " + d + " " + st.Elapsed.ToString());
                    } break;
                case 7:
                    {
                      double d = 0.0;
                      Stopwatch st = new Stopwatch();
                      st.Start();
                      for (int i = 0; i < n; i++)
                      {
                      d += Algorithm.Distance(p1, p2, Accessor.getX, Accessor.getY);
                      }
                      st.Stop();
                      System.Console.WriteLine("Using accessor met static delegates " + d + " " + st.Elapsed.ToString());
                    } break;
                case 8:
                    {
                      Traits traits = new Traits();

                      double d = 0.0;
                      Stopwatch st = new Stopwatch();
                      st.Start();
                      for (int i = 0; i < n; i++)
                      {
                      d += Algorithm.Distance(p1, p2, traits);
                      }
                      st.Stop();
                      System.Console.WriteLine("Using traits " + d + " " + st.Elapsed.ToString());
                    } break;
                case 9:
                    {
                      Traits traits = new Traits();
                      TraitsRegister.Register<MyPoint2>(traits);

                      double d = 0.0;
                      Stopwatch st = new Stopwatch();
                      st.Start();
                      for (int i = 0; i < n; i++)
                      {
                      d += Algorithm.DistanceTR(p1, p2);
                      }
                      st.Stop();
                      System.Console.WriteLine("Using traits/register " + d + " " + st.Elapsed.ToString());
                    } break;
                case 10:
                    {
                      LambdaRegister.Register<MyPoint2>(p => p.x, p => p.y);

                      double d = 0.0;
                      Stopwatch st = new Stopwatch();
                      st.Start();
                      for (int i = 0; i < n; i++)
                      {
                      d += Algorithm.DistanceLR(p1, p2);
                      }
                      st.Stop();
                      System.Console.WriteLine("Using lamba/register " + d + " " + st.Elapsed.ToString());
                    } break;
            }

            System.Console.WriteLine("");
        }
    }
}

And here are the complete timings (for each the smallest of 5 runs):
1 Using interface 50000000 00:00:00.1000114
2 Using wrapper 50000000 00:00:00.1055539
3 Using delegate-wrapper 50000000 00:00:00.1812642
4 Using inline delegate-wrapper 50000000 00:00:00.1843941
5 Using lambda-wrapper 50000000 00:00:00.1810666
6 Using delegate-algorithm+lambda 50000000 00:00:00.1509385
7 Using accessor met static delegates 50000000 00:00:00.1274787
8 Using traits 50000000 00:00:00.1327729
9 Using traits/register 50000000 00:00:00.4192440
10 Using lamba/register 50000000 00:00:00.4194542

Conclusions

Are already done. Specializations in C# are possible. Use them, it makes C# and generics more fun.

Sunday, July 25, 2010

C# Specializations by Traits III


C# Specializations by Traits III


Stormy: Specializations by Traits - Object Relational Model

I like SOCI very much. It is a C++ ORM. Especially the way to go from SQL to model, the object-relational mapping, is very convenient. It is based on specializations.

In the earlier Blogs of this series I have shown that it is possible to do real specializations in C#. This is possible using the combination of traits, a dictionary, and (if necessary) extension methods. This is all explained in previous blogs and I will not explain it again. I will only show how this system is really convenient in Object Relational Mapping (ORM). A hundred-lines prototype is developed. Called Stormy (storm was already occupied).

Use case

In ORM the database (relational) is mapped to objects (models, C# classes). So by nature there are many classes all handled the same way (from SQL to the class instance).

Instead of using the ADO.NET SqlDataReader (delivering just abstract fields and not a model), we want to do things like this:
IEnumerable<Cat> cats = connection.Select<Cat>("select * from cat");

where
  • Cat is our model, shown below
  • connection is any connection to a database
  • the SQL statement is shown, literally. I like that.
  • so it returns a generic collection of our model
In C# it is not trivial to specialize the Select method per model. But with traits and a register it can be solved.

The model Cat

The model Cat is borrowed from nHibernate (I know nHibernate - it will not map the class below - it wants method to be virtual). Slightly modified (I like this way of specifying attributes):

public class Cat
{
    public Guid Id { get; set; }
    public string Name { get; set; }
    public char Sex { get; set; }
    public float Weight { get; set; }
}

The Object Relational mapping

The ORM is done entirely in code, the way SOCI does it. No XML mappings here. We stay with C#. We show here the implementations Map the Cat from (relational) Database to Object, and vice versa.


public class CatConverter : ITypeConversion<Cat>
{
    public Cat fromSql(SqlDataReader reader)
    {
        Cat cat = new Cat();
        cat.Id = (Guid)reader["CatId"];
        cat.Name = (string)reader["name"];
        cat.Sex = (((string)reader["sex"]) + " ")[0];
        cat.Weight = (float)reader["weight"];
        return cat;
    }

    public void fillParameters(Cat cat, SqlCommand command)
    {
        command.Parameters.Add(new SqlParameter("@name", cat.Name));
        command.Parameters.Add(new SqlParameter("@sex", cat.Sex));
        command.Parameters.Add(new SqlParameter("@weight", cat.Weight));
    }
}


Note that it is mapped using SqlDataReader. It can be made more convenient (eliminating casts) of course, but this is how it is done with SqlDataReader, normally.

That SOCI-like type-converter (I renamed the methods from_base to fromSQL and to_base to fillParameters) is an interface ITypeConversion<T>, and is registered (normally) once per model:
Orm.Register<Cat>(new CatConverter());


Main program

We can implement our scenario, converting from database to Cat and vice versa, using generic programming. Our program:
class Program
{
    static void Main(string[] args)
    {
        Orm.Register<Cat>(new CatConverter());

        Connection connection = new Connection(
            @"
                Data Source=localhost\SQLEXPRESS;
                MultipleActiveResultSets=True;
                Initial Catalog=stormy;
                Integrated Security=SSPI;
            "
);

        var cats = connection.Select<Cat>("select * from cat");
        foreach(Cat cat in cats)
        {
            System.Console.WriteLine("Cat {0} named {1}", cat.Id, cat.Name);
        }

        // Create subselection using linq (not related to SpecializationbyTraits)
        var toms = from cat in cats where cat.Name == "Tom" select cat;
        if (toms.Count() > 0)
        {
            Cat tom = toms.First();
            System.Console.WriteLine("Tom found, ID={0}", tom.Id);
        }
        else
        {
            Cat tom = new Cat();
            tom.Name = "Tom";
            tom.Sex = 'm';
            tom.Weight = 5.2F;
            connection.Execute(CatConverter.InsertSql(), tom);
        }
    }
}


We first register our type conversion specialization. We create a connection to the database (hard coded - alternatively you might get it from e.g. appSettings). We can use any SQL statement to fill any list with any (registered) model. For fun we use LINQ here to do a subselection. We can execute SQL to insert, update or delete things. That InsertSql is specified (for convenience, I prefer it close to its parameters) within the converter as well, it can be anywhere, up to you.
public static string InsertSql()
{
    return "insert into Cat(CatId, Name, Sex, Weight) values(NEWID(), @name, @sex, @weight)";
}



Stormy ORM - wrapping it up


Great isn't it? The Stormy code is about hundred lines now. Of course it is not a full-featured ORM as others are, but in many cases more convenient, more simple to understand, it does not create shadow classes, and it does not force you to learn a new criteria language. If you know SQL, you will like it!

The project including sample can be downloaded here.

We're nearly done with C# Specializations. It is really useful. Can be used everywhere. Makes C# closer to C++.

Next:
Stay tuned!

Friday, July 23, 2010

C# Specializations by Traits II


C# Specializations by Traits II


Cat and Mouse populate a Silverlight Listbox

In my previous blog we saw that you seriously can do specialization in C#, using traits classes, extension methods and a directionary. The use case was a bit centered on class (method) specialization.

In this blog we will see that it is equally possible, and probably even more useful, to specialize a generic method for different classes. The system is the same, the samples are more useful.

Use case

Imagine two models (classes), a Cat and a Mouse. They are different, not sharing an interface and not inheriting from a common base class. They are kept simple, just name and ID. On purpose attributes are named differently for Cat and Mouse.

    public class Cat
    {
        public Cat(int i, string n)
        {
            Id = i;
            Name = n;
        }
        public int Id { get; set; }
        public string Name { get; set; }
    }

    public class Mouse
    {
        public Mouse(int i, string n)
        {
            MouseId = i;
            MouseName = n;
        }
        public int MouseId { get; set; }
        public string MouseName { get; set; }
    }

We have two generic collections of them: a List<Cat> and a List<Mouse>. I like the generic collections! We want to add both collections to a Silverlight listbox... of course in a generic way. That is not trivial, but with help of previous blog, or more specificly with help of our new "Specialization by Traits" system, we can do it. Note that this example (filling a list box) is a bit inspired on this page where a dropdown should be specific for a model.

We will use the traits system which helped us so much in previous blog to reach our goal. And there are more traits-ways to do it.

Traits 1: Common Interface

First we create a traits class which tries to create a common interface, getting the Id and the Name for both classes in the same way.

namespace Traits
{
    public interface AnimalTraits<T>
    {
        int GetId(T obj);
        string GetName(T obj);
    }

    public class CatTraits : AnimalTraits<Models.Cat>
    {
        public int GetId(Models.Cat cat) { return cat.Id; }
        public string GetName(Models.Cat cat) { return cat.Name; }
    }
    public class MouseTraits : AnimalTraits<Models.Mouse>
    {
        public int GetId(Models.Mouse mouse) { return mouse.MouseId; }
        public string GetName(Models.Mouse mouse) { return mouse.MouseName; }
    }

    public static class AnimalRegister
    {
        private static IDictionary<System.Type, object> register;
        public static void Register<T>(AnimalTraits<T> traits)
        {
            if (register == null)
            {
                register = new Dictionary<System.Type, object>();
            }
            register[typeof(T)] = traits;
        }
        public static AnimalTraits<T> Get<T>()
        {
            return register[typeof(T)] as AnimalTraits<T>;
        }
    }
}


Once we have those classes, we can fill the list using them, using the common interface. For Cats we take the CatTraits, for the Mice the MouseTraits, of course. Or we can let the compiler take them automagically using that traits-register, the Dictionary<Type, object> which can be approached by the typeof function.

        private void fillGeneric1<T>(ListBox lb, IEnumerable<T> animals)
        {
            AnimalTraits<T> traits = AnimalRegister.Get<T>();

            foreach (T animal in animals)
            {
                ListBoxItem item = new ListBoxItem();
                item.Content = traits.GetName(animal);
                item.Tag = traits.GetId(animal);
                animalListBox.Items.Add(item);
            }
        }

        private void button1_Click(object sender, RoutedEventArgs e)
        {
            // (Re)fillGeneric1 our list using the generic way
            animalListBox.Items.Clear();
            fillGeneric1(animalListBox, cats);
            fillGeneric1(animalListBox, mice);
        }

We see that we can fill the listbox easily like this. The fillGeneric1 method is generic! It is specialized per animal.

However, if we want to do anything different for the Cats class than we do for Mice (besides getting ID and name), we have to solve it differently. This is in Traits 3 below. First Lambda.

"Traits 2": Lambda Register

Is this still traits... No traits involved, only lambda. They play the role of the traits. The architecture is similar.

We define a delegate type and create (usually in a singleton) a dictionary delegate-by-type. In this use case we need two delegates (one for ID, one for name) but that is flexible of course. We select here a dictionary of pairs.

We have the same directionary as in the previous examples as a register, mapping from Type to any object (now a delegate-pair). We add a convenience method to register lambda's and to retrieve them using Get<>


using System.Collections.Generic;

delegate int get_id<Animal>(Animal a);
delegate string get_name<Animal>(Animal a);

class LambdaRegister
{
    private static IDictionary<System.Type, KeyValuePair<object, object>> register;

    public static void Register<Animal>(get_id<Animal> gi, get_name<Animal> gn)
    {
        if (register == null)
        {
            register = new Dictionary<System.Type, KeyValuePair<object,object>>();
        }
        register[typeof(Animal)] = new KeyValuePair<object,object>(gi, gn);
    }

    public static void Get<Animal>(out get_id<Animal> gi, out get_name<Animal> gn)
    {
        KeyValuePair<object, object> pair = register[typeof(Animal)];
        gi = pair.Key as get_id<Animal>;
        gn = pair.Value as get_name<Animal>;
    }
}

The register can be initialized, once, like this:

            LambdaRegister.Register<Models.Cat>(p => p.Id, p => p.Name);
            LambdaRegister.Register<Models.Mouse>(p => p.MouseId, p => p.MouseName);

We see: we created the register in the same way. But, again, we don't need any traits here. Then we populate our listbox using the lambda-register

        private void fillGeneric3<T>(ListBox lb, IEnumerable<T> animals)
        {
            get_id<T> gi;
            get_name<T> gn;
            LambdaRegister.Get<T>(out gi, out gn);

            foreach (T animal in animals)
            {
                ListBoxItem item = new ListBoxItem();
                item.Tag = gi(animal);
                item.Content = "L " + gn(animal);
                animalListBox.Items.Add(item);
            }
        }



Traits 3: Specific Goal

We can also create a traits interface which is designed to fill a listbox. It then has a method called (e.g.) Apply, which takes a listbox and adds an item. Or which returns an item. Anyway, the traits classes which (also here) are specific for Cat and Mouse have full access to these classes, and can call any method. In this way they assign the ListBoxItem and return it.

using System;
using System.Windows;
using System.Windows.Controls;

namespace Traits
{
    public interface FillAnimalTraits<T>
    {
        void Apply(ListBoxItem item, T obj);
    }

    public class FillCatTraits : FillAnimalTraits<Models.Cat>
    {
        public void Apply(ListBoxItem item, Models.Cat cat)
        {
            item.Tag = cat.Id;
            item.Content = String.Format("cat: {0}", cat.Name);
        }
    }
    public class FillMouseTraits : FillAnimalTraits<Models.Mouse>
    {
        public void Apply(ListBoxItem item, Models.Mouse mouse)
        {
            item.Tag = mouse; // Note: here the object is tagged to the item, instead of the ID
            item.Content = String.Format("mouse: {0}", mouse.MouseName);
        }
    }
}


The register is be initialized, again, once, in a similar way.
AnimalFillListBoxRegister.Register<Models.Cat>(new Traits.FillCatTraits());
AnimalFillListBoxRegister.Register<Models.Mouse>(new Traits.FillMouseTraits());


We then use it in our code as following:
        private void fillGeneric3<T>(ListBox lb, IEnumerable<T> animals)
        {
            FillAnimalTraits<T> traits = AnimalFillListBoxRegister.Get<T>();
            foreach (T animal in animals)
            {
                ListBoxItem item = new ListBoxItem();
                traits.Apply(item, animal);
                animalListBox.Items.Add(item);
            }
        }

You see, the fillGeneric3 is quite convenient (and generic) now. The traits do the work here.

Traits 3b: Extensions


Finally, as in our previous blog, we can combine these very same traits quite conveniently with extension methods, defined as following:
    public static ListBoxItem ToListBoxItem<T>(this T obj)
    {
        FillAnimalTraits<T> traits = register[typeof(T)] as FillAnimalTraits<T>;
        ListBoxItem item = new ListBoxItem();
        traits.Apply(item, obj);
        return item;
    }        

and used as the following:

        private void fillGeneric4<T>(ListBox lb, IEnumerable<T> animals)
        {
            foreach (T animal in animals)
            {
                animalListBox.Items.Add(animal.ToListBoxItem());
            }
        }

Looking cool.

And yes, the extension method might make use of the lambda register as well, instead of the traits register, of course. No traits needed then. We can make it more beautiful with each step. This is not worked out now.


OK, I again like this system very much. I blogged it yesterday (based on research earlier this month and in April) and today we did need it at our office. We did need it twice!

The Silverlight Application can be seen here and complete sources are here.

In the next blogs we will see more on this:
  • geometry...
  • object relational modelling...
  • and of course there will be more on geometry (Boost.Geometry) soon
Stay tuned!

Thursday, July 22, 2010

C# Specializations by Traits I


C# Specializations by Traits I

Since version 2.0, C# supports generics. Really a great feature. Generics are a bit comparable to C++ templates. Generics enable a C# programmer to do generic programming. But alas, specialization is not supported by default. However, with some tricks you can get quite close. In fact, you can do it, you can use specialization in C#.

Generics in C# are defined like, e.g. MyClass<T> and can be instantiated then as MyClass<int> for the integer case, MyClass<double> for the double case, etc. Generics can be used at the class level and at the method level.

What is specialization? Many C# programmers will ask. With specializations you can create different implementations for (more) specific instances of a class. There is class specialization and there is function specialization. We will work this out in detail below for C#.

What are traits classes? Traits classes are associating information with a compile-time entity. Stated otherwise, traits add another level of indirection. And by adding a level of indirection, most problems can be solved. We will see traits below.

Use case

So let's first define what we want. (By researching how to C# specializations would look like in a Generic Geometry Library, I encountered this link and my sample is a bit based on it).  We have a class:
class MyClass<T>
{
    public string Foo() { return "MyClass"; }
}

And we want to do something this with this class:
            var cls1 = new MyClass<int>();
            var cls2 = new MyClass<double>();

            string id = cls1.Bar();
            string dd = cls2.Bar();

Where, and that is important here: the Bar() method gives a different result for  MyClass<int> then for MyClass<double>. So, MyClass is specialized for MyClass<int> in another way as for MyClass<double>. There is no inheritance here; MyClass<int> is not inherited from MyClass<T>, but is a specific case of MyClass<T>.

Extension methods

With extension methods, another really great new feature of C#, we can do this.

        public static string Bar1<T>(this MyClass<T> obj)
        {
            return "*";
        }
        public static string Bar1(this MyClass<int> obj)
        {
            return "i";
        }
        public static string Bar1(this MyClass<double> obj)
        {
            return "d";
        }

This appliance of extension methods for specialization is described here, in a similar example. The Bar1 method, as it is now called, is an extension method, and results in different results for the int case and the double case. This is already great.

Alas, as soon as called within another generic function, for example:
        public static void CallBar1<T>(MyClass<T> cls)
        {
            string s = cls.Bar1();
        }



it will always call the generic one, returning a *. If we remove that generic one, we get compiler errors:
Error    1    Instance argument: cannot convert from 'MyClass<T>' to 'MyClass<int>' 
Error    2    'MyClass<T>' does not contain a definition for 'Bar1' and the best extension method overload 'Bar1(StackOverflow.MyClass<int>)' has some invalid arguments   

Whatever we try here, it will not work, as is described here on the same page. Alas. In C++ this would work. We need this to work, otherwise it is of low usage.

Traits classes

So we try another approach by adding a level of indirection. This turns out to be, based on our good experiences in C++, a traits class. It reads like this:

    interface BaseTraits<T>
    {
        string Apply(T cls);
    }

    class IntTraits : BaseTraits<MyClass<int>>
    {
        public string Apply(MyClass<int> cls)
        {
            return cls.Foo() + " i";
        }
    }

    class DoubleTraits : BaseTraits<MyClass<double>>
    {
        public string Apply(MyClass<double> cls)
        {
            return cls.Foo() + " d";
        }
    }


We see here a generic interface, BaseTraits<T>, and two derived classes implementing that interface for specific cases of MyClass. They are completely different classes. The only thing is that they implement the same interface. Their method Apply does something with that class, here returning a string.

We implement a new generic extension method, Bar2, there is only one version of it now. It takes both the object and traits as an argument. It calls the apply method of the traits, specifying the object:

        public static string Bar2<T>(this T obj, BaseTraits<T> traits)
        {
            return traits.Apply(obj);
        }


Bar2 can be called like the following:
string sb21 = cls1.Bar2(new IntTraits());
string
sb22 = cls2.Bar2(new DoubleTraits());


and it now works from a generic method. So that is the difference with the previous CallBar1: that one didn't work. This one works, because we have added a level of indirection, the traits class.       

public static void CallBar2<T>(T cls, BaseTraits<T> traits)
{
    string s = traits.Apply(cls);
}


CallBar2(cls1, new IntTraits());

In both cases (int / double) the correct Apply method is taken. Of course it is... Because the traits to call is specified explicitly... It is just inheritance, nothing new. Besides this, I think it is considered as ugly to always mention the traits class so explicitly...

To make up the balance, this traits give:
  • a call to Bar2 which is quite ugly
  • but the traits system is still quite powerful! 
  • and this traits system is the key to success! 
Read on.

IDictionary<Type, object>

In C++, traits classes are used for generic programming, as e.g. in tag dispatching (my favourite). Traits are (I repeat) associating information with a compile-time entity. The right implementation (information) is found by the compiler automatically by the compile-time entity (the class). It seems to feel the type automagically and performs the right action (defining a type, calling a method).

As mentioned, in C# this is not possible, it is just not implemented, specialization is not implemented. However, we can associate information between types and traits using a dictionary.

So the 'trick' (we talked about auto-magic) is a dictionary of types and traits classes... The directionary-key is a Type, its value is a traits. Let's call it a specialization register, traits register, or just a register. So we add:
public static IDictionary<Type, object> register;


... and we fill the register once, for example at the start of program:
register = new Dictionary<Type, object>();
register[typeof(MyClass<int>)] = new IntTraits();
register[typeof(MyClass<double>)] = new DoubleTraits();


... and then we use this register in our extension method Bar to find the right traits:
public static string Bar<T>(this T obj)
{
    BaseTraits<T> traits = register[typeof(T)] as BaseTraits<T>;
    return traits.Apply(obj);
}


... and we can use it now without referring to the traits:
            var cls1 = new MyClass<int>();
            var cls2 = new MyClass<double>();

            string id = cls1.Bar();
           string dd = cls2.Bar();

This was our use case! It will call the right specialization. Magic! Also if you call it from a generic method, it takes the right specialization. We have implemented specialization in C#. We've done it!

A few notes

  • Don't think this as an academic exercise. It has thousands of use cases. It is really a great design pattern. Let's call it Specialization by Traits
  • Don't think this is common place. I googled for several combinations of specialization, dictionary<Type, object>, traits,extension methods, and google is not holy but still your friend; I did find many reports that specialization is not possible, but nowhere I saw any mentioning of this system. Close is this and this where a similar register is used, but for different purposes, and this one which is quite close
  • We can simplify the calls to register by making it a private singleton and adding a method, see below for the end version
  • We use here the extension method and call it as it if were a method of MyClass<T>. It is also possible to use it in a normal method (of course), for example to calculate the distance between two points, in the next Blog
  • Depending on the use case, the register of traits can also be a register of delegates, and registering can be done using a lambda function. The traits class then takes the form of a delegate. We wil see more of this.
  • Of course the dictionary will influence performance. So contrary to C++, where specialization and inline methods will boost performance, it will be a little bit slower here. Normally, no problem, I estimate. We will come back to this in another blog.


So, to be complete, we list the full source here, including the main program with the more appropriate calls to the dictionary.

using System;
using System.Collections.Generic;


namespace StackOverflow
{
    class MyClass<T>
    {
        public string Foo() { return "MyClass"; }
    }

    interface BaseTraits<T>
    {
        string Apply(T cls);
    }

    class IntTraits : BaseTraits<MyClass<int>>
    {
        public string Apply(MyClass<int> cls)
        {
            return cls.Foo() + " i";
        }
    }

    class DoubleTraits : BaseTraits<MyClass<double>>
    {
        public string Apply(MyClass<double> cls)
        {
            return cls.Foo() + " d";
        }
    }

    static class Specialization
    {
        private static IDictionary<Type, object> register;

        public static void Associate<T>(object traits)
        {
            if (register == null)
            {
                register = new Dictionary<Type, object>();
            }
            register[typeof(T)] = traits;
        }
        public static BaseTraits<T> Associated<T>()
        {
            return register[typeof(T)] as BaseTraits<T>;
        }
    }

    
    static class Program
    {
        public static string Bar<T>(this T obj)
        {
            return Specialization.Associated<T>().Apply(obj);
        }

        public static string CallBar<T>(MyClass<T> cls)
        {
            return cls.Bar();
        }

        static void Main(string[] args)
        {
            Specialization.Associate<MyClass<int>>(new IntTraits());
            Specialization.Associate<MyClass<double>>(new DoubleTraits());

            var cls1 = new MyClass<int>();
            var cls2 = new MyClass<double>();

            string id = cls1.Bar();
            string dd = cls2.Bar();
            string ii = CallBar(cls1);
            string di = CallBar(cls2);
        }
    }
}


In the next blogs we will see how this is really useful, in real use cases:
  • geometry...
  • object relational modelling...
  • filling Silverlight lists...
Stay tuned!