Slicing; I/O and the Implicit State

Sebastian Danicic
School of Computing, University of North London, UK

Yoga Sivagurunathan
School of Computing, University of North London, UK

Mark Harman
School of Computing, University of North London, UK

Ladda ner artikelhttp://www.ep.liu.se/ecp_article/index.en.aspx?issue=001;article=006

Ingår i: Proceedings of the 3rd International Workshop on Automatic Debugging; 1997 (AADEBUG-97)

Linköping Electronic Conference Proceedings 1:6, s. 59-67

Linköping Electronic Articles in Computer and Information Science 009:6, s. 59-67

Visa mer +

Publicerad: 1997-09-10


ISSN: 1650-3686 (tryckt), 1650-3740 (online)


Program slicing consists of deleting statements from a program; creating a reduced program; a slice; that preserves the original programs behaviour for a given set of variables at a chosen point in the program. However; some aspects of a programs semantics are not captured by a set of variables; rendering slicing inapplicable to their analysis. These aspects of the programs state shall; collectively; be termed the `implicit state. For example; the input list supplied to a program is not denoted by a variable; rather it is part of the implicit state. It will be shown that this implicitness causes existing slicing algorithms to produce incorrect slices with respect to input. In order to solve the problem the program to be sliced will be transformed into an `explicit version (in which all aspects of its semantics are captured by variables). The approach is also applied to a wider class of problems in which slicing is inhibited by the lack of variables upon which to form a suitable slicing criterion. Because the approach can be expressed as a source-level transformation; it has the attractive property that the slicing algorithm need not be altered.


Slicing; Real--Time Systems; Implicit State; I/O


[1] Hiralal Agrawal and Joseph R. Horgan. Dynamic program slicing. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 246-256 New York, June 1980.

[2] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, techniques and tools. Addison Wesley 1986

[3] G. Canfora, A. Cimitile, Andrea De Lucia, and G. A. Di Lucca. Software salvaging based on conditions. In International Conference on Software Maintenance (ICSM’96), pages 424-433, Victoria, Canada, September1994. IEEE.

[4] Sebastian Danicic, Mark Harman, and Yogasundary Sivagurunathan. A parallel algorithm for static program slicing. Information Processing Letters, 56(6):307-314, December 1995.

[5] Andrea. De Lucia, Anna Rita Fasolino, and Malcolm Munro. Understanding function behaviours through program slicing. In th IEEE Workshop on Program Comprehension, Berlin, Germany, March 1996.

[6] Keith B. Gallagher and James R. Lyle. Using program slicing in software maintenance. IEEE Transactions on Software Engineering, 17(8):751-761 August 1991.

[7] Mark Harman. Functional Models of Procedural Programs. PhD thesis, University of North London, 1991.

[8] Mark Harman and Sebastian Danicic. Using program slicing to simplify testing. Journal of Software Testing, Verification and Reliability, 5:143-162, September 1995.

[9] Mark Harman and Sebastian Danicic. Amorphous program slicing. In Anneliese von Mayrhauser, Gerardo Canfora, and Arun Lakhotia, editors,5th IEEE Internation Workshop on Program Comprehesion (IWPC’91), Dearborn, Michigan, USA, May 1997.

[10] Mark Harman, Dan Simpson, and Sebastian Danicic. Slicing programs in the presence of errors. Formal Aspects of Computing, 8:490-497, 1996.

[11] Susan Horwitz, Jan Prins, and Thomas Reps. Integrating non interfering versions of programs. ACM Transactions on Programming Languages and Systems, 11(3):345-387, July 1989.

[12] Susan Horwitz, Thomas Reps, and David Binkley. Interprocedural slicing using dependence graphs. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 25-46, Atlanta, Georgia, June 1988 Proceedings in SIGPLAN Notices, 23(7), pp.35-46, 1988.

[13] Mariam Kamkar. Interprocedural dynamic slicing with applications to debugging and testing. PhD Thesis, De partment of Computer Science and Information Science, Linköping University, Sweden, 1993. Available as Linköping Studies in Science and Technology, Dissertations, Number 297.

[14] Bogdan Korel and Janusz Laski. Dynamic programslicing. Information Processing Letters, 29(3): 155-163, October 1988.

[15] Arun Lakhotia. Rule based approach to computing module cohesion. In Proceedings of the 15th Conference on Software Engineering. (ICSE-15), pages 34-44.

[16] James R. Lyle, Dolores R. Wallace, James R. Graham, Keith B. Gallagher, Joseph P. Poole, and David W. Binkley. Unravel project.

[17] Linda M. Ott and J. J. Thuss. The relationship between slices and module cohesion. In Proceedings of the th ACM conference on Software Engineering, pages 198-204, May 1989.

[18] D. A. Schmidt. Denotational semantics, A Methodology for Language Development. Allyn and Bacon, 1986.

[19] Joseph E. Stoy. Denotational semantics, The Scott Strachey approach to programming language theory. MIT Press, 1985. Third edition.

[20] Guda A. Venkatesh. The semantic approach to program slicing. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 26-28, Toronto, Canada, June 1991. Proceedings in SIGPLAN Notices, 26(6), pp. 107-119,1991.

[21] Mark Weiser. Program slices, Formal, psychological, and practical investigations of an automatic program abstraction method. PhD thesis, University of Michigan, Ann Arbor, MI, 1979.

[22] Mark Weiser. Program slicing. IEEE Transactions on Software Engineering, 10(4):253-157, 1984.

Citeringar i Crossref