program slicing (was Re: random software speculations)

[Bradley M. Kuhn]

Kragen Sitaker wrote:

[..lots of stuff about program slicing deleted...]

> This same kind of analysis can be used to follow the effects of a variable
> assignment or initialization downstream.  (Brad, wc?  Tell us more!)

I assume you are talking about the DSDS that I wrote in college.  This was
based on the PhD thesis of one of the faculty at my undergrad institution
(Keith Gallagher: http://www.cs.loyola.edu/~kbg).

What you are talking about is all stuff that has been researched heavily.
Look into program slicing, and how it can be used for software engineering.

There is a group at Wisconsin-Madison lead by Reps and Horawitz doing a lot
of work in this area.  There is a group at NIST doing work in this area, as
well.  I am sure there are others but a lot of key research comes out of
there.

Decomposition slicing (invented by Keith Gallagher) seemed to me when I was
reading the literature to be the only piece of work directly applied to do
doing the kind of things you are talking about with program slicing.

I don't know the state of kbg's slicing tool.  His tool is described at
http://www.cs.loyola.edu/~kbg/Surgeon/

In 1995, the only thing it had ever sliced was the wc(1) program.  I don't
know if anything else has ever been sliced.  :)

I tried to talk him into releasing it as free software once, and he scoffed
at me because he feared people in the proprietary software realm would do
bad things.  I didn't understand the GPL well enough at the time to make the
canonical argument.

Kragen, if you are interested in this, I can contact him again and ask him
to do so.  Let me know.

(I could release the DSDS as free software, as I own the copyright on most
 of it; however, it's useless without the Surgeon's Assistant's output.)
 

> - what basic blocks pass control to what other basic blocks
> - what statements or expressions change the values of what variables
> - what statements or expressions get aliases to what variables, and where
>   they put them

Most slicing tools get this information by building a PDG and getting
def-use edge information.

Aliasing is the hard problem.

> Why Doesn't Somebody modify gcc to output this information?  It has to
> compute most of it anyway.

Another faculty member from where I went undergraduate, David Binkley
(http://www.cs.loyola.edu/~binkley), was working on just that at one point.
I don't know how far he got.  If you are interested, I could ask him.
 

> [0] Look Brad, no killfile!

Well, you should've kill-filed yourself.  :)  Using a curse word in a post.
ecommitt would have had you for lunch. :0

-- 
         -  bkuhn@ebb.org  -  Bradley M. Kuhn  -  bkuhn@gnu.org  -
                          http://www.ebb.org/bkuhn