Rohit's Blog

Occasional writing on software engineering.

Algebra-Driven Design, Part 5: The Right Observation, and Rendering Fractals

scalaapi-design

The last of the series, following Chapter 5.3 of Algebra-Driven Design by Sandy Maguire (tile algebra originally Peter Henderson’s, Functional Geometry, 1982). Parts 2, 3, and 4 got us to a working, correct, extremely slow implementation and a property-test suite that pins down its observable behaviour.

Now we throw the implementation away. The suite means nobody can tell.

Rendering is plain java.awt.image.BufferedImage and javax.imageio.ImageIO — no browser, no dependencies beyond the JDK. Run the file, get a PNG.

🔗Three things that smelled

I flagged some unease in part 2 and a broken law in part 3. Time to collect the evidence.

Rows and columns are asymmetric. In the algebra, beside and above are perfect mirrors — one law defines each in terms of the other. In the observation they look nothing alike, because a list-of-lists forces you to pick row-major or column-major, and once picked, one direction gets ++ and the other gets a transpose sandwich.

The rotation law was found by guessing. rasterize(w, h, cw(t)) = rasterize(h, w, t).transpose.map(_.reverse). I tried combinations until one worked, and so did Maguire. Code you can only justify with “it seems to work” is code you don’t understand.

pure isn’t a homomorphism. This is the real one. ap respects the applicative structure; pure doesn’t. But an Applicative is a pair of operations defined relative to each other — having one half be a morphism and not the other is incoherent. Something is wrong.

The diagnosis, which is Maguire’s and which I’d never have reached alone:

Messy laws mean you’re reasoning about the wrong thing.

rasterize is a fine thing to implement. It is the wrong thing to reason about.

🔗What are we actually looking for?

The failed pure homomorphism is the clue. Morally, pure(a) fills all of space with a. rasterize can only make a finite grid. So whatever observation we should have been using must:

  1. Fill infinite space, so pure has somewhere to live.
  2. Combine pointwise, so ap keeps working.
  3. Treat horizontal and vertical symmetrically, so beside and above stop diverging.

There’s a structure that does all three and it’s embarrassingly familiar: functions.

The applicative instance for A => * is exactly what we need. pure ignores its argument and returns a constant — filling the entire domain. And ap applies both functions at the same point and combines:

def pure[A, R](a: A): R => A            = _ => a
def ap[R, A, B](ff: R => (A => B))(fa: R => A): R => B =
  r => ff(r)(fa(r))

Pointwise. Total. Symmetric in whatever the domain happens to be.

So propose a new observation — sample a tile at a point:

// scala-check: skip
def sample[A](x: Double, y: Double, t: Tile[A]): A

Continuous rather than discrete. Infinite rather than bounded. By convention, the square from (-1, -1) to (1, 1) is the part we’ll eventually draw; everything outside still has a value, we just don’t look at it.

🔗The laws, restated

Watch what happens.

sample(x, y, flipH(t))  =  sample(-x,  y, t)
sample(x, y, flipV(t))  =  sample( x, -y, t)
sample(x, y, cw(t))     =  sample( y, -x, t)
sample(x, y, ccw(t))    =  sample(-y,  x, t)

Four laws, one line each, perfectly symmetric. flipH negates x, flipV negates y, and the rotations swap-and-negate in opposite directions. cw ∘ ccw = id is now obvious on inspection — apply both substitutions and the negations cancel. In part 2 that took a derivation.

The transpose guesswork is gone, because there was never any transposing. There was a coordinate transform, and a matrix was the wrong place to look at it.

Subdivision:

sample(x, y, beside(l, r))  =  if x < 0 then sample((x + 0.5) * 2, y, l)
                                        else sample((x - 0.5) * 2, y, r)

sample(x, y, above(t, b))   =  if y < 0 then sample(x, (y + 0.5) * 2, t)
                                        else sample(x, (y - 0.5) * 2, b)

Also symmetric. beside splits on x, above splits on y, and the arithmetic is identical: shift the half you’re in to be centred, then scale up by two. (The transform runs backwards relative to intuition — you’re mapping the sample point from the outer space into the inner one, so you invert what you’d do to the image. That contravariance is the only genuinely confusing bit of the whole post.)

And the pair that failed before:

sample(x, y, pure(a))       =  a
sample(x, y, ff.ap(fa))     =  sample(x, y, ff) ( sample(x, y, fa) )

Both morphisms. pure fills space; sampling it anywhere gives a. The incoherence is gone because it was never in the Applicative — it was in rasterize.

🔗The implementation, in one step

Here’s the recipe, and it’s the most mechanical thing in the whole book:

  1. Find the denotation — the observation from which every other observation follows.
  2. Rearrange its type so the algebra’s type is the first parameter.
  3. Delete that parameter.
  4. What’s left is your implementation.
sample : (Double, Double, Tile[A]) => A
       ⟶  Tile[A] => (Double, Double) => A          -- step 2
       ⟶            (Double, Double) => A           -- step 3
