Stack-Copying Delimited Continuations for Scala Native
Pages 2 - 13
Abstract
Scala, an industrial-strength functional and object-oriented programming language, is in need for an ergonomic approach to asynchronous programming. Project Loom provides direct-style concurrency to Scala on the JVM, which leaves its low-footprint high-performance backend Scala Native looking for an equivalent mechanism. We present a design and implementation of delimited continuations, a powerful control flow mechanism that provides the fundamental building block for direct-style concurrent and effectful programming, in Scala Native. Our implementation aims to preserve the unique advantages of the Native target: zero-cost C interoperability, runtime modularity and debugger compatibility. Through a detailed discussion of the implementation, we show that despite the limitations with stack address stability, it meets all the requirements of Scala Native while exhibiting comparable performance to our JVM counterpart.
References
[1]
2014. Go 1.3 Release Notes - The Go Programming Language. https://web.archive.org/web/20240324120446/https://go.dev/doc/go1.3
[2]
2017. DWARF Debugging Information Format Version 5. https://web.archive.org/web/20240621113516/https://dwarfstd.org/doc/DWARF5.pdf
[3]
2022. GitHub - koka-lang/libmprompt: Robust multi-prompt delimited control and effect handlers in C/C++. https://web.archive.org/web/20221014061022/http://github.com/koka-lang/libmprompt
[4]
2024. Cats Effect · The pure asynchronous runtime for Scala. https://web.archive.org/web/20240515110705/https://typelevel.org/cats-effect/
[5]
2024. Gears - An Experimental Asynchronous Programming Library for Scala 3. https://web.archive.org/web/20240629172709/https://lampepfl.github.io/gears/
[6]
2024. java.nio (Java SE 21 & JDK 21). https://web.archive.org/web/20240515032110/https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/nio/package-summary.html
[7]
2024. Native code interoperability — Scala Native 0.4.17 documentation. https://web.archive.org/web/20240224090543/https://scala-native.org/en/stable/user/interop.html##memory-management
[8]
2024. Scala Native — Scala Native 0.5.1 documentation. https://web.archive.org/web/20240515151405/https://scala-native.org/en/stable/
[9]
2024. ZIO | ZIO. https://web.archive.org/web/20240602194018/https://zio.dev/
[10]
Aleksander Boruch-Gruszecki, Martin Odersky, Edward Lee, Ondrej Lhoták, and Jonathan Immanuel Brachthäuser. 2023. Capturing Types. ACM Trans. Program. Lang. Syst., 45, 4 (2023), 21:1–21:52. https://doi.org/10.1145/3618003
[11]
Jonathan Immanuel Brachthäuser, Philipp Schuster, and Klaus Ostermann. 2020. Effects as capabilities: effect handlers and lightweight effect polymorphism. Proc. ACM Program. Lang., 4, OOPSLA (2020), 126:1–126:30. https://doi.org/10.1145/3428194
[12]
Jonathan Immanuel Brachthäuser, Philipp Schuster, and Klaus Ostermann. 2020. Effekt: Capability-passing style for type- and effect-safe, extensible effect handlers in Scala. J. Funct. Program., 30 (2020), e8. https://doi.org/10.1017/S0956796820000027
[13]
Carl Bruggeman, Oscar Waddell, and R. Kent Dybvig. 1996. Representing Control in the Presence of One-Shot Continuations. In Proceedings of the ACM SIGPLAN’96 Conference on Programming Language Design and Implementation (PLDI), Philadephia, Pennsylvania, USA, May 21-24, 1996, Charles N. Fischer (Ed.). ACM, 99–107. https://doi.org/10.1145/231379.231395
[14]
Olivier Danvy and Andrzej Filinski. 1990. Abstracting Control. In Proceedings of the 1990 ACM Conference on LISP and Functional Programming, LFP 1990, Nice, France, 27-29 June 1990, Gilles Kahn (Ed.). ACM, 151–160. https://doi.org/10.1145/91556.91622
[15]
R. Kent Dybvig, Simon L. Peyton Jones, and Amr Sabry. 2007. A monadic framework for delimited continuations. J. Funct. Program., 17, 6 (2007), 687–730. https://doi.org/10.1017/S0956796807006259
[16]
Kavon Farvardin and John H. Reppy. 2020. From folklore to fact: comparing implementations of stacks and continuations. In Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2020, London, UK, June 15-20, 2020, Alastair F. Donaldson and Emina Torlak (Eds.). ACM, 75–90. https://doi.org/10.1145/3385412.3385994
[17]
Matthew Flatt and R. Kent Dybvig. 2020. Compiler and runtime support for continuation marks. In Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2020, London, UK, June 15-20, 2020, Alastair F. Donaldson and Emina Torlak (Eds.). ACM, 45–58. https://doi.org/10.1145/3385412.3385981
[18]
Matthew Flatt, Gang Yu, Robert Bruce Findler, and Matthias Felleisen. 2007. Adding delimited and composable control to a production programming environment. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP 2007, Freiburg, Germany, October 1-3, 2007, Ralf Hinze and Norman Ramsey (Eds.). ACM, 165–176. https://doi.org/10.1145/1291151.1291178
[19]
Yannick Forster, Ohad Kammar, Sam Lindley, and Matija Pretnar. 2019. On the expressive power of user-defined effects: Effect handlers, monadic reflection, delimited control. J. Funct. Program., 29 (2019), e15. https://doi.org/10.1017/S0956796819000121
[20]
Dan R. Ghica, Sam Lindley, Marcos Maroñas Bravo, and Maciej Piróg. 2022. High-level effect handlers in C++. Proc. ACM Program. Lang., 6, OOPSLA2 (2022), 1639–1667. https://doi.org/10.1145/3563445
[21]
Alexis King. 2021. ghc-proposals: Delimited continuation primops. https://web.archive.org/web/20230319140521/https://github.com/ghc-proposals/ghc-proposals/blob/master/proposals/0313-delimited-continuation-primops.rst
[22]
Oleg Kiselyov and Hiromi Ishii. 2015. Freer monads, more extensible effects. In Proceedings of the 8th ACM SIGPLAN Symposium on Haskell, Haskell 2015, Vancouver, BC, Canada, September 3-4, 2015, Ben Lippmeier (Ed.). ACM, 94–105. https://doi.org/10.1145/2804302.2804319
[23]
Daan Leijen. 2017. Implementing Algebraic Effects in C - "Monads for Free in C". In Programming Languages and Systems - 15th Asian Symposium, APLAS 2017, Suzhou, China, November 27-29, 2017, Proceedings, Bor-Yuh Evan Chang (Ed.) (Lecture Notes in Computer Science, Vol. 10695). Springer, 339–363. https://doi.org/10.1007/978-3-319-71237-6_17
[24]
Daan Leijen. 2017. Type directed compilation of row-typed algebraic effects. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, Paris, France, January 18-20, 2017, Giuseppe Castagna and Andrew D. Gordon (Eds.). ACM, 486–499. https://doi.org/10.1145/3009837.3009872
[25]
Nystrom. 2015. What Color is Your Function? – journal.stuffwithstuff.com. https://web.archive.org/web/20240607162416/https://journal.stuffwithstuff.com/2015/02/01/what-color-is-your-function/
[26]
Martin Odersky. 2022. SIP-44 - Fewer Braces. https://docs.scala-lang.org/sips/fewer-braces.html
[27]
Martin Odersky. 2024. Lean Scala | Language and Code. https://web.archive.org/web/20240511072330/https://odersky.github.io/blog/2024-04-11-post.html
[28]
Bruno C. d S. Oliveira, Adriaan Moors, and Martin Odersky. 2010. Type classes as objects and implicits. In Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2010, October 17-21, 2010, Reno/Tahoe, Nevada, USA, William R. Cook, Siobhán Clarke, and Martin C. Rinard (Eds.). ACM, 341–360. https://doi.org/10.1145/1869459.1869489
[29]
Ron Pressler and Alan Bateman. 2023. JEP 425: Virtual Threads (Preview). https://web.archive.org/web/20240621024945/https://openjdk.org/jeps/425
[30]
Tiark Rompf, Ingo Maier, and Martin Odersky. 2009. Implementing first-class polymorphic delimited continuations by a type-directed selective CPS-transform. In Proceeding of the 14th ACM SIGPLAN international conference on Functional programming, ICFP 2009, Edinburgh, Scotland, UK, August 31 - September 2, 2009, Graham Hutton and Andrew P. Tolmach (Eds.). ACM, 317–328. https://doi.org/10.1145/1596550.1596596
[31]
K. C. Sivaramakrishnan, Stephen Dolan, Leo White, Tom Kelly, Sadiq Jaffer, and Anil Madhavapeddy. 2021. Retrofitting effect handlers onto OCaml. In PLDI ’21: 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Virtual Event, Canada, June 20-25, 2021, Stephen N. Freund and Eran Yahav (Eds.). ACM, 206–221. https://doi.org/10.1145/3453483.3454039
[32]
Ningning Xie and Daan Leijen. 2021. Generalized evidence passing for effect handlers: efficient compilation of effect handlers to C. Proc. ACM Program. Lang., 5, ICFP (2021), 1–30. https://doi.org/10.1145/3473576
[33]
Yizhou Zhang and Andrew C. Myers. 2019. Abstraction-safe effect handlers via tunneling. Proc. ACM Program. Lang., 3, POPL (2019), 5:1–5:29. https://doi.org/10.1145/3290318
Index Terms
- Stack-Copying Delimited Continuations for Scala Native
Recommendations
Evaluating the Java Native Interface JNI: Leveraging Existing Native Code, Libraries and Threads to a Running Java Virtual Machine
This article aims to explore JNI features and to discover fundamental operations of the Java programming language, such as arrays, objects, classes, threads and exception handling, and to illustrate these by using various algorithms and code samples. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2024
13 pages
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to 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 the author(s) 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: 13 September 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- FNSNF
- EPFL
Conference
ICOOOLPS '24
Sponsor:
ICOOOLPS '24: 19th ACM International Workshop on Implementation, Compilation, Optimization of OO Languages, Programs and Systems
September 20, 2024
Vienna, Austria
Acceptance Rates
Overall Acceptance Rate 11 of 14 submissions, 79%
Upcoming Conference
ISSTA '25
- Sponsor:
- sigsoft
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 91Total Downloads
- Downloads (Last 12 months)91
- Downloads (Last 6 weeks)36
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
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.
Sign in