Program schemas and slicing

Program slicing is a program simplification technique in which we eliminate parts of the program that are not of interest. For example, we might produce a (backwards static) slice of a program p at a given node n and for the variables in a set V - we can eliminate any statement of p that cannot affect the values of variables in V at n. Program slicing has the potential to help wherever complexity could be a problem.

There are a number of variants on slicing. For example, we could ask for the parts of the program affected by the node of interest (forwards slicing) - something that can help in ripple analysis. We also might have additional information when we slice, such as the exact input in which we are interested (dynamic slicing) or a condition that we can place on the input (conditioned slicing). We can also allow more general transformations to be applied to the program, rather than just deleting statements (amorphous slicing).

Our interest in program slicing led us to investigate program schemas. A program schema is an abstraction produced by replacing each expression in a program by a name (function or predicate name) and a list of parameters. This abstracts away details regarding what the actual expressions do. The hope is that problems, such as equivalence, will become decidable for classes of schemas.

The abstraction applied when using schemas correspond to that used in many program analysis techniques (such as program slicing and variable dependence analysis). It is also consistent with dataflow testing techniques. Thus, if we can answer questions about schemas we may well be able to make advancements in these areas.

Back to Rob Hierons' home page

Last updated: May 2010.

Disclaimer The contents of this page falls outside the responsibility of Brunel University.