opaque type Tile[A] = (Double, Double) => A

That’s it. That’s the library. The enum with five cases, the smart constructors with their pattern-matched law enforcement, the recursive Vector-allocating interpreter — all of it replaced by a function type, and every law we wrote becomes an implementation directly:

// scala-check: skip
object Tile:
  def pure[A](a: A): Tile[A] = (_, _) => a

extension [A](t: Tile[A])
  def sample(x: Double, y: Double): A = t(x, y)

  def flipH: Tile[A] = (x, y) => t(-x, y)
  def flipV: Tile[A] = (x, y) => t(x, -y)
  def cw: Tile[A]    = (x, y) => t(y, -x)
  def ccw: Tile[A]   = (x, y) => t(-y, x)

  def beside(r: Tile[A]): Tile[A] = (x, y) =>
    if x < 0 then t((x + 0.5) * 2, y) else r((x - 0.5) * 2, y)

  def above(b: Tile[A]): Tile[A] = (x, y) =>
    if y < 0 then t(x, (y + 0.5) * 2) else b(x, (y - 0.5) * 2)

  def quad(b: Tile[A], c: Tile[A], d: Tile[A]): Tile[A] =
    t.beside(b).above(c.beside(d))

  def swirl: Tile[A] = t.quad(t.cw, t.ccw, t.cw.cw)

Each body is the corresponding law, transcribed. There is no cleverness anywhere, because all the thinking happened in parts 2 and 3.

opaque type is doing real work. Outside this file Tile[A] is not a function — you can’t apply it, you can’t pattern-match it, you can only use the algebra. Zero runtime cost, genuinely sealed boundary, no escape hatch. This is the final encoding with an abstraction barrier the compiler enforces.

The Applicative is now inherited wholesale from the function applicative:

// scala-check: skip
given Applicative[Tile] with
  def pure[A](a: A): Tile[A] = (_, _) => a
  def ap[A, B](ff: Tile[A => B])(fa: Tile[A]): Tile[B] =
    (x, y) => ff(x, y)(fa(x, y))

And rasterize — the thing we spent two posts reasoning about — demotes to a convenience that samples on a grid:

// scala-check: skip
def rasterize[A](w: Int, h: Int, t: Tile[A]): Vector[Vector[A]] =
  Vector.tabulate(h, w) { (row, col) =>
    t(pixelCentre(col, w), pixelCentre(row, h))
  }

private def pixelCentre(i: Int, n: Int): Double = (i + 0.5) / n * 2 - 1

Sampling at pixel centres, which is why every rasterize law from part 2 involved fiddly off-by-one decisions about who absorbs the odd pixel. Those decisions haven’t disappeared — they’ve moved somewhere they belong, into a rendering concern, out of the algebra.

🔗Does it still pass?

Run part 4’s suite against it, unchanged. Same generators, same observational Eq, same properties.

Two implementations sharing nothing — one an allocating tree interpreter, one a composition of closures — and the suite can’t tell them apart, because observationally there is nothing to tell. That’s the abstraction barrier from part 2 paying out.

Expect one class of genuine failure: floating-point boundaries. The old Above split at h / 2 with integer division; the new one splits at y >= 0. At odd heights the pixel that lands exactly on the seam may differ. That’s not a bug in either implementation — it’s an under-specified law, and the honest fix is to tighten the law about which side owns the boundary rather than to fudge the test.

🔗Rendering, with nothing but the JDK

A colour, its monoid, and a file writer.

// scala-check: skip
final case class Colour(r: Double, g: Double, b: Double, a: Double):
  def argb: Int =
    def ch(d: Double) = (math.max(0.0, math.min(1.0, d)) * 255).round.toInt
    (ch(a) << 24) | (ch(r) << 16) | (ch(g) << 8) | ch(b)

object Colour:
  val clear: Colour = Colour(0, 0, 0, 0)

  // source-over compositing: `front` is drawn on top of `back`
  given Monoid[Colour] with
    def empty: Colour = clear
    def combine(front: Colour, back: Colour): Colour =
      val a = front.a + back.a * (1 - front.a)
      if a == 0 then clear
      else
        def mix(f: Double, b: Double) =
          (f * front.a + b * back.a * (1 - front.a)) / a
        Colour(mix(front.r, back.r), mix(front.g, back.g), mix(front.b, back.b), a)

Which gives us the last two constructors from part 3, for free:

// scala-check: skip
def emptyTile[A](using A: Monoid[A]): Tile[A] = Tile.pure(A.empty)

extension [A: Monoid](back: Tile[A])
  def behind(front: Tile[A]): Tile[A] = (x, y) => front(x, y) |+| back(x, y)

And the renderer:

// scala-check: skip
import java.awt.image.BufferedImage
import java.io.File
import javax.imageio.ImageIO

