research-article

Implementing first-class polymorphic delimited continuations by a type-directed selective CPS-transform

Authors:

Martin OderskyAuthors Info & Claims

ICFP '09: Proceedings of the 14th ACM SIGPLAN international conference on Functional programming

Pages 317 - 328

https://doi.org/10.1145/1596550.1596596

Published: 31 August 2009 Publication History

Abstract

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 effects from those without and accurately tracks answer type modification incurred by control effects. To tackle the problem of implementing first-class continuations under the adverse conditions brought upon by the Java VM, we employ a selective CPS transform, which is driven entirely by effect-annotated types and leaves pure code in direct style. Benchmarks indicate that this high-level approach performs competitively.

Supplementary Material

JPG File (implementingfirst-classpolymorphicdelimitedcontinuationsbya.jpg)

Download
17.23 KB

MP4 File (implementingfirst-classpolymorphicdelimitedcontinuationsbya.mp4)

Download
85.03 MB

References

[1]

Agha, Gul, and Carl Hewitt. 1987. Concurrent programming using actors. In Object-oriented concurrent programming, 37--53. MIT Press, Cambridge, MA, USA.

Digital Library

[2]

Appel, Andrew W. 1992. Compiling with continuations. Cambridge University Press, New York, NY, USA.

Digital Library

[3]

Appel, Andrew W., and Trevor Jim. 1989. Continuation-passing, closurepassing style. In Proc. POPL'89, 293--302.

Digital Library

[4]

Asai, Kenichi. 2007. On typing delimited continuations: Three new solutions to the printf problem. Tech. Rep. OCHA-IS 07-1, Department of Information Science, Ochanomizu University, Tokyo, Japan. Available from: http://pllab.is.ocha.ac.jp/~asai/papers/.

[5]

Asai, Kenichi, and Yukiyoshi Kameyama. 2007. Polymorphic delimited continuations. In Proc. APLAS'07, vol. 4807 of LNCS, 91--108.

Digital Library

[6]

Atkey, Robert. 2006. Parameterised notions of computation. In Proc. MSFP'06, 31--45. Electronic Workshops in Computing, British Computer Society.

Digital Library

[7]

Balat, Vincent, and Olivier Danvy. 1997. Strong normalization by run-time code generation. Tech. Rep. BRICS RS-97-43, Department of Computer Science, University of Aarhus, Denmark.

[8]

Biernacki, Dariusz, Olivier Danvy, and Chung-chieh Shan. 2006. On the static and dynamic extents of delimited continuations. Science of Computer Programming 60(3):274--297.

Digital Library

[9]

Clinger, William D., Anne H. Hartheimer, and Eric M. Ost. 1999. Implementation Strategies for First-Class Continuations. Higher-Order and Symbolic Computation 12(1):7--45.

Digital Library

[10]

Cooper, Gregory H., and Shriram Krishnamurthi. 2006. Embedding dynamic dataflow in a call-by-value language. In Proc. ESOP'06, 294--308.

Digital Library

[11]

Courtney, Antony, Henrik Nilsson, and John Peterson. 2003. The Yampa arcade. In Proc. ACM SIGPLAN workshop on Haskell, 7--18.

Digital Library

[12]

Danvy, Olivier. 1998. Functional unparsing. J. Funct. Program. 8(06):621--625.

Digital Library

[13]

Danvy, Olivier, and Andrzej Filinski. 1989. A Functional Abstraction of Typed Contexts. Tech. Rep., DIKU University of Copenhagen, Denmark.

[14]

---. 1990. Abstracting control. In Proc. LFP'90, 151--160.

Digital Library

[15]

---. 1992. Representing Control: A Study of the CPS Transformation. Mathematical Structures in Computer Science 2(4):361--391.

[16]

Danvy, Olivier, Kevin Millikin, and Lasse R. Nielsen. 2007. On one-pass CPS transformations. J. Funct. Program. 17(6):793--812.

Digital Library

[17]

Dragos, Iulian, Antonio Cunei, and Jan Vitek. 2007. Continuations in the Java Virtual Machine. In Proc. ICOOOLPS'07.

[18]

Dyvbig, R. Kent, Simon Peyton-Jones, and Amr Sabry. 2007. A monadic framework for delimited continuations. J. Funct. Program. 17(6):687--730.

Digital Library

