数理解析研究所講究録996 巻 1997 年 54-65

54Program Slicing using Functional Networks
Sebastian Danicic and Mark Harman
Project Project,
School of Computing,
University of North London,.
Eden Grove, London, N7
tel: $+44$ (0)1716072789
fax: +44 (0)1717537009-mail: . harmanunl. . uk
$8\mathrm{D}\mathrm{B}$$\mathrm{m}$$\mathrm{e}$$4^{th}$RIMS Workshop in Computing,$\mathrm{a}\mathrm{c}$$22^{nd_{-24^{t}}h}$July, 1996

Abstract
Program slicing is a technique for identifying a subprogram from an original program. The subprogram,called a slice, is an executable program which maintains the effect of the original upon a chosen set ofvariables at some point within the Control Flow Graph (CFG) of the original. The variable set, CFG nodepair isthe slicing criterion.
Slices find applications in debugging, testing, parallelisation, -use, code measurement and program
comprehension. These applications exploit the way in which slicing preserves a projection of the original
program’s semantics, allowing, in some cases, for considerable syntactic simplification.
The paper introduces an approach to the computation of a slightly more general form of a slice, called asimultaneous slice. A simultaneous slice is constructed with respect to a set of conventional slicing criteria.
The approach introduced here uses a functional implementation of a network of communicating processes,
each process corresponding to a CFG node and each message corresponding to either a variable name or anode identifier.
$\mathrm{c}\mathrm{a}\mathrm{U}\mathrm{e}\mathrm{d}$$\mathrm{r}\mathrm{e}$1Introduction

Program slicing can be used to extract a sub-program concerned with a sub-domain of the overall computationof a program, provided this sub-domain is captured at compile time by the values that the program stores ina subset of its variables at some point of interest during the computation. Definition 1.1 gives an informal
definition of a slice. This definition is concerned with the static paradigm, where no information describing the
inputs to the program is available.

Definition 1.1 (Static Slice)
A slice of a program is constructed with respect to a slicing criterion (V, ), where is a set of variables, andis a point of interest within . A slice of is any program constructed from by the deletion of zero or morestatements, and which has the same effect as upon the variables in
at .
$V$

$n$

$p$

$n$

$p$

$p$

$p$

$p$

$V$

$n^{1}$

Figure 1, shows a program (in the left hand box) and a slice constructed from it, with respect to the slicing.
criterion
Following Weiser’s original definition of this static form of program slice [29, 30, 32], several authors haveadapted the slicing concept to the dynamic paradigm [2, 16, 9, 17] (in which the input sequence to the programis fully defined at slice-construction time), and to a quasi-static paradigm $[26, 28]$ (where partial information
about the input to the program is available). This paper is concerned solely with the static slicing paradigm.
Because a slice captures the thread of computation pertinent to a chosen set of variables at some point in theoriginal program, it has many applications, all of which are based upon the fact that a slice is a simplified version$(\{\mathrm{s}\}, 9)$

1It is conventional to number the statements of the program, in order to identify statements of interest.

55