def render(w: Int, h: Int, t: Tile[Colour], out: File): Unit =
  val img = BufferedImage(w, h, BufferedImage.TYPE_INT_ARGB)
  for
    row <- 0 until h
    col <- 0 until w
  do img.setRGB(col, row, t(pixelCentre(col, w), pixelCentre(row, h)).argb)
  ImageIO.write(img, "png", out)

Eleven lines, zero dependencies, works on any JVM. Because Tile is a function rather than a grid, render is also resolution-independent — ask for 4096×4096 and you get genuine detail, not an upscale. That’s the payoff from insisting back in part 2 that we were designing images, not PNGs.

Getting a photo in is nearest-neighbour sampling:

// scala-check: skip
def fromImage(path: File): Tile[Colour] =
  val img = ImageIO.read(path)
  (x, y) =>
    val col = (((x + 1) / 2) * img.getWidth).toInt.max(0).min(img.getWidth - 1)
    val row = (((y + 1) / 2) * img.getHeight).toInt.max(0).min(img.getHeight - 1)
    val p   = img.getRGB(col, row)
    Colour(
      ((p >> 16) & 0xff) / 255.0,
      ((p >> 8) & 0xff) / 255.0,
      (p & 0xff) / 255.0,
      ((p >>> 24) & 0xff) / 255.0
    )

🔗Pictures

A checkerboard, from quad and nothing else:

// scala-check: skip
def checker(depth: Int): Tile[Colour] =
  if depth <= 0 then Tile.pure(Colour(0.1, 0.1, 0.15, 1))
  else
    val c = checker(depth - 1)
    val w = Tile.pure(Colour(0.95, 0.95, 0.9, 1))
    c.quad(w, w, c)

A Sierpinski-style fractal — three copies and a hole, recursively:

// scala-check: skip
def sierpinski(depth: Int): Tile[Colour] =
  if depth <= 0 then Tile.pure(Colour(0.05, 0.2, 0.4, 1))
  else
    val s = sierpinski(depth - 1)
    s.quad(s, s, emptyTile[Colour])

Three lines. render(1024, 1024, sierpinski(7), File("sierpinski.png")) and there it is — and because the tile is a function, depth 12 at 4096px costs render time but no memory.

And my favourite, which is the whole argument for part 3 in one expression:

// scala-check: skip
def invert(c: Colour): Colour = Colour(1 - c.r, 1 - c.g, 1 - c.b, c.a)

val halfInverted: Tile[Colour] =
  val fs: Tile[Colour => Colour] = Tile.pure(identity).beside(Tile.pure(invert))
  fs.ap(fromImage(File("photo.png")))

A tile whose left half is the identity function and whose right half inverts a colour, applied to a photo. Left half untouched, right half inverted, hard seam down the middle.

We never designed an image-processing library. We designed a spatial layout algebra, noticed in part 3 that it didn’t care what it was laying out, and got image processing as a consequence. That is what Maguire means by generality making a design powerful — usable in situations entirely unlike the ones it was built for.

🔗What the five posts actually cost

Honestly: about two evenings of thinking and one of typing, for a library I’d have hacked together in ninety minutes.

What that bought:

  • Two design bugs caught before implementation. The flipH/beside argument swap, and the missing pure homomorphism that revealed the architecture was wrong.
  • A test suite generated from the specification, which by construction cannot drift from it.
  • A complete implementation swap — tree interpreter to closures — with zero risk and no caller changes.
  • A final implementation that is one line long, because all the difficulty was moved into a place where thinking is cheap.

And the caveat I raised in part 1 still stands, more sharply than ever. Every equation here assumes referential transparency. t.cw.cw.cw.cw == t holds only because none of these functions can throw, block, or mutate. Haskell’s type system guarantees that precondition. Scala’s does not — opaque type seals the representation, but nothing seals the effects. The method transfers; the guarantee that makes the method sound does not.

That’s the running theme of this strand of the blog and I expect to keep finding it. Not a reason to write Haskell. A reason to know exactly which of my Scala habits are choices and which are consequences.

🔗Sources

  • Maguire, Sandy. Algebra-Driven Design. 2020. Chapter 5.3 (An Efficient Implementation). https://leanpub.com/algebra-driven-design — the “messy laws mean the wrong observation” diagnosis, the sample denotation, and the four-step denotation-to-implementation recipe are all his. The book is worth your money; these posts are a signpost to it.
  • Henderson, Peter. Functional Geometry. ACM Symposium on Lisp and Functional Programming, 1982 (revised 2002) — the original algebra, and the Escher Square Limit reconstruction.
  • Elliott, Conal. Denotational design with type class morphisms. 2009 — the denotational method underlying the whole approach.
  • cats (Typelevel) for Applicative and Monoid; ScalaCheck (Rickard Nilsson) for the suite carried over from part 4.

The Scala 3 translation, the opaque type framing, the JDK-only renderer, and the Monoid[Colour] source-over instance are mine. The fractal and half-inverted examples are adapted from figures in Maguire’s Chapter 2.