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" lecture 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 POPL 2018 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

Current Post-Docoral Associates, Staff, and Visitors

Students

Former Students, Post-Doctoral Associates, Staff, and Visitors

[Back to the Table of Contents]


Categorized Index to Project Publications

Program Slicing, Differencing, Merging, etc.

Overview

The Wisconsin Program-Slicing Tool

CodeSurfer System

Slicing

Chopping

Differencing

Merging

Algebra of slices (and applications to program merging)

Semantics and slicing

Other applications of slicing

Implemented integration system (for a small Pascal subset)

Miscellaneous

Ph.D. Dissertations

[Back to the Table of Contents]

Interprocedural Dataflow Analysis

Demand IDFA via bottom-up logic programming and the magic-sets transformation

Exhaustive and Demand IDFA via graph reachability

IDFA using more than graph reachability

PTIME completeness of IDFA

[Back to the Table of Contents]

Alias Analysis, Pointer Analysis, and Shape Analysis

Ph.D. Dissertations

[Back to the Table of Contents]

Analysis of Multi-Threaded Programs

Ph.D. Dissertations

[Back to the top]

Symbolic Abstraction and Decision Procedures

Ph.D. Dissertations

[Back to the top]

Other Program-Analysis Problems

Ph.D. Dissertations

[Back to the top]

Path Problems

Context-Free-Language Reachability

Other Path Problems

Ph.D. Dissertations

[Back to the Table of Contents]

Model Checking

Software

Ph.D. Dissertations

[Back to the Table of Contents]

Computer Security

Ph.D. Dissertations

[Back to the Table of Contents]

Code Instrumentation

Ph.D. Dissertations

[Back to the Table of Contents]

Computational Differentiation and Computational Divided Differencing

[Back to the Table of Contents]

Clone Detection

Software

Ph.D. Dissertations

[Back to the Table of Contents]

Miscellaneous

[Back to the Table of Contents]


Project Bibliography

Books

[Back to the top]

Journal Publications

[Back to the Table of Contents]

Invited Papers

[Back to the Table of Contents]

Book Chapters

[Back to the Table of Contents]

Reprinted in Collections

  • Reps, T. and Teitelbaum, T., Language processing in program editors. In Language Architectures and Programming Environments, T. Ichikawa and H. Tsubotani (eds.), The World Scientific Publishing Company, Singapore, 1992, pp. 146-169.

    Reprinted from IEEE Computer 20, 11 (November 1987), 29-40.

  • Teitelbaum, T. and Reps, T., The Cornell Program Synthesizer: A syntax-directed programming environment. In Interactive Programming Environments, D. Barstow, E. Sandewall, and H. Shrobe (eds.), McGraw-Hill, 1984, pp. 97-116.

    Reprinted from Communications of the ACM 24, 9 (September 1981), 563-573. [abstract; ACM Author-Izer Link.]

  • Teitelbaum, T., Reps, T., and Horwitz, S., The why and wherefore of the Cornell Program Synthesizer. In Software Development Environments, A.I. Wasserman (ed.), IEEE Computer Society, Washington, DC, 1981, 64-72.

    Reprinted from 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.]

    [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]

    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]