In the series My first domain-specific language with Racket, I have created a simple hardware description language (HDL) called Tiny-HDL. The intent of the series was to illustrate the techniques for creating a domain-specific language in Racket, from parsing to code generation, with a focus on name resolution and semantic checking. In this post, I will focus on the runtime aspects: how can we simulate a digital circuit description in Racket.
Functional modeling of digital circuits
In this post, I focus on Register-Transfer Level (RTL) simulation of digital circuits with the following restrictions: there is only one clock domain and no three-state logic.
At the Register-Transfer Level, such a circuit has the following general structure:
- A register stores the current state and updates it on every clock tick.
- is the transition function that computes the next state
from the inputs and the current state:
- is the output function that computes the current outputs
from the inputs and the current state:
and are both pure functions. The only memory element is the register.
Several special cases of such circuits can be mentioned:
Modeling combinational circuits in a programming language can be fairly straightforward, but there are pitfalls. The developer must keep in mind that the program will not be executed as a sequence of operations, but will be synthesized into an interconnection of hardware components working concurrently.
As a consequence, the program must be expandable into a dataflow graph with a finite number of operations and no feedback loop. Recursion and looping constructs can be problematic if they cannot be fully unrolled: the maximum number of iterations must be known at compile time.
For instance, if I had to describe a circuit that computes the greatest common divisor of two positive numbers using Euclid’s algorithm, a recursive implementation would look like this:
(define (gcd a b) (cond [(> a b) (gcd (- a b) b)] [(> b a) (gcd a (- b a))] [else a])) (gcd 143 91) ; 13
Since the actual number of comparisons and subtractions depends on
themselves, we cannot infer the number of components that will be needed to
implement this function as a combinational circuit.
But if we know the maximum value
b can take, we can rewrite this
function with an iterative algorithm.
In the following example:
gcd-stepprocesses a pair
(a, b)and produces a new pair for the the next step;
N-1times; each result of
gcd-stepis passed as arguments to the next call.
(define (gcd-step a b) (cond [(> a b) (values (- a b) b)] [(> b a) (values a (- b a))] [else (values a b)])) (define (gcd N a b) (for/fold ([a^ a] [b^ b] #:result a^) ([i (sub1 N)]) (gcd-step a^ b^)))
If we unroll the loop, we can synthesize
gcd as a cascade of
gcd-step itself can easily be synthesized into a combinational
circuit with two inputs and two outputs.
When synthesizing a combinational circuit, iterative algorithms are translated into spatially replicated hardware elements. An alternative technique consists in reusing the same hardware in consecutive time slots, storing intermediate results as the algorithm is executed.
In a synchronous digital circuit, the elementary storage element is the D flip-flop. It can store one bit of data, and updates its state every clock cycle. The effect of a D flip-flop is to delay its input to the next clock edge. A register is a group of D flip-flops that store a piece of data encoded as a binary word.
In a sequential circuit, the outputs can no longer be computed from the current values of the inputs.
A sequential circuit transforms a sequence of values into another sequence. To model such a circuit in a purely functional language, we need to write functions that operate on sequence objects rather than single values. A naive implementation could use lists like in this example:
(define (gcd-step ra rb e a b) (cond [e (values a b)] [(> ra rb) (values (- ra rb) rb)] [(> rb ra) (values ra (- rb ra))] [else (values ra rb)])) (define (gcd sig-e sig-a sig-b) (define-values (sig-ra sig-rb) (feedback gcd-step (0 0) sig-e sig-a sig-b)) sig-ra) (gcd '(#f #t #f #f #f #f #t #f #f #f #f ) '(0 143 0 0 0 0 680 0 0 0 0 ) '(0 91 0 0 0 0 440 0 0 0 0 )) ; '(0 0 143 52 52 13 13 680 240 240 40 40)
In this implementation of the GCD, I have introduced an additional enable
e) to notify the circuit that a new pair
(a, b) is available.
Now, the arguments of
gcd are lists of values
and the result is a list of output values.
feedback is a macro that inserts a given combinational function
in a feedback loop with registers: in this example, it calls
and constructs lists of values for registers
rb, with 0 as their
feedback is similar to
but it returns a list of accumulated values like the Haskell function
feedback accepts a list as the initial seed value, and supports
several other lists as inputs:
(define-simple-macro (feedback fn (val ...) sig ...) #:with (x ...) (generate-temporaries #'(sig ...)) #:with (y ...) (generate-temporaries #'(val ...)) #:with (r ...) (generate-temporaries #'(val ...)) (for/fold ([r (list val)] ... #:result (values (reverse r) ...)) ([x (in-list sig)] ...) (define-values (y ...) (fn (first r) ... x ...)) (values (cons y r) ...)))
Using lists as a data structure for signals is not a general solution: when function
is called, we need to provide complete lists of input values
This works only because there is no feedback loop between
gcd and its environment.
If we want to model circuits using functions, we need a better signal data type to connect these functions as we would connect hardware components.
A detour via Haskell and Clash
Clash is a functional hardware description language
implemented as an embedded DSL in Haskell.
In Clash, circuits are modeled as Haskell functions that operate on objects
Signal defined as follows:
data Signal a = a :- (Signal a)
arepresents the data type of each sample of a signal;
:-is the data constructor for signals.
The above definition means that a signal is constructed as a pair whose first
element is a sample value and whose second element is another signal.
Since the second operand of
:- cannot be null, a signal always contains
an infinite number of samples.
The exact definition of the
Signal type in Clash includes the notion of
In this post, I will consider circuits that contain only one clock domain.
In Haskell, infinite data structures and feedback loops are made possible by the lazy evaluation strategy, where the value of an expression is only computed when needed. For instance, in Clash, a counter can be defined like this:
counter = c where c = 0 :- (add1 c) add1 (x :- xs) = (x + 1) :- (add1 xs)
which means that
counter is a signal
- the first sample is 0;
- the rest of the signal is the result of applying
add1is a function that adds 1 to each sample of a signal.
Let’s define a function that returns the first
n samples of a signal
as a list:
-- Taking zero samples returns an empty list. sampleN 0 _ =  -- When n > 0, we extract the first sample x from the signal, -- and we use sampleN recursively to get the next (n-1) samples. sampleN n (x :- xs) = x : sampleN (n - 1) xs
Here is what happens when we take the first 4 samples of the
sampleN 4 counter = sampleN 4 (0 :- (add1 counter)) -- Substitute the definition of counter = 0 : (sampleN 3 (add1 counter)) -- Apply sampleN with n > 0 = 0 : (sampleN 3 (add1 (0 :- (add1 counter)))) -- Substitute the definition of counter = 0 : (sampleN 3 (1 :- (add1 (add1 counter)))) -- Apply add1 = 0 : (1 : (sampleN 2 (add1 (add1 counter)))) -- Apply sampleN with n > 0 = 0 : (1 : (sampleN 2 (add1 (add1 (0 :- (add1 counter)))))) -- Substitute the definition of counter = 0 : (1 : (sampleN 2 (add1 (1 :- (add1 (add1 counter)))))) -- Apply add1 = 0 : (1 : (sampleN 2 (2 :- (add1 (add1 (add1 counter)))))) -- Apply add1 = 0 : (1 : (2 : (sampleN 1 (add1 (add1 (add1 counter)))))) -- Apply sampleN with n > 0 = 0 : (1 : (2 : (sampleN 1 (add1 (add1 (add1 (0 :- (add1 counter)))))))) -- etc. = 0 : (1 : (2 : (sampleN 1 (add1 (add1 (1 :- (add1 (add1 counter)))))))) = 0 : (1 : (2 : (sampleN 1 (add1 (2 :- (add1 (add1 (add1 counter)))))))) = 0 : (1 : (2 : (sampleN 1 (3 :- (add1 (add1 (add1 (add1 counter)))))))) = 0 : (1 : (2 : (3 : (sampleN 0 (add1 (add1 (add1 (add1 counter)))))))) = 0 : (1 : (2 : (3 : ))) = [0, 1, 2, 3]
In Clash, the
Signal type implements the
Functor typeclass, so we can convert
any unary function
f that operates on values into a function that operates on
We can use it to rewrite
add1 as follows:
instance Functor Signal where fmap f (x :- xs) = (f x) :- (fmap f xs) add1 = fmap (1+)
Signal also implements the
It defines a function
pure that can be used for creating constant signals.
It also defines an operator
<*> that will seem a little strange if you are
not familiar with applicative functors.
In fact, the operands of
<*> are two signals:
the left operand produces a sequence of functions,
and the right operand produces a sequence of values.
The result is a signal that produces the output of each function applied
to the value at the same position.
instance Applicative Signal where pure x = s where s = x :- s (f :- fs) <*> (x :- xs) = (f x) :- (fs <*> xs)
<*> provide a more general mechanism to make ordinary functions
operate on signals.
If a function
f takes N arguments, we can apply it to N signals
by following this process:
fin a signal using
<*>N times, with each input signal as the right operand of each application.
For instance, adding the values of two signals can be performed like this:
pure (+) <*> xs <*> ys
Using this technique, we can implement the
Num typeclass on signals,
comparison and boolean operators, and a
mux function that will be the
if-then-else for signals:
liftA2 f xs ys = pure f <*> xs <*> ys liftA3 f xs ys zs = pure f <*> xs <*> ys <*> zs instance Num a => Num (Signal a) where (+) = liftA2 (+) (-) = liftA2 (-) (*) = liftA2 (*) abs = fmap abs signum = fmap signum fromInteger = pure . fromInteger negate = fmap negate (.==.) = liftA2 (==) (.>.) = liftA2 (>) (.&&.) = liftA2 (&&) (.||.) = liftA2 (||) -- etc. mux = liftA3 (\c x y -> if c then x else y)
Now we can create a cyclic counter like this:
counterMod5 = c where c = 0 :- mux (c .==. 4) 0 (c + 1) sampleN 11 counterMod5 --> [0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0]
And finally, here is an implementation of the GCD:
gcd' e a b = ra where ra = 0 :- (mux e a $ mux (ra .>. rb) (ra - rb) ra) rb = 0 :- (mux e b $ mux (rb .>. ra) (rb - ra) rb)
Clash provides other facilities for creating sequential functions that follow the Medvedev, Moore, and Mealy structures. Explaining them is out of the scope of this post.
Implementing signals in Racket
The concept of signal, as explained in this section, is very close to the concept of stream in Scheme (SRFI41) and in Racket. The book Structure And Interpretation of Computer Programs (SICP) also contains a section about streams.
When I started writing an implementation of signals in Racket, my only source of inspiration was the Clash source code. I didn’t know anything about promises and streams in Racket, and I hadn’t read SICP.
This section is mostly based on my implementation of signals from scratch. While writing this post, I have made several changes to align the terminology and the implementation with the literature.
In Racket, lazy evaluation can be achieved using promises.
macro converts an expression into a promise,
and the force
function evaluates that expression.
The result of the evaluation is cached, so that we can
the same promise multiple times without the cost of reevaluating the expression.
Here is a proposed implementation of
force for signals.
Lazyness is achieved by wrapping the given body in a function.
The result is memoized in a variable
(define-simple-macro (signal-delay body ...) (let ([res #f]) ; Will store the value of the promise. (λ () (unless res ; If the promise has not been forced, (set! res (begin body ...))) ; compute its value and store it. res))) ; Return the stored value. (define-simple-macro (signal-force promise) (promise)) ; Call the λ created by signal-delay.
signal-delay would not work in a general-purpose implementation of promises.
In fact, if the delayed body returned
#f, we would mistake it for a
promise that has never been forced and the memoization would not work.
As we will see later, in the implementation of signals, the delayed expressions
will always produce truthy values.
A signal will be represented by a promise that produces a pair
(val . sig) where
val is the first value and
sig is a promise
that generates the rest of the signal:
(define-simple-macro (signal-cons val sig) (signal-delay (cons val sig))) (define (signal-first sig) (car (signal-force sig))) ; Returns the left element of the pair. (define (signal-rest sig) (cdr (signal-force sig))) ; Returns the right element of the pair.
Since the pair is wrapped in a promise, nothing is evaluated until the first
Signal conversion from and to lists
Like the Clash function
signal-take computes the first
of a signal and returns them as a list.
It is named after the Racket list manipulation function
(define (signal-take sig n) (if (positive? n) (cons ; Make a list with: (signal-first sig) ; the value of the first sample, (signal-take (signal-rest sig) (sub1 n))) ; the next n-1 sample values. empty)) ; If n is zero or less, return an empty list.
Without any syntactic sugar, a constant signal can be written as a circular
definition like in the example below.
Remember that inside
sig1 is not evaluated,
so we don’t need to worry about infinite recursion here:
(define sig1 (signal-cons 56 sig1)) ; The rest of sig1 is sig1 itself! (signal-take sig1 5) ; '(56 56 56 56 56)
To create signals, two other constructs are introduced.
list->signal converts a list into a signal.
signal is syntactic sugar to create signals from the list of its
To convert a finite list into an infinite signal,
list->signal maps the last
element of the list to a constant signal by creating a circular
like in the previous example:
(define (list->signal lst) (define rst (rest lst)) (define sig (signal-cons ; Create a signal: (first lst) ; with the first element of the list, (if (empty? rst) ; and if there are no more samples, sig ; cycle over the current signal, (list->signal rst)))) ; else, create a signal with the rest of the list. sig) (define-simple-macro (signal val ...) (list->signal (list val ...))) ; Pass the arguments as a list to list->signal. (define sig2 (signal 10 20 30)) ; The value 30 will be replicated forever. (signal-take sig2 5) ; '(10 20 30 30 30)
Operations on signals
Like we did in Haskell with the
we want to lift ordinary functions into functions that operate on signals.
A general solution for an arbitrary function
f consists in creating
f^ that accepts any number of signals as arguments, and that returns
another signal constructed like this:
- Make a list with the first sample of each argument, and call
- Make a list with the rest of each argument and call
- Cons the results of
f^into a new signal.
(define (signal-lift f) (define (f^ . sig-lst) ; The lifted version of f takes any number of arguments. (signal-cons ; It will return a signal: (apply f (map signal-first sig-lst)) ; with f applied to the first sample of each argument, (apply f^ (map signal-rest sig-lst)))) ; and the lifted f applied to the rest of each argument. f^)
For instance, the addition operation for signals will be implemented
by lifting the
(define signal+ (signal-lift +)) (define signal- (signal-lift -)) (define sig3 (signal+ (signal 1 2 3) (signal 10 20 30) (signal 100 200 300))) (signal-take sig3 5) ; '(111 222 333 333 333)
When the number of arguments is known, we can spare the calls to
map by using the following macro:
(define-simple-macro (signal-lift* f arg ...) #:with (tmp ...) (generate-temporaries #'(arg ...)) ; Make a unique name for each argument. (letrec ([f^ (λ (tmp ...) ; The lifted version of f takes the given number of arguments. (signal-cons ; It will return a signal: (f (signal-first tmp) ...) ; with f applied to the first sample of each argument, (f^ (signal-rest tmp) ...)))]) ; and the lifted f applied to the rest of each argument. f^))
generate-temporaries is a little trick to avoid checking that
contains distinct symbols (see the next example).
I don’t know whether choosing
signal-lift* rather than
is relevant in terms of performance,
but a benefit of the macro is that
f does not need to be a function.
For instance, we can implement a version of the
if form for signals:
(define signal-if (signal-lift* if _ _ _)) (define sig4 (signal-if (signal #t #f #t #f #t #t #f) (signal 1) (signal 0))) (signal-take sig4 8) ; '(1 0 1 0 1 1 0 0)
Finally, we can use
signal-lift* to implement
forms similar to
(define-syntax-parser signal-λ ; Lift a λ with the given list of arguments. [(signal-λ (sig:id ...) body ...) #'(signal-lift* (λ (sig ...) body ...) sig ...)] ; Lift a λ that accepts any number of arguments. [(signal-λ sig-lst:id body ...) #'(signal-lift (λ sig-lst body ...))]) (define-syntax-parser define-signal ; Define a variable that contains a signal. [(define-signal name:id val ...) #'(define name (signal val ...))] ; Define a function with the given list of arguments. [(define-signal (name:id sig:id ...) body ...) #'(define name (signal-λ (sig ...) body ...))] ; Define a function that accepts any number of arguments. [(define-signal (name:id . sig-lst:id) body ...) #'(define name (signal-λ sig-lst body ...))]) (define-simple-macro (for/signal ([var:id sig] ...) body ...) ; Create a lifted λ and apply it immediately to the given signals. ((signal-λ (var ...) body ...) sig ...))
define-signal is a shorthand for
(define name (signal ...))
(define name (signal-λ ...)).
We can use it to define functions whose arguments and results are signals,
but whose body uses ordinary operations on values:
; Multiply and accumulate. (define-signal (signal-mac a b c) (+ a (* b c))) ; Compute the mean of the given signals. (define-signal (signal-mean . sig-lst) (/ (apply + sig-lst) (length sig-lst)))
for/signal lifts its body and applies it to the given signals
; Compute the mean of these two signals. (define sig7 (for/signal ([a (signal 10 20 30)] [b (signal 40 5 100)]) (/ (+ a b) 2))
Two circuit description styles
Now we can implement the GCD example as:
(define signal> (signal-lift >)) (define (gcd sig-e sig-a sig-b) (define sig-ra (signal-cons 0 (signal-if sig-e sig-a (signal-if (signal> sig-ra sig-rb) (signal- sig-ra sig-rb) sig-ra)))) (define sig-rb (signal-cons 0 (signal-if sig-e sig-b (signal-if (signal> sig-rb sig-ra) (signal- sig-rb sig-ra) sig-rb)))) sig-ra) (signal-take (gcd (signal #f #t #f #f #f #f #t #f #f #f #f) (signal 0 143 0 0 0 0 680 0 0 0 0) (signal 0 91 0 0 0 0 440 0 0 0 0)) 12) ; '(0 0 143 52 52 13 13 680 240 240 40 40)
It is not always useful to decompose a complex circuit into basic operations
on signals like this.
In the above case,
gcd manages several internal signals that are not
In this case, we can use the macro
for/signal like this:
(define (gcd sig-e sig-a sig-b) (define sig-ra (signal-cons 0 (for/signal ([e sig-e] [a sig-a] [ra sig-ra] [rb sig-rb]) (cond [e a] [(> ra rb) (- ra rb)] [else ra])))) (define sig-rb (signal-cons 0 (for/signal ([e sig-e] [b sig-b] [ra sig-ra] [rb sig-rb]) (cond [e b] [(> rb ra) (- rb ra)] [else rb])))) sig-ra)
Registers and feedback loops
For readability, we can provide a
register form with built-in support for
feedback loops via the syntax parameter
(define-syntax-parameter this-reg (λ (stx) (raise-syntax-error (syntax-e stx) "can only be used inside register"))) (define-simple-macro (register q0 expr) (letrec ([res (signal-cons q0 (syntax-parameterize ([this-reg (make-rename-transformer #'res)]) expr))]) res))
These macros define three register variants with synchronous reset and enable inputs:
(define-simple-macro (register/r q0 sig-r sig-d) (register q0 (for/signal ([r sig-r] [d sig-d]) (if r q0 d)))) (define-simple-macro (register/e q0 sig-e sig-d) (register q0 (signal-if sig-e sig-d this-reg))) (define-simple-macro (register/re q0 sig-r sig-e sig-d) (register q0 (for/signal ([r sig-r] [e sig-e] [d sig-d] [q this-reg]) (cond [r q0] [e d] [else q]))))
A Medvedev-style state machine component can be implemented using this pattern:
(define (make-state-machine sig-cmd1 sig-cmd2) (register 'IDLE (for/signal ([st this-reg] [cmd1 sig-cmd1] [cmd2 sig-cmd2]) (match st ['IDLE (cond [cmd1 'RUNNING] [else 'IDLE])] ['RUNNING (cond [cmd1 'IDLE] [cmd2 'PAUSED] [else 'RUNNING])] ['PAUSED (cond [cmd1 'IDLE] [cmd2 'RUNNING'] [else 'PAUSED])]))))
And here is an implementation of the GCD using only one
to generate a signal of lists:
(define signal-list-first (signal-lift* first _)) (define (gcd sig-e sig-a sig-b) (signal-list-first (register '(0 0) (for/signal ([e sig-e] [a sig-a] [b sig-b] [ra-rb this-reg]) (match-define (list ra rb) ra-rb) (cond [e (list a b)] [(> ra rb) (list (- ra rb) rb)] [(> rb ra) (list ra (- rb ra) [else ra-rb])])))))
In the series My first domain-specific language with Racket, Tiny-HDL lacked a proper model of computation and runtime to be a convincing hardware description language. In this post, I have introduced a functional API for manipulating digital signals in Racket, similar to what Clash offers in Haskell.
As a next step, we could use it to improve Tiny-HDL with proper support for signals in the generated Racket code. At the syntactic level, we could also add constructs for describing sequential circuits.
Another approach could be to use this API directly, as an embedded DSL for hardware description in Racket. This is basically what I did in the examples that illustrate this post, but it is not my preferred approach. In fact, I tend to prefer an HDL where the supported syntax clearly maps to hardware, compared to a general-purpose language with a hardware description layer, where the synthesizable subset would be difficult to specify.
In a best-of-both-worlds scenario, I would use a Racket-based standalone DSL to write synthesizable circuit descriptions, and I would simulate them in a test environment written in Racket.