1 Introduction
Algebraic effects [20] and handlers [21] are a powerful abstraction mechanism to represent and implement control effects, such as exceptions, interactive I/O, mutable states, nondeterminism, and so on. They are growing in popularity for the success in achieving modularity of effects, especially clear separation between their interfaces and implementations. An interface of effects is given as a set of operations—for example, an interface of mutable states consists two operations put and get—with their signatures. An implementation is given by a handler , which provides a set of interpretations of operations (called operation clauses), and a – expression associates effects invoked during the computation of with handler . Algebraic effects and handlers work as resumable exceptions: when an effect operation is invoked, the runtime system tries to find the nearest handler that handles the invoked operation; if it is found, the corresponding operation clause is evaluated by using the argument to the operation invocation and the continuation up to the handler. The continuation gives the ability to resume the computation from the point where the operation was invoked, using the result from the operation clause. Another modularity that algebraic effects provide is flexible composition: multiple algebraic effects can be combined freely [13].
In this work, we study an extension of algebraic effects and handlers with another typebased abstraction mechanism—parametric polymorphism [22]. In general, parametric polymorphism is a basis of generic programming and enhance code reusability by abstracting expressions over types. This work allows abstracting not only expressions but also effect operations and handlers, which makes it possible to reuse and reason about effect implementations that are independent of concrete type representations. As many functional languages, we introduce polymorphism as the form of letpolymorphism for its practically desirable properties such as decidable typechecking and type inference.
As is well known, however, naive combination of polymorphic effects and letpolymorphism breaks type safety [23, 11]. Many researches have attacked this classical problem [23, 17, 1, 12, 24, 10, 2, 14], and their common idea is to restrict the form of letbound expressions. For example, the value restriction [23, 24], which is the standard way to make MLlike languages with imperative features and letpolymorphism typesafe, allows only syntactic values to be polymorphic.
In this work, we propose a new approach to achieving type safety in a language with letpolymorphic and polymorphic effects and handlers: the idea is to restrict, instead of letbound expressions, handlers. Since a handler gives an implementation of an effect, our work can be viewed as giving a criterion that suggests what effects can be cooperated safely with (unrestricted) letpolymorphism and what effects cannot. Our key observation for type safety is, informally speaking, that an invocation of a polymorphic effect in a letbound expression is safe if resumptions in the corresponding operation clause do not interfere with each other. We formalize this discipline into a type system and show that typeable programs do not get stuck.
Our contributions are summarized as follows.

We introduce a callbyvalue, statically typed lambda calculus that supports letpolymorphism and polymorphic algebraic effects and handlers. The type system of allows any letbound expressions involving effects to be polymorphic but, instead, disallows handlers where resumptions interfere with each other.

To give the semantics of , we formalize an intermediate language where type information is made explicit and define elaboration from to .

