betaFeedback

WorksComputer Science

An Algebraic Perspective on Operational Semantics

Abstract

Languages with effects are typically given two independently specified semantic accounts: a denotational semantics based on (free) models, and an operational semantics defined by effect-specific reduction rules. This separation leads to two independently constructed semantic structures whose relationship must then be established a posteriori. We present a unified construction in which both denotational interpretation and operational reduction are constructed from an algebraic theory specifying the effects. We work with call-by-push-value extended by the operations of an algebraic theory. We prove equational canonicity and give a tree-based operational semantics that reduces every closed computation to a tree of operations. When the free model monad is a monadic container, we derive from it a configuration-based small-step semantics. Configurations are elements of the free model. Every step preserves the denotation. Under a condition we call affinity, every reduction terminates and at ground types computes the denotation. We instantiate the framework with state, errors, writer, and weighted and pre-convex probabilistic choice. For errors, writer and weighted choice we recover the familiar rules. For state we get a machine that runs the program from every initial state at once.

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}) and to lift it to T(Term⁡)T(\operatorname{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) we first take the denotations ⟦M⟧,…\llbracket M\rrbracket,\ldots 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), the operation can be interpreted right away, before any of its operands has run. The operands M,…M,\ldots become new subterms of the configuration, to be run later. For example, with writer effects a configuration ⟨m,N⟩\langle m,N\rangle pairs the log mm with a term NN. The step ⟨m,tell⁡n(N)⟩↦⟨m⊗n,N⟩\langle m,\operatorname{tell}_{n}(N)\rangle\mapsto\langle m\otimes n,N\rangle records nn before NN runs. Take M=tell⁡a(tell⁡b(ret⁡ x))M=\operatorname{tell}_{a}(\operatorname{tell}_{b}(\operatorname{ret}\ x)) and the empty log ee. The denotation adds bb to the log first but the machine adds aa 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}

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 FAFA 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 XX to the free model of the theory on XX, 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=(Σ,Eqns)\mathcal{T} = (\Sigma, \mathsf{Eqns}), consisting of a signature Σ\Sigma and a set of equations Eqns\mathsf{Eqns}. A signature Σ=(Ops,ar)\Sigma= (\mathsf{Ops}, \mathsf{ar}) specifies a set of operation Ops\mathsf{Ops} and for each operation op:Ops\mathsf{op} : \mathsf{Ops}, an arity ar(op):N\mathsf{ar}(\mathsf{op}) : \mathbb{N}. Given a signature Σ\Sigma, the set of terms generated by the signature with variables of type XX is inductively defined by:

x:Xvar x:TermΣ(X)op:Ops∀i. ti:TermΣ(X)op(t1,t2,…,tar(op)):TermΣ(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)}

which we denote as TermΣ(X)\mathsf{Term}_{\Sigma}(X). An equation consists of a context size ctx:N\mathsf{ctx} : \mathbb{N} with two terms lhs,rhs:TermΣ(ctx)\mathsf{lhs},\mathsf{rhs} : \mathsf{Term}_{\Sigma}(\mathsf{ctx}) where ctx\mathsf{ctx} is interpreted as a finite set of cardinality ctx\mathsf{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), where ee denotes the empty output and ⊗\otimes combines the outputs produced by successive computations. For a given monoid, we define the theory Twriter\mathcal{T}_{\mathrm{writer}} to consist of a signature Σwriter\Sigma_{\mathrm{writer}} with one unary operation tell⁡m(t)\operatorname{tell}_{m}(t) for every m:Mm : M. The equations of this theory are:

tell⁡e(t)=ttell⁡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)

Example 2.2 (Theory of Errors). The theory of errors models computations that may abort [36 Ex. 1]. We define the theory Terr\mathcal{T}_{\mathrm{err}} to consist of a signature Σerr\Sigma_{\mathrm{err}} with a single nullary operation err⁡\operatorname{err}, and no equations.

