Red: Compiling Haskell to Reduceron

The idea for this project came out of my research in the fall, when I learned about the Reduceron project. The Reduceron is an experimental computer architecture and accompanying low-level language that can run code written in a pure functional programming language natively. Traditionally, functional programs are executed on modern hardware via a translation to standard machine-level programming languages (x86, ARM, etc.), but while this method does produce executable programs, it means that functional programs suffer overhead in the form of CPU and memory usage only required because of the incompatibilites of the imperative and functional programming styles. The Reduceron, then, offers a "functional" assembly language as a target for compilation of functional programs, eliminating the overhead incurred by the awkward translation.

Currently, the only way to generate Reduceron-executable code is via the F-lite compiler. F-lite is a minimal lazy functional language that supports standard functional constructs such as lambdas, algebraic data types, pattern matching, etc. The F-lite compiler performs necessary transformations required by the Reduceron specification over the source code and generates executable Reduceron code. However, the F-lite compiler exists mostly as a proof of concept and therefore does not contain any of the standard libraries used by practical functional programmers. In order for the Reduceron to become a viable architecture, there must be a way to compile arbitrary source code to it.

The programming language used by most people looking for a non-strict, pure functional language is Haskell. While there are several implementations of the Haskell specification, the most widely used compiler is the Glasgow Haskell Compiler (GHC). My goal is to write a new backend for GHC so that Haskell can be compiled directly to Reduceron. I believe that such a compiler will greatly facilitate further research into the field of functional programming languages and their implementations.

Implementation Notes:

The most difficult part of this project came from the knowledge gap that existed at the beginning. To put it simply, I had no idea where to start. While I knew that somewhere, buried deep in the heart of the GHC API, there was a data type that looked something like: data Expr = Var | Let (Expr) (Expr) | ... the problem was finding it and using the GHC API to access it. In order to explain what I eventually did, I will first give a brief overview of GHC itself.

GHC, like many modern compilers, consists of several consecutive pipeline stages each transforming the original source code in some manner. For GHC, these are: Parse, Rename, Typecheck, Desugar, Simplify. Since the point of using GHC as a front end for compiling functional code was to take advantage of the power of an established compiler, I won't go into much detail about these stages. Instead, what is important is that during the desugaring stage, GHC converts Haskell syntax, which is rather extensive and complicated, into a much smaller language called Core.

Core is an explicitly typed pure functional language supporting only the bare minimum number of features needed to represent Haskell programs. Core is one of the great successes of GHC and a big part of the reason GHC remains popular after several decades of development. Core consists of only 15 constructors, which makes it a good source for further transformations, and this is what I aimed to take advantage of when compiling to Reduceron code. Additionally, because Core was designed as an interface for performance optimizations in the form of Core -> Core passes, I was able to easily incorporate many standard optimizations.

Initially, my plan was to convert Core syntax directly to Reduceron syntax, but this was quickly deemed a bad idea. First of all, the current compilation scheme for Reduceron programs exists in the form of Flite, a "minimalist lazy functional language." The Flite compiler, written as part of the original Reduceron project, compiles and generates Reduceron templates. It also has the capability to create FPGA schematics containing the compiled program, as well as a an emulator for the Reduceron itself, generated in C. Not only is the compilation of Flite to Reduceron templates nontrivial, but the toolchain supporting FPGA and and C emulation backends is invaluable to the project. So to start from scratch would be a big waste of time- luckily, there was a more natural solution. Instead of rewriting the code to generate Reduceron templates from Core programs rather than Flite programs, I chose to create a translation from Core to Flite, then rely on the already-written Flite compilation scheme to create Reduceron templates.

Ultimately, then, my contribution to this project comes in the form of a single function, translate :: CoreProgram -> Flite.Prog, translating GHC's Core syntax to Flite's syntax. While some of the translation is trivial, such as converting let-expressions and lambdas, some of the language features in Core- for example, type classes- are not supported directly in Flite and so require additional logic. Additionally, the mapping from Core to Flite is not a lossless transformation- for example, Core is an explicitly typed language and carries around many type annotations and coercions, but Flite is technically an untyped language.

For a more detailed examination of the nuances of the conversion, I would encourage reading Translate.hs, which contains the translation code itself.