Sorting A List

---

Note:I’ve rewritten this post based on feedback from Neal and Ted in the comments. I’ve left the inflammatory comments in (this is a blog, after all), but tried to do a more apples-to-apples comparison between GScript and java. The original article can be viewed here.

---

My first post showing some GScript on this blog compared sorting in Java with sorting in GScript. Today I spent a lot of time going over the psychosis of Comparators in java, and it got me thinking again about how differently Java and GScript approach the problem of sorting lists. I’ll split the discussion into two parts: the code developers must write to sort a list and the actual signatures of the sorting methods used.

The “Client Side”

Comparators, as everyone knows, are java’s way of defining orderings for collections of objects. In Java 1.5 and greater, they are parameterized on T: if you want to sort a List<T>, you pass in a Comparator<T>. Sort of. We’ll get to that. First, let’s look at a simple (!!!) example of sorting in java:

   List>Employees> someEmployees = getEmployees();
   Collections.sort( someEmployees, new Comparator<Employee>(){
    public int compare( Employee e1, Employee e2 ) {
      return e1.getSalary().compareTo( e2.getSalary() );
    }
  });
  return someEmployees

What that code does is sort a collection of employees by Salary. You are forgiven if you can’t tease that fact out of that mess.

As I wrote in the previous post, the GScript to accomplish the same task is:

  return Employees.sortBy( \ e -> e.Salary )

GScript uses closures to boil the operation down to a single line of code and type inference to minimize the syntax of that line. What do we want to do? Sort the list by something. What is that something? The employees Salary. We know that Employees is a list of Employees, so why should we have to specify the type of the “e” parameter to the closure? A GScripter can let the compiler take care of a lot of the details, and still gets nice code completion since everything is statically typed.

The “Server Side”

Now let’s take a look at the other side of the fence: the signatures of the methods used for sorting.

The signature of Collections#sort(list, c) is:

static <T> void sort(List<T> list, Comparator<? super T> c)

What the hell does that mean? Basically, it means you can pass in any comparator that is parameterized on T or a supertype of T. This is because the comparator is going to be invoked with objects of type T, so only comparators that take that type or *higher* in the inheritance chain will work. In particular, Comparator<? extends T> will *not* work, because the comparator might be expecting a subtype of T. This is a case of contra-variance, which is fairly rare in type-systems. We are used to the opposite, variance, where a subtype of T is acceptable in place of T. Some programming languages, notably Scala, allow you to annotate type variables with the particular variance they allow, usually using a ‘+’ or ‘-‘ sign.

(As a side note, as I’ve said elsewhere, any non-trivial application of generics requires me to stop and put on my generics hat, and, ten minutes after I’ve understood and solved the task at hand, *poof*, it’s gone.)

Interestingly, since java lacks any way to specify variance, internally Sun engineers have to cast the Comparators to the generic type to do comparisons. I’m not lying. Check out the implementation. The implementation of TreeSet is even better, with the developer putting in little /*-*/ comments in the places to indicate variance more correctly when he has to cast to the generic type.

So here we have a lot of syntax flying around to make sure sorting lists is absolutely, positively, 100% type safe. And, despite all that, the sun engineers still have to crosscast to the generic type to make the damned thing work. All to prevent what has to be one of the rarest programming errors I can imagine: accidentally sorting a List with a bad Comparator. I’ve never seen that happen. I’ve never heard of that happening. I’ve never even heard it mentioned that it might happen. And yet all that complexity has been thrown at this problem in java.

The signature of sortBy() is:

  function sortBy( value(T):Comparable ) : List

and it is injected onto List via GScript Enhancements.

The parameter is declared to be a block that takes an argument of type T and returns a Comparable object, which will be used to order the list. (We eventually delegate to Collections.sort() internally so that the sort occurs in java, rather than GScript. Hey, we still want it to be fast, right?)

Note that Comparable is left generic because there is almost zero chance someone will screw a call to sortBy() up from a typing perspective, and if they did, the incomprehensible generics error message would be far harder to understand than then inevitable runtime exception that would occur. It just isn’t worth the complexity to specify it.

Yeah, so?

Well, to me, GScript throws complexity at the right part of the problem. It takes a common operation on Lists, sorting by some attribute of their component elements, and boils it down to its essence using closures. Closures, like generics, are somewhat complicated and can take a bit to get your head around. But once you grock closures in GScript you end up having to know less, not more, about the complexities of sorting. This is in stark contrast with the generics in Collections.sort(). That application of complexity doesn’t help developers much, if at all. The only time you will ever notice it is when it gets in your way.

The overriding theme of GScript, formally spelled out by Scott at the start of our Bedrock release: “GScript features are about making developer’s lives easier.” I’m convinced that if static language designers make pragmatic concessions to real-world developer needs and the acknowledge the practical limitations of static typing, the current excitement around dynamic languages would temper dramatically.

---