Elegant Bowling

Posted in programming -

I’ve had a few mind-blowing moments since I started learning Erlang. One of those was at a hack night where we did the Bowling Game as a pair programming exercise. It’s a standard, simple programming challenge: calculate the score for a series of rolls in bowling. It’s not entirely trivial: Calculating the score for spare and strike frames adds a bit of trickiness, and there are edge cases around the end of the game.

By coincidence, I’d done it about a year earlier in Python for another hack night. In an OO language, it’s pretty obvious to model it as a Game object which contains a list of Frame objects. It’s less clear how to handle the fact that the score for a frame may depend on rolls in other frames. Either frames have to know about other frames, or rolls have to be added to multiple frames, or the Game class has to handle the spare and strike calculations, or something like that. All of the options feel a little awkward, so you can get wrapped around the axle there. But in the end, I had a solution I was pretty happy with. It weighed in at 53 lines of code.

The final version* in Erlang was 15. Wow. I think of Python as a pretty compact language, and the Erlang code is less than a third as long. And it’s not some high-density, Perl-style line noise; it’s clearer - hardly more than a definition of the rules of the game.

(* Thanks to Rusty for pointing us in the right direction here.)

score(Rolls) -> score(Rolls, 1, 0).

score(_BonusRolls, 11, Score) -> Score;

score([10 | Rest], Frame, Score) ->
    score(Rest, Frame + 1, Score + 10 + strike_bonus(Rest));

score([Roll1, Roll2 | Rest], Frame, Score) when (Roll1 + Roll2 == 10) ->
    score(Rest, Frame + 1, Score + 10 + spare_bonus(Rest));

score([Roll1, Roll2 | Rest], Frame, Score) ->
    score(Rest, Frame + 1, Score + Roll1 + Roll2);

score([Roll1], _Frame, Score) -> Score + Roll1;
score([], _Frame, Score) -> Score.


spare_bonus([]) -> 0;
spare_bonus([Bonus1 | _Rest]) -> Bonus1.

strike_bonus([]) -> 0;
strike_bonus([Only]) -> Only;
strike_bonus([Bonus1, Bonus2 | _Rest]) -> Bonus1 + Bonus2.

(If you’re completely new to Erlang, the multiple function definitions are essentially implicit if-elseif conditions matched against the values of the parameters.)

So what makes the Python code so much longer? A lot of it is spent querying and updating the state of the objects. That’s also where a lot of the design complexity came from, figuring out how each object interacts with the others. In the Erlang solution, we do an end run around all that by just using simple lists and variables. The input is a list of numbers; the output is a single number; why use anything more complex in between?

The point of this is not which language is better; it’s that using Erlang showed me a different way to solve this problem. I went back and translated the Erlang code into Python. It’s straightforward: one function with a big if-elif block. You can do it as either a recursive function or a while loop. Either way, it ends up being pretty much the same length as in Erlang.

(As a side note: A nice thing about using recursion is that it simplifies variable scoping. At each step, you’re calling a function with an explicit set of parameters. This makes it clear what state is being passed along. If you’re just modifying variables and looping, it would be easy to forget to update a value.)

So why didn’t I come up with the simpler solution when I wrote this in Python? It’s mostly a matter of culture. As with natural languages, programming languages come with a layer of culture; what the normal way of writing programs is. Because Python is an OO language, the first question I asked was “What are the objects?” What are the concepts in the problem domain, and how do I map them to classes? While that may turn out to be a necessary intermediate step, it’s not actually the end goal. It’s easy to lose sight of that. You can jump right in and start coding up classes: constructors, accessors, unit tests and so on. You can write a fair amount of code without thinking too much about what you’re trying to accomplish. That feels like progress, but it may just be a diversion. In this case, it’s not necessary and only adds complexity.

In a functional language like Erlang, the first question is “What are my inputs and outputs?” What is the end result I’m trying to get to, and where am I starting from? It keeps you focused on the data you have and what you’re trying to accomplish. Erlang’s pattern matching brings a lot of power to working with simple data structures. If you want to create real mutable objects, you can, but Erlang makes you deal with concurrency up front, so it’s less trivial. It encourages you to think of the simplest thing that works.

It seems like this should be a transferable skill, but I suspect there’s a catch. I could certainly use recursion and simple data structures in my Python code (or Ruby and maybe to a lesser extent Java). If it cuts out a lot of extraneous object munging and dramatically reduces the line count, that should make it more maintainable. The trouble is that “maintainable” means “maintainable by other programmers”. My code may be more elegant and concise, but if it’s using programming idioms they aren’t familiar with, they’re going to have trouble with it. I can trust that Erlang programmers are familiar with recursion because Erlang uses it for everything. That’s not true of Python. This is the flip side of culture: There are things that you could say - that are grammatically correct - but you wouldn’t.

Newer article
Fizzbuzz
Older article
Crafty Erlang