【正文】 gram metrics, human factors, dataflow analysisIntroductionA large puter program is more easily constructed, understood, and maintained when broken into smaller pieces. Several different methods depose programs during program design, such as information hiding (Parnas 1972), data abstraction (Liskov and Zilles 1975), and HIPO (Stay 1976). These methods are not mutally exclusive, but rather plement one another. Proposed here is another plementary method of program deposition: program slicing. Unlike most other methods (but see Tarjan and Valdes, 1980), slicing is applied to programs after they are written, and is therefore useful in maintenance rather than design. Unlike design methodologies, working on actual program text allows slicing to be specified precisely and performed automatically.Slicing starts with the observation that these are times when only a portion of a program39。s behavior is of interest. For instance, during debugging a subset of Dehavior is being corrected, and in program modification or maintenance a sub set of behavior is being improved or replaced. In these cases, a programmer starts from the program behavior and proceeds to find and modify the corresponding portions of program code. Code not having to do with behavior of interest is ignored. Gould and Dronkowski k19/4) report programmers behaving this way during debugging, and a further confirming experiment is presented below.*This research was supported in part by the Computer Science Center at the University of Maryland, and by grants from the Air Force Office of Scientific Research and the General Research Board at the University of Maryland.A programmer maintaining a large, unfamiliar program would almost have to use this behaviorfirst approach to the code. Understanding an en tire system to change only a small piece would take too much time. Since most program maintenance is done by persons other than the program designers, and since 67 percent of programming effort goes into maintenance (Zelkowitz, Shaw, and annon 1979), deposing programs by behavior must be a mon occurence.Automatic slicing requires that behavior be speclfied in a certain form. If the behavior of interest can be expressed as the values of some sets of variables at some set of statements, then this specification is said to be a slicing criterion. Dataflow analysis (Hecht 1977) can find all the program code which might have influenced the specified behavior, and this code is called a slice of the program. A slice is itself an executable program, whose behavior must be identical to the specified subset of the original program39。s behavior.Figure 1 gives examples of some slicing criteria and their corresponding slices.There are usually many different slices for a given program and slicing criterion, depending on how minimal a slice is desired. The issue of minimality is discussed further below. There is always at least one slice the program itself. The interesting slices are the ones which, pared to the original program, are significantly smaller and simpler.The idea of isolating portions of programs according to their behavior has appeared previously. Schwartz (1971) hints at such a possibility for a debugging system. Browne and Johnson (1978) describe a questionanswerer for Fortran programs.Examples of SlicesThe ori ginal program:1 BEGIN2 READ(X,Y)3 TUTAL:=4 SUM:=5 IF X=16 THEN SUM:=Y7 ELSE BEGIN8 READ(Z)9 TOTAL:=X*Y10 END11 WRITE (TOTAL,SUM)12 ENDSlice on the value of Z at statement 12. BEGIN READ(X,Y) IF X1 THEN ELSE READ(Z) ENDSlice on the value of X at statement 9. BEGIN READ(X,Y) ENDSlice on the value of TOTAL at statement 12. BEGIN READ(X,Y) TOTAL:=0 IF X=1 THEN ELSE TOTAL:=X*Y ENDFigure 1which, through a succession of questions, could bemade to reveal the slices of a program although very slowly. Several online debuggers permit a limited traceback of the location of variable references (. Aygun, 1973), and this information is a kind of dynamic slice.Slicing is a source code transformation of a program. Previous work in program transformation has concentrated on preserving program correctnesswhile improving some desirable property of programs. For instance, Baker (1977) and Ashcroft and Manna (1973) both are concerned with adding good structure to programs. Wegbreit (1976), Arsac (1979), Gerhart (1975), and Loveman (1977), are more oriented to improving a program39。s performance.Slicing AlgorithmsThis section more formally discusses the ideas of a slicing criterion and a slicing algorithm, using the reader39。s intuitive understanding of machine execution. All proofs have been carried out in an abstract operational model (Weiser 1979). This paper considers the slicing of blockstructured, possibly recursive programs written in a Pascallike language. All variables are assumed to be uniquely named, and all procedures are assumed to be singleentry, single exit.The following notation is used throughout this paper. Due to typesetting limitations, square brackets ([...]) are used to enclose superscripted and subscripted quantities. Set notation is expressed as follows. Let A and B denote sets, let f and g be functions whose values are sets, and let C(i) be a finite family of sets indexed by i. Then:A union B denotes the set union of A and B.A intersect B denctes the set intersection of A and B.f union g denotes the function whose value is f(n) union g(n) for each n in the domain of f and g, and is undefined elsewhere.UNION C(i) denotes the union of all C(i) for each i.A slicing_ criterion for a program specifies a window for observing its behavior. A window is specified as a statement and a set of variables. The window allo