Article

Free access

Realistic compilation by program transformation (detailed summary)

Authors:

R. Kelsey,

P. HudakAuthors Info & Claims

POPL '89: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 281 - 292

https://doi.org/10.1145/75277.75302

Published: 03 January 1989 Publication History

PDF eReader

Abstract

Using concepts from denotational semantics, we have produced a very simple compiler that can be used to compile standard programming languages and produces object code as efficient as that of production compilers. The compiler is based entirely on source-to-source transformations performed on programs that have been translated into an intermediate language resembling the lambda calculus. The output of the compiler, while still in the intermediate language, can be trivially translated into machine code for the target machine. The compilation by transformation strategy is simple: the goal is to remove any dependencies on the intermediate language semantics that the target machine cannot implement directly. Front-ends have been written for Pascal, BASIC, and Scheme and the compiler produces code for the MC68020 microprocessor.

References

[1]

James M. Boyle and Monagur N. Muralidharan. Program reusability through program transformation. in IEEE Transactions on, Software Engineering SE- 10(5):574-588, September 1984.

Digital Library

Google Scholar

[2]

James M. Boyle, Kenneth W. Dritz, M .N. Muralidharan, and Robert J. Taylor. Deriving sequential and parallel programs from pure Lisp Specifications by program transformation. in IFIP WGP.1 Working Conference on Programme Specifications and Transformations.

Digital Library

Google Scholar

[3]

Brooks, R.A., Gabriel, R.P. and Steele, G.J. Jr. An optimizing compiler for lexically scoped LISP. in Proceedings of the SIGPLAN Symposium on Compiler Construction, ACM, SIGPLAN Notices 17(6)~ June 1982.

Digital Library

Google Scholar

[4]

M. Feeley and G. Lapalme. Closure generation based on viewing LAMBDA as EPSILON plus COMPILE. D~partement d'informatique et de recherche op~rationnelle (I.R.O.), Universit~ de MontrSal, P.O.B. 6128, Station A, Montreal, QuSbec, H3C3J7 (Canada).

Google Scholar

[5]

Thomas Johnsson. Lambda lifting: Transforming programs into recursire equations. In Compiling Lazy Functional Languages. PhD thesis, Chalmers University of Technology, 1987

Google Scholar

[6]

Richard Kelsey. Compilation by Program Transformation. PhD thesis, Yale University, 1989.

Digital Library

Google Scholar

[7]

Kranz D.A., Kelsey, R., Rees J.A., Hudak P., Philbin, J. and Adams, N.I. Orbit: An optimizing compiler for Scheme. In Proceedings of the SIGPLAN '86 Symposium on Compiler Construction, ACM, SIGPLAN Notices 21(7), June 1986.

Digital Library

Google Scholar

[8]

Peter Lee. The Automatic Generation of Realistic Compilers from High-level Semantics Descriptions. PhD tlhesis, University of Michigan, 1987.

Digital Library

Google Scholar

[9]

Lawrence Paulson. A semantics-directed compiler generator. in Converenee Record of the Ninth Annual ACM Symposium on Principles of Programming Languages, ACM, 1982.

Digital Library

Google Scholar

[10]

G. D. Plotkin. Call-by-name, call-by-value and the A-calcuhs. in Theoretical Computer Science 1:125-159, 1975.

Crossref

Google Scholar

[11]

Jonathan A. Rees, Norman I. Adams, and James R. Meehan. The T manual, fourth edition. Yale University Computer Science Department, January 1984.

Google Scholar

[12]

T. A. Standish, D. C. harriman, D. F. Kibler, and J. M. Neighbors. The Irvine program transformation catalogue Department of Information and Computer Science, University of California at Irvine, 1976.

Google Scholar

[13]

Guy L. Steele Jr. Rabbit: a compiler for Scheme. MIT Artificial Intelligence Laboratory Technical Report 474, May 1978.

Digital Library

Google Scholar

Cited By

View all

