Declarative programming languages have higher levels of expressionand abstraction than most other programming paradigms. Not only does declarative programming reduce source code — it also prevents many common bugs that cripple any large C++ or Java development project.

Yet, while the expressive nature and robustness of declarative programming are appreciated in academic circles, the vast majority of software engineers have never heard of, let alone experienced, languages such as Mercury, Oz, or Haskell.

Ironically, hardware engineers are adamant about declarative programming. Though few have heard it coined as such, structural HDL declares what to instantiate and how to wire it in with the rest of the system. When a hardware engineer rejects SystemC, most argue hardware is better represented in HDL due to its implicit parallelism — a trait found in most declarative languages.

Declarative programming has two major sub paradigms: logic and functional. General purpose logic programming languages include Prolog and Mercury. For hardware, PSL/Sugar also belongs to this category. PSL declares system properties in terms of linear-time temporal logics (LTL). Functional programming languages include LISP, Scheme, Standard ML, Haskell, and Oz (technically speaking, Haskell is the only pure declarative language; the others include imperative mechanisms). For hardware design, Confluence is a functional programming language similar to Oz and Scheme with many HDL features mixed in.

Confluence is a purely structural RTL language. Similar to structural HDL, every Confluence statement and expression is implicitly parallel. As a functional programming language, Confluence employs powerful abstraction mechanisms including recursion, higher-order data-types, lexical scoping, and referential transparency. Yet the language is concise and easy to learn — its syntax is 3 times smaller than Verilog-1995. For implementation and verification, Confluence programs compile into Verilog, VHDL, C, and Python.

The goal of this article is to introduce declarative functional programming from a hardware perspective. Through a practical example we will illustrate techniques that add new dimensions to abstraction and design reuse, and hence, minimize source code. Using Confluence, we will construct a parametric finite impulse response (FIR) filter in less than 25 lines of code.

For designers new to Confluence, a complete tutorial, language reference, and compiler are available on-line from Launchbird Design Systems, Inc.

2 Basic Confluence syntax

Though this article is not meant to be a Confluence tutorial, it may help the reader to cover some basic notation. Fortunately Confluence is clean and concise. 90% of the language can be quickly introduced.

Confluence has 7 data types: integers, floats, booleans, lists, vectors, components, and systems. Integers, floats, and booleans are standard types found in most other languages. Lists are composite data structures useful for combining multiple data into a single entity. Vectors represent bit vectors found in HDL. Components are analogous to functions in other languages, and modules and entity/architecture pairs found in Verilog and VHDL. And finally, systems are the result of component instantiations.

Confluence is a generator language; programs are algorithms that generate RTL structures. In this regard, Confluence vectors are special types. They are the only data-type to appear at the output code (Verilog, VHDL, C, Python). The Confluence types are merely configuration parameters.

Confluence components are the fundamental building block. Components can have multiple inputs and outputs — input and output ports are denoted with "+" and "-" respectively. For example, the following AddIt component adds two numbers together:

Components can also be defined anonymously. The following connects an anonymous component to the variable AddIt and is equivalent to the previous example:

Components are instantiated between "{" and "}" with commas delimiting the component expression, the input expressions, and the output expressions. The following instantiates AddIt with inputs 1 and 2:

The place holder symbol "$" may be used at a port expression to return a value from an instantiation. This syntax enables nested instantiations:

Most Confluence operators follow C and Verilog convention. To distinguish between parameter operations and generated logic, vector operators are surrounded with single quotes:

Lists have important roles in functional programming. In Confluence, lists are manipulated with 4 operators — "head" returns the first element in a list, "tail" returns a list minus the first element, "::" constructs a new list given an element and another list, and "++" appends two lists together. Here are some examples:

3 FIR filter specification and high level subsystems

Our goal is to produce a generic FIR filter that can be reused for many different configurations. Specifically, the parameters should control the number of filter coefficients, the coefficient precision, and the input data precision. To meet these requirements, the filter IP core will have the following interface:

To begin the design, we partitioning the filter into three major subsystems: a bank of cascading registers for the filter's taps, a set of registered multipliers for multiplying coefficients with filter tap values, and a pipelined adder tree to sum up the multiplication results. The three subcomponents have the following interfaces:

4 Recursive components: DelayBank

"To iterate is human, to recurse, divine."
— L. Peter Deutsch, Robert Heller

Most programmers -- hardware and software alike -- understand recursion, but rarely use it. The problem is most languages do not implement recursion efficiently, and for practicality, force us to control our algorithms with iteration. Over time, "for" and "while" loops become second nature, as we long forgot the recursive elegance we experienced in our first course in computer programming.

But when a language is geared towards recursion, as with any functional programming language, the programmer has far more control to design elaborate structures that are difficult to express with iterative mechanisms. In fact some functional programming languages do not even have "for" and "while" loops; those that do are usually just syntactic sugar for a recursive function.

The transition from an iterative to a recursive mind set is not hard, but does take practice. For hardware design, we must think in terms of recursively instantiation and connecting components. Fortunately, many hardware structure are already inherently recursive, thus easing the transition.

When designing a recursive hardware component, we need to keep a few things in mind:

• What happens at each recursive step? What is instantiated and how is it connected?
• How is the next recursion called? How are the inputs modified from the previous instantiation?
• And how and when does the recursion terminate?

In this case, the answers to the three questions are:

