Topic List for Advanced Functional Programming
Session 1, 2004
Topic Area I: Combinator Libraries & EDSLs
Combinator libraries have long been a topic of interest in lazy
functional programming. They replace an ad-hoc library interface with a
systematically derived set of functions (called combinators) that
usually satisfy a set of desirable algebraic properties. This approach
to library design has first been explored for parser and pretty-printer
libraries, but has since then gained a much wider area of application
culminating in the design of so-called Embedded Domain Specific
Languages (EDSL). An EDSL is a domain specific languages (e.g., a
hardware description language or a web programming language) that is
implemented as a library for a general purpose language instead of being
implemented from scratch by building a custom compiler or interpreter.
Topic 1: Yampa - Robots in Haskell
Yampa is a library for reactive programming that can handle
discrete events and continous behaviours. It comes with an
infrastructure for programming both real and simulated robots.
To be determined
Topic 2: EDSLs for Web Programming
The statelessness of the web protocol HTTP has inspired a number of
people to draw parallels to purely functional programming.
Implement a web site using WASH or extend WASH
Allocated to Thomas Sewell
Topic 3: EDSLs for Hardware Description
There has been a significant amount of work on the design of EDSLs to
describe hardware for purposes of verification and low-level language
(e.g., VHDL) generation.
Assignment: Design a simple hardware
description EDSL with a library to generate VHDL.
Topic Area II: Meta Programming
Meta programs are programs manipulating programs. Meta
programming languages provide special support for this task,
especially when the manipulated language is the same as the
Topic 4: EDSLs for Device Drivers & Meta Programming
Device drivers contain a substantial amount of stylised code,
which lends itself to be generated with the result of fewers
bugs in the resulting driver.
Assignment: Investigate the application of meta
programming to the implementation of a Devil-like language.
Allocated to Sean Seefried
Topic Area III: Functional Data Structures
Algebraic data structures and pattern matching make FP languages ideally
suited for applications that make heavy use of data structures (such as
most applications from the area of symbolic computing). However, most
books on algorithms traditionally feature very imperative descriptions
of algorithms making them a less than ideal source for FP algorithms.
Topic 5: Tree Algorithms
The are is a large body of work on purely functional tree-based
algorithms. The aim of this topic is to select a few instructive
examples and to understand the interaction between formal reasoning and
Implement an application based on one of the discussed data structures,
or better even come up with a new data structure design (the latter
is a challenge)
Topic 6: Graph Algorithms
Graph algorithms are frequently used in computationally intensive
applications. Unfortunately, many optimised graph algorithms make
essential use of destructive updates and so require some thought to be
used in a functional context.
- (6a) Develop a generic graph library in Haskell
along the lines of the design outlined by Garcia et al.
- (6b) Comparative study of alternative
implementations of the maximum matching problem using Edmonds'
algorithm with Gabow's Labelling System.
Allocated to Roshan Ragel (6a) and Zixiao Jake He (6b)
Topic Area IV: Implementation Techniques
Aspects of the implementation of functional languages range from
abstract machines over program transformations to supporting tools, such
as debuggers and profilers.
Topic 7: Core - A Functional Intermediate Language
Core is the intermediate language of the Glasgow Haskell Compiler. It is a
purely functional language with the usual denotational semantics, but at
the some time has a clear operational interpretation. As such it is the
ideal vehicle for transformation-based optimisations. Related to Core
is the language of the Spineless Tagless G-machine whose operational
semantics is even closer to typical machine code.
Assignment: Formalise a Core-like lambda
calculus with unboxed values in LF using the theorem prover Twelf.
Allocated to Simon Winwood
Topic Area V: Generic Programming
Generic programming is about writing programs that work uniformly across
a whole range of data structures such that the programmer writes only
the generic version and specialisation to specific data structures is
left to the compiler.
Topic 8: Generic Haskell
Generic Haskell is a prototype generic programming language
based on Haskell.
An application in Generic Haskell
Allocated to Michael Leeming
Topic Area V: Graphics Programming
Industrial-strength graphics programming implies access to an
industrial-strength graphics or GUI library, such as OpenGL, GTK+, or wxWidgets. This raised two
issues: (a) how can an existing imperative graphics library be
accessed from a functional language and (b) in which form should
the library API be provided to the FP programmer.
Topic 9: 3D Programming with OpenGL
OpenGL is an industry standard for graphics programming, which has been
made available in Haskell by the HOpenGL binding.
A simple 3D game
Allocated to Hugh Rayner
Topic 10: GUI and 2D Programming
wxHaskell is a binding to the cross platform GUI toolkit wxWidgets.
A game or other graphical application.
Allocated to Wei Tan
Schedule of Presentations
This is a preliminary schedule of the student presentations.
Each presentation extends over approximately one hour plus time
|#10 [10 May]
||EDSLs for Device Drivers & Meta Programming (Sean Seefried)
|Core - A Functional Intermediate Language (Simon Winwood)
|#11 [17 May]
||Generic Haskell (Michael Leeming)
|EDSLs for Web Programming (Thomas Sewell)
|#12 [24 May]
||3D Programming with OpenGL (Hugh Rayner)
|GUI and 2D Programming (Wei Tan)
|#13 [31 May]
||Graph Algorithms, Part 1 (Roshan Ragel)
|Graph Algorithms, Part 2 (Zixiao Jake He)