Functional programs that explain their work

We present techniques that enable higher-order functional compu-tations to “explain ” their work by answering questions about how parts of their output were calculated. As explanations, we con-sider 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 fash-ion and show that a least slice for a given criterion exists. We then present an algorithm, called unevaluation, for computing least pro-gram slices from computations reified as traces. Observing a limi-tation of program slices, we develop a notion of trace slice as an-other form of explanation and present an algorithm for computing them. The unevaluation algorithm can be applied to any subtrace o