Some Types - Part 2

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

In the first post in this series, I looked at how Julia's native type system is powerful enough to stand in for a more formal implementation of Sum Types (a.k.a. Tagged Unions), such as that found in the wonderful SumTypes.jl library. One problem with that comparison, however, was that using native Julia types necessitated creating instances of the types, whereas using SumTypes.jl one is able to follow a more traditional pattern. As a specific example, to create a game board for the "Count Your Chickens" game being simulated, it is possible to create an array of Square types directly when using SumTypes.jl:

board = [Empty, Regular(Sheep), Regular(Pig), Bonus(Tractor), Regular(Cow), ... ]

With native Julia types, it was necessary to create an array of instances of the types instead:

board = [Empty(), Regular{Sheep}(), Regular{Pig}(), Bonus{Tractor}(), Regular{Cow}(), ... ]

If these instances were being used to convey some information, that would be one thing, but the way the simulation was written, these instances serve only as markers to guide method dispatch. Specifically, if we look at the ismatch function we used in Part 1 to match results from the spinner to squares on the game board, we see that the entirety of the logic in this function derives from the type-signature of the two methods:

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

For a small game board data structure, such as the one we used to simulate "Count Your Chickens", the overhead of having to instantiate and allocate each square is negligible, but it's not hard to imagine a situation where having to constantly instantiate types that are used only to guide dispatch could become burdensome. Could we, somehow, use native Julia types without having to instantiate them each time?

It turns out, we can! To understand how, we first need to have a look at what a type really is in Julia. The Julia REPL is a wonderful tool for exploring Julia, so if we fire it up and create a few objects:

julia> a = 1
1

julia> b = "hello"
"hello"

julia> struct Foo; end

julia> c = Foo()
Foo()

...we can interrogate Julia as to what their type is:

julia> typeof(a)
Int64

julia> typeof(b)
String

julia> typeof(c)
Foo

But what if we interrogate Julia about the type...of a type?

julia> typeof(Foo)
DataType

In fact, this works not just for user-created types, but also for Julia's built-in types:

julia> typeof(typeof(a))
DataType

In Julia, each type is an instance of the DataType. Further than that, as the Julia documentation states:

Every concrete value in the system is an instance of some DataType.

Neat! But how does this help us with eliminating the need to instantiate our game board types? That's where Type{} comes in. The parametric Type{} type gives us a way to directly reference the DataType instance that represents each type. You might need to read that last sentence a few times for it to make sense...or you can ask the REPL. Using the isa operator that tells us about the relationship between objects and their types:

julia> c isa Foo
true

julia> Foo isa DataType
true

julia> String isa DataType
true

julia> Foo isa Type{Foo}
true

julia> String isa Type{Foo}
false

We can see that, as promised, the user-created Foo and the built-in String types are both instances of DataType, but this is not particularly helpful if we want to write methods that can distinguish between the two. For that we look at the Type{Foo} parametric type and see that it is the type that Foo is an instance of, but that String is not an instance of Type{Foo} (it would, instead, be an instance of Type{String}). Indeed, the only instance of Type{Foo} is the Foo type.

Returning, then, to our ismatch method, we can re-write the methods using Type{} for the method signature:

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

Note that we're not just using Type{}, but we're also combining it with the ability to parameterize methods and limit the acceptable types for parameterization. Testing this out, we can now see that we can pass types, rather than instances of the types, to ismatch:

julia> ismatch(Empty, Pig)
false

julia> ismatch(Empty, Nothing)
false

julia> ismatch(Regular{Pig}, Pig)
true

julia> ismatch(Bonus{Pig}, Pig)
true

julia> ismatch(Bonus{Pig}, Cow)
false

Finally, this allows us to update our definition of the game board to be nearly identical to the version using SumTypes.jl (just substituting curly-braces in place of parens):

board = [Empty, Regular{Sheep}, Regular{Pig}, Bonus{Tractor}, Regular{Cow}, ... ]

It's worth noting that this technique, dispatching on the Type{} of a type, is not just a neat parlor trick. It is key to a number of advanced techniques in Julia such as Conversion and Promotion and "Holy traits".

So, now that we are no longer instantiating every square on the game board, everything should be much smoother and we would expect our game simulations to run faster, right? Well...

Next time, I'll start looking at some basic bench-marking of the various approaches to this problem, using SumTypes.jl, instances of native Julia types, and native Julia types themselves. The results are not what you'd expect!