Figure 1: A Pascal Program Fragment and One of its Static Slicesof the original which maintains a projection of its semantics. These applications include cohesion measurement[4, 22, 18, 11], algorithmic debugging [23, 15, 10], -engineering $[19, 24]$ , component -use [3], automaticparallelisation [31], maintenance and debugging $[8, 20]$ and program integration [13]. Tip [27] and Binkley andGallagher [5] provide .etailed surveys of the paradigms, applications and algorithms for program slicing.
Simultaneous slicing is a generalisation of slicing, where the slicing criterion, rather than being a single pointin the program, is a whole set of program point, variable set pairs. .
A fixpoint theory for simultaneous slicing is developed in terms of Functional Networks. Functional Networks, in his theory of parallel programs and thoseare a structure based on the networks introduced byfor reasoning about concurrent systems. Directly from this ‘semantics of simultaneous
used byslicing’, an algorithm for simultaneous slicing is derived.
One of the useful properties of an FN is that is can be viewed both as a set of functions written in a purefunctional language or as a network of intercommunicating processes. The composition of functions corresponds
to the topology of the network, while the parameter passing between functions corresponds to message passingin the network.
For the problem of slicing, messages will consist of variable names and ‘node identifiers’, and each functionin the FN will represent a node in the CFG of the program to be sliced. The variable names represent variables
whose value must be preserved in the slice and the node identifiers represent nodes of a
CFG whichhave already been included in the slice.
Functional languages, with their higher order semantics and polymorphic functions on sets, provide a very
natural medium for implementing such process communication systems. The language Hope is used for definiteness, although any similar functional notation would be equally suitable.
The rest of this paper is organised as follows. Section 2 presents an overview of the parallel slicing algorithm
first introduced in [6] and section 4 introduces Functional Networks. Section 5 presents the slice semantics of, which is used in section 6 to develop an implementation of slicing using the functional language Hope.
$\mathrm{r}\mathrm{e}$$\mathrm{r}\mathrm{e}$$\mathrm{d}$$\mathrm{K}\mathrm{a}\mathrm{h}\mathrm{n}[14]$$(\mathrm{F}\mathrm{N}\mathrm{s})$$\mathrm{A}\mathrm{b}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}\mathrm{k}\mathrm{y}[1]$)$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}$$\mathrm{F}\mathrm{N}\mathrm{s}$2

The Parallel Slicing Algorithm

This section briefly reviews the parallel algorithm introduced in [6].
The algorithm has two distinct stages:

1. A Compilation Stage: The program to be sliced2 is compiled into a functional network.
2. An Execution Stage: The functional network is executed. The statements of the object program to be
kept in the final slice are obtained from the resulting input to the process corresponding to the START
node of the CFG of the program to be sliced.
2From now on, the program to be sliced will be referred to as the ‘object program’.

56
The Compilation Stage

2.1

The compilation stage is straight-forward. The topology of the network is that of the object program’s Reverse
channel in the process network.
Control Flow Graph (RCFG)3 [12]. Each arc ofthe RCFG corresponds to an
is described by definition 2.1.
behaviour
whose
in
the
networkprocess
Each node of the RCFG corresponds to a$\mathrm{I}/\mathrm{O}$

2.1.1

Process States

The behaviour of each process depends entirely on its state. The state of each process is derived from the object
program and consists of a four-tuple containing the following information:
The node identifier of process
The set of referenced variables of
The set of defined variables of
The set of controlled nodes of
$n$

$n$

REF

$(n)$

$n$

$n$

$\mathrm{D}\mathrm{E}\mathrm{F}(n)$$C(n)$$n$An algorithm for calculating $C(n)$ is given in [7] and the calculation of REF $(n)$ and2.1.2$\mathrm{D}\mathrm{E}\mathrm{F}(n)$is trivial [29].

Process Behaviour

Each process is a process which sends and receives messages, each message being a set of variable names andprocess identifiers.
or $C.(n)$ then the
Suppose a process receives a set . If has any elements in common withprocess outputs a set consisting of:
$I$

$I$

$n$

$\mathrm{D}\mathrm{E}\mathrm{F}(n)$$n$1. all elements of$I$

that it does not define,

2. all variables that it references and3. its own node identifier.
otherwise process simply copies the input to its output channels.
in definition 2.1.
More formally, the behaviour of process is denoted
$I$

$n$

$\delta(n)$$n$Definition 2.1 (Process Behaviour)$\delta(n)=\lambda I$.

