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.
- 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.]]Google Scholar
- S.K. Biswas. A Demand-Driven Set-Based Analysis. In Proc. of ACM Symp. on Principles of Programming Languages, pages 372--385. ACM Press, 1997.]] Google ScholarDigital Library
- S.K. Biswas. Dynamic Slicing in Higher-Order Programming Languages. PhD thesis, Department of CIS, University of Pennsylvania, 1997.]] Google ScholarDigital Library
- B. Braßel, M. Hanus, F. Huch, and G. Vidal. A Semantics for Tracing Declarative Multi-Paradigm Programs. In Proc. of the 6th Int'l Conf. on Principles and Practice of Declarative Programming (PPDP'04). ACM Press, 2004. To appear.]] Google ScholarDigital Library
- J. Ferrante, K.J. Ottenstein, and J.D. Warren. The Program Dependence Graph and Its Use in Optimization. ACM Transactions on Programming Languages and Systems, 9(3):319--349, 1987.]] Google ScholarDigital Library
- A. Gill. Debugging Haskell by Observing Intermediate Data Structures. In Proc. of the 4th Haskell Workshop. Technical report, University of Nottingham, 2000.]]Google Scholar
- T. Hallgren. Haskell Tools from the Programatica Project. In Proc. of the ACM Workshop on Haskell (Haskell'03), pages 103--106. ACM Press, 2003.]] Google ScholarDigital Library
- M. Hanus. A Unified Computation Model for Functional and Logic Programming. In Proc. of the 24th ACM Symp. on Principles of Programming Languages (POPL'97), pages 80--93. ACM, 1997.]] Google ScholarDigital Library
- M. Hanus and C. Prehofer. Higher-Order Narrowing with Definitional Trees. Journal of Functional Programming, 9(1):33--75, 1999.]] Google ScholarDigital Library
- M. Hanus (ed.). Curry: An Integrated Functional Logic Language. Available at: http://www.informatik.uni-kiel.de/~curry/+.]]Google Scholar
- B. Korel and J. Laski. Dynamic Program Slicing. Information Processing Letters, 29(3):155--163, 1988.]] Google ScholarDigital Library
- Y.A. Liu and S.D. Stoller. Eliminating Dead Code on Recursive Data. Science of Computer Programming, 47:221--242, 2003.]] Google ScholarDigital Library
- F. López-Fraguas and J. Sánchez-Hernández. TOY: A Multiparadigm Declarative System. In Proc. of Int'l Conf. on Rewriting Techniques and Applications (RTA'99), pages 244--247. Springer LNCS 1631, 1999.]] Google ScholarDigital Library
- H. Nilsson and J. Sparud. The Evaluation Dependence Tree as a Basis for Lazy Functional Debugging. Automated Software Engineering, 4(2):121--150, 1997.]] Google ScholarDigital Library
- S. Peyton~Jones, editor. Haskell 98 Language and Libraries: The Revised Report. CUP, 2003.]]Google Scholar
- B. Pope and L. Naish. A Program Transformation for Debugging Haskell 98. In Proc. of ACSC 2003, volume 16 of Conferences in Research and Practice in Information Technology, pages 227--236. ACS, 2003.]] Google ScholarDigital Library
- T. Reps and T. Turnidge. Program Specialization via Program Slicing. In Partial Evaluation. Dagstuhl Castle, Germany, pages 409--429. Springer LNCS 1110, 1996.]] Google ScholarDigital Library
- J. Sparud and C. Runciman. Tracing Lazy Functional Computations Using Redex Trails. In Proc. of Int'l Symp. on Programming Languages, Implementations, Logics and Programs (PLILP'97), pages 291--308. Springer LNCS 1292, 1997.]] Google ScholarDigital Library
- F. Tip. A Survey of Program Slicing Techniques. Journal of Programming Languages, 3:121--189, 1995.]]Google Scholar
- 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.]] Google ScholarDigital Library
- 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.]]Google Scholar
- M.D. Weiser. Program Slicing. IEEE Transactions on Software Engineering, 10(4):352--357, 1984.]]Google ScholarDigital Library
Index Terms
- Dynamic slicing based on redex trails
Recommendations
Dynamic slicing of lazy functional programs based on redex trails
Tracing computations is a widely used methodology for program debugging. Lazy languages, however, pose new demands on tracing techniques because following the actual trace of a computation is generally useless. Typically, tracers for lazy languages ...
Lightweight program specialization via dynamic slicing
WCFLP '05: Proceedings of the 2005 ACM SIGPLAN workshop on Curry and functional logic programmingProgram slicing is a well-known technique that extracts from a program those statements which are relevant to a particular criterion. While static slicing does not consider any input data, dynamic slices are computed from a particular program execution. ...
Static and Dynamic Slicing of Constraint Logic Programs
Slicing is a program analysis technique originally developed for imperative languages. It facilitates understanding of data flow and debugging.
This paper discusses slicing of Constraint Logic Programs. Constraint Logic Programming (CLP) is an emerging ...
Comments