More Web Proxy on the site http://driver.im/

Article

Free access

Program improvement by source to source transformation

Author:

David B. LovemanAuthors Info & Claims

POPL '76: Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages

Pages 140 - 152

https://doi.org/10.1145/800168.811548

Published: 01 January 1976 Publication History

Abstract

We treat a program as an object of manipulation, determine items of program constancy, and simplify the program based on the constancy. Some motivation for program manipulation is presented, along with two examples of “higher level optimization” written in an Algol-like language. A collection of program transformations and a model of the compilation process in terms of source-to-source transformations are presented. Finally a description of the application of these ideas to an existing programming language is given.

References

[1]

Abrams, Philip: {APL}, "An APL Machine", Stanford Electronics Laboratory, SU-SEL-70-017, February 1970.]]

[2]

ACM Sigplan: {Languages}, Symposium on Very High Level Languages, Sigplan Notices, 9, 4 April 1974.]]

[3]

ACM Sigplan: {Optimization}, Proceedings of a Symposium on Compiler Optimization, Sigplan Notices, July 1970.]]

[4]

Allen, Frances E. and Cocke, John: {Catalogue}, "A Catalogue of Optimizing Transformations", in R. Rustin (Ed.) Design and Optimization of Compilers, Prentice-Hall 1972.]]

[5]

Bearisto, David and Sattley, Kirk: {Laboratory}, "BETA Laboratory", Final Report, Mass. Computer Associates, Inc., CADD-7312-3111, December 31, 1973.]]

[6]

Beckman, Lenhart et al: {Evaluator}, "A Partial Evaluator and its use as a Programming Tool", Dept. of Computer Sciences, Uppsala University, Sweden, November 1974.]]

[7]

Burstall, R.M. and Darlington, J.: {Transformations}, "Some Transformations for Developing Recursive Programs", Int. Conf. on Reliable Software, IEEE Computer Society, April 1975, 465-472.]]

Digital Library

[8]

Cheatham, T. E.: {Evaluator}, "EL1 Symbolic Evaluator-Design Notes", working paper.]]

[9]

Cheatham, T. E. and Wegbreit, Ben: {Laboratory}, "A Laboratory for the Study of Automatic Programming", AFIPS Conf. Proc., Vol. 70, Spring 1972.]]

Digital Library

[10]

Gerhart, S. L.: {Transformations}, "Correctness Preserving Program Transformations ", Second ACM Symposium on Principles of Programming Languages, January 1975.]]

Digital Library

[11]

Geschke, Charles M.: {Optimization}, "Global Program Optimizations", Ph. D Thesis, Computer Science Department, Carnegie-Mellon University, Pittsburgh, Pennsylvania, 1972.]]

Digital Library

[12]

Hoare, C. A. R.: {Hints}, "Hints on Programming Language Design", Computer Science Department, Stanford University, STAN-CS-73-403, December 1973.]]

Digital Library

[13]

Karr, Michael: {Information}, "Gathering Information About Programs", Mass. Computer Associates, Inc., CA-7507-1411, July 14, 1975.]]

[14]

Karr, Michael: {Assignment}, "The Assignment of Scalar Variables to Memory Cells", Mass. Computer Associates, Inc., CAID-7501-0611, January 1975.]]

[15]

Karr, Michael: {Inequalities}, "Proving Inequalities", Mass. Computer Associates, Inc., CA-7406-1011, June 1974. Submitted for publication.]]

[16]

Karr, Michael: {Affine}, "Affine Relationships Among Variables of a Program", Mass. Computer Associates, Inc., CA-7402-2811, June 1974. Accepted for publication by Acta Informatica.]]

[17]

Knuth, Donald: {Go To}, "Structured Programming with go to Statements ", Computing Surveys, Vol. 6, No. 4, December 1974.]]

Digital Library

[18]

Lamport, Leslie: {Parallel}, "Parallel Execution on Array and Vector Computers ", Proceedings of the 1975 Sagamore Conference on Parallel Processing, August 1975.]]

[19]

Lamport, Leslie: {Hyperplane}, "The Hyperplane Method for an Array Computer", Proceedings of the 1974 Sagamore Conference on Parallel Processing, August 1974.]]

Digital Library

[20]

Lamport, Leslie: {Loops}, "The Parallel Execution of DO Loops", Comm. ACM 17, 2, February 1974.]]

Digital Library

[21]

