Stop Sitting On The Type Fence

Static typing is not just about preventing simple bugs, and dynamic typing is not just about writing millions of tests that you wouldn't have to write with static typing.

Programmers of languages like Java, C#, C, C++, etc., middle-of-the-road statically typed languages with some dynamic features, have some intuitions, built up from years of experience at getting the best out of their language, but don't often stop to see what contortions their language makes them go through, or that they are limited in what their compiler tells them about their code.

They often think that rigorous static typing is about preventing bugs that a few unit tests would solve, or that dynamic typing is about writing tests that static typing would solve.

Static Typing is Not About Low-Hanging Bugs

Many years back, clever mathematicians proved that functions express types. If you have an expressive enough type system, you only need to give the input and output types for a function, and you have its implementation. Consider the identity function, written in Scheme like this:

    (lambda (x) x)

Don't worry if lambdas are unfamiliar to you. No, actually, do worry. Lambdas underpin most of computer science and certainly all of programming, even if that's not obvious. If, as I did, you gained a Computer Science degree without ever hearing about lambdas, ask for your money back, and spend it on a copy of The Structure and Interpretation of Computer Programs (SICP) for you, all your friends and family. It's also available in PDF form for no money, in case you're unsuccessful in getting your money back from your University.

Anyway, a lambda expression is analogous to an anonymous function in many languages, and even an anonymous class (with one method) in Java. The particular lambda expression above is a function that takes a value, and returns that same value.

In Haskell, the syntax isn't much different:

    \x -> x

The \ is Haskell's approximation to the Greek letter lambda, the bit before -> is the parameter list, and the bit after it is the result. Scheme doesn't care about telling you the types of things, but Haskell does. The type of \x -> x is t -> t, which means it's a function that takes a t (which can be anything) and returns a t (which is the same as the first t). All fairly obvious.

Given the above, there's only one logical implementation of t -> t, and that's \x -> x. You could make silly ones, where you store x in a local variable, and then return it later, but they're all equivalent. Or perhaps the implementation could look up the type of x, and grab something similarly-typed from a cache. All a bit silly though. Perhaps if all types in a language had a clone function, then you could provide a different implementation, but without that, or something similar,

What you can see from this is that, at least for simple functions, you only need the types to derive the implementation. Does this scale up to things like \x y -> x/y, etc.? Yes, as it happens, though you then need the concept of dependent types, which is types that depend on runtime values. They can still be checked at compile time. In other words, types and values are isomorphic to each other (isomorphic is a mathematical way of saying 'equivalent').

What does the Java version of the identity function look like? Oddly, it depends on whether you write it how Scheme works, or how Haskell works. In Scheme there are no compile time types (or you can say there is exactly one), and the closest that Java comes to that is Object:

    public static Object identity(Object x)
    {
            return x;
    }

If you write it like Haskell, then you need to make sure that the return type is the same as the input type, with no silent upcasting (to Object):

    public static <T> T identity(T x)
    {
            return x;
    }

There is quite a difference between the two pieces of code, which is particularly disturbing, because the Haskell and Scheme versions look so similar to each other. In fact, there's a project called Liskell, which gives Haskell lispy syntax. There, the two would probably be the same. This is a first hint that Java gets in the way of thinking about static typing, by making it very verbose, in particular by making untyped code look different to typed code.

Haskell is also guilty of this, partly by design, and partly because of some deficiencies in its type system. That's the reason that the side of the fence I sit on is the dynamically typed one, but I keep my eye on the static typing people, because they come up with great ideas, and secretly I'd like to be able to use their type systems on some of my code.

So static typing isn't just about making sure that you don't add two credit card numbers together, it's about expressing code as close as possibly to mathematics. Mathematicians tend to be very good at reducing problems to their smallest representations, and coming up with very general solutions, so there can be no doubt that this approach will (and already has) produced amazing results.

Haskell's type system is certainly imperfect, and so are its programmers - this is clear because of the presence of its unit testing system, QuickCheck. If the type system was perfect, and the programmers using it never took shortcuts, there would be no need to run unit tests. It would be evident by the compiler succeeding, that the code could not crash, or produce any results outside the expected range.

If you look for more and more sophisticated type systems, you will probably come across Coq at some point, which is a proof engine that can generate executable code. There you deal with logic, with set theory, all things that are the pinnacle of static typing, and which my Computer Science degree, and probably yours, did not cover.