Example 2.3 (Theory of Finite State). The theory Tstate\mathcal{T}_{\mathrm{state}} of state for a finite set of states SS consists of a signature ΣS\Sigma_{S} with unary operations set⁡s(t)\operatorname{set}_{s}(t) for all s:Ss : S and a single operation get⁡(t→)\operatorname{get}(\overrightarrow{t}) of arity ∣S∣|S|. The equations of Tstate\mathcal{T}_{\mathrm{state}} [36 §3] consist of the usual lens laws, for all s,s′:Ss, s' : S:

get⁡(set⁡s(t)→)=tset⁡s(get⁡(t→))=set⁡s(ts)set⁡s(set⁡s′(t))=set⁡s′(t)get⁡(get⁡(t→s))=get⁡(t→ss′)\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'})

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,⋅,1R)(R, \mathord{\cdot}, 1_{R}) be a multiplicative monoid of weights. We define the theory Twmon\mathcal{T}_{\mathrm{wmon}} to consist of a signature Σwmon\Sigma_{\mathrm{wmon}} with a nullary operation ee, a binary operation ⊗\otimes, and one unary operation act⁡r\operatorname{act}_{r} for each r:Rr : R. The equations of this theory are given below.

t⊗(t′⊗t′′)=(t⊗t′)⊗t′′e⊗t=tt⊗e=tact⁡1R(t)=tact⁡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}

Equivalently, a weighted monoid is a monoid (M,⊗,e)(M, \otimes, e) with an action of the multiplicative monoid (R,⋅,1R)(R, \mathord{\cdot}, 1_{R}) by monoid homomorphisms. That is, act⁡1\operatorname{act}_{1} is the identity, act⁡r∘act⁡r′=act⁡r⋅r′\operatorname{act}_{r} \circ\operatorname{act}_{r'} = \operatorname{act}_{r\cdot r'}, and each act⁡r\operatorname{act}_{r} preserves ⊗\otimes and ee. This makes the theory of weighted monoids the tensor of the theory of monoids with the theory of writer for (R,⋅,1R)(R, \mathord{\cdot}, 1_{R}) [23]. Its free model is the writer monad transformer for (R,⋅,1R)(R, \mathord{\cdot}, 1_{R}) applied to the list monad, List⁡(R×X)\operatorname{List}(R \times X) [23 Thm. 12].

Example 2.5 (Theory of RR-Semimodules). The theory of RR-semimodules [19 Ch. 14] models computations that can be combined into formal linear combinations. Here the semiring RR 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) be a semiring. We define the theory TR-Semi\mathcal{T}_{R\text{-}\mathrm{Semi}} to consist of a signature ΣR-Semi\Sigma_{R\text{-}\mathrm{Semi}} with:

  • a constant 00,

  • a binary operation ++,

  • for each r∈Rr \in R, a unary operation scale⁡r(−)\operatorname{scale}_{r}(-).

Intuitively, ++ and scale⁡r\operatorname{scale}_{r} together form linear combinations of computations. ++ adds two computations, 00 represents the empty combination, and scale⁡r(t)\operatorname{scale}_{r}(t) scales the computation tt by the coefficient

rr. The equations of TR\mathcal{T}_{R}-Semi are:

