Monthly Archives: March 2015

An FFT (Cooley–Tukey) for a synchronous dataflow extension to Feldspar

Unfortunately I’m not able to share most of my university course work, due to our honor code. There are some exceptions, though. For instance, the last assignment in Patrik Jansson’s MSc/PhD course Advanced Functional Programming at Chalmers University of Technology is self-directed and open-ended. The general task is to “read, understand, evaluate and extend an advanced Haskell code base”, with the underlying goal of getting us students involved with an ongoing local research project, or in open-source development by contributing to one of the more popular Haskell package on Hackage.

In this article I will merely provide some background for the work we did, including relevant references. The information below should suffice to give an overview of this project.

Emil Axelsson, one of the authors of the Feldspar language [1], which is an embedded DSL for digital signal processing that is implemented in Haskell, gave a guest lecture on combining deep and shallow embeddings [2], and how this technique was used for the implementation of Feldspar.

In our project, my lab partner Niklas Logren and me collaborated with Markus Aronsson, a PhD Student in the Software Technology division in the Department of Computer Science and Engineering at Chalmers. Markus is currently working on a synchronous data flow extension to Feldspar, i.e. an extension to Feldspar that allows it to operate on streams. For details, please refer to the corresponding paper [3].

We implemented an FFT based on Cooley-Tukey. Our implementation is based on the FFT implementation that is outlined by Bjesse, Claessen and Sheeran in their paper on the hardware description language Lava [4]. Our entire code is available in my Github repository gregorulm/fft_feldspar. Markus Aronsson’s Feldspar extension is currently work-in-progress and not publicly available. Our FFT implementation, though, will be part of the eventual release.

References:

[1] E. Axelsson, K. Claessen, G. Devai, Z. Horvath, K. Keijzer, B. Lyckegard, A. Persson, M. Sheeran, J. Svenningsson, and A. Vajda. “Feldspar: A domain specific language for digital signal processing algorithms”. MEMOCODE 2010.

[2] J. Svenningsson and E. Axelsson. “Combining deep and shallow embedding for EDSL”. Trends in Functional Programming, LLNCS 2012.

[3] M. Aronsson, E. Axelsson, M. Sheeran. “Stream Processing for Embedded Domain Specific Languages”, (draft, submitted to IFL 2014).

[4] P. Bjesse, K. Claessen, M. Sheeran, S. Singh. “Lava: Hardware design in Haskell”, International Conference on Functional Programming, pp. 174–184, 1998.