Article

Free access

Continuation-passing, closure-passing style

Authors:

A. W. Appel,

T. JimAuthors Info & Claims

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

Pages 293 - 302

https://doi.org/10.1145/75277.75303

Published: 03 January 1989 Publication History

PDF eReader

Abstract

We implemented a continuation-passing style (CPS) code generator for ML. Our CPS language is represented as an ML datatype in which all functions are named and most kinds of ill-formed expressions are impossible. We separate the code generation into phases that rewrite this representation into ever-simpler forms. Closures are represented explicitly as records, so that closure strategies can be communicated from one phase to another. No stack is used. Our benchmark data shows that the new method is an improvement over our previous, abstract-machine based code generator.

References

[1]

Andrew W. Appel and David B. Mac- Queen, "A Standard ML compiler," in Functional Programming Languages and Computer Architecture (LNCS 274), pp. 301-324, Springer-Verlag, 1987.

Digital Library

Google Scholar

[2]

Guy L. Steele, "Rabbit: a compiler for Scheme," AI-TR-474, MIT, 1978.

Digital Library

Google Scholar

[3]

D. Kranz, R. Kelsey, J. Rees, P. Hudak, J. Philbin, and N. Adams, "ORBIT: An optimizing compiler for Scheme," Proc. Sigplan '86 Syrup. on Compiler Construction, vol. 21 (Sigplan Notices), no. 7, pp. 219-233, July 1986.

Digital Library

Google Scholar

[4]

David Kranz, "ORBIT: An Optimizing Compiler for Scheme," PhD Thesis, Yale University, 1987.

Digital Library

Google Scholar

[5]

Andrew W. Appel, Christopher W. Fraser, David R. Hanson, and Arthur H. Watson, "Generating code for the Case statement," in preparation.

Google Scholar

[6]

V. Vyssotsky and P. Wegner, A graph theoretical Fortran source language analyzer, AT&T Bell Laboratories, Murray Hill, NJ, 1963.

Google Scholar

[7]

G. Cousineau, P. L. Curien, and M. Mauny, "The Categorical Abstract Machine," in Functional Programming Languages and Computer Architecture, LNCS Vol 201, ed. J. P. Jouannaud, pp. 50-64, Springer- Verlag, 1985.

Digital Library

Google Scholar

[8]

Andrew W. Appel and Trevor Jim, "Optimizing closure environment representations," CS-TR- 168-88, Princeton University, 1988.

Google Scholar

[9]

David Ungar, "Generation scavenging: a non-disruptive high performance storage reclamation algorithm," SIGPLAN Notices (Proc. ACM SIGSOFTISIGPLAN Software Eng. Syrup. on Practical Software Development Environments), vol. 19, no. 5, pp. 157-167, ACM, 1984.

Digital Library

Google Scholar

[10]

A.W. Appel, "Garbage collection can be faster than stack allocation," Information Processing Letters, vol. 25, no. 4, pp. 275- 279, 1987.

Digital Library

Google Scholar

[11]

David R. Chase, "Safety considerations for storage allocation optimizations," SIG- PLAN '88 Conf. on Prog. Lang. Design and Implementation, pp. 1-10, ACM, 1988.

Digital Library

Google Scholar

Cited By

View all

Downen P(2024)Call-by-Unboxed-ValueProceedings of the ACM on Programming Languages10.1145/36746548:ICFP(845-879)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674654
Mason D(2023)Threaded Execution as a Dual to Native CodeCompanion Proceedings of the 7th International Conference on the Art, Science, and Engineering of Programming10.1145/3594671.3594673(7-11)Online publication date: 13-Mar-2023
https://dl.acm.org/doi/10.1145/3594671.3594673
Shishkin EKislitsyn E(2021)SafeComp: Protocol for Certifying Cloud Computations IntegrityProgramming and Computer Software10.1134/S036176882108005347:8(871-881)Online publication date: 28-Dec-2021
https://doi.org/10.1134/S0361768821080053
Show More Cited By

Index Terms

Continuation-passing, closure-passing style
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation
  1. Semantics and reasoning
    1. Program semantics

Recommendations

Reasoning about programs in continuation-passing style.

Plotkin's λ-value calculus is sound but incomplete for reasoning about βeegr;-transformations on programs in continuation-passing style (CPS). To find a complete extension, we define a new, compactifying CPS transformation and an “inverse”mapping, un-...
Reasoning about programs in continuation-passing style.
LFP '92: Proceedings of the 1992 ACM conference on LISP and functional programming

Plotkin's λ-value calculus is sound but incomplete for reasoning about βeegr;-transformations on programs in continuation-passing style (CPS). To find a complete extension, we define a new, compactifying CPS transformation and an “inverse”mapping, un-...
Reasoning about programs in continuation-passing style
Special issue on continuations—part I

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

110
Total Citations
View Citations
1,721
Total Downloads

Downloads (Last 12 months)246
Downloads (Last 6 weeks)36

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Downen P(2024)Call-by-Unboxed-ValueProceedings of the ACM on Programming Languages10.1145/36746548:ICFP(845-879)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674654
Mason D(2023)Threaded Execution as a Dual to Native CodeCompanion Proceedings of the 7th International Conference on the Art, Science, and Engineering of Programming10.1145/3594671.3594673(7-11)Online publication date: 13-Mar-2023
https://dl.acm.org/doi/10.1145/3594671.3594673
Shishkin EKislitsyn E(2021)SafeComp: Protocol for Certifying Cloud Computations IntegrityProgramming and Computer Software10.1134/S036176882108005347:8(871-881)Online publication date: 28-Dec-2021
https://doi.org/10.1134/S0361768821080053
Farvardin KReppy J(2020)A New Backend for Standard ML of New JerseyProceedings of the 32nd Symposium on Implementation and Application of Functional Languages10.1145/3462172.3462191(55-66)Online publication date: 2-Sep-2020
https://dl.acm.org/doi/10.1145/3462172.3462191
MacQueen DHarper RReppy J(2020)The history of Standard MLProceedings of the ACM on Programming Languages10.1145/33863364:HOPL(1-100)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3386336
Farvardin KReppy JDonaldson ATorlak E(2020)From folklore to fact: comparing implementations of stacks and continuationsProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3385994(75-90)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3385994
Heller TLelbach BHuck KBiddiscombe JGrubel PKoniges AKretz MMarcello DPfander DSerio AFrank JClayton GPflüger DEder DKaiser H(2019)Harnessing billions of tasks for a scalable portable hydrodynamic simulation of the merger of two starsThe International Journal of High Performance Computing Applications10.1177/1094342018819744(109434201881974)Online publication date: 14-Feb-2019
https://doi.org/10.1177/1094342018819744
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
Blelloch GGibbons PGu YMcGuffey CShun JScheideler CFineman J(2018)The Parallel Persistent Memory ModelProceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures10.1145/3210377.3210381(247-258)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3210377.3210381
Zhai EPiskac RGu RLao XWang X(2017)An auditing language for preventing correlated failures in the cloudProceedings of the ACM on Programming Languages10.1145/31339211:OOPSLA(1-28)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133921
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

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

Reasoning about programs in continuation-passing style.

Reasoning about programs in continuation-passing style.

Reasoning about programs in continuation-passing style