Why Cast?

Last week I was writing some C code, and as is often the case in C, I started getting frustrated with the language and thinking about how it could be better. This time my thoughts were on casting.

The problem started when I encountered some code where a function needed to be passed a pointer to a const value, but the data available was in the form const volatile. Declaring a variable as const volatile simply means that it it can change (volatile), but you cannot change it (const). It is useful for embedded microcontrollers, where there are cases where values stored in program flash ROM (const) that can actually be changed and so shouldn't really be taken as "never changing", but instead should be reread from program flash every time it is accessed.

But that is beside the point. The point is that I have to cast something like this:

const MyAwesomeType* myAwsomeVariable = 
    (const MyAwesomeType*)myOtherVariable;

myFunction(myAwsomeVariable);

One of my coworkers would never have used const for the function, and would just write it like this:

myFunc((void*)myVar);

Certainly the latter is more readable and bit more compact, which is valuable. On the other hand, the former is more explicit and more type safe, which is also valuable. In this example I also tried to show a difference in naming convention - I prefer more explicit names, which makes lines of code harder to read, but individual variables easier to understand, while my coworker prefers shorter variable names which make the syntax of a line more readable. There is value in both approaches and the choice is purely a choice of style and philosophy, but I'm sure you can see there's a similarity in the reasoning behind the choices of variable names and more explicit types.

But why?

Initially I was debating about which approach is better - to be more explicit or more compact - but then my thoughts turned to "why do I have to cast at all?". I would say there are generally two reasons to explicitly cast:

• Either I know the type beyond what the compiler knows and therefore need to persuade it that the type is correct,
• Or I intend to convert the value to a type that it isn't currently

These are really very different things, and I'm only really going to talk about the first case. In the latter case of converting the type, the type-casting syntax is really just a syntactic convenience for what could have been done with intrinsic functions.

Casting, in the latter case, is used to persuade the compiler to treat some data as a type that the compiler doesn't otherwise think the data is. In the particular example of casting volatile const to const, we are persuading the compiler that for the purposes of myAwsomeVariable, we don't need to think about the data as volatile. Of course this is a complete lie! Either the data is volatile or it isn't. If it isn't volatile, then why was it declared that way? And if it is volatile, then why is it legal to say it isn't? The code could introduce a subtle bug: the developer of myFunction assumes that the data doesn't change, while clearly there is some good reason that we need to be able to change it. In short:

There is a conflict of expectations between the caller and callee, for which the compiler nicely produces a type error, but which we suppress with a type cast and thus introduce a subtle bug

When I say "introduces a subtle bug", I'm not being strictly truthful. There is no bug introduced in the code, because I've seen the functions myself and I know that the value won't change for the duration of the function call. But this does emphasize my point: I needed to look at the code on both sides of the function call to know that it's safe. This is bad. I need to know that myFunction doesn't cache the value across multiple calls (thinking it's constant and persistent), and I need to know that the caller doesn't change the value during the call (a threading race-condition), or during repeated calls (if myFunction also expects the value to be persistent across a longer time). The cast introduces one more piece of information that needs to be manually tracked throughout the program, coupling one part to another. In an ideal world, however, the function declaration should be enough to define the contract between the caller and the callee, when it comes to type consistency. Casting is an explicit breach of this contract, and so should never be allowed by the referee (the compiler).

Note that this situation isn't unique to const or volatile, of course. The same thing happens in C all the time with other type casts. It happens where we know the type of something that the compiler doesn't, or we want to keep track of the "type" of something ourselves and not give it to the compiler because it's too stupid to let us do what we want with it.

Another simple example might be a C container type, for which one implementation would be for it to contain void*-typed items because C doesn't have templates or generics. Once again we know more about the data than the compiler: we know what type of objects the container holds. And once again we have to perform casts to persuade the compiler of what we know. And once again, different parts of the program are coupled together by our special knowledge. That is, we have to keep track in our minds (or in the comments), so that the part that puts items into the container only puts in items that the other part of the program can take out. And once again this opens up a huge gaping whole for bugs to creep in.

What I'm saying is this: casting is not feature of the language, it's a code-smell that says that either your code is badly designed, or that the language is conceding defeat and needs to give you a kludge because its type system has failed you.

So, whats the solution?

I think the obvious solution is add more power to the type system. In the end, the compiler should know almost as much as we do about the code, so that if a cast is actually valid then it isn't necessary. That is, if it's valid to cast from volatile const to const, then the compiler already knew that it wasn't volatile at that point of the program so we don't need to cast it.

This is what happens with generics in C# - if we read an item from a List<int>, then the compiler already knows that it's valid to cast the item to int, so a cast becomes redundant. That is, the item already is an int, so there's no point in casting it. Indeed in C# I find that I never need casts (except for integer conversions which aren't the same thing). When I find myself needing a cast, its generally because I've done something wrong with the design - I've coded something that needs to act generically, but without writing generic code.

You might be wondering how generics could possibly help in the example of const volatile above. Well, it wouldn't be sufficient for C to have generics like C# (although it would certainly help). C++ templates are half a solution, but they have many shortfalls, which I won't go into right now.

What would such a type system look like? Well if there was an obvious answer to that then C would probably already have it. Computer science research is constantly improving the situation at a theoretical level, and I think soon we'll have the perfect low-level type system, just in time to not need it anymore.

Aren't Subtype and Parametric Polymorphism the Same?