$(I-\mathrm{D}\mathrm{E}\mathrm{F}(n))\cup \mathrm{R}\mathrm{E}\mathrm{F}(n)\cup\{n\}$
$\{$

$I$

2.2

The Execution Stage

2.2.1

Initiating the Network

ifotherwise.

$I\cap(\mathrm{D}\mathrm{E}\mathrm{F}(n)\cup C(n))\neq\emptyset$,

In order to construct a slice for the criterion (V, ), network communication is initiated by placing the set
the output arc(s) of process .
$n$

$V$

on

$n$

2.2.2

Changes in the Network StateThe network state changes as a result of process outputting values in response to inputs, thereby causing newsets to appear on the arcs of the network.
A process outputting a set, , has the effect of updating the value(s) of all the output arc(s) of by‘unioning’ what was on the arc(s) before with . The state of each process, however, remains unchanged as the
$n$

$O$

$n$

$O$

communication progresses.
3A program’s RCFG is simply the inverse of its CFG. Note that an RCFG is itself a CFG. The START node of a program’s
RCFG is the STOP node of its CFG and vice-versa.

57
;
;
;
while

1

$1^{=}1$

2
3
4
5
6

$\mathrm{s}=0$$\mathrm{p}=1$$(\mathrm{i}<=\mathrm{N})$$\mathrm{s}=\mathrm{s}+\mathrm{i}$

$\{$

;

$\mathrm{P}^{=}\mathrm{P}^{*_{\mathrm{i};}}$

7
8$\mathrm{i}=\mathrm{i}+1;\}$Figure 2: The ‘Sum and Product’ Program

2.2.3

Termination

Eventually the network reaches a state where further communication causes no new messages to be created on
any arc. At this stage communication ceases and the network is said to be stable.

2.3

The Final Result

The statements of an object program that should be included in the final slice are precisely those whose
corresponding identifiers are on an input arc of the STOP process when the network stabilises [6].

3

An Example

3.1

Example Compilation

The object program is the ‘Sum and Product’ Program given in Figure 2.
Diagramatically, the state of each process will be represented by placing the values of each four statecomponents in one of four quadrants. Defined variables will be placed in the lower left quadrant, referenced
variables in the lower right, controlled nodes in the upper left and the node identifier in the upper right.
Each process corresponds to one of the numbered ‘statements’ of the ‘Sum and Product’ program. Process
7, for example, corresponds toand so has DEF(7)and has $C(7)=\emptyset$ . Its state is thus
shown as:$\mathrm{i}:=\mathrm{i}+1$$=\mathrm{R}\mathrm{E}\mathrm{F}(7)=\{\mathrm{i}\}$

Processes corresponding to primitive statements of the object program will have one input channel. Process
4, however, is a called ‘predicate process), corresponding to a predicate in the object program and thus has two
input channels. Also, being a typical predicate, process 4 controls other processes, in this case, $C(4)=\{5,6,7\}$ .
Process 4 also references the two variables and , and, being side-effect free, has no defined variables. Its
state, therefore, is:$\mathrm{i}$$\mathrm{N}$The network constructed for the program in Figure 2 is thus as shown in Figure 3.

3.1.1

Example Execution

Let the slicing criterion be$(\{\mathrm{p}\}, 8)$.

58

Figure 3: Initial Network State

Execution is initiated by placing
on the output channel of the START process.
passes through processes 4 and 5 without effect, until it reaches process 6. Since DEF(6)The set,this input causes process 6 to output. This is an example of a process responding to a data dependence
in the object program. The set
passes through process 5 without effect. At the same time,
passesfrom process 4 to process 3, whereupon, process 3 outputs {3} This set passes on through processes 2 and 1
without effect. The network state at this stage is picture in Figure 3.1.1.
Since the $C(4)=\{5,6,7\}$ , the input
causes process 4 to output. This is an example ofa process responding to a control dependence in the original program.
The state of the network at this stage is pictured in Figure 5.
The sethaving been output from process 4, passes round the cycle causing process 7 to output
also through process 2 and 1 causing process 1 to output. Once the output
from process 7 has reached the STOP process of the network, no new
occurs and the system has stabilisedin the final network state pictured in Figure 6.
In this state those process identifiers which reside as input arcs to the STOP process is {7, 6, 4, 3, 1} andthus the slice for the ‘Sum and Product’ program produced by this algorithm is as shown in Figure 7.
$\{\mathrm{p}\}$$=\{\mathrm{p}\}$$\{\mathrm{p}\}$$\{\mathrm{p}, \mathrm{i}, 6\}$$\{\mathrm{p}, \mathrm{i}, 6\}$$\{\mathrm{p}\}$$\{\mathrm{p}, \mathrm{i}, 6\}$$\{\mathrm{p}, \mathrm{i}, \mathrm{w}, 6,4\}$$\{\mathrm{p}, \mathrm{i}, \mathrm{N}, 6,4\}$$\{\mathrm{p}, \mathrm{i}, \mathrm{N}, 7,6,4\}$$\{\mathrm{p}, \mathrm{i}, \mathrm{N}, 7,6,4,1\}$$\mathrm{I}/\mathrm{O}$4