We prove type safety of by type preservation of the elaboration and type soundness of .
We believe that our approach is complementary to the usual approach of restricting letbound expressions: for handlers that are considered unsafe by our criterion, value restriction can be still used.
The rest of this paper is organized as follows. Section 2 describes an overview of our work, giving motivating examples of polymorphic effects and handlers, a problem in naive combination of polymorphic effects and letpolymorphism, and our solution to gain type safety under those features. Section 3 defines surface language and Section 4 does intermediate language and elaboration from to . We also state that the elaboration is typepreserving and is type sound in Section 4. Finally, we discuss related work in Section 5 and conclude in Section 6. The proofs of the stated properties and the full definition of the elaboration are given in Appendix.
2 Overview
We start with reviewing how monomorphic algebraic effects and handlers work through examples and then extend them to a polymorphic version. We also explain why polymorphic effects are inconsistent with letpolymorphism, if naively combined, and how we resolve it.
2.1 Monomorphic algebraic effects and handlers
Exception.
Our first example is exception handling, shown in an MLlike language below.
Some and None are constructors of datatype option. Line 1 declares an effect operation fail, which signals that an anomaly happens, with its signature , which means that the operation is invoked with the unit value (), causes some effect, and may return the unit value. The function div100, defined in Lines 3–5, is an example that uses fail; it returns the number obtained by dividing 100 by argument x if x is not zero; if x is zero, otherwise, it raises an exception by calling effect operation fail.^{1}^{1}1Here, “; 1” is necessary to make the types of both branches the same; it becomes unnecessary when we introduce polymorphic effects. In general, we write #op() for invoking effect operation op with argument . The function f (Lines 7–10) calls div_100 inside a handle–with expression, which returns Some if div_100 returns integer normally and returns None if it invokes fail.
An expression of the form handle with handles effect operations invoked in (we call handled expression) according to the effect interpretations given by handler . A handler consists of two parts: a single return clause and zero or more operation clauses. A return clause return x will be executed if the evaluation of results in a value . Then, the value of (where x is bound to ) will be the value of the entire handle–with expression. For example, in the program above, if a nonzero number is passed to f, the handle–with expression would return Some because div100 returns . An operation clause x defines an implementation of effect op: if the evaluation of handled expression invokes effect op with argument , expression will be evaluated after substituting for x and the value of will be the value of the entire handle–with expression. In the program example above, if zero is given to f, then None will be returned because div100 0 invokes fail.
As shown above, algebraic effect handling is similar to exception handling. However, a distinctive feature of algebraic effect handling is that it allows resumption of the computation from the point where an effect operation was invoked. The next example demonstrates such an ability of algebraic effect handlers.
Choice.
The next example is effect choose, which returns one of the given two arguments.
As usual, is a product type, (,) is a pair expression, and fst is the first projection function. The first line declares that effect choose is for choosing integers. The handled expression #choose(1,2) + #choose(10,20) intuitively suggests that there would be four possible results—11, 21, 12, and 22—depending on which value each invocation of choose returns. The handler in this example always chooses the first element of a given pair^{2}^{2}2We can think of more practical implementations, which choose one of the two arguments by other means, say, random values. and returns it by using a resume expression, so the expression in Line 3–5 evaluates to 11.
A resumption expression resume in an operation clause makes it possible to return a value of to the point where an effect operation was invoked. This behavior is realized by constructing a delimited continuation from the point of the effect invocation up to the handle–with expression that deals with the effect and passing the value of to the continuation. We illustrate it by using the program above. When the handled expression #choose(1,2) + #choose(10,20) is evaluated, continuation + #choose(10,20) is constructed. Then, the body resume (fst x) of the operation clause is evaluated after binding x to the argument (1,2) of the invocation. Receiving the value 1 of fst (1,2), the resumption expression passes it to the continuation ; as a result, is evaluated under the same handler. Next, choose is invoked with argument (10,20). Similarly, continuation is constructed and the operation clause for choose is executed again. Since fst (10,20) evaluates to 10, is evaluated under the same handler. Since the return clause returns what it receives, the entire expression evaluates to 11.
Finally, we briefly review how an operation clause involving resumption expressions is typechecked [13, 3, 16]. Let us consider operation clause op(x) for of type signature . The typechecking is performed as follows. First, argument x is assigned domain type of the signature as it will be bound to an argument of an effect invocation. Second, for resumption expression resume in , (1) is required to have codomain type of the signature because its value will be passed to the continuation as the result of the invocation and (2) the resumption expression is assigned the same type as the return clause. Third, the type of the body has to be the same as that of the return clause because the value of is the result of the entire handle–with expression. For example, the above operation clause for choose is typechecked as follows: first, argument x is assigned type intint; second, it is checked whether the argument fst x of the resumption expression has int, the codomain type of choose; third, it is checked whether the body resume (fst x) of the clause has the same type as the return clause, that is, int. Satisfying the all requirements, the clause is well typed.
2.2 Polymorphic algebraic effects and handlers
This section motivates polymorphism for algebraic effects and handlers. There are two ways to introduce polymorphism: by parameterized effects and by polymorphic effects.
The former is to parameterize the declaration of an effect by types. For example, one might declare:
An invocation #choose involves a parameterized effect of the form (where denotes a type), according to the type of arguments: For example, #choose(true,false) has effect bool choose and #choose(1,1) has int choose. Handlers are required for each effect .
The latter is to give a polymorphic type to an effect. For example, one may declare
In this case, the effect can be invoked with different types but all invocations have the same effect choose. One can implement a single operation clause that can handle all invocations of choose, regardless of argument types. Koka supports both styles [16] (with value restriction) but we focus on the latter in this paper. A type system for parameterized effects lifting value restriction is studied by Kammar and Pretnar [14] (see Section 5 for comparison).
In what follows, we show a polymorphic version of the examples we have seen, along with brief discussions how polymorphic effects help reasoning about effect implementations. Other practical examples of polymorphic effects can be found in Leijen’s work [16].
Polymorphic exception.
First, we extend the exception effect fail with polymorphism.
The polymorphic type signature of effect fail, given in Line 1, means that the codomain type can be any. Thus, we do not need to append the dummy value 1 to the invocation of fail by instantiating the bound type variable with int (the shaded part).
Choice.
Next, let us make choose polymorphic.
The function random_walk implements random walk; it takes the current coordinate x, chooses whether it stops, and, if it decides to continue, recursively calls itself with a new coordinate. In the definition, choose is used twice with different types: bool and int. Lines 11–12 give choose an interpretation, which calls rand to obtain a random float,^{3}^{3}3One might implement rand as another effect operation. and returns either first or second element of y.
Typechecking of operation clauses could be extended in a straightforward manner. That is, an operation clause op(x) for an effect operation of signature would be typechecked as follows: first, is locally assigned in the clause and is assigned type ; second, an argument of a resumption expression must have type (which may contain type variable ); third, must have the same type as the return clause (its type cannot contain as is local) under the assumption that resumption expressions have the same type as the return clause. For example, let us consider typechecking of the above operation clause for choose. First, it allocates a local type variable and assigns type to y. The body has two resumption expressions, and it is checked whether the arguments fst y and snd y have codomain type of the signature. Finally, it is checked whether the body is typed at int assuming that the resumption expressions have type int. The operation clause meets the all requirements, so it would be well typed.
An obvious advantage of polymorphic effects is reusability. Without polymorphism, one has to declare many versions of choose for different types.
Another pleasant effect of polymorphic effects is that, thanks to parametricity, inappropriate implementations for an effect operation can be excluded. For example, it is not possible for an implementation of choose to resume with values other than the first or second element of y. In the monomorphic version, however, it is possible to resume with any integer, as opposed to what the name of the operation suggests. A similar argument applies to fail; since the codomain type is , which does not appear in the domain type, it is not possible to resume! In other words, the signature enforces that no invocation of fail will return.
2.3 Problem in naive combination with letpolymorphism
While polymorphic effects and handlers give an ability to abstract and restrict effect implementations, one may easily expect that their unrestricted use with naive letpolymorphism, which allows any letbound expressions to be polymorphic, breaks type safety. Indeed it does.
We develop a counterexample, inspired by Harper and Lillibridge [11], below.
The function f first binds g to the invocation result of op. The expression #get_id() is given type and naive letpolymorphism would assign type scheme to g, which makes both g true and g 0 (and so the definition of f) well typed.
An intended use of f is as follows:
The operation clause for get_id resumes with the identity function z.z. It would be well typed under the typechecking procedure described in Section 2.2 and it safely returns 1.
However, the following strange expression
will get stuck, although this expression would be well typed: both z1. ;z1 and z2. z1 could be given type by assigning both z1 and z2 type , which is the type variable local to this clause. Let us see how the evaluation gets stuck in detail. When the handled expression f () invokes effect get_id, the following continuation will be constructed:
Next, the body of the operation clause get_id is evaluated. It immediately resumes and reduces to
where
which is the continuation under the same handler. The evaluation proceeds as follows (here, ):
Here, the hole in is filled with function (z2.true) which returns a Boolean value, though the hole is supposed to be filled by a function of . This weird gap triggers a runtime error:
We stop here because true + 1 cannot reduce.
2.4 Our solution
Standard approaches to this problem are to restrict the form of letbound expressions by some means such as (relaxed) value restriction [23, 24, 10] or weak polymorphism [1, 12]. These approaches amount to restricting how effect operations can be used.
In this paper, we seek for a complementary approach, which is to restrict how effect operations can be implemented.^{4}^{4}4We compare our approach with the standard approaches in Section 5 in detail. More concretely, we develop a type system such that letbound expressions are polymorphic as far as they invoke only “safe” polymorphic effects and the notion of safe polymorphic effects are formalized in terms of typing rules (for handlers).
To see what are “safe” effects, let us examine the above counterexample to type safety. The crux of the counterexample is that

