Logan Campbell

I write about building web apps using FP. Mostly Clojure and ClojureScript.

core.typed Game of Life

02 Oct 2013

I wanted to see how core.typed would deal with annotating some of my production Clojure code. After hitting an issue with protocols, and spending all of 5 minutes unable to fix it, my gen Y attention span kicked in and I lowered my goals. Instead I wrote a plain Clojure solution to Conway's Game of Life and then annotated it with core.typed. Then got a friend to re-write it in Scala. Then re-wrote it myself in Haskell.

This should give you the 10,000 feet view:

If you want the details view the full image or the source on github.

The algorithm is mostly the same across solutions. It's not the best but it makes use of some intermediate representations that I thought would be interesting to type check. The core idea is that by merging overlapping neighbourhoods that have a some understanding of the world you eventually arrive at the truth. When there are key collisions the cells are merged and they become more and more accurate. For instance (cell false 1) and (cell true 0) merge to (cell true 1) and we know that the cell is alive and has at least one neighbour.

You can see that typed Clojure solution was the largest. But I don't think it's unreasonably large. I couldn't bring myself to do a Java version but I'd expect it to be several times larger. There are a couple of limitations to the local type inferencing that this example hit.

Firstly for loops must be replaced with the for> macro. This takes inline type annotations for the return type and each variable binding. There are a few more cases where you need to use special macros, but not many.

Secondly functions passed to higher order functions needed annotations. This meant I had to break my anonymous functions out into top level definitions. Ambrose has written about this situation but it's unlikely to be overcome in the near future.

Even with these limitations I think it's awesome that a dynamic language can have a type system added to it without needing any compiler extensions. If you do too then help support the development of core.typed.

comments powered by Disqus