Functional Networks(FNs)

A Functional Network is simply a generalisation of the network described above. Let $N$ be a set of Processes
and a set (of messages). A functional network is a pair, consisting of a CFG, , and a process function,, the type of which is:$S$$(G, \delta)$$G$$\delta$$\delta$: $Narrow(Sarrow S)$

where is a set of subsets consisting of variable names and node identifiers. Importantly, for each particular
program, will be finite since it is bounded above by the union of the set of variable names mentioned in the
program together with the set of labels (node identifiers) of the program. Observe that forms a finite latticewith respect to , with, andequal to the set consisting of all the variable names and labels (nodeidentifiers) mentioned in the program from which the FN was derived.
$S$

$S$

$S$

$\subseteq$$\perp=\emptyset$$\mathrm{T}$59

Figure 4: An intermediate Network State

Figure 5: An intermediate Network State

60

Figure 6: Final Network State

1

3
4
6

7

;
;
while
$1=1$

$\mathrm{p}=1$$(\mathrm{i}<=_{\mathrm{N})}$$\{$$\mathrm{p}^{=}\mathrm{p}*_{\mathrm{i};}$$\mathrm{i}=\mathrm{i}+1$; }Figure 7: The slice produced with respect to$(\{\mathrm{p}\}, 8)$

61
areis monotonic, and hence, since is finite, theAlso, essentially, each process function
with respect to . Furthermore, since is finite, it is a complete lattice and therefore the relevant least upperbounds and least fixpoints all exist.
guarantees, that continuity of theIt will be shown, by appealing to Kleene’s First Recursion
that the required fixpoints corresponding (best’ (i.e. thinnest) slices can be reached in a finite number of steps,$S$$\delta(n)$$\delta(n)$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{u}\mathrm{o}\mathrm{u}\mathrm{s}[25]$$S$$\subseteq$$\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{m}[21]$$\delta(n)$as the least upper bounds of Kleene Chains.

)
Definition 4.1 (A Functional Network
Let be a finite lattice of messages,, consisting of a CFG, , and a process function
An FN is a pair$(\mathrm{F}\mathrm{N})$

$S$

$G$

$(G, \delta)$$\delta$: $Narrow(Sarrow S)$

such that
Processes $(G)\subseteq N$

and$\forall n\in N,$ $\delta(n)$5The Slice Semantics of FNs

5.1

Simultaneous Slicing Criteria

is continuous.

A Simultaneous Slicing Criterion was introduced in section 1. It is simply a labelling of the arcs ofelements of . Namely a function of type:

$G$

with

$L$

$S$

$L$

: $Garrow S$ .

Note that labelling function is total. Technically, arcs not mentioned in the slicing criterion will be mapped
to the empty set in its corresponding arc labelling.
$L$)
Definition 5.1 (Slicing Criteria of anis simply a labelling ofA slicing criterion for a$\mathrm{F}\mathrm{N}$$\mathrm{F}\mathrm{N},$5.2$(G, \delta)$$G$.

Termination

Execution of the network terminates when further activity has no effect on the labelling of all of the arcs of the
network. A network reaches this state when its arcs are labelled with what is called a Stable Labelling. In thisstate the labelling function represents a stable network.

Definition 5.2 (A Stable Labelling of anis a function
A Stable Labelling of$\mathrm{F}\mathrm{N}$)$(G, \delta)$$L$: $Garrow S$

such that$(a, b)\in G$ and $(a, c)\in G\Rightarrow L(a, b)=L(a, c)$and$(a, b)\in G$ and $(b, c)\in G\Rightarrow\delta(b)(L(a, b))\subseteq L(b, c)$

The first condition simply ensures that all arcs emerging from a process are labelled with the same values.
The second condition states that the labelling of the output arcs from each process is a set containing the resultof applying the process’s corresponding process function to the value of the labels of its input arcs. Since this
it is clear that further activity cannot change this network state. The
is true for every process in the
network is thus considered to be stable.
$\mathrm{n}\mathrm{e}\mathrm{t}\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{k}\rangle$

62
A finite lattice of stable labellings

5.3

From any$\mathrm{F}\mathrm{N}$, a finite lattice of stable labellings, ordered by pointwise set inclusion is derived. i.e.

$\forall x\in G,$ $L_{1}(X)\subseteq L_{2}(x)$.

$L_{1}\subseteq L_{2}\Leftrightarrow$.

A slice of an FN

5.4

Given a slicing criterion$C$, a slice with respect to $C$ is simply a stable labelling ‘at least as big’ as $C$ .

Definition 5.3 (A Slice of anLet
be a slicing criterion ofrespect to if and only if.

$\mathrm{F}\mathrm{N}$$C$$(G, \delta)$$C$), and let.
$L$

be a stable labelling of, then$L$with respect to$C$$(G, \delta)$

is a slice of$(G, \delta)$

with$C\subseteq L$

The ‘Best’ Slice

5.5

and a slicing criterion
Given an FN
least stable labelling containing , i.e.

$C$$(G, \delta)$, the best slice of$(G, \delta)$, denoted$\mathcal{B}S_{C}^{(G,\delta)}$, is the$C$

Definition 5.4 (The Best Slice of an1.

,$BS_{C}^{(\delta)}G$

is a slice of$(G, \delta)$$\mathrm{F}\mathrm{N}$)with respect to $C$

and

2.

$L$

is a slice of$(G, \delta)$

with respect to$C\Rightarrow BS_{C}^{(G,\delta)}\subseteq L$

corresponds to a labelling where the network has stabilised. That is each of the arcs are labelledwith sets that are ‘as small as possible’ but still contain the slicing criterion. Since the set of stable labellingsof an FN is a finite lattice, and hence complete, best slices always exist.
The ‘Best Slice Theorem’ that follows defines a function
on slicing criteria forwhose least
fixpoint containing $C$ must be the best slice ofwith respect to $C$ . Intuitively, applying the function
corresponds to executing a single
orof the parallel slicing algorithm introduced in [6].
Becauseis continuous, Kleene’s First Recursion Theorem guarantees that successive applications ofwill take the network into a state corresponding to the best slice. The finiteness of guarantees that thisprocess will terminate.
$BS_{C}^{(G,\delta)}$$(G, \delta)$$f_{(G,\delta)}$$(G, \delta)$($f_{(G,\delta)}$($\mathrm{c}\mathrm{l}\mathrm{i}_{\mathrm{C}}\mathrm{k}’$$\mathrm{r}\mathrm{i}_{\mathrm{P}\mathrm{P}}1\mathrm{e}^{)}$$f_{(G,\delta)}$$S$$f_{(G,\delta)}$

Theorem 5.1 (The Best Slice Theorem)Let: $((Garrow S)arrow(Garrow S))$ be defined as$f_{(G,\delta)}$$f_{(G,\delta)}= \lambda C.\lambda(x, y).C((_{X}, y))\cup(z,)\bigcup_{x\in G\triangleright x}\delta(x)(c((_{Z}, x)))$where$G\triangleright x$

is the set of all arcs ofleast fixpoint of$Bs_{C}^{(G,\delta)}=\mathrm{t}\mathrm{h}\mathrm{e}$$G$which end in$f_{(G,\delta)}$

containing

i.e. $\{(y, z)\in G|z=x\}$ then.

$x$$C=\lfloor.\rfloor f_{(\delta)}^{i}c,(c_{)}|$

Proof

Clearly is a stable labelling ofis a slice ofw.r.t
is the least fixpoint of
But. is a fixpointis a fixpoint of
is a fixpoint of
andcontaining .

$(G, \delta)\Leftrightarrow z$

$z$

So
So

$C\Leftrightarrow z$$(G, \delta)$$z$$Bs_{C}^{(G,\delta)}$$\mathrm{u}_{\dot{\iota}}f_{(c,\delta)}^{i}(C)$$f_{(G,\delta)}$$f_{(G,\delta)}\mathrm{c}\mathrm{o}..\mathrm{n}\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}C$$f_{(G,\delta)}$$f_{(G,\delta)}$$C$.

Moreover, suppose is a fixpoint
containing
thenfor all by induction,$B$$f_{(G,\delta)}$$i$$f_{(G,\delta)}^{i}(C)\subseteq B$

therefore$\square _{i}f_{(c,\delta}^{i}$)$(C)\subseteq B$

.

$C$

,

.

$C\subseteq z$.

63
dec mapset: (alpha $->$ set (beta)) X set (alpha)–mapset $(\mathrm{f},\{\})<=$$—$

mapset(f, s)

type node$<=$$==\mathrm{n}\mathrm{u}\mathrm{m}$

let
in

type
type
dec

split(s)union mapset$(\mathrm{x},\mathrm{y})==$$\mathrm{f}(\mathrm{X})$$(\mathrm{f},\mathrm{y})$;;data message $==$ no(node)$\mathrm{S}==$set (beta);

$->$

;

$\{\}$$++\mathrm{v}\mathrm{n}$($\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}$(char));set (message);node;(num $->$ alpha)$\mathrm{N}==$$\mathrm{e}\mathrm{q}$:X (num $->$ alpha)
;
if
then
else false;

