Rohit's Blog

Occasional writing on software engineering.

Lava in Scala 3, Part 2: Combinators for Regular Circuits

scaladsl

Following “Lava: Hardware Design in Haskell” by Bjesse, Claessen, Sheeran and Singh (ICFP 1998). Part 1 set up the capability hierarchy and made a half adder run under the identity monad.

This post is about the vocabulary you build on top: a small set of combinators for describing circuits that have regular structure. It’s the part of the paper with the least theory and the most immediately stealable content, and it contains an observation the authors flag as a surprise.

🔗Circuits are first-order; descriptions are not

The distinction the paper draws, and it’s worth being precise about:

A circuit is a first-order object. Wires in, wires out. Silicon has no notion of a function as a value.

A circuit description is a program, and there is no reason for that program to be first-order. Lava uses higher-order functions freely to build circuits — a function that takes a circuit and returns a bigger one is perfectly ordinary, even though the result is still just gates.

The authors say they knew in theory that having circuits as first-class objects was a good idea, and were surprised how useful it turned out to be in practice. Their example: circuits containing look-up tables. VHDL descriptions of those tend to be long and hard to read precisely because the language has no suitable combinators — you end up writing out the regularity by hand, instance by instance.

That’s the whole argument in one observation. Regular structure wants a combinator, and if your language can’t express one, the regularity gets transcribed instead of captured.

🔗Serial composition, which cats already has

The first combinator feeds one circuit’s output into the next:

extension [F[_], A, B](f: A => F[B])
  def >->[C](g: B => F[C])(using Monad[F]): A => F[C] =
    a => f(a).flatMap(g)

And its list version:

def compose[F[_]: Monad, A](fs: List[A => F[A]]): A => F[A] =
  fs.foldRight((a: A) => a.pure[F])(_ >-> _)

compose(List(f, g, h)) is a pipeline: f feeds g feeds h.

Worth naming what >-> actually is. A function A => F[B] is a Kleisli arrow, and composing two of them left-to-right is Kleisli composition — cats spells it >=>, or Kleisli(f).andThen(Kleisli(g)). The paper’s serial-composition combinator for circuits is the standard monadic composition operator, and compose is foldRight over it with pure as the identity.

That’s not a deflation. It means the pipeline structure of a circuit is exactly the structure the host language already has a name for, which is why the combinator is one line rather than a traversal.

🔗Splitting buses

Now the ones specific to hardware. Both operate on lists of wires — a bus — and both divide it in half.

one f applies f to one half and leaves the rest alone. two f applies f to both halves independently.

def one[F[_]: Monad, A](f: List[A] => F[List[A]]): List[A] => F[List[A]] =
  xs =>
    val (l, r) = xs.splitAt(xs.length / 2)
    f(l).map(_ ++ r)

def two[F[_]: Monad, A, B](f: List[A] => F[List[B]]): List[A] => F[List[B]] =
  xs =>
    val (l, r) = xs.splitAt(xs.length / 2)
    (f(l), f(r)).mapN(_ ++ _)

Both take a circuit on n wires and give you one on 2n wires. two uses mapN rather than a for-comprehension deliberately: the two halves have no data dependency on each other, so this only needs Applicative. That’s not just tidiness — an applicative structure says “these are independent”, which is exactly what you want to be true of two halves of a bus that will sit side by side on silicon.

And repeated application:

def raised[A](n: Int)(f: A => A): A => A =
  a => (0 until n).foldLeft(a)((x, _) => f(x))

raised(3)(two)(f) gives you eight copies of f, each applied to one eighth of the input wires. Three halvings, eight pieces. Written out by hand that’s eight instances with index arithmetic; here it’s a number.

🔗Position-dependent components

The one that’s genuinely awkward without higher-order functions. A regular circuit whose components vary with position:

def decmap[F[_]: Monad, A, B](n: Int)(f: (Int, A) => F[B]): List[A] => F[List[B]] =
  xs => (n - 1 to 0 by -1).toList.zip(xs).traverse(f.tupled)

decmap n f applies f(n-1), f(n-2), … f(0) to successive elements. So the kth wire gets a component parameterised by k.

This is the shape the paper singles out as hard even in Ruby, its own predecessor: a circuit with regular structure but components that differ according to where they sit. It’s ubiquitous — every twiddle-factor stage in an FFT is one, as part 4 will show — and it’s a two-line traverse once circuits are values you can index over.

🔗Riffle

The prettiest one, and the one that does the most work later.

