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.
For this project, design a very simple functional language and compile
it to 2D.
Your source language should ultimately include
- First-class, nested functions
- let and lambda
- Simple datatypes with a pattern-matching case expression
(nested patterns are optional)
- Peano arithmetic on natural numbers (represented using the
standard unary datatype)
- Decimal literals for natural numbers
- A static type system
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:
- Concrete syntax, abstract syntax, and parser based on
parser combinators (class topic)
- Type inference and translation into typed
intermediate form (class topic)
- Lowering to the primitive values and computations
of 2D (simple implementation idea)
- Defunctionalization to eliminate higher-order
functions (class topic)
- A-normalization to make sure there's a wire to
hold every input and output (more advanced implementation idea)
- Linearization to make sure each wire is used
exactly once (connected with advanced type systems)
- Control normalization to ensure every function is
a single extended basic block
- 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