Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article
Open access

Handling bidirectional control flow

Published: 13 November 2020 Publication History

Abstract

Pressed by the difficulty of writing asynchronous, event-driven code, mainstream languages have recently been building in support for a variety of advanced control-flow features. Meanwhile, experimental language designs have suggested effect handlers as a unifying solution to programmer-defined control effects, subsuming exceptions, generators, and async–await. However, despite these trends, complex control flow—in particular, control flow that exhibits a bidirectional pattern—remains challenging to manage.
We introduce bidirectional algebraic effects, a new programming abstraction that supports bidirectional control transfer in a more natural way. Handlers of bidirectional effects can raise further effects to transfer control back to the site where the initiating effect was raised, and can use themselves to handle their own effects. We present applications of this expressive power, which falls out naturally as we push toward the unification of effectful programming with object-oriented programming. We pin down the mechanism and the unification formally using a core language that makes generalizations to effect operations and effect handlers.
The usual propagation semantics of control effects such as exceptions conflicts with modular reasoning in the presence of effect polymorphism—it breaks parametricity. Bidirectionality exacerbates the problem. Hence, we set out to show the core language, which builds on the existing tunneling semantics for algebraic effects, is not only type-safe (no effects go unhandled), but also abstraction-safe (no effects are accidentally handled). We devise a step-indexed logical-relations model, and construct its parametricity and soundness proofs. These core results are fully mechanized in Coq. While a full-featured compiler is left to future work, experiments show that as a first-class language feature, bidirectional handlers can be implemented efficiently.

Supplementary Material

Auxiliary Presentation Video (oopsla20main-p51-p-video.mp4)
OOPSLA 2020 talk on paper "Handling Bidirectional Control Flow"

References

