This paper made two main contributions: it defined system dependence graphs (SDGs), which extended program dependence graphs (PDGs) [31, 17] to incorporate collections of procedures (with procedure calls) rather than just monolithic programs. It then defined an interprocedural slicing algorithm that identifies the components of the SDG that might affect the values of the variables defined at or used at a given program point Ô, and/or how often Ô executes. The novelty of the algorithm was that it correctly accounts for the calling context of a called procedure, thereby improving on the technique for interprocedural slicing algorithm that had been presented in Mark Weiser's seminal papers on program slicing [47, 48] . The paper's results form part of David Binkley's Ph.D. thesis [6] , and a journal version of the paper was published in TOPLAS [20] . SDGs are covered by a U.S. patent [40] ; algorithms for forward and backward slicing were part of the original patent application that was submitted, but the Wisconsin Alumni Research Foundation decided that enough money had been spent by the time the patent office was convinced that Claim 1 (SDGs) was patentable. The data structures and slicing algorithms described in the paper are used in one commercial product, CodeSurfer R , a tool for code understanding and inspection that supports browsing and slicing of dependence graphs. CodeSurfer is available from GrammaTech, Inc. (see http://www.grammatech.com/products/codesurfer/). (The slicing algorithm used in CodeSurfer is actually based on the improved method described in [23] .) The PLDI 88 paper was careful to state what slicing problem it did not solve, i.e., that of producing a slice that is an executable projection of the original program. The reason has to do with multiple calls to the same procedure: in general, a slice may include more than one such call, and at each, a different subset of the procedure's parameters may be in the slice. An extended slicing algorithm that addresses this parameter-mismatch problem was later given by Binkley [7] . The PLDI 88 paper was couched in terms of a very simple programming language. However, one can think of SDGs as a class of program representations: to represent programs in different programming languages, one uses different variants of PDGs containing nodes and edges that capture the features and constructs of the language. The issue of how to create appropriate PDGs/SDGs is really orthogonal to the issue of how to slice them. There has been considerable work on how to build dependence graphs for the features and constructs found in real-world programming languages, Design and Implementation (1979-1999)  Years of the ACM/SIGPLAN Conference on Programming Language Nowadays the interprocedural-slicing method of the PLDI 88 paper would be termed a "context-sensitive" interprocedural-slicing method. In general, a context-sensitive analysis is one in which the analysis of a called procedure is "sensitive" to the context in which it is called. A context-sensitive analysis captures the fact that calls to a procedure through different call sites can have different effects on the program's execution state. General frameworks for context-sensitive program analysis already existed in 1988 [13, 45] , although we were not aware of them at the time. Our work was more influenced by Kastens's algorithm for building a collection of cooperating finite-state machines for evaluating derivation trees of attribute grammars [24] (see below). The two other papers in the session at PLDI 88 in which our paper was presented [8, 12] actually foreshadowed a major direction that our work was to take subsequently: Callahan presented a context-sensitive algorithm for a certain kind of dataflow-analysis problem [8]; Cooper and Kennedy presented a graph-reachability algorithm for finding procedures' MayMod and MayUse sets (which summarize possible side-effects of procedure calls on global variables) [12] . Later work by Horwitz, Reps, and collaborators showed how many dataflow-analysis problems similar to the one that Callahan addressed could be turned into graphreachability problems in a fashion similar to the technique used in the Cooper-Kennedy paper-and then solved using algorithms very similar to the Horwitz-Reps-Binkley interprocedural-slicing algorithm. However, even though the three papers were presented in the same hour and a half session at PLDI 88, the act of combining their techniques did not occur for another six years. The PLDI 88 paper pointed out a correspondence between the call structure of a program and a context-free grammar, and between the intraprocedural transitive dependences among a PDG's parameter nodes and the dependences among attributes in an attribute grammar [25] . Our paper exploited this correspondence to compute summary edges that were added to the SDG at call sites to capture certain transitive dependences. The transitive dependences of interest are very much like the transitive dependences captured by the characteristic graphs of an attribute grammar's nonterminals; the algorithm for identifying summary edges was inspired by the first two passes of the algorithm for creating the "TDS graphs" that are used to define the class of ordered attribute grammars [24] . This ACM SIGPLAN 229 Best of PLDI 1979
Horwitz et al. REF extended the technique to interprocedural slicing.
Interprocedural slicing using dependence graphs
SIGP
Computer Science