X num $->$ truval;$—\mathrm{e}\mathrm{q}(\mathrm{f},\mathrm{g},0)<=\mathrm{f}(0)=\mathrm{g}(0)$–$\mathrm{e}\mathrm{q}(\mathrm{f},\mathrm{g}, \mathrm{s}\mathrm{u}\mathrm{c}\mathrm{C}(\mathrm{n}))<=$$\mathrm{f}(\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}(\mathrm{n}))=\mathrm{g}(\mathrm{s}\mathrm{u}\mathrm{C}\mathrm{C}(\mathrm{n}))$$\mathrm{e}\mathrm{q}(\mathrm{f},\mathrm{g},\mathrm{n})$dec$\mathrm{B}\mathrm{S}$:(num X$(\mathrm{N}->\mathrm{S})\mathrm{X}(\mathrm{N}->(\mathrm{S}->\mathrm{S}))\mathrm{X}(\mathrm{N}->\mathrm{s}\mathrm{e}\mathrm{t}(\mathrm{N}))$$—$ BS(max,C,delta, G)

let$\mathrm{f}\mathrm{G}\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{t}\mathrm{a}==$lambdaunion (delta$->(\mathrm{N}->\mathrm{s})$;$\mathrm{x}=>$$\mathrm{C}(\mathrm{x})$

in if

)

$<=$

$(\mathrm{X})$)$\mathrm{m}\mathrm{a}\mathrm{p}\mathrm{S}\mathrm{e}\mathrm{t}(\mathrm{C}, \mathrm{G}(\mathrm{x}))$$\mathrm{e}\mathrm{q}(\mathrm{C},\mathrm{f}\mathrm{c}\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{t}\mathrm{a},\max)$thenelse BS ($\mathrm{C}$$\max,\mathrm{f}\mathrm{G}\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{t}\mathrm{a}$, delta, G);

