Monadic Intersection Types, Relationally

Abstract

We extend intersection types to a computational $\lambda$-calculus with algebraic operations à la Plotkin and Power. We achieve this by considering monadic intersections—whereby computational effects appear not only in the operational semantics, but also in the type system. Since in the effectful setting termination is not anymore the only property of interest, we want to analyze the interactive behavior of typed programs with the environment. Indeed, our type system is able to characterize the natural notion of observation, both in the finite and in the infinitary setting, and for a wide class of effects, such as output, cost, pure and probabilistic nondeterminism, and combinations thereof. The main technical tool is a novel combination of syntactic techniques with abstract relational reasoning, which allows us to lift all the required notions, e.g. of typability and logical relation, to the monadic setting.

1 Introduction

Type systems are a key aspect of programming languages, ensuring good behavior during the execution of programs, such as absence of errors, termination, or properties such as productivity, safety, and reachability. Additionally, they ensure it in a compositional way, that is, if programs are assembled according to the underlying type discipline, then the good behavior is ensured also for the composed program.

Intersection Types. Type systems have solid roots in logic and proof theory, as witnessed by the Curry-Howard correspondence between simple types and intuitionistic natural deduction. However, in the theory of the $\lambda$-calculus, there is another use of types that has been studied at length: intersection types. They were introduced by Coppo and Dezani-Ciancaglini in the late 70’s [16] to overcome the limitations of Curry’s type discipline and enlarge the class of terms that can be typed. This is reached by means of a new type constructor, the intersection. In this way, one can assign a finite set of types to a term, thus providing a form of finite polymorphism.

Similarly to simple types, intersection types ensure termination. In contrast to most notions of types, however, they also characterize termination, that is, they type all terminating $\lambda$-terms. They can be seen as a compositional way of defining operational semantics, or, in a dual way, as a syntactic presentation of denotational models. Additionally, intersection types have shown to be remarkably flexible, since different termination forms can be characterized by tuning details of the type system (e.g., weak/strong full normalization, head/weak/call-by-value evaluation). Termination being only semi-decidable, type inference cannot be decidable, which is why standard intersection types are somewhat incompatible with programming practice, although some restricted forms of intersection types have found applications in programming, see for example [28, 33, 34, 53], or the recent survey by Bono and Dezani-Ciancaglini [12].

Beyond the Pure $\boldsymbol{\lambda }$-Calculus. Intersection types have been mostly developed in the realm of the pure $\lambda$-calculus. However, current programming languages are deeply effectful, exhibiting several simultaneous impure behaviours, such as raising exceptions, performing input/output operations, sampling from distributions, etc. Reasoning about effectful programs becomes a challenging goal since their behaviour becomes highly interactive, depending on the external environment. Type-based techniques seem very interesting in this respect, since they enable modular and compositional analysis of program behaviour. In particular, intersection type systems have already been successfully adapted to some concrete computational effects, such as probabilistic [13, 18], and pure nondeterminism [65]. In spite of the remarkable results achieved by each of these formalisms – for instance, probabilistic intersection types have been proved to characterize almost-sure termination – all of these come with a major drawback: they are tailored to the specific family of effects considered. This results in a lack of robustness and modularity when it comes to extending languages with new effects. For instance, probabilistic intersection types as they are, cannot cope with, e.g., languages with both randomness and output. This problem can be fixed (output is a well-behaved effect that nicely interacts with probabilistic nondeterminism) but in highly non-modular way. One has, in fact, to re-engineer the whole theoretical framework behind probabilistic intersection types to account for output, too.

Now, the leading question is: can intersection types be scaled up in the case of effectful $\lambda$-calculi, in a modular way? In this paper, we answer this question in the affirmative by developing a general monadic intersection type system for an untyped computational $\lambda$-calculus  [50, 51] with algebraic operations à la Plotkin and Power [57]. In fact, our system covers both finitary and infinitary effectful operational behaviours in a sound and complete way, and generalises existing effectful intersection type systems, such as probabilistic intersection types. To achieve this result, we combine state-of-the-art techniques in monadic semantics, intersection types, and relational reasoning, in a novel and nontrivial way.

Monadic Semantics. As we have already mentioned, our work is grounded on the theoretical framework pioneered by Moggi [50, 51], which describes computational effects via monads [49]. Moggi’s work described how monads could give denotational semantics to effectful programs, but did not tell anything about how computational effects are actually produced. Plotkin and Power [57, 58] introduced algebraic effects as a way of giving monadic semantics, in the style of Moggi, to certain operations which actually produce computational side effects. The core syntax of effectful languages can be thus given in terms of computational calculi with effect-triggering operations. But what about the operational semantics and, most importantly, the (intersection) type system?

There is a well-known way to give effectful operational semantics to programming languages, namely making operational semantics effectful itself. That is, if we model the operational semantics of a language using a transition relation between terms, then we can make such a relation monadic by relating terms with monadic terms, i.e. terms encapsulated by a monad, encoding the effects produced during the computation. Such relations—i.e. relations of the form $R\subseteq A \times T(B)$, with T a monad—are known as monadic or Kleisli relations and have been successfully used to give operational semantics to monadic calculi [36].

What about the type system? In its bare essence, it is given by a relation between terms and types, hence leading to a situation similar to the one of operational semantics. The analogy is no coincidence: as we obtain monadic operational semantics relying on the theory of monadic relations, the very same theory allows us to define monadic type systems: a monadic typing relation associates terms with monadic types. This idea has already been exploited by Dal Lago and collaborators [13, 18], who realised that to extend intersection types to probabilistic languages one has to type expressions not with types, but with distribution of types.¹ This is nothing but a monadic typing relation instantiated to the distribution monad.

Relational Reasoning. Working at the abstract level of monadic relations gives several advantages, both in terms of modularity and expressiveness. Concerning the former, we shall develop abstract proof techniques that allow us to give proofs of subject reduction and expansion independently of the underlying monad. Such factorization results rely on the theory of (monadic) relational extensions. Here, one studies how to extend a monadic relation $R\subseteq A \times T(B)$, such as the one modeling one-step operational semantics, or typing between terms and monadic types, to a relation $R^{\dagger } \subseteq T(A) \times T(B)$, necessary to model operational semantics, or typing, of monadic terms. Such extensions, even if canonical, do not exist in general, and a celebrated result by Barr [10] gives necessary and sufficient conditions for the existence of relational extensions: monads must be weakly cartesian [15, 71]. Intuitively, being weakly cartesian means that during the evaluation there is no loss of information about the performed effects. This is a form of reversibility, that is needed, e.g., in subject expansion,

This restriction rules out from our analysis monads such as the powerset or the distribution monad. Although that may appear as a weakness of our framework, it actually exploits a nontrivial limitative result that has already been observed in different forms in the literature: results involving forms of reversibility, such as subject expansion, are simply not available when monads are not weakly cartesian. This is the deep reason why probabilistic intersection types are defined via the multi-distribution, rather than distribution, monad. Remarkably, the same kind of limitative result has also been proved in the setting of monadic operational semantics and rewriting [36].

Contributions. In this paper, we introduce the first (to the best of our knowledge) intersection type system handling the computational $\lambda$-calculus with algebraic operations. This is done by letting not only terms, but also intersection types be monadic. The main idea of intersection types is that they are a static way to describe the mechanism of evaluation of programs. Since the operational semantics of effectful languages can be conveniently described by evaluation inside monads, it is natural to embed also intersection types inside them. This way, we are able to push forward the correspondence between intersection type derivations and term evaluation to the effectful/monadic setting. More precisely, we develop several contributions and theoretical advances:

• The Type System: We provide the first idempotent² intersection type system for a $\lambda$-calculus with algebraic operations which is parametric in the underlying monad. We design the type system in such a way that not only terms, but also types become monadic.

• Characterization of Observable Behavior: Differently from the pure untyped setting, in which intersection types characterize (different forms of) termination of programs, in the effectful setting we would like to characterize via the type system all the effects produced during the evaluation. Indeed, we obtain such a result by generalizing standard soundness and completeness theorems, via abstract relational techniques. In particular, observable behaviors of typable (i.e. all the terminating) terms can be read out of their types.

• Intrinsic Limits: Our approach comes with the already described intrinsic limits about the class of well-behaving monads (the weakly cartesian ones). Moreover, if one sticks with the finitary case, where the natural notion of convergence is must termination, another restriction on the kinds of admissible operations is needed. Indeed, also operations that erase arguments break the subject expansion, and thus the completeness of the system. Still, this restriction can be removed considering an infinitary semantics.