References

  1. [1]Michael Abbott, Thorsten Altenkirch, and Neil Ghani. 2005. Containers: Constructing strictly positive types. Theoretical Computer Science 342, 1 (2005), 3–27. Applied Semantics: Selected Topics. doi:10.1016/j.tcs.2005.06.002DOI
  2. [2]Michael Abbott, Thorsten Altenkirch, Neil Ghani, and Conor McBride. 2003. Derivatives of Containers. In Typed Lambda Calculi and Applications (TLCA 2003) (LNCS, Vol. 2710). Springer, 16–30. doi:10.1007/3-540-44904-3_2DOI
  3. [3]Faris Abou-Saleh and Dirk Pattinson. 2013. Models and Effects in Mathematical Operational Semantics. In Foundations of Software Science and Computation Structures (FoSSaCS 2013) (LNCS, Vol. 7794). 129–144. doi:10.1007/978-3-642-37075-5_9
  4. [4]Daniel Ahman and Andrej Bauer. 2020. Runners in Action. In Programming Languages and Systems (ESOP 2020) (LNCS, Vol. 12075). Springer, 29–55. doi:10.1007/978-3-030-44914-8_2DOI
  5. [5]Thorsten Altenkirch and Gun Pinyo. 2017. Monadic Containers and Universes (abstract). In Abstracts of TYPES 2017. 20–21.
  6. [6]Pedro H. Azevedo de Amorim, Satoshi Kura, and Philip Saville. 2025. Logical relations for call-by-push-value models, via internal fibrations in a 2-category . In 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society, Los Alamitos, CA, USA, 732–747. doi:10.1109/LICS65433.2025.00061
  7. [7]Andrej Bauer and Matija Pretnar. 2014. An Effect System for Algebraic Effects and Handlers. Logical Methods in Computer Science 10, 4 (2014). doi:10.2168/LMCS-10(4:9)2014DOI
  8. [8]Pierre-Louis Curien, Marcelo Fiore, and Guillaume Munch-Maccagnoni. 2016. A theory of effects and resources: adjunction models and polarised calculi. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (St. Petersburg, FL, USA) (POPL ’16). Association for Computing Machinery, New York, NY, USA, 44–56. doi:10.1145/2837614.2837652DOI
  9. [9]Francesco Dagnino, Paola Giannini, and Elena Zucca. 2025. Monadic Type-And-Effect Soundness. In 39th European Conference on Object-Oriented Programming (ECOOP 2025) (LIPIcs), 7:1–7:31. doi:10.4230/LIPIcs.ECOOP.2025.7DOI
  10. [10]Nachum Dershowitz and Zohar Manna. 1979. Proving Termination with Multiset Orderings. Commun. ACM 22, 8 (1979), 465–476. doi:10.1145/359138.359142DOI
  11. [12]Marcelo Fiore. 2012. Discrete generalised polynomial functors. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming - Volume Part II (Warwick, UK) (ICALP’12). Springer-Verlag, Berlin, Heidelberg, 214–226. doi:10.1007/978-3-642-31585-5_22DOI
  12. [13]Marcelo Fiore and Chung-Kil Hur. 2009. On the construction of free algebras for equational systems. Theoretical Computer Science 410, 18 (2009), 1704–1729. Automata, Languages and Programming (ICALP 2007). doi:10.1016/j.tcs.2008.12.052DOI
  13. [14]Tobias Fritz. 2009. Convex Spaces I: Definition and Examples. arXiv:0903.5522.arxiv.org/abs/0903.5522
  14. [15]Dan Frumin, Amin Timany, and Lars Birkedal. 2024. Modular Denotational Semantics for Effects with Guarded Interaction Trees. Proc. ACM Program. Lang. 8, POPL, Article 12 (Jan. 2024), 30 pages. doi:10.1145/3632854
  15. [16]Nicola Gambino and Joachim Kock. 2013. Polynomial functors and polynomial monads. Mathematical Proceedings of the Cambridge Philosophical Society 154, 1 (2013), 153–192. doi:10.1017/S0305004112000394DOI
  16. [17]Francesco Gavazzo and Claudia Faggian. 2021. A Relational Theory of Monadic Rewriting Systems, Part I. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021). 1–14. doi:10.1109/LICS52264.2021.9470633DOI
  17. [18]Francesco Gavazzo, Riccardo Treglia, and Gabriele Vanoni. 2024. Monadic Intersection Types, Relationally. In Programming Languages and Systems (ESOP 2024) (LNCS). 52–51. doi:10.1007/978-3-031-57262-3_2
  18. [19]Jonathan S. Golan. 1999. Semirings and their Applications. Kluwer Academic Publishers, Dordrecht. doi:10.1007/978-94-015-9333-5DOI
  19. [20]Sergey Goncharov, Stefan Milius, Lutz Schröder, Stelios Tsampas, and Henning Urbat. 2023. Towards a Higher-Order Mathematical Operational Semantics. Proc. ACM Program. Lang. 7, POPL, Article 22 (Jan. 2023), 27 pages. doi:10.1145/3571215DOI
  20. [21]Sergey Goncharov, Stefan Milius, Lutz Schröder, Stelios Tsampas, and Henning Urbat. 2025. Bialgebraic Reasoning on Stateful Languages. Proc. ACM Program. Lang. 9, ICFP, Article 244 (Aug. 2025), 30 pages. doi:10.1145/3747513DOI
  21. [22]Sergey Goncharov, Stelios Tsampas, and Henning Urbat. 2025. Abstract Operational Methods for Call-by-Push-Value. Proc. ACM Program. Lang. 9, POPL, Article 35 (Jan. 2025), 27 pages. doi:10.1145/3704871DOI
  22. [23]Martin Hyland, Gordon Plotkin, and John Power. 2006. Combining effects: Sum and tensor. Theoretical Computer Science 357, 1 (2006), 70–99. Clifford Lectures and the Mathematical Foundations of Programming Semantics. doi:10.1016/j.tcs.2006.03.013DOI
  23. [24]Bart Jacobs. 2016. Affine Monads and Side-Effect-Freeness. In Coalgebraic Methods in Computer Science (CMCS 2016) (LNCS, Vol. 9608). Springer, 53–72. doi:10.1007/978-3-319-40370-0_5DOI
  24. [25]Patricia Johann, Alex Simpson, and Janis Voigtländer. 2010. A Generic Operational Metatheory for Algebraic Effects. In 2010 25th Annual IEEE Symposium on Logic in Computer Science. 209–218. doi:10.1109/LICS.2010.29DOI
  25. [26]Ohad Kammar, Sam Lindley, and Nicolas Oury. 2013. Handlers in Action. In Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming (ICFP 2013). ACM, 145–158. doi:10.1145/2500365.2500590DOI
  26. [27]Ohad Kammar and Dylan McDermott. 2018. Factorisation Systems for Logical Relations and Monadic Lifting in Type-and-effect System Semantics. Electronic Notes in Theoretical Computer Science 341 (2018), 239–260. doi:10.1016/j.entcs.2018.11.012DOI
  27. [28]G. A. Kavvos. 2025. Adequacy for Algebraic Effects Revisited. Proc. ACM Program. Lang. 9, OOPSLA1, Article 113 (April 2025), 29 pages. doi:10.1145/3720457DOI
  28. [29]Joachim Kock. 2012. Data Types with Symmetries and Polynomial Functors over Groupoids. Electronic Notes in Theoretical Computer Science 286 (2012), 351–365. doi:10.1016/j.entcs.2013.01.001DOI
  29. [30]F. William Lawvere. 1963. FUNCTIONAL SEMANTICS OF ALGEBRAIC THEORIES. Proceedings of the National Academy of Sciences 50, 5 (1963), 869–872. arXiv:https://www.pnas.org/doi/pdf/10.1073/pnas.50.5.869 doi:10.1073/pnas.50.5.869DOI
  30. [31]Paul Blain Levy. 2003. Adjunction Models For Call-By-Push-Value With Stacks. Electronic Notes in Theoretical Computer Science 69 (2003), 248–271. CTCS’02, Category Theory and Computer Science. doi:10.1016/S1571-0661(04)80568-1DOI
  31. [32]Conor McDowell. 2001. The Derivative of a Regular Type is Type of One-Hole Contexts. (2001). Unpublished manuscript. http://strictlypositive.org/diff.pdf
  32. [33]E. Moggi. 1989. Computational lambda-calculus and monads. In [1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science. 14–23. doi:10.1109/LICS.1989.39155
  33. [34]H. Nakano. 2000. A modality for recursion. In Proceedings Fifteenth Annual IEEE Symposium on Logic in Computer Science (Cat. No.99CB36332). 255–266. doi:10.1109/LICS.2000.855774
  34. [35]Gordon Plotkin. 2009. Graded Adequacy for Infinitary Algebraic Effects (Abstract). In Algebra and Coalgebra in Computer Science (CALCO 2009) (LNCS, Vol. 5728). 1–2. doi:10.1007/978-3-642-03741-2_1DOI
  35. [36]Gordon Plotkin and John Power. 2002. Notions of Computation Determine Monads. In Foundations of Software Science and Computation Structures, Mogens Nielsen and Uffe Engberg (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 342–356.DOI
  36. [37]Gordon Plotkin and John Power. 2003. Algebraic Operations and Generic Effects. Applied Categorical Structures 11, 1 (2003), 69–94. doi:10.1023/A:1023064908962DOI
  37. [38]Gordon Plotkin and John Power. 2008. Tensors of Comodels and Models for Operational Semantics. Electronic Notes in Theoretical Computer Science 218 (2008), 295–311. Proceedings of MFPS XXIV. doi:10.1016/j.entcs.2008.10.018DOI
  38. [39]Gordon D. Plotkin. 2004. A Structural Approach to Operational Semantics. Journal of Logic and Algebraic Programming 60–61 (2004), 17–139. Originally Technical Report DAIMI FN-19, Aarhus University, 1981. doi:10.1016/j.jlap.2004.05.001DOI
  39. [40]Gordon D. Plotkin. 2001. Adequacy for Algebraic Effects. Foundations of Software Science and Computation Structures (FoSSaCS 2001) (LNCS, Vol. 2030). Springer, 1–24. doi:10.1007/3-540-45315-6_1DOI
  40. [41]Matija Pretnar. 2015. An Introduction to Algebraic Effects and Handlers. Electronic Notes in Theoretical Computer Science 319 (2015), 19–35. doi:10.1016/j.entcs.2015.12.003DOI
  41. [42]Chris Purdy and Stefania Damato. 2025. Distributive Laws of Monadic Containers. In 11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025) (LIPIcs, Vol. 342). 4:1–4:22. doi:10.4230/LIPIcs.CALCO.2025.4
  42. [43]Sam Staton. 2010. Completeness for Algebraic Theories of Local State. In Foundations of Software Science and Computational Structures (FoSSaCS 2010) (LNCS, Vol. 6014). Springer, 48–63. doi:10.1007/978-3-642-12032-9_5DOI
  43. [44]Sam Staton. 2013. Instances of Computational Effects: An Algebraic Perspective. In 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE, 519–528. doi:10.1109/LICS.2013.58DOI
  44. [45]Marshall H. Stone. 1949. Postulates for the Barycentric Calculus. Annali di Matematica Pura ed Applicata 29, 1 (1949), 25–30. doi:10.1007/BF02413910DOI
  45. [46]D. Turi and G. Plotkin. 1997. Towards a mathematical operational semantics. In Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science. 280–291. doi:10.1109/LICS.1997.614955
  46. [47]Tarmo Uustalu. 2015. Stateful Runners of Effectful Computations. Electronic Notes in Theoretical Computer Science 319 (2015), 403–421. Proceedings of MFPS XXXI. doi:10.1016/j.entcs.2015.12.024DOI
  47. [48]Tarmo Uustalu. 2017. Container Combinatorics: Monads and Lax Monoidal Functors. In Topics in Theoretical Computer Science (TTCS 2017) (LNCS, Vol. 10608). Springer, 91–105. doi:10.1007/978-3-319-68953-1_8DOI

Paper details

vlnc:W_uvvstkeb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

an LLM-based coding assistant

View statement
Looking for related papers…
Contents