Dynamic slicing based on redex trails

ABSTRACT

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. 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.

REFERENCES

• 1: E. Albert, M. Hanus, F. Huch, J. Oliver, and G. Vidal. Operational Semantics for Functional Logic Languages. Electronic Notes in Theoretical Computer Science, vol. 76 (Proc. of WFLP'02), 2002.
• 2: Sandip K. Biswas, A demand-driven set-based analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.372-385, January 15-17, 1997, Paris, France [doi>10.1145/263699.263753]
• 3: Sandip Kumar Biswas , Carl A. Gunter, Dynamic slicing in higher-order programming languages, 1997
• 4: B. Brassel , M. Hanus , F. Huch , G. Vidal, A semantics for tracing declarative multi-paradigm programs, Proceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.179-190, August 24-26, 2004, Verona, Italy [doi>10.1145/1013963.1013984]
• 5: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 6: A. Gill. Debugging Haskell by Observing Intermediate Data Structures. In Proc. of the 4th Haskell Workshop. Technical report, University of Nottingham, 2000.
• 7: Thomas Hallgren, Haskell tools from the programatica project, Proceedings of the 2003 ACM SIGPLAN workshop on Haskell, p.103-106, August 28-28, 2003, Uppsala, Sweden [doi>10.1145/871895.871907]
• 8: Michael Hanus, A unified computation model for functional and logic programming, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.80-93, January 15-17, 1997, Paris, France [doi>10.1145/263699.263710]
• 9: Michael Hanus , Christian Prehofer, Higher-order narrowing with definitional trees, Journal of Functional Programming, v.9 n.1, p.33-75, January 1999 [doi>10.1017/S0956796899003330]
• 10: M. Hanus (ed.). Curry: An Integrated Functional Logic Language. Available at: http://www.informatik.uni-kiel.de/~curry/+.
• 11: B. Korel , J. Laski, Dynamic program slicing, Information Processing Letters, v.29 n.3, p.155-163, October 26, 1988 [doi>10.1016/0020-0190(88)90054-3]
• 12: Yanhong A. Liu , Scott D. Stoller, Eliminating dead code on recursive data, Science of Computer Programming, v.47 n.2-3, p.221-242, May 2003 [doi>10.1016/S0167-6423(02)00134-X]
• 13: Francisco Javier López-Fraguas , Jaime Sánchez Hernández, TOY: A Multiparadigm Declarative System, Proceedings of the 10th International Conference on Rewriting Techniques and Applications, p.244-247, July 02-04, 1999
• 14: Henrik Nilsson , Jan Sparud, The Evaluation Dependence Tree as a Basis for Lazy FunctionalDebugging, Automated Software Engineering, v.4 n.2, p.121-150, April 1997 [doi>10.1023/A:1008681016679]
• 15: S. Peyton~Jones, editor. Haskell 98 Language and Libraries: The Revised Report. CUP, 2003.
• 16: Bernard Pope , Lee Naish, A program transformation for debugging Haskell 98, Proceedings of the twenty-sixth Australasian conference on Computer science: research and practice in information technology, p.227-236, February 01, 2003, Adelaide, Australia
• 17: Thomas W. Reps , Todd Turnidge, Program Specialization via Program Slicing, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.409-429, February 12-16, 1996
• 18: Jan Sparud , Colin Runciman, Tracing Lazy Functional Computations Using Redex Trails, Proceedings of the9th International Symposium on Programming Languages: Implementations, Logics, and Programs: Including a Special Trach on Declarative Programming Languages in Education, p.291-308, September 03-05, 1997
• 19: F. Tip. A Survey of Program Slicing Techniques. Journal of Programming Languages, 3:121--189, 1995.
• 20: G. Vidal. Forward Slicing of Multi-Paradigm Declarative Programs Based on Partial Evaluation. In Logic-based Program Synthesis and Transformation, LOPSTR'02, pp. 219--237. Springer LNCS 2664, 2003.
• 21: M. Wallace, O. Chitil, T. Brehm, and C. Runciman. Multiple-View Tracing for Haskell: a New Hat. In Proc. of the 2001 ACM SIGPLAN Haskell Workshop. Universiteit Utrecht UU-CS-2001-23, 2001.
• 22: M.D. Weiser. Program Slicing. IEEE Transactions on Software Engineering, 10(4):352--357, 1984.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

General Terms:
Languages, Theory

Keywords:
lazy functional logic programming, redex trails, slicing