Solving Advent Of Code on FPGAs with Haskell RetroClash – Tristan's Zettelkasten

propagates<br>through ES module imports) plus the main entry as a deferred<br>module. The FOUC theme applier above stays inline because it<br>must run pre-paint; the vendor Stork WASM loader above stays<br>inline because window.stork must be defined synchronously<br>before the stork.js module evaluates. -->

This post presents how I solved the Advent Of Code (AOC) day four on a Field-Programmable Gate Array (FPGA) chip using Clash:

First, I introduce the specifics of hardware design with Clash.

Next, I demonstrate three incremental designs to solve the first few problems.

Finally, I show how to compute the solutions on real hardware.

This post contains many code snippets for Haskell programmers and the full source code is available in my advent-of-clash repository. To dive deeper into how that works, I can only recommend the Retrocomputing with Clash book.

I invite you to follow along with this post by starting a REPL like this:

$ git clone https://codeberg.org/TristanCacqueray/advent-of-clash<br>$ cd advent-of-clash<br>$ nix run git+https://codeberg.org/TristanCacqueray/clash-osc#ghci<br>λ> import Clash.Prelude<br>λ> :load AdventOfClash.Utils<br>[1 of 1] Compiling AdventOfClash.Utils ( AdventOfClash/Utils.hs, interpreted )<br>Ok, one module loaded.<br>λ> showDigit 7<br>0b0011_0111

Introduction

FPGAs are digital circuits that can be programmed at a very low level using a Hardware Description Language (HDL). Clash is a functional HDL, that compiles high-level designs written in Haskell down to a low-level synthesizable HDL, such as Verilog. AOC is an advent calendar made of small programming puzzles, each consisting of a problem description, a text input and the expected output. AOC has always been a great way for me to learn a new programming language as the puzzles gradually introduce new concepts within the language.

Day four’s problem involved processing a grid similar to a single-rule Game Of Life. This was an interesting challenge because I only had a superficial understanding of Clash. Solving this puzzle has prompted me to implement my own RAM machine, a fundamental building block I hadn’t worked with before.

Clash Prelude

Before diving into FPGA designs, this section introduces the Clash standard library named clash-prelude. It provides alternative data types and APIs made specifically for creating hardware designs. This is necessary because the core data types provided by the Haskell standard library are not suitable for HDL synthesis.

KnownNat

Most of Clash’s API relies on the KnownNat constraint to express static sizes. They are type-level naturals that contain their values in their types. This compile-time size information is important for FPGAs because the integrated circuits (IC) must be inter-connected with exact bit-width wires before synthesis. This requires the DataKinds Haskell language extension to be able to use term-level values at the type-level. Thus, Clash uses singleton types for type-level natural numbers defined in Clash.Promoted.Nat with this constructor:

SNat :: KnownNat n => SNat n

… which can be created like that:

-- 41 is a type-level KnownNat value.<br>myNat :: SNat 41<br>myNat = SNat

-- 21 is also a KnownNat, declared with a type application inline.<br>twentyOne = SNat @21

SNats can be used to do type-level computation, for example:

-- From Clash.Promoted.Nat:<br>succSNat :: SNat a -> SNat (a + 1)<br>mulSNat :: SNat a -> SNat b -> SNat (a * b)

Note

These type definitions are rather special because they include type-level operations such as a + 1 or a * b.

The SNat values are known at compile time, for example by inferring the final type:

λ> :t succSNat myNat<br>succSNat myNat :: SNat 42

λ> :t mulSNat twentyOne (SNat @2)<br>mulSNat twentyOne (SNat @2) :: SNat 42

Tip

To improve the ergonomics of KnownNats, Clash provides custom compiler plugins to solve the constraints for advanced usage. The REPL must be set up this way:

ghci -XDataKinds -fplugin GHC.TypeLits.KnownNat.Solver -fplugin GHC.TypeLits.Normalise -fplugin GHC.TypeLits.Extra.Solver

Singletons like SNats took me a bit of time to get used to, though they are not too complicated in practice. This Unfolder episode #50 provides a solid explanation on how they work and why they are necessary.

BitPack Constraint

Thanks to KnownNat, the Clash prelude features fixed-size data types that can be efficiently represented at the bit level.

Sized Integers

Clash provides its own data types to represent fixed-size integers:

Unsigned n is analogous to Words.

Signed n is analogous to Ints.

For example, Signed 64 is equivalent to Int64, or Unsigned 8 is like Word8. These data types come with convenient bitCoerce and resize functions to convert between representations:

resizeDemo :: Signed 8 -> Signed 16<br>resizeDemo = resize

bitCoerceDemo :: Signed 8 -> Unsigned 8<br>bitCoerceDemo = bitCoerce

bitResizeDemo :: Signed 8 -> Unsigned 16<br>bitResizeDemo = resize . bitCoerce

These new...