Browse Prior Art Database

PROGRAM SLICES: FORMAL, PSYCHOLOGICAL, AND PRACTICAL INVESTIGATIONS OF AN AUTOMATIC PROGRAM ABSTRACTION METHOD

IP.com Disclosure Number: IPCOM000128760D
Original Publication Date: 1979-Jan-01
Included in the Prior Art Database: 2005-Sep-19

Publishing Venue

Software Patent Institute

Related People

Weiser, Mark David: AUTHOR [+3]

Abstract

PROGRAM SLICES: FORMAL, PSYCHOLOGICAL, AND PRACTICAL INVESTIGATIONS OF AN AUTOMATIC PROGRAM ABSTRACTION METHOD by Mark David Weiser Co-Chairs: Stephen Kaplan, William Rounds Program slicing is a method used by experienced computer programmers for abstracting from programs. Starting from a subset of a program's behavior, slicing reduces that program to a minimal form which still produces that behavior. The reduced program, called a ";slice";, is an independent program guaranteed to faithfully represent the original program within the domain of the specified subset of behavior. Program slicing is investigated in three ways: (1) formal programming language semantics, (2) cognition in experienced programmers, and (3) slicing real programs.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 3% of the total text.

Page 1 of 69

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

PROGRAM SLICES: FORMAL, PSYCHOLOGICAL, AND PRACTICAL INVESTIGATIONS OF AN AUTOMATIC PROGRAM ABSTRACTION METHOD

by Mark David Weiser

A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Computer and Communication Sciences)in The University of Michigan 1979

Doctoral Committee:

Professor Stephen Kaplan, Co-Chair
Associate Professor William Rounds, Co-Chair Professor Bernard Galler
Associate Professor William Riddle, University of Colorado Associate Professor Arthur Schwartz

ABSTRACT

PROGRAM SLICES: FORMAL, PSYCHOLOGICAL, AND PRACTICAL INVESTIGATIONS OF AN AUTOMATIC PROGRAM ABSTRACTION METHOD

by Mark David Weiser

Co-Chairs: Stephen Kaplan, William Rounds

Program slicing is a method used by experienced computer programmers for abstracting from programs. Starting from a subset of a program's behavior, slicing reduces that program to a minimal form which still produces that behavior. The reduced program, called a "slice", is an independent program guaranteed to faithfully represent the original program within the domain of the specified subset of behavior.

Program slicing is investigated in three ways: (1) formal programming language semantics, (2) cognition in experienced programmers, and (3) slicing real programs.

To formally define slicing, abstract behaviors of programs are investigated within a formal framework similar to program schemes. Finding "statement minimal" slices is then shown to be unsolvable. A new kind of minimality, called "dataflow minimal", is introduced. The dataflow minimal slice permits an algorithmic approximation, using a new graph- theoretic method for precisely determining when a branch node can influence a specified behavior. This method, called "color dominance", is combined with successive levels of dataflow analysis to produce a slice. Slices can be approximated this way in O(n2e) time for a program flowgraph with n nodes and e edges.

Cognition in experienced programmers is placed within a general framework for understanding differences between novices and experts. Based on this framework, the experimental method of algorithmic recognition is introduced to investigate cognition in programmers. This method is used to investigate slicing by programmers during debugging. In addition to verifying the presence of slicing, the experimental results suggest several directions for further investigation.

Author(s) Page 1 Jan 01, 1979

Page 2 of 69

PROGRAM SLICES: FORMAL, PSYCHOLOGICAL, AND PRACTICAL INVESTIGATIONS OF AN AUTOMATIC PROGRAM

ABSTRACTION METHOD

A prototype slicing tool for Fortran programs is constructed and tried on several programs. The resultant slices verify that, depending upon the program and the behavior subset, slices can be significantly smaller than the original program. The issues around construction of a full-scale slicer are reviewed and some design principles suggested. Fin...