Thomas Reps
Thomas Reps Professor and Vilas AssociatePh.D., Cornell University, 1982
Computer Sciences Department
University of Wisconsin
1210 W. Dayton St.
Madison, WI 53706-1685
telephone: (608) 262-1204
fax: (608) 262-9777
email: reps@cs.wisc.edu
http://www.cs.wisc.edu/~reps/
The slice of a program with respect to a set of program elements $S$ is a projection of the program that includes only program elements that might affect (either directly or transitively) the values of the variables used at members of $S$. Slicing allows one to find semantically meaningful decompositions of programs, where the decompositions consist of elements that are not textually contiguous. Program slicing is a fundamental operation that can aid in solving many software-engineering problems. For instance, it has applications in program understanding, maintenance, debugging, testing, differencing, specialization, reuse, and merging.
Recently, I was asked by the Defense Advanced Research Projects Agency (DARPA) to advise them about what they should do with regard to the Year 2000 Problem (the use, in many computer programs, of only two-digit fields to record year values in date-valued data). The question they asked me was whether there were `any techniques in the research community that could be applied to the Year 2000 Problem and have impact beyond present commercial products and services'. The most exciting of the ideas that turned up concerns a method for using path profiling as a heuristic to locate some of the sites in a program where there are problematic date manipulations. It works as follows: In path profiling, a program is instrumented so that the number of times each different loop-free path executes is accumulated during an execution run. With such an instrumented program, each run (or set of runs) of the program generates a path spectrum for the execution --- a distribution of the paths that were executed. Path spectra can be used to identify paths in a program that are good candidates for being date-dependent computations by finding differences between path spectra from execution runs on pre-year-2000 data and post-year-2000 data. By choosing input datasets to hold all factors constant except the way dates are used in the program, any differences in the spectra obtained from different execution runs can be attributed to date-dependent computations in the program. Differences in the spectra reveal paths along which the program performed a new sort of computation during the post-year-2000 run, as well as paths --- and hence computations --- that were no longer executed during the post-year-2000 run.
I have also been doing research on analyzing programs to determine information about the way pointer variables and heap-allocated storage are used. This information is useful in optimizing compilers as well as in tools for aiding software understanding.
Interconvertibility of a class of set constraints and context-free language reachability (with D. Melski), to appear in Theoretical Computer Science.
Parametric shape analysis via 3-valued logic (with M. Sagiv and R. Wilhelm), in Twenty-Sixth Symposium on Principles of Programming Languages, to appear, San Antonio, TX, ACM, New York, NY, 1999. (Expanded version)