Rohit's Blog

Occasional writing on software engineering.

Algebra-Driven Design, Part 4: The Initial Encoding, and Generating a Thousand Tests

scalaapi-design

Following Chapters 2 and 5 of Algebra-Driven Design by Sandy Maguire (tile algebra originally Peter Henderson’s, Functional Geometry, 1982). Parts 2 and 3 built the design. This one finally writes some Scala.

The goal here is emphatically not a good implementation. It’s an obviously correct one — slow, naive, and impossible to argue with — whose real purpose is to serve as an oracle for the test suite that will let us write a fast one in part 5.

🔗Every algebra comes with a free implementation

There’s an implementation you always get for nothing: make each constructor a data constructor. Object-oriented programmers know it as the interpreter pattern; the literature calls it the initial encoding.

enum Tile[A]:
  case Pure(a: A)
  case Cw(t: Tile[A])
  case Ccw(t: Tile[A])
  case FlipH(t: Tile[A])
  case FlipV(t: Tile[A])
  case Beside(l: Tile[A], r: Tile[A])
  case Above(t: Tile[A], b: Tile[A])
  case Quad(a: Tile[A], b: Tile[A], c: Tile[A], d: Tile[A])
  case Swirl(t: Tile[A])
  case Ap[X, B](f: Tile[X => B], x: Tile[X]) extends Tile[B]

No computation happens. We build a tree that mirrors the expression the user wrote, and interpret it later.

rasterize doesn’t appear, because it isn’t a constructor — it’s an observation, the way data gets out. It’ll be a function that pattern-matches on this tree.

Note Ap. It introduces X, which doesn’t appear in the result type, so X is existential — once a value goes into an Ap, its intermediate type is gone forever. In Scala 3 that needs the explicit extends Tile[B] form. This is a GADT (see the GADTs and variance post for the mechanics), and Scala 3 handles it without ceremony, though we’ll hit a rough edge shortly.

🔗The laws don’t hold yet

A one-to-one mapping between algebra and data is not enough. flipH ∘ flipH = id is a law, and FlipH(FlipH(t)) is plainly not t.

Fix: enforce laws by fiat in smart constructors.

// scala-check: skip
def flipH[A](t: Tile[A]): Tile[A] = t match
  case FlipH(inner) => inner
  case _            => FlipH(t)

def cw[A](t: Tile[A]): Tile[A] = t match
  case Cw(Cw(Cw(inner))) => inner
  case _                 => Cw(t)

Three Cw in the pattern, not four — the fourth is the call itself. Easy to get wrong, and Scala 3’s nested enum patterns make the intent about as legible as it can be.

You could keep going, hand-writing a case for every equation. For twenty laws that’s unmanageable. So instead, use the laws to shrink the problem: pick a minimal set of primitives and derive everything else.

Maguire lands on five:

enum Tile[A]:
  case Pure(a: A)
  case Cw(t: Tile[A])
  case FlipH(t: Tile[A])
  case Above(t: Tile[A], b: Tile[A])
  case Ap[X, B](f: Tile[X => B], x: Tile[X]) extends Tile[B]

Ten constructors gone. Where did the five come from? Trial and error — the book says so, and so do I. There’s little downside to guessing badly: a non-minimal set means more work, and an insufficient one means you get stuck inside five minutes and back up.

🔗Deriving the rest

Every other constructor now comes from a derivation we already did in part 2. This is the step where the algebra stops being documentation and starts being code generation you perform by hand.

// scala-check: skip
def ccw[A](t: Tile[A]): Tile[A] = cw(cw(cw(t)))

That’s the part-2 derivation, transcribed:

ccw(t) = ccw(cw(cw(cw(cw(t)))))    -- cw⁴ = id
       = cw(cw(cw(t)))             -- ccw ∘ cw = id

Likewise:

// scala-check: skip
def flipV[A](t: Tile[A]): Tile[A]              = ccw(flipH(cw(t)))
def beside[A](l: Tile[A], r: Tile[A]): Tile[A] = ccw(above(cw(l), cw(r)))
def quad[A](a: Tile[A], b: Tile[A], c: Tile[A], d: Tile[A]): Tile[A] =
  above(beside(a, b), beside(c, d))
def swirl[A](t: Tile[A]): Tile[A]              = quad(t, cw(t), ccw(t), cw(cw(t)))
def above[A](t: Tile[A], b: Tile[A]): Tile[A]  = Above(t, b)

One rule matters enormously here: derive using the smart constructors, never the raw data constructors. ccw is cw(cw(cw(t))), not Cw(Cw(Cw(t))). Use the raw ones and ccw(ccw(t)) builds six nested Cw nodes — a state cw guarantees is impossible, which means every downstream pattern match is now working from a false premise. Corollary: each primitive should be used by exactly one smart constructor, if you can manage it.

Functor and Applicative fall straight out of part 3:

