Functional Programs That Explain Their Work

Roly Perera, Umut A. Acar, James Cheney, Paul Blain Levy

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present techniques that enable higher-order functional computations to "explain" their work by answering questions about how parts of their output were calculated. As explanations, we consider the traditional notion of program slices, which we show can be inadequate, and propose a new notion: trace slices. We present techniques for specifying flexible and rich slicing criteria based on partial expressions, parts of which have been replaced by holes.

We characterise program slices in an algorithm-independent fashion and show that a least slice for a given criterion exists. We then present an algorithm, called unevaluation, for computing least program slices from computations reified as traces. Observing a limitation of program slices, we develop a notion of trace slice as another form of explanation and present an algorithm for computing them. The unevaluation algorithm can be applied to any subtrace of a trace slice to compute a program slice whose evaluation generates that subtrace. This close correspondence between programs, traces, and their slices can enable the programmer to understand a computation interactively, in terms of the programming language in which the computation is expressed. We present an implementation in the form of a tool, discuss some important practical implementation concerns and present some techniques for addressing them.
Original languageEnglish
Title of host publicationProceedings of the 17th ACM SIGPLAN International Conference on Functional Programming
Place of PublicationNew York, NY, USA
Number of pages12
ISBN (Print)978-1-4503-1054-3
Publication statusPublished - 2012

Publication series

NameICFP '12


  • debugging, program slicing, provenance

Fingerprint Dive into the research topics of 'Functional Programs That Explain Their Work'. Together they form a unique fingerprint.

Cite this