What is a program slice?

A program slice singles out all statements that may have affected the value of a given variable at a specific program point. The screenshot below gives an example. Mark Weiser, who introduced the concept two decades ago, claimed a slice to be the mental abstraction people make when they are debugging a program.

Slicing for refactoring

Different software engineering tasks require slightly different notions of slices. For example, refactoring requires the computed slices to be executable, whereas code understanding does not. A refactoring tool must rely on a well-balanced slicing analysis, neither too slow nor too inaccurate. Our tool is based on a static interprocedural analysis, i.e. using statically available information through different methods and classes.

Our approach

Several algorithms have been proposed to compute slices. There are mainly two approaches: slicing as an iterative dataflow equations problem and slicing as a dependence graph reachability problem. We believe that building a graph representation of a whole program is inappropriate in the case of refactoring where only one slice of the same program is needed at a time. Our approach consists of an iterative context-sensitive analysis using inference rules which are computed on demand and cached for possible reuse. Details can be found here.

Links

• Mark Harman's analysis, slicing and transformation network: ASTReNeT
• A survey of program slicing techniques (PDF) by Frank Tip
• The Wisconsin Program Slicing Project
• Jens Krinke's slicing page (many useful links to related projects and papers)

Screenshot (statements that do not contribute to the value of product are removed)

Back to Nate's home page