School of Computer Science and Engineering, UNSW
CRICOS Provider No. 00098G
Session 1, 2004
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.
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.
Assignment: To be determined
The statelessness of the web protocol HTTP has inspired a number of people to draw parallels to purely functional programming.
Assignment: Implement a web site using WASH or extend WASH
Allocated to Thomas Sewell
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.
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.
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
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.
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.
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)
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.
Allocated to Roshan Ragel (6a) and Zixiao Jake He (6b)
Aspects of the implementation of functional languages range from abstract machines over program transformations to supporting tools, such as debuggers and profilers.
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
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.
Generic Haskell is a prototype generic programming language based on Haskell.
Assignment: An application in Generic Haskell
Allocated to Michael Leeming
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.
OpenGL is an industry standard for graphics programming, which has been made available in Haskell by the HOpenGL binding.
Assignment: A simple 3D game
Allocated to Hugh Rayner
wxHaskell is a binding to the cross platform GUI toolkit wxWidgets.
Assignment: A game or other graphical application.
Allocated to Wei Tan
This is a preliminary schedule of the student presentations. Each presentation extends over approximately one hour plus time for discussion.
|#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)|