Amusing discovery of the day

Java bytecode lets you overload method names based on the return type as well as the argument types, even if the language doesn't.

Hardware vendor shit list

In keeping with my recent stance on blog content, this has nothing whatsoever to do with programming. It won't educate you about esoteric languages, you won't learn good development practices from it, and frankly you probably won't care about it. This is a post about hardware companies who suck. This post has two purposes: a) In the hopes that it will prevent someone else from having to deal with these issues. b) A small measure of petty revenge against those who have SERIOUSLY PISSED ME OFF. It's not like they'll notice the loss of a few sales, but if this persuades even one person not to give them money for their crap it will make me feel better. There's a tentative c) that if anyone could give me a suggestion for fixing my laptop I'd be eternally grateful. :-) But I don't really expect that. The past six months have not been happy ones for hardware. My work machine has never worked right, and my personal laptop has mysteriously died. Twice. The incompetence of Mesh in dealing with the desktop's problems has been rivaled only by the astoundingly poor communication skills and unreliable hardware of Asus. First, Mesh. The problem with the desktop is a very annoying one: The screen would intermittently go black for a second or two. At first it did this once every few hours and I wasn't sure if it wasn't just power saving mode or something. Eventually I verified that no, it really was happening, and it was happening in both vista and ubuntu, so it most likely wasn't a software problem. As time went on the problem got progressively worse - these days the rate is several times per minute. I eventually narrowed it down. The problem would only manifest in the exact following circumstances: a) This exact PC. Any other one worked fine. b) The exact brand and make of monitor. Brand and make you say? Want to know how I know this? It's because they sent us three. Sending us the second one was quite reasonable - it looked like a monitor problem. After the second we pointed out that maybe this wasn't such a productive use (however we didn't complain too hard, as the monitor had developed several dead pixels. But they wouldn't replace it for the dead pixels sitting smack in the middle of the screen. You need at least 5 before it's a replaceable condition. More on this later.). c) Only on DVI input. c) was the fortunate point which meant that I've actually been able to get work done in the last six months. I dislike VGA, but it's at least usable. Speaking of the brand of monitors, here's another shit list entry: Mirai, the brand of this monitor. Quite possibly the worst monitor I've ever used. Despite my best efforts and tinkering the colour has never been anything less than washed out. They've developed dead pixels, random image problems (my favourite was the "yellow line down the middle of the screen". That was a fun one. The flickering effect was another nice touch). Anyway, back to mesh and this peculiarly specific hardware problem. Very random, isn't it? What's the chance that two pieces of hardware picked out of the blue would demonstrate such a specific incompatibility? Wait, picked out of the blue? That doesn't sound right. Let's try again. What's the chance that two pieces of hardware picked and provided specifically to work together would show such a specific incompatibility? Having exhausted monitor options they concluded that maybe we should replace the motherboard (it had onboard video). And so they did. Eventually. It took more than a little trying and them sending no less than four people out (it might even have been five. I forget if we had one or two no shows). Between these four, they managed the following problems: a) A no show b) someone who came out with a very handy motherboard box. No motherboard mind you, but one out of two isn't bad, right? c) Someone who in his truly inspiring competence managed to bring not only a motherboard box but an actual motherboard contained within. Rapture! What service! Oops. Wrong motherboard. What service? d) Finally someone who managed the simultaneous combination of box, motherboard and correct brand of motherboard. He didn't arrive until 7:00 in the evening and seemed to think he was going to be visiting a home address, but oh well. Why be picky? He managed to replace the motherboard successfully and everything, we booted up the machine and the display appeared stable. Could it be that after all this time the problem was finally resolved?? For context, I should clarify that I was now working on a different machine. We'd cut our losses and moved me to another desktop (a Dell. I'm not a big fan of Dell, but I have to admit their customer service is great). This meant that I wasn't directly observing the other machine, but we booted it up with the intent of testing it and once we were sure the problem was resolved putting it to another use. At some point during the following day I got a question from someone who sits next to where I had the computer set up. "David, did Mesh come to fix this last night?" I moved around to talk to them. As I did I said something along the lines of "Yeah, they replaced the motherboard and it seems to have solved the... oh shit" Flicker. Flicker flicker. Blink. Which is about where we stand currently. I don't know what we're going to do now. Now, Asus. I went with Asus because I'd been told their laptops were very reliable. Yeah... not so much. Also their website is awful, their customer support is awful, and their communication skills lie somewhere between "awful" and "nonexistent". I placed the order on a weekend. I got a generic "thank you for placing an order" with a note about sending confirmation when they were ready to deliver. On tuesday I still hadn't heard from them so I made a mental note to call them in the morning to ask when they were likely to deliver. And arrived to find my laptop sitting on my doorstep. On the one hand, yay laptop. On the other hand, RANDOMLY LEAVING EXPENSIVE HARDWARE ON ONE'S DOORSTEP IS NOT COOL. Granted it was internal to my building, not on the street, so clearly someone had to have let them in and signed for it, but this is still not acceptable behaviour. But even setting that aside, the key point here is that there was no communication, no advance warning, nothing. If they'd just done exactly what they should have done and said they were going to and let me know that they were planning to deliver that day I would have planned accordingly. Anyway, rather than tear them a new one, I decided to let it pass. After all, I had a laptop (and a reasonably nice one). No harm done. A week and a half later the laptop turned into a brick. The power light came on when you pressed the power button, and some vague whirring noises, but nothing more than that. I called up asus technical support, reading their support procedures on the card with growing dread (it involved sending you a snail mail form to fill out if they decided that yes really you needed replacement hardware). Fortunately their procedures were 71% less insane than claimed, and the dreaded form was in fact an excel spreadsheet. Hurray. Upon filling this out and getting confirmation I had to call an entirely different branch in order to arrange a pickup. When I did they asked me to call back later as the details had yet to come through. Apparently their inability to communicate extends to eachother as well as their customers. It's good to know I'm not being singled out. Eventually I persuaded them to pick up the laptop. In fairness it didn't require *that* much persuading. They picked it up promptly once arranged. And then silence. Two and a half weeks later I finally found time to call them up and say "Soo... laptop. What's going on with that?". "Oh, yeah, we sent it out this morning. You should be getting it today". Fine, great, I'm glad they sent it back. But again with the total non-communication. And slowness. Two and a half weeks is not a nice length of time to be laptopless. For additional failure to communicate, they gave no indication whatsoever of what the fault was. I should have enquired, but I couldn't be bothered at the time. This was a mistake. That was a couple of weeks ago - I forget how many, but definitely not longer than a month - and the absence of this knowledge is now highly relevant, because the laptop has just done it again. This time it appears to have been the result of leaving it on until it went into power saving mode - I fell asleep with it on, woke up four hours later to discover that I no longer possessed a functioning laptop. If anything it's brickier than last time - I'm not even getting a power light when pressing the switch. This is especially upsetting as it means I will have no laptop over the christmas period. This means no working on personal projects I've been putting off due to work and, more importantly, a very limited amount of communication - in particular I'll have to borrow my parents' computer if I want to use Skype or IM (and no video at all. Sigh). It also probably means that you get a respite from my blogging. :-) For added irritation (and admittedly I can't blame this on hardware vendors, although if I could I'd try at this point), I seem to be running a moderately high fever. All in all this does not result in a happy David.

Type classes in Scala

Some backstory on this post: I got about halfway through writing it before realising that in fact it didn't work because of a missing feature. I sent an email to the mailing list about this feature and after some discussion it was concluded that in fact this missing feature was a failure to meet the specification and that it had been fixed in 2.6.1. There's still one thing lacking, but more on that later. The post now resumes. I mentioned in a recent post that Scala could emulate Haskell type classes with its implicit defs and first class modules. In actual fact, the situation is much happier than that. Implicit defs + first class modules give you significantly more than Haskell type classes (although with a tiny loss of type safety). At least, much more than Haskell 98. In particular, multiparameter type classes and associated types come for free. You also gain a number of other advantages, such as type class instantiation scopes lexically, so you can redefine type classes locally. So, how does all this work? I'll begin with a general introduction to this style of programming with no real reference to Haskell, and then I'll tie this back in to encoding Haskell type classes at the end of it. Here's a class that's familiar to anyone who has written non-trivial Java:

trait Comparator[T]{
  def compare(x : T, y : T) : Int; 
}

trait Comparable[T]{
  def compareTo(t : T);
}

Now, let's define the following method:

def sort[T](array : Array[T])(implicit cmp : Comparator[T]) = stuff

So our sort method can either have a comparator passed to it explicitly or it will pull one from the surrounding environment. For example we could do:

object SortArgs{
  implicit val alphabetical = new Comparator[String]{
     def compare(x : String, y : String) = x.compareTo(y);
  }

  def main(args : Array[String]){
     println(sort(args));
  }
}

Will pick up the alphabetical instance. It would be nice if we could also have defined the more general version:

object SortArgs{
  implicit def naturalOrder[T <: Comparable] = new Comparator[T]{
     def compare(x : T, y : T) = x.compareTo(y);
  }

  def main(args : Array[String]){
     println(sort(args));
  }
}

But this doesn't seem to work. :-/ Hopefully this will be fixed - it seems like wrong behaviour. Matt Hellige came up with the following workaround, but it's not very nice:

object Sorting{
    trait Comparator[T]{
        def compare(x : T, y : T) : Int;
    }

    def sort[T](arr : Array[T])()(implicit cmp : () => Comparator[T]) = null;
    implicit def naturalOrder[T <: Comparable]() : Comparator[T] = null;
    implicit def lexicographical[T]() (implicit cmp : () => Comparator[T]) :
        Comparator[List[T]] = null;

    def main(args : Array[String]){
        sort(args);
        sort(args.map(List(_)))
        sort(args.map(List(_)).map(List(_)))
    }
}

Moreover I haven't the faintest notion of why it works. :-) However we can also chain implicit defs:

   implicit def lexicographicalOrder[T] (implicit cmp : Comparator[T]) : Comparator[List[T]] = stuff;

So now the following code *does* work:

  def main(args : Array[String]){
    sort(args);
    sort(args.map(List(_)))
    sort(args.map(List(_)).map(List(_)))
  }
}

An amazingly nice feature of this which some encodings of type classes miss is that you don't need an instance of a type to select on that type. Take for example the following:

object BinaryDemo{
  import java.io._;
  trait Binary[T]{
    def put(t : T, stream : OutputStream);
    def get(stream : InputStream) : T;
  }

