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

research-article

Selective CPS transformation for shift and reset

Authors:

Chihiro UeharaAuthors Info & Claims

PEPM '18: Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation

Pages 40 - 52

https://doi.org/10.1145/3162069

Published: 25 December 2017 Publication History

Abstract

This paper presents a selective CPS transformation for a program that uses control operators, shift and reset, introduced by Danvy and Filinski. By selectively CPS-transforming a program, we can execute a program with shift and reset in a standard functional language without support for control operators. We introduce a constraint-based type inference system that annotates the parts that are captured by shift and thus require CPS transformation. We show that the best annotation does not exist in general, and present a constraint solving algorithm that is reasonably efficient. The selective CPS transformation is defined over annotated terms and its correctness is proven. Finally, experimental results show that selective CPS transformation does improve performance compared to the standard CPS transformation.

References

[1]

Asai, K. “On Typing Delimited Continuations: Three New Solutions to the Printf Problem,” Higher-Order and Symbolic Computation, Vol. 22, No. 3, pp. 275–291, Kluwer Academic Publishers (September 2009).

Digital Library

[2]

Asai, K., and Y. Kameyama “Polymorphic Delimited Continuations,” Proceedings of the Fifth Asian Symposium on Programming Languages and Systems, LNCS 4807, pp. 239–254 (November 2007).

Digital Library

[3]

Asai, K., and O. Kiselyov “Introduction to Programming with Shift and Reset,” Tutorial notes on delimited continuations at Continuation Workshop 2011, available from http://pllab.is.ocha.ac. jp/˜asai/cw2011tutorial/main-e.pdf, 14 pages (September 2011).

[4]

Biernacka, M., D. Biernacki, and O. Danvy “An Operational Foundation for Delimited Continuations in the CPS Hierarchy,” Logical Methods in Computer Science, Vol. 1, No. 2:5, pp. 1–39 (November 2005).

[5]

Danvy, O. “Functional Unparsing,” Journal of Functional Programming, Vol. 8, No. 6, pp. 621–625, Cambridge University Press (November 1998).

Digital Library

[6]

Danvy, O., and A. Filinski “A Functional Abstraction of Typed Contexts,” Technical Report 89/12, DIKU, University of Copenhagen ( July 1989).

[7]

Danvy, O., and A. Filinski “Abstracting Control,” Proceedings of the 1990 ACM Conference on Lisp and Functional Programming, pp. 151–160 ( June 1990).

Digital Library

[8]

Danvy, O., and A. Filinski “Representing Control, a Study of the CPS Transformation,” Mathematical Structures in Computer Science, Vol. 2, No. 4, pp. 361–391 (December 1992).

[9]

Danvy, O., and J. Hatcliff “CPS-Transformation After Strictness Analysis,” ACM Letters on Programming Languages and Systems, Vol. 1, No. 3, pp. 195–212 (September 1992).

Digital Library

[10]

Danvy, O., and J. Hatcliff “On the transformation between direct and continuation semantics,” In S. Brookes, M. Main, A. Melton, M. Mislove, and D. Schmidt editors, Mathematical Foundations of Programming Semantics (LNCS 802), pp. 627–648 (April 1993).

Digital Library

[11]

Davis, M., W. Meehan, and O. Shivers “No-Brainer CPS Conversion (Functional Pearl),” Proceedings of the ACM on Programming Languages, Vol. 1, Issue ICFP, Article No. 23, 25 pages (September 2017).

Digital Library

[12]

Dolan, S., L. White, and A. Madhavapeddy “Multicore OCaml,” OCaml Workshop, 2 pages (May 2014).

[13]

Filinski, A. “Representing Monads,” Conference Record of the 21st Annual ACM Symposium on Principles of Programming Languages, pp. 446– 457 ( January 1994).

Digital Library

[14]

Henglein, F. “Efficient Type Inference for Higher-Order Binding-Time Analysis,” In J. Hughes, editor, Functional Programming Languages and Computer Architecture (LNCS 523), pp. 448–472 (August 1991).

Digital Library

[15]

Kameyama, Y., and M. Hasegawa “A Sound and Complete Axiomatization of Delimited Continuations,” Proceedings of the eighth ACM SIGPLAN International Conference on Functional Programming, pp. 177– 188 (August 2003).

Digital Library

[16]

Kim, J., K. Yi, and O. Danvy “Assessing the Overhead of ML Exceptions by Selective CPS Transformation,” Proceedings of the 1998 ACM SIG-PLAN Workshop on ML, pp.103–114 (September 1998). Also in BRICS Research Report RS-98-15, Department of Computer Science, Aarhus University, 34 pages (September 1998).

[17]

Kiselyov, O. “Delimited Control in OCaml, Abstractly and Concretely: System Description,” In M. Blume, N. Kobayashi, and G. Vidal, editors, Functional and Logic Programming (LNCS 6009), pp. 304–320 (April 2010).

Digital Library

[18]

Kobori, I., Y. Kameyama, and O. Kiselyov “Answer-Type Modification without Tears: Prompt-Passing Style Translation for Typed DelimitedControl Operators,” Workshop on Continuations 2015, Electronic Proceedings in Theoretical Computer Science 212, pp. 36–52 (June 2016).

[19]

Lawall, J. L., and O. Danvy “Continuation-Based Partial Evaluation,” Proceedings of the 1994 ACM Conference on Lisp and Functional Programming, pp. 227–238 (June 1994).

Digital Library

[20]

Leijen, D. “Type Directed Compilation of Row-Typed Algebraic Effects,” Proceedings of the 44rd ACM SIGPLAN Symposium on Principles of Programming Languages, pp. 486–499 (January 2017).

