Togaroga

In What’s in a name? (C#’s hidden support for structural typing) we explored a few of the areas in which C# currently supports structural typing. I would like to propose two new additions to C#’s structural typing abilities: implicit interface inheritance and richer generic constraints.

Implicit interface inheritance

I propose that class or struct ought to be able to implicitly inherit from an interface if the two are structurally equivalent in every way. The idea is that if a type has all the members of an interface it can claim implicit inheritance of that interface making examples like this legal:

using System;
using System.Collections;

interface IName
{
    String Name { get; }
}
class Example
{
    static void Main()
    {
        printName(new { Name = "Nic" });
    }
    static void printName(IName name)
    {
        Console.WriteLine(name.Name);
    }
}

Allowing any type to implicitly implement an interface would open many opportunities. First, it would encourage the use of anonymous types for message passing between methods thereby avoiding the need to declare a type.

Second, now the fact that interfaces would offer even more flexibility, developers would be encouraged to choose interfaces for their method parameter types (i.e. program to an interface).

Richer generic constraints

Currently, C# only supports new() as a generic constraint for type constructors. This constrains the type parameter to only those types that have parameterless constructors. This means that if you want to instantiate an instance of a generic type argument you are forced to use reflection to do so:

using System;

class Foo
{
    public Foo() { }
    public Foo(String name) { }
}
class Example
{
    static void Main()
    {
        Foo f = create<Foo>();
    }
    static T create<T>() where T : new()
    {
        Object instance 
            = Activator.CreateInstance(typeof(T), 
                                       new[] { "Foo" });
        return (T)instance;
    }
}

While Activator.CreateInstance is a very useful method, it does use reflection and any incompatibility between the constructor of the type and the arguments passed to it will cause an exception to be thrown. I propose that C# incorporate a new type of generic constraint for constructors that allow developers to specify the signature of the constructor like this:

using System;

class Foo
{
    public Foo() { }
    public Foo(String name) { }
}
class Example
{
    static void Main()
    {
        Foo f = create<Foo>();
    }
    static T create<T>()
        where T : new(String)
    {
        return new T("Foo");
    }
}

If the generic type argument has a constructor that matches the structure of the generic type constraint it should satisfy the constraint. This will allow richer generic programming as we will be able to instantiate many different types of objects without sacrificing type-safety.

So what do you think? Are there other areas that C# could implement structural typing that would be beneficial?

Each time you write a parametrized method you must decide which are the best types to use for your parameters. If you are not careful, your choice could place unnecessary restrictions on the caller of the method that requires them to pass too specific of a type. When you are making this decision you should ask yourself the following question:

Is there an interface that encapsulates all the members that I need for the type of this parameter?

Here is the classic example of this problem:

class Example
{
    public void Print(List<String> values)
    {
        foreach (String value in values)
            Console.WriteLine(value);
    }
}

This Print method was not written with the caller in mind – these kinds of methods are often written with a narrow focus on the needs of the developer who wrote the method. This developer is used to using a List<T> for any sequence of items so he naturally chooses it as his parameter type for this method. But is it the right choice?

Since this article is about choosing interfaces I imagine that you rightly guessed not. In order to choose the correct type for the argument you need to first find the least restrictive type you can that will allow you to accomplish everything you need to do to satisfy the requirements of the method.

Here is the process for finding the best type for your parameter. Start by looking at the implementation of the type you want to use. List the methods and properties you use from it. Next determine if it implement any interfaces. If it does, does any one interface provide all the members your method needs to function? If so, repeat this exercise but this time look at the implementation of the interface you have chosen. Does it inherit from another interface? Is it that interface that actually provides the members you need? Keep doing this until you have reached the highest level of abstraction that you can. Once you cannot go any further you have found the right type for your parameter.

In the case that your type does not implement any interfaces or the interfaces it does implement cannot be used as the parameter type (in other words the exercise in the previous paragraph failed) you will have to rely on a concrete type for your parameter. At this point you must repeat the exercise but do so using the inheritance hierarchy of types above your type.

After you have completed this exercise you can be confident that you have chosen the most abstract choice possible for your parameter and therefore you are providing maximum flexibility for the callers of your method.

Let’s apply this process to a new method that removes all instances of “1″ from the Text property of an ASP.NET textbox:

void removeOnes(TextBox textbox)
{
    textbox.Text 
        = textbox.Text.Replace("1", "");
}

Here is the mental process that I would go through to choose the proper type for this method:

• This removeOnes method uses just one member from TextBox and that is TextBox.Text.
• TextBox implements two interfaces: IPostBackDataHandler and IEditableTextControl.
• Does any one interface provide all the members your method needs to function? Yes, IEditableTextControl declares a Text property.
• Does IEditableTextControl inherit from any other interface and if so does that interface provide a Text property? Yes, IEditableTextControl inherits from ITextControl which does provide a Text property.
• Does ITextControl inherit from any other interface and if so does that interface provide a Text property? No, this is as far as we can go.

We have just found the most abstract interface that we can possibly use and that means that it is the best type to use for our parameter:

void removeOnes(ITextControl textControl)
{
    textControl.Text 
        = textControl.Text.Replace("1", "");
}

Now that we have changed the type of the parameter to ITextControl we have now given much more flexibility to the caller of this method. We have also improved the reusability of this method since it can now be used for any control that implements the ITextControl interface (e.g. TextBox, Label, Literal and many more).

Can anyone tell me what type should have been used for the first example? What if the implementation of the first example changed a bit (as I am sure that everyone was able to quickly identify the proper type for the first example).

public void Print(List values)
{
    for (Int32 i = 0; i < values.Count; i++)
        Console.WriteLine(values[i]);
}

Can you list what members of List<T> are being used by Print now? With that in mind, what type would you choose for values?

In part 1 of this series I explained the difference between reference equality and value equality. In this article I am going to demonstrate how to compare two reference types using value equality semantics.

Override Object.Equals

Every time you use the binary equality operator (==) or the Equals method on a reference type you are invoking Object.Equals for the instances in question. If you wish to provide value equality the most obvious thing to do would be to override System.Object.Equals and use this method to compare the fields of your two instances. Let us begin by revisiting our Person type which I have refactored to make these examples a bit more interesting:

class Person
{
    public String Name { get; set; }
    public DateTime Birthday { get; set; }
}

We have a class with two properties – let’s override the Equals method:

class Person
{
    public String Name { get; set; }
    public DateTime Birthday { get; set; }

    public override Boolean Equals(Object obj)
    {
        Person other = (Person)obj;
        return this.Name == other.Name
            && this.Birthday == other.Birthday;
    }
}

Now we have value equality for our reference type. While this is a simple solution, it is not ideal for the following reasons:

1. This approach is not type safe. Since the Equals method accepts an argument of type Object we cannot guarantee that the instance that was passed to this method is actually a Person.

   somePerson.equals("hello, world");  // throws an InvalidCastException

2. This approach is not “null safe”. Any comparisons with null will throw a NullReferenceException.

   somePerson.equals(null); // throws a NullReferenceException

The null safety issue is easy enough to fix:

public override Boolean Equals(Object obj)
{
    if (obj == null)
        return false;

    Person other = (Person)obj;
    return this.Name == other.Name
        && this.Birthday == other.Birthday;
}

But how do we preserve type safety? Meet the IEquatable<T> interface.

IEquatable<T>

This interface was designed specifically to help us tackle the type safety issue that we are facing. It declares a single member:

public interface IEquatable<T>
{
    Bolean Equals(T other);
}

As you can see, this interface gives us the ability to create a strongly-typed override of our existing Equals method. Implement the interface like this:

class Person : IEquatable<Person>
{
    public String Name { get; set; }
    public DateTime Birthday { get; set; }

    public override Boolean Equals(Object obj)
    {
        return this.Equals(obj as Person);
    }
    public Boolean Equals(Person other)
    {
        if (other == null)
            return false;

        return this.Name == other.Name
            && this.Birthday == other.Birthday;
    }
}

Now that we have a strongly-typed Equals method any equality comparisons that are done on two instances of our type will be type-safe and null-safe. Using the as cast in the default overridden implementation of Equals allows us to pass either an instance of Person or null and our implementation of IEquatable<T>.Equals returns false which ensures that our methods won’t fail for null (for more information on the as operator, please read Two casts are not better than one).

GetHashCode

I am not going to cover the GetHashCode method in depth but it is an essential part of identity equality checks. A hash code is an integral value that represents the state of the current instance. Basically, if two instances have the same hash code, they may be equal in terms of value. But if two objects do not have the same hash code they are most certainly not equal in terms of value. This method allows our calling code a performance boost by not having to call Equals in the event that the hash codes do not match.

As for the proper or best way to generate a hash code for an object instance, that is a discussion for another day. For now I will add a simple GetHashCode implementation to our example to complete the exercise. (Thank you to Jon Skeet for this particular implementation of GetHashCode.)

class Person : IEquatable<Person>
{
    public String Name { get; set; }
    public DateTime Birthday { get; set; }

    public override Boolean Equals(Object obj)
    {
        return this.Equals(obj as Person);
    }
    public Boolean Equals(Person other)
    {
        if (other == null)
            return false;

        return this.Name == other.Name
            && this.Birthday == other.Birthday;
    }
    public override Int32 GetHashCode()
    {
        Int32 hash = 23;
        hash = hash * 37 + this.Name.GetHashCode();
        hash = hash * 37 + this.Birthday.GetHashCode();
        return hash;
    }
}

All we are doing here is taking two coprime numbers (23 and 37) and using them to manipulate the hash codes of our instance’s state in order to arrive at a final integral value. Again, how the implementation works is not important at this point, what is important is that we are providing some implementation so that we can reap the performance benefits that GetHashCode can provide. I will post an article in the future that discusses the different techniques of generating hash codes and why some implementations are better than others.

Conclusion

Now we have a class that properly provides value equality semantics. I hope I have showed not only how to implement this pattern in your code but also why it is important and necessary in the first place.

Edit: Bradley Grainger correctly points out in a comment below that I have neglected to provide equality operator overloads for my Person type! Here is a complete example that includes those operator overloads:

class Person : IEquatable<Person>
{
    public String Name { get; set; }
    public DateTime Birthday { get; set; }

    public override Boolean Equals(Object obj)
    {
        return this.Equals(obj as Person);
    }
    public Boolean Equals(Person other)
    {
        if (other == null)
            return false;

        return this.Name == other.Name
            && this.Birthday == other.Birthday;
    }
    public override Int32 GetHashCode()
    {
        Int32 hash = 23;
        hash = hash * 37 + this.Name.GetHashCode();
        hash = hash * 37 + this.Birthday.GetHashCode();
        return hash;
    }
    public static Boolean operator ==(Person left, Person right)
    {
         // If the object's have the same reference then they are most
         // certainly equal - return true here.
        if (Object.ReferenceEquals(left, right))
            return true;

        // Check for null here as well - make sure you cast the references
        // to Object so that you don't accidentally invoke this same operator
        // again.  Casting to Object allows you to invoke Object's == operator.
        if ((Object)left == null || (Object)right == null)
            return false;

        return left.Equals(right);
    }
    public static Boolean operator !=(Person left, Person right)
    {
        return !(left == right);
    }
}

Here is a new addition to the C# language in version 4 that doesn’t seem to be getting much attention. The type inference algorithm has become smarter and for the first time we are able to infer generic type arguments from the return types of methods in certain cases.

Consider this example that compiles in C# 4 but does not compile in C# 3:

using System;
using System.Linq;

class Example
{
    static void Main()
    {
        var characters 
            = new [] { 97, 98, 99 }
                .Select(Convert.ToChar);
    }
}

Here I am converting an array of integers to a new sequence of characters. In order to do this I chose to project this new sequence from the old sequence using LINQ’s Enumerable.Select<TSource,TResult> extension method. Now if I were using C# 3 I would have to explicitly provide type arguments for the Select method since the compiler would be unable to infer the types from the usage alone.

Note: This was a follow-up to You don’t always need a lambda expression. As you can see this new functionality gives us many more opportunities to forgo a lambda expression since we are no longer limited to Action delegates.

Here is a bit of a quiz: What does this program print?

using System;
using System.Collections.Generic;

class Person
{
    public String Name { get; set; }
}

class Example
{
    static void Main()
    {
        var people = new List<Person> { 
            new Person { Name = "George Washington" } };

        Console.WriteLine(
            people.Contains(
                new Person { Name = "George Washington" }));
    }
}

If you said “True” then unfortunately you would be incorrect – this program prints “False”. Before I explain why this program prints “False” I would like to make one slight change to this program to make it print “True”.

using System;
using System.Collections.Generic;

struct Person
{
    public String Name { get; set; }
}

class Example
{
    static void Main()
    {
        var people = new List<Person> { 
            new Person { Name = "George Washington" } };

        Console.WriteLine(
            people.Contains(
                new Person { Name = "George Washington" }));
    }
}

Did you spot it?

If you look carefully you will notice that I changed the Person type to be a struct instead of a class. Why would this make a difference? In order to understand let’s take a brief tour of how C# (and the CLR) handle equality.

Whenever you create a type without overriding the Equals method or implementing the IEquatable<T> interface you relinquish control over how two instances of your type will be compared and accept the CLR’s default comparison mechanisms. If your type is a reference type (a class) you will get identity equality and if your type is a value type (a struct) you will get value equality.

Identity equality

Reference types are called reference types because the object itself is stored on the managed heap and you access that object via a reference to that object.

When you compare two instances of a reference type (like the Person type in my first example) the CLR will compare the references to the objects to see if the references point to the same object. Two reference types will only be equal if their reference point to the exact same object on the managed heap. If the references are different the objects are not equal then neither are the objects – even if their fields are identical.

Identity equality asks this question:

Do these two references point to the same object on the managed heap?

Value equality

Value equality is a different process but is actually much simpler to understand. Value equality takes all instance fields of a value type and compares them to the instance fields of a second instance in respective order. I would imagine that value equality works much the way most developers expect all equality checks ought to.

Value equality asks this question:

For each field in these two instances, are all the values equal?

So does this mean that in order to have value equality we must use value types? Of course not! I will soon publish a follow-up article explaining the proper way to implement value equality semantics with reference types.

Edit: Here is the follow-up article: All types are not compared equally (part 2).