PPPiotr Polesiuk

Piotr Polesiuk

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Piotr Polesiuk has a total of 14 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Deciding not to Decide

    by Patrycja Balik, Szymon JęDras, Piotr Polesiuk


  • Open Access

    Remarks on Algebraic Reconstruction of Types and Effects

    by Patrycja Balik, Szymon JęDras, Piotr Polesiuk

    In their 1991 paper "Algebraic Reconstruction of Types and Effects," Pierre Jouvelot and David Gifford presented a type-and-effect reconstruction algorithm based on an algebraic structure of effects. Their work is considered a milestone in the development of type-and-effect systems, and has inspired numerous subsequent works in the area of static analysis. However, unlike the later research it spawned, the original algorithm considered a language with higher-rank polymorphism, a feature which is challenging to implement correctly. In this note, we identify subtle bugs related to variable binding in their approach to this feature. We revisit their type system and reconstruction algorithm, and describe the discovered issues.

  • Open Access

    Deciding not to Decide: Sound and Complete Effect Inference in the Presence of Higher-Rank Polymorphism

    by Patrycja Balik, Szymon JęDras, Piotr Polesiuk

    Type-and-effect systems help the programmer to organize data and computational effects in a program. While for traditional type systems expressive variants with sophisticated inference algorithms have been developed and widely used in programming languages, type-and-effect systems did not yet gain widespread adoption. One reason for this is that type-and-effect systems are more complex and the existing inference algorithms make compromises between expressiveness, intuitiveness, and decidability. In this work, we present an effect inference algorithm for a type-and-effect system with subtyping, expressive higher-rank polymorphism, and intuitive set-like semantics of effects. In order to deal with scoping issues of higher-rank polymorphism, we delay solving of effect constraints by transforming them into formulae of propositional logic. We prove soundness and completeness of our algorithm with respect to a declarative type-and-effect system. All the presented results have been formalized in the Rocq proof assistant, and the algorithm has been successfully implemented in a realistic programming language.

  • Open Access

    Fully Abstract Encodings of $λ$-Calculus in HOcore through Abstract Machines

    by Małgorzata Biernacka, Dariusz Biernacki, Sergueï Lenglet, Piotr Polesiuk, Damien Pous, Alan Schmitt

    We present fully abstract encodings of the call-by-name and call-by-value $\lambda$-calculus into HOcore, a minimal higher-order process calculus with no name restriction. We consider several equivalences on the $\lambda$-calculus side -- normal-form bisimilarity, applicative bisimilarity, and contextual equivalence -- that we internalize into abstract machines in order to prove full abstraction of the encodings. We also demonstrate that this technique scales to the $\lambda\mu$-calculus, i.e., a standard extension of the $\lambda$-calculus with control operators.

  • Open Access

    Binders by day, labels by night: effect instances via lexically scoped handlers

    by Dariusz Biernacki, Maciej Piróg, Piotr Polesiuk, Filip Sieczkowski

    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

    Diacritical Companions

    by Dariusz Biernacki, Sergueï Lenglet, Piotr Polesiuk


  • Open Access

    Bisimulations for Delimited-Control Operators

    by Dariusz Biernacki, Sergueï Lenglet, Piotr Polesiuk

    We present a comprehensive study of the behavioral theory of an untyped $\lambda$-calculus extended with the delimited-control operators shift and reset. To that end, we define a contextual equivalence for this calculus, that we then aim to characterize with coinductively defined relations, called bisimilarities. We consider different styles of bisimilarities (namely applicative, normal-form, and environmental) within a unifying framework, and we give several examples to illustrate their respective strengths and weaknesses. We also discuss how to extend this work to other delimited-control operators.


  • Open Access

    Equational Theories and Monads from Polynomial Cayley Representations

    by Maciej Piróg, Piotr Polesiuk, Filip Sieczkowski

    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

    A Complete Normal-Form Bisimilarity for State

    by Dariusz Biernacki, Sergueï Lenglet, Piotr Polesiuk

    We present a sound and complete bisimilarity for an untyped $$\lambda $$ -calculus with higher-order local references. Our relation compares values by applying them to a fresh variable, like normal-form bisimilarity, and it uses environments to account for the evolving store. We achieve completeness by a careful treatment of evaluation contexts comprising open stuck terms. This work improves over Støvring and Lassen’s incomplete environment-based normal-form bisimilarity for the $$\lambda \rho $$ -calculus, and confirms, in relatively elementary terms, Jaber and Tabareau’s result, that the state construct is discriminative enough to be characterized with a bisimilarity without any quantification over testing arguments.