[19]

Elliott, Conal, and Paul Hudak. 1997. Functional reactive animation. In Proc. ICFP'97.

Digital Library

[20]

Felleisen, Matthias. 1991. On the expressive power of programming languages. Science of Computer Programming 17(1-3):35--75.

Digital Library

[21]

Felleisen, Matthias, Mitch Wand, Daniel Friedman, and Bruce Duba. 1988. Abstract continuations: a mathematical semantics for handling full jumps. In Proc. LFP'88, 52--62.

Digital Library

[22]

Felleisen, Mattias. 1988. The theory and practice of first-class prompts. In Proc. POPL-88, 180--190.

Digital Library

[23]

Filinski, Andrzej. 1994. Representing monads. In Proc. POPL'94, 446--457.

Digital Library

[24]

---. 1999. Representing layered monads. In Proc. POPL'99, 175--188.

Digital Library

[25]

Flanagan, Cormac, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. 1993. The essence of compiling with continuations. In Proc. PLDI'93, vol. 28(6), 237--247.

Digital Library

[26]

Fournet, Cedric, and Georges Gonthier. 1996. The reflexive CHAM and the join-calculus. In Proc. POPL'96, 372--385.

Digital Library

[27]

Gabriel, Richard P. 1991. The design of parallel programming languages. In Artificial intelligence and mathematical theory of computation: papers in honor of john mccarthy, 91--108. Academic Press Professional, San Diego, CA, USA.

Digital Library

[28]

Gasbichler, Martin, and Michael Sperber. 2002. Final shift for call/cc:: direct implementation of shift and reset. In Proc. ICFP'02, 271--282.

Digital Library

[29]

Haller, Philipp, and Martin Odersky. 2006. Event-based programming without inversion of control. In Proc. JMLC'06, vol. 4228 of LNCS, 4--22.

Digital Library

[30]

---. 2009. Scala actors: Unifying thread-based and event-based programming. Theor. Comput. Sci 410(2-3):202--220.

Digital Library

[31]

Kameyama, Yukiyoshi, and Takuo Yonezawa. 2008. Typed dynamic control operators for delimited continuations. In Proc. FLOPS'08, vol. 4989 of LNCS, 239--254.

Digital Library

[32]

Kiselyov, Oleg. 2005. How to remove a dynamic prompt: static and dynamic delimited continuation operators are equally expressible. Tech. Rep. TR611, Department of Computer Science, Indiana University.

[33]

---. 2007. Genuine shift/reset in haskell98. Announcement and explanations posted on the Haskell mailing list on 12/12/2007. Implementation available from: http://okmij.org/ftp/Haskell/ShiftResetGenuine.hs.

[34]

Kiselyov, Oleg, Chung-chieh Shan, and Amr Sabry. 2006. Delimited dynamic binding. In Proc. ICFP'06, 26--37.

Digital Library

[35]

Lea, Doug. 2000. A Java fork/join framework. In Proc. ACM Java Grande, 36--43.

Digital Library

[36]

Moors, Adriaan, Frank Piessens, and Martin Odersky. 2008. Generics of a higher kind. In Proc. OOPSLA'08, 423--438.

Digital Library

[37]

Nielsen, Anders Bach. 2008. Scala compiler phase and plug-in initialization. Available from: http://lampsvn.epfl.ch/svn-repos/scala/lamp-sip/compiler-phase-init/sip-00002.xhtml.

[38]

Nielsen, Lasse R. 2001. A selective CPS transformation. Tech. Rep. RS-01-30, BRICS, Department of Computer Science, Aarhus University.

[39]

Odersky, Martin. 2000. Functional Nets. In Proc. European Symposium on Programming Languages and Systems, 1--25.

Digital Library

[40]

Pettyjohn, Greg, John Clements, Joe Marshall, Shriram Krishnamurthi, and Matthias Felleisen. 2005. Continuations from generalized stack inspection. SIGPLAN Not. 40(9):216--227.

Digital Library

[41]

Rompf, Tiark. 2007. Design and implementation of a programming language for concurrent interactive systems. Master's thesis, Institute of Software Technology and Programming Languages, University of Lubeck, Germany. Available from: http://vodka.nachtlicht-media.de/docs.html.

[42]