• The Infinitary Case: Some interesting notions of observation, such as the probability of convergence in probabilistic calculi, are naturally infinitary. For this reason, we extend our type system to capture infinitary behaviors. Interestingly, we need to add just one typing rule to the previous (finitary) system, namely the one that can type every term with the bottom of the monad. Naturally, this extension requires the monads to satisfy more conditions (mainly domain theoretic ones). Remarkably, this way we are actually able to relax the constraint on non-erasing operations introduced in the finitary system.

Related Work. To the best of our knowledge, this is the first work about monadic intersection type systems for effectful calculi with algebraic operations, which are parametric on the underlying monad. On an orthogonal axis, an intersection type system for a variant over Moggi’s computational $\lambda$-calculus, but without any reference to algebraic operations, has been proposed in [25], while intersections types have developed for calculi with continuations in [9] and, paired with union types, in [45]. With concrete monads, instead, various proposals have appeared for the state monad [5, 26, 27, 29], and the distribution monad [13, 18, 31]. Moreover, lifting the monad to the type system has already been done in a series of works by Dal Lago and coauthors, e.g. to analyze complexity [6, 22] and recently for the state monad in [5]. More on the programming side, intersection types have been proposed for a $\lambda$-calculus with computational side effects and reference types in [23], but without any reference to monads.

Proofs. Omitted proofs are in the technical report [37].

2 Intersection Types and the CbV $\lambda$-Calculus

We devote this section to a gentle introduction to intersection type systems. For the moment, we do not consider effectful calculi and we set our analysis in the (almost) standard setting of Plotkin’s call-by-value (CbV) $\lambda$-calculus [55]. Actually, the calculus we present is the kernel of CbV $\lambda$-calculus, that is as expressive as the Plotkin’s [2, 32], but allows only a restricted form of term application.

The (kernel) CbV $\boldsymbol{\lambda }$-Calculus. Given a countable set of variables $\mathcal {V}$, values and computations are defined by mutual induction as follows:

Free and bound variables are defined as usual: $\lambda x.t$ binds $x$ in $t$. Terms are considered modulo $\alpha$-equivalence. Capture-avoiding (meta-level) substitution of $u$ for all the free occurrences of $x$ in $t$ is written $t\{x/u\}$. As it is customary when working in the CbV setting, we restrict ourselves to closed terms, i.e., we consider only terms without free variables. This means that the normal forms are all and only the closed values, noted , i.e. the $\lambda$-abstractions. The traditional $\beta$ rule is restricted to values, i.e. only (closed) values can be substituted: $(\lambda x.t)v\rightarrowtail t\{x/v\}$. The deterministic operational semantics $\mapsto$ is obtained by closing the $\beta$ rule (by value) $\rightarrowtail$ w.r.t. all evaluation contexts. Please notice that although we restricted term application to have a value as the left subterm, we can recover the usual application between terms as $tu:=(\lambda x.xu)t$, where $x$ is a fresh variable.

Fig. 1.

The intersection type system for closed call-by-value.

Intersection Types for the CbV $\boldsymbol{\lambda }$-Calculus.The CbV $\lambda$-Calculus is a universal, i.e. Turing complete, model of computation. This way its halting problem is obviously undecidable. Nonetheless, terminating terms can be characterized by syntactic means. Intersection types are one way of doing this, in a compositional and logical way. The grammar of types is reminiscent of the call-by-value translation $(\cdot )^\texttt{v}$ of intuitionistic logic into linear logic [30, 38] $(A\rightarrow B)^\texttt{v}=\,!(A^\texttt{v})\multimap \, !(B^\texttt{v})$. Semantically, they can be seen as a syntactical presentation of filter models of the $\lambda$-calculus [17]. The grammar for types is based on two layers of types, defined in a mutually recursive way, value types $A$, and intersections (i.e. sets) $I$ of value types.

Remark 1

Please notice that intersections can be empty. The empty intersection type $\textbf{0}:=\{\}$ stands for the type of erasable terms, which in Closed CbV are just those terms evaluating to closed values (i.e. $\lambda$-abstractions). In CbV, terminating terms and erasable terms coincide, as the argument of a $\beta$-reduction has to be evaluated before being erased (and so its evaluation has to terminate).

Type environments, ranged over by $\varGamma ,\varDelta$, are total maps from variables to intersection types such that only finitely many variables are mapped to non-empty intersection types, and we write $\varGamma = x_1:I_1,\ldots ,x_n:I_n$ if $\textsf{dom}(\varGamma )= \{x_1,\ldots ,x_n\}$. Type judgments have the form $\varGamma \vdash t:G$. The typing rules are in Fig. 1, where F stands for a finite, possibly empty, set of indexes; type derivations are written $\pi$ and we write $\pi \;\triangleright \,\varGamma \vdash t:G$ for a type derivation $\pi$ with the judgment $\varGamma \vdash t:G$ as its conclusion.

Intuitively, intersections are needed because, during the evaluation of a term $t$, a subterm of $t$ can assume different types. For example in $(\lambda x.xx)(\lambda y.y)$, the argument $\lambda y.y$ has type $\textbf{0}\rightarrow \textbf{0}$, when it substitutes the first occurrence of $x$ in functional position, and has type $\textbf{0}$ when it substitutes the second occurrence of $x$ in argument position. These different uses, which require different types, are encoded into the intersection type. Moreover, the type system, contrarily to what happens in call-by-name, and consistently with the rationale of CbV, needs arguments of applications to be typed (with an intersection) just once.

Example 1

We provide the type derivation for the term $\vdash (\lambda x.xx)(\textsf{II}):\textbf{0}$, where $\textsf{I}:=\lambda x.x$, in Fig. 2. One can notice that our example term, being CbV-normalizing, can be typed with $\textbf{0}$.

Fig. 2.

Type derivation for $\vdash (\lambda x.xx)(\textsf{II}):\textbf{0}$. We set $\texttt{id}:=\textbf{0}\rightarrow \textbf{0}$.

Characterization of Termination. Intersection types characterize Closed CbV termination, that is, they type all and only those $\lambda$-terms that terminate with respect to Closed CbV. We give a very brief overview of how this result is achieved. In the following sections, we shall prove all these results in the effectful setting. The reader could, however, benefit from the exposition of the main steps in this simpler setting.

Similarly to more traditional type systems, this intersection type system enjoys subject reduction, i.e. types are preserved under reduction.

Lemma 1 (Subject Reduction)

[Subject Reduction] Let $t$ be a closed $\lambda$-term. If $\vdash t:I$ and $t\mapsto u$, then $\vdash u:I$.

Moreover, as with simple types, all typable terms terminate.

Proposition 1 (Soundness)

[Soundness] Let $t$ be a closed $\lambda$-term. If $\vdash t:I$, then $t$ has normal form.

Contrarily to simple types, intersection types satisfy also subject expansion. This means that types are preserved also by backward reductions (i.e. expansions).

Lemma 2 (Subject Expansion)

[Subject Expansion] Let $t$ be a closed $\lambda$-term. If $\vdash u:I$ and $t\mapsto u$, then $\vdash t:I$.

Together with the fact that normal forms, i.e. $\lambda$-abstractions, can always be typed with the empty type $\textbf{0}$, this gives the completeness of the type system, i.e. the fact that every terminating term is typable.

Proposition 2 (Completeness)

[Completeness] Let $t$ be a closed $\lambda$-term. If $t$ has normal form, then there exists an intersection type $I$ such that $\vdash t:I$.

Putting soundness and completeness together, we obtain the full characterization of termination via typability.

Theorem 1 (Characterization)

[Characterization] Let $t$ be a closed $\lambda$-term. Then there exists an intersection type $I$ such that $\vdash t:I$ if and only if $t$ has normal form.

3 Preliminaries on Monads, Algebraic Effects, Operations

In this section, we recall some preliminary notions on monads [49], algebras [60], and relational reasoning [61], that will be central to the rest of this paper. Due to space constraints, there is no hope to be comprehensive, and thus we assume the reader to have minimal familiarity with those fields. Unless explicitly stated, we work in the category $\textbf{Set}$ of sets and functions and we tacitly restrict all definitions to it. Since we will extensively work with relations, we employ the relational notation even for functions, writing $f;g: A \rightarrow C$ for the composition (in diagrammatic order) of $f: A \rightarrow B$ and $g: B \rightarrow C$, and $\boldsymbol{1}_A: A \rightarrow A$ (mostly omitting subscripts) for the identity function.