  implicit val utf8 : Binary[String] = null;
  implicit def binaryOption[T] (implicit bin : Binary[T]) : Binary[Option[T]] = null;

  val myStream : InputStream = null;

  def readText(implicit bin : Binary[Option[String]]) : Option[String] = bin.get(myStream);

  readText match{
    case None => println("I found nothing. :(");
    case Some(x) => println("I found" + x);
  }
}

Unfortunately this example betrays a weakness in our encoding. I can't just randomly call "get" like in Haskell's Data.Binary - because I need to invoke it on an instance of Binary[T] I need to ensure at the method level that one is available. There doesn't appear to be a good way of getting access to implicits from the enclosing scope directly. However, here's a silly hack:

   def fromScope[T] (implicit t : T) = t; 

And we get:

  fromScope[Binary[Option[String]].get(myStream) match{
    case None => println("I found nothing. :(");
    case Some(x) => println("I found" + x);
  }
}

This works just as well with multiple type parameters. For example, if we wanted to port Java's AtomicArray classes without wrapping everything (although admittedly wrapping everything would be more idiomatic Scala) we could do the following:

object ArrayDemo{
  import java.util.concurrent.atomic._;
  trait AtomicArray[S, T]{
    def get(s : S, i : Int) : T;
    def set(s : S, i : Int, t : T);
    def compareAndSet(s : S, i : Int, expected : T, update : T);
  }

 implicit val long = new AtomicArray[AtomicLongArray, Long]{
    def get(s : AtomicLongArray, i : Int) = s.get(i);
    def set(s : AtomicLongArray, i : Int, t : Long) = s.set(i, t);
    def compareAndSet(s : AtomicLongArray, i : Int, expected : Long, update : Long) = s.compareAndSet(i, expected, update);
  }
}

So, that's multi-parameter type classes. But one thing you'll notice about the above encoding is that it's a bloody nuisance to invoke - you need to know the type of the array class you're using, which is annoying. Far better would be if the trait took care of that. In Haskell terms this would be an associated type. No problem.

object ArrayDemo{
  import java.util.concurrent.atomic._;
  trait AtomicArray[T]{
    type S;
    def get(s : S, i : Int) : T;
    def set(s : S, i : Int, t : T);
    def compareAndSet(s : S, i : Int, expected : T, update : T);
  }

 implicit val long = new AtomicArray[Long]{
    type S = AtomicLongArray;
    def get(s : AtomicLongArray, i : Int) = s.get(i);
    def set(s : AtomicLongArray, i : Int, t : Long) = s.set(i, t);
    def compareAndSet(s : AtomicLongArray, i : Int, expected : Long, update : Long) = s.compareAndSet(i, expected, update);
  }
}

Scala's classes can have abstract types. So we just encode associated types as those. So, to recap on our encoding:

  class Foo a where
     bar :: a
     baz :: a -> a

becomes

  trait Foo[A]{
     def bar : A;
     def baz(a : A) : A;
  }

  instance Foo Bar where
  stuff

becomes

  implicit Foo[Bar] bar = new Foo[A]{
    stuff
  }


  instance (Foo a) => Foo [a]

becomes

  implicit def[T] (implicit foo : Foo[A]) : Foo[List[A]];

And for invoking:

  foo = bar

becomes

  val yuck = fromScope[Foo[A]].bar 

So it's a more verbose encoding, but not a terrible one. And it has some abstraction advantages too. For example:

   sortBy :: (a -> a -> Ord) -> [a] -> [a]
   sortBy = stuff;

   sort :: (Ord a) => [a] -> [a]

becomes

   def sort[A](xs : List[A])(implicit cmp : Comparator[A]);

Because our type classes are a form of implicit object passing, we can also use them with *explicit* object passing. Thus we can redefine behaviour much more nicely to behave equally well with an ordered type and explicitly provided comparison functions. This has disadvantages too - you need to be more careful to ensure that you can't accidentally use two instances of the type class. This isn't a major burden though. The general solution is that when you have something which needs to maintain type class consistency between invocations you pass it an instance at construction type. Take for example Haskell's Data.Set. In Haskell getting a new Set (Set.empty) works for any type but almost all the functions for building sets have a constraint that the type belongs to Ord. In Scala you would require an Ord instance to be passed for Set construction but after that would not need one (analagous to Java's TreeSet providing a constructor that takes a Comparator). One thing I haven't covered is type classes which abstract over type constructors rather than types. The reason I haven't covered them is that I've yet to peek into that corner of Scala's type system. However, I assume they work as Tony Morris has done some stuff with monads in Scala. Also, see this paper (which I've not read yet)

Random thoughts on OO

OO is supposed to be about modularisation right? Separating your concerns and all. Suppose I told you there were two major areas of your code that were deeply intertwined. Each is intimately connected to the other and it was almost impossible to tell where one started and the other began, yet the two were really very different. Doesn't sound very modular, does it? Practically the antithesis of good OO practice. Suppose I now told you those two areas were "behaviour" and "data". Don't mind me. Just thinking out loud...

No, seriously, why Scala?

Recently an article called Why Scala? was posted on reddit. It's an ok introduction to the language, but the very fair observation was made that it's much more of a "What is Scala?" than a "Why Scala?". I thought I'd share my thoughts on the subject. Mainly because I like hearing (reading) myself talk (write). :-) Quick background: I initially learned to program in standard ML while at university (self taught, mostly, with the help of some friends doing computer science. I was doing maths). On graduating I then switched tracks entirely and started doing Java web development in a small software firm in London (I've since switched again, but I'm still doing Java professionally). I've also dabbled and read a lot with computer science and programming languages in my spare time since then, filling in the gaps that not having done any real computer science at university left me. My train of thought on the language switch from ML to Java was basically: a) Wow, this is different. b) Ugh. Where are my higher order functions? c) Where are all these random exceptions coming from?? I've compiled the code successfully, isn't it supposed to work now? d) Hmm. But there's some useful stuff here too. Scala's a nice way to scratch both itches, and adds some very interesting features and functionality of its own. It's not my favourite language (I don't really have one. All languages suck. It's just that some of them suck less in interesting ways), but it has a lot I like. Here's a brain dump of some of it.

Things I like:

Object oriented programming

I know, it's so entrenched it's past even bothering with its buzzword status. But object oriented programming has a lot of advantages for medium to large scale composition. It has some disadvantages, and frankly sucks at small scale composition of functionality (which is where functional programming shines), but it allows for some very nice pluggability.

Module oriented programming

ML has higher order modules. I never really used them much when I was programming it more often (mostly because I was only writing enough code to do some simple maths projects. I never wrote anything large scale), but having looked into them in more details since they're really powerful. They're essentially a different take on the composition that object orientation provides. Where object orientation resolves everything dynamically, ML's higher order modules resolve everything statically. This introduces some limitations in flexibility but makes up for them in power and type safety - they provide a much more flexible and interesting abstraction over a type than mere subclassing and interfaces can. Scala has both. Further, it has both and lo and behold they are the same thing. Objects are modules, and can declare their own types (note: This is much more than just declaring an inner class in Java is), imported, etc. Modules are objects and can be instantiated at runtime, extended, etc. You lose a bit of the static guarantees that ML modules but you gain a lot of flexibility from both sides.

Static Typing

