Some Types - Part 1

(The full code from this post is available at https://github.com/jballanc/SomeTypes.jl)

I recently came across a wonderful blog post by Alec Loudenback wherein he used SumTypes.jl to simulate games of "Count Your Chickens". As a fellow "Count Your Chickens" enthusiast¹, and a long-time fan of Sum Types, I very much enjoyed his post. After reaching the end I couldn't shake a nagging thought: was SumTypes.jl actually necessary for the approach that Alec took?

Julia's type system, how it handles gradual typing, and the way it makes multiple dispatch a central feature of the language, combine to create an extremely powerful language. It is so powerful that, despite not explicitly including Sum Types as a feature (like languages such as Haskell or Rust) you can achieve nearly the same result. Let's take Alec's original code using SumTypes.jl and see what it would look like using simple, vanilla Julia instead.

First, we start with the definition of a type to describe the animals present on the spinner and squares on the board (that may or may not contain an image of an animal). The original utilizes the @sum_type macro from SumTypes.jl:

@sum_type Animal begin
    Cow
    Tractor
    Sheep
    Dog
    Pig
    Fox
end

@sum_type Square begin
    Empty
    Regular(::Animal)
    Bonus(::Animal)
end

There's a comment in the Wikipedia entry for Sum Types (also known as "Tagged Unions") that mentions that OOP class hierarchies are nearly analogous to Sum Types but for the fact that subclasses at a level in the type hierarchy can be further subclassed, breaking an important invariant of Sum Types. However, Julia's type system is unique in that only leaf types are allowed to be non-abstract, and so you cannot arbitrarily subclass a type in Julia. This allows us to describe Animal in Julia as a simple type:

abstract type Animal end
struct Cow <: Animal end
struct Tractor <: Animal end
struct Sheep <: Animal end
struct Dog <: Animal end
struct Pig <: Animal end
struct Fox <: Animal end

For the squares, which may or may not contain an Animal, we have to bring in parametric types. Because of the nature of Julia as a gradually typed language, and because of the restriction on only being allowed to subtype abstract types, we can do some extremely powerful things with just a touch of type parametrization. First, we need to define our base Square type and allow it to be parametrized with an Animal or Nothing:

abstract type Square{T<:Union{Nothing,Animal}} end

Next, we will define a type for empty squares. There is no need to allow empty squares to be parametrized, since they will always be empty, and Julia allows us to describe exactly this:

struct Empty <: Square{Nothing} end

Finally, we will define regular and bonus squares as being able to be parametrized, however we only want them to be able to take an Animal for their parameter. Again, Julia gives us an elegant way to describe just this:

struct Regular{T<:Animal} <: Square{T} end
struct Bonus{T<:Animal} <: Square{T} end

The approach Alec takes to simulate the game is relatively straight-forward. The board is described as an array, the spinner as a tuple of animals, and on each move a random choice of the spinner tuple is then matched against the board array, starting at the current position. That code can remain largely unchanged in a vanilla Julia approach, save for a few key differences. The most significant difference is how we match the animal resulting from the spin to the corresponding next square on the board. Using Sum Types, the code looks like this:

"""
    ismatch(space,spin)

True or false depending on if the `spin` (an `Anmial`) matches the data within the `square` (`Animal` if not an `Empty` `Square`). 
"""
function ismatch(square, spin)
    @cases square begin
        Empty => false
        [Regular, Bonus](a) => spin == a
    end
end

Using the @cases macro from SumTypes.jl, this looks an awful lot like something straight out of Haskell, and it really couldn't be clearer what's going on: empty squares never match, and other squares are a match if the animal they've been parametrized with matches the animal provided. Just 6 lines. Not bad...but can we do better without SumTypes.jl?

ismatch(_, _) = false
ismatch(::Square{T}, ::T) where {T<:Animal} = true

This is where the power of Julia really begins to shine through! There's a lot going on in these 2 lines, though, so let's break it down a bit. The first line here takes advantage of Julia's gradual type system and allows us to define a universal base case: ismatch will take two arguments, and by default we will assume they don't match. The underscores are just a convention to say we aren't using the variables (you can name them if you like, the code will still work), and the lack of type annotation (denoted with a :: in Julia) implies we don't care about the types.

With this base case defined, now we only need to worry about exceptions to this case. Again, we don't actually care about the arguments because we're going to lean on the power of the types we defined to determine if they match. So, we start with ::Square{T} indicating that the first argument should be some subclass of a Square (if you want to name the variable square::Square{T} or _::Square{T} you can, but it's not necessary). We then indicate that the second argument should be a ::T. Since we use the same label for both the parameter to Square and the type definition of the second argument, we are implying that they should match. The only thing left to do is to indicate that this T should be restricted to being one of the Animals (since, remember, Squares can also hold Nothing). Adding the where {T<:Animal} achieves this, so that we can avoid inadvertently matching Empty to Nothing.

The only other place we need to update Alec's original code to work with vanilla Julia is in the move method where we determine how many chicks we should pick up. In the original code, this is again achieved with a @case:

n_spaces = next_square - cur_position
@cases board[next_square] begin
    Empty => (spaces=n_spaces, chicks=n_spaces)
    Bonus => (spaces=n_spaces, chicks=n_spaces + 1)
    Regular => (spaces=n_spaces, chicks=n_spaces)
end

Again, the code is very clear and unambiguous. To do the same thing with vanilla Julia, we can do a bit of a refactor and lean on some runtime type checks:

n_spaces = next_square - cur_position
(spaces=n_spaces, chicks=n_spaces + board[next_square] isa Bonus ? 1 : 0)

So there you have it! We can do the same thing Alec does using SumTypes.jl with nothing more than Julia's awesome type system. There are, of course some additional subtle differences, and a handfuls of pros and cons comparing SumTypes.jl and vanilla Julia. The most important difference has to do with the ability to ensure completeness of the code. One of the major reasons to grab for a Sum Type is that it is possible to definitively check that all possible cases have been handled. For example, if we were to add a SuperBonus square type that gave a bonus of 2 chicks instead of 1, the code using @cases would catch if we forgot to handle the SuperBonus case, while the vanilla Julia code would simply award no bonus. On the other hand, the vanilla Julia code is more flexible in the face of additional types. With SumTypes.jl, we would have to update our ismatch() code for every new square type we introduce, while the type-system-driven ismatch() code will continue to work for any new square type, so long as it is a subclass of Square{Animal}.

The vanilla Julia code also differs from the SumTypes.jl code in performance and in the board squares and spinner animals need to be instantiated, but this post is already long enough. More on these interesting differences next time...

1. For the uninitiated, "Count Your Chickens" is a very simple cooperative game consisting of a board with a linear path of squares containing pictures, and a spinner with corresponding pictures. Each player spins the spinner, and moves the shared marker to the next square containing the corresponding picture, picking up a "chick" and placing it in the coop for each square traversed. Bonus squares allow you to pick up an extra chick, and a fox on the spinner makes you remove a chick from the coop, the goal being to get all your chicks to the coop by the time you reach the last square. ↩