Go there. Have a look. Even if you decide that static typing is not for you, or that you'll get by with a lesser static typing system such as Haskell's or Java's, you can learn a very general way of thinking that will apply across a lot of programming, in the same way that understanding lambdas will help you when you see C# delegates, JavaScript's anonymous functions, etc.

Dynamic Typing is Not Just About Writing Tests

Many static typing proponents, even Haskellers, have the opinion that while Lisp, Python, Ruby, JavaScript, et al, might have some nice syntax, the fact that they are devoid of static types makes them ultimately useless. You can't easily get the compiler to tell you if you try to do something stupid. For example, 3/"hello world" will be accepted by the language despite it being obvious (read: provable) that a runtime problem will occur.

Many Java programmers assume that you have to guess at the types being used in a dynamic program, or provide excessive documentation. The greater point is that what will work will work. Dynamic languages get out of your way so that you can explore a problem. Whereas in a statically typed language you have to make the solution consistent before you can try it out, you can try out an incomplete function very easily in dynamically-typed languages.

    (lambda (x)
      (if (< x 0)
          (do-this x)
          (do-that x)))

I can call the above lambda on negative numbers, even if do-that hasn't been written yet (assuming do-this has). The runtime doesn't generally complain unless it has to.

Once you have explored a problem, and you understand it, you probably have a nearly-working program, so you're pretty close to having a working one. You get no guarantees that the program will work for all possible inputs, and there isn't even a general way of restricting inputs (other than adding checks at runtime).

Dynamic programmers tend to think in the language they are using - that is, they write code while they're thinking, and test functions out to see whether they work for the cases they're interested in. If I write a function that adds two numbers together, I'm not even remotely interested in what happens if someone passes strings to it, because I'm not writing it for that use case.

This way of thinking keeps the code focused on the task in hand. If the code starts to get hard to read, or repetitive, the programmer will come up with an abstraction. E.g., beginner Java programmers often try this:

    if (x==3 || 5 || 10)

which doesn't compile, because the compiler sees 3 expressions that should all be booleans, and the 2nd and 3rd are ints instead. The programmer gets told they're wrong, and they should fix it to be:

    if (x==3 || x==5 || x==10)

That's clearly garbage, because x== is repeated. The programmer has just adopted a poorer way of thinking to suit a language, instead of adapting the language.

    if (x in (3,5,10))

would be great, as would:

    if ((3,5,10) contains x)

, or even, as valid Java:

    if (asList(3,5,10).contains(x))