Figure 8: Hope Implementation of the Slicing Algorithm

So

So

6

$\lfloor_{:}\rfloor f_{(}^{i}c,\delta$$eS_{C}^{()}G,\delta$) $(c)$ is the least fixpoint ofis the least fix point of$f_{(G,\delta)}$$f_{(G,\delta)}$that contains $C$ .

containing$C=\lfloor_{\iota},\rfloor f_{()}iG,\delta(C)$as required.

Implementing Static Slicing Using FNs

The theory above has shown that in order to implement an algorithm to produce a best slice, all that is required
is to implement the process of producing successive approximations tobyapplications of.
.
The implementation is defined in the functional language Hope in Figure 8.
$BS_{C}^{()}G,\delta$$f_{(G,\delta)}$$\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{e}.\mathrm{d}$7Conclusion and Future Work

This paper introduces a functional implementation of the concurrent static slicing algorithm introduced in [6].
The implementation relies upon a theory of functional networks, which can be viewed in either of two ways
–as a composition of functions on sets of messages or as a network of communicating processes. The theory
guarantees the existence of ‘best slices’ (slices which are as thin as possible given the approximate nature of
the calculation of defined and referenced variables, and the simplifying assumption that no define-use chainsare infeasible). The guarantee, in turn, ensures that the implementation of the functional network (as a Hope.
.program) terminates, yielding the ‘best
Work is currently in progress to extend this theory and its associated implementation to the problem ofinterprocedural slicing (slicing across procedure boundaries) and to handle slicing in the presence of pointeraliasing.
The authors also believe that the close correspondence between a CFG of a program and the concurrent
solution to graph theoretic problems involving the CFG may be more widely applicable.
$\mathrm{s}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}^{)}$‘

