Luke Hoban's Blog

March, 2007

  • LukeH's WebLog

    In-Memory Query with C#2.0 and C#3.0

    • 12 Comments

    Here's some sample code from a demo I did a few months ago.  It's a simple example of how much easier in-memory query and transformation are with C#3.0 and LINQ, compared with a straightforward implementation using C#2.0.

    The Query

    The goal is to implement this query:

    "Get all the instance methods on System.String, ordered by name and grouped into overloads, each with the name of the overloaded member and the number of overloads."

    For example, you can imagine that a C# editor IntelliSense implementation might need code such as this one to present a completion list on an instance of System.String.

    C# 2.0 Implementation

    MethodInfo[] methods = typeof(string).GetMethods();
    
    List<MethodInfo> instanceMethods = new List<MethodInfo>();
    foreach (MethodInfo method in methods)
        if (!method.IsStatic)
            instanceMethods.Add(method);
    instanceMethods.Sort(delegate(MethodInfo m1, MethodInfo m2) { return m1.Name.CompareTo(m2.Name); });
    Dictionary<string, List<MethodInfo>> methodGroups = new Dictionary<string, List<MethodInfo>>();
    foreach (MethodInfo method in instanceMethods)
    {
        if (methodGroups.ContainsKey(method.Name))
        {
            methodGroups[method.Name].Add(method);
        }
        else
        {
            methodGroups.Add(method.Name, new List<MethodInfo>());
            methodGroups[method.Name].Add(method);
        }
    }
    List<Container> result = new List<Container>();
    foreach (string name in methodGroups.Keys)
    {
        Container container = new Container();
        container.MethodName = name;
        container.Overloads = methodGroups[name].Count;
        result.Add(container);
    }
    foreach (Container item in result)
    {
        Console.WriteLine(item);
    }
    

    C# 3.0 Implementation

    MethodInfo[] methods = typeof(string).GetMethods();
    
    var query =
        from m in methods
        where !m.IsStatic
        orderby m.Name
        group m by m.Name into g
        select new { MethodName = g.Key, Overloads = g.Count() };
    
    foreach (var item in query)
    {
        Console.WriteLine(item);
    }

    Conclusion

    The C#3.0 implementation is quite a bit shorter!  But more importantly, it reads a lot like the English description of the query given above.   It's also a more declarative description of the query - it says what to do, but not how to do it.  These are general features of using LINQ to Objects with C#3.0.  There are many cases where what would have been for loops, if statements, and assignments to intermediate collections - can now be written as queries, providing a clearer description of what the code is doing.

    BTW - Which do you think is faster?  Why?

    kick it on DotNetKicks.com

  • LukeH's WebLog

    The C# Compiler in Orcas

    • 1 Comments

    I started working on the C# compiler team a little more than a year ago, right around the time that we started development on the Orcas C# compiler.  It's been a great project to work on, and it's good to see folks starting to use the new compiler in the recently released March CTP.  I thought it might be interesting to share some of the background on how we approached the scheduling aspects of the development of the compiler.

    We had the great benefit of starting Orcas with a prototype C#3.0 compiler already built and released as part of the LINQ CTPs.  This had allowed us to get great in-depth feedback on the language features early, and has enabled a large community of developers to work with LINQ over the last year and a half.  Although this prototype compiler was great for many projects, there were a number of significant known limitations, which were a result of fundamental implementation decisions, and so the senior developers on the team decided that we would need to implement the C#3.0 language features more-or-less from the ground up to get to a ship-quality implementation.  This process also helped us to clarify the design for many of the features, and to make changes or improvements to the design where necessary.

    Here's a quick summary of how we scheduled our work to build the C#3.0 compiler for Orcas. 

    Milestone 1

    Our first goal was to get the most fundamental new language features implemented, so we could begin building LINQ applications with the Orcas compiler as early as possible.  Many of the features in this first set were also chosen because they were pre-requisites for implementing some of the later language features.  For example, lambdas were important to get in early, because the conversion of lambdas to expression trees depended on this.  Here's what we built first:  

    • Local Variable Type Inference (var)
    • Lambdas
    • Object Initializers
    • Extension Methods (usage)

    Milestone 2

    For our second milestone, our goal was to replace the C#3.0 prototype compiler that we had shipped with the May 2006 CTP.  When we finished this milestone, we actually moved all of the teams internally who were using C#3.0 over to use the Orcas C# compiler.  This required implementing:

    • Lambdas bound to Expression Trees
    • Extension Methods (definition)
    • Collection Initializers
    • Anonymous Types
    • Query Expressions

    Milestone 3

    The third milestone was shorter, and our goal for this milestone was to get to a good state for the first Beta.  The results of this milestone are what you'll see in the Orcas February/March CTP and the first Orcas Beta.  We also implemented one of the most requested language features in the history of C# - auto-implemented properties!

    • Auto-Implemented Properties
    • Enhancements to Collection Initializers
    • Non-language features, such as debuggability improvements

    Milestone 4

    We're now working on the last feature milestone for Orcas.  We're finishing off with one more language feature and a lot of work to improve compiler fundamentals, such as error messages and performance.  Note that this work won't make it into the first Beta:

    • Partial Methods
    • Compiler Error Message Improvements
    • Compiler Performance
    • Compiler Generated IL Performance
  • LukeH's WebLog

    Using LINQ to solve puzzles

    • 15 Comments

    A couple months ago, I had a great time participating in Microsoft's PuzzleHunt event along with our team "Cup<T>".  Normally, the puzzles in puzzle hunt are designed to limit the value of writing programs to help solve them.  But this year, I did end up writing some code to help with one of the puzzles - and it happened to be a simple LINQ query that helped.  Since this is an example of using LINQ in a problem domain that's pretty different than the usual querying examples, I thought it might be worth sharing.

    The Puzzle

    Here's a puzzle similar to the one in the puzzle hunt.  The diagram below is a bunch of weights (A-M) hanging from a system of bars.  Each weight has an integer value between 1 and 13, and the goal is to figure out what each weight must be for the the diagram below to balance correctly as shown: 

                              |
                              |
                  +--+--+--+--+--+--+--+
                  |                    |
                  |                    |
               +--+--+--+--+--+        |
               |     L        M        |
               |                       |
      +--+--+--+--+--+--+     +--+--+--+--+--+
      H              |  I     |  J        K  |
                     |        |              |
            +--+--+--+--+--+  |     +--+--+--+--+--+
            E              F  |     G              |
                              |                    |
                  +--+--+--+--+--+  +--+--+--+--+--+--+
                  A              B  C                 D
    

    The rules for this kind of puzzle are: (1) The weights on either side of a given pivot point must be equal, when weighted by the distance from the pivot, and (2) a bar hanging beneath another contributes it's total weight as through it were a single weight.  For instance, the bar on the bottom right must have 5*C=D, and the one above it must have 3*G=2*(C+D).

    A First Solution

    Here's what I tried first.  Note that it's not really much different than a bunch of for loops with an if statement inside:

    using System;
    using System.Linq;
    
    class WeighsAndMeans
    {
      static void Main(string[] args)
      {
        var solveForWeights =
          from a in Enumerable.Range(1, 13)
          from b in Enumerable.Range(1, 13)
          from c in Enumerable.Range(1, 13)
          from d in Enumerable.Range(1, 13)
          from e in Enumerable.Range(1, 13)
          from f in Enumerable.Range(1, 13) 
          from g in Enumerable.Range(1, 13)
          from h in Enumerable.Range(1, 13)
          from i in Enumerable.Range(1, 13) 
          from j in Enumerable.Range(1, 13)
          from k in Enumerable.Range(1, 13) 
          from l in Enumerable.Range(1, 13)
          from m in Enumerable.Range(1, 13) 
          where (4 * a == b)
             && (5 * c == d)
             && (3 * e == 2 * f)
             && (3 * g == 2 * (c + d))
             && (3 * (a + b) + 2 * j == k + 2 * (g + c + d))
             && (3 * h == 2 * (e + f) + 3 * i)
             && ((h + i + e + f) == l + 4 * m)
             && (4 * (l + m + h + i + e + f) == 3 * (j + k + g + a + b + c + d))
          select new { a, b, c, d, e, f, g, h, i, j, k, l, m, 
    Total = a + b + c + d + e + f + g + h + i + j + k + l + m };
    solveForWeights.ToList().ForEach(result => Console.WriteLine(result)); } }

    A More Efficient Solution

    Part way through writing the code above, I recognized that it wasn't going to be very fast.  It's not too hard to see that it'll execute the body of the where clause 13^13 times.  That's more than 300 trillion times!  Turns out this is exactly what join can help with, and in contrast to the for loop case, it's pretty easy to turn the query above into one which uses joins.  The following code solves the puzzle right away:

    using System;
    using System.Linq;
    
    class WeighsAndMeans
    {
      static void Main(string[] args)
      {
        var solveForWeights =
          from a in Enumerable.Range(1, 13)
          join b in Enumerable.Range(1, 13) on 4 * a equals b
          from c in Enumerable.Range(1, 13)
          join d in Enumerable.Range(1, 13) on 5 * c equals d
          from e in Enumerable.Range(1, 13)
          join f in Enumerable.Range(1, 13) on 3 * e equals 2 * f
          join g in Enumerable.Range(1, 13) on 2 * (c + d) equals 3 * g
          from h in Enumerable.Range(1, 13)
          join i in Enumerable.Range(1, 13) on 3 * h - 2 * (e + f) equals 3 * i
          from j in Enumerable.Range(1, 13)
          join k in Enumerable.Range(1, 13) on 3 * (a + b) + 2 * j - 2 * (g + c + d) equals k
          from l in Enumerable.Range(1, 13)
          join m in Enumerable.Range(1, 13) on (h + i + e + f) - l equals 4 * m
          where (4 * (l + m + h + i + e + f) == 3 * (j + k + g + a + b + c + d))
          select new { a, b, c, d, e, f, g, h, i, j, k, l, m, 
    Total = a + b + c + d + e + f + g + h + i + j + k + l + m }; solveForWeights.ToList().ForEach(result => Console.WriteLine(result)); } }

    Conclusion

    It turns out this is an example of using LINQ to solve integer constraints problems.  In the general case, special purpose libraries built to solve these problems are almost certainly more efficient, but the LINQ example using joins is sufficiently quick at least for this case.  More importantly, the LINQ solution is not too hard to arrive at, and doesn't require knowledge of some special purpose Integer Programming framework.  I see this as an example of one of the great benefits of LINQ - that I can do all sorts of query and transformation in C# without resorting to special purpose frameworks for each different domain I need to work with.

    kick it on DotNetKicks.com

Page 1 of 1 (3 items)