There are apparently two common types of polymorphism in software: subtype polymorphism and parametric polymorphism. I think that these are really the same thing, and I can't any good reason why modern languages separate the two. I'm going to explain my reasoning in this post.

Firstly, what are the claimed differences between the two? Well, I'm going to demonstrate by an example. Lets say we have an abstract type, IPet, which has two implementations, Cat and Mouse, each of which implements the IPet's Stroke function (I'm using C# for the examples):

interface IPet 
{
    void Stroke();
}

class Cat : IPet
{
    void Stroke() { Console.WriteLine("Purr"); }
}

class Mouse : IPet
{
    void Stroke() { Console.WriteLine("Squeak"); }
}

Now lets say we want a function to repeatedly stroke a pet a given number of times, but abstracted from what type of pet it actually is. We can implement this using subtype polymorphism:

void StrokePet1(IPet pet, int count)
{
    for (int i = 0; i < count; i++)
        pet.stroke();
}

And here is the implementation using parametric polymorphism:

void StrokePet2<T>(T pet, int count) where T: IPet
{
    for (int i = 0; i < count; i++)
        pet.stroke();
}

So what's the difference? Well in terms of the implementation of StrokePet1 and StrokePet2 I see no difference. Both function implementations read like this:

Given a pet of any type:
    Loop count times:
        Stroke the pet

Well, in C# there is a nontrivial difference. Particularly in the way you call the function. With parametric polymorphism, you need to know the type T upfront when you call StrokePet2, otherwise it degenerates into subtype polymorphism. The same thing applies generally. For example, when you declare a List<T>, T needs to be known upfront when the declaration is made (or it needs to be a type parameter in itself).

There is another difference in C#: the parametric type T can be used in multiple locations to ensure that each declaration has the same type. Consider we have a function that evaluates two pets of the same species, and returns the "winner" (by some unknown criteria):

T ChooseWinner<T>(T left, T right) where T: IPet;

And now lets try implement this using subtype polymorphism:

IPet ChooseWinner(IPet left, IPet right);

Oh dear.. there's no way to specify that left is the same pet type as right or the return type. This is the same problem we would have with using non-generic container classes: there's no way to specify at compile time that some abstract queue should only contain elements of a certain type:

// This queue is supposed to only contain IPets, but how do we specify it?
Queue myQueue = new Queue(); 

myQueue.Enqueue(new Mouse());
myQueue.Enqueue(new Cat());
myQueue.Enqueue(new object); // Ooops. Why can't the compiler catch this? 

IPet first = myQueue.Dequeue(); // why won't it allow this?

So wait, I'm saying they're actually different? No. I'm saying that in C#, subtyping polymorphism is just parametric polymorphism but with less static information.

I don't think this is a shortcoming of subtype polymorphism - it's a shortcoming of the language to not be allow us to fully express the relationships between between types used in an class or function. There's no way to specify that a C# Queue container has to be homogeneous without using generics, but that just means that C# subtyping polymorphism isn't as expressive as its parametric polymorphism. Conversely, parametric polymorphism in C# is more strict because we need to supply more static information. Consider the following:

Queue<IPet> myQueue = new Queue<IPet>();

// Here myPet is a mouse, but we haven't told the compiler it must be
object myPet = new Mouse();

myQueue.Enqueue(myPet); // Why won't it allow this?

So really, it's all about the balance between information we keep in our heads vs information we give to the compiler for static type checking.

So What?

What's the point? Does anyone care that there may be some airy-fairy overarching concept that ties parametric and subtype polymorphism? I would say yes, and the reason is about code re-usability and performance.

Regarding performance, in C# there is a difference in the performance of using each type of polymorphism. In the case of parametric polymorphism, the underlying code can be specialized for the provided type argument, making it more efficient. For example, a List<int> will perform much better than a List<object> whose elements are ints. Lets say we have an INumber interface, (like Javas Number class). Should we really have to decide between the following two implementations:

INumber Add(INumber first, INumber second)
{
    return first + second;
}

TResult Add<TFirst,TSecond,TResult>(TFirst first, TSecond second)
    where TFirst: INumber
    where TSecond: INumber
    where TResult: INumber
{
    return first + second;
}

This seems like the sort of thing the compiler should sort out, akin to inline optimization there should be specialization optimization. Inlining of functions involves taking their parameters and substituting concrete arguments to specialize it for a specific call site - sound familiar?

Regarding reusability, note that functions with generic parameters are not interchangeable with functions that have virtual parameters, and so to some extent the designer of a function or class needs to think ahead about how much of it to make generic. But why? Why can't the language make generics seamless: the coder should specify exactly the required details for the code, and no more. Everything else should just be "generic" by default. Need a number variable...? Just use INumber, not int or short. The compiler can "inline" (specialize) specific types as they become known. Whether the compiler generates an actual abstract object with dynamic dispatching at runtime, or just specializes the code to the concrete type, should just an optimization issue and not the concern of the programmer.

As a side note, there are languages which make generics much less invasive. For example, F# is a language where I think it really is feasible to make all code generic (except at the root). But I think we need this capability in more popular OOP languages like C# and Java.

In conclusion, I think that parametric and subtype polymorphism are actually the same thing in a statically typed language. In terms of program operation, subtype polymorphism is just like a parametric polymorphism that's missing a few static features. Popular modern languages should use this make it easier to write reusable, high-performance code.