Maciej Piróg
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Maciej Piróg has a total of 21 co-authors. Here are the top co-authors by number of shared publications:
Filip Sieczkowski
University of Wrocław, Poland
4 shared publications- Piotr Polesiuk
University of Wrocław
4 shared publications - Tom Schrijvers
Department of Computer Science, KU Leuven, Leuven, Belgium
4 shared publications Dariusz Biernacki
University of Wrocław, Poland
3 shared publicationsJeremy Gibbons
3 shared publications- Alexander Vandenbroucke
KU Leuven, Belgium
2 shared publications
Latest Publications
- Open Access
- 20 December 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Electronic Notes in Theoretical Informatics and Computer Science
- Vol. ume 5 - Pr
Strong Dinatural Transformations and Generalised Codensity Monads
We introduce dicodensity monads: a generalisation of pointwise codensity monads generated by functors to monads generated by mixed-variant bifunctors. Our construction is based on the notion of strong dinaturality (also known as Barr dinaturality), and is inspired by denotational models of certain types in polymorphic lambda calculi - in particular, a form of continuation monads with universally quantified variables, such as the Church encoding of the list monad in System F. Extending some previous results on Cayley-style representations, we provide a set of sufficient conditions to establish an isomorphism between a monad and the dicodensity monad for a given bifunctor. Then, we focus on the class of monads obtained by instantiating our construction with hom-functors and, more generally, bifunctors given by objects of homomorphisms (that is, internalised hom-sets between Eilenberg--Moore algebras). This gives us, for example, novel presentations of monads generated by different kinds of semirings and other theories used to model ordered nondeterministic computations. 15 pages
- 20 December 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Electronic Notes in Theoretical Informatics and Computer Science
- Vol. ume 5 - Pr
Open AccessStrong Dinatural Transformations and Generalised Codensity Monads
We introduce dicodensity monads: a generalisation of pointwise codensity monads generated by functors to monads generated by mixed-variant bifunctors. Our construction is based on the notion of strong dinaturality (also known as Barr dinaturality), and is inspired by denotational models of certain types in polymorphic lambda calculi - in particular, a form of continuation monads with universally quantified variables, such as the Church encoding of the list monad in System F. Extending some previous results on Cayley-style representations, we provide a set of sufficient conditions to establish an isomorphism between a monad and the dicodensity monad for a given bifunctor. Then, we focus on the class of monads obtained by instantiating our construction with hom-functors and, more generally, bifunctors given by objects of homomorphisms (that is, internalised hom-sets between Eilenberg--Moore algebras). This gives us, for example, novel presentations of monads generated by different kinds of semirings and other theories used to model ordered nondeterministic computations. 15 pages
- Open Access
- 31 October 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (OOPSLA2) , 1639-1667
High-level effect handlers in C++
Effect handlers allow the programmer to implement computational effects, such as custom error handling, various forms of lightweight concurrency, and dynamic binding, inside the programming language. We introduce cpp-effects, a C++ library for effect handlers with a typed high-level, object-oriented interface. We demonstrate that effect handlers can be successfully applied in imperative systems programming languages with manual memory management. Through a collection of examples, we explore how to program effectively with effect handlers in C++, discuss the intricacies and challenges of the implementation, and show that despite its limitations, cpp-effects performance is competitive and in some cases even outperforms state-of-the-art approaches such as C++20 coroutines and the libmprompt library for multiprompt delimited control.
- 31 October 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (OOPSLA2) , 1639-1667
Open AccessHigh-level effect handlers in C++
Effect handlers allow the programmer to implement computational effects, such as custom error handling, various forms of lightweight concurrency, and dynamic binding, inside the programming language. We introduce cpp-effects, a C++ library for effect handlers with a typed high-level, object-oriented interface. We demonstrate that effect handlers can be successfully applied in imperative systems programming languages with manual memory management. Through a collection of examples, we explore how to program effectively with effect handlers in C++, discuss the intricacies and challenges of the implementation, and show that despite its limitations, cpp-effects performance is competitive and in some cases even outperforms state-of-the-art approaches such as C++20 coroutines and the libmprompt library for multiprompt delimited control.
- Open Access
- 20 December 2019
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 4 (POPL) , 1-29
Binders by day, labels by night: effect instances via lexically scoped handlers
Handlers of algebraic effects aspire to be a practical and robust programming construct that allows one to define, use, and combine different computational effects. Interestingly, a critical problem that still bars the way to their popular adoption is how to combine different uses of the same effect in a program, particularly in a language with a static type-and-effect system. For example, it is rudimentary to define the “mutable memory cell” effect as a pair of operations, put and get , together with a handler, but it is far from obvious how to use this effect a number of times to operate a number of memory cells in a single context. In this paper, we propose a solution based on lexically scoped effects in which each use (an “instance”) of an effect can be singled out by name, bound by an enclosing handler and tracked in the type of the expression. Such a setting proves to be delicate with respect to the choice of semantics, as it depends on the explosive mixture of effects, polymorphism, and reduction under binders. Hence, we devise a novel approach to Kripke-style logical relations that can deal with open terms, which allows us to prove the desired properties of our calculus. We formalise our core results in Coq, and introduce an experimental surface-level programming language to show that our approach is applicable in practice.
- 20 December 2019
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 4 (POPL) , 1-29
Open AccessBinders by day, labels by night: effect instances via lexically scoped handlers
Handlers of algebraic effects aspire to be a practical and robust programming construct that allows one to define, use, and combine different computational effects. Interestingly, a critical problem that still bars the way to their popular adoption is how to combine different uses of the same effect in a program, particularly in a language with a static type-and-effect system. For example, it is rudimentary to define the “mutable memory cell” effect as a pair of operations, put and get , together with a handler, but it is far from obvious how to use this effect a number of times to operate a number of memory cells in a single context. In this paper, we propose a solution based on lexically scoped effects in which each use (an “instance”) of an effect can be singled out by name, bound by an enclosing handler and tracked in the type of the expression. Such a setting proves to be delicate with respect to the choice of semantics, as it depends on the explosive mixture of effects, polymorphism, and reduction under binders. Hence, we devise a novel approach to Kripke-style logical relations that can deal with open terms, which allows us to prove the desired properties of our calculus. We formalise our core results in Coq, and introduce an experimental surface-level programming language to show that our approach is applicable in practice.
- Open Access
- 8 August 2019
- Published by Association for Computing Machinery (ACM)
- p. 98-113
Monad transformers and modular algebraic effects: what binds them together
- 8 August 2019
- Published by Association for Computing Machinery (ACM)
- p. 98-113
Open AccessMonad transformers and modular algebraic effects: what binds them together
- Open Access
- 4 July 2019
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 15, Is
Guarded and Unguarded Iteration for Generalized Processes
Models of iterated computation, such as (completely) iterative monads, often depend on a notion of guardedness, which guarantees unique solvability of recursive equations and requires roughly that recursive calls happen only under certain guarding operations. On the other hand, many models of iteration do admit unguarded iteration. Solutions are then no longer unique, and in general not even determined as least or greatest fixpoints, being instead governed by quasi-equational axioms. Monads that support unguarded iteration in this sense are called (complete) Elgot monads. Here, we propose to equip (Kleisli categories of) monads with an abstract notion of guardedness and then require solvability of abstractly guarded recursive equations; examples of such abstractly guarded pre-iterative monads include both iterative monads and Elgot monads, the latter by deeming any recursive definition to be abstractly guarded. Our main result is then that Elgot monads are precisely the iteration-congruent retracts of abstractly guarded iterative monads, the latter being defined as admitting unique solutions of abstractly guarded recursive equations; in other words, models of unguarded iteration come about by quotienting models of guarded iteration.
- 4 July 2019
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 15, Is
Open AccessGuarded and Unguarded Iteration for Generalized Processes
Models of iterated computation, such as (completely) iterative monads, often depend on a notion of guardedness, which guarantees unique solvability of recursive equations and requires roughly that recursive calls happen only under certain guarding operations. On the other hand, many models of iteration do admit unguarded iteration. Solutions are then no longer unique, and in general not even determined as least or greatest fixpoints, being instead governed by quasi-equational axioms. Monads that support unguarded iteration in this sense are called (complete) Elgot monads. Here, we propose to equip (Kleisli categories of) monads with an abstract notion of guardedness and then require solvability of abstractly guarded recursive equations; examples of such abstractly guarded pre-iterative monads include both iterative monads and Elgot monads, the latter by deeming any recursive definition to be abstractly guarded. Our main result is then that Elgot monads are precisely the iteration-congruent retracts of abstractly guarded iterative monads, the latter being defined as admitting unique solutions of abstractly guarded recursive equations; in other words, models of unguarded iteration come about by quotienting models of guarded iteration.
- Open Access
- 5 April 2019
- Published by Springer Nature
- p. 453-469
Equational Theories and Monads from Polynomial Cayley Representations
We generalise Cayley’s theorem for monoids by providing an explicit formula for a (multi-sorted) equational theory represented by the type $$PX \rightarrow X$$ , where $$P$$ is an arbitrary polynomial endofunctor with natural coefficients. From the computational perspective, examples of effects given by such theories include backtracking nondeterminism (obtained with the original Cayley representation $$X \rightarrow X$$ ), finite mutable state (obtained with $$n \rightarrow X$$ , for a constant n), and their different combinations (via $$n \times X \rightarrow X$$ or $$X^n \rightarrow X$$ ). Moreover, we show that monads induced by such theories are implementable using the type formers available in programming languages based on a polymorphic $$\lambda $$ -calculus, both as compositions of algebraic datatypes and as continuation-like monads. We give a set-theoretic model of the latter in terms of Barr-dinatural transformations. We also introduce , a tool that takes a polynomial as an input and generates the corresponding equational theory together with the two implementations of the induced monad in Haskell.- 5 April 2019
- Published by Springer Nature
- p. 453-469
Open AccessEquational Theories and Monads from Polynomial Cayley Representations
We generalise Cayley’s theorem for monoids by providing an explicit formula for a (multi-sorted) equational theory represented by the type $$PX \rightarrow X$$ , where $$P$$ is an arbitrary polynomial endofunctor with natural coefficients. From the computational perspective, examples of effects given by such theories include backtracking nondeterminism (obtained with the original Cayley representation $$X \rightarrow X$$ ), finite mutable state (obtained with $$n \rightarrow X$$ , for a constant n), and their different combinations (via $$n \times X \rightarrow X$$ or $$X^n \rightarrow X$$ ). Moreover, we show that monads induced by such theories are implementable using the type formers available in programming languages based on a polymorphic $$\lambda $$ -calculus, both as compositions of algebraic datatypes and as continuation-like monads. We give a set-theoretic model of the latter in terms of Barr-dinatural transformations. We also introduce , a tool that takes a polynomial as an input and generates the corresponding equational theory together with the two implementations of the induced monad in Haskell. - Open Access
- 2 January 2019
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 3 (POPL) , 1-28
Abstracting algebraic effects
Proposed originally by Plotkin and Pretnar, algebraic effects and their handlers are a leading-edge approach to computational effects: exceptions, mutable state, nondeterminism, and such. Appreciated for their elegance and expressiveness, they are now progressing into mainstream functional programming languages. In this paper, we introduce and examine programming language constructs that back adoption of programming with algebraic effects on a larger scale in a modular fashion by providing mechanisms for abstraction. We propose two such mechanisms: existential effects (which hide the details of a particular effect from the user) and local effects (which guarantee that no code coming from the outside can interfere with a given effect). The main technical difficulty arises from the dynamic nature of coupling an effectful operation with the right handler during execution, but, as we show in this paper, a carefully designed type system can ensure that this will not break the abstraction. Our main contribution is a novel calculus for algebraic effects and handlers, called λ HEL , equipped with local and existential algebraic effects, in which the dynamic nature of handlers is kept in check by typed runtime coercions. As a proof of concept, we present an experimental programming language based on our calculus, which provides strong abstraction mechanisms via an ML-style module system.
- 2 January 2019
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 3 (POPL) , 1-28
Open AccessAbstracting algebraic effects
Proposed originally by Plotkin and Pretnar, algebraic effects and their handlers are a leading-edge approach to computational effects: exceptions, mutable state, nondeterminism, and such. Appreciated for their elegance and expressiveness, they are now progressing into mainstream functional programming languages. In this paper, we introduce and examine programming language constructs that back adoption of programming with algebraic effects on a larger scale in a modular fashion by providing mechanisms for abstraction. We propose two such mechanisms: existential effects (which hide the details of a particular effect from the user) and local effects (which guarantee that no code coming from the outside can interfere with a given effect). The main technical difficulty arises from the dynamic nature of coupling an effectful operation with the right handler during execution, but, as we show in this paper, a carefully designed type system can ensure that this will not break the abstraction. Our main contribution is a novel calculus for algebraic effects and handlers, called λ HEL , equipped with local and existential algebraic effects, in which the dynamic nature of handlers is kept in check by typed runtime coercions. As a proof of concept, we present an experimental programming language based on our calculus, which provides strong abstraction mechanisms via an ML-style module system.
- Open Access
- 9 July 2018
- Published by Association for Computing Machinery (ACM)
- p. 809-818
Syntax and Semantics for Operations with Scopes
- 9 July 2018
- Published by Association for Computing Machinery (ACM)
- p. 809-818
Open AccessSyntax and Semantics for Operations with Scopes
- Open Access
- 27 December 2017
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 2 (POPL) , 1-30
Handle with care: relational interpretation of algebraic effects and handlers
Algebraic effects and handlers have received a lot of attention recently, both from the theoretical point of view and in practical language design. This stems from the fact that algebraic effects give the programmer unprecedented freedom to define, combine, and interpret computational effects. This plenty-of-rope, however, demands not only a deep understanding of the underlying semantics, but also access to practical means of reasoning about effectful code, including correctness and program equivalence. In this paper we tackle this problem by constructing a step-indexed relational interpretation of a call-by-value calculus with algebraic effect handlers and a row-based polymorphic type-and-effect system. Our calculus, while striving for simplicity, enjoys desirable theoretical properties, and is close to the cores of programming languages with algebraic effects used in the wild, while the logical relation we build for it can be used to reason about non-trivial properties, such as contextual equivalence and contextual approximation of programs. Our development has been fully formalised in the Coq proof assistant.
- 27 December 2017
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 2 (POPL) , 1-30
Open AccessHandle with care: relational interpretation of algebraic effects and handlers
Algebraic effects and handlers have received a lot of attention recently, both from the theoretical point of view and in practical language design. This stems from the fact that algebraic effects give the programmer unprecedented freedom to define, combine, and interpret computational effects. This plenty-of-rope, however, demands not only a deep understanding of the underlying semantics, but also access to practical means of reasoning about effectful code, including correctness and program equivalence. In this paper we tackle this problem by constructing a step-indexed relational interpretation of a call-by-value calculus with algebraic effect handlers and a row-based polymorphic type-and-effect system. Our calculus, while striving for simplicity, enjoys desirable theoretical properties, and is close to the cores of programming languages with algebraic effects used in the wild, while the logical relation we build for it can be used to reason about non-trivial properties, such as contextual equivalence and contextual approximation of programs. Our development has been fully formalised in the Coq proof assistant.
- 13 July 2017
- Published by Cambridge University Press (CUP) in Journal of Functional Programming
- Vol. 27
Backtracking with cut via a distributive law and left-zero monoids
We employ the framework of algebraic effects to augment the list monad with the pruning cut operator known from Prolog. We give two descriptions of the resulting monad: as the monad of free left-zero monoids, and as a composition via a distributive law of the list monad and the ‘unary idempotent operation’ monad. The scope delimiter of cut arises as a handler.
- 13 July 2017
- Published by Cambridge University Press (CUP) in Journal of Functional Programming
- Vol. 27
Backtracking with cut via a distributive law and left-zero monoids
We employ the framework of algebraic effects to augment the list monad with the pruning cut operator known from Prolog. We give two descriptions of the resulting monad: as the monad of free left-zero monoids, and as a composition via a distributive law of the list monad and the ‘unary idempotent operation’ monad. The scope delimiter of cut arises as a handler.