// scala-check: skip
given Applicative[Tile] with
  def pure[A](a: A): Tile[A] = Pure(a)
  def ap[A, B](ff: Tile[A => B])(fa: Tile[A]): Tile[B] = Ap(ff, fa)
  override def map[A, B](fa: Tile[A])(f: A => B): Tile[B] = ap(pure(f))(fa)

map defined as ap(pure(f)) is the applicative law fmap f x = pure f <*> x, used as an implementation. It’s correct for every applicative, so cats gives it to you as a default — but writing it out makes the point that we’re not inventing anything.

And the monoid pair from part 3:

// scala-check: skip
def emptyTile[A](using A: Monoid[A]): Tile[A]                 = pure(A.empty)
def behind[A: Monoid](back: Tile[A], front: Tile[A]): Tile[A] = (front, back).mapN(_ |+| _)

🔗The interpreter

Now rasterize, pattern-matching over five cases:

// scala-check: skip
def rasterize[A](w: Int, h: Int, t: Tile[A]): Vector[Vector[A]] = t match
  case Pure(a) =>
    Vector.fill(h)(Vector.fill(w)(a))

  case FlipH(inner) =>
    rasterize(w, h, inner).map(_.reverse)

  case Cw(inner) =>
    rasterize(h, w, inner).transpose.map(_.reverse)

  case Above(top, bottom) =>
    rasterize(w, h / 2, top) ++ rasterize(w, h - h / 2, bottom)

  case Ap(f, x) =>
    val fs = rasterize(w, h, f)
    val xs = rasterize(w, h, x)
    fs.zip(xs).map { (fRow, xRow) => fRow.zip(xRow).map(_(_)) }

Five cases, each a transcription of a law from part 2. Cw swaps w and h in the recursive call because rotating swaps the dimensions. Above gives the odd pixel to the bottom half, exactly as the law says. Ap zips pointwise — the zippy applicative from part 3, now concrete.

This allocates a nested Vector at every node of the tree and it is slow. Deliberately. It is also, line for line, the specification.

A Scala 3 wrinkle. The Ap case relies on GADT refinement: matching Ap(f, x) has to teach the compiler that f: Tile[X => A] and x: Tile[X] for some existential X, and that the zip therefore produces A. Scala 3’s GADT reasoning is real but thinner than GHC’s, and depending on your version you may need to annotate the intermediate values or introduce the existential via a helper method with its own type parameter. If it fights you, that’s the known limitation and not your mistake.

🔗Generating tiles

For property tests we need random tiles. The pattern is fixed and worth memorising, because every recursive generator you ever write has this shape.

// scala-check: skip
import org.scalacheck.{Arbitrary, Gen}
import Arbitrary.arbitrary

def genTile[A: Arbitrary]: Gen[Tile[A]] =
  Gen.sized { size =>
    if size <= 1 then arbitrary[A].map(pure)
    else
      def smaller(k: Int): Gen[Tile[A]] = Gen.resize(size / k, genTile[A])
      Gen.frequency(
        3 -> arbitrary[A].map(pure),
        9 -> Gen.zip(smaller(2), smaller(2)).map(beside),
        9 -> Gen.zip(smaller(2), smaller(2)).map(above),
        2 -> smaller(1).map(cw),
        2 -> smaller(1).map(ccw),
        4 -> smaller(1).map(flipH),
        4 -> smaller(1).map(flipV),
        6 -> smaller(4).map(swirl),
        3 -> Gen.zip(smaller(4), smaller(4), smaller(4), smaller(4)).map(quad)
      )
  }

given [A: Arbitrary]: Arbitrary[Tile[A]] = Arbitrary(genTile[A])

Three things doing real work:

The size check terminates the recursion. Without it, genTile recurses forever. Every recursive generator needs a base case keyed off Gen.sized.

smaller splits the complexity budget. A beside gets two sub-tiles of half the size, so total complexity stays bounded. swirl and quad divide by four because they use their argument four times. Skip this and generation blows up exponentially.

The weights are not decoration. beside and above are weighted 9 against pure’s 3 because they’re what makes a tile structurally interesting. An unweighted generator produces a lot of nearly-trivial tiles and tests almost nothing.

And the rule from earlier, which matters most here: the generator calls the smart constructors. smaller(1).map(cw), never .map(Cw.apply). Generating raw data constructors would produce trees that violate our by-fiat laws and you’d spend an evening debugging a “failure” that’s really an invalid input.

🔗Which type to instantiate at

Subtle, and almost never discussed. Tile[A] is polymorphic; tests need a concrete A.

Maguire’s argument, which transfers directly: you want a type that’s small enough that any particular value gets hit (so edge cases can’t hide) but large enough that collisions are rare (so you don’t see false equalities). He uses Word8. In Scala that’s Byte — 256 values.

To exercise empty and behind, you additionally need a Monoid. Cheapest is List[Byte].

