The semantics of program slicing and program integration

Thomas Reps, Wuu Yang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

31 Scopus citations

Abstract

A slice of a program with respect to a program point p and variable x consists of all statements of the program that might affect the value of x at point p. Slices can be extracted particularly easily from a program representation called a program dependence graph, originally introduced as an intermediate program representation for performing optimizing, vectorizing, and parallelizing transformations. Such slices are of a slightly restricted form: rather than permitting a program to be sliced with respect to program point p and an arbitrary variable, a slice must be taken with respect to a variable that is defined at or used at p. This paper concerns the relationship between the execution behavior of a program and the execution behavior of its slices. Our main results about slicing are those stated as the Slicing Theorem and the Termination Theorem. The Slicing Theorem demonstrates that a slice captures a portion of a program's behavior in the sense that, for any initial state on which the program halts, the program and the slice compute the same sequence of values for each element of the slice. The Termination Theorem demonstrates that if a program is decomposed into (two or more) slices, the program halts on any state for which all the slices halt. These results are then used to provide semantic justification for a program-integration algorithm of Horwitz, Prins, and Reps.

Original languageEnglish
Title of host publicationTAPSOFT 1989
Subtitle of host publicationProceedings of the International Joint Conference on Theory and Practice of Software Development - Advanced Seminar on Foundations of Innovative Software Development II and Colloquium on Current Issues in Programming Languages, CCIPL
EditorsJosep Diaz, Fernando Orejas
PublisherSpringer Verlag
Pages360-374
Number of pages15
ISBN (Print)9783540509400
DOIs
StatePublished - 1 Jan 1989
Event3rd International Joint Conference on Theory and Practice of Software Development, TAPSOFT 1989 - Barcelona, Spain
Duration: 13 Mar 198917 Mar 1989

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume352 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Joint Conference on Theory and Practice of Software Development, TAPSOFT 1989
CountrySpain
CityBarcelona
Period13/03/8917/03/89

Fingerprint Dive into the research topics of 'The semantics of program slicing and program integration'. Together they form a unique fingerprint.

Cite this