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.
algebraic effects
Print-on-Demand