[1]
A. Ahmed. Step-indexed syntactic logical relations for recursive and quantified types. In 15th European Symposium on Programming, 2006. Extended/corrected version available as Harvard University TR-01-06.
[2]
S. Alimadadi, D. Zhong, M. Madsen, and F. Tip. Finding broken promises in asynchronous JavaScript programs. Proc. ACM on Programming Languages, 2 (OOPSLA), Oct. 2018.
[3]
A. W. Appel and D. McAllester. An indexed model of recursive types for foundational proof-carrying code. ACM Trans. on Programming Languages and Systems, 23 ( 5 ), Sept. 2001.
[4]
A. W. Appel, P.-A. Melliès, C. D. Richards, and J. Vouillon. A very modal model of a modern, major, general type system. In 34th ACM Symp. on Principles of Programming Languages (POPL), 2007.
[5]
K. Asai and Y. Kameyama. Polymorphic delimited continuations. In 5th Asian Symposium on Programming Languages and Systems (APLAS), 2007.
[6]
B. Aydemir, A. Charguéraud, B. C. Pierce, R. Pollack, and S. Weirich. Engineering formal metatheory. In 35th ACM Symp. on Principles of Programming Languages (POPL), 2008.
[7]
A. Bauer and M. Pretnar. Programming with algebraic efects and handlers. Journal of Logical and Algebraic Methods in Programming, 84 ( 1 ), 2015.
[8]
G. Bierman, C. Russo, G. Mainland, E. Meijer, and M. Torgersen. Pause 'n' play: Formalizing asynchronous C#. In 26th European Conf. on Object-Oriented Programming, 2012.
[9]
D. Biernacki, M. Piróg, P. Polesiuk, and F. Sieczkowski. Handle with care: Relational interpretation of algebraic efects and handlers. Proc. ACM on Programming Languages, 2 (POPL), Jan. 2018.
[10]
D. Biernacki, M. Piróg, P. Polesiuk, and F. Sieczkowski. Abstracting algebraic efects. Proc. ACM on Programming Languages, 3 (POPL), Jan. 2019.
[11]
D. Biernacki, M. Piróg, P. Polesiuk, and F. Sieczkowski. Binders by day, labels by night: efect instances via lexically scoped handlers. Proc. ACM on Programming Languages, 4 (POPL), Jan. 2020.
[12]
J. I. Brachthäuser, P. Schuster, and K. Ostermann. Algebraic efects for the masses. Proc. ACM on Programming Languages, 2 (OOPSLA), Oct. 2018.
[13]
J. I. Brachthäuser, P. Schuster, and K. Ostermann. Efekt: Capability-passing style for type-and efect-safe, extensible efect handlers in Scala. J. Functional Programming, 30, Mar. 2020.
[14]
O. Bračevac, N. Amin, G. Salvaneschi, S. Erdweg, P. Eugster, and M. Mezini. Versatile event correlation with algebraic efects. Proc. ACM on Programming Languages, 2 (ICFP), Aug. 2018.
[15]
P. A. Buhr. µ C+ + annotated reference manual, version 7.0.0. Technical report, School of Computer Science, University of Waterloo, 2019.
[16]
B. Cabral and P. Marques. Hidden truth behind.NET's exception handling today. IET Software, 1 ( 6 ), 2007.
[17]
L. Convent, S. Lindley, C. McBride, and C. McLaughlin. Doo bee doo bee doo. J. Functional Programming, 30, Mar. 2020.
[18]
O. Danvy and A. Filinski. Abstracting control. In ACM Conf. on LISP and Functional Programming, pages 151-160, 1990.
[19]
S. Dolan, S. Eliopoulos, D. Hillerström, A. Madhavapeddy, K. C. Sivaramakrishnan, and L. White. Concurrent system programming with efect handlers. In Trends in Functional Programming, 2017.
[20]
D. Dreyer. Milner award lecture: The type soundness theorem that you really want to prove (and now you can). In 45th ACM Symp. on Principles of Programming Languages (POPL), 2018.
[21]
D. Dreyer, A. Ahmed, and L. Birkedal. Logical step-indexed logical relations. In 24th Annual IEEE Symposium on Logic In Computer Science (LICS), 2009.
[22]
ECMA International. ECMAScript 2018 language specification. Standard-ECMA 262, June 2018.
[23]
M. Felleisen. The theory and practice of first-class prompts. In 15th ACM Symp. on Principles of Programming Languages (POPL), pages 180-190, 1988.
[24]
M. Felleisen. On the expressive power of programming languages. Science of Computer Programming, 17 ( 1 ), 1991.
[25]
Y. Forster, O. Kammar, S. Lindley, and M. Pretnar. On the expressive power of user-defined efects: Efect handlers, monadic reflection, delimited control. Proc. ACM on Programming Languages, 1 (ICFP), Aug. 2017.
[26]
S. Fowler, S. Lindley, J. G. Morris, and S. Decova. Exceptional asynchronous session types. In 46th ACM Symp. on Principles of Programming Languages (POPL), Jan. 2019.
[27]
J. Gosling, B. Joy, G. Steele, G. Bracha, A. Buckley, and D. Smith. The Java Language Specification. Oracle America, se 11 edition, Aug 2018.
[28]
R. E. Griswold, D. R. Hanson, and J. T. Korb. Generators in Icon. ACM Trans. on Programming Languages and Systems, 3 ( 2 ): 144-161, Apr. 1981.
[29]
D. Grossman, G. Morrisett, T. Jim, M. Hicks, Y. Wang, and J. Cheney. Region-based memory management in Cyclone. In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), pages 282-293. ACM Press, 2002.
[30]
C. A. Gunter, D. Rémy, and J. G. Riecke. A generalization of exceptions and control in ML-like languages. In 7th Conf. on Functional Programming Languages and Computer Architecture (FPCA), 1995.
[31]
C. T. Haynes, D. P. Friedman, and M. Wand. Obtaining coroutines from continuations. Journal of Computer Languages, 11 ( 3-4 ): 143-153, 1986.
[32]
A. Hejlsberg, S. Wiltamuth, and P. Golde. The C # Programming Language. Addison-Wesley, 1st edition, Oct. 2003. ISBN 0321154916.
[33]
D. Hillerström and S. Lindley. Shallow efect handlers. In Asian Symp. on Programming Languages and Systems, 2018.
[34]
K. Honda, V. T. Vasconcelos, and M. Kubo. Language primitives and type discipline for structured communication-based programming. In European Symposium on Programming, 1999.
[35]
O. Kammar, S. Lindley, and N. Oury. Handlers in action. In 18th ACM SIGPLAN Int'l Conf. on Functional Programming, 2013.
[36]
S. Klabnik and C. Nichols. The Rust Programming Language (Covers Rust 2018 ). No Starch Press, 2019.
[37]
C. Lattner and J. Grof. Async/await for Swift. https://gist.github.com/lattner/429b9070918248274f25b714dcfc7619, 2019.
[38]
D. Leijen. Koka: Programming with row polymorphic efect types. In 5th Workshop on Mathematically Structured Functional Programming. EPTCS, 2014.
[39]
D. Leijen. Structured asynchrony with algebraic efects. In Proceedings of the 2nd ACM SIGPLAN International Workshop on Type-Driven Development, TyDe 2017, 2017a.
[40]
D. Leijen. Type directed compilation of row-typed algebraic efects. In 44th ACM Symp. on Principles of Programming Languages (POPL), 2017b.
[41]
D. Leijen. Implementing algebraic efects in C. In 15th Asian Symposium on Programming Languages and Systems (APLAS), 2017c.
[42]
S. Lindley, C. McBride, and C. McLaughlin. Do be do be do. In 44th ACM Symp. on Principles of Programming Languages (POPL), 2017.
[43]
B. Liskov and L. Shrira. Promises: Linguistic support for eficient asynchronous procedure calls in distributed systems. In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), June 1988.
[44]
B. Liskov, A. Snyder, R. Atkinson, and J. C. Schafert. Abstraction mechanisms in CLU. Comm. of the ACM, 20 ( 8 ): 564-576, Aug. 1977. Also in S. Zdonik and D. Maier, eds., Readings in Object-Oriented Database Systems.
[45]
J. Liu, A. Kimball, and A. C. Myers. Interruptible iterators. In 33rd ACM Symp. on Principles of Programming Languages (POPL), POPL '06, pages 283-294, Jan. 2006.
[46]
J. M. Lucassen and D. K. Giford. Polymorphic efect systems. In 15th ACM Symp. on Principles of Programming Languages (POPL), POPL '88, pages 47-57, 1988.
[47]
E. Meijer, M. Fokkinga, and R. Paterson. Functional programming with bananas, lenses, envelopes and barbed wire. In 5th Conf. on Functional Programming Languages and Computer Architecture (FPCA), 1991.
[48]
J. G. Mitchell, W. Maybury, and R. Sweet. Mesa language manual version 5.0. Technical Report CSL-79-3, Xerox Research Center, Palo Alto, Ca., 1979.
[49]
J. H. Morris, Jr. Lambda-Calculus Models of Programming Languages. PhD thesis, Massachusetts Institute of Technology, 1968.
[50]
S. Murer, S. Omohundro, D. Stoutamire, and C. Szyperski. Iteration abstraction in Sather. ACM Trans. on Programming Languages and Systems, 18 ( 1 ): 1-15, Jan. 1996.
[51]
S. Okur, D. L. Hartveld, D. Dig, and A. v. Deursen. A study and toolkit for asynchronous programming in C#. In 36th Int'l Conf. on Software Engineering (ICSE), 2014.
[52]
M. Piróg, P. Polesiuk, and F. Sieczkowski. Typed equivalence of efect handlers and delimited control. In 4th International Conference on Formal Structures for Computation and Deduction (FSCD), 2019.
[53]
A. M. Pitts and I. Stark. Operational reasoning for functions with local state. Higher order operational techniques in semantics, pages 227-273, 1998.
[54]
G. Plotkin and J. Power. Algebraic operations and generic efects. Applied Categorical Structures, 11 ( 1 ): 69-94, Feb 2003.
[55]
G. Plotkin and M. Pretnar. Handling algebraic efects. Logical Methods in Computer Science, Volume 9, Issue 4, Dec. 2013.
[56]
P. Polesiuk. IxFree: Step-indexed logical relations in Coq. In 3rd International Workshop on Coq for Programming Languages (CoqPL), 2017.
[57]
J. C. Reynolds. Types, abstraction and parametric polymorphism. In IFIP Congress, pages 513-523, 1983.
[58]
Rust language team. Async & await in Rust: a full proposal. https://boats.gitlab.io/blog/post/2018-04-06-async-await-final, 2018.
[59]
M. Shaw, W. Wulf, and R. London. Abstraction and verification in Alphard: Defining and specifying iteration and generators. Comm. of the ACM, 20 ( 8 ), Aug. 1977.
[60]
B. Stroustrup. The C+ + Programming Language. Addison-Wesley, 1987.
[61]
D. Thomas, C. Fowler, and A. Hunt. Programming Ruby: The Pragmatic Programmers' Guide. The Pragmatic Programmers, 2nd edition, 2004. ISBN 0-974-51405-5.
[62]
M. Tofte and J.-P. Talpin. Region-based memory management. Information and Computation, 132 ( 2 ): 109-176, 1997.
[63]
G. van Rossum. The Python Language Reference Manual. Network Theory, Ltd., Sept. 2003.
[64]
M. Wand. Type inference for record concatenation and multiple inheritance. Information and Computation, 93 ( 1 ), 1991.
[65]
Y. Zhang and A. C. Myers. Abstraction-safe efect handlers via tunneling. Proc. ACM on Programming Languages, 3 (POPL), Jan. 2019.
[66]
Y. Zhang, G. Salvaneschi, Q. Beightol, B. Liskov, and A. C. Myers. Accepting blame for safe tunneled exceptions. In 37th ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), pages 281-295, June 2016.
[67]
Y. Zhang, G. Salvaneschi, and A. C. Myers. Handling bidirectional control flow: Technical report. https://arxiv.org/abs/ 2010. 09073, 2020.