Monads and Algebraic Effects. We use monads [50, 51] to model computational effects.

Definition 1 (Monad)

[Monad] A monad (on $\textbf{Set}$) is a triple $(T, \eta , \mu )$ consisting of a functor $T$ (on $\textbf{Set}$) together with two natural transformations: $\eta : 1_{\textbf{Set}} \Rightarrow T$ (called unit) and $\mu : TT\Rightarrow T$ (called multiplication) subject to the following laws: $\eta ; \mu = T(\eta ); \mu = \boldsymbol{1}$ and $T(\mu ); \mu =\mu ;\mu$.

Given a monad $(T, \eta , \mu )$ we oftentimes identify it with its carrier functor. Moreover, we write $f^{\dagger }: T(A) \rightarrow T(B)$ for the Kleisli extension of $f: A \rightarrow T(B)$, where $f^{\dagger } :=T(f);\mu$, and for the binding operator induced by $-^{\dagger }$. Such an operator maps a monadic element $t \in T(A)$ and a monadic function $f: A \rightarrow T(B)$ to the monadic element $t \mathrel {[1]{>\!>=}}f$ in T(B) defined as $f^{\dagger }(t)$. It is well-known that using this construction a monad could be presented also as a Kleisli triple $(T, \eta , -^{\dagger })$, or with the bind operation instead of $\mu$, i.e. as  [70].

To model how actual effects are produced, Plotkin and Power [54, 58] introduced the notion of an algebraic operation, which we shall use to make calculi truly effectful.

Definition 2 (Algebraic Operation)

[Algebraic Operation] Given a monad $(T, \eta , \mu )$, an n-ary algebraic operation is a natural transformation $\alpha : T^n \Rightarrow T$ respecting the monad multiplication.

From an operational perspective, algebraic operations describe those operations whose execution is independent of the context in which they are executed.

Example 2 (Concrete Monads and Operations)

[Concrete Monads and Operations]

• 1. Divergent computations are modelled by the maybe or partiality monad $(\mathcal {E}, \eta , \mu )$, where $\mathcal {E}(A) :=A + \{\bot \}$, $\eta$ is the left injection $\iota _{\ell }$, and $\mu : ((A + \{\bot \}) + \{\bot \}) \rightarrow A + \{\bot \}$ sends $\iota _{\ell }(\iota _{\ell }(x))$ to $\iota _{\ell }(x)$, and all the rest to $\bot$. Therefore, an element in $\mathcal {M}A$ is either an element $a \in A$ (meaning that we have a terminating computation returning a), or the element $\bot$ (meaning that the computation diverges). As non-termination is an intrinsic feature of complete programming languages, we do not consider explicit operations to produce divergence. Nonetheless, notice that we might consider the constant $\bot$ as a zero-ary operation producing divergence (linguistically, this essentially corresponds to adding an always diverging constant $\texttt{diverge}$).

• 2. Replacing $\{\bot \}$ with a set of errors $Err$, we obtain the exception monad. Exceptions are produced by means of 0-ary operations $\texttt{raise}_{e}$ indexed by elements in $Err$.

• 3. Probabilistic computations are modelled by the (finitary) distribution monad $(\mathcal {D}, \eta , \mu )$, where $\mathcal {D}(X)$ is the set of distributions over X with finite support (where the support of a distribution $d\in \mathcal {D}(X)$ is defined as $\textsf{supp}(d):=\{x\in X\text { such that }d(x)>0\}$), $\eta (x)$ is the Dirac distribution on x, and $\mu (\varPhi )(x) :=\sum _{\phi } \varPhi (\phi ) \cdot \phi (x)$. Finite distributions are produced using weighted sums, i.e. [0, 1]-indexed binary operations $+_p$ defined thus: $(\phi _1 +_p \phi _2)(x) :=p \cdot \phi _1(x) + (1-p) \cdot \phi _2(x)$. In a similar fashion, one defines the finitary subdistribution monad $\mathcal {D}^{\le 1}$ and the countably supported (sub)distribution monad $\mathcal {D}_{\omega }^{(\le 1)}$. In the former case, we simply allow distribution to have weight smaller than 1, whereas in the latter case, we allow distributions to have a countable support (i.e. the set of elements where the distribution is non-null must be countable).

• 4. Computations with output are modelled by the writer or output monad $(\mathcal {W}, \eta , \mu )$, where $\mathcal {W}A = W \times A$ and $(W, 1, \cdot )$ is a monoid. Unit and multiplication are defined by $\eta (x) = (1,x)$ and $\mu (w, (v,x)) = (w\cdot v, x)$. Taking the monoid of words, then we can think of (w, x) as the result of a program printing w and returning x. If, instead, we take the monoid , then we obtain the cost or complexity monad [59], whereby we read (n, x) as the result of a computation that produces x with cost n. We consider a W-indexed family of unary operations $\texttt{out}_w$ defined by $\texttt{out}_w(v,x) = (w\cdot v,x)$. These are indeed algebraic. When dealing with cost, one usually considers the single operation $\texttt{out}_1$, usually written $\texttt{tick}$ or simply $\checkmark$.

• 5. We model nondeterminism using the powerset monad $(\mathcal {P}, \eta , \mu )$, where $\eta (x) = \{x\}$ and $\mu (\mathcal {U}) = \bigcup \mathcal {U}$. We generate nondeterminism using (binary) set-theoretic union, which is indeed algebraic. The finitary powerset monad is obtained from $\mathcal {P}$ by taking as underlying functor the finite powerset functor $\mathcal {P}_{ f }$. Similarly, the non-empty powerset monad $\mathcal {P}^{+}$ is obtained by the taking the non-empty powerset functor $\mathcal {P}^{+}$.

Most monads seen in Example 2 have countable support in the sense that whenever $t \in T(A)$ there exists a countable set $\textsf{supp}(t) \subseteq A$ upon which t is built. Such a set is called the support of t and generalises the notion of a support one has for distributions. In general, not all monads have support and thus we restrict our analysis to such monads. First, we consider only monads that preserve injections: that is, if $\iota : X \hookrightarrow A$ is an injection, then so is $T(\iota ): T(X) \hookrightarrow T(A)$. We regard $T(\iota )$ as a monadic inclusion and write $t \in T(X)$ if there exists (a necessarily unique) $s \in T(X)$ such that $T(\iota )(s) = t$. Notice that all monads of Example 2 preserves injections and that if a monad preserves weak pullbacks (a condition we shall exploit in Section 4), then it preserves injections.

Definition 3 (Support)

[Support]

• 1. Given an element $t \in T(A)$, the support of t, if it exists, is the smallest subset $\iota : X \hookrightarrow A$ such that $t \in T(X)$. We denote such a set by $\textsf{supp}(t)$.

• 2. We say that a monad T has countable (resp. finitary) support if any $t \in T(A)$ has countable (resp. finite) support — i.e. $\textsf{supp}(t)$ exists and it is countable (resp. finite) — for any set A.

Example 3

All the monads in Example 2 are countable, with the exception of the (non-finitary) powerset monads. Nonetheless, we can regard them as countable by taking their countable restriction. Indeed, as we shall apply them to countable sets (of terms), such a restriction is by no means a constraint. The output monad, the maybe monad, the finitary (sub)distribution monad, and the finitary powerset monad all have finitary support. For example, let us take the set of the probability distributions on natural numbers. If , applying the definition of support stated above, we obtain that the smallest set X such that $d\in \mathcal {D}(X)$, which is $X=\{5,7\}$. This set matches exactly the one obtained from the standard definition of support for probability distributions given in Example 2.

Algebraic Theories. Since effects are ultimately produced by algebraic operations, we oftentimes describe computational effects by means of algebraic theories, i.e. via a collection of operations and equations.

Recall that a signature $\varSigma$ is a family of sets , the elements $\sigma , \rho , \ldots$ of each $\varSigma _k$ being called k-ary operations. The set $T_{\varSigma }(X)$ of $\varSigma$-terms (just terms) over X is the least such that (1) $x \in T_{\varSigma }(X)$ for any $x \in X$, and (2) $\sigma (t_1, \ldots , t_n) \in T_{\varSigma }(X)$, whenever $t_1, \ldots , t_n \in T_{\varSigma }(X)$. The construction of $\varSigma$-terms defines a functor $T_{\varSigma }$ which is part of a monad whose unit is given by the subset inclusion injection $\iota : X \hookrightarrow T_{\varSigma }{X}$ and whose multiplication is given by term substitution.

