Prasanna Kumar K.
Amey Karkare
Saswat Padhi
ABSTRACT
An effective static slicing technique for functional programs must have two features. Its handling of function calls must be context sensitive without being inefficient, and, because of the widespread use of algebraic datatypes, it must take into account structure transmitted dependences. It has been shown that any analysis that combines these two characteristics is undecidable, and existing slicing methods drop one or the other. We propose a slicing method that only weakens (and not entirely drop) the requirement of context-sensitivity and that too for some and not all programs.
We then consider applications that require the same program to be sliced with respect to several slicing criteria. We propose an incremental version of our slicing method to handle such situations efficiently. The incremental version consists of a one time pre-computation step that uses the non-incremental version to slice the program with respect to a fixed default slicing criterion and processes the results to a canonical form. Presented with a slicing criterion, a low-cost incremental step uses the results of the pre-computation to obtain the slice.
Our experiments with a prototype incremental slicer confirms the expected benefits---the cost of incremental slicing, even when amortized over only a few slicing criteria, is much lower than the cost of non-incremental slicing.
- David Binkley and Mark Harman. 2004. A survey of empirical results on program slicing. Advances in Computers 62 (2004).Google Scholar
- Sandip Kumar Biswas. 1997.Google Scholar
- Dynamic Slicing in Higher-order Programming Languages. Ph.D. Dissertation. University of Pennsylvania, Philadelphia, PA, USA.Google Scholar
- R. Hindley. 1969. The Principal Type-Scheme of an Object in Combinatory Logic. Trans. Amer. Math. Soc. 146 (1969), 29–60. http://www.jstor.org/stable/1995158Google Scholar
- Prasanna Kumar K. 2019.Google Scholar
- Dependence Analysis of Functional Programs and its Applications. Ph.D. Dissertation. Indian Institute of Technology, Bombay, Mumbai, India.Google Scholar
- Amey Karkare, Uday Khedker, and Amitabha Sanyal. 2007.Google Scholar
- Liveness of Heap Data for Functional Programs. In Heap Analysis and Verification Workshop.Google Scholar
- Yanhong A. Liu and Scott D. Stoller. 2003. Eliminating Dead Code on Recursive Data. Sci. Comput. Program. 47 (2003). Google ScholarDigital Library
- Robin Milner. 1978. A theory of type polymorphism in programming. J. Comput. System Sci. 17, 3 (1978), 348 – 375. 0000(78)90014- 4Google ScholarCross Ref
- Neil Mitchell and Colin Runciman. 2009. Losing Functions Without Gaining Data: Another Look at Defunctionalisation. In Proceedings of the 2nd ACM SIGPLAN Symposium on Haskell. Google ScholarDigital Library
- Mehryar Mohri and Mark-Jan Nederhof. 2000. Regular Approximation of Context-Free Grammars through Transformation. In Robustness in Language and Speech Technology. Kluwer Academic Publishers.Google Scholar
- NoFib. 2019.Google Scholar
- Haskell Benchmark Suite. http://git.haskell.org/nofib.git. (Last accessed).Google Scholar
- Claudio Ochoa, Josep Silva, and Germán Vidal. 2008. Dynamic Slicing of Lazy Functional Programs Based on Redex Trails. Higher Order Symbol. Comput. 21 (2008). Google ScholarDigital Library
- Roly Perera, Umut A. Acar, James Cheney, and Paul Blain Levy. 2012. Functional programs that explain their work. In ACM SIGPLAN International Conference on Functional Programming. Google ScholarDigital Library
- Simon L. Peyton-Jones. 1987.Google Scholar
- The Implementation of Functional Programming Languages. Prentice-Hall.Google Scholar
- Benjamin C. Pierce. 2002.Google Scholar
- Types and Programming Languages (1st ed.). The MIT Press. Google ScholarDigital Library
- Thomas Reps. 2000. Undecidability of Context-sensitive Data-dependence Analysis. ACM Trans. Program. Lang. Syst. (2000). Google ScholarDigital Library
- Thomas W. Reps and Todd Turnidge. 1996. Program Specialization via Program Slicing. In Partial Evaluation, International Seminar, Dagstuhl Castle, Germany. Google ScholarDigital Library
- Nuno F. Rodrigues and Luis S. Barbosa. 2006. Component Identification Through Program Slicing. Electronic Notes in Theoretical Computer Science 160 (2006).Google Scholar
- Nuno F. Rodrigues and Luis S. Barbosa. 2006. Program Slicing by Calculation. Journal of Universal Computer Science (2006).Google Scholar
- Amr Sabry and Matthias Felleisen. 1992.Google Scholar
- Reasoning About Programs in Continuation-passing Style. SIGPLAN Lisp Pointers (1992). Google ScholarDigital Library
- Josep Silva. 2012.Google Scholar
- A Vocabulary of Program Slicing-based Techniques. ACM Comput. Surv. (2012). Google ScholarDigital Library
- Josep Silva, Salvador Tamarit, and César Tomás. 2012.Google Scholar
- System Dependence Graphs in Sequential Erlang. In Proceedings of the 15th International Conference on Fundamental Approaches to Software Engineering (FASE’12). Google ScholarDigital Library
- Frank Tip. 1995. A Survey of Program Slicing Techniques. Journal of Programming Languages 3 (1995).Google Scholar
Index Terms
- A static slicing method for functional programs and its incremental version
Recommendations
A brief survey of program slicing
Program slicing is a technique to extract program parts with respect to some special computation. Since Weiser first proposed the notion of slicing in 1979, hundreds of papers have been presented in this area. Tens of variants of slicing have been ...
Precise slicing of interprocedural concurrent programs
Program slicing is an effective technique for analyzing concurrent programs. However, when a conventional closure-based slicing algorithmfor sequential programs is applied to a concurrent interprocedural program, the slice is usually imprecise owing to ...
Abstract Program Slicing: An Abstract Interpretation-Based Approach to Program Slicing
In the present article, we formally define the notion of abstract program slicing, a general form of program slicing where properties of data are considered instead of their exact value. This approach is applied to a language with numeric and reference ...
Comments