UNSW   Faculty of Engineering myCSEPRINT VERSIONSITE MAP  
cse | School of Computer Science and Engineering (CRICOS Provider No. 00098G)
    #About CSE     #Undergraduate Study     #Postgraduate Study     #Timetables & Courses     #Research & Publications     #People & Work Units     #Help & Resources     #News & Events     #High School Portal

Last updated 17.05.04

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.

References:

Assignment: To be determined

Not allocated

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.

References:

Assignment: 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.

References:

Assignment: Design a simple hardware description EDSL with a library to generate VHDL.

Not allocated

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 manipulating language.

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.

References:

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 program design.

References:

Assignment: 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)

Not allocated

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.

References:

Assignment:

  • (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.

References:

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.

References:

Assignment: 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.

References:

Assignment: 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.

References:

Assignment: 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 for discussion.

Week Topic
#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)
Top Of Page

 ###
Site maintained by webmistress@cse.unsw.edu.au
Please read the UNSW Copyright & Disclaimer Statement