An algebraic or equational theory over $T_{\varSigma }(X)$ is given by a relation $E \subseteq T_{\varSigma }(X) \times T_{\varSigma }(X)$ of equations between such terms. For a theory E, we write $\sim _{E}$ (or just $\sim$) for the least congruence relation on terms that is closed under term substitution and contains E. The free E-theory over X is the quotient of $T_{\varSigma }(X)$ by $\sim _{E}$. This construction gives a functor which is part of a monad, called the free theory monad of E.

Example 4 (Concrete Algebraic Theories)

[Concrete Algebraic Theories]

• 1. The theory of divergence has a single 0-ary operation and no equation. Its free theory monad gives the maybe monad.

• 2. The theory of nondeterminism consists of a single binary operation $\vee$ together with the usual join semilattice equations [1]. Its associated free theory monad gives the finitary non-empty powerset monad. If we drop the idempotency equation $x \vee x \sim x$, we obtain the theory of multisets [64] and the associated multiset monad. If we also drop commutativity, we obtain the theory of lists and the associated list monad.

• 3. The theory of probabilistic nondeterminism has binary operations $+_p$ indexed by rational numbers $0 \le p \le 1$ subject to the usual axioms of a barycentric algebra [63]:

  $$\begin{aligned} \begin{array}{c} x +_p x \sim x; \qquad \quad x +_1 y \sim x; \qquad \quad \,\, x +_p y \sim y +_{1-p} x; \\ x +_p (y +_q z) \sim (x +_{\frac{p}{p + (1-p)q}} y) +_{p + (1-p)q} z. \end{array} \end{aligned}$$

  The free theory monad of this theory gives the finitary distribution monad. The theory of multi-distribution or indexed valuations (and their corresponding monads) [7, 66, 67], is obtained by dropping the idempotency axiom $x +_p x \sim x$.

• 4. Fixing a monoid W, the theory of the writer monad has a unary operation $\texttt{out}_{w}$ for each $w \in W$, and equations

  $$\begin{aligned} \texttt{out}_1(x) \sim x & \qquad \qquad \texttt{out}_w(\texttt{out}_v(x)) \sim \texttt{out}_{w\cdot v}(x). \end{aligned}$$

Relations. We will extensively work with relations. We denote by $\textbf{Rel}$ the category with sets as objects and binary relations as arrows. As it is customary, we use the notation for a relation $R\subseteq A \times B$, and write $\textbf{Rel}(A,B)$ for the collection of relations of type . We tacitly regard each function f as a relation via its graph and write for the identity relation, the latter being the graph of the identity function. We furthermore denote by the composition of and , and by the dual or transpose of .

4 Monadic Intersection Types

In this section, we present the monadic extension of the intersection type system for CbV presented in Section 2.

Effectful CbV. The target calculus of the remaining part of this work is an effectful extension of the CbV $\lambda$-calculus previously introduced. We follow the methodology of algebraic effects [57] and fix a signature $\varSigma$ of effect triggering operations, as seen in the previous section. The calculus $\varLambda _{\varSigma }^{\textsf{cbv}}$ is obtained by extending the grammar of the (kernel) CbV $\lambda$-calculus as follows:

As before, we denote by and the collection of closed computations and values, respectively. Finally, we write for the subset of of redexes, i.e. computations of the form $(\lambda x.t)v$ or $\texttt{op}(t_1, \ldots , t_n)$.

We give an operational semantics to $\varLambda _{\varSigma }^{\textsf{cbv}}$ in monadic style [36, 56]. Let $(T, \eta , \mu )$ be an arbitrary but fixed monad with countable support. We assume that to each n-ary operation $\texttt{op}\in \varSigma$ it is associated a n-ary algebraic operation $g_\texttt{op}$ on T.

We define a function on closed terms that performs a single computation step (possibly performing effects) by first defining ground reduction and then closing the latter under evaluation contexts. To improve readability, we write $t \mathrel {{\mapsto }} e$ in place of ${{\mapsto }}(t) = e$ and we refer to elements in (resp. ) as monadic (or effectful) computations (resp. values).

Definition 4 (Operational Semantics)

[Operational Semantics] We define the function as follows:

The function is then defined as the contextual closure of $\rightarrowtail$, i.e. , where r is a redex and $r \mathrel {\rightarrowtail } e$.

In this last definition the symbol has to be intended as a meta-lambda notation, i.e. by we mean the function such that $h(u):=\eta (E[u])$. In particular, in the definition of the contextual closure we exploit the algebricity of the effects, making them commute with evaluation contexts. Moreover, notice that ${\mapsto }$ is indeed a function. Consequently, we can rely on its Kleisli extension ${\mapsto }^{\dagger }$ to reduce monadic computations. We write ${\mapsto }^n$ for the n-iteration of ${\mapsto }$, where ${\mapsto }^0 :=\eta$ and ${\mapsto }^{n+1} :={\mapsto }; ({\mapsto }^n)^{\dagger }$. In a similar fashion, we write ${\mapsto }^*$ for $\bigcup _n {\mapsto }^n$. Please notice that since algebraic operations are finitary, all monadic computations that a computation t can achieve in finite times have finite support, meaning that $t \mathrel {{\mapsto }^*} e$ implies that $\textsf{supp}(e)$ is finite.

Definition 5 (Finitary Convergence)

[Finitary Convergence] We say that a closed computation t converges if there exists such that .³ In that case, we write $\llbracket t \rrbracket = e$.

Please notice that $\llbracket \cdot \rrbracket$ is a partial function. Indeed, terms can diverge.

The Monadic Type System. The main idea behind the development of the type system is that not only terms, but also intersection types become monadic. The natural design choice is to follow the informal CbV translation of intuitionistic logic into linear logic combined with Moggi’s translation:

$$ A\rightarrow B\cong \; !A\multimap {T(!B)} $$

A third level of (monadic) types is then added to the grammar of types:

Fig. 3.

The monadic intersection type system.

We maintain all the notations already presented in Section 2 for the CbV type system. The typing rules are in Fig. 3. While rules $\textsc {abs},\textsc {var}$ and $\textsc {int}$ are almost unchanged, the other rules deserve some comments. The rule $\textsc {unit}$ is needed to give a monadic type to values. Since values do not produce any effect, they are injected into the monad just with $\eta$. Rule $\textsc {app}$ types applications $vt$ with a monadic type. The important point is that the subterm $v$ in function position has to be typed many times, one for each element in the support of the (monadic) type of the argument $t$. Please notice (i) that with the notation $\{I_i\Rightarrow M_i\}_{1\le i\le n}$ we mean the function that maps pointwise $I_i$ to $M_i$ for each $1\le i\le n$; and (ii) the operator at the level of types. This should not come unexpectedly, since types are monadic, and thus are composed using monadic laws. In particular, the effects produced by the argument, encoded in its type, have to be composed with the effects that will be generated by the rest of the computation (see the example below for more intuitions). Finally, rule $\textsc {op}$ types operations with the monadic type built with the corresponding algebraic operation, applied to the (monadic) types of the arguments of the operation itself.

Example 5

We provide in Fig. 4 the derivation for $\vdash (\lambda x.x(\texttt{out}_b(x)))(\texttt{out}_a(\textsf{II})):(ab,\textbf{0})$, which is the very same term as in Example 1, decorated with output operations. As monoid of words, we consider the monoid $\varSigma ^*$ freely generated from the alphabet $\varSigma :=\{a,b\}$. One can notice that the assigned type contains all the information about the symbols printed on the output buffer during the evaluation of the term. Please notice how types are composed in the last rule $\textsc {app}$. The right-hand side is typed only once, since the support of the monadic type on the left-hand side is a singleton. Notice that the bind operator in the case of the output monad is defined as: if $f(x)=(b,y)$. Intuitively, the usual composition is done, but for the fact that the strings (a and b in this case) are concatenated.

Fig. 4.

Type derivation for $\vdash (\lambda x.x(\texttt{out}_b(x)))(\texttt{out}_a(\textsf{II})):(ab,\textbf{0})$. We set $\texttt{id}:=\textbf{0}\rightarrow \eta (\textbf{0})=\textbf{0}\rightarrow (\varepsilon ,\textbf{0})$.

