School of Computing

Olaf's Research Project Proposals

Tracing Real-World Functional Programs

The Haskell tracer Hat (www.haskell.org/hat) consists of a trace generation system plus various tools for viewing a trace. Hat demonstrated its enormous value for locating faults in Haskell programs. However, it is not used in practice, because its trace generation system only handles Haskell 98, a small subset of the real-world Haskell language compiled by the Glasgow Haskell compiler ghc. Recently Maarten Faddegon and I developed a new tracing method that Maarten applied in his algorithmic debugger Hoed. Thus at the heart of this project is to redevelop Hat such that it uses the new, lightweight method. This work will be followed by detailed studies of using traces of real-world Haskell programs. The experience will directly lead to ideas for improvements. For example, it is already clear that for most purpose only the computations of some program parts have to be traced whereas standard libraries and other parts are trusted to be correct and hence are not traced. Although trusting is a well-known concept in tracing, a useful scheme still needs to be developed.

Trace-Based Just-In-Time Compilation for Lazy Functional Languages

At runtime a trace-based just-in-time compiler identifies instruction sequences that are executed frequently. It then optimises these so-called traces, also at runtime, and later executes the optimised code instead of each original trace. Traces usually cross function call boundaries and thus their optimisation can remove substantial function call overhead. Because a trace has a simple, linear control-flow, it is easy to optimise. In 2013 Thomas Schilling submitted his PhD thesis on building a trace-based just-in-time compiler for the lazy functional language Haskell. He noted substantial speed-ups for some programs, but also obstacles that are specific to lazy evaluation. The aim of this project is to understand and remove these obstacles. Instead of developing Thomas’ compiler further, a new model compiler for a small core language would be developed. One possibility is to use the RPython meta-tracing framework, which was already used successfully for building the tracing just-in-time compiler Pycket, which implements a dialect of Scheme.

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 23/06/2017