Experience Report: A Mastermind Simulation in Lua, Java & Haskell

The source code for each version can be found here: https://github.com/eugenkiss/mastermind

Motivation

You might wonder why I wrote the same program in three different languages. The reason is that I wanted to experience the application of different programming paradigms on the same task in order to judge them more fairly. This experience report could have just as well been titled “Procedural against Object Oriented against Functional Programming Styles” or “Imperative against Declarative Programming Styles”. I acknowledge that the task is fairly small and therefore can only tell so much about a paradigm. On the other hand, it is large enough to encounter details and corner cases of each paradigm so it is still useful.

Background

I have written this simulation for a university project where Lego Mindstorms robots were supposed to play a variation of the game mastermind in an enclosed area. These robots needed a strategy, of course, and since there are several (classical) mastermind strategies a simulation to test these various strategies seemed like a good idea, particularly as it wouldn’t have been feasible to simply observe the robot using a strategy in real time.

As I was tinkering with Lua at the time I decided to write a first prototype of the simulation in Lua. Lua seemed like a good fit because it is a fairly paradigm neutral & lightweight programming language. Since the source code for the robots had to be written in Java I rewrote the simulation in Java. By then I had written a (hopefully) procedural and an (hopefully) object oriented version and since I was a beginning haskeller I devoted myself to rewriting the simulation in Haskell. I specifically wanted to observe how the explicit state/effect separation of Haskell helped in writing better & easier to reason about code because the most pervasive and malicious bugs in the Lua & Java versions were state/identity related. One of the plentiful motivations has been the paper Out of the Tarpit.

Analysis

I spare you the description of the task as it won’t make the following observations clearer and it is somewhat elaborate. If you are really interested have a look at one of the READMEs in the respective Github projects, you can find it there.

Lua & Java

What I liked about writing the Lua version was that there was so little overhead in concepts. You’ve got functions, some control structures, tables and that’s basically it. At the same time there were some annoying things. A common complaint about Lua is its relatively high verbosity - at least for a dynamic language. It’s true. Seeing long keywords like function or local everywhere hinders readability.

Just as Lua Java has the reputation of being overly verbose. In fact, Java is much more verbose than Lua so I shouldn’t really call Lua verbose in this context. On the plus side, using classes to encapsulate code made it easier to understand the structure of the problem despite the “cognitive overhead” of the class-based approach compared to the more minimal “function-approach” of the Lua version.

One shouldn’t underestimate the help of a static type system when refactoring code, too. In Java, refactoring was easy because the compiler complained if parts of the code didn’t type check so you were kind of sure that you did not break anything. Trying to refactor the Lua version almost always lead to subtle bugs that a compiler could have found and so could have saved me a lot of time.

Haskell

If you are not familiar with Haskell have a look at the deliberately uncritical Why Haskell Matters. Haskell’s most valuable virtue for this task is that Haskell is purely functional. That means, you must be very explicit in your code whenever using effects and therefore you are always aware if your change can alter effects or not. I find this approach very good and I felt that you start to think more precisely about problems because you try to reduce the “state variables” to the absolute minimum.

You should know that this has been my first “real” or rather independent Haskell project apart from small exercises. As the saying goes, the devil is in the details and even though the small exercises were very naturally solved in Haskell this particular task highlighted some problems with Haskell especially regarding laziness. To give you an example of Haskell’s beautiful side take a look at this definition:

-- | Create a list of all possible codes with a specific length.
createAllCodes :: Int -> Codes
createAllCodes 0 = [[]]
createAllCodes length = [ c:r | c <- buttons, r <- createAllCodes (length-1) ]

I think the code is pretty self-explanatory if you know Haskell a bit. The only thing you need to know is that buttons is a list of, let’s say, the colors in mastermind. At the same time there are some, I’d say, quite ugly definitions in my code. Somehow, however, I suspect that they could be rewritten in a better style if I was more experienced - or maybe even not.

Generally, I like Haskell’s type system. Even though sometimes I couldn’t understand the error messages immediately the type system often unveiled bugs. Furthermore, adding type definitions makes the code self-documenting.

As mentioned, I was/am a Haskell beginner. Nonetheless, I hoped writing the simulation in Haskell would have went smoother. E.g., I did not fully understand the State Monad when I first used it. Also, I had some problems utilizing the, for me new, functional paradigm.

On the plus side, I encountered less bugs. Actually there were only two off- by-1 runtome errors when using head and !! and a devious infinite mutual recursive loop. Now is a great time to say this: Haskell & its type system is no magic dust. It can help you extensively but it cannot do everything as it is sometimes preached. There are, however, extensions to Haskell like dependant types which, I think, could have prevented the off- by-one errors at compile time by specifying that e.g. a list cannot be empty or that two lists for a function must have the same length. Now that I think about it I did a wrong conversion from seconds to milliseconds in both the Java & Haskell version. This could have been prevented by associating units with types but perhaps it would have been overkill. As you can see, I can count the bugs in the Haskell version on one hand. Yet, there were other annoyances. Let’s have a look at Haskell’s warts.

First of all, the record syntax is tedious, very tedious. There are extensions that make it easier like RecordWildCards but still. Granted, implicit conversion of numbers is not a good idea but on the other hand explicit conversion lead to fromIntegral noise in my code. Sometimes, it seems, straight imperative programming is the best way for a function but then the code looks kind of ugly. The dreaded type related error messages of Haskell are not that bad I’d say. Yet sometimes you don’t understand a word of them. I guess this is the price you pay for an expressive but abstract & general type system. There is indeed some boilerplate especially regarding the update of fields in state records. Whereas in imperative languages you can write something like variable += 1 which is perfectly obvious, in Haskell on the other hand, due to the cumbersome syntax for field updates and immutable variables, there is far too much line noise unless state updates/queries are put in their own helper functions. Laziness was a real problem for showing progress and measuring the execution time of the computation. Granted, here it was a rather artificial requirement. If I really wanted to measure the performance I would have used profiling tools. But the point is, again, to compare (almost) the same implementation in different programming languages.

And although the above paragraph sounds like I am very nitpicking regarding programming languages (which I am) and Haskell, Haskell made damn fun because it allowed me to be very expressive & precise and it gave me a feeling of safety about my program. I understand that Haskell has its weak points, too, and I really felt them and now know (better than before) how to deal with them.

Conclusion

The point I wanted to make with this experience report is that I believe the reductions of effects/state to a local and managable minimum helps writing good & correct software. Even more so if the programming language provides syntactical and semantic means to achieve this goal.

Published: 14.05.2011 Last modified: 21.12.2013
Comment? Mail or tweet me.