Relational Reasoning. To prove soundness and completeness of the monadic type system, we will need to reason both about expressions and monadic expressions. In fact, as long as we are interested in reduction sequences we have to deal both with terms, to start the sequence, and with their (monadic) reducts, to continue the computation. Working with monads, we have already seen that we can extend the dynamic semantic of $\varLambda ^{\textsf{cbv}}$ to monadic computations, for free. Computations, however, come both with a dynamic and static semantics (i.e. types); and if the former semantics (viz. ${\mapsto }$) extends to monadic computation (as ${\mapsto }^{\dagger }$), it is not immediately clear how to do the same with the latter. In fact, whereas ${\mapsto }$ is a function, the static semantics of $\varLambda ^{\textsf{cbv}}$, given by the typing relation $\vdash$, is genuinely relational, meaning that we cannot rely on the axioms of a monad to extend it.

Relational Extensions. We overcome this problem by relying on the notion of a relational extension of a monad [8, 10, 11, 14, 39, 42]. Remarkably, relational extensions come with powerful proof techniques, whereby one extends term-based results (such as subject reduction and expansion, in our case) to monadic terms essentially. All of that, however, has a price: relational extensions cannot be given for all monads. As long as we are interested in ‘forward properties’, such as subject reduction, it is enough to give a relaxed notion of relational extensions — called lax relational extensions — that is available for a large class of monads (such as all the ones seen so far). But if we ask for ‘backward properties’, such as subject expansion, then we need the full axiomatics of a relational extension. And by a well-known result by Barr [10], we know that a monad has a relational extension if and only if it is weakly cartesian [15, 71]. From an equational perspective, weakly cartesian monads are defined by affine theories [35], meaning that they cannot have equations that duplicate variables. This excludes important monads, such as the distribution and powerset monads. This way, one has to rely on their ‘linearization’ to obtain well-behaved intersection type systems. In the case of the distribution and powerset monad one does so simply by dropping the idempotency equations from their equational theories, thus obtaining the so-called multi-distribution [7, 18, 66, 67] and multiset monads [64]. It is important to stress that this is not a design issue, but an intrinsic limit of the model, as shown by Example 8 (below in this section).

Lifting the Type System. The type system in Figure 3 defines a dependent relation , where is the collection of terms of the calculus, and is the collection of terms with free variables among $\varGamma$. Notice that ${\vdash }$ respects syntactic categories, in the sense that since , we can see ${\vdash }$ as the sum of three relations , , and . In the following, we shall tacitly use this decomposition. Moreover, since type soundness and completeness refer to programs, we will mostly work with ${\vdash }$ restricted to closed terms (i.e. when $\varGamma$ is empty): in that case, ${\vdash }$ is just an ordinary binary relation.

When instantiated to monadic types (and closed computations), the relation is a so-called monadic relation [36]. Under suitable conditions on monads, monadic relations come with an operation similar to the Kleisli extension that allows them to be composed and to regard $\eta$ (seen as a relation) as the unit of such an operation.

Definition 6 (Relational Extension, [10])

[Relational Extension, [10]] A relational extension of a monad $(T, \eta , \mu )$ is a family of monotone maps $\varPhi : \textbf{Rel}(A,B) \rightarrow \textbf{Rel}(TA, TB)$ such that:

Replacing $=$ with $\subseteq$, we obtain the notion of a lax relational extension.

Any monad $T$ comes with a canonical candidate relational extension: its Barr extension $\widehat{T}$. Recall that for each relation , we can regard $R$ as a set $\mathcal {G}(R) \subseteq A \times B$. In particular, the projections $\pi _1: \mathcal {G}(R) \rightarrow A$, $\pi _2: \mathcal {G}(R) \rightarrow B$ give $R= \pi _1^{\circ }; \pi _2$.

Definition 7 (Barr Extension)

[Barr Extension] The Barr extension $\widehat{T}$ of $T$ is defined as $\widehat{T}(R) = (T(\pi _1))^{\circ }; T(\pi _2).$ Elementwise, we have $\phi _1 \mathbin {\widehat{T}R} \phi _2$ iff

$$\exists \varPhi \in T\mathcal {G}(R).\ T(\pi _1)(\varPhi ) = \phi _1 \text { and } T(\pi _2)(\varPhi ) = \phi _2. $$

Example 6 (Concrete Barr Exts.)

[Concrete Barr Exts.] Let .

• 1. For the powerset monad, we have $u \mathbin {\widehat{\mathcal {P}}{R}} v$ iff $\forall x \in u.\exists y \in v.\ x\mathbin {R} y$ and $\forall y \in v.\exists x \in u.\ x\mathbin {R} y$. A similar definition holds for variations of the powerset monad.

• 2. For the distribution monad, we have $\phi _1 \mathbin {\widehat{\mathcal {D}}{R}} \phi _2$ iff there exists $\varPhi \in \mathcal {D}(A \times B)$ such that $\sum _y \varPhi (x,y) = \phi _1(x)$, $\sum _x \varPhi (x,y) = \phi _2(y)$, and $\varPhi (x,y) > 0 \implies x \mathbin {R} y$. A similar definition holds for variations of the distribution monad.

• 3. The output monad, we have $(a,x) \mathrel {\widehat{\mathcal {W}}(R)} (b,y)$ iff $a=b$ and $x \mathrel {R} y$.

• 4. More generally, if a monad is presented by a theory $(\varSigma , E)$, then we have $t \mathrel {\widehat{T_{\varSigma }}(R)} s$ iff $t \sim _E C[x_1, \ldots , x_n]$, $s \sim _E C[y_1, \ldots , y_n]$, and $x_i \mathrel {R} y_i$, for any i.

The Barr extension of a monad is not a relational extension, in general. However, the Barr extension of a monad is a relational extension iff the monad is weakly cartesian [15, 71].

Theorem 2

([10]). Recall that a monad $(T, \eta , \mu )$ is weakly cartesian if (i) it preserves weak pullbacks and (ii) all naturality squares of $\eta$ and $\mu$ are weak pullbacks. If $T$ is weakly cartesian, then its Barr extension is the unique relational extension of $T$. If $T$ preserves weak pullbacks, then its Barr extension is a lax relational extension.

For brevity, we say that a monad is WC—resp. WP—if it is weakly cartesian—if it preserves weak pullbacks.

Example 7

All the monads seen so far are WP. The output and maybe monad, additionally, are WC, whereas the powerset and distribution monads are not [71], as naturality squares of their unit are not weak pullbacks. If a monad T is presented by an affine equational theory [35] $(\varSigma , E)$, meaning that all equations in E are affine, then it is WC. Consequently, the multiset and multidistribution monad are WC.

Given a monad $T$ and a monadic relation $R\subseteq A \times T(B)$, we define its Kleisli extension $R^{\dagger } \subseteq T(A) \times T(B)$ as $\widehat{T}(R); \mu$. Using Kleisli extension, we define the composition of monadic relations $R\subseteq A \times T(B)$ and $S\subseteq B \times T(C)$ as the relation defined as $R; S^{\dagger }$. If $T$ is WC (resp. WP), is (lax) associative and has $\eta$ as (lax) unit [36, 40]. Using the Kleisli extension we can design abstract proof techniques ensuring that properties of ${\vdash }$ with respect to the one-step semantics ${\mapsto }$ can be lifted to ${\vdash }^{\dagger }$ and ${\mapsto }^{\dagger }$.

Proposition 3

([10]). Let be a relation and $\varPhi$ be a lax relational extension of a monad T. Then, (i) $\varPhi (R)$ is closed under algebraic operation; (ii) $\varPhi (R)$ is closed under monadic binding: $R;g \subseteq f ; \varPhi (S)$ implies $\varPhi (R);g^{\dagger } \subseteq f^{\dagger } ; \varPhi (S)$.

The next result will be crucial to prove subject expansion.

Proposition 4

Let $T$ be WC. Then: $f; R^{\dagger } \subseteq S\implies f^{\dagger }; R^{\dagger } \subseteq S^{\dagger }$.

In particular, taking both $R$ and $S$ as the typability relation and as f the one-step semantic function , we see that ${\mapsto }; {\vdash }^{\dagger } \subseteq {\vdash }$ states that whenever we have a term $t$ with $t\, {\mapsto }\, e$ and a monadic type M with $\vdash ^{\dagger } e: M$, then $\vdash t: M$. This is exactly the statement of the subject expansion theorem at the level of term-based evaluation that we shall prove in the next section: if $t\mathrel {{\mapsto }} e$ and $\vdash ^{\dagger } e : M$, then $\vdash t: M$. Prop. 4 then implies that subject expansion can be extended to full monadic reduction ${\mapsto }^{\dagger }$: if $e \mathrel {{\mapsto }^{\dagger }} e'$ and $\vdash ^{\dagger }e' : M$, then $\vdash ^{\dagger } e : M$.

