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) = bwhere natural numbers are build from constructors

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,_) = aHere, the second rule in the definition of function

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)

main xs = SLICE (main Len xs) SLICE x = xIf you want to play with the system, you can load in the program slicing tool as follows:

prelude> :l slicerThen, to compute the above slice, you can type

slicer> main "Examples/lenmax"where

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