The Power of Tiny DSLs

I was playing around with codeworld-api recently, and found myself with a pair of interesting problems:

• Place (move and scale) a grid (represented as a CodeWorld Picture) onto the canvas; and
• When responding to mouse clicks on the grid, reverse the transformation that placed the grid, so that I can determine which grid cell was clicked.

Placing the picture is easy — codeworld-api provides two functions that do exactly what I want:

• translated :: Double -> Double -> Picture -> Picture
• scaled :: Double -> Double -> Picture -> Picture

Going the other way is more difficult. After noodling around on paper trying to compute the inverse transform, I remembered that these transformations could be represented as 3x3 matrices (Wikipedia has some examples), and that inverting a 3x3 matrix is easy (provided that the affine transformation it represents hasn’t collapsed the space).

This means I have to compute the transformation twice: once as codeworld-api calls, and once as matrices. Or do I?

A Simple DSL

Let’s invent a simple DSL instead. We’ll start by defining a type for our transformations:

data Transform
  = Scale Double Double
  | Translate Double Double

We’ll also define the fold for Transform, as this will make it much easier to implement one of our interpreters. These functions are often really handy as a compact way to do case-analysis on a value:

-- Note: transform Scale Translate = id (over Transform)
--     , just as      foldr (:) [] = id (over lists)
--     , and    maybe Nothing Just = id (over Maybe a)
transform
  :: (Double -> Double -> a) -- ^ Handle 'Scale'
  -> (Double -> Double -> a) -- ^ Handle 'Translate'
  -> Transform
  -> a
transform f _ (Scale x y) = f x y
transform _ g (Translate x y) = g x y

Now, we need to interpret some Transforms into either a matrix or a codeworld-api function. In Haskell, DSLs are often associated with free monads and effect systems, but all we want is a linear sequence of commands, so a list will do fine.

Both interpretations are essentially foldMap over different monoids:

• To construct a matrix, map each Transform into a matrix, then multiply them all together.
• To construct a function Picture -> Picture, map each Transform into such a function, then compose them all together.

Unfortunately, the Monoid instances don’t give us what we want:

• We’ll be using the matrix types and functions from Ed Kmett’s linear package, which considers matrices as vectors of vectors. The Monoid instance for vectors is elementwise append; and

• The Monoid instance for functions is instance Monoid b => Monoid (a -> b), which combines results. That’s not what we want either — we want the instance associated with the Endo a newtype.

We could stand up a newtype for matrix multiplication, but it’s a lot of syntactic noise for a single use. Having noted that these are both foldMap, let’s move along and implement them manually.

Let’s start with toMatrix :: [Transform] -> M33 Double. M33 Double is the type of a 3x3 matrix of Double (a 3-vector of (3-vectors of Double)):

-- (!*!) is matrix multiplication
toMatrix :: [Transform] -> M33 Double
toMatrix list = foldr (!*!) identity $ map toMatrix' list
  where
    toMatrix' (Translate x y) = V3
      (V3 1 0 x)
      (V3 0 1 y)
      (V3 0 0 1)

    toMatrix' (Scale x y) = V3
      (V3 x 0 0)
      (V3 0 y 0)
      (V3 0 0 1)

Simplifying the Interpreter

My friend Tony taught me (and many others) that foldr performs constructor replacement. If we write the (:) calls in prefix position, we can see that map is expressible in terms of foldr:

  map f (x1 : x2 : [])
= f x1 : f x2 : []                  -- Effect of `map`
= (:) (f x1) ((:) (f x2) [])        -- Rewrite in prefix position
= ((:) . f) x1 (((:) . f) x2 [])    -- Observing that g (f x) = (g . f) x
= foldr ((:) . f) [] (x1 : x2 : []) -- Noting that we replaced (:) with (:) . f
                                    --         and we replaced  [] with []

In our toMatrix case, we’re using map to:

• replace (:) with (:) . toMatrix'; and
• replace [] with []

We then immediately replace (:) with (!*!) and [] with identity. This suggests that we can avoid folding twice, by:

• replacing (:) with (!*!) . toMatrix'; and
• replacing [] with identity.

This works, and we can avoid explicitly naming and applying the list argument while we’re at it (a process called eta-reduction):

