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

The source code for each ver­sion can be found here: https://​github.​com/​eugenkiss/​mastermind

Mo­ti­va­tion

You might won­der why I wrote the same pro­gram in three dif­fer­ent lan­guages. The rea­son is that I wanted to ex­pe­ri­ence the ap­pli­ca­tion of dif­fer­ent pro­gram­ming par­a­digms on the same task in order to judge them more fairly. This ex­pe­ri­ence re­port could have just as well been ti­tled “Pro­ce­dural against Ob­ject Ori­ented against Func­tional Pro­gram­ming Styles” or “Im­per­a­tive against De­clar­a­tive Pro­gram­ming Styles”. I ac­knowl­edge that the task is fairly small and there­fore can only tell so much about a par­a­digm. On the other hand, it is large enough to en­counter de­tails and cor­ner cases of each par­a­digm so it is still use­ful.

Back­ground

I have writ­ten this sim­u­la­tion for a uni­ver­sity pro­ject where Lego Mind­storms ro­bots were sup­posed to play a vari­a­tion of the game mas­ter­mind in an en­closed area. These ro­bots needed a strat­egy, of course, and since there are sev­eral (clas­si­cal) mas­ter­mind strate­gies a sim­u­la­tion to test these var­i­ous strate­gies seemed like a good idea, par­tic­u­larly as it wouldn’t have been fea­si­ble to sim­ply ob­serve the robot using a strat­egy in real time.

As I was tin­ker­ing with Lua at the time I de­cided to write a first pro­to­type of the sim­u­la­tion in Lua. Lua seemed like a good fit be­cause it is a fairly par­a­digm neu­tral & light­weight pro­gram­ming lan­guage. Since the source code for the ro­bots had to be writ­ten in Java I rewrote the sim­u­la­tion in Java. By then I had writ­ten a (hope­fully) pro­ce­dural and an (hope­fully) ob­ject ori­ented ver­sion and since I was a be­gin­ning haskeller I de­voted my­self to rewrit­ing the sim­u­la­tion in Haskell. I specif­i­cally wanted to ob­serve how the ex­plicit state/ef­fect sep­a­ra­tion of Haskell helped in writ­ing bet­ter & eas­ier to rea­son about code be­cause the most per­va­sive and ma­li­cious bugs in the Lua & Java ver­sions were state/iden­tity re­lated. One of the plen­ti­ful mo­ti­va­tions has been the paper Out of the Tarpit.

Analy­sis

I spare you the de­scrip­tion of the task as it won’t make the fol­low­ing ob­ser­va­tions clearer and it is some­what elab­o­rate. If you are re­ally in­ter­ested have a look at one of the READMEs in the re­spec­tive Github pro­jects, you can find it there.

Lua & Java

What I liked about writ­ing the Lua ver­sion was that there was so lit­tle over­head in con­cepts. You’ve got func­tions, some con­trol struc­tures, ta­bles and that’s ba­si­cally it. At the same time there were some an­noy­ing things. A com­mon com­plaint about Lua is its rel­a­tively high ver­bosity - at least for a dy­namic lan­guage. It’s true. See­ing long key­words like func­tion or local every­where hin­ders read­abil­ity.

Just as Lua Java has the rep­u­ta­tion of being overly ver­bose. In fact, Java is much more ver­bose than Lua so I shouldn’t re­ally call Lua ver­bose in this con­text. On the plus side, using classes to en­cap­su­late code made it eas­ier to un­der­stand the struc­ture of the prob­lem de­spite the “cog­ni­tive over­head” of the class-based ap­proach com­pared to the more min­i­mal “func­tion-ap­proach” of the Lua ver­sion.

One shouldn’t un­der­es­ti­mate the help of a sta­tic type sys­tem when refac­tor­ing code, too. In Java, refac­tor­ing was easy be­cause the com­piler com­plained if parts of the code didn’t type check so you were kind of sure that you did not break any­thing. Try­ing to refac­tor the Lua ver­sion al­most al­ways lead to sub­tle bugs that a com­piler could have found and so could have saved me a lot of time.

Haskell

If you are not fa­mil­iar with Haskell have a look at the de­lib­er­ately un­crit­i­cal Why Haskell Mat­ters. Haskell’s most valu­able virtue for this task is that Haskell is purely func­tional. That means, you must be very ex­plicit in your code when­ever using ef­fects and there­fore you are al­ways aware if your change can alter ef­fects or not. I find this ap­proach very good and I felt that you start to think more pre­cisely about prob­lems be­cause you try to re­duce the “state vari­ables” to the ab­solute min­i­mum.

