Wisconsin Program-Slicing Project

Table of Contents

Disclaimer

 This web page contains links to PostScript and PDF files of articles that may be covered by copyright. You may browse the articles at your convenience (in the same spirit that you read a journal article or an article from a conference proceedings in a public library). Retrieving, copying, or distributing these files may violate copyright law.

Please note that the definitive versions of these papers are the published versions. The PostScript versions are provided here as a courtesy, and, in some cases, there may be differences between the PostScript provided here and the published version. We believe that all of the differences are either formatting differences or copy-editing changes. If you cite these papers, please cite the published version rather than giving a URL.

[Back to the Table of Contents]

Research Summary

 The goal of this project is to create enhanced tools to support the development of complex software systems. The objective is to create tools that provide powerful language-specific program-manipulation operations. In particular, the project has explored how program slicing can serve as the basis for such program-manipulation operations.

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 to program understanding, maintenance, debugging, testing, differencing, specialization, reuse, and merging.

The activities of the project have been devoted to:

More recently, we found some unexpected connections between interprocedural dataflow analysis and our previous work on interprocedural program slicing. In particular, we have shown how a large class of interprocedural dataflow-analysis problems can be solved by transforming them into a special kind of graph-reachability problem. This graph-reachability problem can be solved precisely in polynomial time by the algorithm originally developed for interprocedural slicing.

[Back to the Table of Contents]

Recent Items of Note*new*

Recent Publications

[Back to the Table of Contents]

Miscellaneous

  1. Tips on writing a research paper (video recording from PLMW@PLDI21)

  2. Some notes on automatic differentiation and back-propagation (PDF)

  3. A recording of a lecture about "retrograde debugging" is available here. The password is Rptp6tSh. The lecture is based on several "retrograde chess puzzles" from the Raymond Smullyan book "The Chess Mysteries of Sherlock Holmes. Smullyan also wrote a second book of such problems, titled "The Chess Mysteries of the Arabian Knights. In the lecture, the chess problems start at 9:56, 33:39, and 45:40, with a fourth one toward the end. (The accompanying text was auto-generated by Webex, and is pretty funny: "chess problems" became "just problems" or "chest problems," etc. Not sure how to turn it off though.) I recommend watching at 1.25x speed though (or even faster) because I talked quite slowly that day.

  4. Material from CAV 2021 tutorial ``Introduction to Algebraic Program Analysis'' (Z. Kincaid and T. Reps):

  5. Reps interview for People of Programming Languages (2018)

  6. The Reps At Sixty Workshop was held in Edinburgh, UK on September 11, 2016.

  7. Information about the life of Susan Horwitz (1955-2014) can be found here.

  8. Raghavan Komondoor has made available the software for detecting clones in C code that he developed as part of his Ph.D. dissertation.

  9. The paper was selected for inclusion in a special SIGPLAN collection of the 50 most influential papers from the SIGPLAN Conference on Programming Language Design and Implementation from 1979 to 1999:

    A retrospective on the paper was published as

    An extended version of the PLDI 88 paper later appeared as the following journal paper:

[Back to the Table of Contents]

Personnel

Faculty

[Back to the Table of Contents]

Edited Books

[Back to the Table of Contents]

Conference and Refereed Workshop Publications

  • Reps, T., Marceau, C., and Teitelbaum, T., Remote attribute updating for language-based editors. In Conference Record of the Thirteenth ACM Symposium on Principles of Programming Languages, (St. Petersburg, FL, January 13-15, 1986), ACM, New York, NY, 1986, pp. 1-13. [ACM Author-Izer Link.]

  • Reps, T. and Teitelbaum, T., The Synthesizer Generator. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, (Pittsburgh, PA, April 23-25, 1984), ACM SIGPLAN Notices 19, 5 (May 1984), pp. 42-48. (Awarded an ACM SIGSOFT Retrospective Impact Paper Award 2010.) [abstract; paper; ACM Author-Izer Link.]

  • Reps, T. and Alpern, B., Interactive proof checking. In Conference Record of the Eleventh ACM Symposium on Principles of Programming Languages, (Salt Lake City, Utah, January 15-18, 1984), ACM, New York, NY, 1984, pp. 36-45. [abstract; ACM Author-Izer Link.]

  • Reps, T., Static-semantic analysis in language-based editors. In Digest of Papers of the IEEE Spring CompCon 83, (San Francisco, CA, March 1-3, 1983), IEEE Computer Society, Washington, DC, 1983, pp. 411-414.

  • Reps, T., Optimal-time incremental semantic analysis for syntax-directed editors. In Conference Record of the Ninth ACM Symposium on Principles of Programming Languages, (Albuquerque, NM, January 25-27, 1982), ACM, New York, NY, 1982, pp. 169-176. [abstract; ACM Author-Izer Link.]

  • Teitelbaum, T., Reps, T., and Horwitz, S., The why and wherefore of the Cornell Program Synthesizer. In Proceedings of the ACM SIGPLAN/SIGOA Symposium on Text Manipulation, (Portland, OR, June 8-10, 1981), ACM SIGPLAN Notices 16, 6 (June 1981), pp. 8-16. [ACM Author-Izer Link.]

  • Demers, A., Reps, T., and Teitelbaum, T., Incremental evaluation for attribute grammars with application to syntax-directed editors. In Conference Record of the Eighth ACM Symposium on Principles of Programming Languages, (Williamsburg, VA, January 26-28, 1981), ACM, New York, NY, 1981, pp. 105-116. [abstract; ACM Author-Izer Link.]

    [Back to the Table of Contents]

    Tutorials

    [Back to the top]

    Patents

    [Back to the Table of Contents]

    Pending Submissions

    [Back to the Table of Contents]

    Ph.D. Dissertations

    [Back to the Table of Contents]

    Magazine Articles

    [Back to the Table of Contents]

    Other Publications and Reports

    [Back to the Table of Contents]

    Software

    [Back to the Table of Contents]