3 ms·

Program slicing

59 points by mhasbini 9y ago

zmonx 9y ago
Very nice, thank you for posting this! Program slicing is especially useful when debugging and reasoning about programs in declarative languages, such as Prolog. In Prolog, it is natural to think in terms of generalizations and specializations of programs, and you can often explain important program properties such as nontermination and failure by showing relevant fragments of clauses. See also failure slicing. In declarative languages, slicing is much more convenient and useful than tracing the execution.
quadcore 9y ago
I think every program should be sliced like this and not doing so is a programming mistake. Of course, Im talking before bottlenecks optimization.
- CogitoCogito 9y ago
  I think this point may be one of the most important in all programming. Taking the example from the wikipedia article (i.e. https://en.wikipedia.org/wiki/Program_slicing#Example https://en.wikipedia.org/wiki/Program_slicing#Example ), I think the correct way to program this is with the sum and product loops separate. The only reason to combine them is if it is a bottleneck as you say. Across a code-base there will be very few places were most time is taken and it is there that these optimizations should occur. Everywhere else it should be separate because that optimizes for code clarity. Always engage in cognitive optimizations first and speed/resource/architecture/etc. optimization second (and even then _only_ if necessary).
arithma 9y ago
I've kind of wanted to formalize this concept ever since I learned about the Static_single_assignment_form used in compilers for optimisation. Programs may be able to benefit greatly from this in terms of refactoring: it's basically separating concerns (from a mechanical point of view.) Separated concerns can open venues for parallelism! https://en.wikipedia.org/wiki/Static_single_assignment_form https://en.wikipedia.org/wiki/Static_single_assignment_form
- theoh 9y ago
  You might find this interesting: http://www.cs.princeton.edu/~appel/papers/ssafun.pdf http://www.cs.princeton.edu/~appel/papers/ssafun.pdf
cdevs 9y ago
I would be interested in a source code scanner that tells you how many functions or lines can modify a variable and show a table of variables/counts. This could be helpful on a new small codebase or checking variables in a specific ugly class that always has scope errors so we can tell our bosses it sucks.
- UncleMeat 9y ago
  Slicing that is sound wrt heaps is often hard, and will contain false positives. Unfortunately in practice developers don't accept fps and get quickly frustrated by these tools unless you are very careful.
userbinator 9y ago
This seems like a technique which a lot of programmers use, without ever hearing the name "program slicing" --- I call it "follow the data flow". It's especially useful when reverse-engineering.
nemo1618 9y ago
Alan Shreve demonstrated a version of this in Go: https://www.youtube.com/watch?v=dSqLt8BgbRQ https://www.youtube.com/watch?v=dSqLt8BgbRQ
andymaule 9y ago
Nice to see interest in this here. Program slicing can also be used for everyday tools too, not just formal verification. I did some research with Microsoft Research trying to show how it can be used to discover which parts of program will be affected, before you make a database schema change. I think program slicing has a lot of potential, and is generally under-appreciated because a lot of the research looks for conservative and safe (i.e. no false positives or negatives) analysis. When you relax this constraint, there are many useful things you can do with slicing. Details on one such example here if anyone is interested: http://www0.cs.ucl.ac.uk/staff/w.emmerich/publications/ICSE2008/schemaChangeICSE08/icse08.pdf http://www0.cs.ucl.ac.uk/staff/w.emmerich/publications/ICSE2...

59 points by mhasbini 9y ago

Very nice, thank you for posting this! Program slicing is especially useful when debugging and reasoning about programs in declarative languages, such as Prolog. In Prolog, it is natural to think in terms of generalizations and specializations of programs, and you can often explain important program properties such as nontermination and failure by showing relevant fragments of clauses. See also failure slicing. In declarative languages, slicing is much more convenient and useful than tracing the execution.

quadcore 9y ago

I think every program should be sliced like this and not doing so is a programming mistake. Of course, Im talking before bottlenecks optimization.

CogitoCogito 9y ago
I think this point may be one of the most important in all programming. Taking the example from the wikipedia article (i.e. https://en.wikipedia.org/wiki/Program_slicing#Example https://en.wikipedia.org/wiki/Program_slicing#Example ), I think the correct way to program this is with the sum and product loops separate. The only reason to combine them is if it is a bottleneck as you say. Across a code-base there will be very few places were most time is taken and it is there that these optimizations should occur. Everywhere else it should be separate because that optimizes for code clarity. Always engage in cognitive optimizations first and speed/resource/architecture/etc. optimization second (and even then _only_ if necessary).

arithma 9y ago

I've kind of wanted to formalize this concept ever since I learned about the Static_single_assignment_form used in compilers for optimisation. Programs may be able to benefit greatly from this in terms of refactoring: it's basically separating concerns (from a mechanical point of view.) Separated concerns can open venues for parallelism! https://en.wikipedia.org/wiki/Static_single_assignment_form https://en.wikipedia.org/wiki/Static_single_assignment_form

theoh 9y ago
You might find this interesting: http://www.cs.princeton.edu/~appel/papers/ssafun.pdf http://www.cs.princeton.edu/~appel/papers/ssafun.pdf

cdevs 9y ago

I would be interested in a source code scanner that tells you how many functions or lines can modify a variable and show a table of variables/counts. This could be helpful on a new small codebase or checking variables in a specific ugly class that always has scope errors so we can tell our bosses it sucks.

UncleMeat 9y ago
Slicing that is sound wrt heaps is often hard, and will contain false positives. Unfortunately in practice developers don't accept fps and get quickly frustrated by these tools unless you are very careful.

userbinator 9y ago

This seems like a technique which a lot of programmers use, without ever hearing the name "program slicing" --- I call it "follow the data flow". It's especially useful when reverse-engineering.

nemo1618 9y ago

Alan Shreve demonstrated a version of this in Go: https://www.youtube.com/watch?v=dSqLt8BgbRQ https://www.youtube.com/watch?v=dSqLt8BgbRQ

andymaule 9y ago

Nice to see interest in this here. Program slicing can also be used for everyday tools too, not just formal verification. I did some research with Microsoft Research trying to show how it can be used to discover which parts of program will be affected, before you make a database schema change. I think program slicing has a lot of potential, and is generally under-appreciated because a lot of the research looks for conservative and safe (i.e. no false positives or negatives) analysis. When you relax this constraint, there are many useful things you can do with slicing. Details on one such example here if anyone is interested: http://www0.cs.ucl.ac.uk/staff/w.emmerich/publications/ICSE2008/schemaChangeICSE08/icse08.pdf http://www0.cs.ucl.ac.uk/staff/w.emmerich/publications/ICSE2...