The Blog of Josh Comer

Ordering Columns

One of my favourite things about Clojure, is constantly discovering new, and usually shorter ways of re-writing code. An example I discovered today has to do with maintaining a particular ordering in a map. When creating html lists using hiccup one needs to make sure the columns of the table all line up. This can be difficult when using a map since the ordering of a map is not defined.

Fear no longer, today I discovered sorted-map-by. This creates a map which maintains an order as defined by a comparator. So here is the easy way I came up with to keep a map in a particular ordering:

Clojure Talks

It has been awhile since my last post, life has been quite busy (as always). I thought that I should share some of the great Clojure themed talks that I have been consuming in my down time.

  • Dynamic Pricing through DSLs This talk by Amit Rathore takes an great approach to DSLs. His company Runa uses a DSL to alleviate the pains of enterprise customisation’s to their product.

  • Why Prismatic Goes Faster With Clojure This talk shows that Clojure can be FAST. I wish these libraries were open-source so that I could get a look at their inner workings.

  • Reducers – Rich Hickey I saved the best for last. This is the best talk I have watched in awhile. Rich does a great job of walking through reducers and explaining why they are important. I keep meaning to download the Clojure 1.5 beta and try these out for myself. In the Clojure programming that I have done it seems that the majority of maps and filters are not order dependent and therefore could greatly benefit from the use of reducers.

Episode 2 Drops

Finally, the moment over one month in the making, The Techsters Episode #2 is here!

Have a listen here.


Clojure Game Engine

I recently attended an undergraduate thesis presentation where one of the students created a javascript game engine from scratch. This got me to thinking, what would a Clojure game engine look like. I have played around with other Java gaming engines, such as Slick. Slick is a really easy engine to work with and lets you immediately focus on developing the game, not contorting the engine to work for your game. Since Slick is so great, why not just write a Clojure wrapper for it? The problem rests in Slick’s heavy dependence on the OOP paradigm. A wrapper would end up causing the programmer to “fight” Clojure at every turn as we sneak objects and, even worse, mutability into the engine. My goal is to have a game engine which embraces the ideals of Clojure.

The design which I have been building in my head is an entity-oriented engine (which I wrote about in a previous post). A world reference will be a bag for all the entities in the game. Entities would only contain their state, and their categorizations. For example you could have a player entity, and also have an entity for each projectile currently alive in the game. An interesting idea would be to make each processor of entities a different thread. This would impose the problem of not being able to deterministically order their execution, but the idea of creating a game based on independent modules seems intriguing. My goal is to create a highly concurrent gaming engine. A cool resource to check out is Rich Hickey’s famous ant demo which was used to demo Clojure’s concurrency in the early days of the language. It is pretty mind blowing how much simulation is packed into so little code (the whole thing is 300 lines, with comments and license).

The rendering and world updating will be done by two (maybe more) agents. Clojure’s wonderful STM will trivially (maybe easy is the better terminology :)) allow these tasks to be independent. I haven’t yet chosen what the renderer is going to be yet, but this will be a 2D engine, so for the minimal amount of effort it will probably end up being the Light Weight Java Game Library, which Slick uses underneath. The unfortunate part of this is that LWJGL requires the use of native libraries. An alternative option would be to also include Swing support, thus making the engine support cross platforms easily. I will have to research to see if the Canvas in Swing is performant enough.

This is all just thought development now, but I have the whole summer ahead of me. Maybe this will make a good project :)

The Techsters

So a couple friend and I have decided to start a new podcast called “The Techsters”. The main focus of the podcast is to be an entertaining discussion on all things technology.

You can check out our first episode here

Let us know what you think.

Median Finding and Incanter

Updated: made a mistake in the random algorithm… left out the random part :) all fixed now and the chart has been updated

Last week we were going over some median finding algorithms in class. To be honest I had never thought of this problem before. In class (before the algorithms were revealed to us) I jumped to the naive approach of sorting the list then grabbing the middle. This is obviously going to have the complexity of sorting, with best case O(nlogn).

We were presented with two algorithms, one random (selection by partitioning) and the other deterministic (median of medians). Both end up averaging a complexity of n, but the random algorithm has a worst case of O(n2). The funny thing is that the random algorithm massively outperforms the deterministic version. This is always an iterating situation, when the theoretically better solution ends up performing (when implemented) far worse than the theoretically worse solution.

Lets see how much worse the deterministic algorithm performs. I created an implementation of both algorithms:

Conveniently both algorithms have the same core, and the only difference between them is how they determine their pivot value. As the name suggests in the random algorithm, the pivot is chosen at random. In the deterministic version, the pivot is chosen to be the median of medians. Finding the median of medians is interesting as the recursions are intertwined, the median finding algorithm is called by the median finding function.

There are also some laziness optimizations sneaking in here as well. In the core, only the “less than” partition is fully realized. The “greater than” partition is only calculated when required, which is only when the median exists within.

Alright, so now I got to take my first attempt at using Incanter, the R-type library for Clojure. Incanter was really easy to use and I found the documentation to be very verbose (in a good way) and well written.

This is the analysis code I whipped up:

Which I used to produce the following chart:

Due to some strange “features” in Incanter, you have to jump through some hoops to get the groups to label correctly, so I left the legend off the chart. The blue points are the deterministic algorithm’s results and the red points are the random algorithm’s results. As you can clearly see from the graph, the random algorithm outperformed the deterministic one by at least one metric bunch.

Entity Oriented Programming

A few friends and I have undertaken a game project, and I get to be in charge of the technical side of things. I immediately thought of using Clojure (since it is only the best language ever), but changed my mind as my main criteria was a easy to use game engine (I’m lazy). I ended up choosing to use the Slick engine which is java-based. To supplement this Slick engine I have decided to use an entity based approach to programming the game. Artemis is an entity framework which was originally designed for use with Slick, but since it has no dependencies, could be used with anything.

The Artemis framework is based on a series of blog posts from T=Machine. The TL;DR of these blog posts is that an entity system in a gaming environment is very extensible and can be parallelised (the articles revolve around PS3 development, which needs done concurrently to take advantage of the hardware). Whilst I don’t have any immediate needs to delve into concurrent game development, this approach has a real functional smell to it (reminiscent to that of fresh baked bread), so it must be a good thing.


Now that TodoClj is done (unless I come up with some new features), it is time for a new project. A while ago a friend and I started messing around with the game of Go. It quickly became apparent that there are no good Go clients out there. The ones that do exist are extremely old, and either do not run on modern hardware, or are almost completely unusable. So the first step in creating a bearable Go client is to make an easy to use wrapper for the gnuGo client. By interfacing with gnuGo, one gets all the rule enforcement and AI for free.

I have decided to name my wrapper after one of the first (founded in 1612) Go houses in Japan, Honinbo. This should be a good chance for me to practice some meta-programming as the interface with gnuGo will take place using the Go Text Protocol (GTP).

As always, the source is checked into GitHub here

TodoClj 1.0.0 Is Done

I have finished the first version of TodoClj. Please check it out. Note that I have put almost no error checking into the parser, therefore things will crash if not perfect. Windows users should compile from source (to get version 1.0.1) since the ANSI codes used to colour the output do not render and the new version prevents colour from being rendered when run on Windows. If you have lein installed compiling is as easy as:

lein uberjar