Paraskevopoulou ZLi JAppel A(2021)Compositional optimizations for CertiCoqProceedings of the ACM on Programming Languages10.1145/34735915:ICFP(1-30)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473591
Clinger WWand M(2020)Hygienic macro technologyProceedings of the ACM on Programming Languages10.1145/33863304:HOPL(1-110)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3386330
Paraskevopoulou ZAppel A(2019)Closure conversion is safe for spaceProceedings of the ACM on Programming Languages10.1145/33416873:ICFP(1-29)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341687
Show More Cited By

Index Terms

Realistic compilation by program transformation (detailed summary)
1. Software and its engineering
  1. Software creation and management
    1. Designing software
      1. Software implementation planning
        Software design techniques
    2. Software development process management
  2. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
      2. Language types
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Functional constructs

Recommendations

Compilation by program transformation
Realistic compilation by partial evaluation

Two key steps in the compilation of strict functional languages are the conversion of higher-order functions to data structures (closures) and the transformation to tail-recursive style. We show how to perform both steps at once by applying first-order ...
Static and Dynamic Program Compilation by Interpreter Specialization

Interpretation and run-time compilation techniques are increasingly important because they can support heterogeneous architectures, evolving programming languages, and dynamically-loaded code. Interpretation is simple to implement, but yields poor ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

POPL '89: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 1989

352 pages

ISBN:0897912942

DOI:10.1145/75277

Editor:
CORPORATE New York, NY Association for Computing Machinery

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 January 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL89

Sponsor:

POPL89: Symposium on the Principles of Programming Languages

January 11 - 13, 1989

Texas, Austin, USA

Acceptance Rates

POPL '89 Paper Acceptance Rate 30 of 191 submissions, 16%;

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

59
Total Citations
View Citations
712
Total Downloads

Downloads (Last 12 months)109
Downloads (Last 6 weeks)13

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Paraskevopoulou ZLi JAppel A(2021)Compositional optimizations for CertiCoqProceedings of the ACM on Programming Languages10.1145/34735915:ICFP(1-30)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473591
Clinger WWand M(2020)Hygienic macro technologyProceedings of the ACM on Programming Languages10.1145/33863304:HOPL(1-110)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3386330
Paraskevopoulou ZAppel A(2019)Closure conversion is safe for spaceProceedings of the ACM on Programming Languages10.1145/33416873:ICFP(1-29)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341687
Morazán MReams LOlson NDzhatdoyev S(2018)Memoized Flat Closures for CPSTrends in Functional Programming10.1007/978-3-319-89719-6_1(1-18)Online publication date: 19-Apr-2018
https://doi.org/10.1007/978-3-319-89719-6_1
Davis MMeehan WShivers O(2017)No-brainer CPS conversion (functional pearl)Proceedings of the ACM on Programming Languages10.1145/31102671:ICFP(1-25)Online publication date: 29-Aug-2017
https://dl.acm.org/doi/10.1145/3110267
Kiselyov OBiboudis APalladinos NSmaragdakis Y(2017)Stream fusion, to completenessACM SIGPLAN Notices10.1145/3093333.300988052:1(285-299)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3093333.3009880
Kiselyov OBiboudis APalladinos NSmaragdakis YCastagna GGordon A(2017)Stream fusion, to completenessProceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages10.1145/3009837.3009880(285-299)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3009837.3009880
Rompf TSujeeth AAmin NBrown KJovanovic VLee HJonnalagedda MOlukotun KOdersky M(2013)Optimizing data structures in high-level programsACM SIGPLAN Notices10.1145/2480359.242912848:1(497-510)Online publication date: 23-Jan-2013
https://dl.acm.org/doi/10.1145/2480359.2429128
Rompf TSujeeth AAmin NBrown KJovanovic VLee HJonnalagedda MOlukotun KOdersky MGiacobazzi RCousot R(2013)Optimizing data structures in high-level programsProceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/2429069.2429128(497-510)Online publication date: 23-Jan-2013
https://dl.acm.org/doi/10.1145/2429069.2429128
Budiu MGalenson JPlotkin G(2013)The compiler forestProceedings of the 22nd European conference on Programming Languages and Systems10.1007/978-3-642-37036-6_2(21-40)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1007/978-3-642-37036-6_2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Compilation by program transformation

Realistic compilation by partial evaluation

Static and Dynamic Program Compilation by Interpreter Specialization