toMatrix :: [Transform] -> M33 Double
toMatrix = foldr ((!*!) . toMatrix') identity
  where
    toMatrix' (Translate x y) = V3
      (V3 1 0 x)
      (V3 0 1 y)
      (V3 0 0 1)

    toMatrix' (Scale x y) = V3
      (V3 x 0 0)
      (V3 0 y 0)
      (V3 0 0 1)

The interpreter for codeworld-api functions only needs a couple of changes:

• We use transform to apply the arguments from Transform’s construtors to the appropriate codeworld-api functions (giving us functions Picture -> Picture instead of matrices); and
• (.) composes all the functions into one, like how we previously used (!*!) to multiply all the matrices together.

toCodeWorld :: [Transform] -> Picture -> Picture
toCodeWorld = foldr ((.) . transform CodeWorld.translated CodeWorld.scaled) id

Finishing Up

The rest is fairly mechanical. We can now write a canonical way to compute the [Transform] that places the grid on the screen:

gridTransforms :: Grid -> [Transform]
gridTransforms g =
  [ Scale (scaleFactor g) (scaleFactor g) -- Shrink to fit viewport
  , toCenter g -- Centre it around the origin
  ]

Rendering the grid is done by interpreting the [Transform] into a Picture -> Picture and applying it to the drawn grid:

renderGrid :: Grid -> Picture
renderGrid g = toCodeWorld (gridTransforms g) (drawGrid g)

Finally, we convert screen coordinates to grid coordinates by interpreting the transforms into a matrix, inverting it, multiplying the inverse matrix with the screen coordinate (as a vector) and rounding the results:

fromPoint :: Grid -> Point -> Maybe (Int, Int)
fromPoint g (x, y)
  | x' >= 0 && x' < w && y' >= 0 && y' < h = Just (x', y')
  | otherwise = Nothing
  where
    (w, h) = (fromIntegral $ width g, fromIntegral $ height g)
    (x', y') = (round invX, round invY)

    -- inv33 inverts a 3x3 matrix, and (!*) is matrix-vector multiplication
    V3 invX invY _ = inv33 (toMatrix (gridTransforms g)) !* V3 x y 1

Even in this relatively simple example, a small DSL saved us a lot of repeated work. It’s a useful technique to keep in your back pocket.

Afterword: Free Monoids

In hindsight, we used [Transform] as an approximation to the free monoid over Transform, which we then interpreted into the two types we cared about. (Reminder: lists are not free monoids, though they’re close enough for most purposes.) If this sort of thinking interests you, Justin Le has some great blog posts about free structures and the cool payoffs you can get when using them:

• Solving a 2018 Advent of Code puzzle using free groups, and accidentally optimising the solution

• Pulling a regular expression library almost out of thin air, using the free alternative

Acknowledgements

I would like to thank the Canberra Functional Programming (CanFP) meetup group, who reviewed drafts of this post.

nix-freeze-tree

I really like using Nix to build and manage my computers. Declarative machine definitions are incredibly powerful, and NixOS actually achieves what tools like Ansible and Chef have tried to reach for.

This web site is served from a NixOS machine, and is a collection of static files which get copied across by nix copy when it sends the built NixOS expression to the server. Until recently, my built website lived in a single derivation, which meant that any time I changed anything, a full rebuild of the site would get sent up my terrible internet connection.

I have written a tool to split up the big derivation called nix-freeze-tree (Hackage). It lets me split the website derivation down to individual files, and symlink them together back into the tree I want. The individual derivations are fixed-output derivations, which means that Nix knows the hash of the files before it builds the derivation, and can check the hash of the files to copy and skip files that haven’t changed.

If you’re reading this, then I’ve successfully wired nix-freeze-tree into my site build pipeline and deployed it.

Ergodox Firmware with Nix

A few years back, I bought an Infinity Ergodox. I’ve been very happy with it, especially once I customised the firmware to add keybindings for my Haskell work.

Unfortunately, the kiibohd repos have broken Infinity Ergodox support for some time, and nobody seems to care. Getting a working build involves jumping through some hoops, and even then modern GCC has slightly different semantics for inline functions, so it needs another patch on top of that.

Pulling all this together is the sort of thing that Nix excels at, so I threw together some Nix expressions to build the firmware, and to give me a shell with dfu-util for flashing. I’ve uploaded them to SourceHut for reference.

Texturing the Game

Android: Netrunner (A:NR) was one of Fantasy Flight’s “Living Card Games” (LCGs). These are a line of card games where you buy some base or “core” set of cards, and the publisher releases smaller additional packs each with a fixed set of cards.

In the early years of A:NR’s run, the single most controversial card was Account Siphon (“Siphon”), pictured below alongside other cards that synergised with it. A lot of words were written about Siphon, arguing that it was “overpowered”, or “balanced”, or “unfair”. In this article, I’m not going to argue those questions. I’m instead going to talk about how Siphon warped the rest of A:NR around itself, and that it is good to have cards like because they give a game something I call “texture”.

Avoid "Just" and "Simply" in Documentation

I am often annoyed by technical documentation that uses words like “just” and “simply” to prefix procedures that users are expected to perform. Such words are almost always waffle, and cutting them is almost always an improvement. When you see “just” or “simply”, you can be almost certain the action that follows is anything but. Instead of fixing the root problem, the documentation unconvincingly tries to paper over it.

“Just” and “simply” also insult the reader’s intelligence: the author is afraid that readers will run screaming if not constantly reassured that It Really Isn’t That Bad. If the instructions are deficient in any way, the reader will blame him or herself instead of the responsible party - the author. Again, there are better fixes: make the procedures acutally simple, and make the documentation actually clear and concise. Strunk and White may have gone out of fashion, but I believe that “omit needless words” is timeless. If you disagree, take it up with Orwell. (“If it is possible to cut a word out, always cut it out.”)

Just use the delete key and simply remove the offending words from documentation you write.