Functional Programming

Our Functional Programming (FP) work addresses a wide range of topics in FP. Projects already undertaken range from formal reasoning about programs, through novel implementation methods, profiling, testing and tracing tools, to application studies and experiments with variants of functional programming for relational, embedded, and interactive computing.

See our group members for current research interests, and our software for distribution. Much of our work involves Haskell in some way.

For more information contact Colin Runciman or Matthew Naylor.

Current and Recent Projects

The Reduceron

(Funded by EPSRC from October 2008 to March 2010; Project Webpage)

We developed a reduction machine for lazy functional languages called the Reduceron. The Reduceron exploits wide, parallel memories and other custom architectural features to increase evaluation speed, and is prototyped in programmable hardware using a field-programmable gate array.

A Lazy Polytypic Grid

(Funded by EPSRC from July 2005 to June 2008; In collaboration with University of Leeds; Project Webpage)

This project involved re-expressing well-known visualisation algorithms (e.g. volumetric surface extraction) in the functional language Haskell. We aimed to make those algorithms:

• lazy, so that the whole dataset is not required all at once;
• datatype-generic (polytypic), so that the algorithm is independent of the original dataset storage format, including questions of irregular and unstructured sampling;
• grid-enabled, such that it is possible to distribute the processing tasks across a heterogeneous network of machines, harnessing any implicit parallelism in the algorithms to speed up the calculation for huge datasets.

SmallCheck and Lazy SmallCheck

(September 2006 to September 2008; In collaboration with Chalmers University; Project Webpage)

We developed two libraries for property-based testing in Haskell. Following the lead of QuickCheck (Claessen and Hughes 2000), these testing libraries SmallCheck and Lazy SmallCheck also use type-based generators to obtain test-sets of finite values for which properties are checked, and report any counter-examples found. But instead of using a sample of randomly generated values they test properties for all values up to some limiting depth, progressively increasing this limit. Furthermore, Lazy SmallCheck tests properties on partially-defined values, using the results to prune test spaces automatically.

Hat: Haskell Tracing

(Began July 2002; Part-funded by EPSRC; In collaboration with University of Kent; Project Webpage)

Hat is a source-level tracer for Haskell 98, the standard lazy functional programming language. Hat is a tool that gives the user access to otherwise invisible information about a computation.

Yhc: York Haskell Compiler

(Began 2006; Project Webpage)

Yhc is an extension of nhc98 featuring improved portability and a simple core language well-suited for program analyses and compiler backends.

Theses

Jason S. Reich. Property-based Testing and Properties as Types: A hybrid approach to supercompiler verification. PhD thesis, 2013. (PDF)

Neil Mitchell. Transformation and analysis of functional programs. PhD thesis, 2008. (PDF)

Matthew Naylor. Target-directed and hardware-assisted evaluation of functional programs. PhD thesis, 2008. (PDF)

Guanhua He. Verification of an Optimisation Algorithm of Stack Machine in Functional Programming Languages. MSc thesis, 2006. (PDF)

Mike Thyer. Lazy specialization. PhD thesis, 2003. (PDF)

Adam Bakewell. An operational theory of relative space efficiency. PhD thesis, 2002. Presents a new way to define and compare the space usage of different program evaluation strategies. (PDF)

Nathan Charles. Data model refinement, generic profiling and functional programming. PhD thesis, 2001. Shows how to express refinement of data models using a combinator library, and applies this technique to design improved profiling tools. (PDF)

Graeme Moss. Benchmarking purely functional data structures. PhD thesis, 2000. (PDF)

Tatsuru Matsushita. Expressive power of declarative programming languages. PhD thesis, 1999. (PS)

R. Noble. Lazy functional components for graphical user interfaces. PhD thesis, 1996. (PS)

I. Checkland. Speculative concurrent evaluation in a lazy functional language. PhD thesis, 1995.

Malcolm Wallace. Functional programming and embedded systems. PhD thesis, 1995. (PS)

D. Cattrall. The design and implementation of a relational programming system. PhD thesis, 1993. Describes Drusilla, a language based on relations rather than functions, and an implementation of it that infers suitable representions of relations.

Mike Firth's. A Fold/Unfold Transformation System for a Non-Strict Language. PhD thesis, 1990. Describes the design and implementation of the STARSHIP system.

Sandra Foubister. Graphical Application and Visualisation of Lazy Functional Computation, 1995. PhD thesis.

David Wakeling. Linearity and Laziness. PhD thesis, 1990. Points out the dichotomy between guaranteeing single-use (linearity) and yet hoping for term-sharing (laziness).

Ian Toyn. Exploratory Environments for Functional Programming. PhD thesis 1987. Describes two programming environments, Fly and Glide, including their facilities for debugging and handling multiple definitions. (TGZ)

Past Projects

Profiling

We have developed techniques that help reduce the amount of memory functional programs require. This includes profiling mechanisms, compiler technology for heap and code compression, and garbage collection techniques.

Applications of functional languages

The FLARE project involved applying functional langauges to real programming tasks. We also looked at extensions and generalisations of functional programming, foreign language interfacing, parallelisation, and benchmarking of data structures.

Program transformation and tracing

We looked at how to improve efficiency and to prove properties about functional programs. The STARSHIP system was one product of this research aimed at proof techniques, and the ART project looked specifically at tracing. We also did some work on partial evaluation and lazy specialisation.

Some further information can be found in the old FP web pages.