Of course, this latter example is a little ugly. Translated directly to Scheme:

    (if (contains (list 3 5 10) x)

If this was used a lot, a Scheme programmer might write:

    (if (in? x 3 5 10)

A Java programmer could do that too, but they would need to know more of the language to be able to do it. Therefore, the Java programmer is 'corrected', instead of shown how to write their idiom in Java.

Because the language gets out of the way, this kind of code is easy to write. That brings about the worry that because you can write code to be as good as you like, you can also write incredibly bad code, and this is completely true.

The remarkable thing is that the language doesn't try to judge whether your code is good or bad - it just runs the code. That's great, because it lets you learn from your own mistakes, and even better, it lets you come up with things that the language designers didn't think of.

It's become quite clear in recent years that Object-Orientated Programming as Java and C++ do it is not the pinnacle of software engineering - but you can't escape Java's OO system. You can't really implement multiple dispatch for two separate codebases in one central place unless you go outside the language (e.g., reflection, bytecode weaving). If it turns out that Haskell's typeclasses aren't the best way of expressing things, you can't remove them from the language, because existing code depends on them - the compiler always needs to understand them - and probably you will still have to use them because the language's central concepts depend on them.

By the language not telling you that you're wrong, it lets you be right in ways that the language designer might not have envisaged. For example, the code snippet (+ "hello" "world") looks wrong, because + is not defined on strings. But in a language like Scheme, + is only a variable, so I can write:

    (let ((+ string-append))
      (+ "hello" "world"))

and it's no longer wrong (arguably a bit stupid though).

So how about those tests? Well, if you look at Java code:

    public Integer add(Integer a,Integer b)
    {
        return a+b;
    }

Both a and b can possibly be null, so what happens if null is passed? Er, you get a NullPointerException. Some programmers will specify that in documentation for the method, or just write that null is not allowed. The same method in Scheme would be callable with any values at all, though it would fail. That changes the attitude of calling programmers. Instead of looking at the half-hearted type signature, and seeing that null is a possible value, the programmer is more likely to look at the implementation.

In the first half of this entry, I said that types imply implementations - well, the reverse is true! Implementations imply types. You don't need a type signature to see what values can be passed to (lambda (a b) (+ a b)), you can infer the type signature from the implementation. In this case, you can pass anything to that lambda that you can pass to the primitive + procedure, whose type signature actually depends on the implementation of Scheme you're using, but it accepts at least those types in the specification.

So Scheme programmers aren't likely to write tests to see what happens if you pass credit cards to a function expecting addresses, because that's never going to be a use case. They informally restrict the inputs. They're emulating what a static type checker does, but mentally. That lets them organically approach a solution to a problem, instead of having to design it beforehand.

It's certainly true that this mental processing is error-prone, and bugs get into source code because of this. Then, many programmers are tempted to write swathes of tests, in an informal attempt to prove that their code is correct.

The bad part of this is that they aren't benefitting from the static typing camp's results now. They have a solution, but they can't use the machine to prove it. They'll end up writing the same kinds of tests over and over.

All this is why I think that, despite him talking about middle-of-the-road type checkers like Java's, Gilad Bracha was on the ball with his presentation about adding pluggable type checkers to dynamic languages. I thoroughly expect that it will be some time before a great one exists, and largely because too many people are sitting on the fence, instead of knocking it down.

If you ignore mediocre languages, there isn't a great deal of difference between how statically typed programmers think and how dynamically typed programmers think. We all like lambdas, we all like side-effect free code, we all dislike crashing programs. So the next time you see a proposal to add static typing to your favourite language, or to add some new dynamic feature to your static language (including 'get-out' clauses like Haskell's unsafePerformIO), bear in mind that you're just witnessing a step on the road to convergence.

If the next big language has a mandatory static type system, then it will either be a crap one, or Computer Science degrees will suddenly contain a lot more mathematics. That won't happen. The next big language will be crap, or dynamic.

Objects To Functions 1 - Stateless Classes

Before I had really heard of functional programming, I had started to notice that it made a lot of sense to make certain objects 'value objects', i.e., create them with all the data they need and then never change them, which lets you pass them around without worrying about who changes them. This sounds like low-hanging fruit, I mean, of course you can easily keep track of changes, just like C++ programmers always manage to track who frees an object.. Ah. You probably see where I'm going now. So, if I don't mutate an object, I can pass it around without thinking about the consequences. That's why it turns out to be better to share Strings rather than StringBuffers in Java. Of course, you can treat a StringBuffer as an immutable value, just by never mutating it, but as it is intended to be mutated, you generally don't share it, at least not without thinking very carefully. Let's look at a very simple stateful class:

public final class Point
{
    public double x,y;
}

I'm sure some readers will be complaining about the lack of get/set methods now - I'll happily explain why I don't use them if you ask in a comment. Others may complain about final, I'll happily explain that too. If you instantiate a Point and pass it around, some programmers will see that it's intended to be mutable, and store a copy of it (or take pains never to store it, but just use its values once), and other programmers will take the attitude of, well, if you're giving out a mutable object you'd damn well better expect it to be mutated*. The latter sounds like an unreasonable attitude, but it's why IDEA places warnings on methods that return the values of fields that hold arrays and collections. IDEA puts the onus on the class giving out the mutable object, rather than on the user of that object - it assumes that the latter programmer is the most likely one. * this latter programmer often also has the attitude that while it's ok for him to mutate the object, nobody else should! It's quite easy to make Point immutable, you can provide a constructor that sets x and y, and then make x and y final. You don't absolutely have to do this - all it really takes to stop a data structure from being modified is to stop modifying it - you don't have to put up barriers to modification to do that. Still, in Java modifying things is the norm, so it might be a good idea for now. If you get to a stage where mutation is only done with great care then you might not need the barrier.

public final class Point
{
    public final double x,y;

    public Point(double x,double y)
    {
       this.x=x;
       this.y=y;
    }
}

So, how does this relate to functions? A Point is now a function, as in mathematics. If you create a Point, it will always give you the same value for x and the same value for y. You can think about it as a function that takes the symbol x or the symbol y and always gives the same result. That is, objects can be or represent functions just as well as methods can. Math.abs represents a function, because it always gives the same output for the same input, and so does point.x. Now I can treat a Point as a long-lived value and never worry whether it will be mutated, just as I don't worry about it being garbage collected. In effect, I've taken time out of its semantics. You might be thinking that Point is crying out to be an interface, because programming to the implementation is inflexible. However, I'd like all clients of Point to be able to rely on .x and .y returning the same thing, forever, and not have to worry about different implementations doing strange things. Instead I would suggest that if you wanted a different implementation, you don't call it Point, and don't try to make it extend or implement Point. Clearly it would be of a different type, e.g., MutablePoint, or DebuggablePoint, Quaternion, etc. - and you wouldn't want to use it in places that expect a Point. There are cases that make this way of programming tricky, and solutions to each: 1. Collections. It would be pretty expensive to copy a collection instead of changing it, so in many cases you may as well change it in place, which loses you the time-independence, and stops the collection from behaving as a function. There are some concessions you could make - e.g., only allowing adds, not removes (then any successful accesses will always succeed - you won't break assumptions). For the more general case, there is one kind of collection in particular that works well as a function - a linked list. Java's LinkedList class doesn't give you access to the individual nodes of the list, which is what we need for this to work, so you'd need to write your own.

class Link<T>
{
    public final T item;
    public final Link<T> next;

    public Link(T item,Link<T> next)
    {
        this.item=item;
        this.next=next;
    }
}

Link<String> list=new Link<String>("hello",null);

If you feel the need to add to the list, you don't need to change anything, just call new Link<String>("world",list) and use that value instead from now on. Then each list retains its properties as a function - it will always return the same value if you ask it the same question. If you want to iterate over such a linked list and do something, say, finding the maximum of a Link<Integer>, you could do it like so:

public int max(Link<Integer> list)
{
    int max=Integer.MIN_VALUE;

    while (list!=null)
    {
        max=Math.max(max,list.item);
        list=list.next;
    }

    return list;
}

This works, and from the outside you can't see any problem, but on the inside you can see that time is important. That is, the list objects always work as functions, but because the variables list and max change values, they don't work as functions - you have to think about time whenever you think of them. It would be easier if you only had to look at the method parameters to see the values, instead of having to trace changes in your head. This is a small-scale version of the bigger problems caused by things that change. We can probably deal with this version with no real problems, but let's follow through and see what happens when we apply the large-scale thinking to the small scale. Because a list is a recursive data structure, it turns out to be quite easy to rewrite max as a recursive method:

public int max(Link<Integer> list)
{
    return new Object()
    {
        public int max(Link<Integer> remaining,int current)
        {
            return remaining==null ? current : max(remaining,Math.max(current,remaining.item));
        }
    }.max(list,Integer.MIN_VALUE);
}

Woah! I'm abusing inner classes or something! What's going on? Java doesn't let you define a method inside a method, but it lets you define a method inside a class, and a class inside a method, so that's what I've done. If I was going to write it in more idiomatic Java, I'd do this:

public int max(Link<Integer> list)
{
    return maxImpl(list,Integer.MIN_VALUE);
}

private int maxImpl(Link<Integer> remaining,int current)
{
    return remaining==null ? current : maxImpl(remaining.next,Math.max(current,remaining.item));
}

Now that you've understood that these two idioms are actually equivalent to each other, you can read the first one without any confusion. Just understand that if I could declare a method inside a method directly, I would have done. There is a problem with this code, in that it throws a StackOverflowError for medium-sized collections, on the Sun JVM, but not IBM's, so I am only using it as an intermediate case for this blog post, before reaching a final conclusion. Anyway, let's move on and create a similar method that gives the minimum for a collection.

public int min(Link<Integer> list)
{
    return new Object()
    {
        public int min(Link<Integer> remaining,int current)
        {
            return remaining==null ? current : min(remaining,Math.min(current,remaining.item));
        }
    }.min(list,Integer.MAX_VALUE);
}

I copied and pasted the code, then changed it, which is a good sign that there's some thinking left to be done. I can make more of it the same by renaming the method inside the anonymous class to 'invoke' or something equally generic. I can move the starting value to the method header - it might not make sense to everyone that the minimum of an empty list is Integer.MAX_VALUE, let's allow the user to decide what value that should be:

public int min(Link<Integer> list,int minimum)
{
    return new Object()
    {
        public int invoke(Link<Integer> remaining,int current)
        {
            return remaining==null ? current : invoke(remaining.next,Math.min(current,remaining.item));
        }
    }.invoke(list,current);
}

There's no reason now not to use the outer method as the target for recursion instead of creating an inner one, so if the anonymous class annoyed you, it goes away now:

public int min(Link<Integer> list,int minimum)
{
    return list==null ? minimum : min(list.next,Math.min(current,remaining.item));
}

Wow, that's short. It's also fairly simple. It says, for an empty list, return the given minimum. For a non-empty list, return ourselves invoked with a smaller list, giving the new invocation a different minimum. Notice that nowhere here have we changed any variables. Still, this throws a StackOverflowError too. Two more steps and we'll get rid of it. The only parts that are specific to minima now are the name of the method, and Math.min. A more general version of what we're doing here is reducing a list to a single value. There are lots and lots of reasons we might do that. Asking whether a list contains a certain item is a reduction.

interface Reducer<T,R>
{
    R reduce(T left,R right);
}

public <T,R> R reduce(Link<T> list,R accumulator,Reducer<T,R> reducer)
{
    return list==null ? accumulator : reduce(list.next,reducer.reduce(accumulator,list.item),reducer);
}

A Reducer is something that knows how to reduce 2 values to one. It doesn't necessarily have to mean two items from the list, just an accumulator and one item from the list. Let's have some imaginary syntax meaning that if I type Math.min with no parentheses, I get a Reducer<Integer,Integer>: int min=reduce(list,0,Math.min); That says find me the minimum value in that list, using Math.min to do so. Unfortunately, Java doesn't support such syntax, so this is what you really end up with:

int min=reduce(list,0,new Reducer<Integer,Integer>()
{
    public Integer reduce(Integer left,Integer right)
    {
        return Math.min(left,right);
    }
});

Unfortunately, this is pretty annoying - so annoying that if you use it more than once, you'll want to wrap the reducer up in a static field or method somewhere, so you end up with: int min=reduce(list,0,Maths.minRef); I'm English, we say Maths instead of Math, which turns out to be a handy conflict resolution here. We still have the StackOverflowError problem, but we can resolve it by rewriting reduce in the 'old' way, with changes to variables. Note that StackOverflowError is really a fault with Java, because at the point where reduce calls itself, there is no need to retain any of reduce's data on the stack. Java could make it work so that reduce overwrites its own parameters and then does a goto to get to the top. Unfortunately, it doesn't, so we have to do that ourselves (except the goto is some loop or other):

public <T,R> R reduce(Link<T> list,R accumulator,Reducer<T,R> reducer)
{
    while (list!=null)
    {
        accumulator=reducer.reduce(accumulator,list.item);
        list=list.next;
    }

    return accumulator;
}

So even though we've ultimately had to make a concession for the technical problems of being in a JVM, we've got something pretty reusable out of the thought experiment. Of course this is nothing new. I actually wouldn't at this time recommend using linked lists in this way in Java, but closures in Java 7 and a solution to the problem of tail-call elimination might make this much more attractive. 2. Cyclic data. If class A needs to hold a B, and B needs to hold an A, there's no way to instantiate them both at the same time. There are clever tricks that make them nearly instantiated at the same time, but you can't make the respective fields final in each. A common solution is to get rid of the cycle by creating a third object, C, that holds A and B, supplying the instances of each other as necessary. Unfortunately, the name for C is often hard to think of, which is a reasonable sign (I'm contradicting another of my blog posts here) that C is a bad thing to have at all. I'd suggest looking at the individual case and deciding what to do. Sometimes it's just that A and B should be merged, or that some functionality should be moved from one class to another. In other cases, it might turn out that some methods can be made static, in which case there's no need to hold an instance. 3. Data that will change over time. Essentially a philosophical question, it is possible to argue that something that is different before a certain time than after it hasn't changed, that there are actually two objects. Monads are a way of treating immutable objects as if they can change, by making the new value replace the old value seamlessly, which effectively solves the philosophical question by letting you write code nearly the same way regardless of the answer. Using Java, though, I'd probably suggest that if data changes over time, you may as well use mutable data. Perhaps Java 7 will make monads more attractive.