Pure fun. A journey towards Elm.

March 27, 2020

In this post, I will share my experience with implementing my first program in the functional programming language Elm. You don't need to know what elm or functional programming is to follow but basic knowledge about programming in general is assumed.

Introduction

At the time this post was written, large parts of the world were faced by the fast spread of the severe acute respiratory syndrome coronavirus 2, (SARS-CoV-2) and strict countermeasures against that spread. This led to two issues for many: Not so much to do and quite limited contact to other people. What a perfect time to write a game you can play with others!

The 1998-card game "Schokohexe" ("chocolate witch") was the basis for this project. The idea is similar to Black Jack, let me give you a quick overview: There are 60 cards in a pile, of which most represent a certain ingredient for chocolate (sugar, milk, raisins, vanilla beans, cocoa beans or hazelnuts). But some cards represent the evil chocolate witch who steals your stuff! Each player takes turn in drawing cards from the pile. As many as they like, but whenever they draw a chocolate witch, they have to stop and discard all cards they collected in this turn. Who can collect one instance of each ingredient first, wins the game. As you might have guessed, the difficulty lies in predicting whether the next card will give you a further valuable ingredient or will make you lose some of them.

But that's just so you know what kind of game this is about, let's get to the interesting part! I had some requirements for my implementation:

Multiple persons can play together without the need for physical proximity.
The game facilitates communication beyond the actual game play.
Very limited technology suffices to synchronise each player's instance of the game.

As it turns out, the functional programming language Elm is a perfect fit for this! If you're comfortable with both the terms "functional programming language" and "Elm", you can skip the next two sections. Otherwise, I will try to roughly explain them:

Crash Course: Functional Programming

Most programmers are used to imperative programming which means that the behaviour of a program is more or less defined by a series of instructions that modify certain data. In functional programming, on the other hand, everything is about, well, functions.

While "function" can mean a quite broad range of things in programming, we are talking about a strict mathematical sense here. You could say, in a way, (and one actually does) that, in functional programming, functions are pure. A pure function

has the same behaviour whenever it is called with the same arguments, and
has no effect on other things outside the function (no side effects), especially not on its arguments.

This second point implies that each piece of data is immutable!

Let's look at this Python snippet to see a definitly non-pure function:

counter = 0

def f(x):
    global counter
    counter += 1
    return x + counter

print(f(1))
print(f(1))
print(f(1))

Whenever f is called, counter is incremented, so there is a side effect. Also, the value of f(x) does not only depend on x but also on counter which means we will get another value for each function call (1, 2 and 3 in this case). This is very different from what we are used to in maths: A function like g: ℝ → ℝ, g(x) = x² will always return the same result when we give it the same x.

The purity and immutability in functional programming makes it easier to reason about the behaviour and correctness of a program as well as execute code in parallel (no data races possible!), but otherwise trivial functions that return the current time or a random number become a bit challenging to use.

Side note

Functional programming is part of declarative programming which means that we don't describe how to compute a solution but what solution we want. If this sounds like magic to you (it certainly did so to me for a long time!), let me tell you that a clever compiler and/or runtime will figure out the imperative details needed for the computer to do the actual computation.

Okay, and what's elm?

Elm is a rather new functional programming language (first appeared 2012) that focuses on the development of web apps. Visit their website to get an in depth introduction, but I will highlight some central aspects from my perspective:

Expressive and strong type system. If you're not familiar with (static) types, just take away that this allows the compiler to perform many checks and prevents a lot of runtime errors (in fact, elm advertises with that lack of runtime errors, which probably is a big selling point when the competitor is JavaScript...). If you have worked with them: Elm allows for struct like and enum like types, types can have type parameters ("generics"), enum variants can have parameters, and function signatures are well expressible with types (well, it better be so in a functional language...). Interfaces/type classes/traits or whatever you call them are only available in a very limited form.

Pattern matching can destructure structs, enums and their variants' parameters, and lists.

A quick example for these first two points to get you familiar with elm's syntax:

type Bee = Queen Int | Worker

isInteresting : List Bee -> Bool
isInteresting bees =
    case bees of
        firstBee :: otherBees ->
            case firstBee of
                Queen age ->
                    age == (length otherBees)
                Worker ->
                    False
        [] ->
            False

