Tracing and Profiling

Profiling

Functional programs often display elegance and simplicity; yet their computational behaviour may be complex, depending on the subtle interplay of several mechanisms in the process of evaluation. The programmer sees only recursion equations; the machine performs normal order graph reduction using those equations as rules. Solutions that are concise as defining formulae can give rise in their execution to surprisingly large demands for machine resources. We have developed effective profiling techniques for analysing and reducing the memory use of lazy functional programs and for investigating parallelism without a parallel machine.

Papers

• Heap profiling of a lazy functional compiler, Colin Runciman and David Wakeling, in Glasgow Functional Programming Workshop 1992, pp.203-215, Springer-Verlag/BCS Workshops in Computing.
• Heap profiling of lazy functional programs, Colin Runciman and David Wakeling, Journal of Functional Programming 3(2), pp. 217-246, Cambridge University Press, April 1993.
• New Dimensions in Heap Profiling, Colin Runciman and Niklas Rojemo, Journal of Functional Programming 6(4), pp.587-620, Cambridge University Press, July 1996. (Also available as a York CS Tech Report, YCS 256.)
• Lag, drag, void and use - heap profiling and space-efficient compilation revisited, Niklas Rojemo and Colin Runciman, in Proceedings of ICFP'96, Philadelphia, USA, SIGPLAN Notices 31(6), pp.34-41, ACM Press, June 1996.

Tracing

We have also been looking into new ways of tracing lazy, higher-order computations so that critical properties can be observed and improved.

Many potential benefits of functional programming are widely acknowledged for certain classes of application; but the subtle pragmatics of lazy evaluation, necessary for purely functional programming of interactive systems, can lead to intricate program structures and unpredictable evaluation costs.

We developed a graphical binary tree browser which enables the user to observe the execution of a program, by displaying the program graph and allowing this graph to be browsed at selected stages in the computation.

Papers

• Techniques for simplifying the visualisation of graph reduction, Sandra Foubister and Colin Runciman, Proceedings of the Glasgow Functional Programming Workshop 1994, Springer-Verlag.
• Graphical application and visualization of lazy functional computation, Sandra Foubister, DPhil Thesis YCST 95/10

We later developed the Hat system, a comprehensive post-mortem tracer for Haskell, which allows the user to interact with a program trace using several different styles of browser: observation of equations, trails back from values to their causes, and an algorithmic debugger. Fuller information about the Hat system is at http://www.cs.york.ac.uk/fp/hat

Papers

• Tracing functional computations with redex trails - work in progress, draft Proceedings of 8th Intl. Workshop on Implementation of Functional Languages, Bonn, Germany, pp.361-366, Sept 1996.
• Tracing Lazy Functional Computations Using Redex Trails, Jan Sparud and Colin Runciman, PLILP'97.
• Complete and Partial Redex Trails of Functional Computations, Jan Sparud and Colin Runciman, IFL'97.
• Tracing and Debugging Lazy Functional Computations Jan Sparud, PhD Thesis, 1999.
• Advanced Redex Trails: Project Proposal, Colin Runciman, 1999.
• Freja, Hat and Hood - A Comparative Evaluation of Three Systems for Tracing and Debugging Lazy Functional Programs, Olaf Chitil, Colin Runciman, and Malcolm Wallace, in Proceedings of the 12th International Workshop on Implementation of Functional Languages, Aachen, Germany, September 4th - 7th 2000, LNCS 2011, 2001, pp. 176-193.
• Multiple-View Tracing for Haskell: a New Hat, Malcolm Wallace, Olaf Chitil, Thorsten Brehm, and Colin Runciman, in Proceedings of the Haskell Workshop 2001, Firenze, Italy.
• A Toolkit for Multi-View Tracing of Haskell Programs, Thorsten Brehm, Master's Thesis, RWTH Aachen, 2001.
• A Semantics for Tracing, Olaf Chitil, in Draft Proceedings of the 13th International Workshop on Implementation of Functional Languages, IFL 2001,lvsj, Sweden, 24-26 September 2001.
• Transforming Haskell for Tracing, Olaf Chitil, Colin Runciman, Malcolm Wallace, submitted to International Workshop on the Implementation of Functional Languages, Madrid, Sept 2002.
• Testing and Tracing Lazy Functional Programs using QuickCheck and Hat , Koen Claessen, Colin Runciman, Olaf Chitil, John Hughes, Malcolm Wallace, 4th Summer School in Advanced Functional Programming, Oxford, Preliminary version, August 2002.