64
References[1] ABRAMSKY, S. Reasoning about concurrent systems. In Distributed Computing (London, 1984), pp. 307-

319.
[2] AGRAWAL, H., AND HORGAN, J. R. Dynamic program slicing. In ACM SIGPLAN Conference on
Programming Language Design and Implementation (New York, June 1990), pp. 246-256.

[3] BECK, J., AND EICHMANN, D. Program and interface slicing for reverse engineering. In $IEEE/ACM15^{th}$Conference on Soflware Engineering (ICSE’9g) (1993), pp. 509-518.
[4] BIEMAN, J. M., AND OTT, L. M. Measuring functional cohesion.
Engineering 20, 8 (Aug. 1994), 644-657.

IEEE Transactions on Soflware[5] BINKLEY, D. W., AND GALLAGHER, K. B. Program slicing. Annals of Computing (1996). To appear.
[6] DANICIC, S., HARMAN, M., AND SIVAGURUNATHAN, Y. A parallel algorithm for static program slicing.
Information Processing Letters 56, 6 (Dec. 1995), 307-313.

[7] FERRANTE, J., OTTENSTEIN, K. J., AND WARREN, J. D. The program dependence graph and its use in
optimization. ACM Transactions on Programming Languages and Systems 9 (July 1987), 319-349.
[8] GALLAGHER, K. B., AND LYLE, J. R. Using program slicing in software maintenance. IEEE Transactions
on Soflware Engineering 17, 8 (Aug. 1991), 751-761.
[9] GOPAL, R. Dynamic program slicing based on dependence graphs. In IEEE Conference on Software
Maintenance (1991), pp. 191-200.
[10] HARMAN, M., AND DANICIC, S. Using program slicing to simplify testing. Journal of Software Testing,
Verification and Reliability 5 (Sept. 1995), 143-162.
[11] HARMAN, M., DANICIC, S., SIVAGURUNATHAN, B., JONES, B., AND SIVAGURUNATHAN, Y. Cohesion
Quality Week (San Francisco, May 29th–june 2nd. 1995), pp. Paper 3-T-2,
metrics. In
pp1-14.
$8^{th}Inte\Gamma nati\mathit{0}nal$[12] HECHT, M. S. Flow Analysis of $c_{ompu}.ter$ Programs. Elsevier, 1977.

[13.] HORWITZ, S., PRINS, J., AND REPS, T. Integrating non-interfering versions of programs. ACM Transactions on Programming Languages and Systems 11, 3 (July 1989), 345-387.

