{"history":[],"article":{"id":"124fca77-1b30-4727-b94d-2f982741a463","title":"Program slicing","slug":"program-slicing","content":":::summary\n:::\n\n# \nIn [computer programming](https://bliptext.com/articles/computer-programming), **program slicing** is the computation of the set of program statements, the **program slice**, that may affect the values at some point of interest, referred to as a **slicing criterion**.\nProgram slicing can be used in [debugging](https://bliptext.com/articles/debugging) to locate source of errors more easily.\nOther applications of slicing include [software maintenance](https://bliptext.com/articles/software-maintenance), [optimization](https://bliptext.com/articles/optimization-computer-science), [program analysis](https://bliptext.com/articles/program-analysis-computer-science), and [information flow control](https://bliptext.com/articles/non-interference-security).\nSlicing techniques have been seeing a rapid development since the original definition by [Mark Weiser](https://bliptext.com/articles/mark-weiser).\nAt first, slicing was only static, i.e., applied on the source code with no other information than the source code.\n[Bogdan Korel](https://bliptext.com/articles/bogdan-korel) and [Janusz Laski](https://bliptext.com/articles/janusz-laski) introduced dynamic slicing, which works on a specific execution of the program (for a given execution trace).\nOther forms of slicing exist, for instance path slicing.\n\n# Static slicing\nBased on the original definition of Weiser, informally, a static program slice S consists of all statements in program P that may affect the value of variable v in a statement x. The slice is defined for a slicing criterion C=(x,v) where x is a statement in program P and v is variable in x. A static slice includes all the statements that can affect the value of variable v at statement x for any possible input.\nStatic slices are computed by backtracking dependencies between statements.\nMore specifically, to compute the static slice for (x,v), we first find all statements that can directly affect the value of v before statement x is encountered.\nRecursively, for each statement y which can affect the value of v in statement x, we compute the slices for all variables z in y that affect the value of v. The union of all those slices is the static slice for (x,v).\n\n## Example\nFor example, consider the C program below.\nLet's compute the slice for ( write(sum), sum ).\nThe value of sum is directly affected by the statements \"sum = sum + i + w\" if N>1 and \"int sum = 0\" if N <= 1.\nSo, slice( write(sum), sum) is the union of three slices and the \"int sum = 0\" statement which has no dependencies:\n

slice( sum = sum + i + w, sum),
slice( sum = sum + i + w, i),
slice( sum = sum + i + w, w), and
{ int sum=0 }.

\nIt is fairly easy to see that slice( sum = sum + i + w, sum) consists of \"sum = sum + i + w\" and \"int sum = 0\" because those are the only two prior statements that can affect the value of sum at \"sum = sum + i + w\".\nSimilarly, slice( sum = sum + i + w, i) only contains \"for(i = 1; i < N; ++i) {\" and slice( sum = sum + i + w, w) only contains the statement \"int w = 7\".\nWhen we union all of those statements, we do not have executable code, so to make the slice an executable slice we merely add the end brace for the for loop and the declaration of i. The resulting static executable slice is shown below the original code below.\nThe static executable slice for criteria (, sum) is the new program shown below.\nIn fact, most static slicing techniques, including Weiser's own technique, will also remove the statement.\nSince, at the statement, the value of is not dependent on the statement itself.\nOften a slice for a particular statement x will include more than one variable.\nIf V is a set of variables in a statement x, then the slice for (x, V) is the union of all slices with criteria (x, v) where v is a variable in the set V.\n\n# Lightweight forward static slicing approach\nA very fast and scalable, yet slightly less accurate, slicing approach is extremely useful for a number of reasons.\nDevelopers will have a very low cost and practical means to estimate the impact of a change within minutes versus days.\nThis is very important for planning the implementation of new features and understanding how a change is related to other parts of the system.\nIt will also provide an inexpensive test to determine if a full, more expensive, analysis of the system is warranted.\nA fast slicing approach will open up new avenues of research in metrics and the mining of histories based on slicing.\nThat is, slicing can now be conducted on very large systems and on entire version histories in very practical time frames.\nThis opens the door to a number of experiments and empirical investigations previously too costly to undertake.\n\n# Dynamic slicing\nDynamic slicing makes use of information about a particular execution of a program.\nA dynamic slice contains all statements that actually affect the value of a variable at a program point for a particular execution of the program rather than all statements that may have affected the value of a variable at a program point for any arbitrary execution of the program.\nAn example to clarify the difference between static and dynamic slicing.\nConsider a small piece of a program unit, in which there is an iteration block containing an if-else block.\nThere are a few statements in both the and blocks that have an effect on a variable.\nIn the case of static slicing, since the whole program unit is looked at irrespective of a particular execution of the program, the affected statements in both blocks would be included in the slice.\nBut, in the case of dynamic slicing we consider a particular execution of the program, wherein the block gets executed and the affected statements in the block do not get executed.\nSo, that is why in this particular execution case, the dynamic slice would contain only the statements in the block.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T20:02:51.594Z","updated_at":"2025-01-25T20:02:51.594Z","search_vector":"'program':1 'slice':2","search_content":" \n \n\n# \nIn [computer programming](https://bliptext.com/articles/computer-programming), **program slicing** is the computation of the set of program statements, the **program slice**, that may affect the values at some point of interest, referred to as a **slicing criterion**.\nProgram slicing can be used in [debugging](https://bliptext.com/articles/debugging) to locate source of errors more easily.\nOther applications of slicing include [software maintenance](https://bliptext.com/articles/software-maintenance), [optimization](https://bliptext.com/articles/optimization-computer-science), [program analysis](https://bliptext.com/articles/program-analysis-computer-science), and [information flow control](https://bliptext.com/articles/non-interference-security).\nSlicing techniques have been seeing a rapid development since the original definition by [Mark Weiser](https://bliptext.com/articles/mark-weiser).\nAt first, slicing was only static, i.e., applied on the source code with no other information than the source code.\n[Bogdan Korel](https://bliptext.com/articles/bogdan-korel) and [Janusz Laski](https://bliptext.com/articles/janusz-laski) introduced dynamic slicing, which works on a specific execution of the program (for a given execution trace).\nOther forms of slicing exist, for instance path slicing.\n\n# Static slicing\nBased on the original definition of Weiser, informally, a static program slice S consists of all statements in program P that may affect the value of variable v in a statement x. The slice is defined for a slicing criterion C=(x,v) where x is a statement in program P and v is variable in x. A static slice includes all the statements that can affect the value of variable v at statement x for any possible input.\nStatic slices are computed by backtracking dependencies between statements.\nMore specifically, to compute the static slice for (x,v), we first find all statements that can directly affect the value of v before statement x is encountered.\nRecursively, for each statement y which can affect the value of v in statement x, we compute the slices for all variables z in y that affect the value of v. The union of all those slices is the static slice for (x,v).\n\n## Example\nFor example, consider the C program below.\nLet's compute the slice for ( write(sum), sum ).\nThe value of sum is directly affected by the statements \"sum = sum + i + w\" if N>1 and \"int sum = 0\" if N \n slice( sum = sum + i + w, sum), \n slice( sum = sum + i + w, i), \n slice( sum = sum + i + w, w), and \n { int sum=0 }. \n \nIt is fairly easy to see that slice( sum = sum + i + w, sum) consists of \"sum = sum + i + w\" and \"int sum = 0\" because those are the only two prior statements that can affect the value of sum at \"sum = sum + i + w\".\nSimilarly, slice( sum = sum + i + w, i) only contains \"for(i = 1; i < N; ++i) {\" and slice( sum = sum + i + w, w) only contains the statement \"int w = 7\".\nWhen we union all of those statements, we do not have executable code, so to make the slice an executable slice we merely add the end brace for the for loop and the declaration of i. The resulting static executable slice is shown below the original code below.\nThe static executable slice for criteria (, sum) is the new program shown below.\nIn fact, most static slicing techniques, including Weiser's own technique, will also remove the statement.\nSince, at the statement, the value of is not dependent on the statement itself.\nOften a slice for a particular statement x will include more than one variable.\nIf V is a set of variables in a statement x, then the slice for (x, V) is the union of all slices with criteria (x, v) where v is a variable in the set V.\n\n# Lightweight forward static slicing approach\nA very fast and scalable, yet slightly less accurate, slicing approach is extremely useful for a number of reasons.\nDevelopers will have a very low cost and practical means to estimate the impact of a change within minutes versus days.\nThis is very important for planning the implementation of new features and understanding how a change is related to other parts of the system.\nIt will also provide an inexpensive test to determine if a full, more expensive, analysis of the system is warranted.\nA fast slicing approach will open up new avenues of research in metrics and the mining of histories based on slicing.\nThat is, slicing can now be conducted on very large systems and on entire version histories in very practical time frames.\nThis opens the door to a number of experiments and empirical investigations previously too costly to undertake.\n\n# Dynamic slicing\nDynamic slicing makes use of information about a particular execution of a program.\nA dynamic slice contains all statements that actually affect the value of a variable at a program point for a particular execution of the program rather than all statements that may have affected the value of a variable at a program point for any arbitrary execution of the program.\nAn example to clarify the difference between static and dynamic slicing.\nConsider a small piece of a program unit, in which there is an iteration block containing an if-else block.\nThere are a few statements in both the and blocks that have an effect on a variable.\nIn the case of static slicing, since the whole program unit is looked at irrespective of a particular execution of the program, the affected statements in both blocks would be included in the slice.\nBut, in the case of dynamic slicing we consider a particular execution of the program, wherein the block gets executed and the affected statements in the block do not get executed.\nSo, that is why in this particular execution case, the dynamic slice would contain only the statements in the block.","revisionCount":0},"hasMore":false,"nextCursor":null}

History