August, 2008

  • Kirill Osenkov

    How I started to really understand generics

    • 16 Comments

    First off, a little explanation for the post title: not that I didn't understand generics before. I'd had a pretty good understanding of how they work, how they are implemented in the CLR, what facilities are provided by the compiler, etc.

    It's just that recently I started seeing some patterns and analogies that I hadn't seen before or just didn't pay enough attention to. This is a little fuzzy feeling but I'll still try and describe these insights, hopefully the reader will understand what I mean. These insights have helped me to think more clearly and have a better understanding of how to use generics in a richer way.

    For a start, let's consider a method called Process that processes command line arguments and modifies the argument list by removing the arguments that it could process:

    public ArgumentList Process(ArgumentList source)
    {
    
    }

    This design is not very good because it mutates the source variable, and I read somewhere that a method should either be immutable and return something or mutate stuff and return void, but not both at the same time. I think it was in Martin Fowler's Refactoring, but I'm not sure.

    But that's not the thing I wanted to talk about today. This design has another serious flaw: it essentially truncates its return type to be ArgumentList, so by calling this method we basically "seal" the output type to be ArgumentList:

    CustomArgumentList customList = new CustomArgumentList();
    ArgumentList processed = Process(customList);

    Even if we originally had a CustomArgumentList, once we pass it into our method, it "truncates" the type and all we have left on the output is the basic ArgumentList. We lose some type information and cannot enjoy the benefits of static typing and polymorphism at its fullest.

    So what have generics to do with all this? Well, generics allow us to "unseal" the return type of our method and to preserve the full static type information available:

    public T Process<T>(T source)
        where T : ArgumentList
    {
    }

    This way we can call Process on our CustomArgumentList and receive a CustomArgumentList back:

    CustomArgumentList customList = new CustomArgumentList();
    CustomArgumentList processed = Process(customList);

    See, type information is not sealed anymore and can freely "flow" from the input type to the output type. Generics enabled us to use polymorphism and preserve full static typing where it wasn't possible before. It might be obvious for many of you, but it was a wow-effect discovery for me. Note how we used type inference to make a call to Process<T> look exactly like a call to Process.

    Another observation here is that when you're talking about covariance and contravariance of generics, you can divide type usages into two groups: "in" and "out". Thus, we can have return type covariance and input parameter contravariance. Let's notice how "out" type usages essentially truncate the type information and limit ("seal") it to one base type. Generics are there to "unseal" this limitation and to allow for derived types to be returned without losing type information.

    I hope this wasn't too fuzzy and handwavy. It's just these little discoveries make me very excited and I'd like to share the way I see these things.

    Let's consider another insight: what's the difference between:

    1. class MyType<T> : IEquatable<T> and
    2. class MyType<T> where T: IEquatable<T>

    Update: I'd like to explain in a little bit more detail, what's going on here. In the first line, we're declaring that the type MyType<T> implements the IEquatable<T> interface (complies with the IEquatable<T> contract). Simpler said, MyType<T> is IEquatable<T> (can be compared with objects of type T). The <T> part reads "of T", which means MyType has a method Equals that accepts a parameter of type T. Hence, the first line imposes the constraint on the type MyType<T> itself.

    Now the second line imposes the constraint on the type parameter, not on the type itself. Now the type parameter that you specify must be a type that has an Equals method that accepts a parameter of type T (objects of type T can be compared with other objects of type T). I would imagine second line could be useful more often than the first line.

    Also, another line is possible:

    class MyType<T> : IEquatable<MyType<T>>

    This line would mean that MyType can be compared with itself (and, independently of this fact, use some other type T).

    Thinking about this difference made another aspect of generics clearer for me: with generics, there are always at least two different types involved: the actual type and the generic type parameters.

    Armed with this wisdom, let's move to a third mental exercise (again, it might all be simple and obvious for some readers, in this case I apologize and am very honored to have such readers). Is the following thing valid?

    class MyGenericType<T> : T
    {
    }

    It turns out it's not valid - we cannot inherit from a generic type parameter (Update: in the original post I wrote that this would lead to multiple inheritance - that's not true). This illustrates my previous points - with generics, there are always at least two different types involved, and we shouldn't mix them arbitrarily.

    Finally, to at least partially save this post from being a complete theoretical disaster, I'd like to share some code I wrote recently. Suppose you're implementing the Command design pattern and have various concrete Commands: CutCommand, CopyCommand, CloseAllDocuments command etc. Now the requirement is to support a unified exception throwing and catching functionality - every command should throw a generic exception InvalidOperationException<T>, where T is the type of the command. You might find this weird (who needs generic exceptions?) but in my real project at work we have some very clever exception classification logic, which requires that each exception should have a different type. Basically, each exception should know what type threw it. Based on this strongly typed exception source information, we do some magic to greatly simplify logging and classify exceptions into buckets based on their root cause. Anyway, here's the source code:

    class Command
    {
        public virtual void Execute() { }
    }
    
    class InvalidOperationException<T> : InvalidOperationException
        where T : Command
    {
        public InvalidOperationException(string message) : base(message) { }
        // some specific information about
        // the command type T that threw this exception
    }
    
    static class CommandExtensions
    {
        public static void ThrowInvalidOperationException<TCommand>(
            this TCommand command, string message) 
            where TCommand : Command
        {
            throw new InvalidOperationException<TCommand>(message);
        }
    }
    
    class CopyCommand : Command
    {
        public override void Execute()
        {
            // after something went wrong:
            this.ThrowInvalidOperationException("Something went wrong");
        }
    }
    
    class CutCommand : Command
    {
        public override void Execute()
        {
            // after something went wrong:
            this.ThrowInvalidOperationException("Something else went wrong");
        }
    }

    Note how two seemingly equal calls to ThrowInvalidOperationException will, in fact, throw different exceptions. The call in CopyCommand will throw an InvalidOperationException<CopyCommand>:

    image

    while the same call from CutCommand will throw an InvalidOperationException<CutCommand>:

    image

    Here (attention!) we infer the type of the command from the type of the "this" reference. If you try calling it without the "this." part, the compiler will fail to resolve the call:

    image

    So this is a situation where extension methods and generic type inference play nicely together to enable what I think is a very interesting trick. We preserve type information all the way from where an exception is thrown, "remember" the type that threw the exception, and still have full type information available when we catch and process it. A nice example of how generics help type information "flow" from one part of your code to other. This is also in line with my first example where we see how type information "flows" from input to output parameter of a method.

    Note: for those of you who spent some time with Prolog, don't you have a déjà vu of how Prolog allows values to "flow" between predicates? In Prolog every parameter to a predicate (method) can be "in" or "out" - input or output. Prolog infers which parameter is which depending on its usage elsewhere and inside the predicate body. I don't know if this analogy is valid at all, but I feel that C# compiler in a certain way does its type inference in a similar manner.

  • Kirill Osenkov

    Representing dependencies in code

    • 6 Comments

    It is more often than you would suspect that people have to deal with some sort of dependencies in an application they're developing. In this post I'll talk about some common algorithms and data-structures to work with dependencies that might turn out helpful with some real-life programming tasks.

    To better understand what kind of dependencies I'm talking about, let's consider a couple of examples first.

    Example 1: A Spreadsheet Application

    In Excel every cell can contain a formula which depends on other cells:

    image

    Here we have the value in C5 depending on values in B2 and D3. A couple of things to note:

    1. Whenever a value in B2 changes, the value in C5 is recalculated automatically based on the formula.
    2. A cell can have multiple dependencies (i.e. cells that this cell depends upon)
    3. Cells can build dependency chains and trees (whenever a cell is changed, the entire subtree is recalculated)
    4. Cells cannot have circular dependencies. If you try to create a circular dependency, Excel will show a message box and draw a nice blue arrow to indicate a cycle in the dependency graph:
      image

    Example 2: Visual Studio Project System

    If you look at a solution in Visual Studio with multiple projects, those projects will most probably reference other projects. When you build the solution, Visual Studio somehow figures out the correct order in which to build the projects, and always guarantees that all the dependencies are built before it builds any given projects.

    Same things to note here:

    1. Whenever a project changes, VS figures out that its dependent projects will need to be rebuilt during the next build.
    2. A project can reference multiple projects
    3. Projects can build dependency chains and trees
    4. Projects cannot have circular references.

    Example 3: Dynamic Geometry

    In a dynamic geometry application, like the one I'm building as a hobby project, geometric figures depend on other figures during their construction. For instance, you need two points to draw a line - and this line will depend on the two points.

    1. As you move a point, the line will redraw to pass through this point
    2. A figure can depend on multiple figures (a parallel line needs a point and a line to be constructed)
    3. Same as above
    4. Same as above

    Why is this important?

    It is important to be aware of such things as dependencies in your domain model and to be explicit about them in your code. Clearly expressed intent in code is goodness that is incredibly useful for those who write the code, who read the code and who use the code.

    I've seen a case where a program naively relied on the order in which objects were created, and failed to save them if the order was changed. It gave a message box like "Please rearrange your objects because I can't figure out in which order to save them, because they have complex interdependencies". Well, the dependency scheme was exactly like in the three examples above, so the application could very well handle the dependencies itself.

    Can you imagine Visual Studio giving you a message box saying: "Please rearrange the projects in your solution because I can't figure out in what order to build them"? That's why it's important - thinking a little bit about such things can make your code clean, smart, robust and the application easy to use.

    Data structure: DAG (Directed Acyclic Graph)

    A data structure that is commonly used to model such dependencies is called DAG. Wikipedia does a great job describing it, so I will just highlight some points here. First, and foremost, every tree is a DAG:

    image

    But in a tree, a node cannot depend on more than one parent (like single inheritance in C#). In a DAG, a node can very well have more than one parent:

    image

    This "diamond" shape is well known to C++ programmers - multiple inheritance is a great example of a DAG. Wikipedia makes a great point that a DAG "flows" in one direction (there can be no cycles).

    Each node in a DAG has a list of dependencies ("parents") and a list of dependents ("children"):

    interface IDagNode
    {
        IDagNodeList Dependencies { get; }
        IDagNodeList Dependents { get; }
    }

    You don't have to store Dependents as well and recalculate them every time, but storing dependents greatly simplifies many algorithms, and it also makes the data structure symmetric.

    With a tree, you clearly know where's the top (root) and the bottom (leaves). A DAG, on the other hand, is symmetric - it can have many "roots" and many "leaves". Our diamond, for example, has one root (above) and one leaf (below) - but if you draw the arrows in the opposite direction, a root becomes a leaf, and a leaf becomes a root. Officially, a "root" is called a source, and a "leaf" is called a sink.

    Let's try to give some definitions:

    • Node A directly depends on node B if A.Dependencies.Contains(B).
    • Node A depends on node B if A directly depends on B or A directly depends on some C, which in turn depends on B (recursive definition).
    • A node is a source if it doesn't depend on any other node.
    • A node is a sink if no other node depends on it.

    Note that a non-empty DAG always has at least one source and at least one sink. Finding sources and sinks is easy - iterate over all nodes and select those that have their Dependencies/Dependents collection empty.

    Algorithm: Topological Sort

    So what's the use of a data structure if we don't have a useful algorithm that comes with it? Well, it turns out, we do. Every DAG can be linearized (serialized) into a sequence, where a node only depends on nodes that come before it. This special sequence is called topological sort of the DAG.

    Thus, to figure out the build order in which we want our Visual Studio projects to be built, we just take all of our projects and sort them topologically with regard to their references.

    The algorithm is actually pretty simple:

    1. Before visiting a note, check if we have already visited it (e.g. using a hashtable or marking the node) - don't visit it the second time.
    2. For every node that we visit, first visit all the dependencies recursively.
    3. After visiting the children, append the node being visited to the end of the results list.

    After visiting all the nodes, the results list will contain all the nodes sorted topologically.

    In my plane geometry application I use topological sorting to recalculate the coordinates of figures in the correct order - if I recalculate a line before a point is moved, the line will use the points old coordinates and will appear off-base. If you're interested, here's the source code.

    The problem with my implementation is that the algorithm is too tied to the nature of the objects being sorted (figures). In the future, I'll look into making this algorithm generic and reusable in other projects.

    Finally, I'll be interested in any examples of DAGs that you come across. I'm collecting such examples, so I'll be grateful if you tell me about your experiences with DAGs and topological sorting and where you encountered this remarkable data structure.

Page 1 of 1 (2 items)