Solving Advent Of Code on FPGAs with Haskell Clash

This account details how the author utilized the Clash library to solve the fourth day of the Advent Of Code (AOC) on an FPGA chip. Clash is a functional hardware description language (HDL) that compiles high-level designs written in Haskell down to a low-level synthesizable HDL, such as Verilog. The author emphasizes that FPGAs are digital circuits programmed at a very low level using an HDL.

To begin, the author explains the purpose of Clash, which is to enable programmers to solve complex problems using hardware design. AOC is an advent calendar of small programming puzzles, each involving a problem description, text input, and expected output. The author highlights that AOC serves as an excellent learning platform for new programming languages.

The author delves into the Clash standard library named clash-prelude, which provides alternative data types and APIs tailored for hardware designs. This library is essential because the standard Haskell library's core data types are not suitable for HDL synthesis. Clash's API relies on the KnownNat constraint to express static sizes, which are type-level natural numbers containing their values in their types.

The author highlights the importance of compile-time size information for FPGAs, as integrated circuits must be inter-connected with exact bit-width wires before synthesis. The DataKinds Haskell language extension is utilized to enable the use of term-level values at the type-level. Clash uses singleton types for type-level natural numbers defined in Clash.Promoted.Nat, which feature type-level operations like addition and multiplication.

The author discusses the necessity of singletons like SNats and explains how they work and why they are necessary. By leveraging KnownNat, Clash prelude features fixed-size data types that can be efficiently represented at the bit level. The library provides its own data types to represent fixed-size integers, such as Signed 64 and Unsigned 8, which come with convenient bitCoerce and resize functions for efficient conversion between representations.

To address the limitations of Haskell's lists in hardware design, Clash introduces the Vector type. This type allows for defining arbitrarily sized numbers that match the number of wires between ICs. Clash also provides the Index n type for values ranging from 0 to n, which is useful for countable things like vector positions or digits.

The author explains that Haskell's lists are not suitable for use with Clash, as they have unbounded size. Instead, Clash prescribes the vector type, which keeps track of the number of elements at the type-level. The author provides several examples of initializing and manipulating vectors using the Clash.Sized.Vector module.

Finally, the author introduces Binary Coded Decimal (BCD) as a special encoding for decimal numbers that can be more efficient than regular integers when handling base 10 numbers. BCD is particularly useful for outputting the AOC's solutions, which consist of decimal numbers. The author provides an example of defining BCD in Clash and determining the length of a BCD representation for a given integer.

In summary, the author demonstrates how to use Clash, a functional HDL, to solve the AOC day four puzzle on an FPGA chip. The author highlights the Clash standard library's features, focusing on singletons, fixed-size data types, vector types, and Binary Coded Decimal. With these tools, the author successfully implements a solution to the puzzle, showcasing the power and flexibility of Clash in hardware design.