[14] KAHN, G. A simple theory of parallel programs. In International Foundations of Information Processing,World Congress (1974).
[15] KAMKAR, M. Interprocedural dynamic slicing with applications to debugging and testing. PhD Thesis,
Department of Computer Science and Information Science, Link\"oping University, Sweden, 1993. Available
as Link\"oping Studies in Science and Technology, Dissertations, Number 297.
[16] KAMKAR, M., SHAHMEHRI, N., AND FRITZSON, P. Interprocedural dynamic slicing. In Proceedings of theConference on Programming Language Implementation and Logic Programming (1992), pp. 370-384.
$4^{th}$[17} KOREL, B., AND LASKI, J. Dynamic program slicing. Information Processing Letters 29, 3 (Oct. 1988),

155-163.

[18] LAKHOTIA, A. Rule-based approach to computing module cohesion. In Proceedings of theon Soflware Engineering (ICSE-15) (1993), pp. 34-44.

[19]$15^{th}$Conference, L., AND ELLIS, R. An approach to eliminating COMMON blocks and deriving ADTs from Fortran, Feb. 1993.
programs. Technical report, University of Westminster,$\mathrm{L}\mathrm{l}\mathrm{U}$$\mathrm{U}\mathrm{K}$[20] LYLE, J. R., AND WEISER, M. Automatic program bug location by program slicing. In
Conference on Computers and Applications (Peking, 1987), pp. 877-882.

$2^{nd}$International

65[21] MANNA, Z. Mathematical Theory of Computation.

$\mathrm{M}\mathrm{c}\mathrm{G}\mathrm{r}\mathrm{a}\mathrm{W}$-Hill, 1974.

[22] OTT, L. M., AND THUSS, J. J. Slice based metrics for estimating cohesion. In Proceedings of the IEEE-CS
International Metrics Symposium (1993), pp. 78-81.

[23] SHAHMEHRI, N. Generalized algorithmic debugging.
Thesis, Department of Computer Science andInformation Science, Link\"oping University, Sweden, 1991. Available as Link\"oping Studies in Science andTechnology, Dissertations, Number 260.
$\mathrm{P}\mathrm{h}\mathrm{D}$[24] SIMPSON, D., VALENTINE, S. H., MITCHELL, R.,$ACM$ Fortran forum 12, 3 (Sept. 1993), 26-32.

$\mathrm{L}\mathrm{l}\mathrm{U}$, L., AND ELLIS, R. Recoup–Maintaining Fortran.

[25] STOY, J. E. Denotational semantics: The cott-Strachey approach to programming language theory. MIT
Press, 1985. Third edition.
$S\backslash$[26] TIP, F. Generation of Program Analysis
Amsterdam, 1995.
[27]$\mathrm{T}\mathrm{l}\mathrm{P}$$Tool\dot{s}$.

$\mathrm{P}\mathrm{h}\mathrm{D}$thesis, Centrum voor Wiskunde en Informatica,, F. A survey of program slicing techniques. Journal of Programming Languages (1995). To appear.

[28] VENKATESH, G. A. The semantic approach to program slicing. In $ACM$ SIGPLAN Conference on Programming Language Design and Implementation (Toronto, Canada, June 1991), pp. 26-28. Proceedings in
SIGPLAN Notices, 26(6), pp.107-119, 1991.
[29] WEISER, M. Program slices: Formal, psychological, and practical investigations $.of$ an automatic program
thesis, University of Michigan, Ann Arbor,, 1979.
abstraction method.
$\mathrm{P}\mathrm{h}\mathrm{D}$[30] WEISER, M. Program slicing. In
Mar. 1981), pp. 439-449.

$\mathrm{M}\mathrm{I}$$5^{th}$International Conference on Soflware Engineering (San Diego,$\mathrm{C}\mathrm{A}$,[31] WEISER, M. Reconstructing sequential behaviour from parallel behaviour projections. Information Processing Letters 17, 10 (1983), 129-135.
[32] WEISER, M. Program slicing. IEEE Transactions on Soflware Engineering 10, 4 (1984), 352-357.