Array Typing Problem in C# (and Java)

In this article, I am going to take a look at array typing problem in C# (and Java).

Before we delve into the details of array typing, let’s look at how we declare an array in C#. An array of T elements is written in T[]. For example, you can declare an array of string as in the following:

string[] strs = new string[] { "hello", "world" };

We can pass this string array around to methods which take an argument of type string[]. For example, we call call Sort method to sort the given strings lexicographically.

static void Sort(string[] strs)
{
   // ...
}

But what if we also want to sort an array of ints? Then we need to create an overloaded method which takes an argument of type int[].

static void Sort(int[] ints)
{
   // ...
}

This code smells bad because we duplicate the exact same code except for the argument type. Of course, we have generics (aka, parametric polymorphism) to solve this problem! However, back in the days before C# 2 or Java 5, there was no generics available and the language designers (James Gosling and Anders Hejlsberg) must solve the problem without generics.

Their choice is to make the array type covariant on its element type. To put it another way, S[] is a subtype of T[] if S is a subtype of T. So string[] is a subtype of object[] because string is a subtype of object. This seems to solve the problem nicely because now we can pass an array of string to a method which takes an argument of type object[]. We don’t redundantly need to duplicate the same code for each argument type.

static void Sort(object[] objs)
{
   // ...
}

string[] strs = new string[] { "hello", "world" };
Sort(strs);

Mission completed? No, there is no free lunch in the world. What about the following code?

static void BadMethod(object[] objs)
{
   objs[0] = new object();
}

string[] strs = new string[] { "hello", "world" };
BadMethod(strs);

Create a console application and try this by yourself. Calling BadMethod with strs throws a System.ArrayTypeMismatchException because C# can’t assign an object instance to an array of strings. This is an example of Liskov substitution principle violation. string[] is a subtype of object[], but it behaves unexpectedly when used where object[] is required.

Fortunately, this at least does not violate the security of .NET runtime. We can’t compromise the runtime by disguising the actual element type. However, we no longer can trust that C# compiler will prevent this kind of problem. By making the array type covariant on its element type, we lost static type safety.

Because C# 2 and Java 5 introduced generics to the languages, we have generics in our hands. So technically we no longer need to make this kind of compromise. However, we can’t fix it now because the change will break the backward compatibility. It’s too late.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s