Programming FPGA using Haskell
Here is very short introduction to functional programming language Haskel and functional reasoning. For this we will use CλaSH compiler, that is extension of Haskell language being able to convert large set of Haskell code in either VHLD, Verilog or SystemVerilog for now. Installation instructions are available in hackage doc.
If you need just quick peek in examples, there is source code available of all examples presented here and is compiled in VHLD, Verilog and SystemVerilog. Code is automatically generated, but can be used as quick check of what kind of circuit code describes and what to expect from CλaSH compiler.
Premise is that circuits described functional way are considered simpler to reason about, compose and reuse. We are able to describe topology trough functional composition on abstract way without sacrificing about reasoning, how may registries are in use and where logic gates are. This approach allows describing similar if not same circuits as with Verilog and VHDL using new and fresh approach allowing composing more ambitious synchronous digital circuits.
Descriptions is mathematical in way that is trying to use tools from mathematical theory about composition. It is common to see relations described with mathematical laws.
Before running coding we should explain how calling functions in Haskell works.
In most languages if function takes 2 arguments
y it is called
f(x,y) where equivalent for this in Haskell is
f\ x\ y . This
come with advantage because Haskell supports partially applied functions
where only one out of two arguments is applied. Lets say that signature
Int -> Int -> Bool. We can interpret this as - it takes two
y and it returns boolean. When only first argument
is applied it returns function whit hremaining signature. When applying
Int -> Int -> Bool first
Int remaining is
Int -> Bool.
That is function that takes
Int and it returns
-- function of 2 Int, that telse if -- 1st argument is greater then 2nd greater :: Int -> Int -> Bool greater x y = x > y -- takes y and tels whatever it is greater than 2 isgt2 :: Int -> Bool isgt2 y = greater 2 y
or less verbose as partially applied
isgt2 :: Int -> Bool isgt2 = greater 2
One way to think about functions in Haskell is that each function takes
only one argument and it returns one value that can be function.
greater can be seen as
greater :: Int -> ( Int -> Bool ). So it takes an
Int and it returns
Int -> Bool. That is function that takes
Int and returns
In Haskell every function returns something. Pure functions, does not execute any action, but just transform input data and return relevant result. Pure functions, has important property that they always returns same output for same input and so they don’t have access to some external time changing data or internal state. In Haskell there is strong force to separate effects from pure functions.
Functional programming is about composition. Here it is example of signatures of 2 functions.
funcA2B :: a -> b funcB2C :: b -> c
funcA2B is function that takes type
a and returns
b, one example
is that it takes
Int and returns
b and it
c. For example it takes
Bool and returns
Bool. Having this
we are able to create function
funcA2C :: a -> c
by composing together
funcB2C to get
For composing two functions we need function
composeFunc :: (b->c) -> (a->b) -> a -> c composeFunc f g x = f (g x)
First we apply
g and then we apply result on
Moving back to
composeFunc it takes 3 arguments. First two are
f with signature
g with signature
x is of type
a. Function returns type
c and is same type
f returns. Looking differently it takes two functions that is
a->b and it returns function
a -> c.
minus1 x = x - 1 largeNum x = x > 3 superLargeNum = composeFunc largeNum minus1
superLargeNum is function composed by
each function is well defined, but we can either define it manually or
compiler can automatically deduce it.
-- simplified types minus1 :: a -> a largeNum :: a -> Bool superLargeNum :: a -> Bool -- actual types minus1 :: Num a => a -> a largeNum :: (Num a, Ord a) => a -> Bool superLargeNum :: (Num a, Ord a) => a -> Bool
We can read this, that function
superLargeNum transforms type
a has to be defined for class
class that has defined function
(-) as minus operator. (among others)
Ord has defined
composeFunc is commonly used and in Haskell it is defined as operator
(.) = composeFunc
Using this, one can alternatively define
superLargeNum = largeNum . minus1 -- or superLargeNum = (> 3) . (- 1) -- or superLargeNum x = (x - 1) > 3
. comes from function composition as defined in mathematics f
∘ g . Here we have showed implemention of
. as in
sometimes instead of implementation we get only laws. For function
id is identity function that returns argument
id :: a -> a id x = x
then function composition laws for ∘ are
id . f == f . id == f f . g . h == (f . g) . h == f . (g . h)
Instead of having function implementation available we sometimes have available laws that function obeys. It helps reasoning about how function behaves without knowing what it does. Laws also goes hand to hand with implementation.
Lets take for example type in CλaSH called
Signal a. This represent
a changing with clock.
Signal is concrete example of functor
a is type embedded in
Other than function composition of
Signal a there is different
composition available for functor.
funcA2B :: a -> b signalA :: Signal a
If we have function of type
a -> b and
Signal a, than functor
enables us to get
fmap :: (a -> b) -> Signal a -> Signal b
Functor obeys two laws
fmap id == id fmap (p . q) == (fmap p) . (fmap q)
Or equivalently when applying signal.
fmap id signal == signal fmap (p . q) signal == fmap p (fmap q signal)
Knowing this we can aswer next question. Does
any registries as for example D flip-flop?
Answer is, if that would be case, neither of laws would hold. Form first
law it would imply that on left we have signal delayed by 1 clock, and
on right non delayed signal and they are not same. Second law would
imply delay by 1 clock on left where right side made 2 delays, each by
To generate core we define function
topEntity. Generic type
be concrete and in this case we will use
Signed 7 what is 7 bit signed
topEntity :: Signal (Signed 7) -> Signal Bool topEntity signal = fmap superLargeNum signal
Executing command fmap can be used as operator. That is
Alternatively we can implement topEntity also as
topEntity signal = superLargeNum <$> signal -- or point free version topEntity = fmap superLargeNum -- or using fmap as operator topEntity = superLargeNum `fmap` signal
It is hard to tell witch version is most common among haskellers, but we can be sure, that due to laws all of them behaves same.
Compiling this exact into Verilog generates code as expected.
For generating output based on previous stored value we can use
function. Lets implement integrator using mealy machine. With integrator
we have in mind function that takes
Signal a and produces
and is representing sum of all previous values including current.
integrator signal = mealy mf 0 signal where mf state input = (nextstate,output) where nextstate = state + input output = nextstate
is function that takes 3 arguments. First parameter is a function on how
to generate next state from state and signal value. Signature of this
s -> i -> (s,o). In our code that is function called
mf is defined in
where block for local visibility so can not be used
integrator . What this
mf function does it takes 2 arguments
input and it returns tuple
(nextstate,output). Next clock cycle
nextstate will be passed again in
mf as argument
argument of integrator
0 is initial state value. Generated core will
provide reset signal that sets state to initial value.
If we now need to create FPGA core, we need to provide
it is full source instantiated with Fixed point arithmetics. We
SFixed 2 8, This is 10 bit signed fixed point
number. It is representing rational numbers from -2 <= x < 2.
module Integrator where import CLaSH.Prelude integrator signal = mealy mf 0 signal where mf state input = (nextstate,output) where nextstate = state + input output = nextstate topEntity :: Signal (SFixed 2 8) -> Signal (SFixed 2 8) topEntity = integrator
integrator can be used in other modules, to build larger and more
ambitious circuits. For example to make integrator of integrated signal
so that output of first integrator is feed in second one.
intInt = integrator . integrator
is sized vector with compile type defined size holding elements of same
type. It is similar to tuple, except that all elements are of same type.
Vec 5 (Signed 7) is type that holds 5 elements of type
Signed 7 what
is 7 bit signed number.
Vec is also an functor.
vs :: Vec 6 (Signed 9) vs = 1 :> 2 :> 3 :> 4 :> 5 :> 6 :> Nil vb :: Vec 6 Bool vb = fmap (> 3) vs -- that is <False,False,False,True,True,True>
:> is right-associativity operator that prepends vector on
right with value on left.
Nil is empty vector and is used, because
:> expects vector on right side.
Vec is defined at compile time and can be generic. Lets take
look on one of many functions from
Vec libraray that is
and has prototype
replicate :: SNat n -> a -> Vec n a -- "replicate n a" returns a vector that has `n` copies of `a`.
Vec 5 a is not same as
Vec 6 a and it means that
different type based on argument
n. For this to work,
n is of type
SNat x and is different type for each x. Value that has type
Signed 5 as 5 bit signed value can be -2 or 7, where value
SNat 3 represents number 3 as unique type.
Moving average is simple low pass FIR filter expressed as sum of last
n values. We will deliberately skip division in our example, so we
will in reality talk about moving sum.
Here is straight forward and naive option to describe moving average
movingAvarage n signal = mealy mf (replicate n 0) signal where mf state input = (nexts,output) where nexts = input :> init state output = fold (+) nexts
n is number of accumulated value is also size of Vec
used as internal state storage. Type of internal state is deduced as
Vec n a and is deduced from type of initial state value
replicate n 0 that returns
Vec that returns
n copies of 0.
init :: Vec (n + 1) a -> Vec n a
is function that takes
Vec with size
n+1 and returns all except last
element that is
Vec of size
nexts expressed as next state is vector right shifted by previous
value and perpended
:> with current clock
input value. Operation
works as fifo shift register.
fold is function best expressed with same picture as in
From signature we can conclude that
fold :: (a -> a -> a) -> Vec (n + 1) a -> a takes 2 arguments. First
is function of type
(a -> a -> a) an second argument is of type
Vec (n + 1) a. Function is than applied over vector in tree like
structure, enabling minimum latency.
Function f from out case is function
(+) (in haskell operator in
brakets is used as function). and has prototype
a -> a -> a and is
There is better
Lets try some optimization of moving average from previous section. Observing totals we can conclude we don’t need that many adders. Total output is changed at each clock only by value that enters fifo from one side and value that pops out of fifo on other. At each clock we need to subtract value that pops out and add value that enters from total. This comes at expanse of 2 extra sized registers (previous solution can be reduced by 1 sized register) but requires only 2 sized adders.
movingAvarage2 n signal = mealy mf ((replicate n 0),0) signal where mf (vec,total) input = ((nextVec,nextTot),output) where output = total + input - (last vec) nextVec = input :> init vec nextTot = output
mf has at this point signature
(Vec n a,a) -> a -> ((Vec n a,a),a).
Internal state type is tuple where first value is
vec used as fifo and
total accumulated in fifp.vec
are unpacked from tuple in input argument, so we are able to access this value, without unpacking them in body. Equivalent, but more verbosemf`
implemetaion is sketched as
mf state input = ... where vec = fst state -- first element of tuple total = snd state -- second element of tuple output = ...
Great power of composition comes from separating logic into reusable
parts and then composing them together in larger blocks. Function
fold are good examples we have used so far. Now lets try something
similar, by designing feedback loop.
+---+ +---+ input -->-| f |-->-| g |-->-+-->-- output +---+ +---+ | | ∨ ∧ +---+ | +----<-| h |-<--+ +---+
First lets figure out prototypes of each function
f :: Signal a -> Signal b -> Signal c g :: Signal c -> Signal d h :: Signal d -> Signal b
and feedback loop can be written directly from circuit diagram as
feedbackLoop :: (Signal a -> Signal b -> Signal c) -> (Signal c -> Signal d) -> (Signal d -> Signal b) -> Signal a -> Signal d feedbackLoop f g h input = out where out = g fout fout = f input (h out)
If user has available functions that works over primitive values like
Signal (Signed 16) for example, he can use
For example if
g :: Signed 16 -> Signed 16
gs working over signal would be constructed from
gs :: Signal (Signed 16) -> Signal (Signed 16) gs = fmap g -- or more verbose gs sig = fmap g sig
For function over 2 input arguments we can use library function liftA2
liftA2 :: (a -> b -> c) -> functor a -> functor b -> functor c
functor is in our example
Signal For example to get function
(-) to operate over
Signal we need to apply
signalMinus :: Signal a -> Signal a -> Signal a signalMinus = liftA2 (-)
To construct negative feedback looking like
+---+ input -->-( - )-->-| g |-->-+-->-- output | +---+ | ∧ ∨ +--------<------+
negativeFeedback :: Num a => (Signal a -> Signal a) -> Signal a -> Signal a negativeFeedback g = feedbackLoop (liftA2 (-)) g id
We have replaced
f argument is
There is subtle issue with this and in some cases this circuit can not
be synthesized. That is because we have feedback loop, so we have made
sure that there is delay in g function. If
g function is for example
fmap id so it works like wire this circuit is not stable any
more. To overcome this, we have to introduce delay in feedback. Function
h from previous diagram, becomes
register 0 instead of
negativeFeedback :: Num a => (Signal a -> Signal a) -> Signal a -> Signal a negativeFeedback g = feedbackLoop (liftA2 (-)) g (register 0)
register :: a -> Signal a -> Signal
is a function, that takes inital value, that outputs this value before
remaining of stream.
register is available in CλaSH libraray, but can
be implemented using
register initialValue signal = mealy mf initialValue where mf prevS input = (input,prevS)
What is even more surprising is that it can be done even vice versa.
mealey can be expressed in terms of
register. For details
check examples on
There are lot of features that were no covered. But are invaluable during development
- repl, (read eval print loop) that allows interactive development, type deduction
- ability to simulate in repl or compile in CPU native executable
- testebenches that generates VHDL / Verilog / Systemverilog and can be used directly in IDE
- full featured library, (ram and rom access and initalisation, multiple clock domains, type safe delays … )
From my and experience of many it takes lot of time and practice to grasp new programming language, what Haskell for those not familiar with functional programming certainly is. Reader with interest will be able to find lot of free resources available online for all levels of experience with open and active community.