Streaming Computations in Feldspar

Abstract

We present a library for expressing digital signal processing algorithms using a deeply embedded language in Haskell. It is an extension Feldspar's stream library, which provides a data type for infinite sequences of values. Until now, streams have been confined to a set of explicit functions for expressing recurrence equations, delays and sampling. The extension we present removes the need for such functions, reducing the gap between streaming algorithms and their mathematical description; efficiency is maintained by optimising the network structures. We demonstrate the usefulness of our library by giving example implementations of common filters and control structures found in digital signal processing. Our library is built on top of Feldspar, a domain specific language for programming digital signal processing algorithms, and, like our extensions, is implemented as a deeply embedded language in Haskell. The Feldspar language itself offers high-level and functional style for describing digital signal processing algorithms, where the final aim of a Feldspar program is to generate high-performance low level code. Feldspar is based around a low-level functional core language, which is semantically similar to machineoriented languages, such as C, and operates at around the same level of abstraction. A number of libraries built on top of the core language are offered, enabling programming in a higher-order manner, one of which is Feldspar's stream library. Feldspar stream library contains a modified version of co-iterative streams, a central concept for reasoning about and optimising stream systems. In the co-iterative approach, each stream consists of a transition function and an initial state, where the transition function takes a state and produces a new state and an output value. The interesting property of co-iterative streams is that they allow one to handle infinite streams in a strict and efficient manner, instead of having to deal with them lazily. As the co-iterative approach provides a good foundation for reasoning about streams, the contributions of this project are based around such streams with added support various temporal operations.