The failure mode is worth stating out loud: instantiate at Unit and every test passes, because all values of Unit are equal. Your suite is green and it is testing nothing.

🔗Observational equality, made executable

Now the payoff from part 2. Two tiles are equal iff they rasterize identically at every size. In a test, approximate “every” with “a random sample”:

// scala-check: skip
import org.scalacheck.Prop.forAll

def sameTile[A](t1: Tile[A], t2: Tile[A]): Prop =
  forAll(Gen.choose(1, 8), Gen.choose(1, 8)) { (w, h) =>
    rasterize(w, h, t1) == rasterize(w, h, t2)
  }

Sizes start at 1, never 0 — two zero-sized rasters agree trivially, the degenerate solution we flagged in part 2.

And the same idea gives us the Eq instance cats needs:

// scala-check: skip
given [A: Eq]: Eq[Tile[A]] with
  def eqv(t1: Tile[A], t2: Tile[A]): Boolean =
    (1 to 5).forall { w =>
      (1 to 5).forall { h => rasterize(w, h, t1) == rasterize(w, h, t2) }
    }

Not equality in any structural sense. Equality in the only sense the algebra ever defined.

🔗The suite

Now transcribe the laws.

// scala-check: skip
class TileSpec extends munit.ScalaCheckSuite:

  property("cw⁴ = id") {
    forAll { (t: Tile[Byte]) => sameTile(cw(cw(cw(cw(t)))), t) }
  }

  property("ccw ∘ cw = id") {
    forAll { (t: Tile[Byte]) => sameTile(ccw(cw(t)), t) }
  }

  property("flipH ∘ flipH = id") {
    forAll { (t: Tile[Byte]) => sameTile(flipH(flipH(t)), t) }
  }

  property("x-symmetry: flipH ∘ cw = ccw ∘ flipH") {
    forAll { (t: Tile[Byte]) => sameTile(flipH(cw(t)), ccw(flipH(t))) }
  }

  property("flipV ∘ flipH = cw ∘ cw") {
    forAll { (t: Tile[Byte]) => sameTile(flipV(flipH(t)), cw(cw(t))) }
  }

  property("flipH distributes over beside, swapping arguments") {
    forAll { (a: Tile[Byte], b: Tile[Byte]) =>
      sameTile(flipH(beside(a, b)), beside(flipH(b), flipH(a)))
    }
  }

  property("above of besides = beside of aboves") {
    forAll { (a: Tile[Byte], b: Tile[Byte], c: Tile[Byte], d: Tile[Byte]) =>
      sameTile(above(beside(a, b), beside(c, d)), beside(above(a, c), above(b, d)))
    }
  }

Plus the typeclass laws, for free:

// scala-check: skip
  checkAll("Tile.applicative", ApplicativeTests[Tile].applicative[Byte, Byte, Byte])
  checkAll("Tile.monoid", MonoidTests[Tile[List[Byte]]].monoid)

At ScalaCheck’s default of 100 cases per property, that’s several thousand generated unit tests from about sixty lines. Which is the argument Maguire quotes from John Hughes: writing 3–4 tests per feature is linear work and misses everything that only shows up when two features interact; writing tests for every pair of features is quadratic and nobody does it. Property tests get the quadratic coverage at linear cost.

For a release build, crank minSuccessful to five figures and go home. You’ll have tens of thousands of unit tests by morning.

🔗What this bought

An implementation that is slow, allocation-heavy, and — as far as several thousand randomised checks can establish — correct.

More importantly, a frozen specification. The suite doesn’t test Tile’s internals. It tests observable behaviour, which means it constrains any implementation that claims to be this algebra.

So: any other implementation that passes this suite is also correct.

Which is the licence we need to throw all of it away.

Next: Part 5 — Finding the right observation, and rendering fractals, in which the ugliness of rasterize finally gets diagnosed, the implementation becomes a one-line type alias, and we render some pictures.

🔗Sources

  • Maguire, Sandy. Algebra-Driven Design. 2020. Chapter 5.1 (The Initial Encoding) and 5.2 (Generating Tests). https://leanpub.com/algebra-driven-design — the initial-encoding method, the minimal-primitive-set technique, the by-fiat law enforcement, the generator shape with its complexity budget, and the argument for choosing Word8 are all his.
  • Claessen, Koen & John Hughes. QuickCheck: a lightweight tool for random testing of Haskell programs. ICFP 2000 — the origin of property-based testing, and of ScalaCheck.
  • Hughes, John. Experiences with QuickCheck: Testing the Hard Stuff and Staying Sane. 2016 — the linear-vs-quadratic coverage argument, quoted by Maguire.
  • Henderson, Peter. Functional Geometry. 1982 — the tile algebra.
  • ScalaCheck (Rickard Nilsson), cats-laws and discipline (Typelevel), MUnit (Scala Center).

The Scala 3 translation and the note on GADT refinement in the Ap case are mine.