Obviously, Proposition 4 still requires us to prove ${\mapsto }; {\vdash }^{\dagger } \subseteq {\vdash }$, and we would like to do so syntactically. Although natural, this relational extension is not always possible. The problem lies in the fact that if we assign a monadic type M to an element of the form $\eta (t)$ via ${\vdash }^{\dagger }$, there is no guarantee that t itself has type M. This becomes problematic when dealing with values. Since a value v (regarded as a computation) reduces to $\eta (v)$ and our monadic type system assigns only types of the form $\eta (I)$ to v, provided that $\vdash v: I$, we need to ensure that any type M such that ${\vdash }^{\dagger } \eta (v) : M$ is itself a type of v, and hence of the form $\eta (I)$. This, however, is not always the case.

Example 8

Let us consider the distribution monad $\mathcal {D}$ and recall that its unit maps a point to its Dirac distribution. Let v be a value such that $\vdash v: A$ and $\vdash v: B$, so that $\vdash v: \{A\}$ and $\vdash v: \{B\}$. By the very definition of the monadic type system, the computation induced by the value v can only have monadic types of the form $\eta (I)$ (i.e. Dirac distributions $1 \cdot I$). Yet, the lifted relation $\vdash ^{\dagger }$ gives ${\vdash }^{\dagger } \eta (v) : \frac{1}{2} \cdot \{A\} + \frac{1}{2} \cdot \{B\}$, since $\eta (v) = 1 \cdot v = \frac{1}{2} \cdot v + \frac{1}{2} \cdot v$ and $\vdash v: \{A\}$ and $\vdash v: \{B\}$ entail $\vdash ^{\dagger } 1\cdot v: 1 \cdot \{A\}$ and $\vdash ^{\dagger } 1\cdot v: 1 \cdot \{B\}$. Consequently, we have $\vdash ^{\dagger } \eta (v) : \frac{1}{2} \cdot \{A\} + \frac{1}{2} \cdot \{B\}$ but we cannot have $\vdash v : \frac{1}{2} \cdot \{A\} + \frac{1}{2} \cdot \{B\}$.

The ultimate source of the problem outlined in the above example is that the unit of $\mathcal {D}$ is not weakly cartesian.

Proposition 5

Let $T$ be WC. For any monadic relation $R\subseteq A \times T(B)$, we have $\eta ; R^{\dagger } = R$. In particular, $\eta ; {\vdash }^{\dagger } = {{\vdash }}$.

The techniques seen so far have been designed to prove subject expansion of the monadic type system. As expected, we are also interested in proving subject reduction and thus it is natural to design similar proof techniques in that setting. This can be easily done following the same path as for subject expansion, but with a main difference: subject reduction does not require the unit of the monad to be WC, and hence subject reduction results can be proved for a much larger class of monads.⁴

Proposition 6

Let $T$ be WP. Then: $R^{\circ }; f \subseteq {R^{\dagger }}^{\circ } \implies {R^{\dagger }}^{\circ }; f^{\dagger } \subseteq {R^{\dagger }}^{\circ }$.

In particular, we can instantiate Proposition 6 with $R$ and f as ${\vdash }$ and ${\mapsto }$, hence obtaining ${\vdash }^{\circ }; {\mapsto }\subseteq {{\vdash }^{\dagger }}^{\circ } \implies {{\vdash }^{\dagger }}^{\circ }; {\mapsto }^{\dagger } \subseteq {{\vdash }^{\dagger }}^{\circ }$, meaning that whenever subject reduction holds at the level of terms (i.e. $\vdash t: M \mathrel { \& } t\mathrel {{\mapsto }} e \implies \vdash ^{\dagger } e : M$), then it holds at the level of their (monadic) evaluation (i.e. $\vdash ^{\dagger } e: M$ and $e \mathrel {{\mapsto }^{\dagger }} e'$ implies $\vdash ^{\dagger } e' : M$).

Soundness. The proof of soundness of the type system consists in showing:

• 1. Subject reduction: types are preserved by reduction.

• 2. Termination: all typable terms terminate.

As we have seen, by Proposition 6, it is sufficient to prove subject reduction with respect to the single-step, term-based reduction ${\mapsto }$. This is done by induction on the structure of evaluation contexts, with the help of a substitution lemma, proved by induction on the structure of terms.

Proposition 7

(Subject Reduction). Let $T$ be WP. Then:

• 1. Let $t$ be a closed $\lambda$-term. If $\vdash t:M$ and $t\,{\mapsto }\,e$, then $\vdash ^{\dagger }e:M$.

• 2. Let e be a monadic closed $\lambda$-term. If $\vdash ^{\dagger } e: M$ and $e \mathrel {{\mapsto }^{\dagger }} e'$, then $\vdash ^{\dagger } e' : M$.

Proving termination instead needs more work.

Effectful Observations. Knowing that typing is preserved by reduction, it remains to show that whenever a computation t has type M, its observable operational behaviour is fully captured by M. In the pure case, such a behaviour is just termination, so that one usually shows that typable terms terminate. In the effectful setting, termination can be given in many forms. First, if effects capture some forms of nondeterminism, meaning that elements in may have more than one element in their support, then termination can be divided into may or must termination (i.e. whether term reaches monadic expressions with one, at least, or all values in their support). In both of these cases, termination remains a boolean notion (viz. a predicate). To account for effects it is natural to ask not only whether a computation terminates, but also which effects are produced during evaluation (e.g. what is stored in memory locations, which are the printed outputs, the cost of the computation, etc). A further option is to make termination effectful itself, a well-known example of effectful termination being almost-sure termination (i.e. probability of convergence). Such notions are usually infinitary and require non-boolean reasoning.

Since here we deal with the finitary case, we agree to observe must termination of computations as well as the effects produced during their evaluation. In the next section, we shall deal with infinitary evaluation and, consequently, with effectful termination. Let us begin by formalising how to observe effects. In a monadic setting, it is customary [19,20,21, 62], to model (effectful) observables as elements of $T(X)$, where X is what is observable of expressions. As we are interested in must termination, only values are observable, and, moreover, they cannot be scrutinized further (i.e. we observe that a computation gives a result (a value), but we cannot inspect such a result⁵).

Definition 8

We define the observation function for monadic objects in T(X) as $\textsf{obs}_{X} :=T(!_{X}): T(X) \rightarrow T(1)$, where $1 :=\{\star \}$ and $!_{X}: X \rightarrow 1$ is the unique arrow collapsing all the elements of X to $\star$. We extend to a partial function on terms by stipulating , provided that $\llbracket t \rrbracket = e$.

As usual, we omit subscripts whenever possible, writing $\textsf{obs}(e)$, $\textsf{obs}(M)$, etc.

Example 9

(Concrete Observations).

• 1. The output, or writer, monad $\mathcal {W}$ has a notion of observation $\textsf{obs}:\mathcal {W}(X)\rightarrow W$, if W is the underlying monoid of words. This is immediate to see because $\mathcal {W}(1):=W\times \{\star \}\cong W$. Then, we have that $\textsf{obs}((w,x)):=w$. This means that what we can observe is the string that has been printed on the output buffer during the computation.

• 2. The partiality monad $\mathcal {E}$ provides a binary notion of observation, indeed $\textsf{obs}:\mathcal {E}(X)\rightarrow \{\star ,\bot \}$. This is actually the way in which one could observe divergence.

• 3. The powerset monad $\mathcal {P}$ comes with the natural notion of must termination, since $\textsf{obs}:\mathcal {P}(X)\rightarrow \{\emptyset ,1\}$.

Remark 2

According to Definition 8, the observable effects produced by a computation are elements of T(1). This certainly works well for some effects and monads, such as output and cost, but it may be unusual for others. For instance, probabilistic nondeterminism is usually modelled using (variations of) the sub-distribution monad $\mathcal {D}$ and, since $\mathcal {D}(1) \cong [0,1]$, it is natural to interpret elements in the latter set as actual probabilities of events (such as the probability of termination, in our case). However, we have already seen that it is simply not possible to have well-behaved forms of intersection types working with $\mathcal {D}$, and that we can overcome that issue by working with the multi-sub-distribution monad $\mathcal {M}$. Unfortunately, $\mathcal {M}(1) \not \cong [0,1]$, although we would still like to think about the observable behaviour of a program as its probability of convergence. This is not a big issue since it does not take much to realise that our analysis of observations works mutatis mutandis if we replace T(1) with S(1), where S is another monad such that there is a monad morphism $\nu : T \Rightarrow S$. This way, for instance, even if modelling static and dynamic semantics in terms of $\mathcal {M}$, we can regard $\textsf{obs}(t)$ as the probability convergence of convergence of t, due to the monad morphism $\nu : \mathcal {M} \Rightarrow \mathcal {D}$ collapsing multi-sub-distributions into ordinary sub-distributions.

