Projects for CS252r (Advanced Functional Programming)

It is unsatisfying to read about programming-language features without using them. Participants in the Advanced Functional Programming seminar will therefore explore language features through a sequence of modest programming exercises. Ideally the results of these exercises will combine to form an integrated whole. The exact nature of the exercises is negotiable, but the typical student will be encouraged to design and implement a very simple functional language, targeting either the ``two-dimensional'' programming language of the 2006 ICFP Programming Contest, or possibly targeting an intermediate language that compiles to hardware. The students whose research interests are connected to functional languages will be encouraged propose a unique project of personal interest.

A 2D compiler

For this project, design a very simple functional language and compile it to 2D. Your source language should ultimately include Your language should be powerful enough to handle the kinds of problems given for the programming contest, including multiplication, addition, list reversal, and even ray tracing.

Of course the compiler is not the point—after all, some contestants wrote compilers in three days. The benefit of this project is that it will provide a framework in which you can flesh out some of the ideas to be discussed in class, while also enabling you to learn a little bit about the implementation of functional languages. A nice implementation might look something like this:

  1. Concrete syntax, abstract syntax, and parser based on parser combinators (class topic)
  2. Type inference and translation into typed intermediate form (class topic)
  3. Lowering to the primitive values and computations of 2D (simple implementation idea)
  4. Defunctionalization to eliminate higher-order functions (class topic)
  5. A-normalization to make sure there's a wire to hold every input and output (more advanced implementation idea)
  6. Linearization to make sure each wire is used exactly once (connected with advanced type systems)
  7. Control normalization to ensure every function is a single extended basic block
  8. Box layout to get an actual 2D program (completely irrelevant to this class, but not without entertainment value)
You will have the chance to present some of these components to the class during the term.

We have prepared a more detailed handout on intermediate forms. We also have a sketch of a Haskell representation of a 2D program (without layout).

A project of your choice

The main criteria for a project of your own choosing is that (a) it should exercise ideas we discuss in class; and (b) there should be period milestones, ideally including code you can present to the class. Depending on your interests, your project can be either primarily an implementation project or something more researchy.

A middle way?

Visiting Professor Marc Feeley is quite interested in compiling functional languages to unusual hardware, including Field Programmable Gate Arrays (FPGAs) such as are made by Xilinx. Such a compilation path approaches the flexibility of pure software and also the performance of pure hardware. It may be possible to target some of Professor Feeley's intermediate forms rather than the 2D language.
Back to Advanced Functional Programming