Digital Library

[21]

Masuko, M., and K. Asai “Caml Light + shift/reset = Caml Shift,” Theory and Practice of Delimited Continuations, pp. 33–46 (May 2011).

[22]

Materzok, M., D. Biernacki “Subtyping Delimited Continuations,” Proceedings of the 16th ACM SIGPLAN International Conference on Functional Programming, pp. 81–93 (September 2011).

Digital Library

[23]

Nielsen, L. R. “A Selective CPS Transformation,” Electronic Notes in Theoretical Computer Science Vol. 45, pp. 311–331 (November 2001).

[24]

Pretnar, M. “An Introduction to Algebraic Effects and Handlers, Invited Tutorial Paper,” Mathematical Foundations of Programming Semantics, Electronic Notes in Theoretical Computer Science 319, pp. 19–35 (June 2015)

Digital Library

[25]

Reppy, J. “Local CPS Conversion in a Direct-style Compiler,” Proceedings of the third ACM SIGPLAN Workshop on Continuations, pp. 13–22 ( January 2001).

[26]

Rompf, T., I. Maier, and M. Odersky “Implementing First-Class Polymorphic Delimited Continuations by a Type-Directed Selective CPS-Transform,” Proceedings of the 2009 ACM SIGPLAN International Conference on Functional Programming, pp. 317–328 (August 2009).

Digital Library

[27]

Thielecke, H. “From Control Effects to Typed Continuation Passing,” Conference Record of the 30th Annual ACM Symposium on Principles of Programming Languages, pp. 139–149 (January 2003).

Digital Library

[28]

Thiemann, P. J. “Cogen in Six Lines,” Proceedings of the ACM SIGPLAN International Conference on Functional Programming, pp. 180–189 (May 1996).

Digital Library

[29]

Wright, A. K., and M. Felleisen “A Syntactic Approach to Type Soundness,” Information and Computation, Vol. 115, No. 1, pp. 38–94 (November 1994).

Digital Library

Cited By

Lundén DHummelgren LKudlicka JEriksson OBroman D(2024)Suspension Analysis and Selective Continuation-Passing Style for Universal Probabilistic Programming LanguagesProgramming Languages and Systems10.1007/978-3-031-57267-8_12(302-330)Online publication date: 5-Apr-2024
https://doi.org/10.1007/978-3-031-57267-8_12
Cong YAsai K(2023)Understanding Algebraic Effect Handlers via Delimited Control OperatorsTrends in Functional Programming10.1007/978-3-031-21314-4_4(59-79)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-21314-4_4
Im H(2021)On Correspondence between Selective CPS Transformation and Selective Double Negation TranslationMathematics10.3390/math90403859:4(385)Online publication date: 15-Feb-2021
https://doi.org/10.3390/math9040385
Show More Cited By

Index Terms

Selective CPS transformation for shift and reset
1. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Control primitives

Recommendations

Implementing first-class polymorphic delimited continuations by a type-directed selective CPS-transform
ICFP '09: Proceedings of the 14th ACM SIGPLAN international conference on Functional programming

We describe the implementation of first-class polymorphic delimited continuations in the programming language Scala. We use Scala's pluggable typing architecture to implement a simple type and effect system, which discriminates expressions with control ...
Verifying Selective CPS Transformation for Shift and Reset
Trends in Functional Programming
Abstract
A selective CPS transformation enables us to execute a program with delimited control operators, and , in a standard functional language without support for control operators. The selective CPS transformation dispatches not only on the structure ...
Offline partial evaluation for shift and reset
PEPM '04: Proceedings of the 2004 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation

This paper presents an offline partial evaluator for the λ-calculus with the delimited continuation constructs shift and reset. Based on Danvy and Filinski's type system for shift and reset, we first present a type system that specifies well-annotated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM '18: Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation

December 2017

73 pages

ISBN:9781450355872

DOI:10.1145/3175493

Program Chairs:
Fritz Henglein
University of Copenhagen, Denmark
,
Hsiang-Shang Ko
National Institute of Informatics, Japan

Copyright © 2017 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

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 December 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL '18

Sponsor:

SIGPLAN

POPL '18: The 45th Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 8 - 9, 2018

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
214
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)3

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lundén DHummelgren LKudlicka JEriksson OBroman D(2024)Suspension Analysis and Selective Continuation-Passing Style for Universal Probabilistic Programming LanguagesProgramming Languages and Systems10.1007/978-3-031-57267-8_12(302-330)Online publication date: 5-Apr-2024
https://doi.org/10.1007/978-3-031-57267-8_12
Cong YAsai K(2023)Understanding Algebraic Effect Handlers via Delimited Control OperatorsTrends in Functional Programming10.1007/978-3-031-21314-4_4(59-79)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-21314-4_4
Im H(2021)On Correspondence between Selective CPS Transformation and Selective Double Negation TranslationMathematics10.3390/math90403859:4(385)Online publication date: 15-Feb-2021
https://doi.org/10.3390/math9040385
Cong YOsvald LEssertel GRompf T(2019)Compiling with continuations, or without? whatever.Proceedings of the ACM on Programming Languages10.1145/33416433:ICFP(1-28)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341643
Cong YAsai K(2018)Handling delimited continuations with dependent typesProceedings of the ACM on Programming Languages10.1145/32367642:ICFP(1-31)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3236764
Yamada UAsai K(2018)Certifying CPS Transformation of Let-Polymorphic Calculus Using PHOASProgramming Languages and Systems10.1007/978-3-030-02768-1_20(375-393)Online publication date: 22-Oct-2018
https://doi.org/10.1007/978-3-030-02768-1_20

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents