Dynamic Slicing Based on Redex Trails

Claudio Ochoa, Josep Silva, Germán Vidal

ACM SIGPLAN 2004 Symposium on Partial Evaluation and Program Manipulation (PEPM 2004), Verona (Italy). ACM Press, pp. 123-134, 2004.

Tracing computations is a widely used methodology for program debugging. Lazy languages, in particular, pose new demands on tracing techniques since following the actual trace of a computation is generally useless. Typically, they rely on the construction of a redex trail, a graph that describes the reductions of a computation and its relationships. While tracing provides a significant help for locating bugs, the task still remains complex. A well-known debugging technique for imperative programs is based on dynamic slicing, a method to find the program statements that influence the computation of a value for a specific program input. In this work, we introduce a novel technique for dynamic slicing in lazy functional logic languages (although the ideas also apply to pure lazy functional languages like Haskell). Rather than starting from scratch, our technique relies on (a slight extension of) redex trails. We provide a method to compute a correct and minimal dynamic slice from the redex trail of a computation. A clear advantage of our proposal is that one can enhance existing tracers with slicing capabilities with a modest implementation effort, since the same data structure (the redex trail) can be used for both tracing and slicing.

Available: PDF BibTeX-Entry

Germán Vidal