continuation uses g polymorphically, namely, as in g true and in g 1;

is invoked twice; and

the use of g as in the first invocation of —where g is bound to z1.; z1—“alters” the type of z2. z1 (passed to resume) from to , contradicting the second use of g as in the second invocation of .
The last point is crucial—if z2.z1 were, say, , there would be no influence from the first invocation of and the evaluation would succeed. The problem we see here is that the naive type system mistakenly allows interference between the arguments to the two resumptions by assuming that z1 and z2 share the same type.
Based on this observation, the typing rule for resumption is revised to disallow interference between different resumptions by separating their types: for each resume in the operation clause for , has to have type obtained by renaming all type variables in with fresh type variables . In the case of get_id, the two resumptions should be called with and for fresh and ; to make the first resume well typed, z1 has to be of type but it means that the return type of z2.z1 (given to the second resumption) is , making the entire clause ill typed, as we expect. If a clause does not have interfering resumptions like
get_id y resume (z1.z1)
or
get_id y resume (z1. (resume (z2.z2)); z1),
it will be well typed.
3 Surface language:
We define a lambda calculus that supports letpolymorphism, polymorphic algebraic effects, and handlers without interfering resumptions. This section introduces the syntax and the type system of . The semantics is given by elaboration to intermediate calculus , which will be introduced in Section 4.
3.1 Syntax
The syntax of is given in Figure 1. Effect operations are denoted by and type variables by , , and . An effect, denoted by , is a finite set of effect operations. We write for the empty effect set. A type, denoted by , , , and , is a type variable, a base type , which includes, e.g., and , or a function type , which is given to functions that take an argument of type and computes a value of type possibly with effect . A type scheme is obtained by abstracting type variables. Terms, denoted by , consist of variables, constants (including primitive operations), lambda abstractions , which bind in , function applications, letexpressions , which bind in , effect invocations , – expressions , and resumption expressions . All type information in is given implicit, so the terms have no type annotations. A handler has a single return clause , where is bound in , and zero or more operation clauses of the form , where is bound in . A typing context binds a sequence of variable declarations and type variable declarations .
We introduce the following notations used throughout in this paper. We write for where . We often omit indices ( and ) and index sets ( and ) if they are not important: for example, we often abbreviate to or even . Similarly, we use a bold font for other sequences ( for a sequence of types, for a sequence of values, and so on). We sometimes write to view the sequence as a set by ignoring the order. Free type variables in a type scheme and type substitution of for type variables in are defined as usual (with understanding that the omitted index sets for and are the same).
We suppose that each constant is assigned a firstorder closed type of the form and that each effect operation is assigned a signature of the form , which means that an invocation of with type instantiation takes an argument of and returns a value of . We also assume that, for , and .
3.2 Type system
The type system of consists of four judgments: wellformedness of typing contexts ; well formedness of type schemes ; term typing judgment , which means that computes a value of possibly with effect under typing context and resumption type (discussed below); and handler typing judgment , which means that handles computation that produces a value of with effect and the clauses in computes a value of possibly with effect under and . A resumption type contains type information for resumption.
Definition 1 (Resumption type)
Resumption types in , denoted by , are defined as follows.
If is not a subterm of an operation clause, it is typechecked under , which means that cannot contain resumption expressions. Otherwise, suppose that is a subterm of an operation clause that handles effect of signature and computes a value of possibly with effect . Then, is typechecked under , which means that argument to the operation clause has type and resumptions in are effectful functions from to with effect . Note that type variables occur free only in and and do not occur in .
Figure 2 shows the inference rules of the judgments (except for , which is defined by: if and only if all free type variables in are bound by ). For a sequence of type schemes , we write if and only if every type scheme in is well formed under .
Wellformedness rules for typing contexts, shown at the top of Figure 2, are standard. A typing context is well formed if: it is empty (WF_Empty); or a variable in the typing context is associated with a type scheme which is well formed in the remaining typing context (WF_Var) and a type variable in the typing context is not declared (WF_TVar). For typing context , denotes the set of type and term variables declared in .
Typing rules for terms are given in the middle of Figure 2. The first six rules are standard for the lambda calculus with letpolymorphism and a typeandeffect system. If a variable is introduced by a letexpression and has type scheme in , it is given type , obtained by instantiating type variables with wellformed types . If is bound by other constructors (e.g., a lambda abstraction), is always bound to a monomorphic type and both and are the empty sequence. Note that (TS_Var) gives any effect to the typing judgment for . In general, in judgment means that evaluation of may invoke effect operations in . Since a reference to a variable involves no effect, it is given any effect; for the same reason, value constructors are also given any effect. The rule (TS_Const) means that the type of a constant is given by (metalevel) function . The typing rules for lambda abstractions and function applications are standard in the lambda calculus equipped with a typeandeffect system. The rule (TS_Abs) gives lambda abstraction function type if computes a value of possibly with effect by using of type . The rule (TS_App) requires that (1) the argument type of function part be equivalent to the type of actual argument and (2) effect invoked by function be contained in the whole effect . The rule (TS_Weak) allows weakening of effects.
The next two rules are mostly standard for algebraic effects and handlers. The rule (TS_Op) is applied to effect invocations. Since supports implicit polymorphism, an invocation of polymorphic effect of signature also accompanies implicit type substitution of wellformed types for . Thus, the type of argument has to be and the result of the invocation is given type . In addition, effect contains . Typeability of – expressions depends on typing of handlers (TS_Handle), which will be explained below shortly.
The last typing rule (TS_Resume) is the key to gain type safety in this work. Suppose that we are given resumption type . Intuitively, is the type of the continuation for resumption and so argument to is required to have type . As we discussed in Section 2, we avoid interference between different resumptions by renaming , type parameters to the effect operation, to fresh type variables , in typechecking . Freshness of will be ensured when wellformedness of typing contexts is checked at leaves of the type derivation. The type variables in the type of , the parameter to the operation, is also renamed in order for to be useful in . To see why this renaming is useful, let us consider an extension of the calculus with pairs and typechecking of an operation clause for of signature :
Variable is assigned product type for fresh type variable and the body is typechecked under the resumption type for some and (see the typing rules for handlers for detail). To typecheck , the argument is required to have type , freshly generated for this . Without applying renaming also to , the clause would not typecheck. Finally, (TS_Resume) also requires that (1) the typing context contains , which should have been declared at an application of the typing rule for the operation clause that surrounds this and (2) effect , which may be invoked by resumption of a continuation, be contained in the whole effect .
The typing rules for handlers are standard [13, 3, 16]. The rule (THS_Return) for a return clause checks that the body is given a type under the assumption that argument has type , which is the type of the handled expression. The effect stands for effects that are not handled by the operation clauses that follow the return clause and it must be a subset of the effect that may cause.^{5}^{5}5Thus, handlers in are open [13] in the sense that a – expression does not have to handle all effects caused by the handled expression. A handler having operation clauses is typechecked by (THS_Op), which checks that the body of the operation clause for of signature is typed at the result type , which is the same as the type of the return clause, under the typing context extended with fresh assigned type variables and argument of type , together with the resumption type . The effect in the conclusion means that the effect operation is handled by this clause and no other clauses (in the present handler) handle it. Our semantics adopts deep handlers [13], that is, when a handled expression invokes an effect operation, the continuation, which passed to the operation clause, is wrapped by the same handler. Thus, resumption may invoke the same effect as the one possibly invoked by the clauses of the handler, hence in the resumption type.
Finally, we show how the type system rejects the counterexample given in Section 2. The problem is in the following operation clause.
where has effect signature . This clause is typechecked under resumption type for some . By (TS_Resume), the two resumption expressions are assigned two different type variables and , and the arguments and are required to have and , respectively. However, cannot because is associated with but not .
Remark.
The rule (TS_Resume) allows only the type of the argument to an operation clause to be renamed. Thus, other variables bound by, e.g., lambda abstractions and letexpressions outside the resumption expression cannot be used as such a type. As a result, more care may be required about where to introduce a new variable. For example, let us consider the following operation clause (which is a variant of the example of choice above).
The variable is assigned first and the resumption requires to be typed at fresh type variable . This clause would be rejected in the current type system because appears outside and so is given type , not . This inconvenience may be addressed by hoisting down the letbinding in some cases: For example, is well typed.
4 Intermediate language:
The semantics of is given by elaboration to an intermediate language , where type abstraction and type application appear explicitly. We define the syntax, operational semantics, and type system of and formal elaboration from to . Finally, we show type safety of via type preservation of the elaboration and type soundness of .
4.1 Syntax
The syntax of is shown in Figure 3. Values, denoted by , consist of constants and lambda abstractions. Polymorphic values, denoted by , are values abstracted over types. Terms, denoted by , and handlers, denoted by , are the same as those of except for the following three points. First, type abstraction and type arguments are explicit in : variables and effect invocations are accompanied by a sequence of types and letbound expressions, resumption expressions, and operation clauses bind type variables. Second, a new term constructor of the form is added. It represents an intermediate state in which an effect invocation is capturing the continuation up to the closest handler for . Here, is an evaluation context [6] and denotes a continuation to be resumed by an operation clause handling . In the operational semantics, an operation invocation is first transformed to (where denotes the empty context or the identity continuation) and then it bubbles up by capturing its context and pushing it onto the third argument. Note that and of become polymorphic when it bubbles up from the body of a type abstraction. Third, each resumption expression declares distinct (type) variables and to denote the (type) argument to an operation clause, whereas a single variable declared at and implicit type variables are used for the same purpose in . For example, operation clause is translated to . This change simplifies the semantics.
Evaluation contexts, denoted by , are standard for the lambda calculus with callbyvalue, lefttoright evaluation except for two points. First, they contain the form , which allows the body of a type abstraction to be evaluated. Second, the metavariable for evaluation contexts is indexed by type variables , meaning that the hole in the context appears under type abstractions binding . For example, is denoted by and, more generally, is by . (Here, stands for the concatenation of the two sequences and .) If is not important, we simply write for . We often use the term “continuation” to mean “evaluation context,” especially when it is expected to be resumed.
As usual, substitution of for in is defined in a captureavoiding manner. Since variables come along with type arguments, the case for variables is defined as follows:
Application of substitution to where is undefined. We also define free type variables and in and , respectively, as usual.
4.2 Semantics
Reduction rules
Evaluation rules
The semantics of is given in the smallstep style and consists of two relations: the reduction relation , which is for basic computation, and the evaluation relation , which is for toplevel execution. Figure 4 shows the rules for these relations. In what follows, we write for the return clause of handler , for the set of effect operations handled by , and for the operation clause for in .
Most of the reduction rules are standard [13, 16]. A constant application reduces to (R_Const), where function maps a pair of constants to another constant. A function application and a letexpression reduce to (R_Beta) and (R_Let), respectively. If a handled expression is a value , the – expression reduces to the body of the return clause where is substituted for the parameter (R_Return). An effect invocation reduces to with the identity continuation, as explained above (R_Op); the process of capturing its evaluation context is expressed by the rules (R_OpApp1), (R_OpApp2), (R_OpOp), (R_OpHandle), and (R_OpLet). The rule (R_OpHandle) can be applied only if the handler does not handle . The rule (R_OpLet) is applied to a letexpression where appears under a type abstraction with bound type variables . Since and may refer to , the reduction result binds in both and . We write for a sequence , …, of type schemes (where ).
The crux of the semantics is (R_Handle), which is applied when reaches the handler that handles . Since the handled term is constructed from an effect invocation , if the captured continuation binds type variables , the same type variables should have been added to and along the capture. Thus, the handled expression on the LHS of the rule takes the form
Comments
There are no comments yet.