I've written too much Java to not like static typing. Wait, I know that sounds like a non sequitur, but read on. I've written too much Java and seen flagrantly stupid and really subtle runtime errors that should never have made it past the compiler coming out of it to not like static typing. NullPointerException, ClassCastException, argh. If you've written enough code in a language like ML, OCaml or Haskell you will know that the compiler is your friend. And, like all good friends, it will yell at you if you do something stupid and then help you pick up the pieces. Scala doesn't quite manage that. If you write code in just the right way you can achieve that level of guarantee (and in some cases, more. But that tends to be the result of abuse of the type system by deranged maniacs), but the combination of subtyping and some Java interoperability decisions mean that it's not quite as good. It's not bad though. So: I like object oriented programming, I like static typing. It logically follows that I must like statically typed object oriented languages, right? Well, in principle, yes. But Scala is the first one I've met with a type system that didn't suck. Scala's traits (a sort of mixin) are so much better to work with than interfaces, the generics work properly, provide variance annotations, etc. A reasonable subset of the types are inferred. Compared to the type systems of Java, C# and C++ it's a dream (it's not as nice as the type systems of the statically typed functional languages I know of. Subtyping seems to cause issues, with a lot of research still needed to make it work well, and Scala seems to have largely ignored what prior work there was Hindley-Milner style type systems with subtyping)

Functional programming

You've all been dreading this section. "Oh no. Now he's going to enthuse about how marvelous functional programming is and how it's going to cure cancer". Nope. Can't be bothered. Functional programming is nice. If you don't believe that, I'm not going to try to convince you of it. Scala's support for functional programming is ok. It has some warts, but it also has some nice points, and it generally works well and isn't too verbose. I'm not going to get any more excited about its presence than I am about the fact that my bike has wheels (but I'd be pretty pissed off if my bike didn't have wheels). Higher order functions, pattern matching, etc. It's all there. It works. Moving on swiftly...

Implicits

Scala offers a bag of features under the keyword 'implicit'. This is one of those things that makes you go "Oh, that's cute" when you first see it and then go "Wow, that's powerful" six months later. Essentially implicits give you statically guaranteed and provided dynamic scoping. You say "I need a Foo. I don't care where it comes from", the compiler says "Here you go" or "Sorry, no Foos today". These can be objects, implicit conversions between types (You know the way Ints get implicitly converted to longs, double, etc in Java? Scala does that too, but it's all programmer definable. They're just library functions in scala.Predefined). If you remember what I said about Scala objects being modules and you've read this paper a little light might just have gone on in your brain. If you haven't read it and don't want to, here's the summary version: Implicit function arguments + first class modules gives you something that looks and quacks very much like Haskell type classes (yes, I know this isn't actually what the paper says, but it follows from it). Mmm. These are the big things to like about Scala. Here are a few little things:

• Sane constructor/class semantics. If you've written a lot of Java there's a good chance you hate its constructor system. Scala's is much nicer.
• Expression oriented code. Everything is an expression. You can form compound expressions trivially - { val foo = bar(); baz(foo, foo); } is an expression which evaluates to baz(foo, foo).
• Sanely uniform scope. Pretty much anything you can do inside a method you can do inside an object and vice versa. Things are for the most part lexically scoped in the right way.
• The primitive/object divide is much less irritating. Primitives get a few special treatments at the language level, but mostly they're just objects. When things should compile to use primitives, they do. When the primitives need to be boxed, they will be. It's almost entirely transparent.
• Performance. Scala generates very good (well. 'good'. Java-like) bytecode, which means it gets to take advantage of most of the optimizations the JVM is willing to throw its way. Further it puts a reasonable amount of its own work into performing optimisations on the bytecode, etc so you get those nice juicy abstractions without much overhead. There's essentiall y no performance penalty for choosing Scala over Java

etc. Scala's far from perfect. It has some syntactic weirdnesses, a few issues carried over from Java, a moderately buggy compiler and a host of little features and edge cases that are really hard to keep in your head. However, I find that these issues don't actually do more than annoy you from time to time. The core language is powerful and very useful for just sitting down and writing good code in.

Open sourced range types

I've expanded on the range types a little bit and created an open source project for them. In particular they now support subranges in a typesafe way.

Statically checked range types in Scala

I was showing off some Scala features earlier (specifically "Oh, hey, look. With proper singleton support + implicit arguments you can completely remove the need for a dependency injection container while losing none of the advantages". More on that later...) and got to discussing the language with Craig, a coworker of mine (well, specifically our CTO. I work at a cool company. :-) ). He asked me if Scala supported range types, to which my answer was something along the lines of "Well, no. But it should be possible to add as a library. Hmm. Might be hard to get it statically enforced though". Turns out it's not. Here's some code: http://snippets.dzone.com/posts/show/4876 How do we use this?

scala> import ranges.Range;
import ranges.Range

scala> val myRange = new Range(0, 10);
myRange: ranges.Range = ranges.Range@10ae3fb

scala> val myRange2 = new Range(0, 20);
myRange2: ranges.Range = ranges.Range@c7014c

scala> val array = new myRange.CheckedArray[String]
array: myRange.CheckedArray[String] = ranges.Range$CheckedArray@280bca

scala> myRange.indices.foreach(x => array(x) = x.toString)

scala> array.mkString
res6: String = Index(0)Index(1)Index(2)Index(3)Index(4)Index(5)Index(6)Index(7)Index(8)Index(9)

scala> array(myRange.minIndex);
res8: String = Index(0)

scala> array(myRange.maxIndex);
res9: String = Index(9)

scala> array(myRange2.minIndex);
:8: error: type mismatch;
 found   : myRange2.Index
 required: myRange.Index
  val res10 = array(myRange2.minIndex);
                            ^

scala> array(myRange.minIndex.mid(myRange.maxIndex));
res11: String = Index(4)

scala> array(myRange.minIndex + myRange.maxIndex);
:8: error: type mismatch;
 found   : myRange.Index
 required: String
  val res13 = array(myRange.minIndex + myRange.maxIndex);
                                              ^

scala> import myRange._;
import myRange._

scala> array(myRange.minIndex + myRange.maxIndex);
:11: error: type mismatch;
 found   : Int
 required: myRange.Index
  val res14 = array(myRange.minIndex + myRange.maxIndex);
                                     ^

scala> array(minIndex + maxIndex);
:11: error: type mismatch;
 found   : Int
 required: myRange.Index
  val res15 = array(minIndex + maxIndex);
                             ^

CheckedArrays (and similarly ArraySlices) are scoped to a particular range object. You can only access them with indices from that same object. You can get Index objects by getting the minimum, the maximum, combining them with various operators, iterating over them or converting from an Integer (at which point it will either min/max it into bounds or throw an IndexOutOfBoundsException if the integer is out of bounds, depending on which method you call). If you import the range (I'm thinking of separating that out into a separate object for convenience with working with multiple ranges) you'll get an implicit convertion from indices to integers (*not* the other way around). Currently nonexistent: Support for subranges, or working with multiple ranges (Update: See below). I think I know how to fix these in a niceish way. Always going to be nonexistent: Can't statically verify that two ranges are equal. This isn't possible in principle, but even simple cases like knowing that new Range(0, 10) and new Range(0, 10) are equal types isn't doable. I don't think this is avoidable without special logic in the compiler or significantly more static resolution of objects than Scala is ever likely to have (e.g. I think we could do this using ML functors and sharing constraints, but it's been so long since I've looked at those that I'm not really sure). Update: Working with multiple ranges is always going to suck without language changes. There's not enough sharing of values at compile time to express what it needs to. Subranges will probably still work though. Update 2: It's been observed that if you don't know Scala then it's non-obvious how this code works. Unlike Java, inner classes of different instances in Scala are actually different types. So given

val range1 = new Range(0, 10);
val range2 = new Range(0, 10);

range1.Index and range2.Index are different types, and may not be freely converted between. So this code works by having Range enforce that its Index elements are in bounds, and the compiler enforces that you can't mix Index elements from different ranges.

Minor irritations

I just noticed the following issue in Java. It's never bothered me before, so it's clearly not that big a deal, but I find it vaguely annoying. The following code is not legal:

final Foo foo;
try{
  foo = stuff();
} catch (Exception e){
  foo = otherStuff(); 
}

The compiler thinks that foo might already have been assigned in the catch block, even though it clearly can't have been. The reason is presumably that it doesn't distinguish it from the following code:

final Foo foo;
try{
  foo = stuff();
  bar();
} catch (Exception e){  // Might have been thrown from bar.
  foo = otherStuff(); 
}

Which is reasonable. I'm not sure if I'd really want this edge case to be handled specially. As Ricky Clarkson pointed out in ##java, what would really be much nicer is:

final Foo foo = try { stuff(); } catch(Exception e) { otherStuff(); }

i.e. Compound expressions ala Scala (or GCC extensions, or any number of other languages). It would avoid a lot of annoying edge cases with assigning to final variables. This isn't really a "Please add this to Java 7" request. I don't care enough and the list of desired features is getting annoying. It's just a minor irritation with the language.

Don't forget to fly

I saw this comic a while ago and it occurred to me during today's HUG. I think the analogy is obvious, but I'm going to spell it out anyway because I feel the need to rant about it. (As a side note, I know I've occasionally been guilty of what I'm ranting about. Hopefully I've stopped...) You like functional programming. That's great. You write C#/Java/C++/Brainfuck/PL-SQL/Malbolge during your day job. That's a shame, but oh well. You and everyone else. I bet you really wish you could use folds/lazy evaluation/lightweight threading/COMEFROM statements in your work code. Great. Me too. There's a lot of neat stuff in functional programming (and in the better OO languages. And in logic programming. And in a wide variety of other things). So, use it. Go wild. Write code. DON'T waste time posting endless blog posts about how closures are awesome and wonderful and here's an example of how they might work in Java. "Here's a nice bit of code I wrote" is one thing. "Here's how to implement a for loop. Isn't it awesome!!!"? Not so much. If you're interested in something, use it. Don't waste time thinking about how to shoehorn its features into a language you know far too well. You can fly. Stop thinking about how great it would be to do so and go out and do it.

Dependency injection in Scala

I (and some others in #scala) have been wondering recently about the state of play for dependency injection in Scala. This is mostly just a brain dump of a few thoughts and a request for feedback. If anyone has any good ideas, please share! As I see it, most of the Java dependency injection frameworks should work fine for Scala. Guice won't because of generics issues, and similarly the generics support from other frameworks (e.g. Spring's type collections) won't though, so you lose a great deal of type safety. You're back to an almost Java-like level of type safety in fact. :) Also these don't take advantage of many of Scala's great features (higher order functions and a more advanced object system in particular), so the whole thing seems rather unsatisfactory. I wondered briefly about a system based on abstract method injection using traits, but I couldn't make it work in a satisfactory manner. The fact that you'd expose dependencies as defs was also unsatisfactory because it means that the compiler doesn't know that they're stable so you can't e.g. import them. There was some discussion in #scala last night about how "dependency injection is useless if you have higher order functions". This seems like nonsense to me. A well designed scala program may have less need for DI because of the presence of higher order functions but the basic need for composing of modules (that's what dependency injection frameworks really are after all - a module composition DSL) is still there, for more or less the same reason why Scala has objects as well as functions. It's not entirely clear to me how DI should work in Scala, both from an API and an implementation point of view. Something Guice-like might be a good starting point (but only a starting point! Porting Guice verbatim to Scala would almost certainly be a bad idea), but it's not clear to me how one would even implement it in Scala. Part of the problem is that Scala lacks a satisfactory metaprogramming facility. It can use Java's reflection, but the scala.reflect packages seem sadly meager. (There do seem to be a bunch of interesting sounding classes in there, but there appears to be no documentation or evidence of prior usage, so I can't figure out what on earth they're for).

Java performance tip: Think about your container sizes

Take a look at this javadoc entry and then think about what happens if you create many thousands of HashMaps with only 1 or 2 entries in them. Our work application has a very large number of objects to which you can attach attributes. We use HashMaps for these. Many of them have no attributes and were just getting their HashMap with a new HashMap() call. In order to investigate just why our application was eating up so much memory (relatively speaking. It still isn't competing with netbeans, firefox, etc). I opened it up in the profiler, saw that of that memory usage the lion's share of it was from HashMaps. I've now changed the code so they're being given an initial capacity of 1. Things are much happier now. This is basically just a heads up - if you're using a lot of a container type which lets you specify an initial capacity (HashMap, HashSet and ArrayList, for example), give it at least some thought rather than using the default. If you only have a few or they're purely transient it doesn't really matter. Even if they're many and long lived you don't need to worry about getting it exactly right, but a little tuning can save you from a lot of the memory bloat that is common in Java applications.

Turn your toString methods inside out

All examples in this post will be written in a pseudo-dialect of Scala. Hopefully they should be easy to translate into your favourite programming language (or Java). I also haven't bothered to compile any of them as they're mostly not entirely valid. Feel free to point out errors. Consider the following code:

class List[T]{
  // list implementation

  override def toString : String = {
    val it = this.elements;
    var result = "[";

    while(it hasNext){
      result = result + (it next);
      if (it hasNext) result = result + ", ";
    }
    result + "]"
  }
}

What's wrong with it? Well, as you presumably know, concatenating two strings of length m and n is an O(m + n) operation (In Haskell or ML it would be an O(m) operation, so this can be made more efficient, but the basic point will still remain). This means we've accidentally made an O(n^2) toString algorithm. Oops. So, the traditional response is:

class List[T]{
  import java.lang.StringBuilder;
  // list implementation

  override def toString : String = {
    val it = this.elements;
    var result = new StringBuilder();

    while(it hasNext){
      result.append(it next);
      if (it hasNext) result.append(", ");
    }
    result.append("]").toString;
  }
}

Great! We've removed all those expensive string concatenations. Now, what happens if we call toString on a List[List[String]]? Umm... Now, consider the following code snippet:

  println(myReallyLongList);

Let's unpack what's going on in it.

  val it = myReallyLongList.elements;
  var result = new StringBuilder();

  while(it hasNext){
    result.append(it next);
    if (it hasNext) result.append(", ");
  }
  println(result.append("]").toString);

So, we've created a big intermediate string via a StringBuilder, then printed it, discarding the string after that. Right? Wouldn't it be great if we'd written the following code instead?

  val it = myReallyLongList.elements;

  while(it hasNext){
    print(it next);
    if (it hasNext) print(", ");
  }
  println("]");

No intermediate structures created at all. And note that the code used to print is almost exactly the same as the code used to append to the StringBuilder. Conveniently there's a useful little interface in java.lang which people tend to ignore. If not, we'd have had to write wrappers. In particular this is a superclass of Writer, PrintStream, StringBuilder and StringBuffer. So, let's rewrite the above code:

class List[T]{
  import java.lang.StringBuilder;
  // list implementation

  def appendTo(ap : Appendable){
    val it = this.elements;

    while(it hasNext){
      ap.append(... // err. What do we do here?

We could just do ap.append(it next toString). But that doesn't solve the first problem - when we nest these things we're creating a lot of intermediate strings and then immediately throwing them away, not to mention having once again introduced a hidden O(n^2) factor. Sadness. :( Let's do the following:

  trait Append{
    def appendTo(ap : Appendable) : Appendable;

    override def toString = appendTo(new java.lang.StringBuilder()) toString;    
  }

  object Appending{
    def append(any : AnyRef, ap : Appendable){
      if (any.isInstanceOf[Append]) any.asInstanceOf[Append].appendTo(ap);
      else ap.append(any toString)
    }
  }

Now we can write it as:

class List[T] extends Append{
  import Appending._;
  import java.lang.StringBuilder;
  // list implementation

  def appendTo(ap : Appendable) = {
    val it = this.elements;
    while(it hasNext){
      append(it next, ap);
      if (it hasNext) ap append(", ");
    }
    ap.append("]");
  }
}

Now, no matter how deeply we nest things, we'll get things printed in a manner with completely consistent performance - no hidden gotchas. There are also other benefits to structuring things this way. If you make everything work based on an API that looks like this you'll tend to write things which work by injecting filters in reading and writing code. And, hey, suddenly all your code works completely transparently when you discover that you need to work with things that are e.g. read off the network, backed by something on the file system, etc. and really need a streaming version of the library. Also note that I'm not saying "Strings are bad". There are a lot of cases where what you need really is a persistently available string. Then, by all means, use toString! But even then this is helpful, as your toString code will work a lot better and more consistently than it might otherwise have done.

Ooooooh. Shiny!

When I built this computer I bought two very nice monitors to go with it. I then promptly discovered that I had *no idea* how to make two monitors work under linux. X configuration is dark magic to me. Consequently the second monitor got shunted to my other machine and I've had a spare old monitor kicking around for a while. However, my computer recently died and I had to reinstall, and in doing so and poking around with video settings I discovered that the "nvidia-settings" program includes support for making multiple monitors work flawlessly. A few quick clicks and I had the two monitors working side by side very nicely. Yay! I do however note that Gnome doesn't handle them that well. This will probably induce me to finally get off my ass and try a better window manager. I tried Enlightenment earlier, but E16 didn't work, the repository version of E17 is kinda unstable (not to mention Enlightenment is *really confusing*, but I'm sure I'd get used to it) and I haven't quite worked up the courage/botheredness to install the CVS version yet. Anyone know what a good window manager is for use with xinerama? Should I be giving XMonad a try?

Best error message ever

"The program 'apt-get' is not currently installed. You can install it by typing 'apt-get install apt'"

I Aten't Dead

Surgeon General's Warning: This post contains an excess of hyperlinks. There is anecdotal evidence that excessive linking may be hazardous to your health. I'm still here. :-) I've just been busy with my new job at Trampoline Systems and non-code things. On the computer front, I've been learning (a bit) about spatial data structures and graph algorithms, mostly for work related reasons although also for personal interest. Tinkering with Haskell continues apace - I've been finding that it's a very good language for thinking in, even if I don't write anything big in it. The Lazy Strings project may look like it died, but fear not! It continues. Ok, you probably didn't care either way, but still it continues. I've decided that a) Life is too short to write it in Java and that b) I should just pick an implementation and stick to it. Consequently I've moved to Scala, and have the basics of an implementation based on a finger tree, rather than the traditional balanced binary tree used in a rope. Why a finger tree? Well, umm. Because. :-) Finger trees have nice performance characteristics, are easy to implement, and seem well suited to the task. The version I'm using is very heavily specialised to the task at hand, and measures a number of things up front (currently just length and hash code) to improve performance and allow for various nice optimisations. The main thing to note is that I've been using scalacheck to test properties of the string. It's been a great help. I've not found it that useful for actually tracking down the specifics of the bugs - its error reporting isn't that great - but it's been very useful for showing that they exist and providing enough of a general area that I can track them down myself. The fact that Scala has a REPL has been very useful in doing enough experimentation to pin it down. The utility of these will come to no surprise to those functional programmers reading my blog. :-) Scalacheck isn't quite as nice as Quickcheck and the Scala REPL isn't as nice as most of the ML ones (it's better than ghci though), but they're both good enough, and it's nice having these in Scala. Scala itself I continue to have mixed feelings about. It's a little too Java like. I very much like what it's done with the object system (first class modules. Yay!), and about half of what it's done with the type system, but the whole effect still feels kludgy to me. It's definitely infinitely better than Java though, and doesn't fall much short of being as pleasant as an ML (it's better in some ways, worse in others).

Lisp tutorial

In a good cause... I must admit I haven't gotten around to reading it yet, but Practical Common Lisp looks really quite good, and is available online for free. Definitely a lisp tutorial worth reading.

How to create sealed classes in Java

As far as I can tell, no one else seems to have spotted this trick, so I thought I'd share my latest corruption of the Java language: public class Sealed { private Sealed() { } public final static class Foo extends Sealed { public Foo() { } } public final static class Bar extends Sealed { } } What does this code do? It creates a class Sealed which is *not* final, but only has a finite number of subclasses which you determine at compile time (you can make those subclasses themselves extensible if you want, although I declared them final above). No one else can subclass it because they're not able to call the super constructor as it's not visible outside of this class.

Tail call optimisation in Scala

This is just a quick note. I couldn't seem to find any good information on what sorts of tail call optimisations were performed by Scala so I ran a few quick tests. Disappointingly, the answer seems to be not much. A simple tail recursion was turned into a loop, but the following code got no love: object Main extends Application{ def foo (x : Int){ if (x == Integer.MAX_VALUE) Console.println("Hello world!"); else bar(x + 1); } def bar (x : Int){ if (x == Integer.MAX_VALUE) Console.println("Hello world!"); else foo(x + 1); } foo(0); } This isn't really surprising, although it's a bit sad. Eliminating general tail calls seems to be quite hard without just converting everything into CPS and making everything work that way (at least so I'm lead to believe. My expertise on the subject is basically nonexistent), which is probably not a great idea on the JVM. Curiously, if you enabled optimisations with -XO, foo was inlined into bar but the resulting tail recursion was not eliminated. That's probably a bug. Update: It's been pointed out to me that I've gotten myself completely confused on the relationship between continuations and tail call elimination. Please ignore any mumbling to that effect. :-) The issue is apparently that TCO is easy when compiling to assembly and hard when compiling to something like JVM byte code which is higher level and doesn't already support it.

Good APIs

At least in the Java world[1], good APIs are very rare. The vast majority of the APIs I've used in Java are at best mediocre, and I've run into some real stinkers (No fingerpointing here, but a lot of them are even in the standard library!). Part of this is the fault of the language. Java code... tends to be ugly. It's not a language which lends itself to really flexible syntax, and so you have to work really hard to produce powerful abstractions which are actually nice to use. The only APIs I've encountered so far which have really made me sit up and go "Wow, that's well designed" are Google Guice and Joda time. They have well thought out class hierarchies, good object oriented style[2], sensible use of fluent interfaces / method chaining and just generally well thought out interfaces and names. They're not perfect by any means, but they show promise that it really is possible to write good APIs for Java. Anyone else know of other similarly well designed libraries? [1] And, unfortunately, I lack much in the way of non-trivially large development in other languages. The Parsec API is nice, 'though it gives me a headache sometimes. Haskell libraries in general look rather pretty, though I suspect that's more a function of the language than the API design. I'm not really experienced enough in it to judge good API design. [2] I'm not an OO fanatic. It has advantages and disadvantages, and sometimes you just want to use a different approach (I rather like FP for example). But one thing I've observed is that if you do it right, OO can have the effect of producing some astonishingly readable code. I don't know either well/at all really, but this style of design seems much more common in Ruby, smalltalk, etc.

Looking through other peoples' code is fun

I'm playing with the google guice code at the moment. It's very interesting, and contains some quite neat tricks (although is rather short on documentation so I'm getting very confused). But that's not what this post is about. I just wanted to share the following fun snippet. :-) // TODO(kevinb): gee, ya think we might want to remove this? private static boolean allowNullsBadBadBad() { return "I'm a bad hack".equals( System.getProperty("guice.allow.nulls.bad.bad.bad")); }

Birds of a Feather and AMQP

Minor announcement in case anyone who lives in London actually reads this thing. :-) Alexis mentioned to me at wednesday's London HUG that he's giving a Birds of a Feather talk on AMQP at No Fluff Just Stuff next week. It looks quite interesting. If you don't know, AMQP is a newish protocol for application level messaging. One of the big implementations out there (which is the one Alexis is involved with) is RabbitMQ, which is written in Erlang (which is how I got interested in the subject in the first place). By the sounds of it, they've been doing some quite fun and useful things with it. This should definitely be an interesting talk and I highly recommend coming if you're in the area.

The world has gone mad

Here is the proof: vv.getRenderContext().setVertexLabelTransformer(MapTransformer.<Number,String>getInstance( LazyMap.<Number,String>decorate(new HashMap<Number,String>(), new ToStringLabeller<Number>()))); Update: I've found a better example.

Data structures in Java

I've been playing with implementing some simple data structures in Java, for later use in the lazy strings project. The results are... a bit depressing, frankly. Clearly I need to learn to optimise better, as right now I'm creating specialised data structures for certain types which turn out to perform worse than the general purpose implementations in the standard library. :-) In particular, I threw together a simple implementation of a Trie, and it performs significantly worse than just using a TreeMap. As the number of collisions increases the relative performance of the Trie improves somewhat, eventually beating the TreeMap, but still in most situations the performance is pretty poor. It also doesn't help that the Trie ends up bloating the keys significantly, as you end up having to create far too many objects per character. I can definitely cut back on the object creation, but even one object per character may prove to be too much to get an efficient implementation in Java.

Playing with Arrows

Apologies in advance for the quality of the html blogger seems to be generating. I probably need to find a better solution (like using lhs and attaching pdfs or something). In the recent discussion about run length encoding, one thing people focused on was the use of the &&& operator and how noone understands arrows so &&& is scary and arcane. I feel perfectly placed to comment on this, because I don't understand arrows either. :-) I cheerfully abuse the arrow operators for their function instance without really worrying about that, and it seems to work fine. So, this is just a rundown of what the arrow operations do for the function instance, in order to make them seem less scary. I might follow up with looking at Kleisli arrows later (which are arrows that arise from monads in a natural way). The arrow class is defined as follows:

class Arrow a where
arr :: (b -> c) -> a b c
pure :: (b -> c) -> a b c
(>>>) :: a b c -> a c d -> a b d
first :: a b c -> a (b, d) (c, d)
second :: a b c -> a (d, b) (d, c)
(***) :: a b c -> a b' c' -> a (b, b') (c, c')
(&&&) :: a b c -> a b c' -> a b (c, c')

The first two are totally uninteresting for functions (they're just the identity). So if we cut those out and specialise the signatures to functions we get the following:

(>>>) :: (b -> c) -> (c -> d) -> (b -> d)
first :: (b -> c) -> (b, d) -> (c, d)
second :: (b -> c) -> (d, b) -> (d, c)
(***) :: (b -> c) -> (b' -> c') -> (b, b') -> (c, c')
(&&&) :: (b -> c) -> (b -> c') -> b -> (c, c')

i.e. these are basically all operators for manipulating combinations of pairs and functions. Most of these you can probably infer the purpose of from their types and names, but I'll go through them anyway. We've already encountered &&&, and it's the one I use the most, so I'll go through these in reverse order. The &&& operator is in fact very simple, but it's the arrow operator I use the most. Consider the following:

> (+1) &&& (+2) $ 3
(4, 5)

i.e. f &&& g when applied to x just evaluates both and returns them as a pairs of both results. We could define this as:

(&&&) :: (a -> b) -> (a -> c) -> (a -> (b, c))
(f &&& g) x = (f x, g x)

For example, in the run length encoding article we had the function head &&& length:

> head &&& length $ [1, 3]
(1,2)

In a similar usage to the RLE article, I've often found the following sort of trick useful:

map (head &&& length) . group . sort

This counts frequencies of elements in a list.

> map (head &&& length) . group . sort $ ["foo", "bar", "foo", "baz"]
[("bar",1),("baz",1),("foo",2)]

Now ***.

> (+1) *** (+2) $ (3, 4)
(4, 6)

i.e. f *** g applied to (x, y) returns (f x, g y). Or, in a more readable form:

(***) :: (b -> c) -> (b' -> c') -> (b, b') -> (c, c')
(f *** g) (x, y) = (f x, g y)

I don't really have an obvious use case for this one. I'm sure they exist though. I'm going to pick up the speed now, as I'm getting bored and so you probably are too. :-)

(>>>) :: (b -> c) -> (c -> d) -> (b -> d)
(f >>> g) x = g (f x)

Or in other words, >>> is just reverse function composition. So we could have written this as

(>>>) :: (b -> c) -> (c -> d) -> (b -> d)
(f >>> g) x = g . f

Or

(>>>) :: (b -> c) -> (c -> d) -> (b -> d)
(>>>) = flip (.)

Now for first and second:

first :: (b -> c) -> (b, d) -> (c, d)
first f (x, y) = (f x, y)

second :: (b -> c) -> (d, b) -> (d, c)
second f (x, y) = (x, f y)

i.e. These just take a function and apply it to the first or second entry of a tuple, leaving the other unchanged. Those are all the core arrow operations. There are a few derived operations, but the only one which is at all interesting for functions is <<<, which is just function composition. Another Arrow related class which functions are an instance of is ArrowChoice. ArrowChoice does for Either what Arrow does for pairs (blah blah, category theory, blah, (,) and Either are dual, blah). Here's the instance declaration:

class Arrow a => ArrowChoice a where
left :: a b c -> a (Either b d) (Either c d)
right :: a b c -> a (Either d b) (Either d c)
(+++) :: a b c -> a b' c' -> a (Either b b') (Either c c')
(|||) :: a b d -> a c d -> a (Either b c) d

Specialised to functions:

left :: (b -> c) -> (Either b d) -> (Either c d)
right :: (b -> c) -> (Either d b) -> (Either d c)
(+++) :: (b -> c) -> (b' -> c') -> (Either b b') -> (Either c c')
(|||) :: (b -> d) -> (c -> d) -> (Either b c) -> d

Lets jump straight to writing out some definitions:

left :: (b -> c) -> (Either b d) -> (Either c d)
left f (Left x) = Left $ f x
left _ (Right y) = Right y

right :: (b -> c) -> (Either d b) -> (Either d c)
right f (Right x) = Right $ f x
right _ (Left y) = Left y

(+++) :: (b -> c) -> (b' -> c') -> (Either b b') -> (Either c c')
(f +++ g) (Left x)  = Left $ f x
(f +++ g) (Right x) = Right $ g x

(|||) :: (b -> d) -> (c -> d) -> (Either b c) -> d
(f ||| g) (Left x)  = f x
(f ||| g) (Right x) = g x

i.e. left f applies f to the left option of an Either and leaves the right option alone.

> left (+1) $ Left 2
Left 3

> left (+1) $ Right 2
Right 2

right does the reverse. f +++ g applies f to the left option and g to the right:

> (+1) +++ (+2) $ Left 2
Left 3

> (+1) +++ (+2) $ Right 2
Right 4

So we could have implemented left and right (and indeed, this is how they're actually implemented in the real instance declaration) as follows:

left :: (b -> c) -> (Either b d) -> (Either c d)
left f = f +++ id

right :: (b -> c) -> (Either d b) -> (Either d c)
right f = id +++ f 

Or even as (+++id) and (id+++). Finally, (f ||| g) x is basically just a combinator for case matching, applying f if we have a Left value, g if we have a Right. It's just the standard 'either' function but it can be nice to have it available as an operator.

> (+1) ||| (+2) $ Left 2
3

> (+1) ||| (+2) $ Right 2
4

So, there you have it. Arrow operations. Not too scary, and now you have a bunch of new combinators to play with. I doubt it will revolutionise your Haskell code, but every now and then they allow for a really neat solution you wouldn't otherwise have thought of. Have fun.

Perversity

When you're programatically creating an abstract syntax tree in order to generate a text representation of a regular expression in order to parse it into an abstract syntax stree in order to compile it to a matcher object which reads your sequential list in a random access manner (causing you to have to fake random access behaviour with a mutable index into your list) in order to iterate over it sequentially... ...at this point the idea that someone, somewhere, might be doing something wrong starts to sink in.

Where lies the problem?

The intersection between my facebook friends and people who read this blog is probably (relatively) large, but for completeness and historical record I'll post my current facebook status: "David is considering at what point he should start to wonder whether the problem might not be with the rest of the world." I get into a lot of arguments, or at least heated disagreements. Sometimes it's because I'm wrong, but most of the time it feels like the world has reflexively thought "Oh, David has an opinion. Let's disagree with it!" This is very frustrating. Especially when I'm clearly right. Or, at the very least, when those I am arguing with are mouthing gibbering nonsense and ignoring my refutations of it. This isn't new either. It happens in whatever area I'm working. More so in programming than it did in maths, but I think that's a function of which side of the discipline I interact with more than it is of the discipline itself. Example points on which I've had arguments in ##java.

• First class functions are a good thing.
• Java's type system is crap.
• Random access strings are a poor design choice for an immutable data structure.
• The non-trivial import features Java provides (* and static imports) are actually a good thing.
• JEE is bloated nonsense (ok, only about half of ##java disagrees with me on this point).
• Large scale ORM is a stupid idea, and causes the most amazing amount of grief.
• XML may be standard, but it's still a rubbish format and should be avoided at all costs (*waves to the RSS readers*).
• Most recently (and inspired by this) the minor suggestion that being allowed to override void methods with non-void ones would be useful (response: Garbage arguments as to why this would be horrificially wrong and unsafe. It's not.).
• Endless stylistic arguments that basically boil down to "Why the Java standard approach of writing procedural code and calling it object oriented because it lives in a class is a bad one".
• Endless philosophical arguments that basically boil down to "Why 'That's not OO' is the most useless criticism of an approach in the history of programming".

As per the earlier quote, eventually I have to start wondering whether the reason I disagree with everyone might just not be because everyone else is wrong. But then I come to my senses. Firstly, these are mostly Java programmers. There are certainly competent Java programmers, but the average Java programmer is the very definition of blub. "Oh noes. It's an anonymous function? What's a function? How do I write that with a for loop???". Even the good ones tend to be very set in their ways. Admittedly some of these arguments are with people who I'd otherwise have believed to be competent. However I'm going to perpetrate a no true scotsman fallacy^H make a highly reasoned distinction: If they were competent, they wouldn't be spouting nonsense and then ignoring a detailed explanation of why they were wrong. Secondly, the state of the the world in general and of technology in particular gives me irrefutable empirical evidence that the vast majority of people are idiots. It therefore stands to reason that a sizable proportion of the people I interact with are idiots. Not coincidentally, I get into arguments with a sizable proportion of the people I interact with. So, in conclusion, I am correct. The problem is not with me, it is with the rest of the world. I should stop letting the opinions of idiots bother me. By the way, this is not a deliberately over the top rant. You may be tempted to think that I'm being tongue in cheek or making some metaphorical or otherwise not entirely serious point with this post. I'm not. Deal with it.

A quick check

Just trying something out for a friend, don't mind me.

This is a test.

I fail miserably at performance testing

I've now standardised my test cases to give a consistent test for each of the three options I'm playing with:

Beginning test cases...


Testing name...

   append reader: StringBuilderAdapter took 11 millis.
   toString: StringBuilderAdapter took 2 millis.
   First run for StringBuilderAdapter took 13 millis.
   Second append: StringBuilderAdapter took 5 millis
   toString: StringBuilderAdapter took 9 millis.
   Second run for StringBuilderAdapter took 14 millis.

Testing name...

   append reader: JumpRope took 6 millis.
   toString: JumpRope took 20 millis.
   First run for JumpRope took 26 millis.
   Second append: JumpRope took 0 millis
   toString: JumpRope took 7 millis.
   Second run for JumpRope took 7 millis.

Testing name...

   append reader: TrefoilString took 11 millis.
   toString: TrefoilString took 18 millis.
   First run for TrefoilString took 29 millis.
   Second append: TrefoilString took 0 millis
   toString: TrefoilString took 8 millis.
   Second run for TrefoilString took 8 millis.

These numbers... are a little different than I'd previously believed. They shouldn't be taken as definitive though - annoying things like "If I change the order of the tests around then the JIT optimises differently and the numbers change" and other random factors make them very variable. Still, interesting points of note: I'm a lot closer to StringBuilder level performance than I'd previously believed. The adapter slows it down a little, but these numbers were pretty close to what I'd been seeing with StringBuilder before - it's the others that are much lower. For lots of small appends, StringBuilder is about twice as fast as my implementations (the numbers are really really variable). For single large appends the situation is reversed. There's not a lot of performance difference between my dirty but supposed to be faster and my nice high level implementations. It turns out allocation is cheap after all. Lessons to take out of this: I suck at performance testing and I need to set up some really extensive test suites if I want to get good performance numbers. Also, I should stick to a nice high level implementation and only worry about performance as a sanity check every now and then. Ho hum.

Beating StringBuilder? Hell no.

So, it turns out that StringBuilder is almost insultingly fast. It's very well written, does almost no allocation, and is almost certainly getting special help from the VM and JIT under the covers. Appending a medium sized string to it appears to be faster (when averaged over about 11000 appends) than allocating new objects! I'm almost tempted to try writing a mutable JumpRopeBuilder which does the same job to see if I can beat it (and I probably will anyway, but use it to generate balanced JumpRopes rather than optimise it for appends), but I think I'll restrain myself. I must remember that hte goal is to have a String replacement rather than a StringBuilder replacement, and as that this does pretty well - the appends are very fast compared to String append (the actual conversion to a string is a little slow admittedly - it takes 100-200 ms for a approximately 100k characters, and about half of that is the overhead of iterating over an unbalanced binary tree). And, unlike StringBuilder, this is totally thread safe by virtue of being immutable. Which reminds me, I should compare it against StringBuffer. Anyway, I should really start adding some actual functionality now. :-)

Lazy strings for Java

I've started yet another open source project, motivated by the fact that Java Strings suck. The aim is to have an efficient string implementation for Java which is optimised for a more sensible set of operations. It draws on ideas from Haskell and purely functional data structures, aiming to take advantage of the fact that the JVM's garbage collection and allocation are now ludicrously well optimised. At the moment it has a basic set of working operations. Unfortunately the performance for one of the crucial operation blows goats. It's very very slow for appending to the right of large strings, and causes outrageous memory overflows. smallString.append(largeString) is pretty fast (I measured it at about 50% slower than appending to the end of a StringBuilder when averaged over a medium large file). I know what the problem is though: A stupid list implementation. I tried to stick too closely to Haskell laziness and failed miserably because the JVM doesn't handle things like that well. I'm going to rewrite it in more idiomatic Java and with more careful attention to detail, and I hope to get the desired O(1) append in every case. I'm debating giving Nice another try and rewriting parts of this in it, particularly the list implementation - because of how I intend to handle it, it's the sort of thing multiple dispatch and functional programming would be *really* handy for. Update: Ok, maybe I don't know how to solve it. I'll put more thought into it and see if I come up with something. As an alternative plan, someone I know pointed me towards Ropes, which is an implementation of a very similar thing for C++ / C. Very likely worth my looking at for inspiration / porting.

Javascript

As you may know, Javascript is the world's most misunderstood language. As a language it's pretty nice - prototype OO, decent functional support, (almost) proper lexical scoping, etc. Some warts, but generally not too bad. But dear god is the web browser an awful platform to develop for, and some of this is Javascript's fault. The single threaded event model is a nuisance, it's really hard to debug, and everything just gets in the way of everything else to produce really non-trivial interactions which break everything. Attempts to layer libraries on top which make this less awful are definitely valid, and to some extent work, but they just add new levels of incompatibilities and grossness.

What's a monad?

It's almost traditional that people learning Haskell should write their own version of 'An introduction to monads'. I think it serves to teach the writer more than the reader, but that's fine. I've understood them in a way which I've not seen covered in the existing introductions, so I thought I'd get it down on 'paper'. Note that the point of this post is to demystify more than it is to enlighten - if you don't already, you probably won't fully understand monads by the end, but you hopefully will be much closer to the point where you can. Java has the foreach loop: for(Foo foo : foos) doStuff(foo); Fundamentally unexciting, but a nice bit of syntactic sugar. A common argument for adding 'closures' (really first class functions) to Java is that if they'd added them in in 1.5 they wouldn't have needed to add the forEach loop because it could be defined as a method. Here's an example in Scala:

package Demo;

object ControlFlow {
    def forEach[T] (iter : Iterator[T], action : T => Unit) : Unit = 
        while(iter.hasNext) action(iter.next); 

    def forEach[T] (iter : Iterable[T], action : T => Unit) : Unit = forEach (iter.elements, action);
}

Still fundamentally unexciting, right? It's just yet another loop. Except... it's not quite, is it? I'm going to give this its own line just to make sure the point is clear: When we introduced first class functions to the language, we gained the ability to define our own control flow mechanisms. This is Exciting. Scala introduces another neat concept, sequence comprehensions:

package Demo;

object ComprehensionTest
{
    def main (args : Array[String])={
        val bar = for {
            val arg <- args;
            val arg2 <- args;
            !arg.equals(arg2) }
            yield (arg, arg2);
        
        Console.println(bar.toList);
    }
}

What does this do? Well, it constructs an iterable object consisting of all pairs of command line arguments, omitting repeated pairs. So

> scala Demo.ComprehensionTest foo bar

List((foo,bar), (bar,foo))

We could do much the same thing with nested for loops, but it wouldn't be as nice. For very involved collection manipulation, comprehensions simplify life a lot, so their addition to Scala is a great boon. But we could have defined something very similar ourself. Here's a rewrite that doesn't use comprehensions:

object NoComprehension
{
    def guard[T](test : Boolean, value : T) = 
        if (test) 
            new ::(value, Nil)
        else 
            Nil;
    
    def main (args : Array[String])={
        val bar = args.flatMap(
            (arg : String) => 
                args.flatMap(
                    (arg2 : String) => 
                        guard(!arg.equals(arg2), (arg, arg2))))

    Console.println(bar.toList);}
}

In fact, these compile to very similar things. Scala would use filter where I defined and used guard. I used the guard because a) I think it's clearer and b) It supports my point. :-) So, what's going on here? The following is the definition of flatMap in the Iterable[A] class definition (See here). def flatMap [B](f : (A) => Iterable[B]) : Collection[B] Applies the given function f to each element of this iterable, then concatenates the results. So, let's look at the inner example first. args.flatMap ((arg2 : String) => guard(!arg.equals(arg2), (arg, arg2))) The anonymous function takes arg2 and returns a List, which is either [(arg, arg2)] or []. It then concatenates these lists together. So this has the effect of simultaneously pairing up the (arg, arg2) values and filtering out all elements for which the two are equal So for each value of arg we have a list of the right (arg, arg2) pairs we want. We now flatMap this over all of args, and get the full list we want. Easy, right? The higher order functions approach is much more flexible, but the comprehension syntax is a lot more readable (and concise). Especially if you come from an imperative background. How do we make the two meet? Now let's rewrite these examples in Haskell. First the higher order function one:

import Monad
import System

main = do{
    args <- getArgs;
    print $ distinctPairs args;
}

distinctPairs :: [String] -> [(String, String)]
distinctPairs args =
    args >>=
        \arg -> 
            args >>=
                \arg2 -> 
                    guard (arg /= arg2) >>
                    return (arg, arg2)

This looks almost identical to the Scala one, once you get over superficial differences in syntax. In particular we replace the method foo.flatMap(bar) with the operator foo >>= bar. It does exactly the same thing (well, the type signatures are a bit different, but in this instance it does exactly the same thing). The 'guard' method is a little different, as we're using Haskell's built in function of that name. This is basically what it does: guard :: Bool -> [()] guard True = [()] guard False = [] (This is again not really correct. It's a correct definition in this instance, but the real definition is more general). What >> does is: (>>) :: [a] -> [b] -> [b] foo >> bar = foo >>= (\_ -> bar) You may find this a bit confusing, so I'll unpack the definition with a quick reminder. \_ -> bar is an anonymous function which takes anything and returns bar. So foo >>= bar concatenates together one copy of bar for each element of foo. i.e. it's length foo copies of bar joined together. In particular guard test >> bar is either [] if test is False or bar if test is true (as guard has length 0 in the first case and 1 in the second). return is very simple. return x = [x] So, guard test >> return x is the same as guard(test, x) in our Scala method. Still with me? Now, how do we write this so it looks like a Scala comprehension?

import Monad
import System

main :: IO ()
main = do{
    args <- getArgs;
    print $ distinctPairs args;
}

distinctPairs :: [String] -> [(String, String)]
distinctPairs args = do{
    arg  <- args;
    arg2 <- args;
    guard(arg /= arg2);
    return (arg, arg2)
}    

Looks almost exactly like the Scala version, doesn't it? At this point you might feel cheated if you've not seen 'do' notation before. "So... the point of this article is that Scala has these cool things called sequence comprehensions, and Haskell has them too? Who cares??". Now, look up there a little bit. For convenience, I'll repeat it here:

Main :: IO ()
main = do{
    args <- getArgs;
    print $ distinctPairs args;
}

What's that got to do with sequence comprehensions? Well, nothing. It turns out that this set of operations '>>=', '>>' and 'return' is so useful that Haskell has bundled them into their own type class, called Monad. So these apply to any type in this type class, including both List and IO, as well as many others. You can then apply do notation to an monad, and it just gets converted into a use of these operations in more or less the same way that we went from the list comprehension to the higher order functions. It works like this:

do { foo } = foo, for foo an instance of the monad.
do { foo; bar; baz } = foo >> do { bar; baz }
do { myFoo <- foo; bar; baz } = foo >>= myFoo -> do{bar; baz} 

(note that the last one puts myFoo in scope for bar and baz, so we can use it in their definitions exactly like we'd expect). Why bother giving this special treatment to monads? Well, it's the same reason as the foreach loop was introduced - they crop up *everywhere*. It turns out that (for reasons I won't go into here) you can realise the most outrageous range of programming idioms as instances of Monad. But doing so gives you somewhat clunky syntax, so the do notation exists to make that nicer. That's all it is. So, what's a monad? Nothing special. It's a type class which gets some preferential treatment from the language because of its ubiquity. It contains some standard operations which map quite well onto common forms of control flow, so it tends to crop up quite a lot. That's all.

Functional programming lies

I like functional programming. A lot. I find it an extremely natural mode of thinking in many respects, and even in imperative programming a sprinkling of functional support helps a lot. There are many practical advantages to it as a discipline. So why are some of the main reasons advocated by people who don't know what they're talking about (a category in which I do find myself grouped more often than I'd like) complete lies? In particular: "Because Haskell is a pure language the compiler can automatically memoize functions for you". No it can't. It would be nice if it could magically infer when it was able to do so, but it doesn't. Lazy evaluation causes enough memory issues without automatically memoizing things. I'm not aware of any Haskell compiler which does this, and GHC certainly doesn't. (As an added annoyance, there's no nice way of memoizing a function at all). A related lie is common subexpression elimination. Haskell doesn't have side effects, so you don't need to worry about that aspect of CSE, but it does have lazy evaluation. Partially evaluating a term has the 'side effect' of increasing its memory footprint significantly, so CSE can result in some very large space leaks if you're not careful. Other more minor lies include implicit parallelisation - it's not there yet, there are some suggestions (which I've not personally evaluated so cannot comment on the veracity of) that it's not nearly as plausible as we'd like it to be. Advocacy isn't a bad thing, but please stick to the facts.

JTypeBuilder and APT

I've just replaced the old parser based approach too JTypeBuilder with an annotation processing tool. It's currently very sketchy, but the code it produces now compiles, which is enough for me for the moment. :-) Basically the idea is that you have an abstract class that looks something like the following:

@TypebuilderTarget
public abstract class Test
{
   public abstract String getFoo();
   public abstract Badger getMushroom(); 
}

The type builder then extends this with the skeleton, filling in the implementations. Next steps include tidying it up (it needs that really really badly. The code that's curently there is basically just what I hacked together while figuring out APT), figuring out how to hook this up into the autodiscovery feature of annotation processing tools, and improving it so it only overrides equals, hashCode and toString if you declare them abstract. After that I have a bunch more annotations I intend to add in order to customise the behaviour and add extra functionality.

Equal opportunities oriented programming

There's a common feeling I get when programming in Java. "Shit. I can't do that. Methods aren't first class citizens". The same holds (in greater generality) for types, code, macros, tables and a variety of other things. Some of these problems have solutions in the works. First class functions have of course been around for ages, dependent types are giving us first class types, multi stage programming gives us first class code and macros. Not sure about tables, but that's probably because I don't know enough database theory. Common theme here: Anything which is not a first class citizen in your language will at some point become a pain when you want to manipulate it as one in order to get the right abstraction for your problem. I wonder how far we can get around this? Certainly the various lisps seem to come the closest, but I'm not sure they go far enough.

Tail call optimisation in Javascript

I just happend across this old link Basically it's a (surprisingly elegant) way of creating tail call optimised functions in javascript. There's a slight subtlety with it unfortunately - you can't simultaneously have a function call itself in a non-tail recursive manner. If you do it will break things. It claims to support mutually recursive functions, and I think this is true, but I bet you'll find there are some finicky details which can cause the stack to grow unboundedly before the optimisation kicks in, and I think you might have trouble properly optimising mutally recursive calls in this manner. Still, very cool.

Viral XKCDing

Pardon me while I maliciously subvert a viral marketing campaign. :-) THE ALGORITHM CONSTANTLY FINDS JESUS THE ALGORITHM KILLED JEEVES THE ALGORITHM IS BANNED IN CHINA THE ALGORITHM IS FROM JERSEY

Blatant and malicious evil

From freenode ##java: 10:13 < DRMacIver> cybereal: Oh, I figured out how to work around the Java type system to make my generators work. It requires a bit of a rearchitecture though. 10:13 < DRMacIver> It's blatant and malicious evil I'm afraid. :) 10:13 < cybereal> That seems to be the way of things for you lately

More JTypeBuilder

No further work done on it at the moment, but that's because I'm rethinking its architecture. Rather than building a DSL, I think it's much more sensible to use abstract Java classes as the templates, with the generated classes subclassing a user defined abstract class and the abstract methods and annotations defining which methods are going to be generated. This will let me switch to a more APT centric approach. I'll probably start using apt-jelly for this, as it works quite well with the existing freemarker based approach.

Job applications

It has occurred to me that this blog is eminently findable when starting from my name, and that consequently the companies who I'm interviewing with at the moment will no doubt see several rather annoyed rants on computer related subjects attached to said name. Rather than retract these, I wish to quote the words of a great man on this subject: (Hotlinking done with permission) I do hope the existence of these rants doesn't put you off. If it does, then we're probably not compatible anyway. Sorry. David

Static vs. Dynamic Typing

Rah. Dynamic typing is evil. It lets you do totally unsafe things. Err, no. Wait, that's not right. Static typing is evil. It's ugly and gets in the way and real programmers don't make type errors anyway, do they? Are you saying you're not a real programmer??? No, wait. Umm... I'm so confused... Want to know what I really think about static vs. dynamic typing? (no you don't. I'm going to tell you anyway). I wish the entire goddamn argument would go away. Seriously, shoo. Buzz off. There's no reason there should be a one true language in which you do everything. None. Sometimes language Foo is better, sometimes language Bar is better. Given this, there's no reason Foo can't be dynamically typed and Bar statically typed. Neither is better. Each have their strengths and weaknesses. People have their preferences, tasks have their requirements. Sometimes you're better off choosing one or the other, sometimes you're more comfortable choosing one or the other. When there's a compelling reason to make a decision between the two (which is so much less often than the fanatics on both sides of the argument want you to think), follow that reason. When there's not, use whichever you prefer. But, in the mean time, shut the fuck about it. Far too many good and interesting discussions about languages turn into poo flinging between the type system monkeys. Shut up, grow up and get over it. There are more interesting things to talk about in the subject than whether certain operations should fail at run or compile time. That is all.

Concision

Warning: This post contains rant and is short on actual reasoned arguments. There are a number of things that are often considered bad practice in Java. These include static imports, star imports, shadowing, omitting braces, notUsingReallyLongVariableNames, etc. Also, many Java developers object to features like first class functions, operator overloading and type inference, because they might 'overcomplicate' the language and cause people to produce unreadable code. Given that this is a post about concision, I will now shorten the above rules into a single rule: It is bad practice to do anything which might cause you to write less code. "Oh." says the (hypothetical - I don't think anyone actually reads this blog) reader, "Another whiner who doesn't like typing. Just use an IDE!" This is not about typing. I know perfectly well that the IDE can do 'typing inference' (so to speak). This is about reading. Making your code more verbose does not make it more readable. In many cases it makes it less readable because you're hiding the actually important stuff inside layers of crap. Further, even when all of it is relevant, expressing it in an overly verbose way makes it much harder to take in. Even ignoring the functional programming argument, I think the Java community and conventions would gain a lot by losing their fear of terse code.

Yet more JTypeBuilder

Well, I've not done a *lot* of work on it since I last posted, but there are a few improvements. In particular the parser has been sanitised and expanded, support for generics has been (experimentally) added, and I've actually used the project in anger. It's currently insufficiently expressive to do most of the things I want, so I've been engaged in the great evil of editing generated code - using JTypeBuilder to generate *most* of the boiler plate and then adding my own bits of code to fix things. I'm probably going to have to replace the code generation entirely at some point. Freemarker is very nice, and there are a lot of things I'd consider using it for. I'm not sure a compiler backend is one of them.

Baby's first open source project

I've decided to start a new personal project, and I'm going to make it open source from day one. The project is called JTypeBuilder and is hosted at Google Code and released under an apache 2.0 license. The basic idea is that it is used for generating data models and producing an awful lot of associated boiler plate code. It produces immutable classes for representing the data, mutable classes for generating the immutable ones and methods for passing back and forth between them. The immutable classes all have the obvious equals and hash code implementations, as well as a toString method which produces a JSON like representation of the class. It currently just consists of a couple freemarker templates and some simple wrapper code for them. When I get around to it I'll add a parser and command line interface for nice representation of the data models. I have vague intentions of using this for some sort of simple ORM package. Another possibility is using it as part of a compiler backend for targeting the JVM - it can be used to generate the data types. All of this is in the future though - right now it's simply a tool for reducing boiler plate code (and a fairly incomplete one at that). Update: Phew. That was a succesful day. The parser and code generator now work, and are hooked together with an extremely rudimentary command line interface (it's little more than a proof of concept). Still to do are improvements to the interface and customisability, as well as general improvements to code generation and parsing. Nonetheless, there is now a working tool there. Yay. Actually, come to think of it, the biggest thing that needs fixing at the moment is the build.xml. It's a really shocking piece of spaghetti XML put together with the intent of having something working quickly rather than actually producing a portable build script... Lots of hard coded paths.

What's in a syntax?

I was looking at JGA earlier. Basically yet another instance of the JGreenspun pattern. I have my own implementation of the same sort of thing - JGA looks significantly better than mine frankly. But, even with a nice terse syntax, the kind of shenanigans one has to go through to make it work are pretty horrible. Take a look at some of my code snippets if you don't believe me (granted the snippets I had are not very terse, but due to heavy use of anonymous inner classes one is pretty stuck with using constructors, which with abundant generics quickly leads to some really horrible lines). Although you can get most (well, about 75%) of the functionality of a functional language like ML or Haskell into Java if you hammer enough, the result is fairly mindly blastingly horrible. Shorter syntax for declaration of anonymous inner classes would certainly help a bit, but I don't think it's really going to be enough. I think that until closures come along to Java (and I mean proper BGGA style closures. Anonymous inner classes just aren't going to cut it) I'm going to have to revert to the way of doing things that doesn't involve too much greenspun. And/or defect to Scala completely.

Unexpectedly popular

Hmm. In keeping with google's recently acquired fascination with me, my stupid little parsec example appears to be the third from the top when you google for haskell parsec. I find this vaguely alarming.

re·cur·sion –noun: See recursion

I've just discovered the following interesting and related facts: 1) Chickenfoot's pattern matching is very error tolerant. If it looks for "Older posts" and can't find it, it will cheerfully settle for "Newer posts". 2) StumbleUpon histories only go back a few months. 3) When writing code, you should be really careful to avoid infinite loops. Sigh.

From the jargon file: Bogosort

bogo-sort: /boh`goh·sort´/, n. (var.: stupid-sort) The archetypical perversely awful algorithm (as opposed to bubble sort, which is merely the generic bad algorithm). Bogo-sort is equivalent to repeatedly throwing a deck of cards in the air, picking them up at random, and then testing whether they are in order. It serves as a sort of canonical example of awfulness. Looking at a program and seeing a dumb algorithm, one might say “Oh, I see, this program uses bogo-sort.” Esp. appropriate for algorithms with factorial or super-exponential running time in the average case and probabilistically infinite worst-case running time. Compare bogus, brute force. A spectacular variant of bogo-sort has been proposed which has the interesting property that, if the Many Worlds interpretation of quantum mechanics is true, it can sort an arbitrarily large array in linear time. (In the Many-Worlds model, the result of any quantum action is to split the universe-before into a sheaf of universes-after, one for each possible way the state vector can collapse; in any one of the universes-after the result appears random.) The steps are: 1. Permute the array randomly using a quantum process, 2. If the array is not sorted, destroy the universe (checking that the list is sorted requires O(n) time). Implementation of step 2 is left as an exercise for the reader.

fix f = let x = f x in x

One function in the Haskell standard library is 'fix', the least fixed point operator (a sort of generalisation of the Y combinator). As per the topic, the entire source code for it is: fix :: (t -> t) -> t fix f = let x = f x in x This is really awesome, but it took me a while to figure out how it worked. Let's take an example: g x = 1 : x ones = fix g This gives us an infinite list of ones. However, it's important to note that at this point nothing is evaluated. Suppose I wanted to evaluate head ones. How would the evaluation proceed? It would go as follows: head(ones) = head(1 : ones) = 1 No more of the argument is evaluated than needed. That's what laziness means. Now let's see how we use it as Y combinator. genfact f 0 = 0 genfact f n = n * (f(n-1)) (I'm aware my bracketing is non-ideal. I haven't quite got the hang of reading and writing Haskell in a normal style yet though) fix genfact 3 = genfact (fix genfact) 3 = 3 * ( (fix genfact) 2 ) = 3 * ( genfact (fix genfact) 2) = 3 * 2 * ( (fix genfact) 1) = 3 * 2 * 1 * (fix genfact 0) = 3 * 2 * 1 * (genfact (fix genfact) 0) = 3 * 2 * 1 * 1 = 6 Neat.

Speling is important

Or, in other words, why you have to check for a 'referer'.

Javascript 'with' clause

I encountered a neat little feature in javascript recently. Javascript has things that look like global variables. They're not. What they *actually* are is fields of the global object. The following syntax lets you write a bunch of code that uses a different global object: with(foo) { // do Stuff } Has foo as the global object inside the braces. Well, almost. There's a caveat. Try the following in Rhino or Spidermonkey: foo = { bar : 2 }; with (foo) { baz = 3; } print(foo.baz); It will print "undefined". But if you do print(baz) It will print 3. Huh? What's going on? This is how javascript scope works. The assignment "foo = bar" will not find the identifier 'foo' bound, so will fall outwards into enclosing scopes until it finds a scope which does bind it, stopping at the top level scope (and corresponding global object) if it doesn't find any. It's kindof annoying, but it does make sense. Further it's more or less how it has to work given the combination of Javascript's soft objects and lexical scoping. With this caveat borne in mind, the 'with' method is quite cool. I shall try and find an excuse to use it in future. :-) (I encountered it via Chickenfoot, where it seems to be useful for loading other pages in the background and applying chickenfoot methods to them). Update: Apparently this is deprecated and considered bad practice, as it's difficult to optimise and leads to some non-intuitive issues with scoping. Oh well.

Cool Gadget of the Day: JTidy Servlet

JTidy is a port of w3's HTML Tidy. It's basically an HTML validation and pretty printing library. JTidy servlet provides tools for using it in a servlet container. So, why is this cool? Well, jsp tags produce really awful whitespace. It makes looking through your generated markup almost impossible. JTidy servlet provides you with a drop in filter which you can just add to your site and cause all outgoing html to be pretty printed, making it readable. It's about 4 lines of XML and two jars on the classpath and everything just works.

Cool gadget of the day: Chickenfoot

You're probably not use the Chickenfoot Firefox extension. You really should be. It's basically an extremely cool API and plugin for writing user scripts (similar to Greasemonkey, only awesome), with very clever pattern matching for finding the relevant elements on the page, which has always been the most annoying thing with writing user scripts. I originally found it via digging through google techtalks. The original techtalk is here (it's quite long). Also, here's a useful snippet for making it less annoying to use from the keyboard. It's not mine - the first part is due to Rob Miller and the second is a trivial adaption of the first. It is however really rather handy.

Enforce your invariants damnit

We have a problem at work. We've done the live release, and now all the bugs are rolling in, merrily slaying kittens as they go. You know what I inevitably find they're caused by? Well, other than multithreading, improperly tested clustering, those goddamn EJBs, Spring MVC... err. what was I saying? Oh yes. They're caused by improperly enforced invariants. Things which should be true and which you rely on being true but aren't, because you never bothered to enforce them and someone fucked up. Sure, we could just not fuck up. After all [insert meaningless excuse here]. Doesn't work. Know why? It's because you're an idiot. Yes. I mean you, personally. Of course, so am I. Everyone is an idiot when at their worst, and do you really want to claim we all have perfect days? You've never had a hungover Monday or an exhausted Friday? People make mistakes. Any pretense that you can avoid this is asking for your project to fail. The correct response is to assume that everyone is going to make mistakes and include steps to deal with this. So, how do I enforce my invariants? The most common source of having too many invariants is redundant information. Choose properties which are orthogonal. For example, we have a boolean property on one of our objects, say 'foo', and a String bar. We failed to enforce the invariant foo == !(bar == null). But 'foo' is clearly a redundant property and the implementation of isFoo should simply have been { return !(bar == null); }. When you can do it this way, this is by far the best approach. It's easy, it's straightforward, and can potentially eliminate most of the invariants you need to preserve. Unfortunately the really hard ones to enforce don't work this way. So, how do we enforce the more complicated ones? For example, I have two properties foo and bar. Either of these may be null, but not both simultaneously (and both may be non-null). How do I enforce this? We're going to have to do it by inserting run time constraints. Compile time checking of invariants would be fantastic, but Java (and most similar languages) have piss poor support for this. You can probably manage some support with the annotation processing tool, but I don't know how and I doubt it's pretty. So, runtime constraints. This means that any code which might cause them to break should check. Note that this applies only to constructors and methods on the object which mutate the state of the object. If these are all invariant safe then so will be any method which invokes them. Key point in the above? If you don't have any methods which mutate state, all you need to bombproof is the constructor. There really is no excuse for making mutability the default. It has so many disadvantages. In particular, JavaBeans loaded with a set method for every private field are the work of the devil. This also combines very well with the thread safety advantages of immutability. Imagine the following code: if (myObject.foo == null) { // Some other nasty thread comes in and chnages foo to some non-null value and nulls bar. doSomethingWhichCountsOnBarBeingNotNull(myObject.bar); } Boom. Nullpointer exception. Sure, you should be synchronising on myObject. This would remove the problem. But why introduce an extra step when you can avoid the problem altogether? Anyway, suppose we really do want mutable state. How do we manage it? We still need to ditch those bloody set methods. In particular you cannot have a set method for both foo and bar on the above bean. Doesn't work. Why? Because we need to be able to do "myBean.setFoo(null); myBean.setBar(someObject);", which enforces the invariant perfectly well. Enforcing the order in which you do things would be a real nightmare, and for more complicated invariants would be flat out impossible. Methods which affect an invariant have to behave atomically with respect to the object, so need to be bundled together on the object. For example you could do "myBean.setFooAndBar(null, someObject)". Not the best of examples, but you get the idea. The point is that you can guarantee that any combination of methods invoked on the object will enforce the invariant iff the invariant held at the end of each method invocation. In fact, this is an example of why the anemic domain model antipattern is such a bad idea. In making your domain object nothing more than a mutable data structure which gets managed by other bigger objects you break encapsulation and scatter your manipulation code to the four winds, decentralising the code that needs to enforce the desired behaviour. Of course, taking it too far the other way can be dangerous too - if you have thousands of methods on your object which mutate state, you need to make sure every one of them is invariant safe. Another good way: use the database. If your object model is backed by a database (a practice I consider questionable, but very common), insert every constraint you can at the database level. Databasi suck in many ways but they also have a lot of good points, enforcing constraints is something they're very good at. Take advantage of this. In particular they're very good for enforcing uniqueness constraints, which are much harder to do at the object level. The constraints that are easy to enforce at the object and database levels are fairly complementary, so using both will ensure a very high coverage. Finally, sprinkle assertions and comments elsewhere in the code wherever an invariant is really important. In fact, I've just thought of a good way to do this - make your invariants public methods with a descriptive name. This means that your assertions can be very nicely structured like: assert(myObject.fooAndBarNotBothNull()); These should of course not be necessary, but add a level of self documentation to the code, and will help catch any places you've failed to enforce the invariants as early as possible (and add no runtime overhead in the live environment, if you worry about such things). If you follow all of the above advice then you will have eliminated a major source of bugs, and the kittens will thank you for it. Even if you only follow some of it, every bug caught early is a bug you don't have to fret about later.