A Forward Slicing Tool for Curry (v1.3)

Essentially, program slicing is a method for decomposing programs by analyzing their data and control flow. It has many applications in the field of software engineering (e.g., program understanding, maintenance, debugging, reuse, merging, testing, etc). This concept was originally introduced by Weiser in the context of imperative programs. Surprisingly, there are very few approaches to program slicing in the context of declarative programming. Roughly speaking, a program slice is a subset of the program statements which are (potentially) related with the values computed at some program point and/or variable, referred to as a slicing criterion. Program slices are usually computed from a program dependence graph. Program dependences can be traversed backwards or forwards (from the slicing criterion), which is known as backward or forward slicing, respectively. Additionally, slices can be dynamic or static, depending on whether a concrete program's input is provided or not. A complete survey on program slicing can be found in [Tip95].

The main purpose of partial evaluation techniques is to specialize a given program w.r.t. part of its input data (hence it is also known as program specialization). The partially evaluated program will be (hopefully) executed more efficiently since those computations that depend only on the known data are performed (at partial evaluation time) once and for all. Many online partial evaluation schemes follow a common pattern: given a program and a partial call, the partial evaluator builds a finite representation (generally a graph) of the possible executions of the (partial) call, and then systematically extracts a residual program (the partially evaluated program) from this graph. This view of partial evaluation clearly shows the similarities with program slicing: both techniques should construct a (finite) representation of some program execution, usually with part (or none) of the input data.

Here, we present a forward slicing tool based on (online) partial evaluation. While the construction of a graph representing some program execution is quite similar in both techniques, the extraction of the final program is rather different. Partial evaluation usually achieves its effects by compressing paths in the graph and by renaming expressions while removing unnecessary function symbols. In contrast, program slicing should preserve the statements of the original program. Roughly speaking, (forward) slicing can be regarded as a rather conservative form of partial evaluation; in particular, it can easily be desgined from a monovariant and monogenetic partial evaluation scheme (in order to preserve a one-to-one relation between the functions of the original and residual programs).

Our (forward) slicing tool for the multi-paradigm language Curry has been implemented by adapting an existing partial evaluator for Curry programs. It required a small implementation effort, i.e., only the underlying meta-interpreter needed significant changes.

Let us illustrate our slicing method by means of an example. Consider the following simple program to compute both the length and the maximum of a given list:

data Nat = Zero | Succ Nat
data Op = Len | Max

main Len xs = fst (lenmax xs)
main Max xs = snd (lenmax xs)

lenmax xs = (len xs, max xs)

len [] = Zero
len (_:xs) = Succ (len xs)

max [x] = x
max (x:y:ys) = if (leq x y) then max (y:ys)
                            else max (x:ys)

leq Zero y = True
leq (Succ x) Zero = False
leq (Succ x) (Succ y) = leq x y

fst (a,_) = a
snd (_,b) = b

where natural numbers are build from constructors Zero and Succ. If the slicing criterion is the expression main Len xs (i.e., we are only interested in computing the length of a list), the computed slice would be:

data Nat = Zero | Succ Nat
data Op = Len | Max

main Len xs = fst (lenmax xs)

lenmax xs = (len xs, T)

len [] = Zero
len (_:xs) = Succ (len xs)

fst (a,_) = a

Here, the second rule in the definition of function main has been removed, since it is not needed to execute the slicing criterion. Also, functions max, leq, and snd have been completely deleted. Finally, observe that the second component of the tuple in the rigth-hand side of function lenmax has been replaced by the special symbol T since the evaluation of this component is not necessary to evaluate the slicing criterion.

A complete description of the program slicing method can be found in [SV07].

The source files of the program slicing tool are in CurrySlicer.tgz; it contains

slicer.curry, the implementation of the forward slicing tool
Flat.curry, Flat2Fcy.curry, and Flat.prim_c2p, some modified files of PAKCS which should be in the same directory as slicer.curry
xprelude.curry, a reduced version of the Curry prelude (which is useful to unfold prelude functions without explicitely including their definitions)
Examples, a folder containing several examples that illustrate the use of the program slicer (including the one above)

PAKCS version 1.6.0 or higher is required. The slicing criterion should be marked in the program with the special symbol SLICE, where SLICE should be defined in the program as the identity function. For instance, in the above program, we should include the following lines:

main xs = SLICE (main Len xs)
SLICE x = x

If you want to play with the system, you can load in the program slicing tool as follows:

prelude> :l slicer

Then, to compute the above slice, you can type

slicer> main "Examples/lenmax"

where Examples/lenmax.curry is the source file. The output of the slicing process is shown on the screen (though in FlatCurry) and stored in the file Examples/lenmax_slice.curry. If you want to see the computed slice in standard Curry form, you may load in the file Examples/lenmax_slice.curry and, then, use the PAKCS utility show as follows:

slicer> :l Examples/lenmax_slice
slicer> :show

Please report any bug or comment to gvidal (at) dsic.upv.es.

MiST ELP GPLIS DSIC UPV

Last update / Germán Vidal