Parametric program slicing

ABSTRACT

Program slicing is a technique for isolating computational threads in programs. In this paper, we show how to mechanically extract a family of practical algorithms for computing slices directly from semantic specifications. These algorithms are based on combining the notion of dynamic dependence tracking in term rewriting systems with a program representation whose behavior is defined via an equational logic. Our approach is distinguished by the fact that changes to the behavior of the slicing algorithm can be accomplished through simple changes in rewriting rules that define the semantics of the program representation. Thus, e.g., different notions of dependence may be specified, properties of language-specific datatypes can be exploited, and various time, space, and precision tradeoffs may be made. This flexibility enables us to generalize the traditional notions of static and dynamic slices to that of a constrained slice, where any subset of the inputs of a program may be supplied.

REFERENCES

• 1: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, ACM SIGPLAN Notices, v.25 n.6, p.246-256, Jun. 1990
• 2: BALL, T. Personal communication.
• 3: Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.257-271, June 1990, White Plains, New York, United States
• 4: H P Barendregt , M C J D Eekelen , J R W Glauert , J R Kennaway , M J Plasmeijer , M R Sleep, Term graph rewriting, Volume II: Parallel Languages on PARLE: Parallel Architectures and Languages Europe, p.141-158, March 1987, Eindhoven, The Netherlands
• 5: E. Cartwright , M. Felleisen, The semantics of program dependence, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.13-27, June 19-23, 1989, Portland, Oregon, United States
• 6: Jong-Deok Choi , Barton P. Miller , Robert H. B. Netzer, Techniques for debugging parallel programs with flowback analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.491-530, Oct. 1991 [doi>10.1145/115372.115324]
• 7: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 8: DUESTERWALD, E., GUPTA, R., AND SOFFA, M. Rigorous data flow testing through output influences. In Proceedings of the Second Irvine Software Symposium ISS'92 (Cahfornia, 1992), pp. 131-145.
• 9: ERNST, M. Practical fine-grained static slicing of optimized code. Tech. Rep. MSR-TR-94-14, Microsoft Research, Redmond, WA, 1994.
• 10: 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]
• 11: John Field, On laziness and optimality in lambda interpreters: tools for specification and analysis, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, December 1989, San Francisco, California, United States [doi>10.1145/96709.96710]
• 12: FIELD, J. A simple rewriting semantics for realistic imperative programs and its application to program analysis. In Proc. ACM SIGPLAN Workshop on Partial Evaluatton and Semantics-Based Program ManipuIanon (San Francisco. June 1992), pp 98-107 Published as Yale University Technical Report YALEU/DCS/RR-909.
• 13: FIELD, J., AND TIP, E Dynamic dependence in term rewnting systems and its application to program slicing. Tech. Rep. RC 19?q?, IBM T.J. Watson Research Center, November t994. (Corrected and expanded version of {14}).
• 14: John Field , Frank Tip, Dynamic Dependence in Term rewriting Systems and its Application to Program Slicing, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.415-431, September 14-16, 1994
• 15: Keith Brian Gallagher , James R. Lyle, Using Program Slicing in Software Maintenance, IEEE Transactions on Software Engineering, v.17 n.8, p.751-761, August 1991 [doi>10.1109/32.83912]
• 16: Susan Horwitz , Jan Prins , Thomas Reps, Integrating noninterfering versions of programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.345-387, July 1989 [doi>10.1145/65979.65980]
• 17: G. Kahn, Natural semantics, 4th Annual Symposium on Theoretical Aspects of Computer Sciences on STACS 87, p.22-39, February 1987, Passau, Germany
• 18: Mariam Kamkar , Peter Fritzson , Nahid Shahmehri, Three approaches to interprocedural dynamic slicing, Microprocessing and Microprogramming, v.38 n.1-5, p.625-636, Sept. 1993
• 19: P. Klint, A meta-environment for generating programming environments, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.2, p.176-201, April 1993 [doi>10.1145/151257.151260]
• 20: J. W. Klop, Term rewriting systems, Handbook of logic in computer science (vol. 2): background: computational structures, Oxford University Press, Inc., New York, NY, 1993
• 21: Bogdan Korel , Janusz Laski, Dynamic slicing of computer programs, Journal of Systems and Software, v.13 n.3, p.187-195, Nov. 1990 [doi>10.1016/0164-1212(90)90094-3]
• 22: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, ACM SIGPLAN Notices, v.27 n.7, p.235-248, July 1992
• 23: LARUS, J., AND CI-IANDRA, S. Using tracing and dynamic slicing to tune compilers. Computer Science Technical Report 1174, University of Wisconsin-Madison, 1993.
• 24: Jim Q. Ning , Andre Engberts , W. Voytek Kozaczynski, Automated support for legacy code understanding, Communications of the ACM, v.37 n.5, p.50-57, May 1994 [doi>10.1145/175290.175295]
• 25: Hsin Pan, Software debugging with dynamic instrumentation and test-based knowledge, Purdue University, West Lafayette, IN, 1993
• 26: A. Podgurski , L. A. Clarke, A Formal Model of Program Dependences and its Implications for Software Testing, Debugging, and Maintenance, IEEE Transactions on Software Engineering, v.16 n.9, p.965-979, September 1990 [doi>10.1109/32.58784]
• 27: Frank Tip, Generic techniques for source-level debugging and dynamic program slicing, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1994
• 28: Frank Tip, A Survey of Program Slicing Techniques., CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1994
• 29: TIP, F. Generation of Program Analysts Tools. PhD thesis, University of Amsterdam, 1995. Forthcoming.
• 30: G. A. Venkatesh, The semantic approach to program slicing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.107-119, June 24-28, 1991, Toronto, Ontario, Canada
• 31: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
• 32: WEISER, M. Reconstructing sequential behavior from parallel behavior projections. Information Processmg Letters 17, 3 (1983), I29-135.
• 33: WEISER, M. Program shcing. IEEE Transactions on Software Engineering 10, 4 (1984), 352-357.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Program and recursion schemes

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Specification techniques
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Languages