Riffle is the shuffle of a card sharp who interleaves two half-decks perfectly:

def riffle[A](xs: List[A]): List[A] =
  val (l, r) = xs.splitAt(xs.length / 2)
  l.zip(r).flatMap((a, b) => List(a, b))

def unriffle[A](xs: List[A]): List[A] =
  val (evens, odds) = xs.zipWithIndex.partition(_._2 % 2 == 0)
  evens.map(_._1) ++ odds.map(_._1)

Riffle interleaves the halves; unriffle separates them again.

Which lets you say something neat about wiring. An FFT butterfly stage pairs wire i with wire i + k/2 — a wiring pattern that, drawn out, is a mess of crossing lines. Expressed with riffle it’s: bring the pairs adjacent, run a column of two-input circuits, put them back.

def bflys[F[_]: Monad](n: Int)(bfly: List[C] => F[List[C]]): List[C] => F[List[C]] =
  riffleK >-> raised(n)(two)(bfly) >-> unriffleK

The permutation and its inverse bracket the computation, so the crossings never appear in the description at all. (riffleK is riffle lifted into F with pure — pure rewiring is a circuit that computes nothing.)

And then bit reversal, the permutation where a wire’s new position is the reverse of the binary representation of its old one. It appears at one end of every FFT and it is genuinely annoying to write directly. From riffle, it’s a fold:

def bitRev[F[_]: Monad, A](n: Int): List[A] => F[List[A]] =
  compose((1 to n).toList.map(i => raised(n - i)(two)(riffleK[F, A])))

Riffle at every scale, from the whole bus down. That’s bit reversal. I would not have found that, and having seen it I can’t unsee it — the binary structure of the index is the recursive halving structure of two.

🔗What this buys, concretely

Take the paper’s own summary: their FFT descriptions are short, and the corresponding VHDL would be several times longer.

That ratio is the point, but the reason for it is what’s worth taking away. VHDL isn’t verbose because it’s badly designed; it’s verbose because the regularity in a circuit has nowhere to live except in the instances. A size-16 FFT has four stages, each with eight butterflies, each with a different twiddle factor. In VHDL that’s a generate loop with index arithmetic attached to instances. In Lava it’s raised (n-i) two and a decmap.

And here’s the part that generalises past hardware: every one of these combinators is independent of the interpretation. one, two, raised, decmap, riffle, compose — none mentions Circuit, only Monad or Applicative. So they work unchanged under simulation, under symbolic evaluation, and under layout. The vocabulary you build to make descriptions readable is automatically vocabulary that every back-end understands.

That’s the property that makes a combinator library compound rather than just accumulate. It’s the same thing that happened in the tile algebra when the constructors turned out not to care what they were laying out.

🔗A note on the layout interpretation

Part 1 mentioned that Lava’s layout interpretation gives >-> a second meaning: A feeds B, and A is placed to the left of B. Now that the combinators are on the table, that idea gets better.

two f doesn’t just mean “apply f to both halves” — under layout it also means the two copies sit next to each other. raised n two f lays out 2ⁿ copies in a row. The combinator that made the description short is the same combinator that determines the floorplan, so the layout can’t drift out of sync with the netlist, because there is only one description.

The paper notes that combining behaviour and layout this way gives descriptions that in VHDL would require attaching complicated arithmetic expressions to instances. Having written that kind of index arithmetic in a different context, I believe them.

🔗Where we are

A vocabulary, all of it interpretation-agnostic, and enough of it to describe real circuits compactly.

What we still can’t do is the thing the whole design was for: take a description and get a logical formula out of it. That needs an interpretation that produces a description of the circuit rather than an answer — and it’s where the monad stops being plumbing and starts earning its keep.

Next: Part 3 — From circuit to SAT solver, in which symbolic evaluation turns a circuit into a netlist, the netlist turns out to already be in the form a SAT solver wants, and the monad quietly solves a problem I left open two series ago.

🔗Sources

  • Bjesse, Per, Koen Claessen, Mary Sheeran & Satnam Singh. Lava: Hardware Design in Haskell. ICFP 1998. The >->/compose/one/two/raised/decmap combinators, the riffle-based butterfly stage and bit-reversal permutation, the layout reading of >->, and the observations about look-up tables in VHDL and position-varying components in Ruby are all theirs.
  • Sheeran, Mary. μFP (1985); Jones & Sheeran, Ruby (1990) — where the combinator style originates.

The Scala 3 translation, the identification of >-> as Kleisli composition, and the note that two needs only Applicative are mine.