• At each step, a tap register is instantiated and connected it to the input.
• Each recursive call receives the output of the tap register and NumberOfTaps is decremented by 1. A new vector list is constructed by adding the register's output to the list produced from the recursive call.
• The recursion terminates when NumberOfTaps reaches 0, thus returning an empty list.

The following DelayBank instantiation produces a list of three vectors with 1, 2, and 3 clock cycle delays from vector Vec0. The resulting structure is shown in Figure 1.

Figure 1 -- DelayBank structure

5 Mapping first class components: MultiplierBank

To implement the bank of registered multipliers, we could use recursion similar to the way DelayBank was constructed in the previous section:

In only 9 lines of code, MultiplierBank constructs registered multiplier logic for any number of input signals, with any precision. Though it provides decent flexibility, we can still achieve greater code density and wider design reuse.

This example illustrates a very common pattern in functional programming: given a list — or multiple lists, as in this case — perform an operation on each element, resulting in a new list. Higher-order data-types can exploit this common pattern, producing a new, generic abstraction.

5.1 Higher-order data-types: first-class components and Map

The hallmark feature of functional programming is higher-order data-types. Often referred as having "first-class status", a higher-order data-type can be defined anywhere in a program and is a valid argument or result of a function application. In Confluence lingo, first-class data can pass into or out of component instances (or systems) through ports.

So what's the big deal? Verilog, VHDL, and C have first-class data-types. What's new?

The importance is that in functional programming languages all data-types have first-class status, even functions themselves. In Confluence it is possible to define a component inside another component, then pass the internal component through a port to somewhere else in the system, just as if it were an integer, boolean, or any other variable.

Using first-class components, Map solves the problem of applying an operation to each element in a list, without having to recode the algorithm for every possible operation. Map takes a generic unary operation (a component with one input and one output) and a list of elements, and applies the operation to each element in the list producing a new list:

The resulting structure produced from Map is shown in Figure 2.

Figure 2 -- Map structure

Now, for example, if you need to add 4 to a list of integers, simply create a component to perform the addition them map the component across a list:

Similar to Map, Map2 applies a binary operation to 2 lists, resulting in a single list (Map2's implementation is left to you as an exercise). The structure generated from Map2 is shown in Figure 3.

Figure 3 -- Map2 structure

As an example, Map2 can be used to add two lists of numbers together:

Now with an understanding of first-class components, MultiplierBank's implementation becomes trivial (9 lines of code, down to 3):

6 List accumulation: AdderTree

In FirFilter, AdderTree sums up a list of signals produced from MultiplierBank. Again, we could write out the recursion by hand:

This illustrates another common functional programming pattern called accumulation. Not surprisingly, first-class components can be used to exploit higher levels of reuse.

6.1 Functional origami: folding

Accumulation, also called folding, is the process of applying a binary operation across a list of elements to produce a single result. The Fold instantiation accepts the following arguments:

where BinaryOperation is a 2-input, 1-output component, StartingElement is the initial value, and Elements is the list of items.

Fold starts by applying the BinaryOperation to the StartingElement and the head of the Elements lists. This result becomes the StartingElement for the next recursive call. The structure generated by a Fold is shown in Figure 4.

Figure 4 -- Fold structure

As an example:

is equivalent to:

Fold is implemented by the following:

Now using Fold, we can simplify AdderTree:

6.2 Other types of folds: Tree

The previous implementation of AdderTree may appear elegant, but in terms of logic design, is far from ideal. For one, AdderTree is not a tree at all, but rather a long cascading chain of adders. Secondly, the logic is not even pipelined; synthesis will certainly complain about a long critical path.

Fortunately, Confluence already has a component for constructing binary trees: Tree. Tree recursively applies a binary operation to each neighboring pair in a list, producing a new list. Tree also accepts a unary operation to be applied to the last element in the list if the input list has an odd number of items. It then recursively performs these same operations on the resulting lists until only a single element remains. Figure 5 illustrates the structure produced from Tree.

Figure 5 -- Tree structure

For AdderTree, the binary operation sign extends the inputs by 1 bit to prevent overflows, then adds the numbers and registers the result. To maintain data alignment in the tree, the unary operation also sign extends and registers the input data.

7 Completing the core: FirFilter

To finish off the filter design, we instantiate and wire-up DelayBank, MultiplierBank, and AdderTree to complete FirFilter's implementation. The complete structure is shown in Figure 6. Total source code is 23 lines.

Figure 6 --FirFilter structure

The resulting FirFilter IP core accepts any numeric precision and can implement a any number of coefficients, whether it is 3, 30, or 300.

To download the Confluence generated Verilog, VHDL, C, and Python, visit the Confluence FIR Filter project at OpenCores.

8 Conclusion

Clearly, declarative functional programming enhances hardware design. The characteristics of recursion and first-class components reduce source code size and increase IP core parametric flexibility. This level of design scaling also plays an important role in verification. For example, verifying a small design structure provides a high level of assurance for larger configurations which may be too expensive for practical simulation or formal verification.

As exemplified by FirFilter, DSP applications are prime candidates for functional programming based hardware design. But Confluence has also shown to excel in other areas including processor design, forward error correction coding, arithmetic structure generation, and reconfigurable computing (see the variety of Confluence projects at www.OpenCores.org).

In addition, recent Confluence experiments have shown hardware centric functional programming has powerful implications for assertion based verification, hardware/software codevelopment, and SOC integration.

Tom Hawkins is the founder and principle engineer of Launchbird Design Systems, Inc. Prior to starting Launchbird, he was an FPGA designer specializing in high-throughput, datapath intensive DSP designs and custom EDA tools.