research-article

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

Authors:

Martin OderskyAuthors Info & Claims

ACM SIGPLAN Notices, Volume 44, Issue 9

Pages 317 - 328

https://doi.org/10.1145/1631687.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

Elizarov RBelyaev MAkhin MUsmanov IDe Meuter WBaniassad E(2021)Kotlin coroutines: design and implementationProceedings of the 2021 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3486607.3486751(68-84)Online publication date: 20-Oct-2021
https://dl.acm.org/doi/10.1145/3486607.3486751
Bao YWei GBračevac OJiang YHe QRompf T(2021)Reachability types: tracking aliasing and separation in higher-order functional programsProceedings of the ACM on Programming Languages10.1145/34855165:OOPSLA(1-32)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485516
Ishio CAsai K(2020)Verifying Selective CPS Transformation for Shift and ResetTrends in Functional Programming10.1007/978-3-030-47147-7_3(38-57)Online publication date: 11-May-2020
https://doi.org/10.1007/978-3-030-47147-7_3
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: 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 ...
Handling delimited continuations with dependent types

Dependent types are a powerful tool for maintaining program invariants. To take advantage of this aspect in real-world programming, efforts have been put into enriching dependently typed languages with missing constructs, most notably, effects. This ...
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 ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

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

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

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 August 2009

Published in SIGPLAN Volume 44, Issue 9

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

83
Total Citations
View Citations
794
Total Downloads

Downloads (Last 12 months)94
Downloads (Last 6 weeks)6

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Elizarov RBelyaev MAkhin MUsmanov IDe Meuter WBaniassad E(2021)Kotlin coroutines: design and implementationProceedings of the 2021 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3486607.3486751(68-84)Online publication date: 20-Oct-2021
https://dl.acm.org/doi/10.1145/3486607.3486751
Bao YWei GBračevac OJiang YHe QRompf T(2021)Reachability types: tracking aliasing and separation in higher-order functional programsProceedings of the ACM on Programming Languages10.1145/34855165:OOPSLA(1-32)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485516
Ishio CAsai K(2020)Verifying Selective CPS Transformation for Shift and ResetTrends in Functional Programming10.1007/978-3-030-47147-7_3(38-57)Online publication date: 11-May-2020
https://doi.org/10.1007/978-3-030-47147-7_3
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
Sherwany AZaza NNystrom N(2015)A Refactoring Library for Scala Compiler ExtensionsCompiler Construction10.1007/978-3-662-46663-6_2(31-48)Online publication date: 2015
https://doi.org/10.1007/978-3-662-46663-6_2
Zakian CZakian TKulkarni AChamith BNewton R(2015)Concurrent CilkRevised Selected Papers of the 28th International Workshop on Languages and Compilers for Parallel Computing - Volume 951910.1007/978-3-319-29778-1_5(73-90)Online publication date: 9-Sep-2015
https://dl.acm.org/doi/10.1007/978-3-319-29778-1_5
Kotelnikov EHaller PMiller H(2014)Type-directed language extension for effectful computationsProceedings of the Fifth Annual Scala Workshop10.1145/2637647.2637648(35-43)Online publication date: 28-Jul-2014
https://dl.acm.org/doi/10.1145/2637647.2637648
Milanés ARodriguez NIerusalimschy R(2014)Reflection-Based Heterogeneous Migration of ComputationsProceedings of the 2014 Brazilian Symposium on Computer Networks and Distributed Systems10.1109/SBRC.2014.27(223-230)Online publication date: 5-May-2014
https://dl.acm.org/doi/10.1109/SBRC.2014.27
Foltzer AKulkarni ASwords RSasidharan SJiang ENewton R(2012)A meta-scheduler for the par-monadACM SIGPLAN Notices10.1145/2398856.236456247:9(235-246)Online publication date: 9-Sep-2012
https://dl.acm.org/doi/10.1145/2398856.2364562
Foltzer AKulkarni ASwords RSasidharan SJiang ENewton RThiemann PFindler R(2012)A meta-scheduler for the par-monadProceedings of the 17th ACM SIGPLAN international conference on Functional programming10.1145/2364527.2364562(235-246)Online publication date: 9-Sep-2012
https://dl.acm.org/doi/10.1145/2364527.2364562
Show More Cited By

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.

Figures

Tables

Media

View Issue’s Table of Contents