Lamport, Leslie: {Coordinate}, "The Coordinate Method for the Parallel Execution of DO Loops", Proceedings of the 1973 Sagamore Conference on Parallel Processing, August 1973.]]

[22]

Loveman, David: {Transformation}, "Source-to-Source Transformation of Programs", in preparation.]]

[23]

Loveman, David, Bearisto, David, Karr, Michael and Sattley, Kirk: {Development 1975}, "Development of Compiler Optimization Techniques", Mass. Computer Associates, Inc., CADD-7508-3111, August 31, 1975.]]

[24]

Loveman, David and Faneuf, Ross: {Optimization}, "Program Optimization-Theory and Practice", Proceedings of a Conference on Programming Languages and Compilers for Parallel and Vector Machines, Sigplan Notices, Vol. 10, No. 3, March 1975.]]

Digital Library

[25]

Loveman, David: {K in a Row}, "The 'K in a Row' Problem ", Mass. Computer Associates, Inc., CADD-7412-0411, December 4, 1974.]]

[26]

Loveman, David, Sattley, Kirk and Bearisto, David: {Development 1974}, "Development of Compiler Optimization Techniques", Mass. Computer Associates, Inc., CADD-7407-2311, July 1974.]]

[27]

Loveman, David: {Replacement}, "On the Compilation of the Beta Replacement Statement", Mass. Computer Associates, Inc., CADD-7308-0911, August 9, 1973.]]

[28]

Presberg, David and Johnson, Neil: {Paralyzer}, "The Paralyzer, IVTRAN's Parallelism Analyzer and Synthesizer", Proceedings of a Conference on Programming Languages and Compilers for Parallel and Vector Machines, Sigplan Notices, Vol. 10, No. 3, March 1975.]]

Digital Library

[29]

Saint, Harry: {Ordering}, "The Partial Ordering of Loops and Array References", Mass. Computer Associates, Inc., CADD-7312-3112, December 31, 1973.]]

[30]

Schaefer, Marvin:{Optimization}, A Mathematical Theory of Global Program Optimization, Prentice-Hall, 1973.]]

Digital Library

[31]

Shapiro, Robert M. and Saint, Harry: {Algorithms}, "The Representation of Algorithms", Applied Data Research, Inc., Final Technical Report. RADC-TR-69-313, Vol. II, Rome Air Development Center, September 1969.]]

[32]

Wegbreit, Ben: {Analysis}, "Mechanical Program Analysis", Comm. ACM 18, 9, September 1975.]]

Digital Library

[33]

Wegbreit, Ben: {Extraction}, "Property Extraction in Well-Founded Property Sets ", IEEE Transactions on Software Engineering, Vol. SE-1, No. 3, September 1975.]]

Digital Library

[34]

Wegbreit, Ben: {Transformation}, "Goal-Directed Program Transformation", Xerox Palo Alto Research Center, September 1975.]]

[35]

Wegbreit, Ben: {Predicates}, "The Synthesis of Loop Predicates", Comm. ACM 17, 2, Feb. 1974.]]

Digital Library

[36]

Wegbreit, Ben: {Closure}, "Procedure Closure in EL1", The Computer Journal, Vol. 17, No. 1, February 1974.]]

[37]

Wegbreit, Ben: {ECL}, "The ECL Programming System", Proc. FJCC, Vol. 39, pp.253-262, 1971.]]

[38]

Wulf, W.A., Russell, D.B. and Habermann, A. N.: {BLISS}, "BLISS:A Language for Systems Programming", Comm. ACM 14, 12, December 1971, 780-790.]]

Digital Library

Cited By

Honda KVasconcelos VYoshida N(2009)Type-Directed Compilation for Multicore ProgrammingElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2009.06.006241(101-111)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1016/j.entcs.2009.06.006
Erez MAhn JGummaraju JRosenblum MDally WSmith B(2007)Executing irregular scientific applications on stream architecturesProceedings of the 21st annual international conference on Supercomputing10.1145/1274971.1274987(93-104)Online publication date: 17-Jun-2007
https://dl.acm.org/doi/10.1145/1274971.1274987
Wen MWu NXun CWu WZhang C(2006)Analysis and Performance Results of a fluid dynamics Application on MASA Stream ProcessorProceedings of the 5th IEEE/ACIS International Conference on Computer and Information Science and 1st IEEE/ACIS International Workshop on Component-Based Software Engineering,Software Architecture and Reuse10.1109/ICIS-COMSAR.2006.21(350-354)Online publication date: 10-Jul-2006
https://dl.acm.org/doi/10.1109/ICIS-COMSAR.2006.21
Show More Cited By

