The Formal Semantics of Program Slicing for Non-Terminating Computations

Since the original development of program slicing in 1979 [.Weiser slices 1979.] there have been many attempts to define a suitable semantics which will precisely define the meaning of a slice. Particular issues include handling termination and non-termination, slicing non-terminating programs and slicing nondeterministic programs. In this paper we review and critique the main attempts to construct a semantics for slicing and present a new operational semantics which correctly handles slicing for non-terminating and nondeterministic programs. We also present a modified denotational semantics which we prove to be equivalent to the operational semantics. This provides programmers with two different methods to prove the correctness of a slice or a slicing algorithm, and means that the program transformation theory and FermaT transformation system, developed over the last 25 years of research, and which has proved so successful in analysing terminating programs, can now be applied to non-terminating interactive programs.