General musings on programming languages, and Java.

Friday, January 16, 2009

Victor James Clarkson De Luca, Version 1.0

After 9 months of hard work and alcohol avoidance, Josefina and I are proud to announce that we have managed a stable release of Victor James Clarkson De Luca. Version 1.0 was released on January 5th 2009, before you got to work.

There are no known bugs, as yet. Here's a screenshot:

Friday, January 02, 2009

The Typeclass Pattern

The Typeclass Pattern

This pattern applies to C# and Java, and possibly some other typed languages. It doesn't apply to C++, which does generics via templates.

A simple problem to demonstrate it with is a generic Pythagoras method that takes two numbers a and b and computes sqrt(a * a + b * b) for them. In both C# and Java this can't be written in the most straightforward way:

public T Pythagoras<T>(T a, T b)
{
    return Math.sqrt(a * a + b * b);
}
There's more than one reason, but the 'innermost' is that T doesn't have the operator *, and there's no way to restrict T so that it does.

The equivalent C++ will work, because C++ generates code rather than using constraints.

So the missing information in Pythagoras is:

   * How to multiply two Ts. (let's assume T * T gives T)

   * How to add two Ts. (let's assume T + T gives T)

   * How to find the square root of a T.


interface Num<T>
{
    T Add(T one, T two);
    T Multiply(T one, T two);
    T Sqrt(T t);
}
Now Pythagoras can be written with an extra parameter, a Num:
public T Pythagoras<T>(T a, T b, Num<T> num)
{
    return num.Sqrt(num.Add(num.Multiply(a, a), num.Multiply(b, b)));
}
Clearly, some language support wouldn't go amiss for this, at least in the arithmetic case. What's more of a problem is that your method gets a 'surprising' extra parameter, the Num. It's one of those things that makes sense in isolation, but is really an unnecessary detail when reading the code to gain an understanding of it. Scala offers an interesting solution to that.

In Scala, you might write Pythagoras as:

def pythagoras[T](a: T, b: T)(implicit num: Num[T]) = num.sqrt(num.add(num.multiply(a, a), num.multiply(b, b)))
Then calling it would look like:
pythagoras(3, 5)
The second parameter list for pythagoras is an 'implicit' parameter list, meaning that in compilation the compiler looks for a Num[T] in scope that it can use for num. You can specify it explicitly, e.g., pythagoras(3, 5)(Num.integer), or you can just import Num.integer at some point.

As with all patterns, though, all it takes is a language to support it directly, and then the pattern disappears from user code. In Haskell, Num is a built in type class and Int, Double, etc. are types that are instances, or members, of Num. +, -, *, / are defined as methods that are part of the Num typeclass. Let's omit the sqrt part for a moment:

Prelude> let pythagorasSquared a b = a * a + b * b
Prelude> pythagorasSquared 3 4
25
Prelude> :type pythagorasSquared
pythagorasSquared :: (Num t) => t -> t -> t
I hope the first two commands I gave to the Haskell interpreter are self-explanatory. The third asks what type pythagorasSquared is. That's like asking what signature a method has.

pythagorasSquared is a function with one type parameter called t. t is an instance, or member, of the Num type class. pythagorasSquared takes two values of this type t, and returns a value of the same type. E.g., given two Doubles it will yield a Double. This usually works internally by passing around a Num implicitly, like in the Scala solution, but can work quite like the C++ code generation way, depending entirely on the compiler.

The reason that I omitted the sqrt is that in Haskell, sqrt is defined on Floating, another type class, rather than Num (giving the sqrt of an Int as an Int is perhaps not useful).

At some point, some readers will have stopped understanding the terms, but if you grasped the concept, this wasn't a waste of time!

Blog Archive

About Me

A salsa dancing, DJing programmer from Manchester, England.