A rewriting semantics for program dependence graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A rewriting semantics for program dependence graphs

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Austin, Texas, United States

Pages: 12 - 24

Year of Publication: 1989

ISBN:0-89791-294-2

Author

R. Parsons-Selke

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 13

Additional Information:

abstract cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/75277.75279 What is a DOI?

ABSTRACT

Program dependence graphs are an important program representation technique for use in vectorization, parallelization and programming environments. We present a graph rewriting semantics for program dependence graphs and prove the equivalence between the program dependence graphs semantics and the operational semantics for programs. We then propose a framework for studying program transformations using program dependence graphs and a programming language calculus based on this rewriting semantics.

CITED BY 13

	Hiralal Agrawal, On slicing programs with jump statements, ACM SIGPLAN Notices, v.29 n.6, p.302-312, June 1994
	E. Cartwright , M. Felleisen, The semantics of program dependence, ACM SIGPLAN Notices, v.24 n.7, p.13-27, July 1989
	Ron Cytron , Jeanne Ferrante , V. Sarkar, Compact representations for control dependence, ACM SIGPLAN Notices, v.25 n.6, p.337-351, Jun. 1990
	A. Podgurski , L. Clarke, The implications of program dependencies for software testing, debugging, and maintenance, ACM SIGSOFT Software Engineering Notes, v.14 n.8, p.168-178, Dec. 1989
	Barrett R. Bryant , Daniel T. Chang , Prakash K. Muthukrishnan , Viswanathan Vaidyanathan, Automatic parallelization of object-oriented programming languages using tuple space, Proceedings of the 1995 ACM 23rd annual conference on Computer science, p.89-96, February 28-March 02, 1995, Nashville, Tennessee, United States
	Richard Johnson , Keshav Pingali, Dependence-based program analysis, ACM SIGPLAN Notices, v.28 n.6, p.78-89, June 1993
	B. Simons , D. Alpern , J. Ferrante, A foundation for sequentializing parallel code, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.350-359, July 02-06, 1990, Island of Crete, Greece
	Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, ACM SIGPLAN Notices, v.25 n.6, p.257-271, Jun. 1990
	Roberto Giacobazzi , Isabella Mastroeni, Compositionality in the puzzle of semantics, ACM SIGPLAN Notices, v.37 n.3, p.87-97, March 2002
	J. A. Bergstra , T. B. Dinesh , J. Field , J. Heering, Toward a complete transformational toolkit for compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.5, p.639-684, Sept. 1997
	David Binkley, Computing amorphous program slices using dependence graphs, Proceedings of the 1999 ACM symposium on Applied computing, p.519-525, February 28-March 02, 1999, San Antonio, Texas, United States
	Roberto Giacobazzi , Isabella Mastroeni, Non-Standard Semantics for Program Slicing, Higher-Order and Symbolic Computation, v.16 n.4, p.297-339, December 2003
	A. Podgurski , L. A. Clarke, A Formal Model of Program Dependences and its Implications for Software Testing, Debugging, and Maintenance, IEEE Transactions on Software Engineering, v.16 n.9, p.965-979, September 1990