📅May 17, 2019
📝988 words — ⏱4 mins 56 secs

The Perils of Overthinking

I was working on Lazyboy, my embedded domain specific language for Game Boy development, when I happened across a scenario wherein I wanted to express “symmetry” in typeclass instances.

For context, I was implementing an abstraction for conditional logic, with a syntax as follows:

It’s not essential to completely understand what’s happening here, only that it’s a representation of conditional execution.

This code produces the following assembly:

The type of cond is cond :: Lazyboy Condition -> Lazyboy () -> Lazyboy (), which for practical purposes means that the condition provided to the function executes a series of instructions and returns which CPU Condition Flag should be checked, with a jump occurring on the flag accordingly.

It’s desirable to provide an abstraction to compare the values contained in registers to immediate values as well as to other registers with the same syntax, so in order to achieve this, a typeclass was my first consideration, since the implementation is dependent on which types are being compared.

But hang on — we’re going to be comparing things of different types, and the actual implementation of equalTo (and other such comparisons) is dependent on the type of the arguments. So we need a typeclass that takes two arguments.

Checking the Haskell Wiki we find that what we want is the MultiParamTypeClasses extension. Awesome. Confirming our philosophy, the wiki notes that single-parameter typeclasses can be considered a “set of types”, while multi-parameter ones can be thought of as “relations between types”, and that’s exactly what we’re doing here.

Let’s try it out and write an instance for comparing 8-bit registers and immediate unsigned bytes. This isn’t how the compiler exactly handles all comparisons, because it has a few optimizations (mostly redundancy checking), but it makes explanation easier.

That was straightforward, and testing it out shows that it works. But what if we swap the argument order? Well, GHC tells us:

RIP. But the definition for this missing instance is trivial — it’s merely the one just defined, only with its arguments flipped. What gives? Is there a way to specify we’d like flipped versions of multi-parameter typeclasses by default? Is there a way to make the typeclass do this automatically?

Out of curiousity, and a craving to avoid repeating code for the purpose of declaring the flipped counterpart instance, I started looking at language extensions. The first that I came across was {-# LANGUAGE FunctionalDependencies #-}, which allows type deduction of a type from a set of one or more other types. This sounded relatively applicable (no pun intended) insofar as we’re always going to return the same type, but the second type parameter can be deduced from the first. Or so I thought, since a new problem arises in that a first argument of Register8 could ambiguously indicate a second argument of another Register8 or a Word8. Unable to get anything meaningful happening, I took it back to the drawing board.

I did some further digging, and came across mentions of using {-# LANGUAGE FlexibleInstances #-} coupled with extensions for allowing undecidability, but I admittedly have too naïve an understanding to grasp what’s going on there, so at that point I thought that there must be a simpler way. It can’t be that obscure a circumstance, and I don’t profess to be an expert at Haskell, but I’d rather write code that is as understandable by others, and by newcomers, as possible — not to mention that an overuse of extensions surely doesn’t help with portability.

So what did I end up going with in the end?

Of course, it requires redeclaring each function which belongs to the typeclass, where a more “elegant” solution may not, but it’s much less of an eyesore than I thought it’d be, and is trivial to understand, even if it feels just a little redundant.

My takeaway from this is that Haskell’s ecosystem and especially its extensions are a vast world that grant you immeasurable power and expression, but it’s easy to get lost in that world if you’re not familiar with it, and sometimes there’s nothing wrong with what first comes to mind.

Oh, and if you happen to think up an elegant way of avoiding the use of MultiParamTypeClasses too, then feel free to get in touch.

Lazyboy is an embedded domain-specific language for programming the Nintendo Game Boy in Haskell. You can follow its development on GitHub.