Index Terms

Program improvement by source to source transformation
1. Social and professional topics
  1. Professional topics
    1. Management of computing and information systems
      1. Software management
        Software maintenance
2. Software and its engineering
  1. Software creation and management
    1. Software post-development issues
  2. Software notations and tools
    1. Compilers

Recommendations

Program Improvement by Source-to-Source Transformation

The use of source-to-source program transformations has proved valuable in improving program performance. The concept of program manipulation is elucidated by describing its role in both conventional optimization and high level modification of ...
Language Design for Program Manipulation

The design of procedural and object-oriented programming languages is considered with respect to how easily programs written in those languages can be formally manipulated. Current procedural languages such as Pascal, Modula-2 and Ada; generally support ...
Source-to-Source Compilation via Submodules
ELS2016: Proceedings of the 9th European Lisp Symposium on European Lisp Symposium

Racket's macro system enables language extension and definition primarily for programs that are run on the Racket virtual machine, but macro facilities are also useful for implementing languages and compilers that target different platforms. Even when ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '76: Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages

January 1976

224 pages

ISBN:9781450374774

DOI:10.1145/800168

Copyright © 1976 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1976

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

POPL '76 Paper Acceptance Rate 20 of 90 submissions, 22%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
473
Total Downloads

Downloads (Last 12 months)72
Downloads (Last 6 weeks)16

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Honda KVasconcelos VYoshida N(2009)Type-Directed Compilation for Multicore ProgrammingElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2009.06.006241(101-111)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1016/j.entcs.2009.06.006
Erez MAhn JGummaraju JRosenblum MDally WSmith B(2007)Executing irregular scientific applications on stream architecturesProceedings of the 21st annual international conference on Supercomputing10.1145/1274971.1274987(93-104)Online publication date: 17-Jun-2007
https://dl.acm.org/doi/10.1145/1274971.1274987
Wen MWu NXun CWu WZhang C(2006)Analysis and Performance Results of a fluid dynamics Application on MASA Stream ProcessorProceedings of the 5th IEEE/ACIS International Conference on Computer and Information Science and 1st IEEE/ACIS International Workshop on Component-Based Software Engineering,Software Architecture and Reuse10.1109/ICIS-COMSAR.2006.21(350-354)Online publication date: 10-Jul-2006
https://dl.acm.org/doi/10.1109/ICIS-COMSAR.2006.21
Azeemi N(2005)Power Aware Framework for Dense Matrix Operations in Multimedia Processors2005 Pakistan Section Multitopic Conference10.1109/INMIC.2005.334414(1-6)Online publication date: Dec-2005
https://doi.org/10.1109/INMIC.2005.334414
Zafar NRupp M(2005)Energy-Aware Source-to-Source Transformations for a VLIW DSP Processor2005 International Conference on Microelectronics10.1109/ICM.2005.1590054(133-138)Online publication date: 2005
https://doi.org/10.1109/ICM.2005.1590054
Nagl M(2005)Graph rewriting and automatic, machine-independent program optimizationGraphtheoretic Concepts in Computer Science10.1007/3-540-10291-4_5(55-69)Online publication date: 25-May-2005
https://doi.org/10.1007/3-540-10291-4_5
Ning PCui YReeves DXu D(2004)Techniques and tools for analyzing intrusion alertsACM Transactions on Information and System Security10.1145/996943.9969477:2(274-318)Online publication date: 1-May-2004
https://dl.acm.org/doi/10.1145/996943.996947
Iwayama MFujii AKando NTakano A(2004)Report on the patent retrieval task at NTCIR workshop 3ACM SIGIR Forum10.1145/986278.98628238:1(22-24)Online publication date: 1-Jul-2004
https://dl.acm.org/doi/10.1145/986278.986282
Erez MAhn JGarg ADally WDarve EHuskamp J(2004)Analysis and Performance Results of a Molecular Modeling Application on MerrimacProceedings of the 2004 ACM/IEEE conference on Supercomputing10.1109/SC.2004.69Online publication date: 6-Nov-2004
https://dl.acm.org/doi/10.1109/SC.2004.69
Delic KDayal U(2002)The rise of the intelligent enterpriseUbiquity10.1145/764008.7640092002:December(1)Online publication date: 1-Dec-2002
https://dl.acm.org/doi/10.1145/764008.764009
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents