Introduction
Operational semantics and denotational semantics offer complementary views of effectful computation. Denotational semantics provides a mathematical account of effects, using monads and their corresponding algebraic theories, while operational semantics explains execution through computable reduction rules. Although these two perspectives are intended to describe the same computations, they are typically developed independently.
Moggi systematized the denotational approach to effects by modeling effectful programs in the Kleisli category of a monad [33 ] . Plotkin and Power refined this approach with “algebraic effects”: by viewing the monads as the free models of an algebraic theory, we get a direct way to connect the effects with the primitive “effectful operations” and axioms that are given in an effectful calculus [36 ] . The algebraic perspective has the benefit that effects and their laws can be studied individually and combined together compositionally using operations such as coproduct and tensor of theories [23 ] . This provides a rich toolkit for specification and reasoning about effects.
On the other hand, the analysis of operational semantics of these same effects is less unified. Operational semantics of algebraic effects originally computed a tree of operations and left them uninterpreted [25 , 40 ] . Categorical approaches using coalgebra [46 ] now extend to higher-order languages [20 ] . They give general results about operational properties like bisimulation, but each language still gives the rules for its effects by hand, and state needs a new approach [21 ] .
Our goal in this paper is to bring the benefits of the systematic perspective of algebraic effects to the operational semantics of effects. A single reduction rule handles every operation, and for a particular algebraic theory it yields the reduction rules that theory’s effects. That is, we reproduce the operational semantics used in practice by deriving them from an algebraic theory. The power of the systematic approach is that then soundness, adequacy and logical relations arguments for these operational systems can be provided once and for all, with a completely uniform development.
The main concept we need to formalize is the runtime state of the operational semantics, traditionally called a configuration [39 ] . For a language that logs messages, a configuration pairs the running program with the log written so far. We take configurations to be elements of the free model of the effect theory. The unit of the free model monad gives the initial configuration of a term, and the multiplication of the monad merges the result of interpreting an operation, reached by one of the terms, back into the configuration. Earlier operational semantics also place programs inside a monad [9 , 17 , 18 ] . The idea is to define reduction as a relation R ⊆ Term × T ( Term ) R \subseteq\operatorname{Term} \times T(\operatorname{Term}) R ⊆ Term × T ( Term ) and to lift it to T ( Term ) T(\operatorname{Term}) T ( Term ) by Kleisli extension. So in all these works, a step reduces every term inside the monad at once. We reduce one term at a time, as the operational semantics used in practice do, and prove that every step preserves the denotation of the configuration.
Our construction requires the free model to be a monadic container [42 , 48 ] , a monad whose underlying functor is a container, also known as a polynomial functor [1 , 16 ] . Each configuration is then a shape, the state of the machine, together with the terms at its positions. The effect rules are computed from this data. Configuration reduction need not terminate in general. We introduce a sufficient condition, which we call affinity . A container is affine when a step never copies the terms around the one it reduces. State, errors, writer, and weighted and pre-convex probabilistic choice all give affine monadic containers. Finite nondeterminism and finitely supported probability distributions do not give monadic containers at all, since their free models are not container functors (§ 5.4 ). How an operation changes the configuration, its new state and where each term goes, is computed from the free model alone, independently of the syntax of the language.
The relation then between the denotational and operational semantics within our framework becomes clear. In a denotational semantics, the effects of a program are evaluated “bottom-up”: in an effectful operation op ( M , … ) \operatorname{op}(M,\ldots) op ( M , … ) we first take the denotations ⟦ M ⟧ , … \llbracket M\rrbracket,\ldots [ [ M ] ] , … and then combine them together with the semantic interpretation of the operation. Contrariwise, in an operational semantics, the effects of a program are evaluated “top-down”. The configuration records the effects performed so far, and when one of its subterms reaches an operation op ( M , … ) \operatorname{op}(M,\ldots) op ( M , … ) , the operation can be interpreted right away, before any of its operands has run. The operands M , … M,\ldots M , … become new subterms of the configuration, to be run later. For example, with writer effects a configuration ⟨ m , N ⟩ \langle m,N\rangle ⟨ m , N ⟩ pairs the log m m m with a term N N N . The step ⟨ m , tell n ( N ) ⟩ ↦ ⟨ m ⊗ n , N ⟩ \langle m,\operatorname{tell}_{n}(N)\rangle\mapsto\langle m\otimes n,N\rangle ⟨ m , tell n ( N )⟩ ↦ ⟨ m ⊗ n , N ⟩ records n n n before N N N runs. Take M = tell a ( tell b ( ret x ) ) M=\operatorname{tell}_{a}(\operatorname{tell}_{b}(\operatorname{ret}\ x)) M = tell a ( tell b ( ret x )) and the empty log e e e . The denotation adds b b b to the log first but the machine adds a a a first.
⟦ M ⟧ = tell a ( tell b ( ⟦ ret x ⟧ ) ) ⟨ e , tell a ( tell b ( ret x ) ) ⟩ = tell a ( tell b ( ⟨ e , x ⟩ ) ) ↦ ⟨ e ⊗ a , tell b ( ret x ) ⟩ = tell a ( ⟨ b ⊗ e , x ⟩ ) ↦ ⟨ ( e ⊗ a ) ⊗ b , ret x ⟩ = ( a ⊗ ( b ⊗ e ) , x ) \begin{aligned}
\llbracket M\rrbracket&= \operatorname{tell}_{a}(\operatorname{tell}_{b}(\llbracket\operatorname{ret}\ x\rrbracket)) &
\langle e,\operatorname{tell}_{a}(\operatorname{tell}_{b}(\operatorname{ret}\ x))\rangle\\
&= \operatorname{tell}_{a}(\operatorname{tell}_{b}(\langle e,x\rangle)) &\mapsto\langle e\otimes a,\operatorname{tell}_{b}(\operatorname{ret}\ x)\rangle\\
&= \operatorname{tell}_{a}(\langle b\otimes e,x\rangle) &\mapsto\langle(e\otimes a)\otimes b,\operatorname{ret}\ x\rangle\\
&= (a\otimes(b\otimes e),x)
\end{aligned} [ [ M ] ] = tell a ( tell b ( [ [ ret x ] ] )) = tell a ( tell b (⟨ e , x ⟩)) = tell a (⟨ b ⊗ e , x ⟩) = ( a ⊗ ( b ⊗ e ) , x ) ⟨ e , tell a ( tell b ( ret x ))⟩ ↦ ⟨ e ⊗ a , tell b ( ret x )⟩ ↦ ⟨( e ⊗ a ) ⊗ b , ret x ⟩
In this example we can easily see that the two results agree by the monoid laws. We generalize this work to more general monads. Since the behavior of both approaches is derived from the same notion of a free model, a short calculation with the monad laws and the fact that stacks are interpreted as homomorphisms shows that every step of the operational semantics preserves the denotation. Under affinity, at ground types, every run of the machine ends in the denotation of the program, which is computational adequacy.
We instantiate this approach concretely by formalizing a Call-by-push-value (CBPV) calculus parameterized by an algebraic theory. We use CBPV as a simple metalanguage into which call-by-value and call-by-name calculi can be easily embedded [31 ] . The calculus can be straightforwardly given a denotational semantics following Levy’s original algebra models. We then give two effect-generic logical relations models establishing canonicity of the equational theory (every closed computation of type F A FA F A is provably equal to a tree of operations with returned values at its leaves) and termination of a tree-based operational semantics that leaves algebraic effects uninterpreted, as in effect trees and interaction trees [15 , 25 , 28 ] . We provide a categorical analysis of how the equational canonicity proof is reached. We then show that, given a monadic container that the free model of the theory, we can derive a configuration-based operational semantics, and we use the affinity side condition to transport the termination proof from the tree semantics to the configuration semantics.
Contributions.
Following standard techniques, we prove equational and operational canonicity for CBPV with a finitary algebraic theory, using effect-generic logical relations (§ 3 and § 4 ). We write out in detail material that is scattered across the CBPV literature and folklore.
For any algebraic theory whose free model is a monadic container, we derive an operational semantics whose configurations are elements of the free model (§ 5 ). A single rule, computed from the monad structure of the container, interprets every operation, acting on one subterm of a configuration at a time.
We prove that each step of this configuration semantics preserves the interpretation of a configuration in the free model, given by the standard denotational semantics of CBPV. When the container is affine, we also prove strong normalization and computational adequacy at ground types (Theorems 5.12 , 5.17 and 5.18 ).
We instantiate the construction for errors, writer, finite state, and weighted and pre-convex probabilistic choice (§ 5.4 ). For errors, writer and weighted choice we recover the usual rules, and for finite state we obtain a machine that runs the program from every initial state at once.
Algebraic Effects in CBPV
In this section we describe a simply typed call-by-push-value (CBPV) calculus extended with primitive operations from a finitary algebraic theory of effects. The syntax distinguishes values, computations, and stacks in the standard CBPV style, and includes algebraic operations as term formers subject to the equations of the theory.
Algebraic Theories and Algebraic Effects
Algebraic effects [37 ] provide a way of describing computational effects such as state, exceptions, nondeterminism, and I/O using algebraic structure. The key idea is that effectful programs can be viewed as computations generated from primitive operations (e.g. reading a value, updating state, or raising an exception), together with equations governing their interaction. Such computations are reduced to trees of operations, which are later interpreted in semantic models. This intuition is formalized by the notion of an algebraic theory [30 ] . Algebraic effects refine the monadic approach to computational effects [33 ] . The operations and equations of the theory correspond to primitive constructs and axioms of the calculus. The monad of the theory sends a set X X X to the free model of the theory on X X X , and the category of models of the theory is isomorphic to the category of Eilenberg–Moore algebras of the monad.
We use a standard definition of finitary algebraic theory T = ( Σ , E q n s ) \mathcal{T} = (\Sigma, \mathsf{Eqns}) T = ( Σ , Eqns ) , consisting of a signature Σ \Sigma Σ and a set of equations E q n s \mathsf{Eqns} Eqns . A signature Σ = ( O p s , a r ) \Sigma= (\mathsf{Ops}, \mathsf{ar}) Σ = ( Ops , ar ) specifies a set of operation O p s \mathsf{Ops} Ops and for each operation o p : O p s \mathsf{op} : \mathsf{Ops} op : Ops , an arity a r ( o p ) : N \mathsf{ar}(\mathsf{op}) : \mathbb{N} ar ( op ) : N . Given a signature Σ \Sigma Σ , the set of terms generated by the signature with variables of type X X X is inductively defined by:
x : X v a r x : T e r m Σ ( X ) o p : O p s ∀ i . t i : T e r m Σ ( X ) o p ( t 1 , t 2 , … , t a r ( o p ) ) : T e r m Σ ( X ) \frac{x : X}{\mathsf{var}\ x : \mathsf{Term}_{\Sigma}(X)}
\qquad
\frac{\mathsf{op} : \mathsf{Ops} \qquad\forall i.\ t_i : \mathsf{Term}_{\Sigma}(X)}
{\mathsf{op}(t_1,t_2,\ldots,t_{\mathsf{ar}(\mathsf{op})}) : \mathsf{Term}_{\Sigma}(X)} var x : Term Σ ( X ) x : X op ( t 1 , t 2 , … , t ar ( op ) ) : Term Σ ( X ) op : Ops ∀ i . t i : Term Σ ( X )
which we denote as T e r m Σ ( X ) \mathsf{Term}_{\Sigma}(X) Term Σ ( X ) . An equation consists of a context size c t x : N \mathsf{ctx} : \mathbb{N} ctx : N with two terms l h s , r h s : T e r m Σ ( c t x ) \mathsf{lhs},\mathsf{rhs} : \mathsf{Term}_{\Sigma}(\mathsf{ctx}) lhs , rhs : Term Σ ( ctx ) where c t x \mathsf{ctx} ctx is interpreted as a finite set of cardinality c t x \mathsf{ctx} ctx .
Example 2.1 (Theory of Writer). The theory of writer [23 ] models computations that accumulate output, such as logging, tracing, or incrementally constructing an output buffer. The type of output is represented by a monoid ( M , ⊗ , e ) (M, \otimes, e) ( M , ⊗ , e ) , where e e e denotes the empty output and ⊗ \otimes ⊗ combines the outputs produced by successive computations. For a given monoid, we define the theory T w r i t e r \mathcal{T}_{\mathrm{writer}} T writer to consist of a signature Σ w r i t e r \Sigma_{\mathrm{writer}} Σ writer with one unary operation tell m ( t ) \operatorname{tell}_{m}(t) tell m ( t ) for every m : M m : M m : M . The equations of this theory are:
tell e ( t ) = t tell m ( tell n ( t ) ) = tell m ⊗ n ( t ) \operatorname{tell}_{e}(t) = t \qquad\operatorname{tell}_{m}(\operatorname{tell}_{n}(t)) = \operatorname{tell}_{m\otimes n}(t) tell e ( t ) = t tell m ( tell n ( t )) = tell m ⊗ n ( t )
Example 2.2 (Theory of Errors). The theory of errors models computations that may abort [36 Ex. 1] . We define the theory T e r r \mathcal{T}_{\mathrm{err}} T err to consist of a signature Σ e r r \Sigma_{\mathrm{err}} Σ err with a single nullary operation err \operatorname{err} err , and no equations.
Example 2.3 (Theory of Finite State). The theory T s t a t e \mathcal{T}_{\mathrm{state}} T state of state for a finite set of states S S S consists of a signature Σ S \Sigma_{S} Σ S with unary operations set s ( t ) \operatorname{set}_{s}(t) set s ( t ) for all s : S s : S s : S and a single operation get ( t → ) \operatorname{get}(\overrightarrow{t}) get ( t ) of arity ∣ S ∣ |S| ∣ S ∣ . The equations of T s t a t e \mathcal{T}_{\mathrm{state}} T state [36 §3] consist of the usual lens laws, for all s , s ′ : S s, s' : S s , s ′ : S :
get ( set s ( t ) → ) = t set s ( get ( t → ) ) = set s ( t s ) set s ( set s ′ ( t ) ) = set s ′ ( t ) get ( get ( t → s ) ) = get ( t → s s ′ ) \operatorname{get}(\overrightarrow{\operatorname{set}_{s}(t)}) = t \qquad\operatorname{set}_{s}(\operatorname{get}(\overrightarrow{t})) = \operatorname{set}_{s}(t_{s}) \qquad\operatorname{set}_{s}(\operatorname{set}_{s'}(t)) = \operatorname{set}_{s'}(t) \qquad\operatorname{get}(\operatorname{get}(\overrightarrow{t}_{s})) = \operatorname{get}(\overrightarrow{t}_{ss'}) get ( set s ( t ) ) = t set s ( get ( t )) = set s ( t s ) set s ( set s ′ ( t )) = set s ′ ( t ) get ( get ( t s )) = get ( t s s ′ )
Example 2.4 (Theory of Weighted Monoids). The theory of weighted monoids models computations that may produce multiple weighted outcomes. Unlike ordinary nondeterminism, the order of outcomes is significant and duplicate outcomes are preserved. Let ( R , ⋅ , 1 R ) (R, \mathord{\cdot}, 1_{R}) ( R , ⋅ , 1 R ) be a multiplicative monoid of weights. We define the theory T w m o n \mathcal{T}_{\mathrm{wmon}} T wmon to consist of a signature Σ w m o n \Sigma_{\mathrm{wmon}} Σ wmon with a nullary operation e e e , a binary operation ⊗ \otimes ⊗ , and one unary operation act r \operatorname{act}_{r} act r for each r : R r : R r : R . The equations of this theory are given below.
t ⊗ ( t ′ ⊗ t ′ ′ ) = ( t ⊗ t ′ ) ⊗ t ′ ′ e ⊗ t = t t ⊗ e = t act 1 R ( t ) = t act r ( act r ′ ( t ) ) = act r ⋅ r ′ ( t ) act r ( t ⊗ t ′ ) = act r ( t ) ⊗ act r ( t ′ ) act r ( e ) = e \begin{aligned}
t \otimes(t' \otimes t'') &= (t \otimes t') \otimes t'' & e \otimes t &= t & t \otimes e &= t & \operatorname{act}_{1_{R}}(t) &= t \\
\operatorname{act}_{r}(\operatorname{act}_{r'}(t)) &= \operatorname{act}_{r\cdot r'}(t) & \operatorname{act}_{r}(t \otimes t') &= \operatorname{act}_{r}(t) \otimes\operatorname{act}_{r}(t') & \operatorname{act}_{r}(e) &= e
\end{aligned} t ⊗ ( t ′ ⊗ t ′′ ) act r ( act r ′ ( t )) = ( t ⊗ t ′ ) ⊗ t ′′ = act r ⋅ r ′ ( t ) e ⊗ t act r ( t ⊗ t ′ ) = t = act r ( t ) ⊗ act r ( t ′ ) t ⊗ e act r ( e ) = t = e act 1 R ( t ) = t Equivalently, a weighted monoid is a monoid ( M , ⊗ , e ) (M, \otimes, e) ( M , ⊗ , e ) with an action of the multiplicative monoid ( R , ⋅ , 1 R ) (R, \mathord{\cdot}, 1_{R}) ( R , ⋅ , 1 R ) by monoid homomorphisms. That is, act 1 \operatorname{act}_{1} act 1 is the identity, act r ∘ act r ′ = act r ⋅ r ′ \operatorname{act}_{r} \circ\operatorname{act}_{r'} = \operatorname{act}_{r\cdot r'} act r ∘ act r ′ = act r ⋅ r ′ , and each act r \operatorname{act}_{r} act r preserves ⊗ \otimes ⊗ and e e e . This makes the theory of weighted monoids the tensor of the theory of monoids with the theory of writer for ( R , ⋅ , 1 R ) (R, \mathord{\cdot}, 1_{R}) ( R , ⋅ , 1 R ) [23 ] . Its free model is the writer monad transformer for ( R , ⋅ , 1 R ) (R, \mathord{\cdot}, 1_{R}) ( R , ⋅ , 1 R ) applied to the list monad, List ( R × X ) \operatorname{List}(R \times X) List ( R × X ) [23 Thm. 12] .
Example 2.5 (Theory of R R R -Semimodules). The theory of R R R -semimodules [19 Ch. 14] models computations that can be combined into formal linear combinations. Here the semiring R R R provides coefficients describing quantitative information such as multiplicities or costs. By choosing different semirings, one recovers familiar computational structures, including finite sets (Boolean semiring) and finite multisets (natural numbers). Formally, let ( R , + , ⋅ , 0 , 1 ) (R, +, \mathord{\cdot}, 0, 1) ( R , + , ⋅ , 0 , 1 ) be a semiring. We define the theory T R - S e m i \mathcal{T}_{R\text{-}\mathrm{Semi}} T R - Semi to consist of a signature Σ R - S e m i \Sigma_{R\text{-}\mathrm{Semi}} Σ R - Semi with:
Intuitively, + + + and scale r \operatorname{scale}_{r} scale r together form linear combinations of computations. + + + adds two computations, 0 0 0 represents the empty combination, and scale r ( t ) \operatorname{scale}_{r}(t) scale r ( t ) scales the computation t t t by the coefficient
r r r . The equations of T R \mathcal{T}_{R} T R -Semi are:
t + ( t ′ + t ′ ′ ) = ( t + t ′ ) + t ′ ′ t + t ′ = t ′ + t t + 0 = t scale 1 ( t ) = t scale r ( scale r ′ ( t ) ) = scale r ⋅ r ′ ( t ) scale r ( t + t ′ ) = scale r ( t ) + scale r ( t ′ ) scale r + r ′ ( t ) = scale r ( t ) + scale r ′ ( t ) scale 0 ( t ) = 0 \begin{aligned}
t + (t' + t'') &= (t + t') + t'' & t + t' &= t' + t & t + 0 &= t & \operatorname{scale}_{1}(t) &= t \\
\operatorname{scale}_{r}(\operatorname{scale}_{r'}(t)) &= \operatorname{scale}_{r\cdot r'}(t) & \operatorname{scale}_{r}(t + t') &= \operatorname{scale}_{r}(t) + \operatorname{scale}_{r}(t') \\
\operatorname{scale}_{r+r'}(t) &= \operatorname{scale}_{r}(t) + \operatorname{scale}_{r'}(t) & \operatorname{scale}_{0}(t) &= 0
\end{aligned} t + ( t ′ + t ′′ ) scale r ( scale r ′ ( t )) scale r + r ′ ( t ) = ( t + t ′ ) + t ′′ = scale r ⋅ r ′ ( t ) = scale r ( t ) + scale r ′ ( t ) t + t ′ scale r ( t + t ′ ) scale 0 ( t ) = t ′ + t = scale r ( t ) + scale r ( t ′ ) = 0 t + 0 = t scale 1 ( t ) = t
Example 2.6 (Probability, Theory of Convex Spaces). The theory of convex spaces [14 , 45 ] axiomatizes a notion of biased coin flip. For every probability p ∈ [ 0 , 1 ] p \in[0,1] p ∈ [ 0 , 1 ] we have a binary operation
t 1 + p t 2 t_1 +_p t_2 t 1 + p t 2
that we interpret as flipping a coin with probability p p p and executing t 1 t_1 t 1 if true and t 2 t_2 t 2 if false. The equations are natural probabilistic laws:
t 1 + 1 t 2 = t 1 t 1 + 0 t 2 = t 2 t + p t = t t 1 + p t 2 = t 2 + 1 − p t 1 \begin{aligned}
t_1 +_1 t_2 &= t_1 & t_1 +_0 t_2 &= t_2 & t +_p t &= t & t_1 +_p t_2 &= t_2 +_{1-p} t_1
\end{aligned} t 1 + 1 t 2 = t 1 t 1 + 0 t 2 = t 2 t + p t = t t 1 + p t 2 = t 2 + 1 − p t 1
( t 1 + p t 2 ) + q t 3 = t 1 + p q ( t 2 + ( 1 − p ) q 1 − p q t 3 ) (t_1 +_p t_2) +_q t_3 = t_1 +_{pq} \left(t_2 +_{\frac{(1-p)q}{1-pq}} t_3\right) ( t 1 + p t 2 ) + q t 3 = t 1 + pq ( t 2 + 1 − pq ( 1 − p ) q t 3 )
The first two laws state that full probability is deterministic. The next, idempotence, says a coin flip between the same choice is unnecessary. The next, symmetry, states that probabilistic choice is symmetric under reordering of branches (with inverted probabilities). The last, quantitative associativity, allows for nesting coin flips in an arbitrary order (with adjusted probability). Note that the last only applies when p q ≠ 1 pq \ne1 pq = 1 .
Example 2.7 (Pre-convex spaces). The theory of pre-convex spaces has the same operations as convex spaces but drops the idempotence and symmetry laws.
An algebra A : Alg Σ A : \operatorname{Alg}_{\Sigma} A : Alg Σ for a signature Σ \Sigma Σ is a set ∣ A ∣ |A| ∣ A ∣ which provides an interpretation ⟦ op ⟧ A : ∣ A ∣ ar ( op ) → ∣ A ∣ \llbracket\operatorname{op} \rrbracket_A : |A|^{\operatorname{ar}(\operatorname{op})} \to|A| [ [ op ] ] A : ∣ A ∣ ar ( op ) → ∣ A ∣ for all operations op : Ops \operatorname{op} : \operatorname{Ops} op : Ops , written ⟦ op ⟧ \llbracket\operatorname{op} \rrbracket [ [ op ] ] when A A A is clear. Any A : Alg Σ A : \operatorname{Alg}_{\Sigma} A : Alg Σ can be used to interpret a Term Σ ( n ) \operatorname{Term}_{\Sigma}(n) Term Σ ( n ) . We denote an environment Env A ( n ) : = ∣ A ∣ n \operatorname{Env}_A(n) := |A|^n Env A ( n ) := ∣ A ∣ n to be an assignment of the n n n free variables to elements of ∣ A ∣ |A| ∣ A ∣ .
⟦ _ ⟧ : Term Σ ( n ) → Env A ( n ) → ∣ A ∣ ⟦ var i ⟧ ( γ ) : = γ i ⟦ op i ( t ⃗ ) ⟧ ( γ ) : = ⟦ op i ⟧ ( ⟦ t ⟧ ( γ ) → ) \begin{aligned}
\llbracket\_ \rrbracket&: \operatorname{Term}_{\Sigma}(n) \to\operatorname{Env}_A(n) \to|A| \\
\llbracket\operatorname{var}\ i \rrbracket(\gamma) &:= \gamma_i \\
\llbracket\operatorname{op}_i(\vec{t}) \rrbracket(\gamma) &:= \llbracket\operatorname{op}_i \rrbracket(\overrightarrow{\llbracket t \rrbracket(\gamma)})
\end{aligned} [ [ _ ] ] [ [ var i ] ] ( γ ) [ [ op i ( t ) ] ] ( γ ) : Term Σ ( n ) → Env A ( n ) → ∣ A ∣ := γ i := [ [ op i ] ] ( [ [ t ] ] ( γ ) )
Thus, a model for theory T \mathcal{T} T is an algebra A : Alg Σ A : \operatorname{Alg}_{\Sigma} A : Alg Σ for the signature of T \mathcal{T} T such that all equations hold in all environments.
A ⊨ T : = ∀ ( eq : Eqns ) , ( γ : Env A ( ctx eq ) ) . ⟦ lhs ⟧ ( γ ) = ⟦ rhs ⟧ ( γ ) A \models\mathcal{T} := \forall(\operatorname{eq} : \operatorname{Eqns}),\;(\gamma: \operatorname{Env}_A(\operatorname{ctx}_{\operatorname{eq}})).\ \llbracket\operatorname{lhs} \rrbracket(\gamma) = \llbracket\operatorname{rhs} \rrbracket(\gamma) A ⊨ T := ∀ ( eq : Eqns ) , ( γ : Env A ( ctx eq )) . [ [ lhs ] ] ( γ ) = [ [ rhs ] ] ( γ )
Given two algebras A , A ′ : Alg Σ A, A' : \operatorname{Alg}_{\Sigma} A , A ′ : Alg Σ for a fixed Σ \Sigma Σ , an algebra homomorphism is a function f : ∣ A ∣ → ∣ A ′ ∣ f : |A| \to|A'| f : ∣ A ∣ → ∣ A ′ ∣ that commutes with all the operations of Σ \Sigma Σ .
f ( ⟦ op ⟧ A ( a ⃗ ) ) = ⟦ op ⟧ A ′ ( f ( a ) → ) f(\llbracket\operatorname{op} \rrbracket_A(\vec{a})) = \llbracket\operatorname{op} \rrbracket_{A'}(\overrightarrow{f(a)}) f ( [ [ op ] ] A ( a )) = [ [ op ] ] A ′ ( f ( a ) )
We denote ALG Σ \operatorname{ALG}_{\Sigma} ALG Σ as the category of Σ \Sigma Σ algebras and algebra homomorphisms. MOD T \operatorname{MOD}_{\mathcal{T}} MOD T is the full subcategory of ALG Σ \operatorname{ALG}_{\Sigma} ALG Σ consisting of the models of T \mathcal{T} T , the algebras A A A where A ⊨ T A \models\mathcal{T} A ⊨ T . For any algebraic theory T \mathcal{T} T the forgetful functor U : MOD T → Set U : \operatorname{MOD}_{\mathcal{T}} \to\operatorname{Set} U : MOD T → Set has a left adjoint F : Set → MOD T F : \operatorname{Set} \to\operatorname{MOD}_{\mathcal{T}} F : Set → MOD T and from this adjunction we have a monad T T T on Set \operatorname{Set} Set given by T = U ∘ F T = U \circ F T = U ∘ F . Conversely, every finitary monad on Set \operatorname{Set} Set is the free model monad of some algebraic theory [36 ] .
Example 2.8. Any theory T \mathcal{T} T has a free model for any set X X X which is given by terms Term Σ ( X ) / Eqns \operatorname{Term}_{\Sigma}(X) / \operatorname{Eqns} Term Σ ( X ) / Eqns quotiented by the smallest congruence generated by Eqns \operatorname{Eqns} Eqns . We call this the term model of a theory T \mathcal{T} T . We present Term T ( X ) \operatorname{Term}_{\mathcal{T}}(X) Term T ( X ) as a quotient inductive recursive type below. Note that for a theory without equations, this type boils down to Term Σ ( X ) \operatorname{Term}_{\Sigma}(X) Term Σ ( X ) .
x : X op : Ops ∀ i . t i : Term T ( X ) eq : Eqns γ : Env Term T ( X ) ( ctx eq ) var x : Term T ( X ) op ( t 1 , t 2 , … , t ar ( op ) ) : Term T ( X ) ⟦ lhs eq ⟧ ( γ ) = ⟦ rhs eq ⟧ ( γ ) \begin{aligned}
&x : X && \operatorname{op} : \operatorname{Ops} && \forall i.\ t_i : \operatorname{Term}_{\mathcal{T}}(X) && \operatorname{eq} : \operatorname{Eqns} && \gamma: \operatorname{Env}_{\operatorname{Term}_{\mathcal{T}}(X)}(\operatorname{ctx}_{\operatorname{eq}}) \\
&\operatorname{var}\ x : \operatorname{Term}_{\mathcal{T}}(X) && \operatorname{op}(t_1,t_2,\ldots,t_{\operatorname{ar}(\operatorname{op})}) : \operatorname{Term}_{\mathcal{T}}(X) && \llbracket\operatorname{lhs}_{\operatorname{eq}}\rrbracket(\gamma) = \llbracket\operatorname{rhs}_{\operatorname{eq}}\rrbracket(\gamma)
\end{aligned} x : X var x : Term T ( X ) op : Ops op ( t 1 , t 2 , … , t ar ( op ) ) : Term T ( X ) ∀ i . t i : Term T ( X ) [ [ lhs eq ] ] ( γ ) = [ [ rhs eq ] ] ( γ ) eq : Eqns γ : Env Term T ( X ) ( ctx eq ) T \mathcal{T} T being a free model monad means that for every set X X X , T ( X ) T(X) T ( X ) is a model of T \mathcal{T} T , with an operation ⟦ op ⟧ : T ( X ) ar ( op ) → T ( X ) \llbracket\operatorname{op}\rrbracket: T(X)^{\operatorname{ar}(\operatorname{op})} \to T(X) [ [ op ] ] : T ( X ) ar ( op ) → T ( X ) for every operation op \operatorname{op} op of Σ \Sigma Σ satisfying the equations Eqns \operatorname{Eqns} Eqns , together with a map η : X → T ( X ) \eta: X \to T(X) η : X → T ( X ) that is universal: for every model M M M and function f : X → ∣ M ∣ f : X \to|M| f : X → ∣ M ∣ there is a unique homomorphism ! f : T ( X ) → M !_f : T(X) \to M ! f : T ( X ) → M with ! f ∘ η = f !_f \circ\eta= f ! f ∘ η = f . The monad structure of T T T comes from this universal property. Its unit is η \eta η , and its multiplication μ : T 2 ( X ) → T ( X ) \mu: T^2(X) \to T(X) μ : T 2 ( X ) → T ( X ) is ! id !_{\operatorname{id}} ! id , the unique homomorphism extending the identity on T ( X ) T(X) T ( X ) .
Example 2.9. For set X X X , model M M M , and function f : X → ∣ M ∣ f : X \to|M| f : X → ∣ M ∣ , the unique homomorphism out of the term model is defined by recursion.2
! f : Term T ( X ) → M ! f ( var x ) = f ( x ) ! f ( op ( t ⃗ ) ) = ⟦ op ⟧ M ( ! f ( t ⃗ ) ) \begin{aligned}
!_f &: \operatorname{Term}_{\mathcal{T}}(X) \to M \\
!_f(\operatorname{var}\ x) &= f(x) \\
!_f(\operatorname{op}(\vec{t})) &= \llbracket\operatorname{op}\rrbracket_M(!_f(\vec{t}))
\end{aligned} ! f ! f ( var x ) ! f ( op ( t )) : Term T ( X ) → M = f ( x ) = [ [ op ] ] M ( ! f ( t ))
Free Model Monads as Canonical Forms
While the free model always exists by this syntactic construction, it is not a very useful model for computation. In practice, for each theory we seek out more explicit formulations of the free models. When the construction is particularly concrete, we can think of these as canonical forms of terms in the syntactic free model.
Example 2.10. The free model of T w r i t e r \mathcal{T}_{\mathrm{writer}} T writer has carrier T ( X ) = M × X T(X) = M \times X T ( X ) = M × X . The operations are given by:
tell e ( m , x ) = ( m , x ) tell n ( m , x ) = ( n ⊗ m , x ) η ( x ) = ( e , x ) \operatorname{tell}_{e}(m,x)=(m,x) \qquad\operatorname{tell}_{n}(m,x)=(n \otimes m,x) \qquad\eta(x)=(e,x) tell e ( m , x ) = ( m , x ) tell n ( m , x ) = ( n ⊗ m , x ) η ( x ) = ( e , x ) An element ( m , x ) (m,x) ( m , x ) can be interpreted as a canonical syntactic term tell m ( var x ) \operatorname{tell}_{m}(\operatorname{var}\ x) tell m ( var x ) .
Example 2.11. The free model of T e r r \mathcal{T}_{\mathrm{err}} T err has carrier T ( X ) = X + 1 T(X) = X + 1 T ( X ) = X + 1 , with err = inr ( ∗ ) \operatorname{err} = \operatorname{inr}(*) err = inr ( ∗ ) and η ( x ) = inl ( x ) \eta(x) = \operatorname{inl}(x) η ( x ) = inl ( x ) .
Example 2.12. The free model of T s t a t e \mathcal{T}_{\mathrm{state}} T state has carrier T ( X ) : = S → X × S T(X) := S \to X \times S T ( X ) := S → X × S . The operations are given by:
set s ( f ) = λ _ . f ( s ) get ( f ) = λ s . f ( s ) ( s ) η ( x ) = λ s . ( x , s ) \operatorname{set}_{s}(f)=\lambda\_. f(s) \qquad\operatorname{get}(f)=\lambda s. f(s)(s) \qquad\eta(x)=\lambda s.(x,s) set s ( f ) = λ _. f ( s ) get ( f ) = λ s . f ( s ) ( s ) η ( x ) = λ s . ( x , s ) An element f f f can be interpreted as a canonical syntactic term get ( s ↦ set s ′ ( var x ) ) \operatorname{get}(s \mapsto\operatorname{set}_{s'}(\operatorname{var}\ x)) get ( s ↦ set s ′ ( var x )) , where ( x , s ′ ) = f ( s ) (x,s')=f(s) ( x , s ′ ) = f ( s ) .
Example 2.13. The free model of T w m o n \mathcal{T}_{\mathrm{wmon}} T wmon has carrier T ( X ) = List ( R × X ) T(X) = \operatorname{List}(R \times X) T ( X ) = List ( R × X ) with operations
e = [ ] t ⊗ t ′ = append ( t , t ′ ) act r ( t ) = map ( ( r ′ , x ) ↦ ( r ⋅ r ′ , x ) ) ( t ) η ( x ) = [ ( 1 R , x ) ] e=[] \qquad t \otimes t'=\operatorname{append}(t,t') \qquad\operatorname{act}_{r}(t)=\operatorname{map}((r',x)\mapsto(r\cdot r',x))(t) \qquad\eta(x)=[(1_R,x)] e = [ ] t ⊗ t ′ = append ( t , t ′ ) act r ( t ) = map (( r ′ , x ) ↦ ( r ⋅ r ′ , x )) ( t ) η ( x ) = [( 1 R , x )] An element [ ( r , x ) , … ] [(r,x),\ldots] [( r , x ) , … ] can be interpreted as a “linear combination” act r ( var x ) ⊗ ⋯ \operatorname{act}_{r}(\operatorname{var}\ x)\otimes\cdots act r ( var x ) ⊗ ⋯ . We use quotes because ⊗ \otimes ⊗ is not commutative, so the order of the summands matters.
Example 2.14. The free model of T R - S e m i \mathcal{T}_{R\text{-}\mathrm{Semi}} T R - Semi T ( X ) = X → f i n R T(X) = X \to_{\mathrm{fin}} R T ( X ) = X → fin R that is, a finitely supported function into the semiring, which is 0 at all but finitely many x x x . Operations are given by
0 ( x ) = 0 ( t + t ′ ) ( x ) = t ( x ) + t ′ ( x ) scale r ( t ) ( x ) = r ⋅ t ( x ) η ( x ) ( x ) = 1 0(x) = 0 \qquad(t + t')(x) = t(x) + t'(x) \qquad\operatorname{scale}_{r}(t)(x) = r \cdot t(x) \qquad\eta(x)(x) = 1 0 ( x ) = 0 ( t + t ′ ) ( x ) = t ( x ) + t ′ ( x ) scale r ( t ) ( x ) = r ⋅ t ( x ) η ( x ) ( x ) = 1
η ( x ) ( y ) = 0 if x ≠ y \eta(x)(y) = 0 \text{ if } x \ne y η ( x ) ( y ) = 0 if x = y
An element f f f can be interpreted as a linear combination in a similar manner to weighted monoids. For weighted monoids the order of the terms is part of the element, since it is a list. Here it is not, so viewing f f f as a particular syntactic term requires choosing an order on the variables X X X . This can also be viewed as a quotient of the free weighted monoid.
Example 2.15. The free model for the theory of pre-convex spaces is given by
T ( X ) = { l : List ( ( 0 , 1 ] × X ) ∣ ∑ ( p , x ) ∈ l p = 1 } T(X) = \{l : \operatorname{List}((0,1] \times X) \mid\sum_{(p,x) \in l} p = 1\} T ( X ) = { l : List (( 0 , 1 ] × X ) ∣ ( p , x ) ∈ l ∑ p = 1 }
Note that the side condition ensures that such lists must be nonempty.
η ( x ) = [ ( 1 , x ) ] l 1 + 1 l 2 = l 1 l 1 + 0 l 2 = l 2 \eta(x) = [(1,x)] \qquad l_1 +_1 l_2 = l_1 \qquad l_1 +_0 l_2 = l_2 η ( x ) = [( 1 , x )] l 1 + 1 l 2 = l 1 l 1 + 0 l 2 = l 2
l 1 + p ∈ ( 0 , 1 ) l 2 = append ( map ( − ∗ p ) ( l 1 ) , map ( − ∗ ( 1 − p ) ) ( l 2 ) ) l_1 +_{p \in(0,1)} l_2 = \operatorname{append}(\operatorname{map}(- * p)(l_1), \operatorname{map}(- * (1-p))(l_2)) l 1 + p ∈ ( 0 , 1 ) l 2 = append ( map ( − ∗ p ) ( l 1 ) , map ( − ∗ ( 1 − p )) ( l 2 ))
An element [ ( p 1 , x 1 ) , ( p 2 , x 2 ) , … ] [(p_1,x_1),(p_2,x_2),\ldots] [( p 1 , x 1 ) , ( p 2 , x 2 ) , … ] can be viewed as a syntactic term η ( x 1 ) + p 1 η ( x 2 ) + p 2 / ( 1 − p 1 ) ⋯ \eta(x_1) +_{p_1} \eta(x_2) +_{p_2/(1-p_1)} \cdots η ( x 1 ) + p 1 η ( x 2 ) + p 2 / ( 1 − p 1 ) ⋯ .
Example 2.16. The free model for the theory of convex spaces is given by finite probability distributions T ( X ) = { D : X → f i n [ 0 , 1 ] ∣ ∑ x ∈ X D ( x ) = 1 } T(X) = \{D : X \to_{\mathrm{fin}} [0,1] \mid\sum_{x \in X} D(x) = 1\} T ( X ) = { D : X → fin [ 0 , 1 ] ∣ ∑ x ∈ X D ( x ) = 1 } . This can be viewed as a quotient of that of pre-convex spaces. Like modules of a semiring, it can be viewed as a term if we impose an ordering on the generating set X X X .
Call-by-Push-Value
Our language of study is a simply typed call-by-push-value (CBPV) [31 ] calculus parameterized by a finitary algebraic theory T = ( Σ , E q n s ) \mathcal{T} = (\Sigma, \mathrm{Eqns}) T = ( Σ , Eqns ) . There are two versions of this calculus that we work with: C B P V ( T ) \mathrm{CBPV}(\mathcal{T}) CBPV ( T ) , for which we will provide an operational semantics in § 4 , and C B P V + ( T ) \mathrm{CBPV}^{+}(\mathcal{T}) CBPV + ( T ) , for which we will provide a denotational semantics in § 3 . C B P V + ( T ) \mathrm{CBPV}^{+}(\mathcal{T}) CBPV + ( T ) is a strict extension of C B P V ( T ) \mathrm{CBPV}(\mathcal{T}) CBPV ( T ) with complex values and complex stacks . The purpose of this distinction is discussed at length by Levy [31 ] but it suffices to know that excluding complex values preserves operational canonicity while including complex values and stacks results in a cleaner equational theory. The syntax and typing rules of the full C B P V + ( T ) \mathrm{CBPV}^{+}(\mathcal{T}) CBPV + ( T ) are shown in Figure 1 , where the gray forms and rules belong to C B P V + ( T ) \mathrm{CBPV}^{+}(\mathcal{T}) CBPV + ( T ) only. The rules are standard [31 ] and are listed for reference.
Figure 1. CBPV(T \mathcal{T} T ) & CBPV+ ( T ) ^{+}(\mathcal{T}) + ( T )
Γ ⊢ V : A Γ ∣ ⋅ ⊢ M : B Γ ∣ ∙ : B ⊢ S : B ′ \Gamma\vdash V : A \qquad\Gamma\mid\cdot\vdash M : B \qquad\Gamma\mid\bullet: B \vdash S : B' Γ ⊢ V : A Γ ∣ ⋅ ⊢ M : B Γ ∣ ∙ : B ⊢ S : B ′
These are the judgments for values, computations and stacks. Here Γ \Gamma Γ is a context of value variables, A A A is a value type, and B B B and B ′ B' B ′ are computation types. In CBPV, values are data which can be bound to variables, passed around, and be duplicated or discarded. Computations represent potentially effectful programs, and a computation of type F A F A F A performs work before returning a value of type A A A . Stacks are a generalized form of evaluation context that represent the remainder of a computation and a single hole into which a computation may be plugged. For convenience, we present the rules using a combined computation and stack judgment form Γ ∣ Δ ⊢ M : B \Gamma\mid\Delta\vdash M : B Γ ∣ Δ ⊢ M : B containing a stoup Δ \Delta Δ , which is either empty, written ⋅ \cdot ⋅ , or a single hole ∙ : B ′ \bullet: B' ∙ : B ′ . Rules with an unspecified stoup Δ \Delta Δ hold for both computation and stack judgment forms while an empty ( ⋅ ) (\cdot) ( ⋅ ) or full ( ∙ ) (\bullet) ( ∙ ) stoup represent a computation judgment or stack judgment respectively. The complex stacks of C B P V + ( T ) \mathrm{CBPV}^{+}(\mathcal{T}) CBPV + ( T ) are the gray stack forms λ x : A . S \lambda x : A.S λ x : A . S , ⟨ S , S ′ ⟩ \langle S,S'\rangle ⟨ S , S ′ ⟩ and ⟨ ⟩ \langle\rangle ⟨ ⟩ of Figure 1 . The typing rules for λ \lambda λ , pairing and ⟨ ⟩ \langle\rangle ⟨ ⟩ use a stoup Δ + \Delta^{+} Δ + , which may be a hole in C B P V + ( T ) \mathrm{CBPV}^{+}(\mathcal{T}) CBPV + ( T ) and is always empty in C B P V ( T ) \mathrm{CBPV}(\mathcal{T}) CBPV ( T ) .
We present the substitution operations, stack operations, and the equational theory of the language in Figure 2 . These are standard except for the laws related to the algebraic theory. There are four substitution operations on our syntax; value substitution V [ γ ] V[\gamma] V [ γ ] , computation substitution M [ γ ] M[\gamma] M [ γ ] , stack substitution S [ γ ] S[\gamma] S [ γ ] , and stack plugging S [ M ] S[M] S [ M ] . A substitution γ : Γ ′ ⇒ Γ \gamma: \Gamma' \Rightarrow\Gamma γ : Γ ′ ⇒ Γ assigns to each variable x : A x : A x : A of Γ \Gamma Γ a value Γ ′ ⊢ γ ( x ) : A \Gamma' \vdash\gamma(x) : A Γ ′ ⊢ γ ( x ) : A , and V [ γ ] V[\gamma] V [ γ ] replaces each variable of V V V by its value. In Figure 2 we name each operation by its result, so V [ γ ] V[\gamma] V [ γ ] there stands for the map V , γ ↦ V [ γ ] V,\gamma\mapsto V[\gamma] V , γ ↦ V [ γ ] . We additionally have notions of composing substitutions δ [ γ ] \delta[\gamma] δ [ γ ] , which substitutes γ \gamma γ into each value of δ \delta δ , and composing stacks S ′ [ S ] S'[S] S ′ [ S ] , the stack S ′ S' S ′ with S S S in its hole. β \beta β and η \eta η laws hold for all type connectives in C B P V + ( T ) \mathrm{CBPV}^{+}(\mathcal{T}) CBPV + ( T ) , and Figure 2 shows a fragment.
Figure 2. Equational Theory of CBPV⁺(T \mathcal{T} T )
Our calculus supports the construction of basic values with an empty type 0 0 0 , unit type 1 1 1 , coproduct type A + A ′ A + A' A + A ′ , and product type A × A ′ A \times A' A × A ′ . Eliminating a value is considered to be a computation in CBPV, but C B P V + \mathrm{CBPV}^{+} CBPV + allows elimination of values into values. A computation M : B M : B M : B can be considered as value, but only after it is suspended via a thunk ( M ) : U B \operatorname{thunk}(M) : U B thunk ( M ) : U B . For computation types, we have the unit computation type ⊤ \top ⊤ , whose introduction form is the empty tuple ⟨ ⟩ \langle\rangle ⟨ ⟩ , functions A → B A \to B A → B , computation product B & B ′ B \mathbin{\&} B' B & B ′ , and a type representing effectful values F A F A F A .
In addition to the typical simply typed CBPV connectives, our calculus includes syntax for the operations of the given theory T \mathcal{T} T . For any operation o p : O p s \mathrm{op} : \mathrm{Ops} op : Ops and ar ( o p ) \operatorname{ar}(\mathrm{op}) ar ( op ) many computations Γ ∣ ⋅ ⊢ M i : B \Gamma\mid\cdot\vdash M_i : B Γ ∣ ⋅ ⊢ M i : B of type B B B we have a computation Γ ∣ ⋅ ⊢ o p ( M → ) : B \Gamma\mid\cdot\vdash\mathrm{op}(\overrightarrow{M}) : B Γ ∣ ⋅ ⊢ op ( M ) : B . As an example, for the theory of state with two states, 0 and 1, we have:
Γ ∣ ⋅ ⊢ M : B Γ ∣ ⋅ ⊢ N : B Γ ∣ ⋅ ⊢ get ( M , N ) : B Γ ∣ ⋅ ⊢ M : B Γ ∣ ⋅ ⊢ set 0 ( M ) : B Γ ∣ ⋅ ⊢ M : B Γ ∣ ⋅ ⊢ set 1 ( M ) : B \frac{\Gamma\mid\cdot\vdash M : B \qquad\Gamma\mid\cdot\vdash N : B}{\Gamma\mid\cdot\vdash\operatorname{get}(M,N) : B}
\qquad
\frac{\Gamma\mid\cdot\vdash M : B}{\Gamma\mid\cdot\vdash\operatorname{set}_{0}(M) : B}
\qquad
\frac{\Gamma\mid\cdot\vdash M : B}{\Gamma\mid\cdot\vdash\operatorname{set}_{1}(M) : B} Γ ∣ ⋅ ⊢ get ( M , N ) : B Γ ∣ ⋅ ⊢ M : B Γ ∣ ⋅ ⊢ N : B Γ ∣ ⋅ ⊢ set 0 ( M ) : B Γ ∣ ⋅ ⊢ M : B Γ ∣ ⋅ ⊢ set 1 ( M ) : B Γ ∣ ⋅ ⊢ M : B
Of particular interest are the laws induced by the algebraic theory T \mathcal{T} T . Stack plugging preserves the algebraic structure, yielding the familiar algebraicity (or homomorphism) property of algebraic effects [37 ] . Finally, for every context Γ \Gamma Γ and computation type B B B , the set of computations Γ ∣ ⋅ ⊢ B \Gamma\mid\cdot\vdash B Γ ∣ ⋅ ⊢ B carries the structure of a Σ \Sigma Σ -algebra and, moreover, satisfies the equations of T \mathcal{T} T . Hence, it is a model of T \mathcal{T} T . In Figure 2 , t [ M → ] t[\overrightarrow{M}] t [ M ] is the computation obtained from a term t t t by replacing its variables with M → \overrightarrow{M} M , so each equation of T \mathcal{T} T is a law.
Denotational Semantics and Equational Canonicity
In this section we establish equational canonicity for C B P V + ( T ) \mathrm{CBPV}^{+}(\mathcal{T}) CBPV + ( T ) . Our proof is organized around a CBPV+ doctrine , an abstract notion of model for CBPV. We first describe the syntactic and denotational models as instances of this doctrine, then construct a glued logical relations model. Initiality of the syntactic model yields the Fundamental Theorem, from which equational canonicity follows.
CBPV+ Doctrine
This section describes the common categorical framework from which the syntax of C B P V + ( T ) \mathrm{CBPV}^{+}(\mathcal{T}) CBPV + ( T ) , denotational semantics, and equational canonicity logical relation arise. To keep the presentation lightweight, we describe the doctrine only for unary C B P V + \mathrm{CBPV}^{+} CBPV + . By unary CBPV, we mean a restricted version of the CBPV calculus for which our judgment forms only have one variable.
x : A ⊢ V : A ′ x : A ⊢ M : B ∙ : B ⊢ S : B ′ x : A \vdash V : A'
\qquad
x : A \vdash M : B
\qquad
\bullet: B \vdash S : B' x : A ⊢ V : A ′ x : A ⊢ M : B ∙ : B ⊢ S : B ′
Consequently, the unary calculus does not admit a function type. Extending the construction to arbitrary contexts requires enriched category theory, but otherwise introduces no fundamentally new ideas. For our set-based models the enrichment is routine, so we do not discuss it further. A
unary CBPV⁺ doctrine consists of a functor
O : V o p × C → MOD T . \mathcal{O} : \mathcal{V}^{\mathrm{op}} \times\mathcal{C} \to\operatorname{MOD}_{\mathcal{T}}. O : V op × C → MOD T .
Levy [31 ] models CBPV with a profunctor V o p × C → S e t \mathcal{V}^{\mathrm{op}} \times\mathcal{C} \to\mathbf{Set} V op × C → Set , which sends A A A and B B B to the set of computations from A A A to B B B . We replace S e t \mathbf{Set} Set by MOD T \operatorname{MOD}_{\mathcal{T}} MOD T , so these computations form a model of T \mathcal{T} T .
The easiest way to understand this definition is through a concrete instance from which the general pattern becomes apparent. We begin by showing that the syntax of CBPV⁺(T \mathcal{T} T ) quotiented by its equational theory forms an instance of a unary CBPV⁺ doctrine which we will call the syntactic model . Below, values, computations and stacks are taken up to the equations of Figure 2 . V \mathcal{V} V is a category where the objects are value types A A A , morphisms are values A ⊢ V : A ′ A \vdash V : A' A ⊢ V : A ′ , and composition is given by value substitution V [ W ] V[W] V [ W ] . C \mathcal{C} C is a category where the objects are computation types B B B , morphisms are stacks ∙ : B ⊢ S : B ′ \bullet: B \vdash S : B' ∙ : B ⊢ S : B ′ , and composition is composition of stacks S ′ [ S ] S'[S] S ′ [ S ] . For any value type A A A and computation type B B B , we have O [ A , B ] \mathcal{O}[A,B] O [ A , B ] is a model of T \mathcal{T} T with carrier given as computations A ⊢ M : B A \vdash M : B A ⊢ M : B and the operations are given by the syntactic operations A ⊢ op ( M → ) : B A \vdash\operatorname{op}(\overrightarrow{M}) : B A ⊢ op ( M ) : B . The contravariant action of O \mathcal{O} O is given by substituting values into computations, while its covariant action is given by plugging computations into stacks. Both operations are homomorphisms. With functoriality specified separately in both arguments, substitution and stack plugging commute.
( S [ M ] ) [ V ] = S [ M [ V ] ] . (S[M])[V] = S[M[V]]. ( S [ M ]) [ V ] = S [ M [ V ]] .
To support the CBPV type connectives, a doctrine must have suitable type structure . By type structure, we mean the packaging of the introduction and elimination rules of a type along with β \beta β and η \eta η equations. From the perspective of a CBPV⁺ doctrine, type structure is simply a universal property. For example, value products are products in the category V \mathcal{V} V , characterized by the natural isomorphism
V [ _ , A × A ′ ] ≅ V [ _ , A ] × V [ _ , A ′ ] . \mathcal{V}[\,\_, A \times A'] \cong\mathcal{V}[\,\_, A] \times\mathcal{V}[\,\_, A']. V [ _ , A × A ′ ] ≅ V [ _ , A ] × V [ _ , A ′ ] .
Unpacking this definition recovers the pairing and projection rules together with their β \beta β - and η \eta η -laws. Naturality of the isomorphism expresses that both pairing and projections commute with substitution, yielding laws such as
( V , W ) [ γ ] = ( V [ γ ] , W [ γ ] ) and π i ( V [ γ ] ) = ( π i V ) [ γ ] . (V,W)[\gamma] = (V[\gamma],W[\gamma]) \qquad\text{and} \qquad\pi_i(V[\gamma]) = (\pi_i V)[\gamma]. ( V , W ) [ γ ] = ( V [ γ ] , W [ γ ]) and π i ( V [ γ ]) = ( π i V ) [ γ ] .
Here π i V \pi_i V π i V is the complex value case× ( V ) { x 1 , x 2 . x i } _\times(V)\{x_1,x_2.x_i\} × ( V ) { x 1 , x 2 . x i } of CBPV+ ( T ) ^+(\mathcal{T}) + ( T ) . The universal property of every connective is in Appendix § 12 of this paper.
Denotational Semantics
We instantiate the CBPV+ ^+ + doctrine using the standard adjunction model of CBPV [31 ] extended to algebraic effects. Value types are interpreted in Set, computation types are interpreted in the category MOD T \operatorname{MOD}_{\mathcal{T}} MOD T of models of the algebraic theory. A computation may be regarded either as a function or a homomorphism with the correspondence provided by the free-forgetful adjunction:
Set [ ⟦ Γ ⟧ , U ⟦ B ⟧ ] ≅ O [ ⟦ Γ ⟧ , ⟦ B ⟧ ] ≅ MOD T [ F ⟦ Γ ⟧ , ⟦ B ⟧ ] . \operatorname{Set}[\llbracket\Gamma\rrbracket,U\llbracket B \rrbracket] \cong\mathcal{O}[\llbracket\Gamma\rrbracket,\llbracket B \rrbracket] \cong\operatorname{MOD}_{\mathcal{T}}[F\llbracket\Gamma\rrbracket,\llbracket B \rrbracket]. Set [ [ [ Γ ] ] , U [ [ B ] ] ] ≅ O [ [ [ Γ ] ] , [ [ B ] ] ] ≅ MOD T [ F [ [ Γ ] ] , [ [ B ] ] ] .
The free computation type is interpreted by the free model, while function and computation product types inherit their model structure pointwise from their codomain.
The initiality of the syntactic model means that we have a unique structure-preserving interpretation of CBPV+ ( T ) ^+(\mathcal{T}) + ( T ) syntax into this model. The recursive equations characterizing this interpretation are given in Figure 3 . The interpretation being a morphism of CBPV+ ^+ + doctrines means it preserves substitution, stack plugging, the algebraic operations, and all type structure. In the figure, ⟦ B ⟧ ⊸ ⟦ B ′ ⟧ \llbracket B \rrbracket\multimap\llbracket B' \rrbracket [ [ B ] ] ⊸ [ [ B ′ ] ] is the set of homomorphisms from ⟦ B ⟧ \llbracket B \rrbracket [ [ B ] ] to ⟦ B ′ ⟧ \llbracket B' \rrbracket [ [ B ′ ] ] , and α B \alpha_B α B is the model structure of ⟦ B ⟧ \llbracket B \rrbracket [ [ B ] ] , giving the interpretation α B op \alpha_B^{\operatorname{op}} α B op of each operation. Sequencing x ← M ; N x \leftarrow M;N x ← M ; N is interpreted using the free model property. The map a ↦ ⟦ N ⟧ ( γ , a ) a \mapsto\llbracket N \rrbracket(\gamma,a) a ↦ [ [ N ] ] ( γ , a ) extends to a unique homomorphism ! ! ! out of the free model F ⟦ A ⟧ F\llbracket A \rrbracket F [ [ A ] ] , which is then applied to ⟦ M ⟧ ( γ ) \llbracket M \rrbracket(\gamma) [ [ M ] ] ( γ ) . For closed terms we write ⟦ _ ⟧ v : Val ( A ) → ⟦ A ⟧ \llbracket\_ \rrbracket_v : \operatorname{Val}(A) \to\llbracket A \rrbracket [ [ _ ] ] v : Val ( A ) → [ [ A ] ] and ⟦ _ ⟧ c : Comp ( B ) → U ⟦ B ⟧ \llbracket\_ \rrbracket_c : \operatorname{Comp}(B) \to U\llbracket B \rrbracket [ [ _ ] ] c : Comp ( B ) → U [ [ B ] ] for V ↦ ⟦ V ⟧ ( ⋆ ) V \mapsto\llbracket V \rrbracket(\star) V ↦ [ [ V ] ] ( ⋆ ) and M ↦ ⟦ M ⟧ ( ⋆ ) M \mapsto\llbracket M \rrbracket(\star) M ↦ [ [ M ] ] ( ⋆ ) .
Figure 3. Denotational Semantics of CBPV+(T \mathcal{T} T ), a Fragment glued model. The interpretation of each value type and computation type is determined entirely by the universal properties of the glued model.
Equational Canonicity Logical Relation
We now instantiate the CBPV+ ^+ + doctrine with a logical relations model obtained by gluing predicates onto the syntactic model. Rather than interpreting value types by sets and computation types by models of T \mathcal{T} T , we enrich each with a predicate. Let Val ( A ) \operatorname{Val}(A) Val ( A ) and Comp ( B ) \operatorname{Comp}(B) Comp ( B ) be the sets of closed values of type A A A and closed computations of type B B B . A value predicate P : VPred ( A ) P : \operatorname{VPred}(A) P : VPred ( A ) is a map Val ( A ) → Prop \operatorname{Val}(A) \to\operatorname{Prop} Val ( A ) → Prop . Since closed computations carry the structure of a Σ \Sigma Σ -algebra, a computation predicate Q : CPred ( B ) Q : \operatorname{CPred}(B) Q : CPred ( B ) is a map Comp ( B ) → Prop \operatorname{Comp}(B) \to\operatorname{Prop} Comp ( B ) → Prop closed under Σ \Sigma Σ , meaning that Q ( op ( M → ) ) Q(\operatorname{op}(\overrightarrow{M})) Q ( op ( M )) holds whenever every Q ( M i ) Q(M_i) Q ( M i ) does. The glued value category consists of pairs ( A , P ) (A,P) ( A , P ) where A A A is a value type and P : VPred ( A ) P : \operatorname{VPred}(A) P : VPred ( A ) . A morphism ( A , P ) → ( A ′ , P ′ ) (A,P) \to(A',P') ( A , P ) → ( A ′ , P ′ ) is a value V : A ′ ⊸ A V : A' \multimap A V : A ′ ⊸ A with P ( W ) ⇒ P ′ ( V [ W ] ) P(W) \Rightarrow P'(V[W]) P ( W ) ⇒ P ′ ( V [ W ]) for all W : Val ( A ) W : \operatorname{Val}(A) W : Val ( A ) . Similarly, the glued computation category consists of pairs ( B , Q ) (B,Q) ( B , Q ) where B B B is a computation type and Q : CPred ( B ) Q : \operatorname{CPred}(B) Q : CPred ( B ) . A morphism ( B , Q ) → ( B ′ , Q ′ ) (B,Q) \to(B',Q') ( B , Q ) → ( B ′ , Q ′ ) is a stack σ : B ⊢ S : B ′ \sigma: B \vdash S : B' σ : B ⊢ S : B ′ with Q ( M ) ⇒ Q ′ ( S [ M ] ) Q(M) \Rightarrow Q'(S[M]) Q ( M ) ⇒ Q ′ ( S [ M ]) for all M : Comp ( B ) M : \operatorname{Comp}(B) M : Comp ( B ) . Finally, for every value object ( A , P ) (A,P) ( A , P ) and computation object ( B , Q ) (B,Q) ( B , Q ) , the functor consists of computations from A A A to B B B that preserve the logical predicates. Concretely,
O [ ( A , P ) , ( B , Q ) ] : = { A ∣ ⊢ M : B ∣ ∀ W : Val ( A ) . P ( W ) ⇒ Q ( M [ W ] ) } . \mathcal{O}[(A,P),(B,Q)] := \{A \mid\vdash M : B \mid\forall W : \operatorname{Val}(A).\,P(W) \Rightarrow Q(M[W])\}. O [( A , P ) , ( B , Q )] := { A ∣⊢ M : B ∣ ∀ W : Val ( A ) . P ( W ) ⇒ Q ( M [ W ])} .
The contravariant action of O \mathcal{O} O is given by value substitution, while the covariant action is given by stack plugging. Since Q : CPred ( B ) Q : \operatorname{CPred}(B) Q : CPred ( B ) is closed under the operations of Σ \Sigma Σ , the pointwise algebra structure on computations restricts to O [ ( A , P ) , ( B , Q ) ] \mathcal{O}[(A,P),(B,Q)] O [( A , P ) , ( B , Q )] , yielding another instance of the CBPV+ ^+ + doctrine.
As with the CBPV+ ^+ + doctrine itself, the construction above extends uniformly to full contexts [8 ] . By initiality of the syntactic model, there is a unique structure-preserving interpretation into the
We present the resulting logical predicates explicitly in Figure 4 . The relations are standard and C [ F A ] C[F A] C [ F A ] is the free computation predicate [6 , 27 ] , inductively generated by two cases. Whenever the value relation V [ A ] V[A] V [ A ] holds at V V V , we have that C [ F A ] ( ret V ) C[F A](\operatorname{ret} V) C [ F A ] ( ret V ) holds. Additionally, whenever the relation C [ F A ] C[F A] C [ F A ] holds at each operand M i M_i M i of operation op \operatorname{op} op , we have that C [ F A ] ( op ( M ⃗ ) ) C[F A](\operatorname{op}(\vec{M})) C [ F A ] ( op ( M )) holds.
Figure 4. CBPV+(T \mathcal{T} T ) Canonicity Logical Relation
Fundamental Theorem
Since the glued logical relations model is an instance of the CBPV+ doctrine, the initiality of the syntactic model means that we have a unique structure-preserving interpretation of the syntax into this model, and the fundamental theorem is a consequence of this interpretation. For completeness, a direct compatibility proof for the concrete logical relation is in Appendix § 9 .
Γ ⊨ V : A : = ∀ ( γ : Γ ) . G [ Γ ] ( γ ) ⇒ V [ A ] ( V [ γ ] ) \Gamma\models V : A := \forall(\gamma: \Gamma).\; G[\Gamma](\gamma) \Rightarrow V[A](V[\gamma]) Γ ⊨ V : A := ∀ ( γ : Γ ) . G [ Γ ] ( γ ) ⇒ V [ A ] ( V [ γ ])
Γ ∣ ⋅ ⊨ M : B : = ∀ ( γ : Γ ) . G [ Γ ] ( γ ) ⇒ C [ B ] ( M [ γ ] ) \Gamma\mid\cdot\models M : B := \forall(\gamma: \Gamma).\; G[\Gamma](\gamma) \Rightarrow C[B](M[\gamma]) Γ ∣ ⋅ ⊨ M : B := ∀ ( γ : Γ ) . G [ Γ ] ( γ ) ⇒ C [ B ] ( M [ γ ])
G [ ∅ ] : = ⊤ G[\emptyset] := \top G [ ∅ ] := ⊤
G [ Γ , x : A ] ( γ , V ) : = G [ Γ ] ( γ ) ∧ V [ A ] ( V ) G[\Gamma, x : A](\gamma, V) := G[\Gamma](\gamma) \wedge V[A](V) G [ Γ , x : A ] ( γ , V ) := G [ Γ ] ( γ ) ∧ V [ A ] ( V )
V [ 0 ] ( V ) : = ⊥ V[0](V) := \bot V [ 0 ] ( V ) := ⊥
V [ 1 ] ( V ) : = ⊤ V[1](V) := \top V [ 1 ] ( V ) := ⊤
V [ A + A ′ ] ( V ) : = { V [ A ] ( W ) if V = σ 1 W V [ A ′ ] ( W ) if V = σ 2 W V[A + A'](V) :=
\begin{cases}
V[A](W) & \text{if } V = \sigma_1 W \\
V[A'](W) & \text{if } V = \sigma_2 W
\end{cases} V [ A + A ′ ] ( V ) := { V [ A ] ( W ) V [ A ′ ] ( W ) if V = σ 1 W if V = σ 2 W
V [ A × A ′ ] ( V , V ′ ) : = V [ A ] ( V ) ∧ V [ A ′ ] ( V ′ ) V[A \times A'](V,V') := V[A](V) \wedge V[A'](V') V [ A × A ′ ] ( V , V ′ ) := V [ A ] ( V ) ∧ V [ A ′ ] ( V ′ )
V [ U B ] ( V ) : = C [ B ] ( force V ) V[U B](V) := C[B](\operatorname{force} V) V [ U B ] ( V ) := C [ B ] ( force V )
C [ ⊤ ] ( M ) : = ⊤ C[\top](M) := \top C [ ⊤ ] ( M ) := ⊤
C [ A → B ] ( M ) : = ∀ ( V : Val ( A ) ) . V [ A ] ( V ) ⇒ C [ B ] ( M V ) C[A \to B](M) := \forall(V : \operatorname{Val}(A)).\; V[A](V) \Rightarrow C[B](M\,V) C [ A → B ] ( M ) := ∀ ( V : Val ( A )) . V [ A ] ( V ) ⇒ C [ B ] ( M V )
C [ B & B ′ ] ( M ) : = C [ B ] ( π 1 ( M ) ) ∧ C [ B ′ ] ( π 2 ( M ) ) C[B \mathbin{\&} B'](M) := C[B](\pi_1(M)) \wedge C[B'](\pi_2(M)) C [ B & B ′ ] ( M ) := C [ B ] ( π 1 ( M )) ∧ C [ B ′ ] ( π 2 ( M ))
V [ A ] ( V ) C [ F A ] ( ret V ) C [ F A ] ( M ) ‾ C [ F A ] ( op ( M ‾ ) ) ∀ op : Ops \frac{V[A](V)}{C[FA](\operatorname{ret} V)}
\qquad
\frac{\overline{C[FA](M)}}{C[FA](\operatorname{op}(\overline{M}))}\ \forall\operatorname{op} : \operatorname{Ops} C [ F A ] ( ret V ) V [ A ] ( V ) C [ F A ] ( op ( M )) C [ F A ] ( M ) ∀ op : Ops
Theorem 3.1 (Fundamental theorem). If Γ ⊢ V : A \Gamma\vdash V : A Γ ⊢ V : A then Γ ⊨ V : A \Gamma\models V : A Γ ⊨ V : A , and if Γ ∣ ⋅ ⊢ M : B \Gamma\mid\cdot\vdash M : B Γ ∣ ⋅ ⊢ M : B then Γ ∣ ⋅ ⊨ M : B \Gamma\mid\cdot\models M : B Γ ∣ ⋅ ⊨ M : B .
From the fundamental theorem, we receive a proof of equational canonicity. Of particular interest are closed computations of type F A FA F A which we show are terms of the free algebra for the signature with variables given by closed values of type A A A . To see this, we define the function reify which quotes a free algebra term as a closed computation.
reify : Term Σ ( Val ( A ) ) → Comp ( F A ) \operatorname{reify} : \operatorname{Term}_{\Sigma}(\operatorname{Val}(A)) \to\operatorname{Comp}(FA) reify : Term Σ ( Val ( A )) → Comp ( F A )
reify ( var t ) : = ret t \operatorname{reify}(\operatorname{var}\ t) := \operatorname{ret}\ t reify ( var t ) := ret t
reify ( op ( t → ) ) : = op ( reify ( t ) → ) \operatorname{reify}(\operatorname{op}(\overrightarrow{t})) := \operatorname{op}(\overrightarrow{\operatorname{reify}(t)}) reify ( op ( t )) := op ( reify ( t ) )
Corollary 3.2 (Equational canonicity). For every M : Comp ( F A ) M : \operatorname{Comp}(FA) M : Comp ( F A ) there is t : Term Σ ( Val ( A ) ) t : \operatorname{Term}_{\Sigma}(\operatorname{Val}(A)) t : Term Σ ( Val ( A )) with M = reify ( t ) M = \operatorname{reify}(t) M = reify ( t ) .
Proof. By the Fundamental Theorem (Theorem 3.1 ), we have C [ F A ] ( M ) C[FA](M) C [ F A ] ( M ) . We find t t t by induction on the proof of C [ F A ] ( M ) C[FA](M) C [ F A ] ( M ) . For M = ret V M = \operatorname{ret} V M = ret V , take t = var V t = \operatorname{var}\ V t = var V . For M = op ( M → ) M = \operatorname{op}(\overrightarrow{M}) M = op ( M ) , the inductive hypotheses give t i t_i t i with M i = reify ( t i ) M_i = \operatorname{reify}(t_i) M i = reify ( t i ) , so op ( M → ) = op ( reify ( t ) → ) = reify ( op ( t → ) ) \operatorname{op}(\overrightarrow{M}) = \operatorname{op}(\overrightarrow{\operatorname{reify}(t)}) = \operatorname{reify}(\operatorname{op}(\overrightarrow{t})) op ( M ) = op ( reify ( t ) ) = reify ( op ( t )) . □
Corollary 3.3. If ⟦ _ ⟧ v : Val ( A ) → ⟦ A ⟧ \llbracket\_\rrbracket_v : \operatorname{Val}(A) \to\llbracket A \rrbracket [ [ _ ] ] v : Val ( A ) → [ [ A ] ] is a bijection, then ⟦ _ ⟧ : Comp ( F A ) → Term T ( Val ( A ) ) \llbracket\_\rrbracket: \operatorname{Comp}(FA) \to\operatorname{Term}_{\mathcal{T}}(\operatorname{Val}(A)) [ [ _ ] ] : Comp ( F A ) → Term T ( Val ( A )) is a bijection.
Proof. By construction ⟦ _ ⟧ : Comp ( F A ) → Term T ( Val ( A ) ) \llbracket\_\rrbracket: \operatorname{Comp}(FA) \to\operatorname{Term}_{\mathcal{T}}(\operatorname{Val}(A)) [ [ _ ] ] : Comp ( F A ) → Term T ( Val ( A )) is a homomorphism. By the universal property of the free model, there is a homomorphism ⟦ _ ⟧ − 1 : Term T ( Val ( A ) ) → Comp ( F A ) \llbracket\_\rrbracket^{-1} : \operatorname{Term}_{\mathcal{T}}(\operatorname{Val}(A)) \to\operatorname{Comp}(FA) [ [ _ ] ] − 1 : Term T ( Val ( A )) → Comp ( F A ) satisfying ⟦ v a r x ⟧ − 1 = r e t ⟦ x ⟧ − 1 \llbracket\mathsf{var}\ x \rrbracket^{-1} = \mathsf{ret}\ \llbracket x \rrbracket^{-1} [ [ var x ] ] − 1 = ret [ [ x ] ] − 1 and furthermore the composition ⟦ _ ⟧ ∘ ⟦ _ ⟧ − 1 = i d \llbracket\_\rrbracket\circ\llbracket\_\rrbracket^{-1} = \mathsf{id} [ [ _ ] ] ∘ [ [ _ ] ] − 1 = id so ⟦ _ ⟧ − 1 \llbracket\_\rrbracket^{-1} [ [ _ ] ] − 1 is injective. It suffices, then, to show that ⟦ _ ⟧ − 1 \llbracket\_\rrbracket^{-1} [ [ _ ] ] − 1 is surjective. First, note that ⟦ _ ⟧ − 1 ∘ q = r e i f y ∘ i \llbracket\_\rrbracket^{-1} \circ q = \mathsf{reify}\circ i [ [ _ ] ] − 1 ∘ q = reify ∘ i where q : Term Σ ( Val ( A ) ) ↠ Term T ( Val ( A ) ) q : \operatorname{Term}_{\Sigma}(\operatorname{Val}(A)) \twoheadrightarrow\operatorname{Term}_{\mathcal{T}}(\operatorname{Val}(A)) q : Term Σ ( Val ( A )) ↠ Term T ( Val ( A )) is the quotient map and i : Term Σ ( Val ( A ) ) ≅ Term Σ ( ⟦ A ⟧ ) i : \operatorname{Term}_{\Sigma}(\operatorname{Val}(A)) \cong\operatorname{Term}_{\Sigma}(\llbracket A \rrbracket) i : Term Σ ( Val ( A )) ≅ Term Σ ( [ [ A ] ] ) is the functorial lifting of the bijection ⟦ _ ⟧ v \llbracket\_\rrbracket_v [ [ _ ] ] v . By Corollary 3.2, reify is surjective, and as a bijection and quotient map, i , q i,q i , q are also surjective. Therefore ⟦ _ ⟧ − 1 \llbracket\_\rrbracket^{-1} [ [ _ ] ] − 1 is surjective as well. □ \square □
Tree Reduction
This section gives a tree-based operational semantics for the smaller calculus CBPV ( T ) \operatorname{CBPV}(\mathcal{T}) CBPV ( T ) , which omits complex values, complex stacks and the equational theory. We prove operational canonicity and strong normalization for it (Theorems 4.6 and 4.7).
Operational Semantics of CBPV(T)
Our tree-based operational semantics for CBPV is given by the reduction relation ↦ t r e e \mapsto_{\mathrm{tree}} ↦ tree in Figure 5 . It is built from S S S -steps ↦ S \mapsto_S ↦ S . A frame F F F is a stack of depth exactly one, namely ∙ V \bullet V ∙ V , π i ∙ \pi_i\bullet π i ∙ or x ← ∙ ; N x\leftarrow\bullet;N x ← ∙ ; N . Every stack of CBPV ( T ) \operatorname{CBPV}(\mathcal{T}) CBPV ( T ) (Figure 1 ) is a sequence of frames, so S S S is either ∙ \bullet ∙ or S [ F ] S[F] S [ F ] . There are two kinds of S S S -steps, which each take place under an arbitrary stack S S S : for each type connective, we have a β \beta β reduction, and we have a commuting conversion that pushes a frame under an operation, as in the small-step semantics of algebraic effects and handlers [7 , 26 , 41 ] . By definition, stack plugging is a congruence for ↦ S \mapsto_S ↦ S , and operations take no S S S -steps. Our tree reduction does not handle reduction of operations op ( M → ) \operatorname{op}(\overrightarrow{M}) op ( M ) . Instead, we leave them uninterpreted and allow tree reductions to operate on the operands of any operation. This is the standard operational account of algebraic effects, in which a program computes a tree of uninterpreted operations [25 , 28 , 40 ] . Note that while ↦ S \mapsto_S ↦ S is deterministic, ↦ t r e e \mapsto_{\mathrm{tree}} ↦ tree is not, as there is no specified evaluation order under an operation. E.g., given an operation op ( M , N ) \operatorname{op}(M,N) op ( M , N ) with two reducible arguments M ↦ t r e e M ′ M\mapsto_{\mathrm{tree}}M' M ↦ tree M ′ and N ↦ t r e e N ′ N\mapsto_{\mathrm{tree}}N' N ↦ tree N ′ , we do not specify which argument to reduce first.
F : : = ∙ V ∣ π i ∙ ∣ x ← ∙ ; N S [ x ← ret V ; N ] ↦ S S [ N [ V / x ] ] S [ F [ op ( M → ) ] ] ↦ S S [ op ( F [ M ] → ) ] S [ case + ( σ i V ) { x 1 . M 1 ∣ x 2 . M 2 } ] ↦ S S [ M i [ V / x i ] ] S [ case 1 ( ( ) ) { M } ] ↦ S S [ M ] S [ case × ( V , W ) { x , y . M } ] ↦ S S [ M [ V / x , W / y ] ] S [ ( λ x : A . M ) V ] ↦ S S [ M [ V / x ] ] S [ π i ⟨ M 1 , M 2 ⟩ ] ↦ S S [ M i ] S [ force ( thunk M ) ] ↦ S S [ M ] M ↦ S M ′ M ↦ t r e e M ′ M i ↦ t r e e M i ′ op ( … , M i , … ) ↦ t r e e op ( … , M i ′ , … ) \begin{aligned}
F &::= \bullet V \mid\pi_i\bullet\mid x\leftarrow\bullet;N \\
S[x\leftarrow\operatorname{ret} V;N] &\mapsto_S S[N[V/x]] &
S[F[\operatorname{op}(\overrightarrow{M})]] &\mapsto_S S[\operatorname{op}(\overrightarrow{F[M]})] \\
S[\operatorname{case}_{+}(\sigma_iV)\{x_1.M_1\mid x_2.M_2\}] &\mapsto_S S[M_i[V/x_i]] &
S[\operatorname{case}_1(())\{M\}] &\mapsto_S S[M] \\
S[\operatorname{case}_{\times}(V,W)\{x,y.M\}] &\mapsto_S S[M[V/x,W/y]] &
S[(\lambda x:A.M)V] &\mapsto_S S[M[V/x]] \\
S[\pi_i\langle M_1,M_2\rangle] &\mapsto_S S[M_i] &
S[\operatorname{force}(\operatorname{thunk} M)] &\mapsto_S S[M] \\
\frac{M\mapsto_S M'}{M\mapsto_{\mathrm{tree}}M'} &
\frac{M_i\mapsto_{\mathrm{tree}}M_i'}{\operatorname{op}(\ldots,M_i,\ldots)\mapsto_{\mathrm{tree}}\operatorname{op}(\ldots,M_i',\ldots)}
\end{aligned} F S [ x ← ret V ; N ] S [ case + ( σ i V ) { x 1 . M 1 ∣ x 2 . M 2 }] S [ case × ( V , W ) { x , y . M }] S [ π i ⟨ M 1 , M 2 ⟩] M ↦ tree M ′ M ↦ S M ′ ::= ∙ V ∣ π i ∙ ∣ x ← ∙ ; N ↦ S S [ N [ V / x ]] ↦ S S [ M i [ V / x i ]] ↦ S S [ M [ V / x , W / y ]] ↦ S S [ M i ] op ( … , M i , … ) ↦ tree op ( … , M i ′ , … ) M i ↦ tree M i ′ S [ F [ op ( M )]] S [ case 1 (( )) { M }] S [( λ x : A . M ) V ] S [ force ( thunk M )] ↦ S S [ op ( F [ M ] )] ↦ S S [ M ] ↦ S S [ M [ V / x ]] ↦ S S [ M ] Figure 5. CBPV(T \mathcal{T} T ) Tree Reduction ↦ t r e e \mapsto_{\mathrm{tree}} ↦ tree .
Lemma 4.1 (Progress and determinism). For every M : Comp ( F A ) M : \operatorname{Comp}(FA) M : Comp ( F A ) , M = ret V M=\operatorname{ret}\ V M = ret V or M = op ( M → ) M=\operatorname{op}(\overrightarrow{M}) M = op ( M ) or ∃ ! M ′ . M ↦ S M ′ \exists! \ M'.\ M\mapsto_S M' ∃ ! M ′ . M ↦ S M ′ .
Proof. By induction on M M M , inspecting the rules of Figure 5 .
Note that soundness of the operational semantics with respect to the denotational semantics follows by the same reasoning as § 3 . CBPV ( T ) \operatorname{CBPV}(\mathcal{T}) CBPV ( T ) is a fragment of CBPV + ( T ) \operatorname{CBPV}^{+}(\mathcal{T}) CBPV + ( T ) , so its terms are interpreted by Figure 3 , and each reduction is a provable equality in the equational theory of Figure 2 , which this interpretation validates.
Theorem 4.2 (Soundness of ↦ t r e e \mapsto_{\mathrm{tree}} ↦ tree ). For M , M ′ : Comp ( B ) M, M' : \operatorname{Comp}(B) M , M ′ : Comp ( B ) , if M ↦ t r e e M ′ M \mapsto_{\mathrm{tree}} M' M ↦ tree M ′ then ⟦ M ⟧ = ⟦ M ′ ⟧ \llbracket M \rrbracket= \llbracket M' \rrbracket [ [ M ] ] = [ [ M ′ ] ] .
Logical Relation
We now adapt our logical relation from the equational to the operational setting. As in the equational setting, for every value type we define a predicate on closed values, and for every computation type we define a predicate on closed computations. The only difference is that computation predicates must now be closed not only under the operations of Σ \Sigma Σ , but also under anti-reduction along S S S -steps. Explicitly, any Q : CPred ( B ) Q : \operatorname{CPred}(B) Q : CPred ( B ) satisfies the following closure conditions:
Q ( M ) ‾ Q ( op ( M → ) ) ∀ op : Ops \frac{\overline{Q(M)}}{Q(\operatorname{op}(\overrightarrow{M}))}\ \forall\operatorname{op}:\operatorname{Ops} Q ( op ( M )) Q ( M ) ∀ op : Ops
Q ( M ′ ) M ↦ S M ′ Q ( M ) . \frac{Q(M') \qquad M \mapsto_S M'}{Q(M)}. Q ( M ) Q ( M ′ ) M ↦ S M ′ .
We present the logical relation in Figure 6 . Its value predicates, and its computation predicates at ⊤ \top ⊤ , A → B A \to B A → B and B & B ′ B \mathbin{\&} B' B & B ′ , are given by the clauses of Figure 4 , now on the closed terms of CBPV ( T ) \operatorname{CBPV}(\mathcal{T}) CBPV ( T ) . Compared with the equational setting, the only additional clause is that the free computation predicate C [ F A ] C[FA] C [ F A ] is closed under anti-reduction along S S S -steps.
Figure 6. CBPV(T \mathcal{T} T ) Canonicity Logical Relation, the free computation predicate. The other clauses are those of Figure 4 .
Lemma 4.3 (Anti-reduction for computation logical predicates). For every computation type B B B , if M ↦ S M ′ M \mapsto_S M' M ↦ S M ′ then C [ B ] ( M ′ ) ⟹ C [ B ] ( M ) C[B](M') \Longrightarrow C[B](M) C [ B ] ( M ′ ) ⟹ C [ B ] ( M ) .
Proof. By induction on B B B . The case ⊤ \top ⊤ is trivial. For A → B A \to B A → B , given V V V with V [ A ] ( V ) \mathcal{V}[A](V) V [ A ] ( V ) , we have M V ↦ S M ′ V M\,V \mapsto_S M'\,V M V ↦ S M ′ V since ↦ S \mapsto_S ↦ S is closed under stacks, so C [ B ] ( M ′ V ) C[B](M'\,V) C [ B ] ( M ′ V ) gives C [ B ] ( M V ) C[B](M\,V) C [ B ] ( M V ) by the inductive hypothesis. The case B & B ′ B \mathbin{\&} B' B & B ′ is the same with the stack π i ∙ \pi_i \mathbin{\bullet} π i ∙ . For F A FA F A it is the anti-reduction clause of Figure 6 .
Lemma 4.4 (Congruence for computation logical predicates). For every computation type, B B B , C [ B ] C[B] C [ B ] is closed under the operations of the theory.
Proof. By induction on B B B . Trivial for ⊤ \top ⊤ and F A FA F A cases. For A → B A \to B A → B consider op ( M → ) \operatorname{op}(\overrightarrow{M}) op ( M ) where we have C [ A → B ] ( M i ) C[A \to B](M_i) C [ A → B ] ( M i ) for all i i i . Given V [ A ] ( V ) \mathcal{V}[A](V) V [ A ] ( V ) we need to show C [ B ] ( op ( M → ) V ) C[B](\operatorname{op}(\overrightarrow{M})\,V) C [ B ] ( op ( M ) V ) . We have C [ B ] ( M i V ) C[B](M_i\,V) C [ B ] ( M i V ) for each i i i , so C [ B ] ( op ( M V → ) ) C[B](\operatorname{op}(\overrightarrow{M\,V})) C [ B ] ( op ( M V )) by the inductive hypothesis. We have op ( M → ) V ↦ S op ( M V → ) \operatorname{op}(\overrightarrow{M})\,V \mapsto_S \operatorname{op}(\overrightarrow{M\,V}) op ( M ) V ↦ S op ( M V ) by the commuting conversion rule, so the result follows by anti-reduction for B B B . The B 1 & B 2 B_1 \mathbin{\&} B_2 B 1 & B 2 case is analogous.
Fundamental Theorem
Theorem 4.5 (Fundamental theorem). If Γ ⊢ V : A \Gamma\vdash V : A Γ ⊢ V : A then Γ ⊨ V : A \Gamma\models V : A Γ ⊨ V : A , and if Γ ∣ ⋅ ⊢ M : B \Gamma\mid\cdot\vdash M : B Γ ∣ ⋅ ⊢ M : B then Γ ∣ ⋅ ⊨ M : B \Gamma\mid\cdot\models M : B Γ ∣ ⋅ ⊨ M : B .
Proof. The compatibility lemmas follow the same structure as those for Theorem 3.1 except that usage of β \beta β equations and of the law S [ op ( M → ) ] = op ( S [ M → ] ) S[\operatorname{op}(\overrightarrow{M})] = \operatorname{op}(S[\overrightarrow{M}]) S [ op ( M )] = op ( S [ M ]) is replaced with the fact that computation predicates are closed under anti-reduction along S S S -steps. Every case is in Appendix § 10 . To demonstrate we consider the case for bind. We show that C [ F A ] ( M ) C[FA](M) C [ F A ] ( M ) and ∀ V . V [ A ] ( V ) ⟹ \forall V.\mathcal{V}[A](V) \Longrightarrow ∀ V . V [ A ] ( V ) ⟹
C [ B ] ( N [ V / x ] ) C[B](N[V/x]) C [ B ] ( N [ V / x ]) imply C [ B ] ( x ← M ; N ) C[B](x \leftarrow M;N) C [ B ] ( x ← M ; N ) , by induction on the proof of C [ F A ] ( M ) C[FA](M) C [ F A ] ( M ) . There are three cases:
(M = ret V M = \operatorname{ret} V M = ret V with V [ A ] ( V ) V[A](V) V [ A ] ( V ) ) Then x ← ret V ; N ↦ S N [ V / x ] x \leftarrow\operatorname{ret} V;N \mapsto_S N[V/x] x ← ret V ; N ↦ S N [ V / x ] and follows by assumption and anti-reduction.
(M = op ( M ⃗ ) M = \operatorname{op}(\vec{M}) M = op ( M ) with C [ F A ] ( M ⃗ ) C[FA](\vec{M}) C [ F A ] ( M ) ) Then x ← op ( M ⃗ ) ; N ↦ S op ( x ← M ; N → ) x \leftarrow\operatorname{op}(\vec{M});N \mapsto_S \operatorname{op}(\overrightarrow{x \leftarrow M;N}) x ← op ( M ) ; N ↦ S op ( x ← M ; N ) , and the result follows by the inductive hypothesis, the congruence lemma and anti-reduction.
(M ↦ S M ′ M \mapsto_S M' M ↦ S M ′ with C [ F A ] ( M ′ ) C[FA](M') C [ F A ] ( M ′ ) ) Then ( x ← M ; N ) ↦ S ( x ← M ′ ; N ) (x \leftarrow M;N) \mapsto_S (x \leftarrow M';N) ( x ← M ; N ) ↦ S ( x ← M ′ ; N ) , since ↦ S \mapsto_S ↦ S is closed under stacks, and the result follows by inductive hypothesis and anti-reduction.
While our logical relation concerns only ↦ S \mapsto_S ↦ S , we can establish operational canonicity of ↦ t r e e \mapsto_{\mathrm{tree}} ↦ tree as a corollary.
Corollary 4.6 (Operational canonicity). For every M : Comp ( F A ) M : \operatorname{Comp}(FA) M : Comp ( F A ) there is t : Term Σ ( Val ( A ) ) t : \operatorname{Term}_{\Sigma}(\operatorname{Val}(A)) t : Term Σ ( Val ( A )) with M ↦ t r e e ∗ reify ( t ) M \mapsto_{\mathrm{tree}}^{*} \operatorname{reify}(t) M ↦ tree ∗ reify ( t ) .
Proof. We proceed by induction on the proof of C [ F A ] ( M ) C[FA](M) C [ F A ] ( M ) which we have by Theorem 4.5 .
ret V \operatorname{ret} V ret V . Then M = reify ( var V ) M = \operatorname{reify}(\operatorname{var} V) M = reify ( var V ) .
op ( M ⃗ ) \operatorname{op}(\vec{M}) op ( M ) . Then by inductive hypothesis, we have M ⃗ ↦ t r e e ∗ reify ( t ⃗ ) \vec{M} \mapsto_{\mathrm{tree}}^{*} \operatorname{reify}(\vec{t}) M ↦ tree ∗ reify ( t ) . Since op \operatorname{op} op has finite arity, we can use finitely many congruences to get op ( M ⃗ ) ↦ t r e e ∗ op ( reify ( t ) → ) = reify ( op ( t ⃗ ) ) \operatorname{op}(\vec{M}) \mapsto_{\mathrm{tree}}^{*} \operatorname{op}(\overrightarrow{\operatorname{reify}(t)}) = \operatorname{reify}(\operatorname{op}(\vec{t})) op ( M ) ↦ tree ∗ op ( reify ( t ) ) = reify ( op ( t )) .
M ↦ S M ′ M \mapsto_S M' M ↦ S M ′ . By inductive hypothesis M ′ ↦ t r e e ∗ reify ( t ) M' \mapsto_{\mathrm{tree}}^{*} \operatorname{reify}(t) M ′ ↦ tree ∗ reify ( t ) , and the result follows by transitivity, since an S S S -step is a tree step.
Since the only nondeterminism in our operational semantics arises from the arbitrary order in which arguments of an operation are independently evaluated, this can be strengthened to a strong normalization result, in which every reduction sequence terminates.
Corollary 4.7 (Strong normalization for ↦ t r e e \mapsto_{\mathrm{tree}} ↦ tree ). For every M : Comp ( F A ) M : \operatorname{Comp}(FA) M : Comp ( F A ) , every reduction sequence from M M M is finite.
Proof. By induction on the proof that C [ F A ] ( M ) C[FA](M) C [ F A ] ( M ) :
ret V \operatorname{ret} V ret V trivial
M = op ( M ⃗ ) M = \operatorname{op}(\vec{M}) M = op ( M ) . An operation takes no S S S -step, so every step from M M M is by congruence in one of its arguments, and M M M stays an operation. Therefore, because op \operatorname{op} op has finite arity, an infinite reduction sequence would give an infinite sequence for at least one M i M_i M i . Since by inductive hypothesis each M i M_i M i is strongly normalizing, this is a contradiction.
M ↦ S M ′ M \mapsto_S M' M ↦ S M ′ . By Theorem 4.1 this is the only step from M M M , and the result follows by inductive hypothesis.
Without equations this strengthens to reducing to the denotation itself, by operational canonicity and soundness (Theorem 4.2 ).
Corollary 4.8. For any theory T \mathcal{T} T with no equations, any type A A A such that ⟦ _ ⟧ v : Val ( A ) ≅ ⟦ A ⟧ \llbracket\_ \rrbracket_v : \operatorname{Val}(A) \cong\llbracket A \rrbracket [ [ _ ] ] v : Val ( A ) ≅ [ [ A ] ] (e.g., any finite type 1 + 1 + ⋯ + 0 1 + 1 + \cdots+ 0 1 + 1 + ⋯ + 0 ), and any M : Comp ( F A ) M : \operatorname{Comp}(FA) M : Comp ( F A ) , M ↦ t r e e ∗ reify ( ⟦ M ⟧ ) M \mapsto_{\mathrm{tree}}^{*} \operatorname{reify}(\llbracket M \rrbracket) M ↦ tree ∗ reify ( [ [ M ] ] ) .
For theories with equations, the corresponding result is the adequacy of configuration reduction (Theorem 5.18 ). Configuration reduction computes in the free model itself.
Configuration Reduction
The tree-based operational semantics leaves algebraic operations uninterpreted. In this section, we provide a second, more abstract machine-like operational semantics to our calculus, under the conditions that the free model of the theory is given by a monadic container.
Reducing Operations
We begin with the guiding example of writer. With the writer effect, programs are monoidally updating an accumulator variable. A natural operational semantics then has as states a pair ⟨ m , N ⟩ \langle m,N\rangle ⟨ m , N ⟩ where m : M m : M m : M is an element of the monoid we are using for the accumulator and N : Comp ( F A ) N : \operatorname{Comp}(FA) N : Comp ( F A ) is a syntactic term that is being evaluated. To execute a term N N N , we first place it in the initial configuration, given by ⟨ e , N ⟩ \langle e,N\rangle ⟨ e , N ⟩ . Then in addition to tree reductions that take internal steps ⟨ m , N ⟩ ↦ ⟨ m , N ′ ⟩ \langle m,N\rangle\mapsto\langle m,N'\rangle ⟨ m , N ⟩ ↦ ⟨ m , N ′ ⟩ , we also should have a step that interprets the syntactic operations in N N N to update the accumulator:
⟨ m , tell n ( N ) ⟩ ↦ ⟨ m ⊗ n , N ⟩ \langle m,\operatorname{tell}_{n}(N)\rangle\mapsto\langle m \otimes n,N\rangle ⟨ m , tell n ( N )⟩ ↦ ⟨ m ⊗ n , N ⟩
Monad aficionados will notice that the states of this machine are precisely the carrier of the free model of the writer theory introduced in § 2.2 T ( Comp ( F A ) ) = M × Comp ( F A ) T(\operatorname{Comp}(FA)) = M \times\operatorname{Comp}(FA) T ( Comp ( F A )) = M × Comp ( F A ) . The initial configuration is exactly the unit of the monad, and the reduction rule is an instance of the multiplication of the monad.
This intuition carries over to our general approach. In operational semantics, a runtime configuration typically consists of some data describing the current state of the machine, alongside some number of syntactic subterms. Here, our configurations are represented by elements of the free model of the theory. To single out one subterm, we take the free model to be a monadic container [42 , 48 ] , whose elements are a shape , the state of the machine, together with a subterm at each of the shape’s positions . A step then either reduces a subterm or interprets an effect, updating the state. The effect rules are computed from the container, as for writer above (Theorem 5.6), and each step preserves the denotation (Theorem 5.12 ).
This establishes a sound operational semantics, but does not immediately establish strong normalization. We identify a simple sufficient condition for the operational semantics to be strongly normalizing, which we call affinity . Affinity says that an operational step never duplicates the subterms around the one it reduces. Assuming affinity, every reduction sequence terminates, by a simple measure built from tree reduction (Theorem 5.17 ). Affinity holds in all of our example theories whose free models are monadic containers.
Not every free model monad is a monadic container. The free model for the theory of join-semilattices is the finite powerset monad, which is not polynomial. We discuss these cases further in § 5.4 .
Monadic Containers
Containers (also known as polynomial functors ) [1 , 16 ] provide a simple combinatorial language for describing syntax and data structures.
Definition 5.1 (Container). A container Sh ◃ P \operatorname{Sh} \triangleleft P Sh ◃ P consists of a set Sh \operatorname{Sh} Sh of shapes together with, for each shape s s s , a set P ( s ) P(s) P ( s ) of its positions. It is finitely branching if every P ( s ) P(s) P ( s ) is finite.
Signatures (§ 2 ) are equivalent to finitely branching containers, though we intentionally avoid conflating them. The operations can be considered to be the shapes, and the arity of an operation describes a finite set of positions. This is a common use for containers, to describing raw syntax. However, we will use containers to describe the free model of an effect theory rather than its signature, and the two typically differ. For errors, the signature has one shape, err, with no positions, while the free model X + 1 X + 1 X + 1 has two shapes, one with no positions and one with a single position.
A container determines an endofunctor on Set via the interpretation
⟦ S h ◃ P ⟧ ( X ) : = ∑ s : S h X P ( s ) \llbracket\mathrm{Sh} \triangleleft P \rrbracket(X) := \sum_{s:\mathrm{Sh}} X^{P(s)} [ [ Sh ◃ P ] ] ( X ) := s : Sh ∑ X P ( s )
We write T T T for ⟦ S h ◃ P ⟧ \llbracket\mathrm{Sh} \triangleleft P \rrbracket [ [ Sh ◃ P ] ] , which will be the free model monad of § 2.2 , and call its elements configurations . Each has the form ⟨ s , x ⃗ ⟩ \langle s, \vec{x}\rangle ⟨ s , x ⟩ , a shape s s s together with a function x ⃗ : P ( s ) → X \vec{x}:P(s) \to X x : P ( s ) → X , which we can think of as a vector of subterms. We call x p x_p x p the subterm at position p p p . The functorial action of T T T on a function f : X → Y f:X \to Y f : X → Y applies f f f to every subterm,
T ( f ) ⟨ s , x ⃗ ⟩ = ⟨ s , f ∘ x ⃗ ⟩ . T(f)\langle s,\vec{x}\rangle= \langle s,f \circ\vec{x}\rangle. T ( f ) ⟨ s , x ⟩ = ⟨ s , f ∘ x ⟩ .
The shape and the number of subterms are unchanged.
For configurations of computations, X = Comp ( F A ) X = \operatorname{Comp}(FA) X = Comp ( F A ) , we write ⟨ s , N ⃗ ⟩ \langle s,\vec{N}\rangle ⟨ s , N ⟩ . In typical operational semantics, a configuration should have only finitely many subterms to evaluate, so we only use finitely branching containers. These may still have infinitely many shapes, like writer for infinite M M M .
The free models form a monad, so what we require is a monad whose underlying functor is a container. Such monads have a combinatorial description called a monadic container [48 ] . Every monad structure on ⟦ S h ◃ P ⟧ \llbracket\mathrm{Sh} \triangleleft P \rrbracket [ [ Sh ◃ P ] ] arises from exactly one monadic container.
Definition 5.2 (Monadic container [42 , 48 ] ). A monadic container on S h ◃ P \mathrm{Sh} \triangleleft P Sh ◃ P consists of
a unit shape ι : S h \iota:\mathrm{Sh} ι : Sh ,
a flattening operation , giving for each shape s s s and family of shapes v : P ( s ) → S h v:P(s) \to\mathrm{Sh} v : P ( s ) → Sh the shape σ ( s , v ) \sigma(s,v) σ ( s , v ) obtained by placing v ( p ) v(p) v ( p ) at each position p p p of $s, and
for each such s s s and v v v , a position map pr s , v : P ( σ ( s , v ) ) → ∑ p : P ( s ) P ( v ( p ) ) \operatorname{pr}_{s,v}:P(\sigma(s,v)) \to\sum_{p:P(s)} P(v(p)) pr s , v : P ( σ ( s , v )) → ∑ p : P ( s ) P ( v ( p )) , written pr = ( pr 1 , pr 2 ) \operatorname{pr}=(\operatorname{pr}_1,\operatorname{pr}_2) pr = ( pr 1 , pr 2 ) , giving for each position q q q of σ ( s , v ) \sigma(s,v) σ ( s , v ) the outer position pr 1 q \operatorname{pr}_1q pr 1 q and the inner position pr 2 q \operatorname{pr}_2q pr 2 q it came from,
satisfying the unit and associativity laws [42 Def. 8] . Its monad [42 Def. 9] is T = ⟦ S h ◃ P ⟧ T=\llbracket\mathrm{Sh} \triangleleft P \rrbracket T = [ [ Sh ◃ P ] ] with
η ( x ) = ⟨ ι , λ _ . x ⟩ , μ ⟨ s , x ⃗ ⟩ = ⟨ σ ( s , π 1 ∘ x ⃗ ) , λ q . π 2 ( x pr 1 q ) ( pr 2 q ) ⟩ . \eta(x)=\langle\iota,\lambda_{\_}.x\rangle,\qquad
\mu\langle s,\vec{x}\rangle=\left\langle\sigma(s,\pi_1\circ\vec{x}),\lambda q.\,\pi_2(x_{\operatorname{pr}_1q})(\operatorname{pr}_2q)\right\rangle. η ( x ) = ⟨ ι , λ _ . x ⟩ , μ ⟨ s , x ⟩ = ⟨ σ ( s , π 1 ∘ x ) , λ q . π 2 ( x pr 1 q ) ( pr 2 q ) ⟩ .
Definition 5.3 (Operational model). An operational model for an algebraic theory T \mathcal{T} T is a finitely branching monadic container ( S h ◃ P , ι , σ , pr ) (\mathrm{Sh}\triangleleft P,\iota,\sigma,\operatorname{pr}) ( Sh ◃ P , ι , σ , pr ) whose monad T T T is the free model monad of T \mathcal{T} T .
Example 5.4. For writer over a monoid ( M , ⊗ , e ) (M,\otimes,e) ( M , ⊗ , e ) , the free model T ( X ) = M × X T(X)=M\times X T ( X ) = M × X of § 2.2 is the monadic container with shapes S h = M \mathrm{Sh}=M Sh = M , one position P ( m ) = { ∗ } P(m)=\{\ast\} P ( m ) = { ∗ } per shape, ι = e \iota=e ι = e , σ ( m , v ) = m ⊗ v ( ∗ ) \sigma(m,v)=m\otimes v(\ast) σ ( m , v ) = m ⊗ v ( ∗ ) and pr ( ∗ ) = ( ∗ , ∗ ) \operatorname{pr}(\ast)=(\ast,\ast) pr ( ∗ ) = ( ∗ , ∗ ) [42 Ex. 14] . A configuration ⟨ m , N ⟩ \langle m,N\rangle ⟨ m , N ⟩ is an accumulator m m m and the one term N N N being run. Its unit is η ( N ) = ⟨ e , N ⟩ \eta(N)=\langle e,N\rangle η ( N ) = ⟨ e , N ⟩ and μ ⟨ m , ⟨ n , N ⟩ ⟩ = ⟨ m ⊗ n , N ⟩ \mu\langle m,\langle n,N\rangle\rangle=\langle m\otimes n,N\rangle μ ⟨ m , ⟨ n , N ⟩⟩ = ⟨ m ⊗ n , N ⟩ .
An operational model need not be a polynomial monad in the sense of Gambino and Kock [16 ] . Polynomial monads are exactly the Cartesian monadic containers, those with P ( ι ) ≅ 1 P(\iota)\cong1 P ( ι ) ≅ 1 and with every pr : P ( σ ( s , v ) ) → ∑ p : P ( s ) P ( v ( p ) ) \operatorname{pr}:P(\sigma(s,v))\to\sum_{p:P(s)}P(v(p)) pr : P ( σ ( s , v )) → ∑ p : P ( s ) P ( v ( p )) a bijection [5 , 48 ] . Writer, errors, weighted monoids and pre-convex spaces are polynomial monads and state is the only one of our examples that is not. The unit of the state monad has one position for each possible initial state (P ( ι ) = S P(\iota)=S P ( ι ) = S ) and its multiplication drops unreached computations.
Reduction
We define a reduction relation on configurations t ~ : T ( Comp ( F A ) ) \tilde{t}:T(\operatorname{Comp}(FA)) t ~ : T ( Comp ( F A )) whose subterms are closed CBPV computations of a returner type F A FA F A . Intuitively, the shape of such a configuration specifies a state of the machine with the subterms being the terms that are currently executing in some nondeterministic order. Matching most common operational semantics, we define a stepping relation that reduces the machine one subterm at a time.
To single out one subterm we use one-hole contexts , given by the derivative of the container [2 , 32 ] :
∂ T ( X ) = ∑ s : S h ∑ p ∙ : P ( s ) X P ( s ) ∖ { p ∙ } . \partial_T(X) = \sum_{s:\mathrm{Sh}} \sum_{p_\bullet:P(s)} X^{P(s)\setminus\{p_\bullet\}}. ∂ T ( X ) = s : Sh ∑ p ∙ : P ( s ) ∑ X P ( s ) ∖ { p ∙ } .
A context C = ⟨ s , p ∙ , x → ⟩ C = \langle s, p_\bullet, \overrightarrow{x} \rangle C = ⟨ s , p ∙ , x ⟩ is a shape s s s with a hole at position p ∙ p_\bullet p ∙ and a subterm x p x_p x p at every other position p p p . Plugging x : X x : X x : X into the hole gives the configuration C [ x ] : T ( X ) C[x] : T(X) C [ x ] : T ( X ) with x x x at position p ∙ p_\bullet p ∙ . Like T T T , ∂ T \partial_T ∂ T is a functor, applying f f f to the subterms around the hole, and plugging is natural:
T ( f ) ( C [ x ] ) = ∂ T ( f ) ( C ) [ f ( x ) ] . T(f)(C[x]) = \partial_T(f)(C)[f(x)]. T ( f ) ( C [ x ]) = ∂ T ( f ) ( C ) [ f ( x )] .
We define the configuration reduction relation ⟼ T \longmapsto_T ⟼ T in Figure 7 . In both rules, C : ∂ T ( Comp ( F A ) ) C : \partial_T(\operatorname{Comp}(FA)) C : ∂ T ( Comp ( F A )) is a one-hole context. The Pure rule simply lifts the underlying CBPV tree reduction ⟼ t r e e \longmapsto_{\mathrm{tree}} ⟼ tree through an arbitrary one-hole context of the current configuration, allowing computations to continue reducing independently of the surrounding effect structure. The Effect rule interprets a single algebraic operation. Its left-hand side C [ S [ op ( M → ) ] ] C[S[\operatorname{op}(\overrightarrow{M})]] C [ S [ op ( M )]] is a context C C C around one subterm, which is an operation op ( M → ) \operatorname{op}(\overrightarrow{M}) op ( M ) under a stack S S S . The idea is to interpret the syntactic operation by its semantic counterpart ⟦ op ⟧ : T ( X ) ar ( op ) → T ( X ) \llbracket\operatorname{op}\rrbracket: T(X)^{\operatorname{ar}(\operatorname{op})} \to T(X) [ [ op ] ] : T ( X ) ar ( op ) → T ( X ) . Since the operation sits under a stack, we first push the stack into each argument, giving ⟦ op ⟧ ( η ( S [ M ] ) → ) : T ( Comp ( F A ) ) \llbracket\operatorname{op}\rrbracket(\overrightarrow{\eta(S[M])}) : T(\operatorname{Comp}(FA)) [ [ op ] ] ( η ( S [ M ]) ) : T ( Comp ( F A )) . The remaining subterms, those of C C C , are injected into T T T by η \eta η , giving ∂ T ( η ) ( C ) \partial_T(\eta)(C) ∂ T ( η ) ( C ) . Plugging the interpreted operation into this context yields an element of T ( T ( Comp ( F A ) ) ) T(T(\operatorname{Comp}(FA))) T ( T ( Comp ( F A ))) , which μ \mu μ flattens into a configuration.
Figure 7. Configuration Reduction ⟼ T \longmapsto_T ⟼ T
Since μ \mu μ is computed by σ \sigma σ and pr \operatorname{pr} pr , the reduct of the Effect rule can be computed from the monadic container operations and the configuration each operation creates. This is how we obtain the rules of § 5.4 . In terms of monadic containers, the reduct is most easily expressed with a derived notion of “one-place” flattening.
Definition 5.5 (One-place flattening). Let ( S h ◃ P , ι , σ , pr ) (\mathrm{Sh} \triangleleft P, \iota, \sigma, \operatorname{pr}) ( Sh ◃ P , ι , σ , pr ) be a monadic container, and s : S h s : \mathrm{Sh} s : Sh a shape, p ∙ : P ( s ) p_\bullet: P(s) p ∙ : P ( s ) and s ∙ : S h s_\bullet: \mathrm{Sh} s ∙ : Sh . The one-place flattening of s ∙ s_\bullet s ∙ into s s s at p ∙ p_\bullet p ∙ is
σ ∙ ( s , p ∙ , s ∙ ) : = σ ( s , ν ) where ν ( p ) = { s ∙ p = p ∙ ι p ≠ p ∙ \sigma_\bullet(s,p_\bullet,s_\bullet) := \sigma(s,\nu)
\qquad\text{where}\qquad
\nu(p) =
\begin{cases}
s_\bullet& p=p_\bullet\\
\iota& p\ne p_\bullet
\end{cases} σ ∙ ( s , p ∙ , s ∙ ) := σ ( s , ν ) where ν ( p ) = { s ∙ ι p = p ∙ p = p ∙
and its one-place position map pr ∙ : P ( σ ∙ ( s , p ∙ , s ∙ ) ) → P ( s ∙ ) + ( P ( s ) ∖ { p ∙ } ) \operatorname{pr}_\bullet: P(\sigma_\bullet(s,p_\bullet,s_\bullet)) \to P(s_\bullet) + (P(s)\setminus\{p_\bullet\}) pr ∙ : P ( σ ∙ ( s , p ∙ , s ∙ )) → P ( s ∙ ) + ( P ( s ) ∖ { p ∙ }) says where each position of the new shape comes from, a position of s ∙ s_\bullet s ∙ (inl) or a position of s s s other than the hole (inr).
pr ∙ ( q ) : = { inl ( pr 2 q ) pr 1 q = p ∙ inr ( pr 1 q ) pr 1 q ≠ p ∙ \operatorname{pr}_\bullet(q) :=
\begin{cases}
\operatorname{inl}(\operatorname{pr}_2q) & \operatorname{pr}_1q=p_\bullet\\
\operatorname{inr}(\operatorname{pr}_1q) & \operatorname{pr}_1q\ne p_\bullet
\end{cases} pr ∙ ( q ) := { inl ( pr 2 q ) inr ( pr 1 q ) pr 1 q = p ∙ pr 1 q = p ∙
Applying ⟦ op ⟧ \llbracket\operatorname{op}\rrbracket [ [ op ] ] to the argument numbers 1 , … , n 1,\ldots,n 1 , … , n gives a configuration
⟦ op ⟧ = ⟦ op ⟧ ( η ( 1 ) , … , η ( n ) ) = ⟨ s op , ? → ⟩ : T ( { 1 , … , n } ) , (1) \llbracket\operatorname{op}\rrbracket= \llbracket\operatorname{op}\rrbracket(\eta(1),\ldots,\eta(n)) = \langle s_{\operatorname{op}}, \overrightarrow{?} \rangle: T(\{1,\ldots,n\}), \tag*{(1)} [ [ op ] ] = [ [ op ] ] ( η ( 1 ) , … , η ( n )) = ⟨ s op , ? ⟩ : T ({ 1 , … , n }) , (1)
with shape s o p s_{\mathrm{op}} s op and argument number ℓ r \ell_r ℓ r at position r r r . An Effect step on C [ S [ op ( M ⃗ ) ] ] C[S[\operatorname{op}(\vec{M})]] C [ S [ op ( M )]] puts ⌈ op ⌉ \lceil\operatorname{op}\rceil ⌈ op ⌉ in the hole of C = ⟨ s , p ∙ , N ⃗ ⟩ C=\langle s,\mathbf{p}_{\bullet},\vec{N}\rangle C = ⟨ s , p ∙ , N ⟩ . The new shape is σ ∙ ( s , p ∙ , s o p ) \sigma_{\bullet}(s,\mathbf{p}_{\bullet},s_{\mathrm{op}}) σ ∙ ( s , p ∙ , s op ) and its subterms are θ ∘ pr ∙ \theta\circ\operatorname{pr}_{\bullet} θ ∘ pr ∙ , where θ : P ( s o p ) + ( P ( s ) ∖ { p ∙ } ) → Comp ( F A ) \theta:P(s_{\mathrm{op}})+(P(s)\setminus\{\mathbf{p}_{\bullet}\})\to\operatorname{Comp}(FA) θ : P ( s op ) + ( P ( s ) ∖ { p ∙ }) → Comp ( F A ) sends inl r \operatorname{inl}r inl r to S [ M ℓ r ] S[M_{\ell_r}] S [ M ℓ r ] and inr p \operatorname{inr}p inr p to N p N_p N p .
The Pure rule is unchanged, and Figure 8 states the Effect rule in container form.
Figure 8. The Effect Rule, Stated with Monadic Container Operations
Proposition 5.6. The Effect rules of Figure 7 and Figure 8 are equivalent. For C = ⟨ s , p ∙ , N ⃗ ⟩ C=\langle s,\mathbf{p}_{\bullet},\vec{N}\rangle C = ⟨ s , p ∙ , N ⟩ : ∂ T ( Comp ( F A ) ) \partial_T(\operatorname{Comp}(FA)) ∂ T ( Comp ( F A )) and θ \theta θ as in Figure 8 ,
μ ( ∂ T ( η ) ( C ) [ [ op ] ] ( η ( S [ M ] ) → ) ) = ⟨ σ ∙ ( s , p ∙ , s o p ) , θ ∘ pr ∙ ⟩ . \mu\bigl(\partial_T(\eta)(C)[\![\operatorname{op}]\!](\overrightarrow{\eta(S[M])})\bigr)=\langle\sigma_{\bullet}(s,\mathbf{p}_{\bullet},s_{\mathrm{op}}),\theta\circ\operatorname{pr}_{\bullet}\rangle. μ ( ∂ T ( η ) ( C ) [ [ op ] ] ( η ( S [ M ]) ) ) = ⟨ σ ∙ ( s , p ∙ , s op ) , θ ∘ pr ∙ ⟩ .
Proof. Since T T T is the free model monad, T ( f ) T(f) T ( f ) is a homomorphism for every f f f . Taking f ( i ) = S [ M i ] f(i)=S[M_i] f ( i ) = S [ M i ] gives ⟦ op ⟧ ( η ( S [ M ] ) → ) = T ( f ) ( ⌈ op ⌉ ) = ⟨ s o p , ( S [ M ℓ r ] ) r ⟩ \llbracket\operatorname{op}\rrbracket(\overrightarrow{\eta(S[M])})=T(f)(\lceil\operatorname{op}\rceil)=\langle s_{\mathrm{op}},(S[M_{\ell_r}])_r\rangle [ [ op ] ] ( η ( S [ M ]) ) = T ( f ) (⌈ op ⌉) = ⟨ s op , ( S [ M ℓ r ] ) r ⟩ . Plugging this into ∂ T ( η ) ( C ) \partial_T(\eta)(C) ∂ T ( η ) ( C ) puts s o p s_{\mathrm{op}} s op at the hole and η ( N p ) = ⟨ ι , ( N p ) ⟩ \eta(N_p)=\langle\iota,(N_p)\rangle η ( N p ) = ⟨ ι , ( N p )⟩ at every other position p p p . Computing μ \mu μ with σ \sigma σ and pr \operatorname{pr} pr then gives shape σ ∙ ( s , p ∙ , s o p ) \sigma_{\bullet}(s,\mathbf{p}_{\bullet},s_{\mathrm{op}}) σ ∙ ( s , p ∙ , s op ) , and position q q q holds the subterm at position pr 2 q \operatorname{pr}_2q pr 2 q of the configuration placed at pr 1 q \operatorname{pr}_1q pr 1 q . By the case split defining pr ∙ \operatorname{pr}_{\bullet} pr ∙ , this is θ ( pr ∙ q ) \theta(\operatorname{pr}_{\bullet}q) θ ( pr ∙ q ) . □
For writer (Theorem 5.4) σ ∙ ( m , ∗ , n ) = m ⊗ n \sigma_{\bullet}(m,*,n)=m\otimes n σ ∙ ( m , ∗ , n ) = m ⊗ n and ⌈ tell n ⌉ = ⟨ n , 1 ⟩ \lceil\operatorname{tell}_n\rceil=\langle n,1\rangle ⌈ tell n ⌉ = ⟨ n , 1 ⟩ . So the Effect step from ⟨ m , S [ tell n ( M ) ] ⟩ \langle m,S[\operatorname{tell}_n(M)]\rangle ⟨ m , S [ tell n ( M )]⟩ gives ⟨ σ ∙ ( m , ∗ , n ) , θ ∘ pr ∙ ⟩ = ⟨ m ⊗ n , θ ( inl ∗ ) ⟩ = ⟨ m ⊗ n , S [ M ] ⟩ \langle\sigma_{\bullet}(m,*,n),\theta\circ\operatorname{pr}_{\bullet}\rangle=\langle m\otimes n,\theta(\operatorname{inl}*)\rangle=\langle m\otimes n,S[M]\rangle ⟨ σ ∙ ( m , ∗ , n ) , θ ∘ pr ∙ ⟩ = ⟨ m ⊗ n , θ ( inl ∗ )⟩ = ⟨ m ⊗ n , S [ M ]⟩ , exactly the rule we started with.
Neither σ ∙ \sigma_{\bullet} σ ∙ nor pr ∙ \operatorname{pr}_{\bullet} pr ∙ mentions terms. They use only the monadic container, so the new shape and its position map do not depend on the syntax of the language. Only the Pure and Effect rules refer to CBPV, through tree reduction and stacks, so we expect configuration reduction to carry over to call-by-value and call-by-name in the same way.
Examples
When instantiated with particular monadic containers, this abstract definition reproduces familiar operational semantics, with the exception of state. Figure 9 gives, for each example, the container, its monad structure and the configuration ⌈ op ⌉ \lceil\operatorname{op}\rceil ⌈ op ⌉ of each operation. By Theorem 5.6 they determine every Effect rule, and each example below derives its rules from one row of the table. The abstract configuration notation is sometimes clunky, and we use example-specific notation that is isomorphic to it.
Example 5.7. For errors, the free model is just T ( X ) = X + 1 T(X)=X+1 T ( X ) = X + 1 . This is the exception monadic container [42 Ex. 13] [48 ] . Its shape err represents the error and run the running computation. A program starts as ⟨ run , M ⟩ \langle\operatorname{run},M\rangle ⟨ run , M ⟩ . Flattening ⌈ err ⌉ \lceil\operatorname{err}\rceil ⌈ err ⌉ into its one position gives σ ∙ ( run , ∗ , err ) = err \sigma_{\bullet}(\operatorname{run},*,\operatorname{err})=\operatorname{err} σ ∙ ( run , ∗ , err ) = err , which has no positions:
⟨ run , S [ err ] ⟩ ↦ T ⟨ err ⟩ \langle\operatorname{run},S[\operatorname{err}]\rangle\mathrel{\mapsto_T}\langle\operatorname{err}\rangle ⟨ run , S [ err ]⟩ ↦ T ⟨ err ⟩
Table 9. Container data and the configuration ⌈ o p ⌉ \lceil op\rceil ⌈ o p ⌉ of each operation. Writer is worked out in Theorem 5.4 and § 5.3 .
Example 5.8. For state, for concreteness we consider two states, 0 and 1. The free model ( 2 × X ) 2 ≅ 2 2 × X 2 (2\times X)^2\cong2^2\times X^2 ( 2 × X ) 2 ≅ 2 2 × X 2 is the state monadic container [42 Ex. 12] [48 ] . A configuration runs the program for all initial states at once. Position b b b holds the term being executed when the initial state was b b b , and s ( b ) s(b) s ( b ) is the current state of that execution. We tabulate the two, writing ⟨ s , N → ⟩ \langle s,\overrightarrow{N}\rangle ⟨ s , N ⟩ as ⟨ ( b 0 , N 0 ) ∣ ( b 1 , N 1 ) ⟩ \langle(b_0,N_0)\mid(b_1,N_1)\rangle ⟨( b 0 , N 0 ) ∣ ( b 1 , N 1 )⟩ with b 0 = s ( 0 ) b_0=s(0) b 0 = s ( 0 ) and b 1 = s ( 1 ) b_1=s(1) b 1 = s ( 1 ) . The initial configuration is η M = ⟨ ( 0 , M ) ∣ ( 1 , M ) ⟩ \eta_M=\langle(0,M)\mid(1,M)\rangle η M = ⟨( 0 , M ) ∣ ( 1 , M )⟩ . At position 0, flattening ⌈ o p ⌉ \lceil op\rceil ⌈ o p ⌉ updates the state b 0 b_0 b 0 to s o p ( b 0 ) s_{op}(b_0) s o p ( b 0 ) and picks the operand at position b 0 b_0 b 0 of ⌈ o p ⌉ \lceil op\rceil ⌈ o p ⌉ . So get keeps b 0 b_0 b 0 and picks S [ M b 0 ] S[M_{b_0}] S [ M b 0 ] , and set b ′ \operatorname{set}_{b'} set b ′ moves to b ′ b' b ′ and picks S [ M ] S[M] S [ M ] . Position 1 is symmetric:
⟨ ( b 0 , S [ g e t ( M 0 , M 1 ) ] ) ∣ ( b 1 , N ) ⟩ ↦ T ⟨ ( b 0 , S [ M b 0 ] ) ∣ ( b 1 , N ) ⟩ \langle(b_0,S[\mathit{get}(M_0,M_1)])\mid(b_1,N)\rangle\mapsto_T\langle(b_0,S[M_{b_0}])\mid(b_1,N)\rangle ⟨( b 0 , S [ get ( M 0 , M 1 )]) ∣ ( b 1 , N )⟩ ↦ T ⟨( b 0 , S [ M b 0 ]) ∣ ( b 1 , N )⟩
⟨ ( b 0 , S [ s e t b ′ ( M ) ] ) ∣ ( b 1 , N ) ⟩ ↦ T ⟨ ( b ′ , S [ M ] ) ∣ ( b 1 , N ) ⟩ \langle(b_0,S[\mathit{set}_{b'}(M)])\mid(b_1,N)\rangle\mapsto_T\langle(b',S[M])\mid(b_1,N)\rangle ⟨( b 0 , S [ set b ′ ( M )]) ∣ ( b 1 , N )⟩ ↦ T ⟨( b ′ , S [ M ]) ∣ ( b 1 , N )⟩
So each pair ( b , N ) (b,N) ( b , N ) runs on its own, and the pair at position b b b is exactly the ordinary stateful machine started in state b b b . § 6.2 sketches how one Effect rule could give both machines.
Example 5.9. The weighted monoid has free model T ( X ) = List ( R × X ) T(X)=\operatorname{List}(R\times X) T ( X ) = List ( R × X ) . As a monadic container it is a weighted version of the list monadic container [42 Ex. 11] . If we write this configuration as ⟨ ( r 1 , M 1 ) ∣ ⋯ ⟩ \langle(r_1,M_1)\mid\cdots\rangle ⟨( r 1 , M 1 ) ∣ ⋯ ⟩ , then the initial configuration is ⟨ ( 1 , M ) ⟩ \langle(1,M)\rangle ⟨( 1 , M )⟩ . Each term in ⟨ ( r 1 , M 1 ) ∣ ⋯ ⟩ \langle(r_1,M_1)\mid\cdots\rangle ⟨( r 1 , M 1 ) ∣ ⋯ ⟩ carries a weight. When the term in a pair ( r , N ) (r,N) ( r , N ) performs op, that pair is replaced by the pairs of ⌈ o p ⌉ \lceil op\rceil ⌈ o p ⌉ , with their weights multiplied by r r r . For a c t r ′ \mathit{act}_{r'} act r ′ that is one pair of weight r ⋅ r ′ r\cdot r' r ⋅ r ′ , for e e e no pairs, and for ⊗ \otimes ⊗ two pairs of weight r r r :
⟨ ⋯ ∣ ( r , S [ a c t r ′ ( M ) ] ) ∣ ⋯ ⟩ ↦ T ⟨ ⋯ ∣ ( r ⋅ r ′ , S [ M ] ) ∣ ⋯ ⟩ \langle\cdots\mid(r,S[\mathit{act}_{r'}(M)])\mid\cdots\rangle\mapsto_T\langle\cdots\mid(r\cdot r',S[M])\mid\cdots\rangle ⟨ ⋯ ∣ ( r , S [ act r ′ ( M )]) ∣ ⋯ ⟩ ↦ T ⟨ ⋯ ∣ ( r ⋅ r ′ , S [ M ]) ∣ ⋯ ⟩
⟨ ⋯ ∣ ( r , S [ e ] ) ∣ ⋯ ⟩ ↦ T ⟨ ⋯ ∣ ⋯ ⟩ \langle\cdots\mid(r,S[e])\mid\cdots\rangle\mapsto_T\langle\cdots\mid\cdots\rangle ⟨ ⋯ ∣ ( r , S [ e ]) ∣ ⋯ ⟩ ↦ T ⟨ ⋯ ∣ ⋯ ⟩
⟨ ⋯ ∣ ( r , S [ M ⊗ M ′ ] ) ∣ ⋯ ⟩ ↦ T ⟨ ⋯ ∣ ( r , S [ M ] ) ∣ ( r , S [ M ′ ] ) ∣ ⋯ ⟩ \langle\cdots\mid(r,S[M\otimes M'])\mid\cdots\rangle\mapsto_T\langle\cdots\mid(r,S[M])\mid(r,S[M'])\mid\cdots\rangle ⟨ ⋯ ∣ ( r , S [ M ⊗ M ′ ]) ∣ ⋯ ⟩ ↦ T ⟨ ⋯ ∣ ( r , S [ M ]) ∣ ( r , S [ M ′ ]) ∣ ⋯ ⟩
Example 5.10. The pre-convex set has a free model that can be seen as a special case of the previous where the weights are nonzero probabilities that must sum to 1. It is the sub-container of the weighted one for the monoid ( 0 , 1 ] (0,1] ( 0 , 1 ] under multiplication, whose shapes are the lists of weights summing to 1. Similarly, a pair ( p , S [ M + q N ] ) (p,S[M+_qN]) ( p , S [ M + q N ]) is replaced by the pairs of ⌈ + q ⌉ \lceil+_q\rceil ⌈ + q ⌉ , with their weights multiplied by p p p . Weights are nonzero, so ⌈ + q ⌉ \lceil+_q \rceil ⌈ + q ⌉ has two pairs, of weights q q q and 1 − q 1-q 1 − q , only when 0 < q < 1 0<q<1 0 < q < 1 , while ⌈ + 1 ⌉ \lceil+_1 \rceil ⌈ + 1 ⌉ keeps just M M M and ⌈ + 0 ⌉ \lceil+_0 \rceil ⌈ + 0 ⌉ just N N N . That split gives the three rules:
⟨ ⋯ ∣ ( p , S [ M + 1 N ] ) ∣ ⋯ ⟩ ↦ T ⟨ ⋯ ∣ ( p , S [ M ] ) ∣ ⋯ ⟩ \langle\cdots\mid(p,S[M+_1N]) \mid\cdots\rangle\mapsto_T \langle\cdots\mid(p,S[M]) \mid\cdots\rangle ⟨ ⋯ ∣ ( p , S [ M + 1 N ]) ∣ ⋯ ⟩ ↦ T ⟨ ⋯ ∣ ( p , S [ M ]) ∣ ⋯ ⟩
⟨ ⋯ ∣ ( p , S [ M + 0 N ] ) ∣ ⋯ ⟩ ↦ T ⟨ ⋯ ∣ ( p , S [ N ] ) ∣ ⋯ ⟩ \langle\cdots\mid(p,S[M+_0N]) \mid\cdots\rangle\mapsto_T \langle\cdots\mid(p,S[N]) \mid\cdots\rangle ⟨ ⋯ ∣ ( p , S [ M + 0 N ]) ∣ ⋯ ⟩ ↦ T ⟨ ⋯ ∣ ( p , S [ N ]) ∣ ⋯ ⟩
⟨ ⋯ ∣ ( p , S [ M + q N ] ) ∣ ⋯ ⟩ ↦ T ⟨ ⋯ ∣ ( p q , S [ M ] ) ∣ ( p ( 1 − q ) , S [ N ] ) ∣ ⋯ ⟩ ( 0 < q < 1 ) \langle\cdots\mid(p,S[M+_qN]) \mid\cdots\rangle\mapsto_T \langle\cdots\mid(pq,S[M]) \mid(p(1-q),S[N]) \mid\cdots\rangle\quad(0<q<1) ⟨ ⋯ ∣ ( p , S [ M + q N ]) ∣ ⋯ ⟩ ↦ T ⟨ ⋯ ∣ ( pq , S [ M ]) ∣ ( p ( 1 − q ) , S [ N ]) ∣ ⋯ ⟩ ( 0 < q < 1 )
Nonexamples. The free-module monad of a semiring is in general not a monadic container. For instance, the modules of the Boolean semiring are the join-semilattices, whose free model is given by the finite powerset monad P f ( X ) \mathcal{P}_f(X) P f ( X ) . The finite powerset functor is not a container functor, since container functors preserve pullbacks [29 ] and P f \mathcal{P}_f P f does not. Intuitively, the functorial action T ( f ) T(f) T ( f ) of a container never changes the number of subterms, but for P f \mathcal{P}_f P f , applying f f f to { x , y } \{x,y\} { x , y } gives { f ( x ) } \{f(x)\} { f ( x )} when f ( x ) = f ( y ) f(x)=f(y) f ( x ) = f ( y ) . The convex spaces, whose free models are the finitely supported probability distributions, fail for the same reason.
The compromise is that we can give an operational model to modules of a semiring by using the theory of weighted monoids, because the theory of modules of a semiring is a quotient of the theory of weighted monoids. This means that there will be multiple weighted monoid configurations that represent the same element of the free module, e.g. ⟨ ( 1 , M ) ∣ ( 1 , M ) ⟩ \langle(1,M)\mid(1,M)\rangle ⟨( 1 , M ) ∣ ( 1 , M )⟩ and ⟨ ( 2 , M ) ⟩ \langle(2,M)\rangle ⟨( 2 , M )⟩ , but this can be viewed as an equivalence that can be imposed on the final result configurations that arise from the operational execution. A more systematic treatment of such quotients is a possible direction for future work (§ 6.2 ).
Nondeterminism and Soundness
Note that configuration reduction ↦ T \mapsto_T ↦ T is nondeterministic in several ways. First, we have the parallel nondeterminism of ↦ t r e e \mapsto_{\mathrm{tree}} ↦ tree where subterms of an operation can be evaluated in any order. We have the same kind of nondeterminism with the Pure and Effect rules, whose context C C C can single out any subterm of the configuration, so the subterms of a configuration can be evaluated in any order. As our weighted monoid example shows, this kind of nondeterminism can be desirable, as the weighted monoid encodes a form of nondeterminism and so it makes sense that the evaluation between different nondeterministic choices has no specified order of evaluation. Similarly for our state example, there is no need to evaluate the term for different start states in a particular order. There is also a nondeterminism between Pure and Effect steps. When a subterm is an operation under a stack, S [ op ( M → ) ] S[\operatorname{op}(\overrightarrow{M})] S [ op ( M )] , we might either take Pure steps or an Effect step. The Effect rule interprets the operation at once, while Pure steps first move it out of S S S one frame at a time.
We show that all of this nondeterminism is ultimately benign. Every step preserves the denotational semantics (Theorem 5.12 ). For an affine operational model, every reduction sequence terminates (Theorem 5.17 ), and at ground types every run reaches the same final configuration (Theorem 5.18 ).
Because we derived the operational semantics and denotational semantics from the free model, we can show that they agree by an abstract categorical calculation. First, we define a denotation of a configuration as the Kleisli extension of the denotation of closed computations of type F A FA F A :
⟦ − ⟧ T : T ( Comp ( F A ) ) → T ( ⟦ A ⟧ ) \llbracket-\rrbracket_T:T(\operatorname{Comp}(FA))\to T(\llbracket A\rrbracket) [ [ − ] ] T : T ( Comp ( F A )) → T ( [ [ A ] ] )
⟦ f ˉ ⟧ T = μ ( T ( ⟦ − ⟧ c ) ( t ˉ ) ) \llbracket\bar{f}\rrbracket_T=\mu(T(\llbracket-\rrbracket_c)(\bar{t})) [ [ f ˉ ] ] T = μ ( T ( [ [ − ] ] c ) ( t ˉ ))
Then the denotation of the initial configuration is correct.
Theorem 5.11 (Soundness of initial configuration). ⟦ η ( M ) ⟧ T = ⟦ M ⟧ c \llbracket\eta(M)\rrbracket_T=\llbracket M\rrbracket_c [ [ η ( M ) ] ] T = [ [ M ] ] c
Proof. Immediate by the unit and naturality laws of the monad
μ ( T ( ⟦ _ ⟧ c ) ( η ( M ) ) ) = μ ( η ( ⟦ M ⟧ c ) ) = ⟦ M ⟧ c \mu\bigl(T(\llbracket\_\rrbracket_c)(\eta(M))\bigr)=\mu\bigl(\eta(\llbracket M\rrbracket_c)\bigr)=\llbracket M\rrbracket_c μ ( T ( [ [ _ ] ] c ) ( η ( M )) ) = μ ( η ( [ [ M ] ] c ) ) = [ [ M ] ] c
And the denotation is an invariant of the reduction relation:
Theorem 5.12 (Soundness of ↦ T \mapsto_T ↦ T ). For t ~ , t ~ ′ : T ( Comp ( F A ) ) \widetilde{t},\widetilde{t}' : T(\operatorname{Comp}(FA)) t , t ′ : T ( Comp ( F A )) , if t ~ ↦ T t ~ ′ \widetilde{t} \mapsto_T \widetilde{t}' t ↦ T t ′ then ⟦ t ~ ⟧ T = ⟦ t ~ ′ ⟧ T \llbracket\widetilde{t}\rrbracket_T=\llbracket\widetilde{t}'\rrbracket_T [ [ t ] ] T = [ [ t ′ ] ] T .
Proof. (1) The Pure case follows from the soundness of tree reduction (Theorem 4.2 ).
(2) The Effect case. Both sides of the Effect rule denote μ ( ∂ T ( ⟦ _ ⟧ c ) ( C ) [ ⟦ o p ⟧ ( ⟦ S [ M ] ⟧ c ) ] ) \mu\bigl(\partial_T(\llbracket\_\rrbracket_c)(C)[\llbracket op\rrbracket(\llbracket S[M]\rrbracket_c)]\bigr) μ ( ∂ T ( [ [ _ ] ] c ) ( C ) [ [ [ o p ] ] ( [ [ S [ M ] ] ] c )] ) . This follows from the monad laws, since stacks and ⟦ _ ⟧ T \llbracket\_\rrbracket_T [ [ _ ] ] T are homomorphisms. The calculation is in Appendix § 11 .
Termination and Adequacy
To prove that configuration reduction terminates, we need one more condition. Every subterm of the reduct of an Effect step is either an operand S [ M i ] S[M_i] S [ M i ] or a neighboring subterm of the configuration. Operands may be copied, but neighboring subterms must not be. We call this condition affinity .3
Definition 5.13 (Affinity). A monadic container is affine if plugging a shape into a hole never copies a neighbor. Formally, for all s s s , s ∙ : Sh s_\bullet: \operatorname{Sh} s ∙ : Sh and p ∙ : P ( s ) p_\bullet: P(s) p ∙ : P ( s ) ,
pr 1 : P ( σ ∙ ( s , p ∙ , s ∙ ) ) → P ( s ) is injective on { q ∣ pr 1 q ≠ p ∙ } . \operatorname{pr}_1 : P\bigl(\sigma_\bullet(s,p_\bullet,s_\bullet)\bigr)\to P(s)\text{ is injective on }\{q\mid\operatorname{pr}_1q\ne p_\bullet\}. pr 1 : P ( σ ∙ ( s , p ∙ , s ∙ ) ) → P ( s ) is injective on { q ∣ pr 1 q = p ∙ } .
An operational model is affine if its monadic container is.
Example 5.14. Writer, errors and state are affine, since pr 1 \operatorname{pr}_1 pr 1 is injective everywhere. For writer and errors every shape has at most one position. For state, pr ( b ) = ( b , s ( b ) ) \operatorname{pr}(b)=(b,s(b)) pr ( b ) = ( b , s ( b )) , so pr 1 \operatorname{pr}_1 pr 1 is the identity. The get steps of state only drop the branch not taken and copy nothing.
Example 5.15. The weighted monoid and the pre-convex sets are affine, since each neighbor receives ι = [ 1 ] \iota=[1] ι = [ 1 ] , which has a single position. Only the hole can split, as in the ⊗ \otimes ⊗ step.
To prove that an affine operational model ensures termination, we show that every step decreases a termination measure in a well-founded order. A computation is measured by how many tree steps and operations it still has to perform (using Theorem 4.7). For a configuration, we collect the measures of its subterms, one for each position, into a multiset.
Definition 5.16 (Termination measure). Let M : Comp ( F A ) M:\operatorname{Comp}(FA) M : Comp ( F A ) , define a measure ∣ M ∣ |M| ∣ M ∣ as follows:
If M = ret V M=\operatorname{ret} V M = ret V , then ∣ ret V ∣ = 0 |\operatorname{ret} V|=0 ∣ ret V ∣ = 0 .
If M = op ( M ⃗ ) M=\operatorname{op}(\vec{M}) M = op ( M ) then ∣ op ( M ⃗ ) ∣ = 1 + ∑ i ∣ M i ∣ |\operatorname{op}(\vec{M})|=1+\sum_i|M_i| ∣ op ( M ) ∣ = 1 + ∑ i ∣ M i ∣ .
Otherwise M M M takes exactly one S S S -step M ↦ S N M\mapsto_S N M ↦ S N (Theorem 4.1), and ∣ M ∣ = 1 + ∣ N ∣ |M|=1+|N| ∣ M ∣ = 1 + ∣ N ∣ .
Because ↦ t r e e \mapsto_{\mathrm{tree}} ↦ tree is strongly normalizing (Theorem 4.7), this measure is finite.
For a configuration t ~ = ⟨ s , N ⃗ ⟩ : T ( Comp ( F A ) ) \widetilde{t}=\langle s,\vec{N}\rangle:T(\operatorname{Comp}(FA)) t = ⟨ s , N ⟩ : T ( Comp ( F A )) , we define the multiset ∣ t ~ ∣ = { ∣ N p ∣ ∣ p : P ( s ) } |\widetilde{t}|=\{|N_p|\mid p:P(s)\} ∣ t ∣ = { ∣ N p ∣ ∣ p : P ( s )} .
Multisets are compared by the Dershowitz–Manna ordering, where Y < M X Y<_M X Y < M X if Y = ( X − R ) + A Y=(X-R)+A Y = ( X − R ) + A for some nonempty R ⊆ X R\subseteq X R ⊆ X such that every element of A A A is smaller than some element of R R R . Because < M <_M < M is well founded, so is < M <_M < M [10 ] .
Then we get strong normalization because every step reduces the measure.
Theorem 5.17 (Strong normalization for ↦ T \mapsto_T ↦ T ). Let the operational model be affine and t ~ : T ( Comp ( F A ) ) \tilde{t} : T(\operatorname{Comp}(FA)) t ~ : T ( Comp ( F A )) . (1) Every reduction sequence from t ~ \tilde{t} t ~ is finite. (2) If no step applies to t ~ \tilde{t} t ~ , then t ~ = T ( ret ) ( v ~ ) \tilde{t} =_T (\operatorname{ret})(\tilde{v}) t ~ = T ( ret ) ( v ~ ) for some v ~ : T ( Val ( A ) ) \tilde{v} : T(\operatorname{Val}(A)) v ~ : T ( Val ( A )) .
Proof. Every reduction t ~ ↦ T t ~ ′ \tilde{t} \mapsto_T \tilde{t}^{\prime} t ~ ↦ T t ~ ′ decreases the measure of Theorem 5.16, ∣ t ~ ′ ∣ < M ∣ t ~ ∣ |\tilde{t}^{\prime}| <_M |\tilde{t}| ∣ t ~ ′ ∣ < M ∣ t ~ ∣ .
If every element of ∣ t ~ ∣ |\tilde{t}| ∣ t ~ ∣ is 0, then every subterm has measure 0. Since an operation or a term that steps has measure at least 1, every subterm is of the form ret V \operatorname{ret}\ V ret V (Theorem 4.1), so t ~ = T ( ret ) ( v ~ ) \tilde{t} =_T (\operatorname{ret})(\tilde{v}) t ~ = T ( ret ) ( v ~ ) .
Otherwise, some element of ∣ t ~ ∣ |\tilde{t}| ∣ t ~ ∣ is positive. By Theorem 4.1 the corresponding subterm is an operation or takes an S-step, so at least one reduction applies. Consider any t ~ ↦ T t ~ ′ \tilde{t} \mapsto_T \tilde{t}^{\prime} t ~ ↦ T t ~ ′ . There are two cases:
If it is a Pure step, it rewrites one subterm N p ↦ t r e e N p ′ N_p \mapsto_{\mathrm{tree}} N_p^{\prime} N p ↦ tree N p ′ , and ∣ N p ′ ∣ < ∣ N p ∣ |N_p^{\prime}| < |N_p| ∣ N p ′ ∣ < ∣ N p ∣ by induction on the tree step, using case 3 of Theorem 5.16 for an S-step and case 2 for a step under an operation. So R = { ∣ N p ∣ } R = \{|N_p|\} R = { ∣ N p ∣ } and A = { ∣ N p ′ ∣ } A = \{|N_p^{\prime}|\} A = { ∣ N p ′ ∣ } . The others stay the same.
If it is an Effect step from C [ S [ op ( M ⃗ ) ] ] C[S[\operatorname{op}(\vec{M})]] C [ S [ op ( M )]] with C = ⟨ s , p ∙ , N ⃗ ⟩ C = \langle s,p_{\bullet},\vec{N}\rangle C = ⟨ s , p ∙ , N ⟩ , then by Theorem 5.6 each subterm of the reduct is a neighbor N p N_p N p (p ≠ p ∙ p \ne p_{\bullet} p = p ∙ ) or an operand S [ M i ] S[M_i] S [ M i ] , and by affinity each neighbor occurs at most once. So we take R = { ∣ S [ op ( M ⃗ ) ] ∣ } R = \{|S[\operatorname{op}(\vec{M})]|\} R = { ∣ S [ op ( M )] ∣ } plus the dropped neighbors, and A A A the measures of the operands in the reduct. It suffices that ∣ S [ M i ] ∣ < ∣ S [ op ( M ⃗ ) ] ∣ |S[M_i]| < |S[\operatorname{op}(\vec{M})]| ∣ S [ M i ] ∣ < ∣ S [ op ( M )] ∣ for each i i i . If S S S has k k k frames, then S [ op ( M ⃗ ) ] S[\operatorname{op}(\vec{M})] S [ op ( M )] reaches op ( S [ M ] → ) \operatorname{op}(\overrightarrow{S[M]}) op ( S [ M ] ) in k k k S-steps, one per frame. So by Theorem 4.1 and cases 3 and 2 of Theorem 5.16, ∣ S [ op ( M ⃗ ) ] ∣ = k + 1 + ∑ i ∣ S [ M i ] ∣ |S[\operatorname{op}(\vec{M})]| = k + 1 + \sum_i |S[M_i]| ∣ S [ op ( M )] ∣ = k + 1 + ∑ i ∣ S [ M i ] ∣ .
Since < M <_M < M is well founded, every reduction sequence terminates. □
Combining soundness and strong normalization gives computational adequacy in the sense of Plotkin and Power [40 ] . Running the configuration machine computes the denotation.
Theorem 5.18 (Computational adequacy). Let the operational model be affine, and let A A A be a type such that ⟦ _ ⟧ v : Val ( A ) → ⟦ A ⟧ \llbracket\_ \rrbracket_v : \operatorname{Val}(A) \to\llbracket A \rrbracket [ [ _ ] ] v : Val ( A ) → [ [ A ] ] is an isomorphism (for instance, a ground type built from 0 , 1 , + , × 0,1,+,\times 0 , 1 , + , × ). Then for every M : Comp ( F A ) M : \operatorname{Comp}(FA) M : Comp ( F A ) : (1) η ( M ) ↦ T ∗ ( ret ) ( v ~ ) \eta(M) \mapsto_T^* (\operatorname{ret})(\tilde{v}) η ( M ) ↦ T ∗ ( ret ) ( v ~ ) for some v ~ : T ( Val ( A ) ) \tilde{v} : T(\operatorname{Val}(A)) v ~ : T ( Val ( A )) ; (2) T ( ⟦ _ ⟧ v ) ( v ~ ) = ⟦ M ⟧ c T(\llbracket\_ \rrbracket_v)(\tilde{v}) = \llbracket M \rrbracket_c T ( [ [ _ ] ] v ) ( v ~ ) = [ [ M ] ] c ; and (3) v ~ \tilde{v} v ~ is unique.
Proof. (1) follows from Theorem 5.17 with t ~ = η ( M ) \tilde{t} = \eta(M) t ~ = η ( M ) . For (2), by soundness ⟦ M ⟧ c = ⟦ η ( M ) ⟧ T = ⟦ T ( ret ) ( v ~ ) ⟧ T \llbracket M \rrbracket_c = \llbracket\eta(M) \rrbracket_T = \llbracket T(\operatorname{ret})(\tilde{v}) \rrbracket_T [ [ M ] ] c = [ [ η ( M ) ] ] T = [ [ T ( ret ) ( v ~ ) ] ] T , and
⟦ T ( ret ) ( v ~ ) ⟧ T = μ ( T ( ⟦ _ ⟧ c ) ( T ( ret ) ( v ~ ) ) ) = μ ( T ( η ∘ ⟦ _ ⟧ v ) ( v ~ ) ) = T ( ⟦ _ ⟧ v ) ( v ~ ) . \llbracket T(\operatorname{ret})(\tilde{v}) \rrbracket_T = \mu(T(\llbracket\_ \rrbracket_c)(T(\operatorname{ret})(\tilde{v}))) = \mu(T(\eta\circ\llbracket\_ \rrbracket_v)(\tilde{v})) = T(\llbracket\_ \rrbracket_v)(\tilde{v}). [ [ T ( ret ) ( v ~ ) ] ] T = μ ( T ( [ [ _ ] ] c ) ( T ( ret ) ( v ~ ))) = μ ( T ( η ∘ [ [ _ ] ] v ) ( v ~ )) = T ( [ [ _ ] ] v ) ( v ~ ) .
(3) follows from (2). Container functors preserve injections, so T ( ⟦ _ ⟧ v ) T(\llbracket\_ \rrbracket_v) T ( [ [ _ ] ] v ) is injective, and any two results with the same denotation ⟦ M ⟧ c \llbracket M \rrbracket_c [ [ M ] ] c are equal. □
Corollary 5.19. Under the hypotheses of Theorem 5.18 , if ⟦ M ⟧ c = ⟦ N ⟧ c \llbracket M \rrbracket_c = \llbracket N \rrbracket_c [ [ M ] ] c = [ [ N ] ] c then η ( M ) \eta(M) η ( M ) and η ( N ) \eta(N) η ( N ) reduce to the same final configuration.
Discussion
We have presented a uniform framework in which both denotational and operational semantics are derived from the same algebraic description of effects. Starting from an algebraic theory, we construct a denotational semantics, a tree-based operational semantics, and a configuration-based operational semantics, together with generic canonicity, soundness and adequacy arguments connecting them. The configuration-based semantics is computed from the monadic container that is the free model. A short calculation shows that every step preserves the denotation. Under a simple affinity condition on the container, every run terminates, and at ground types it ends in the denotation of the program. We believe this provides a foundation for developing operational semantics for algebraic effects in a systematic manner.
Related Work
Operational Semantics of Algebraic Effects
Many operational accounts of algebraic effects [25 , 28 , 40 ] proceed by evaluating programs to effect trees (or free monadic syntax), which are subsequently interpreted into a semantic model via a monad morphism or handler. This cleanly separates operational evaluation from denotational interpretation, but does not, in general, account for the equations of an algebraic theory during reduction. By contrast, our configuration reduction contains tree reduction as its Pure steps (Figure 7 ), so a program can be evaluated to a tree and then interpreted, or have its operations interpreted as they are reached. Either way, configuration reduction is sound with respect to the denotational semantics (Theorem 5.12 ).
The work on Guarded Interaction Trees [15 ] shares our idea that operational reduction should take place within semantic configurations. Programs are interpreted in the semantic domain of guarded interaction trees, and a corresponding notion of configuration-based reduction is defined at the level of interaction trees. The authors define a small-step, configuration-based operational semantics for a recursive language with natural numbers and I/O, and prove it sound and adequate with respect to the guarded interaction tree reduction. Their proofs use effect-specific logical relations, while ours are effect generic.
Monadic Rewriting and Operational Semantics
Monadic rewriting [17 ] uses a rewriting relation between elements of a monad, and later work builds on it for studying a monadic variant of intersection types [18 ] and operational semantics for type-and-effect systems [9 ] . Monadic rewriting is based on a rewriting relation between elements of T ( E x p ) T(\mathrm{Exp}) T ( Exp ) , which is quite similar in spirit to our configuration reduction. Furthermore, their reductions evaluate the terms in the configuration by evaluating the operation into the monad. Our approach differs firstly in that we emphasize a notion of one-place reduction capturing the common style of existing operational semantics, whereas in all of these works, the effects are evaluated as a parallel reduction . That is, when an effectful step is taken, all subterms take a step simultaneously, whereas in our system a subterm is non-deterministically chosen to step. Furthermore, Gavazzo and Faggian [17 ] and Gavazzo et al. [18 ] restrict to weakly Cartesian monads, so they exclude some common examples such as reader and state. On the other hand, we require monadic containers and not all weakly Cartesian monads are monadic containers, e.g. finite multisets (§ 6.2 ). However, Gandin et al. [9 ] do not restrict to weakly Cartesian monads, but do restrict to the underlying operational semantics of terms being deterministic, which we do not, as our tree reduction includes non-deterministic evaluation order. Because none of these works use one-place reduction, none use monadic containers and none of them identify anything like an affinity condition or prove an analogous termination result, as they include non-terminating systems. Gavazzo et al. [18 ] characterize termination by intersection typability, but this is not analogous to our termination result, which follows for simply typed CBPV terms. Additionally none of these approaches prove soundness and adequacy with respect to denotational semantics or relate to the tree-based reduction.
Structural Operational Semantics
Our work is related in spirit to the bialgebraic approach to structural operational semantics of Turi and Plotkin [46 ] , also known as abstract GSOS, which seeks a systematic categorical account of operational semantics. There, operational behavior is specified by a distributive law between syntax and behavior functors, inducing a canonical coalgebra on the initial algebra. The bialgebraic framework has been extended to higher-order languages [20 ] , including call-by-push-value [22 ] , and stateful computation [21 ] .
Such a distributive law gives each syntactic constructor its behavior from the behaviors of its arguments, so behavior sits under the syntax. We instead fix the syntax of CBPV and derive the configurations and effect rules from an algebraic theory and its free model. Our configurations are the other way around, with the syntax inside the free model of the effects, and our container is this free model, rather than a polynomial functor describing the syntax. Closest in this line is the extension of Turi and Plotkin’s framework with algebraic effects by Abou-Saleh and Pattinson [3 ] , where the one-step behavior of a program lies in an effect monad, such as the free model of a Lawvere theory, possibly combined with a comodel for state. Their languages are first-order and their states hold a single program rather than many subterms. Whether our configuration reduction can be given in their framework is open.
Future Work
To support a wider variety of effects, we would like to extend this framework to include theories of local state [43 , 44 ] , whose models are algebras in categories of presheaves rather than in Set. There computational contexts are indexed by varying notions of locality and resource. This perspective is well developed in work of Fiore on discrete generalized polynomial functors [12 ] and of Fiore and Hur on equational systems [13 ] , where presheaf categories model syntax with scope and dependency.
Our strong normalization proof for configuration reduction relies on a termination measure and therefore does not extend directly to general recursion. Future work could integrate guarded recursion [34 ] into our framework by treating it as an algebraic effect.
Our operations have finite arity, and our containers have finitely many positions. Allowing infinite arities, for example state over an infinite set of states, would give configurations with infinitely many subterms. The initial configuration then holds one copy of the program for each initial state, and unless the program is already a value, no finite reduction sequence reaches a normal form. Plotkin’s adequacy result for infinitary algebraic effects [35 ] is a natural starting point.
Our configuration-based reduction is currently restricted to algebraic effects whose free models are monadic containers, excluding quotient-based theories such as finite sets and convex spaces. A natural extension is to reduce in a theory with fewer equations whose free model T ′ T' T ′ is a monadic container, such as lists for finite sets, with a split surjection q : T ′ ( X ) ↠ T ( X ) q : T'(X) \twoheadrightarrow T(X) q : T ′ ( X ) ↠ T ( X ) , allowing reduction to operate on canonical representatives while remaining sound with respect to the quotient equations. The present framework is the special case of the trivial quotient. For example, finite sets admit canonical representatives as sorted, duplicate-free lists over totally ordered sets. We leave a systematic development of quotient-based operational models to future work.
Our configurations for state are not those of the ordinary stateful machine, which pair a single state with a single term. That machine instead comes from the state comodel [38 , 47 ] , which answers each get and set, and more generally from runners [4 ] . Both kinds of configuration are right modules over the monad T T T . A comodule C C C gives the module C × T C \times T C × T , and our configurations are T T T acting on itself by μ \mu μ . We believe the Effect rule extends to any right T T T -module whose functor is a container, with the module action in place of μ \mu μ , which would recover the ordinary machine as well as ours.
Algebraic theories can be combined by sum and tensor [23 ] , and we would like operational models to combine in the same way. Some combinations stay within monadic containers. Our weighted monoids are the tensor of monoids with writer, and tensoring with writer or with finite state preserves monadic containers in general. Others do not, since the tensor of monoids with itself has finite multisets as its free model. Distributive laws of monadic containers [42 ] describe when two monadic containers compose, and so suggest when an operational model can be built from its parts. Whether distributive laws of monadic containers preserve affinity is open.
Acknowledgments
This material is based upon work supported by the National Science Foundation CISE Graduate Fellowships (CSGrad4US) under Grant No. 2313998. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
Disclosure of Use of AI in Research
We used an LLM-based coding assistant to help formalize the paper’s results in an unpublished Agda mechanization. The formalization revealed a gap in one proof and several smaller errors, which we corrected by hand.
Data Availability Statement
This paper has no artifact, all novel theorems are proven in the paper or its appendices.
References
Proof of the Fundamental Theorem of Section 3
We prove Theorem 3.1 by induction on the typing derivation, with one case for each rule of C B P V + ( T ) \mathrm{CBPV}^{+}(\mathcal{T}) CBPV + ( T ) in Figure 1 for the judgments Γ ⊢ V : A \Gamma\vdash V : A Γ ⊢ V : A and Γ ∣ ⋅ ⊢ M : B \Gamma\mid\cdot\vdash M : B Γ ∣ ⋅ ⊢ M : B . In each case we fix γ \gamma γ with G [ Γ ] ( γ ) \mathcal{G}[\Gamma](\gamma) G [ Γ ] ( γ ) and apply the inductive hypotheses at γ \gamma γ . Values and computations are taken up to the equations of Figure 2 , so V [ A ] \mathcal{V}[A] V [ A ] and C [ B ] \mathcal{C}[B] C [ B ] hold of a term exactly when they hold of every term equal to it. In each β \beta β case below, the β \beta β law turns the goal into a hypothesis.
Variable. V [ A ] ( γ ( x ) ) \mathcal{V}[A](\gamma(x)) V [ A ] ( γ ( x )) is a conjunct of G [ Γ ] ( γ ) \mathcal{G}[\Gamma](\gamma) G [ Γ ] ( γ ) .
Unit. V [ 1 ] ( ( ) ) \mathcal{V}[1](()) V [ 1 ] (( )) holds by definition.
Injection. V [ A 1 + A 2 ] ( σ i ( V [ γ ] ) ) \mathcal{V}[A_1 + A_2](\sigma_i(\mathcal{V}[\gamma])) V [ A 1 + A 2 ] ( σ i ( V [ γ ])) is V [ A i ] ( V [ γ ] ) \mathcal{V}[A_i](\mathcal{V}[\gamma]) V [ A i ] ( V [ γ ]) , the hypothesis.
Pair. V [ A × A ′ ] ( V [ γ ] , V ′ [ γ ] ) \mathcal{V}[A \times A'](\mathcal{V}[\gamma],\mathcal{V}'[\gamma]) V [ A × A ′ ] ( V [ γ ] , V ′ [ γ ]) is the conjunction of the two hypotheses.
Thunk. We need C [ B ] ( force ( thunk M [ γ ] ) ) \mathcal{C}[B](\operatorname{force}(\operatorname{thunk} M[\gamma])) C [ B ] ( force ( thunk M [ γ ])) . Since force ( thunk M [ γ ] ) = M [ γ ] \operatorname{force}(\operatorname{thunk} M[\gamma]) = M[\gamma] force ( thunk M [ γ ]) = M [ γ ] , this is the hypothesis.
Force. V [ U B ] ( V [ γ ] ) \mathcal{V}[UB](\mathcal{V}[\gamma]) V [ U B ] ( V [ γ ]) is by definition C [ B ] ( force V [ γ ] ) \mathcal{C}[B](\operatorname{force}\mathcal{V}[\gamma]) C [ B ] ( force V [ γ ]) .
Case on the empty type. The hypothesis on V V V gives V [ 0 ] ( V [ γ ] ) \mathcal{V}[0](V[\gamma]) V [ 0 ] ( V [ γ ]) , which is ⊥ \bot ⊥ , so the case is vacuous. The same holds for the complex value case 0 ( V ) { } \operatorname{case}_0(V)\{\} case 0 ( V ) { } .
Case on unit. The η \eta η law for 1 1 1 gives V [ γ ] = ( ) V[\gamma] = () V [ γ ] = ( ) . Then case 1 ( ( ) ) { M [ γ ] } = M [ γ ] \operatorname{case}_1(())\{M[\gamma]\} = M[\gamma] case 1 (( )) { M [ γ ]} = M [ γ ] , so the goal is the hypothesis on M M M . The complex value case 1 ( V ) { W } \operatorname{case}_1(V)\{W\} case 1 ( V ) { W } is the same with V [ A ] \mathcal{V}[A] V [ A ] in place of C [ B ] \mathcal{C}[B] C [ B ] .
Case on sums. The hypothesis on V V V gives V [ γ ] = σ i W V[\gamma] = \sigma_i W V [ γ ] = σ i W with V [ A i ] ( W ) \mathcal{V}[A_i](W) V [ A i ] ( W ) . Then
case + ( σ i W ) { x 1 . M 1 [ γ ] ∣ x 2 . M 2 [ γ ] } = M i [ γ ] [ W / x i ] , \operatorname{case}_{+}(\sigma_i W)\{x_1.M_1[\gamma] \mid x_2.M_2[\gamma]\} = M_i[\gamma][W/x_i], case + ( σ i W ) { x 1 . M 1 [ γ ] ∣ x 2 . M 2 [ γ ]} = M i [ γ ] [ W / x i ] ,
and G [ Γ , x i : A i ] ( γ , W ) \mathcal{G}[\Gamma,x_i:A_i](\gamma,W) G [ Γ , x i : A i ] ( γ , W ) gives C [ B ] ( M i [ γ ] [ W / x i ] ) \mathcal{C}[B](M_i[\gamma][W/x_i]) C [ B ] ( M i [ γ ] [ W / x i ]) . The complex value case + ( V ) { x 1 . W 1 ∣ x 2 . W 2 } \operatorname{case}_{+}(V)\{x_1.W_1 \mid x_2.W_2\} case + ( V ) { x 1 . W 1 ∣ x 2 . W 2 } is the same with V [ A ] \mathcal{V}[A] V [ A ] in place of C [ B ] \mathcal{C}[B] C [ B ] .
Case on products. The hypothesis on V V V gives W W W and W ′ W' W ′ with V [ γ ] = ( W , W ′ ) V[\gamma] = (W,W') V [ γ ] = ( W , W ′ ) , V [ A ] ( W ) \mathcal{V}[A](W) V [ A ] ( W ) and V [ A ′ ] ( W ′ ) \mathcal{V}[A'](W') V [ A ′ ] ( W ′ ) . Then
case × ( W , W ′ ) { x , y . M [ γ ] } = M [ γ ] [ W / x , W ′ / y ] , \operatorname{case}_{\times}(W,W')\{x,y.M[\gamma]\} = M[\gamma][W/x,W'/y], case × ( W , W ′ ) { x , y . M [ γ ]} = M [ γ ] [ W / x , W ′ / y ] ,
and G [ Γ , x : A , y : A ′ ] ( γ , W , W ′ ) \mathcal{G}[\Gamma,x:A,y:A'](\gamma,W,W') G [ Γ , x : A , y : A ′ ] ( γ , W , W ′ ) gives C [ B ] \mathcal{C}[B] C [ B ] of it. The complex value case × ( V ) { x , y . W } \operatorname{case}_{\times}(V)\{x,y.W\} case × ( V ) { x , y . W } is the same with V [ A ] \mathcal{V}[A] V [ A ] in place of C [ B ] \mathcal{C}[B] C [ B ] .
Return. The first rule of C [ F A ] \mathcal{C}[FA] C [ F A ] in Figure 4 .
Bind. Let S : = x ← ∙ ; N [ γ ] S := x \leftarrow\bullet; N[\gamma] S := x ← ∙ ; N [ γ ] . The hypothesis on M M M gives C [ F A ] ( M [ γ ] ) \mathcal{C}[FA](M[\gamma]) C [ F A ] ( M [ γ ]) , and we show C [ B ] ( S [ M ′ ] ) \mathcal{C}[B](S[M']) C [ B ] ( S [ M ′ ]) for every M ′ M' M ′ with C [ F A ] ( M ′ ) \mathcal{C}[FA](M') C [ F A ] ( M ′ ) , by induction on the proof of C [ F A ] ( M ′ ) \mathcal{C}[FA](M') C [ F A ] ( M ′ ) .
( M ′ = return V (M' = \operatorname{return} V ( M ′ = return V with V [ A ] ( V ) ) \mathcal{V}[A](V)) V [ A ] ( V )) Then S [ return V ] = N [ γ ] [ V / x ] S[\operatorname{return} V] = N[\gamma][V/x] S [ return V ] = N [ γ ] [ V / x ] , and G [ Γ , x : A ] ( γ , V ) \mathcal{G}[\Gamma,x:A](\gamma,V) G [ Γ , x : A ] ( γ , V ) gives C [ B ] ( N [ γ ] [ V / x ] ) \mathcal{C}[B](N[\gamma][V/x]) C [ B ] ( N [ γ ] [ V / x ]) .
( M ′ = op ( M ‾ ) (M' = \operatorname{op}(\overline{M}) ( M ′ = op ( M ) with C [ F A ] ( M i ) \mathcal{C}[FA](M_i) C [ F A ] ( M i ) for each i ) i) i ) The inductive hypothesis gives C [ B ] ( S [ M i ] ) \mathcal{C}[B](S[M_i]) C [ B ] ( S [ M i ]) for each i i i , and C [ B ] \mathcal{C}[B] C [ B ] is closed under the operations of Σ \Sigma Σ , so C [ B ] ( op ( S [ M ] ‾ ) ) \mathcal{C}[B](\operatorname{op}(\overline{S[M]})) C [ B ] ( op ( S [ M ] )) . The algebraic law S [ op ( M ‾ ) ] = op ( S [ M ] ‾ ) S[\operatorname{op}(\overline{M})] = \operatorname{op}(\overline{S[M]}) S [ op ( M )] = op ( S [ M ] ) makes this the goal.
Operation. Each C [ B ] ( M i [ γ ] ) C[B](M_i[\gamma]) C [ B ] ( M i [ γ ]) holds, and C [ B ] C[B] C [ B ] is closed under the operations of Σ \Sigma Σ , so C [ B ] ( op ( M → [ γ ] ) ) C[B](\operatorname{op}(\overrightarrow{M}[\gamma])) C [ B ] ( op ( M [ γ ])) .
Empty tuple. C [ ⊤ ] ( ⟨ ⟩ ) C[\top](\langle\rangle) C [ ⊤ ] (⟨ ⟩) holds, since C [ ⊤ ] C[\top] C [ ⊤ ] holds of every computation.
Abstraction. Given V [ A ] ( V ) V[A](V) V [ A ] ( V ) , we have ( λ x : A . M [ γ ] ) V = M [ γ ] [ V / x ] (\lambda x : A.\ M[\gamma])\ V = M[\gamma][V/x] ( λ x : A . M [ γ ]) V = M [ γ ] [ V / x ] , and G [ Γ , x : A ] ( γ , V ) G[\Gamma, x : A](\gamma,V) G [ Γ , x : A ] ( γ , V ) gives C [ B ] ( M [ γ ] [ V / x ] ) C[B](M[\gamma][V/x]) C [ B ] ( M [ γ ] [ V / x ]) .
Application. The hypothesis on M M M , applied to V [ γ ] V[\gamma] V [ γ ] , which satisfies V [ A ] V[A] V [ A ] by the hypothesis on V V V .
Pairing. By definition of C [ B 1 & B 2 ] C[B_1 \mathbin{\&} B_2] C [ B 1 & B 2 ] , we need C [ B i ] ( π i ⟨ M 1 [ γ ] , M 2 [ γ ] ⟩ ) C[B_i](\pi_i\langle M_1[\gamma], M_2[\gamma]\rangle) C [ B i ] ( π i ⟨ M 1 [ γ ] , M 2 [ γ ]⟩) for each i i i . Since
π i ⟨ M 1 [ γ ] , M 2 [ γ ] ⟩ = M i [ γ ] , \pi_i\langle M_1[\gamma], M_2[\gamma]\rangle= M_i[\gamma], π i ⟨ M 1 [ γ ] , M 2 [ γ ]⟩ = M i [ γ ] ,
this is the hypothesis on M i M_i M i .
Projection. C [ B i ] ( π i M [ γ ] ) C[B_i](\pi_i M[\gamma]) C [ B i ] ( π i M [ γ ]) is a conjunct of C [ B 1 & B 2 ] ( M [ γ ] ) C[B_1 \mathbin{\&} B_2](M[\gamma]) C [ B 1 & B 2 ] ( M [ γ ]) .
Proof of the Fundamental Theorem of Section 4
We prove Theorem 4.5 by induction on the typing derivation, with one case for each rule of C B P V ( T ) CBPV(T) C B P V ( T ) in Figure 1 . In each case we fix γ \gamma γ with G [ Γ ] ( γ ) G[\Gamma](\gamma) G [ Γ ] ( γ ) and apply the inductive hypotheses at γ \gamma γ . Each β \beta β rule of Figure 5 with S = ∙ S = \mathord{\bullet} S = ∙ is an S-step, so in the β \beta β cases the anti-reduction lemma for computation logical predicates turns the goal into a hypothesis.
Variable. V [ A ] ( γ ( x ) ) V[A](\gamma(x)) V [ A ] ( γ ( x )) is a conjunct of G [ Γ ] ( γ ) G[\Gamma](\gamma) G [ Γ ] ( γ ) .
Unit. V [ 1 ] ( ( ) ) V[1](()) V [ 1 ] (( )) holds by definition.
Injection. V [ A 1 + A 2 ] ( σ i ( V [ γ ] ) ) V[A_1 + A_2](\sigma_i(V[\gamma])) V [ A 1 + A 2 ] ( σ i ( V [ γ ])) is V [ A i ] ( V [ γ ] ) V[A_i](V[\gamma]) V [ A i ] ( V [ γ ]) , the hypothesis.
Pair. V [ A × A ′ ] ( V [ γ ] , V ′ [ γ ] ) V[A \mathbin{\times} A'](V[\gamma],V'[\gamma]) V [ A × A ′ ] ( V [ γ ] , V ′ [ γ ]) is the conjunction of the two hypotheses.
Thunk. We need C [ B ] ( force ( thunk M [ γ ] ) ) C[B](\operatorname{force}(\operatorname{thunk} M[\gamma])) C [ B ] ( force ( thunk M [ γ ])) . Anti-reduction along force ( thunk M [ γ ] ) ↦ S M [ γ ] \operatorname{force}(\operatorname{thunk} M[\gamma]) \mapsto_S M[\gamma] force ( thunk M [ γ ]) ↦ S M [ γ ] gives it from the hypothesis.
Force. V [ U B ] ( V [ γ ] ) V[U B](V[\gamma]) V [ U B ] ( V [ γ ]) is by definition C [ B ] ( force V [ γ ] ) C[B](\operatorname{force} V[\gamma]) C [ B ] ( force V [ γ ]) .
Case on the empty type. The hypothesis on V V V gives V [ 0 ] ( V [ γ ] ) V[0](V[\gamma]) V [ 0 ] ( V [ γ ]) , which is ⊥ \bot ⊥ , so the case is vacuous.
Case on unit. The only closed value of type 1 1 1 is ( ) () ( ) , so V [ γ ] = ( ) V[\gamma] = () V [ γ ] = ( ) . Then case 1 ( ( ) ) { M [ γ ] } ↦ S M [ γ ] \operatorname{case}_1(())\{M[\gamma]\} \mapsto_S M[\gamma] case 1 (( )) { M [ γ ]} ↦ S M [ γ ] , and anti-reduction gives C [ B ] C[B] C [ B ] of it from the hypothesis on M M M .
Case on sums. The hypothesis on V V V gives V [ γ ] = σ i W V[\gamma] = \sigma_i W V [ γ ] = σ i W with V [ A i ] ( W ) V[A_i](W) V [ A i ] ( W ) . Then
case + ( σ i W ) { x 1 . M 1 [ γ ] ∣ x 2 . M 2 [ γ ] } ↦ S M i [ γ ] [ W / x i ] , \operatorname{case}_+(\sigma_i W)\{x_1.\ M_1[\gamma]\mid x_2.\ M_2[\gamma]\} \mapsto_S M_i[\gamma][W/x_i], case + ( σ i W ) { x 1 . M 1 [ γ ] ∣ x 2 . M 2 [ γ ]} ↦ S M i [ γ ] [ W / x i ] ,
and G [ Γ , x i : A i ] ( γ , W ) G[\Gamma, x_i : A_i](\gamma,W) G [ Γ , x i : A i ] ( γ , W ) gives C [ B ] ( M i [ γ ] [ W / x i ] ) C[B](M_i[\gamma][W/x_i]) C [ B ] ( M i [ γ ] [ W / x i ]) . Anti-reduction finishes the case.
Case on products. The hypothesis on V V V gives W W W and W ′ W' W ′ with V [ γ ] = ( W , W ′ ) V[\gamma] = (W,W') V [ γ ] = ( W , W ′ ) , V [ A ] ( W ) V[A](W) V [ A ] ( W ) and V [ A ′ ] ( W ′ ) V[A'](W') V [ A ′ ] ( W ′ ) . Then
case × ( W , W ′ ) { x , y . M [ γ ] } ↦ S M [ γ ] [ W / x , W ′ / y ] , \operatorname{case}_{\times}(W,W')\{x,y.\ M[\gamma]\} \mapsto_S M[\gamma][W/x,W'/y], case × ( W , W ′ ) { x , y . M [ γ ]} ↦ S M [ γ ] [ W / x , W ′ / y ] ,
and G [ Γ , x : A , y : A ′ ] ( γ , W , W ′ ) G[\Gamma, x : A, y : A'](\gamma,W,W') G [ Γ , x : A , y : A ′ ] ( γ , W , W ′ ) gives C [ B ] C[B] C [ B ] of the reduct. Anti-reduction finishes the case.
Return. The first rule of C [ F A ] C[FA] C [ F A ] in Figure 6 .
Bind. Let S : = x ← ∙ ; N [ γ ] S := x \leftarrow\mathord{\bullet};\ N[\gamma] S := x ← ∙ ; N [ γ ] . The hypothesis on M M M gives C [ F A ] ( M [ γ ] ) C[FA](M[\gamma]) C [ F A ] ( M [ γ ]) , and we show C [ B ] ( S [ M ′ ] ) C[B](S[M']) C [ B ] ( S [ M ′ ]) for every M ′ M' M ′ with C [ F A ] ( M ′ ) C[FA](M') C [ F A ] ( M ′ ) , by induction on the proof of C [ F A ] ( M ′ ) C[FA](M') C [ F A ] ( M ′ ) .
(M ′ = ret V M' = \operatorname{ret} V M ′ = ret V with V [ A ] ( V ) V[A](V) V [ A ] ( V ) ) Then S [ ret V ] ↦ S N [ γ ] [ V / x ] S[\operatorname{ret} V] \mapsto_S N[\gamma][V/x] S [ ret V ] ↦ S N [ γ ] [ V / x ] , and G [ Γ , x : A ] ( γ , V ) G[\Gamma, x : A](\gamma,V) G [ Γ , x : A ] ( γ , V ) gives C [ B ] ( N [ γ ] [ V / x ] ) C[B](N[\gamma][V/x]) C [ B ] ( N [ γ ] [ V / x ]) . Anti-reduction finishes the case.
(M ′ = op ( M → ) M' = \operatorname{op}(\overrightarrow{M}) M ′ = op ( M ) with C [ F A ] ( M i ) C[FA](M_i) C [ F A ] ( M i ) for each i i i ) The frame rule gives S [ op ( M → ) ] ↦ S op ( S [ M → ] ) S[\operatorname{op}(\overrightarrow{M})] \mapsto_S \operatorname{op}(S[\overrightarrow{M}]) S [ op ( M )] ↦ S op ( S [ M ]) . The inductive hypothesis gives C [ B ] ( S [ M i ] ) C[B](S[M_i]) C [ B ] ( S [ M i ]) for each i i i , so the congruence lemma for computation logical predicates gives C [ B ] ( op ( S [ M → ] ) ) C[B](\operatorname{op}(S[\overrightarrow{M}])) C [ B ] ( op ( S [ M ])) . Anti-reduction finishes the case.
( M ′ ↦ S M ′ ′ ) (M' \mapsto_S M'') ( M ′ ↦ S M ′′ ) with C [ F A ] ( M ′ ′ ) C[FA](M'') C [ F A ] ( M ′′ ) . Since ↦ S \mapsto_S ↦ S is closed under stacks, S [ M ′ ] ↦ S S [ M ′ ′ ] S[M'] \mapsto_S S[M''] S [ M ′ ] ↦ S S [ M ′′ ] . The inductive hypothesis gives C [ B ] ( S [ M ′ ′ ] ) C[B](S[M'']) C [ B ] ( S [ M ′′ ]) , and anti-reduction finishes the case.
Operation. Each C [ B ] ( M i [ γ ] ) C[B](M_i[\gamma]) C [ B ] ( M i [ γ ]) holds, so the congruence lemma for computation logical predicates gives C [ B ] ( op ( M [ γ ] ‾ ) ) C[B](\operatorname{op}(\overline{M[\gamma]})) C [ B ] ( op ( M [ γ ] )) .
Empty tuple. C [ ⊤ ] ( ⟨ ⟩ ) C[\top](\langle\rangle) C [ ⊤ ] (⟨ ⟩) holds, since C [ ⊤ ] C[\top] C [ ⊤ ] holds of every computation.
Abstraction. Given V [ A ] ( V ) V[A](V) V [ A ] ( V ) , we have ( λ x : A . M [ γ ] ) V ↦ S M [ γ ] [ V / x ] (\lambda x : A.\ M[\gamma])\ V \mapsto_S M[\gamma][V/x] ( λ x : A . M [ γ ]) V ↦ S M [ γ ] [ V / x ] , and G [ Γ , x : A ] ( γ , V ) G[\Gamma,x : A](\gamma,V) G [ Γ , x : A ] ( γ , V ) gives C [ B ] ( M [ γ ] [ V / x ] ) C[B](M[\gamma][V/x]) C [ B ] ( M [ γ ] [ V / x ]) . Anti-reduction finishes the case.
Application. The hypothesis on M M M , applied to V [ γ ] V[\gamma] V [ γ ] , which satisfies V [ A ] V[A] V [ A ] by the hypothesis on V V V .
Pairing. By definition of C [ B 1 & B 2 ] C[B_1 \mathbin{\&} B_2] C [ B 1 & B 2 ] , we need C [ B i ] ( π i ⟨ M 1 [ γ ] , M 2 [ γ ] ⟩ ) C[B_i](\pi_i\langle M_1[\gamma],M_2[\gamma]\rangle) C [ B i ] ( π i ⟨ M 1 [ γ ] , M 2 [ γ ]⟩) for each i i i . Since
π i ⟨ M 1 [ γ ] , M 2 [ γ ] ⟩ ↦ S M i [ γ ] , \pi_i\langle M_1[\gamma],M_2[\gamma]\rangle\mapsto_S M_i[\gamma], π i ⟨ M 1 [ γ ] , M 2 [ γ ]⟩ ↦ S M i [ γ ] ,
anti-reduction gives it from the hypothesis on M i M_i M i .
Projection. C [ B i ] ( π i M [ γ ] ) C[B_i](\pi_i M[\gamma]) C [ B i ] ( π i M [ γ ]) is a conjunct of C [ B 1 & B 2 ] ( M [ γ ] ) C[B_1 \mathbin{\&} B_2](M[\gamma]) C [ B 1 & B 2 ] ( M [ γ ]) .
Proof of Soundness of Configuration Reduction
We prove Theorem 5.12 by cases on the rule.
Pure. This follows from the soundness of tree reduction (Theorem 4.2 ).
Effect. By the Effect rule the redex is C [ S [ op ( M ‾ ) ] ] C[S[\operatorname{op}(\overline{M})]] C [ S [ op ( M )]] for some C : ∂ T ( Comp ( F A ) ) C : \partial_T(\operatorname{Comp}(FA)) C : ∂ T ( Comp ( F A )) , and the reduct is μ ( ∂ T ( η ) ( C ) ) [ ⟦ op ⟧ ( η ( S [ M ] ) ‾ ) ] \mu(\partial_T(\eta)(C))[\llbracket\operatorname{op}\rrbracket(\overline{\eta(S[M])})] μ ( ∂ T ( η ) ( C )) [ [ [ op ] ] ( η ( S [ M ]) )] . Write f † = μ ∘ T ( f ) f^\dagger= \mu\circ T(f) f † = μ ∘ T ( f ) for the Kleisli extension of f : X → T ( Y ) f : X \to T(Y) f : X → T ( Y ) , so that ⟦ _ ⟧ T = ⟦ _ ⟧ c † \llbracket\_\rrbracket_T = \llbracket\_\rrbracket_c^\dagger [ [ _ ] ] T = [ [ _ ] ] c † . We use four facts.
(A) f † ∘ η = f f^\dagger\circ\eta= f f † ∘ η = f (naturality of η \eta η and the unit law).
(B) f † ∘ μ = μ ∘ T ( f † ) f^\dagger\circ\mu= \mu\circ T(f^\dagger) f † ∘ μ = μ ∘ T ( f † ) (naturality of μ \mu μ and associativity).
(C) Plugging is natural, T ( f ) ( C [ x ] ) = ∂ T ( f ) ( C ) [ f ( x ) ] T(f)(C[x]) = \partial_T(f)(C)[f(x)] T ( f ) ( C [ x ]) = ∂ T ( f ) ( C ) [ f ( x )] (§ 5.3 ).
(D) f † f^\dagger f † is a homomorphism, being the unique homomorphism extending f f f (§ 2.1 ), so it commutes with ⟦ op ⟧ \llbracket\operatorname{op}\rrbracket [ [ op ] ] .
For the left-hand side, (C) gives
⟦ C [ S [ op ( M ‾ ) ] ] ⟧ T = μ ( T ( ⟦ _ ⟧ c ) ( C [ S [ op ( M ‾ ) ] ] ) ) = μ ( ∂ T ( ⟦ _ ⟧ c ) ( C ) [ ⟦ S [ op ( M ‾ ) ] ⟧ c ] ) . \llbracket C[S[\operatorname{op}(\overline{M})]]\rrbracket_T
= \mu(T(\llbracket\_\rrbracket_c)(C[S[\operatorname{op}(\overline{M})]]))
= \mu(\partial_T(\llbracket\_\rrbracket_c)(C)[\llbracket S[\operatorname{op}(\overline{M})]\rrbracket_c]). [ [ C [ S [ op ( M )]] ] ] T = μ ( T ( [ [ _ ] ] c ) ( C [ S [ op ( M )]])) = μ ( ∂ T ( [ [ _ ] ] c ) ( C ) [ [ [ S [ op ( M )] ] ] c ]) .
For the right-hand side,
⟦ μ ( ∂ T ( η ) ( C ) [ ⟦ op ⟧ ( η ( S [ M ] ) ‾ ) ] ) ⟧ T = μ ( T ( ⟦ _ ⟧ T ) ( ∂ T ( η ) ( C ) [ ⟦ op ⟧ ( η ( S [ M ] ) ‾ ) ] ) ) (B) = μ ( ∂ T ( ⟦ _ ⟧ c ∘ η ) ( C ) [ ⟦ _ ⟧ T ( ⟦ op ⟧ ( η ( S [ M ] ) ‾ ) ) ] ) (C) = μ ( ∂ T ( ⟦ _ ⟧ c ) ( C ) [ ⟦ op ⟧ ( ⟦ _ ⟧ c † ( η ( S [ M ] ) ) ‾ ) ] ) (A), (D) = μ ( ∂ T ( ⟦ _ ⟧ c ) ( C ) [ ⟦ op ⟧ ( ⟦ S [ M ] ⟧ c ‾ ) ] ) . \begin{aligned}
\llbracket\mu(\partial_T(\eta)(C)[\llbracket\operatorname{op}\rrbracket(\overline{\eta(S[M])})])\rrbracket_T
&= \mu(T(\llbracket\_\rrbracket_T)(\partial_T(\eta)(C)[\llbracket\operatorname{op}\rrbracket(\overline{\eta(S[M])})])) \quad\text{(B)}\\
&= \mu(\partial_T(\llbracket\_\rrbracket_c \circ\eta)(C)[\llbracket\_\rrbracket_T(\llbracket\operatorname{op}\rrbracket(\overline{\eta(S[M])}))]) \quad\text{(C)}\\
&= \mu(\partial_T(\llbracket\_\rrbracket_c)(C)[\llbracket\operatorname{op}\rrbracket(\overline{\llbracket\_\rrbracket_c^\dagger(\eta(S[M]))})]) \quad\text{(A), (D)}\\
&= \mu(\partial_T(\llbracket\_\rrbracket_c)(C)[\llbracket\operatorname{op}\rrbracket(\overline{\llbracket S[M]\rrbracket_c})]).
\end{aligned} [ [ μ ( ∂ T ( η ) ( C ) [ [ [ op ] ] ( η ( S [ M ]) )]) ] ] T = μ ( T ( [ [ _ ] ] T ) ( ∂ T ( η ) ( C ) [ [ [ op ] ] ( η ( S [ M ]) )])) (B) = μ ( ∂ T ( [ [ _ ] ] c ∘ η ) ( C ) [ [ [ _ ] ] T ( [ [ op ] ] ( η ( S [ M ]) ))]) (C) = μ ( ∂ T ( [ [ _ ] ] c ) ( C ) [ [ [ op ] ] ( [ [ _ ] ] c † ( η ( S [ M ])) )]) (A), (D) = μ ( ∂ T ( [ [ _ ] ] c ) ( C ) [ [ [ op ] ] ( [ [ S [ M ] ] ] c )]) .
The two sides differ only in the plugged value, so it suffices that
⟦ S [ op ( M ‾ ) ] ⟧ c = ⟦ op ⟧ ( ⟦ S [ M ] ⟧ c ‾ ) . \llbracket S[\operatorname{op}(\overline{M})]\rrbracket_c
= \llbracket\operatorname{op}\rrbracket(\overline{\llbracket S[M]\rrbracket_c}). [ [ S [ op ( M )] ] ] c = [ [ op ] ] ( [ [ S [ M ] ] ] c ) .
This holds because stacks are interpreted as homomorphisms (Figure 3 ), so
⟦ S [ op ( M ‾ ) ] ⟧ c = ⟦ S ⟧ ( ⟦ op ⟧ ( ⟦ M ⟧ ‾ ) ) = ⟦ op ⟧ ( ⟦ S ⟧ ( ⟦ M ⟧ ) ‾ ) = ⟦ op ⟧ ( ⟦ S [ M ] ⟧ c ‾ ) . \llbracket S[\operatorname{op}(\overline{M})]\rrbracket_c
= \llbracket S\rrbracket(\llbracket\operatorname{op}\rrbracket(\overline{\llbracket M\rrbracket}))
= \llbracket\operatorname{op}\rrbracket(\overline{\llbracket S\rrbracket(\llbracket M\rrbracket)})
= \llbracket\operatorname{op}\rrbracket(\overline{\llbracket S[M]\rrbracket_c}). [ [ S [ op ( M )] ] ] c = [ [ S ] ] ( [ [ op ] ] ( [ [ M ] ] )) = [ [ op ] ] ( [ [ S ] ] ( [ [ M ] ] ) ) = [ [ op ] ] ( [ [ S [ M ] ] ] c ) .
Type Structure of the CBPV+ Doctrine
Section § 3.1 gives type structure by universal properties and works out value products. Table 1 lists the universal property of every connective of the unary calculus. The function type needs contexts with more than one variable and is omitted, as in § 3.1 . The two isomorphisms for + + + are compatible with substitution, M [ case + ( z ) { x . W 1 ∣ y . W 2 } / w ] = case + ( z ) { x . M [ W 1 / w ] ∣ y . M [ W 2 / w ] } M[\operatorname{case}_{+}(z)\{x.W_{1}\mid y.W_{2}\}/w]=\operatorname{case}_{+}(z)\{x.M[W_{1}/w]\mid y.M[W_{2}/w]\} M [ case + ( z ) { x . W 1 ∣ y . W 2 } / w ] = case + ( z ) { x . M [ W 1 / w ] ∣ y . M [ W 2 / w ]} , and the two for & \mathbin{\&} & with plugging, ⟨ S 1 , S 2 ⟩ [ M ] = ⟨ S 1 [ M ] , S 2 [ M ] ⟩ \langle S_{1},S_{2}\rangle[M]=\langle S_{1}[M],S_{2}[M]\rangle ⟨ S 1 , S 2 ⟩ [ M ] = ⟨ S 1 [ M ] , S 2 [ M ]⟩ .
Table 1. Universal properties of the connectives in a unary CBPV+ doctrine.