Rose, John. 2008. JSR 292: Supporting dynamically typed languages on the Java platform. http://jcp.org/en/jsr/detail?id=292.

[43]

Shan, Chung-chieh. 2004. Shift to control. In Proc. ACM SIGPLAN workshop on Scheme and functional programming, 99--107.

[44]

---. 2007. A static simulation of dynamic delimited control. Higher-Order and Symbolic Computation 20(4):371--401.

Digital Library

[45]

Srinivasan, Sriram. 2006. A thread of one's own. In New horizons in compilers workshop, hipc, bangalore.

[46]

Srinivasan, Sriram, and Alan Mycroft. 2008. Kilim: Isolation-typed actors for Java. In Proc. ECOOP'08, 104--128.

Digital Library

[47]

Strachey, Christopher, and Christopher P.Wadsworth. 2000. Continuations: A mathematical semantics for handling full jumps. Higher-Order and Symbolic Computation 13(1):135--152.

Digital Library

[48]

Thielecke, Hayo. 2003. From control effects to typed continuation passing. In Proc. POPL'03, 139--149.

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

Implementing first-class polymorphic delimited continuations by a type-directed selective CPS-transform
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Control structures

Recommendations

Implementing first-class polymorphic delimited continuations by a type-directed selective CPS-transform
ICFP '09

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 ...
Polymorphic delimited continuations
APLAS'07: Proceedings of the 5th Asian conference on Programming languages and systems

This paper presents a polymorphic type system for a language with delimited control operators, shift and reset. Based on the monomorphic type system by Danvy and Filinski, the proposed type system allows pure expressions to be polymorphic. Thanks to the ...
On typing delimited continuations: three new solutions to the printf problem

In "Functional Unparsing" (J. Funct. Program. 8(6):621---625, 1998), Danvy presented a type-safe printf function using continuations and an accumulator to achieve the effect of dependent types. The key technique employed in Danvy's solution is the non-...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICFP '09: Proceedings of the 14th ACM SIGPLAN international conference on Functional programming

August 2009

364 pages

ISBN:9781605583327

DOI:10.1145/1596550

General Chair:
Graham Hutton
University of Nottingham
,
Program Chair:
Andrew Tolmach
Portland State University

ACM SIGPLAN Notices Volume 44, Issue 9
ICFP '09
September 2009
343 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1631687
Issue’s Table of Contents

Copyright © 2009 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: 31 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP '09

Sponsor:

ICFP '09: ACM SIGPLAN International Conference on Functional Programming

August 31 - September 2, 2009

Edinburgh, Scotland

Acceptance Rates

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

83
Total Citations
View Citations
747
Total Downloads

Downloads (Last 12 months)102
Downloads (Last 6 weeks)24

Reflects downloads up to 23 Oct 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
Wei GBračevac OTan SRompf T(2020)Compiling symbolic execution with staging and algebraic effectsProceedings of the ACM on Programming Languages10.1145/34282324:OOPSLA(1-33)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428232
Rutz HGroß-Vogt KHöldrich R(2020)A pattern system for sound processesProceedings of the 15th International Audio Mostly Conference10.1145/3411109.3411151(93-100)Online publication date: 15-Sep-2020
https://dl.acm.org/doi/10.1145/3411109.3411151
Helm DKübler FKölzer JHaller PEichberg MSalvaneschi GMezini MKhurshid SPăsăreanu C(2020)A programming model for semi-implicit parallelization of static analysesProceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3395363.3397367(428-439)Online publication date: 18-Jul-2020
https://dl.acm.org/doi/10.1145/3395363.3397367
Wang FZheng DDecker JWu XEssertel GRompf T(2019)Demystifying differentiable programming: shift/reset the penultimate backpropagatorProceedings of the ACM on Programming Languages10.1145/33417003:ICFP(1-31)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341700
Wang FDecker JWu XEssertel GRompf T(2018)Backpropagation with continuation callbacksProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3327546.3327682(10201-10212)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3327546.3327682
D'Elia DDemetrescu C(2018)On-stack replacement, distilledACM SIGPLAN Notices10.1145/3296979.319239653:4(166-180)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192396
Duck GYap R(2018)EffectiveSan: type and memory error detection using dynamically typed C/C++ACM SIGPLAN Notices10.1145/3296979.319238853:4(181-195)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192388
Show More Cited By

View Options

Get Access

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