Read this as: A Bee is either a Queen and has an Int number associated to it (which we interpret as the age) or it is a Worker. Now, we find a list of bees interesting if the first one is a queen and, if so, if her age is equal to the number of other bees in the list. The formal definition of this is declared (hence declarative programming) by the function isInteresting. It maps a List of Bees (List Bee would be List<Bee> in C++, Java or Rust) to a Bool value. For any concrete List of Bees, let's call it bees, we first check if it consists of a first element and further elements. If applicable, call them firstBee and otherBees, if not, the answer to our question is clearly "no" ([] -> False, where [] denotes the empty list). Now, further examine this firstBee. If it is a Worker, the answer is again "no", if it is a Queen with a number that we call age, then just check if that number equals the length of otherBees. Quite expressive syntax, isn't it?

Finally, three application-oriented features: Usage of the Model-View-Controller principle. That's not just a suggestion, elm literally needs you to have a type for the model, a function for the view (maps a model to HTML), and a function for the controller (maps the model and an action ("message", in elm terms) to a new model).

Being primarily designed for web apps, elm makes it rather easy to put together the necessary elements of a web site, no extra HTML required.

Elm's compiler has really helpful error messages. They don't just freak out for missing an underscore (looking at you, LaTeX!) but patiently tell you what went wrong and even provide an example how to do it right.

Could we talk about that game, please?

Okay so that's been a lot of stuff, but quite necessary for my point I would like to make. I will now sketch the design of my elm code, emphasising the key parts, skipping the boring technicalities.

The model

The most important thing in my opinion is always the model or state. Whether you're designing a tool, game, or even build a mathematical model, think about how to describe the state first, the rest will follow. In programming, this state is usually expressed by types. So, dealing with a card game, let's start with the Card type which is pretty straight forward:

type Card
    = ChocolateWitch
    | Sugar
    | Raisins
    | Milk
    | Hazelnuts
    | VanillaBeans
    | CocoaBeans

Then, we need a player:

type alias Player =
    { name: String
    , safeCards: Set Int
    , currCards: List Card
    }

