Higher Order Functions in Hardware Design

Mary Sheeran

I presented my experiences in using higher order functions in hardware design. I briefly described muFP, an extension of Backus' FP to synchronous streams, in which the combining forms are given a geometric as well as a behavioural interpretation. The result is a hardware design language that is particularly well suited for designing and reasoning about regular array algorithms. In 1986-87, it was used by engineers at Plessey to design a video picture motion estimator circuit that became a product. Unfortunately, the design group was closed down shortly afterwards.

Next, I presented Ruby, a generalisation of muFP in which circuits are modelled as binary relations on synchronous streams. I showed the kinds of higher order functions that are used in circuit design and some examples of their algebraic properties. Groups of higher order functions for various design idioms have been studied, for example regular arrays (including grids and hex-connected arrays), state machines, and high wire area networks (such as butterflies). An extensive suite of tools has been built (by people other than me): a formalisation in Isabelle, a transformation assistant, symbolic evaluators, visualisers, VHDL generators etc.

Ruby can perhaps be classified as an academic success. BUT, it is not used in practice. We have provided many of the tools for hardware design that the skeletons community plans to provide for high level parallel programming, yet we have not succeeded in finding users. Why is this? A possible reason is that our papers are cryptic and published in the wrong places. But maybe it is just that circuit design by formal derivation is just too hard to do! I asked this question in order to prompt the skeletons community into thinking about its plans for the future.

Finally, I briefly described my current work with Satnam Singh on a hardware design system that uses Haskell as the hardware description language.