Termination by Logical Relations. Our goal is now to prove that whenever a term t has type M then: (i) t must terminate, and (ii) the observable behaviour of t, i.e., $\textsf{obs}(t)$, is fully described by M. That is, $\textsf{obs}(t) = \textsf{obs}(M)$. To achieve such a goal, we define a logical relation $\models$ between (closed) terms and types acting as the semantic interpretation of $\vdash$ in such a way that ${\vdash } = {\models }$ and $\models t: M$ implies $t \Downarrow e$ (must termination) and $\textsf{obs}(e) = \textsf{obs}(M)$. Remarkably, such a logical relation makes crucial use of the Barr extension of $T$.

Definition 9

We define the logical semantics of ${\vdash }$ (restricted to closed expressions) as the relation that inductively refines ${\vdash }$ (i.e. $\models \,\subseteq {\vdash }$) as follows, where we use the notation $\widehat{\models } e : M$ in place of .

As usual, we omit subscripts whenever unambiguous. We first show that, indeed, $\models$ ensures the desired property.

Lemma 3

$\models t: M$ implies $\exists e\text { such that }\llbracket t \rrbracket = e$ and $\textsf{obs}(e) = \textsf{obs}(M)$.

Then, we prove the soundness of our type system showing that $\models$ and $\vdash$ coincide.

Proposition 8

(Soundness). ${{\vdash }} = {\models }$.

Completeness. Having proved soundness of our type system, we now move on to completeness, meaning that normalising terms are typable. The proof of completeness follows the usual pattern for intersection types, and makes crucial use of subject expansion. The proof of subject expansion is divided into two parts: first, we prove subject expansion with respect to the single-step reduction on terms and then extend such a result to monadic terms and monadic reduction relying on Proposition 4. Concerning the first part, we would like to prove subject expansion by induction on the structure of evaluation contexts (after having proved a straightforward anti-substitution lemma). However, the statement is not true in general.

Example 10

Let us consider the multidistribution monad and the binary operation $\oplus _1$, i.e. the first projection. Let us consider the reduction $\lambda x.x\oplus _1\varOmega \mapsto 1\cdot \lambda x.x$. Even if $\vdash ^{\dagger }1\cdot \lambda x.x:1\cdot M$, it is not possible to type $\lambda x.x\oplus _1\varOmega$ with rule $\textsc {op}$, because of course there is no way of typing $\varOmega$.

Then, we need a restriction on our calculus, this time about operations. We allow only operations $\texttt{op}(t_1,\ldots ,t_n)$ that do not erase their arguments, i.e. for which $\textsf{supp}(g_\texttt{op}(\eta (t_1),\ldots ,\eta (t_n)))=\{t_1,\ldots ,t_n\}$. In terms of equational theories, this is guaranteed by considering linear theories. We already anticipate that we will be able to remove this restriction in the next section, by the use of infinitary means.

Proposition 9

(Subject Expansion). Let $T$ be WC. Then:

• 1. If $t\mathrel {{\mapsto }} e$ and $\vdash ^{\dagger } e : M$, then $\vdash t: M$.

• 2. If $e \mathrel {{\mapsto }^{\dagger }} e'$ and $\vdash ^{\dagger }e' : M$, then $\vdash ^{\dagger } e : M$.

Proposition 9, together with the fact that monadic values can always be typed, gives the completeness of the type system.

Theorem 3

(Completeness). If $\llbracket t \rrbracket =e$, then there exists a monadic type $M$ such that $\vdash t:M$.

Soundness and completeness together provide a characterization of finitary effectful termination via typability with intersection types.

Corollary 1

(Characterization). The following clauses are equivalent:

• 1. Effectful termination: $\textsf{obs}(\llbracket t \rrbracket )=o$.

• 2. Typability: there exists $M$, such that $\vdash t:M$ and $\textsf{obs}(M)=o$.

5 Infinitary Effectful Semantics

In this section, we extend the type system of Section 4 to account for infinitary behaviours. To do so, we require monads to have enough structure to support such behaviours. A standard approach to do that is by requiring suitable order-theoretic enrichments. Here, we consider monads whose Kleisli category is enriched in the category of directed complete pointed partial order (dcppos) [1, 43], but in order to maintain the paper as self-contained as possible, we use the following more concrete (and restricted) definition.

Definition 10

A monad is dcppo-ordered if, for any set A, we have a dcppo $(T(A), \sqsubseteq _A, \bot _A)$ such that the bind operator is strict and continuous in both arguments.

As usual, we omit subscripts whenever unambiguous. Notice that if T is dcppo-ordered, then all its algebraic operations are strict and continuous.

Example 11

Both the multiset and multidistribution monad can be turned into dcppo-ordered monads by simply adding a zero-ary operation symbol $\bot$ to their equational theories. Semantically, $\bot$ corresponds to the empty multiset and multidistribution, respectively.

From now on, we tacitly work with an arbitrary but fixed dcppo-ordered monad .

Infinitary Typing. Extending the monadic type system to the infinitary case is straightforward. We simply add the typing rule

allowing to type any computation with the total uninformative type $\bot$. Consequently, we can assign several types to each term.

Example 12

We provide in Fig. 5 the type derivation for the term $\vdash (\lambda x.xx)(\textsf{II}\oplus \varOmega ):\frac{1}{2}\textbf{0}$, again a simple variation on the theme of the previous examples. One can notice that we are able to type it, even if clearly the term does not converge. Its type $\frac{1}{2}\textbf{0}$ says exactly that: the probability of convergence is $\textsf{obs}(\frac{1}{2}\textbf{0})=\frac{1}{2}$.

Fig. 5.

Type derivation for $\vdash (\lambda x.xx)(\textsf{II}\oplus \varOmega ):\frac{1}{2}\textbf{0}$. $\texttt{id}:=\textbf{0}\rightarrow \eta (\textbf{0})=\textbf{0}\rightarrow 1{\cdot }\textbf{0}$.

Nonetheless, we can think about type derivations (with occurrences of the $\textsc {bot}$ rule) as approximations of the semantic content of a computation, the latter being reached only at the limit. Moreover, the set of the observations $\mathcal {O}(t)$ of a term t, defined as the collection of all the observations $\textsf{obs}(M)$ for $\vdash t : M$ is directed. Consequently, we can associate to each t a more informative observation obtained through types given as $O(t) :=\bigsqcup \mathcal {O}(t)$. Notice that even if $O(t)$ is a valid observation, there may be no (necessarily finite) derivation $\pi \mathrel {\;\triangleright \,} {\vdash t: M}$ such that $\textsf{obs}(M)=O(t)$.

Infinitary Operational Semantics. A standard approach to deal with infinitary effectful semantics consists in defining a monadic evaluation function mapping computations to monadic values. To capture forms of convergence in the limit, such a function is defined as a suitable least upper bound of maps evaluating computations for a fixed number of steps. We implement this strategy building upon the definition of ${\mapsto }$.

Definition 11

(Approximate Operational Semantics). Let mapping values v (as elements in ) to $\eta (v)$ and all other terms t to $\bot$. Then, we define the -indexed family of maps by $\llbracket t \rrbracket ^0 :=\bot$, and $\llbracket t \rrbracket ^n :=e \mathrel {[1]{>\!>=}}\phi$, if $n > 0$ and $t \mathrel {{\mapsto }^n} e$.

Lemma 4

([19]). For any closed computation t, the sequence $\{\llbracket t \rrbracket ^n\}_{n \ge 0}$ forms a directed set (an $\omega$-chain, actually).

Consequently, we define (overriding the previous finitary definition) $\llbracket t \rrbracket = \bigsqcup _n \llbracket t \rrbracket ^n$. Notice that this also gives a straightforward way to extend the observation function $\textsf{obs}$ (on terms) to the infinitary setting. We simply define be as before. Moreover, since T is dcppo-enriched, $\textsf{obs}$ is continuous (and thus monotone). In particular, we can define a bounded observation function as $\textsf{obs}^{n}(t) :=T(!)(\llbracket t \rrbracket ^n)$ and see that $\textsf{obs}(t) = \bigsqcup _n \textsf{obs}^{n}(t)$. We now have all the ingredients needed to extend our characterization to the infinitary setting.