You should know that this has been my first “real” or rather in­de­pen­dent Haskell pro­ject apart from small ex­er­cises. As the say­ing goes, the devil is in the de­tails and even though the small ex­er­cises were very nat­u­rally solved in Haskell this par­tic­u­lar task high­lighted some prob­lems with Haskell es­pe­cially re­gard­ing lazi­ness. To give you an ex­am­ple of Haskell’s beau­ti­ful side take a look at this de­f­i­n­i­tion:

-- | 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-ex­plana­tory if you know Haskell a bit. The only thing you need to know is that but­tons is a list of, let’s say, the col­ors in mas­ter­mind. At the same time there are some, I’d say, quite ugly de­f­i­n­i­tions in my code. Some­how, how­ever, I sus­pect that they could be rewrit­ten in a bet­ter style if I was more ex­pe­ri­enced - or maybe even not.

Gen­er­ally, I like Haskell’s type sys­tem. Even though some­times I couldn’t un­der­stand the error mes­sages im­me­di­ately the type sys­tem often un­veiled bugs. Fur­ther­more, adding type de­f­i­n­i­tions makes the code self-doc­u­ment­ing.

As men­tioned, I was/am a Haskell be­gin­ner. Nonethe­less, I hoped writ­ing the sim­u­la­tion in Haskell would have went smoother. E.g., I did not fully un­der­stand the State Monad when I first used it. Also, I had some prob­lems uti­liz­ing the, for me new, func­tional par­a­digm.

On the plus side, I en­coun­tered less bugs. Ac­tu­ally there were only two off- by-1 run­tome er­rors when using head and !! and a de­vi­ous in­fi­nite mu­tual re­cur­sive loop. Now is a great time to say this: Haskell & its type sys­tem is no magic dust. It can help you ex­ten­sively but it can­not do every­thing as it is some­times preached. There are, how­ever, ex­ten­sions to Haskell like de­pen­dant types which, I think, could have pre­vented the off- by-one er­rors at com­pile time by spec­i­fy­ing that e.g. a list can­not be empty or that two lists for a func­tion must have the same length. Now that I think about it I did a wrong con­ver­sion from sec­onds to mil­lisec­onds in both the Java & Haskell ver­sion. This could have been pre­vented by as­so­ci­at­ing units with types but per­haps it would have been overkill. As you can see, I can count the bugs in the Haskell ver­sion on one hand. Yet, there were other an­noy­ances. Let’s have a look at Haskell’s warts.

First of all, the record syn­tax is te­dious, very te­dious. There are ex­ten­sions that make it eas­ier like Record­Wild­Cards but still. Granted, im­plicit con­ver­sion of num­bers is not a good idea but on the other hand ex­plicit con­ver­sion lead to fromInte­gral noise in my code. Some­times, it seems, straight im­per­a­tive pro­gram­ming is the best way for a func­tion but then the code looks kind of ugly. The dreaded type re­lated error mes­sages of Haskell are not that bad I’d say. Yet some­times you don’t un­der­stand a word of them. I guess this is the price you pay for an ex­pres­sive but ab­stract & gen­eral type sys­tem. There is in­deed some boil­er­plate es­pe­cially re­gard­ing the up­date of fields in state records. Whereas in im­per­a­tive lan­guages you can write some­thing like vari­able += 1 which is per­fectly ob­vi­ous, in Haskell on the other hand, due to the cum­ber­some syn­tax for field up­dates and im­mutable vari­ables, there is far too much line noise un­less state up­dates/queries are put in their own helper func­tions. Lazi­ness was a real prob­lem for show­ing progress and mea­sur­ing the ex­e­cu­tion time of the com­pu­ta­tion. Granted, here it was a rather ar­ti­fi­cial re­quire­ment. If I re­ally wanted to mea­sure the per­for­mance I would have used pro­fil­ing tools. But the point is, again, to com­pare (al­most) the same im­ple­men­ta­tion in dif­fer­ent pro­gram­ming lan­guages.

And al­though the above para­graph sounds like I am very nit­pick­ing re­gard­ing pro­gram­ming lan­guages (which I am) and Haskell, Haskell made damn fun be­cause it al­lowed me to be very ex­pres­sive & pre­cise and it gave me a feel­ing of safety about my pro­gram. I un­der­stand that Haskell has its weak points, too, and I re­ally felt them and now know (bet­ter than be­fore) how to deal with them.

Con­clu­sion

The point I wanted to make with this ex­pe­ri­ence re­port is that I be­lieve the re­duc­tions of ef­fects/state to a local and man­agable min­i­mum helps writ­ing good & cor­rect soft­ware. Even more so if the pro­gram­ming lan­guage pro­vides syn­tac­ti­cal and se­man­tic means to achieve this goal.

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