Design and Implementation of Effect Handlers for Object-Oriented Programming Languages

DSpace Repository


Dateien:

URI: http://hdl.handle.net/10900/102021
http://nbn-resolving.de/urn:nbn:de:bsz:21-dspace-1020211
http://dx.doi.org/10.15496/publikation-43400
Dokumentart: PhDThesis
Date: 2020-07-01
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Informatik
Advisor: Ostermann, Klaus (Prof. Dr.)
Day of Oral Examination: 2020-05-07
DDC Classifikation: 004 - Data processing and computer science
Keywords: Programm , Programmiersprache , Kontrollfluss , Objektorientierung , Ausnahmebehandlung , Modularität , Erweiterbarkeit
Other Keywords: Effektbehandlung
Algebraische Effekte
algebraic effects
effect handlers
License: http://tobias-lib.uni-tuebingen.de/doku/lic_mit_pod.php?la=de http://tobias-lib.uni-tuebingen.de/doku/lic_mit_pod.php?la=en
Order a printed copy: Print-on-Demand
Show full item record

Abstract:

An important aspect of software development is to structure the control flow of a program. Features to structure the control flow range from simple branching between two possible execution paths, to non-local control-flow transfers by means of jumps or exceptions. Furthermore, modern programming languages offer advanced control-flow structures like async/await to avoid blocking when performing input / output actions, generators to model demand driven computation of streams, or coroutines to express control-flow transfer between different software components. Often, those advanced control-flow abstractions are built into the language and are thus not user definable. Users are thus limited to the control-flow features provided by the programming language designers and cannot create their own custom domain-specific control-flow abstractions. Another aspect of software development is to parametrize a software component over details that might vary. Parametrizing a component with configuration, behavior, or other components, enables reuse of the same component in different contexts. Components can be configured statically, or dynamically at runtime. Manually parametrizing components can quickly become tedious, both for the component author who needs to design the component for parametrization, as well as the user of the component who needs to provide all parameters. This is especially the case for components that depend on other parametrized components. They often need to be parametrized by all transitive parameters of their dependencies. Algebraic effects (Plotkin and Power, 2003) and their extension with handlers (Plotkin and Pretnar, 2009, 2013) offer interesting new ways to structure programs. Programs use effect operations, which, like normal functions, can receive arguments and return results. However, the implementation of effect operations is left open and depends on the context in which the program is executed. Effect handlers, much like exception handlers, handle effect operations and provide their implementation. Like throwing an exception, calling an effect operation transfers control to the corresponding handler. Unlike exceptions, the handler can resume the computation and thus transfer control back to the call site. Effect handlers support both aspects of software development concisely: they can express advanced control-flow structures as well as parametrization of software components. It has been shown in the literature that effect handlers can express many of the aforementioned control-flow structures as libraries, such as async/await, generators, and coroutines. At the same time, effect operations can conveniently be used to parametrize software components while handlers provide the configuration. Unifying both aspects also guarantees well-defined interaction between control flow and parametrization. While algebraic effects recently gained popularity in the programming language research community, we identify two problems hindering adoption by a wider audience of programmers. Firstly, programmers are immediately confronted with the full generality of effect handlers. While effect handlers are expressive enough to model advanced control-flow structures, not all use cases require this expressivity. Secondly, algebraic effects and handlers have been conceived in the realm of functional programming languages. In consequence, most implementations of effect handlers are either standalone languages following the functional programming paradigm or are library embeddings into existing functional programming languages. In this thesis, we propose solutions to the two aforementioned problems with the goal to facilitate adoption of effect handlers by a wider audience. To address the first problem, we systematically present effect handlers as a combination of delimited control (that is, they allow control-flow transfers) and dynamic binding (that is, they allow parametrization). While the connection between effect handlers and delimited control has previously been established and it has been shown that effect handlers can express dynamic binding, we discover that dynamic binding and effect handlers form a spectrum. We present a language design that embraces this spectrum. Increasing expressivity and conceptual complexity step-by-step, we introduce the three features ambient values, ambient functions, and ambient control. Ambient values coincide with dynamically bound variables and ambient control coincides with a slightly restricted form of effect handlers. The novel intermediate form of ambient functions enables abstraction similar to effect handlers, but without modifying the control flow: Ambient functions are dynamically bound, but statically evaluated. Introducing effect handlers from dynamic binding offers programmers an alternative way to approach handlers. They can incrementally learn and understand the different generalizations (ambient values, functions, and control). We hope this facilitates adoption of effect handlers by a wider audience. To address the second problem, we present a library design, which embeds effect handlers in object-oriented programming languages. Our design embraces the object-oriented programming paradigm and we map abstractions of effect handlers to key abstractions of object-oriented programming. Combining the two paradigms not only enables programmers to use effect handlers in object-oriented programs, but also to use object-oriented programming abstractions to modularize effect handlers. Our design employs explicit capability-passing style. That is, instead of dynamically searching for a handler at runtime, we pass instances of handlers as additional arguments to methods. We present an implementation of our library design in the language Scala. It is based on a variation of a continuation monad for multi-prompt delimited control (Dybvig et al., 2007) to allow effect handlers to express advanced control-flow structures. We study the extensibility properties gained by embedding effect handlers into an object-oriented programming language. While it opens up new dimensions of extensibility, the implementation still comes with two limitations. Firstly, being based on a monad user programs have to be written in monadic style. Secondly, the implementation is not effect safe and capabilities can escape the scope of their handler. This potentially results in runtime errors. We separately address the two limitations. Firstly, we present an implementation in Java that performs a type-selective continuation-passing style transformation by rewriting of bytecode. This way, user programs in the Java implementation can be written in direct-style overcoming the limitation of the Scala implementation. Secondly, we enhance our Scala library with an embedded effect system. We index the type of effectful programs with an intersection type to track the set of used effects. Expressing the set of used effects as an intersection type allows us to reuse Scala's support for subtyping to express effect subtyping and to reuse Scala's support for type polymorphism to express effect polymorphism.

This item appears in the following Collection(s)