Lightweight program specialization via dynamic slicing

ABSTRACT

Program 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. Thus, dynamic slicers are usually easier to design and implement.In this work, we present a program specialization technique for lazy functional logic programming which is based on dynamic slicing. Our method exploits the code size reduction capabilities of slicing in order to produce a version of the original program specialized w.r.t. a given criterion. We also introduce some simple, post-processing transformations that allow us to further simplify the specialized program. The kind of specialization performed by our approach cannot be achieved with other related techniques like partial evaluation.

References

1. E. Albert, M. Hanus, F. Huch, J. Oliver, and G. Vidal. Operational Semantics for Declarative Multi-Paradigm Languages. Journal of Symbolic Computation, 2004. To appear.]]
2. S.K. Biswas. Dynamic Slicing in Higher-Order Programming Languages. PhD thesis, Department of CIS, University of Pennsylvania, 1997.]]
3. B. Braβel, M. Hanus, F. Huch, and G. Vidal. A Semantics for Tracing Declarative Multi-Paradigm Programs. In Proc. of PPDP'04, pages 179--190. ACM Press, 2004.]]
4. J. Ferrante, K.J. Ottenstein, and J.D. Warren. The Program Dependence Graph and Its Use in Optimization. ACM TOPLAS, 9(3):319--349, 1987.]]
5. V. Gouranton. Deriving Analysers by Folding/Unfolding of Natural Semantics and a Case Study: Slicing. In Proc. of SAS'98, pages 115--133, 1998.]]
6. M. Hanus. A Unified Computation Model for Functional and Logic Programming. In Proc. of POPL'97, pages 80--93. ACM, 1997.]]
7. M. Hanus and C. Prehofer. Higher-Order Narrowing with Definitional Trees. Journal of Functional Programming, 9(1):33--75, 1999.]]
8. M. Hanus(ed.). Curry: An Integrated Functional Logic Language. Available at: http://www.informatik.uni-kiel.de/~curry/+.]]
9. M. Harman and R.M. Hierons. An Overview of Program Slicing. Software Focus, 2(3):85--92, 2001.]]
10. T. Hoffner, M. Kamkar, and P. Fritzson. Evaluation of Program Slicing Tools. In Proc. of AADEBUG'95, pages 51--69. IRISA-CNRS, 1995.]]
11. D.J. Kuck, R.H. Kuhn, D.A. Padua, B. Leasure, and M. Wolfe. Dependence Graphs and Compiler Optimization. In Proc. of POPL'81, pages 207--218. ACM, 1981.]]
12. J. Launchbury. A Natural Semantics for Lazy Evaluation. In Proc. of POPL'93, pages 144--154. ACM Press, 1993.]]
13. M. Leuschel and M.H. Sørensen. Redundant Argument Filtering of Logic Programs. In Proc. of LOPSTR'96, pages 83--103. LNCS 1207 83--103, 1996.]]
14. F. López-Fraguas and J. Sánchez-Hernández. TOY: A Multiparadigm Declarative System. In Proc. of the 10th Int'l Conf. on Rewriting Techniques and Applications (RTA'99), pages 244--247. Springer LNCS 1631, 1999.]]
15. C. Ochoa, J. Silva, and G. Vidal. Dynamic Slicing Based on Redex Trails. In Proc. of PEPM'04, pages 123--134. ACM Press, 2004.]]
16. T. Reps and T. Turnidge. Program Specialization via Program Slicing. In O. Danvy, R. Glück, and P. Thiemann, editors, Partial Evaluation. Dagstuhl Castle, Germany, February 1996, pages 409--429. Springer LNCS 1110, 1996.]]
17. S. Schoenig and M. Ducasse. A Backward Slicing Algorithm for Prolog. In Proc. of SAS'96, pages 317--331. Springer LNCS 1145, 1996.]]
18. G. Szilagyi, T. Gyimothy, and J. Maluszynski. Static and Dynamic Slicing of Constraint Logic Programs. J. Automated Software Engineering, 9(1):41--65, 2002.]]
19. F. Tip. A Survey of Program Slicing Techniques. Journal of Programming Languages, 3:121--189, 1995.]]
20. G.A. Venkatesh. Experimental Results from Dynamic Slicing of C Programs. ACM Transactions on Programming Languages and Systems, 17(2):197--217, 1995.]]
21. G. Vidal. Forward Slicing of Multi-Paradigm Declarative Programs Based on Partial Evaluation. In Proc. of LOPSTR 2002, pages 219--237. Springer LNCS 2664, 2003.]]
22. M.D. Weiser. Program Slices: Formal, Psychological, and Practical Investigations of an Automatic Program Abstraction Method. PhD thesis, The University of Michigan, 1979.]]

Index Terms

• Theory of computation

  • Semantics and reasoning

    • Program semantics

      • Operational semantics