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")); }

Testing, testing. Is this thing on? (Also, Cheesebread)

Good lord. There’s a blog here. I wonder how that happened? Whose is it? Mine, you say? Wow…

In keeping with my new enterprisey status, I’d like to begin this post with a little Q&A session.

Q: Why has David not been posting humorous cooking anecdotes?
A: Because he’s lame.

Q: What was David doing at 2:30AM?
A: Making cheesebread.

Q: Why on earth was David making cheesebread at such a silly hour?
A: His body has this really funny trick it plays on him. When he’s tired he thinks “Hm. I’m tired. I think I’ll go to bed early”. He does so and most unusually falls right to sleep. He then wakes up a mere three hours later still tired but totally unable to get back to sleep. On this particular occasion, after two hours of trying to sleep he decided to make use of the wonderful distraction that is the internet and upon repeated application of StumbleUpon found his way to an interesting looking recipe. Given that he’d recently been complaining about not doing any proper cooking, had all the ingredients to hand and suddenly possessed a great deal of spare time, a better question would be:

Q: Did David have anything better to do at 2:30AM than make cheesebread?
A: No.

David will now cease this bizarre affectation of referring to himself in the third person.

The recipe I used is pretty much taken from that post verbatim. I may be slapdash with other recipes, but you don’t fuck with bread or the bread mafia will come round to your house and break your kneecaps (also, worse, you’ll get lousy bread). I ended up adding about half a cup more flour, as the dough was looking very gloopy (I’m not sure why).

So, after a careful perusal of the recipe (for those just joining us, that means “I vaguely eyeballed the ingredients and ensured that I had all of them”) I set to work. I got all the ingredients out and put the oven on to preheat.

The astute reader will note that you do not need to put the oven on to preheat at the start of making bread, as it has to rise for over an hour.

The not so astute David took about 10 minutes to realise this before looking sheepish and turning the oven off.

Anyway, other than the mentioned gloopiness I followed the recipe fairly exactly. No comments there. I will add that when doing a quick eyeball of the ingredients you should also do a quick eyeball of the cooking implements, as I realised too late that this was a two tin recipe and I only had one bread tin. I ended up using the excess to make a small round loaf on the base of one of my other baking trays.

I also ended up being impatient and putting the small round loaf in after only half an hour of rising. I shall be prepared when the bread mafia come for me.

This stuff smells amazing while baking. Rather unsurprisingly, a combination of the smell of freshly baking bread and grilled cheese. Equally unsurprising, the impatient version of the loaf was too flat. Still tasted pretty good though, as the rapid vanishing of over half of it demonstrated.

The second one rose a lot more, so I’m expecting it to be a lot better, but I’ll wait ’till the morning to actually open it and find out. I’ll add an update then. For now, I’m going to go make another attempt at that sleep thing.

Update:

A little disappointing. The loaf seems to have collapsed overnight. It’s still a lot less dense than the trial version, but doesn’t have the really appealing consistency of the version I linked to. I think I should have let it rise for longer than I did (it was about an hour, but it might have been on the short side of ‘about’. Quite possibly I should have mixed it more vigorously than I did). Also, I think I should have used a sharper cheddar. Still, tastes great, and is light enough. I’m going to enjoy it. :-)

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.