It has a name, a set of safe cards (the chocolate witch can't steal them!), and a list of the cards drawn in the current move (they might still be lost).

The type of safeCards maybe calls for some discussion. A player only needs one instance of every ingredient so a set is the natural choice. However, why a set of Ints and not of Cards? This has to do with a certain limitation in Elm. You can only have a Set of types which are comparable, where comparable is an inbuilt type class in elm (I assume that's because elm uses a search tree for sets internally). Elm does not let you implement comparable` for your own type so you need to use, for example, Int. A simple cardId function that maps Card to Int did the trick for me.

Players and cards are the only special entities in this game, so having them we can define a game state:

type alias GameState =
    { players: Array Player
    , currPlayer: Int
    , rngState: Seed
    , drawPile: List Card
    , discardPile: List Card
    }

Obviously, a game consists of a bunch of players. I've chosen an Array instead of a List because we need random access. currPlayer keeps track of the index of the player that is currently doing their move, drawPile and discardPile are, well, the draw pile and the discard pile.

The really interesting part is rngState: Seed, the random number generator state. In fact, the next section will only be about it:

How does pure randomness work and how can we use it?

Let's recall for a moment what I stated in the beginning of this post. I wanted multiple persons to play this game remotely together with as little technology as possible. Actually, having each player need to connect to a central server would already be too much. I'd have to implement a backend and manage its availability and security, which is not a trivial task. So that's problem number one: Synchronise the instances of the game without any internet connection between them.

A seemingly unrelated point: It is in the nature of card games that cards must be shuffled. In this very case, the game would be pretty pointless if a player could somehow certainly predict the next card. So we need to introduce some kind of randomness. Easy in imperative programming but challenging in functional programming, as pointed out earlier. Elm just could not have a function like

shuffleCards : List Card -> List Card

that produced a randomly shuffled version of its input because then it would not be pure. (In case you're thinking of that one xkcd now... here it is. You're welcome.) So there we have problem number two: Shuffle cards randomly in a pure, functional way.

The cool thing is: We can solve both problem one and two with the same solution! We will exploit the way elm deals with generating random data to synchronise remote instances easily.

So, how does elm generate random data? Almost always when you let a computer produce "random" values, it in fact gives you pseudo-random values. That means it applies a complicated calculation to a number to get a new number that looks unrelated to the previous. Oh so it's just a deterministic mapping from one number to another? We can do that with functional programming! The elm-way of denoting such a mapping is the Generator type. It describes what random values we'd like to have (again, declarative programming). There is, for example, Random.int: a Generator that expresses "I'd like to have a random integer between a lower and upper limit". We can use it to build our own Generator:

coin : Generator Int
coin = Random.int 0 1

which means that coin is a Generator that produces an Int that is either 0 or 1.

This "number" that gets mapped by a random generator is often called a "seed". Elm follows this terminology and provides a type Seed. The actual mapping is done using the step function:

step : Generator a -> Seed -> ( a, Seed )

For now, read this as: step is a function that takes a Generator of any type (let's call it a) and a Seed and gives you a value of type a and a new Seed. (Two remarks: Read this to really understand this notation. Also, in C++, Java or Rust the convention would be to use T instead of a.)

We're almost through the hard part! The last thing we need is a Generator for a shuffled List of Cards like our drawPile. Luckily, the package Random.List provides exactly that:

shuffle : List a -> Generator (List a)

Now, we can put the pieces together and build our shuffleDrawPile function:

shuffleDrawPile : GameState -> GameState
shuffleDrawPile gamestate =
    let
        (shuffled, newState) = step (shuffle gamestate.drawPile) gamestate.rngState
    in
        { gamestate | rngState = newState, drawPile = shuffled }

Some new syntax again but nothing too hairy, let me guide you through: The function maps the previous GameState to a new one, so far so good. It does that by introducing two auxiliary variables (the let ... in ... thing): shuffled and newState. They are what we get when we apply the step function on the Generator shuffle gamestate.drawPile and the seed gamestate.rngState. We then use them to build a new GameState for which we utilise Elm's update syntax: The return value is basically just the old gamestate but rngState should be newState and drawPile should be shuffled. Remember, gamestate is immutable! This produces an entirely new GameState, we just reuse most of the old data.

There you have it! We can randomly shuffle the cards but still stay completely pure and keep total control over what happens in our program. A similiar function exists to randomly pick which player starts the game, by the way.

"You still haven't explained how to remotely synchronise the players!!", I hear some of you nag. True, but that's trivial now: Just agree on an initial seed and give it the program in the beginning! Then, everyone can reproduce the actions of each opponent. How to know what the others did? Call them! This tackles the third of my initial requirements: The game forces you to have a communication on a further channel. It's also much more fun to share your emotions live (and there will be lots of emotions in this game!) and fulfils an unmet need for social contact in these days of #stayathome.

Further notes on the implementation

I won't go into much detail here, the rest is mostly boring stuff like checking if a player has won, organising the different collections of Cards (drawPile, discardPile and each Player's safeCards and currCards) during a move. However, I do want to point out that most parts of the game logic could be described in quite concise, < 10 lines functions. This seems to be a general advantage of functional programming.

On the user interface side, I made three different views: One to enter all players' names and the initial seed, one for the actual game, and one to display the winner. Below, you can find screenshots.

Screenshot of the actual game's view — (I shamelessly used non-free images to display the cards, hence I painted over them in this screenshot.)

Although this does not look like ugly pure HTML, I used almost no CSS for the design. This is due to the elm-bulma package which is like "Here, take this button function and tell me what label to put on the button and what to do if the user clicks it, I will handle the rest and return you a handsome button, ready for you to use". I would be totally overstrained if I had to design good CSS myself, so I'm very glad there are packages like that.

Final remarks

A summary of what we learned today and I learned during this project:

Functional programming can challenge your mindset when you first encounter it but its pure functions give you quite nice new powers.
Elm is a really good point to start exploring functional programming with its helpful attitude throughout and its ease of producing good looking apps.
Purity does not necessarily restrict the use of randomness but can actually enhance the control over it. Read about stream ciphers to see how this idea is actually used in the real life.
Striving for a solution with minimal technological effort can open a joyful substitution for traditional approaches (in this case: call your friends and laugh at them when they draw a witch!)

Can you get the source code/the final game? Sorry, I don't think so. As I said, the used images are not free, but even more critical, I'm afraid I'd impinge upon the rights of Ravensburger, the original publisher of the game.

I guess that's all I have to say. Stay healthy!