Cited By

View all
  • (2022)Effects, capabilities, and boxes: from scope-based reasoning to type-based reasoning and backProceedings of the ACM on Programming Languages10.1145/35273206:OOPSLA1(1-30)Online publication date: 29-Apr-2022
  • (2022)A typed continuation-passing translation for lexical effect handlersProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523710(566-579)Online publication date: 9-Jun-2022
  • (2022)Understanding Algebraic Effect Handlers via Delimited Control OperatorsTrends in Functional Programming10.1007/978-3-031-21314-4_4(59-79)Online publication date: 17-Mar-2022
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages
Proceedings of the ACM on Programming Languages  Volume 4, Issue OOPSLA
November 2020
3108 pages
EISSN:2475-1421
DOI:10.1145/3436718
Issue’s Table of Contents
This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 November 2020
Published in PACMPL Volume 4, Issue OOPSLA

Permissions

Request permissions for this article.

Check for updates

Badges

Author Tags

  1. Effect handlers
  2. exceptions
  3. iterators
  4. parametricity
  5. promises
  6. type systems

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)346
  • Downloads (Last 6 weeks)51
Reflects downloads up to 23 Sep 2024

Other Metrics

Citations

Cited By

View all
  • (2022)Effects, capabilities, and boxes: from scope-based reasoning to type-based reasoning and backProceedings of the ACM on Programming Languages10.1145/35273206:OOPSLA1(1-30)Online publication date: 29-Apr-2022
  • (2022)A typed continuation-passing translation for lexical effect handlersProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523710(566-579)Online publication date: 9-Jun-2022
  • (2022)Understanding Algebraic Effect Handlers via Delimited Control OperatorsTrends in Functional Programming10.1007/978-3-031-21314-4_4(59-79)Online publication date: 17-Mar-2022
  • (2022)What You See Is What You Get: Practical Effect Handlers in Capability-Passing StyleErnst Denert Award for Software Engineering 202010.1007/978-3-030-83128-8_3(15-43)Online publication date: 1-Jan-2022
  • (2021)A Large-scale Analysis of Hundreds of In-memory Key-value Cache Clusters at TwitterACM Transactions on Storage10.1145/346852117:3(1-35)Online publication date: 16-Aug-2021

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Full Access

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media