6 Characterizing Infinitary Behaviors

In this section, we extend the soundness and completeness results previously seen to the infinitary setting. Remarkably, most of the proofs given in the finitary case, such as those of subject reduction and expansion, scale to the infinitary case. This is no coincidence but a main strength of the abstract relational approach that we have developed in the previous part of this work.

Soundness. As in the finitary case, we have subject reduction for WP monads.

Proposition 10

(Subject Reduction, Infinitary). Let $T$ be WP. Then:

• 1. Let $t$ be a closed $\lambda$-term. If $\vdash t:M$ and $t\,{\mapsto }e$, then $\vdash ^{\dagger }{e}:{M}$.

• 2. Let e be a monadic closed $\lambda$-term. If $\vdash ^{\dagger } e: M$ and $e \mathrel {{\mapsto }^{\dagger }} e'$, then $\vdash ^{\dagger } e' : M$.

Notice that Proposition 10 is given relying on the Barr extension of T which, by its very definition, does not take into account the order $\sqsubseteq$ induced by T. In particular, whenever we have $\vdash ^{\dagger } e : M$, then e and M must have the same effectful behaviour. This means that as long as we stick with $\widehat{T}{(\vdash )}$, it is simply not possible to extend subject reduction (and thus soundness) to the full evaluation $\llbracket - \rrbracket$, the latter being infinitary. Consequently, contrary to the finitary case, there is no hope to prove that whenever $\vdash t: M$, then M encodes the whole observable behaviour of t, i.e. $\textsf{obs}(\llbracket t \rrbracket )$. What we can show, however, is that M provides an approximation of such a behaviour, and that the limit of such approximations is precisely the operational behaviour of t. The right tool to achieve such a goal, is an ordered version of the Barr extension [41].

Definition 12

(Right Barr Extension). Given $R\subseteq A \times B$, we define its right Barr extension $\widehat{T}_{\sqsupseteq }(R) \subseteq T(A) \times T(B)$ as $\widehat{T}_{\sqsupseteq }(R) :=\widehat{T}{(R)}; {\sqsupseteq }$.

Proposition 11

([41]). If $T$ is WP, then $\widehat{T}_{\sqsupseteq }$ is a lax relational extension.

Using the right Barr extension, we define the logical relation interpreting $\vdash$.

Definition 13

(Infinitary Logical Relation). We define the logical semantics of ${\vdash }$ (restricted to closed expressions) as the relation that inductively refines ${\vdash }$ (i.e. $\models \,\subseteq {\vdash }$) as follows, where we use the notation $\widetilde{\models }\; e : M$ in place of $e \mathrel {\widehat{T}_{\sqsupseteq }(\models )} M$.

As usual, we omit subscripts whenever unambiguous.

Lemma 5

$\models t: M$ implies $\textsf{obs}(\llbracket t \rrbracket ) \sqsupseteq \textsf{obs}(M)$.

As in the finitary case, we prove the soundness of our type system showing that $\models$ and $\vdash$ coincide.

Proposition 12

(Soundness). If $T$ is WP, then ${{\vdash }} = {\models }$.

Completeness. As in the finitary case, completeness is proved via subject expansion. This latter result, in turn, is obtained exactly as in the finitary case. The only difference is that we are able to drop the constraint about non-erasing operations. Indeed, this time we can type erased (and thus possibly diverging) arguments with the rule $\textsc {bot}$.

Proposition 13

(Subject Expansion, Infinitary). Let $T$ be WC. Then:

• 1. If $t\mathrel {{\mapsto }} e$ and $\vdash ^{\dagger } e : M$, then $\vdash t: M$.

• 2. If $e \mathrel {{\mapsto }^{\dagger }} e'$ and $\vdash ^{\dagger }e' : M$, then $\vdash ^{\dagger } e : M$.

Then, we are able to prove approximate completeness, by finitary means.

Theorem 4

(Approximate Completeness). Let $t$ be a closed $\lambda$-term. Then, for each $k\ge 0$, there exist $\pi _k\;\triangleright \,\vdash t:M_k$ such that $\textsf{obs}(M_k)=\textsf{obs}^{k}(t)$.

Finally, we can claim the full characterization of the infinitary effectful behavior of any program by the way of our intersection type system.

Corollary 2

(Characterization). Let $t$ be a closed $\lambda$-term. Then $O(t)=\textsf{obs}(t)$.

Fig. 6.

Type derivation for $\vdash \checkmark ((\lambda x.\checkmark (xx))(\checkmark (\textsf{II})\oplus \textsf{I})):\frac{1}{2}{\cdot }(3,\textbf{0}),\frac{1}{2}{\cdot }(2,\textbf{0})$. We set $\texttt{id}:=\textbf{0}\rightarrow \eta (\textbf{0})=\textbf{0}\rightarrow 1{\cdot }(0,\textbf{0})$.

Example 13

As a concluding example, in Fig. 6 we show the type derivation for the term $\vdash \checkmark ((\lambda x.\checkmark (xx))(\checkmark (\textsf{II})\oplus \textsf{I})):\frac{1}{2}{\cdot }(3,\textbf{0}),\frac{1}{2}{\cdot }(2,\textbf{0})$. Please notice that this example is built on the composition of two different monads: cost and multidistribution. This way, we show how we are able to handle computational effects in a modular way. It is easy to verify that the same would have been possible, e.g., for cost and multipowerset. $\textsf{obs}(\frac{1}{2}{\cdot }(3,\textbf{0}),\frac{1}{2}{\cdot }(2,\textbf{0}))=\frac{1}{2}{\cdot }3,\frac{1}{2}{\cdot }2$, which is a distribution on costs. Taking its expected value, one can indeed obtain the average cost of the computation. One can build an example that actually uses infinitely many types (and derivations) on the same line of the one presented in [18].

7 Conclusion

In this paper, we have proposed the first intersection type system able to characterize the effectful behavior for terms of the $\lambda$-calculus enriched with algebraic operations. In particular, we are able to do that parametrically with respect to the underlying monad. Moreover, having presented effects as algebraic theories, it is possible to compose effects relying both on the sum and tensor of algebraic theories. Since effectful behaviors are often observed at the limit, we had to deal with infinitary constructions. Technically speaking, relational reasoning was the main tool exploited to obtain our result in an abstract and modular way.

Perspectives. This work opens several research directions:

• Quantitative Cost Analyses: Idempotent intersection types are qualitative in nature because they are not able to track the use of resources, such as time or space, during the evaluation. Turning intersections (i.e. sets) into multisets is enough to measure the precise cost of the evaluation of typed terms, while maintaining the correctness of the type system [3, 4, 24]. Extending this machinery to the effectful setting would be very interesting, although not trivial. While there are standard notions of monadic costs (e.g. the average cost in the probabilistic setting, or the maximum cost in must nondeterminism), it is not clear how to devise the type system to capture them. In the probabilistic case, for example, some additional information had to be stored inside types to correctly compute the average number of steps [18]. Very recently some investigations on the state and the exception monad (featuring also handling) have appeared [5, 44], but the design of the type systems seems ad-hoc and not easy to generalize.

• Higher-Order Model Checking: Model checking of higher-order recursion schemes has been proven decidable by Ong in 2006 [52]. Since then, several papers dissected the original result and gave other proof methods and model checking algorithms. Among them, Kobayashi and coauthors developed type-theoretic techniques based on intersection types [46, 48]. While the literature contains results about model checking higher-order programs enriched with specific effects, such as probability [47] or nondeterminism [65], no general method covering families of computational effects is known. Indeed, we would like to investigate if our type system could guide the synthesis of model checking algorithms in the style of [65]. Since the problem has been proved in general undecidable in the effectful setting, e.g. in the case of the sub-distribution monad [47], one would need of course to restrict the class of monads in order to recover decidability.

• Adding Coinduction: Our type system is not able to deal with coinductive properties, such as productivity, or with coinductive effects, like the output of streams. We would like to enhance the type system with coinductive types/rules in order to capture these kind of properties. Since the type system is somehow modelled on top of operational semantics, this would require to change it as well. We mention that very recently some works covering coinduction have appeared, but limited to the pure $\lambda$-calculus, and carried on in the non-idempotent setting [68, 69].