Search Results

Documents authored by Ahman, Danel

Document
Invited Talk
DOI: 10.4230/LIPIcs.FSCD.2026.1
Sheaves as Oracle Computations (Invited Talk)

Authors: Danel Ahman and Andrej Bauer

Published in: LIPIcs, Volume 378, 11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026)

Abstract
In type theory, an oracle may be specified abstractly by a predicate whose domain is the type of queries asked of the oracle, and whose proofs are the oracle answers. Such a specification induces an oracle modality that captures a computational intuition about oracles: at each step of reasoning we either know the result, or we ask the oracle a query and proceed upon receiving an answer. We characterize an oracle modality as the least one forcing the given predicate. We establish an adjoint retraction between modalities and propositional containers, from which it follows that every modality is an oracle modality. The left adjoint maps sums to suprema, which makes suprema of modalities easy to compute when they are given in terms of oracle modalities. We also study sheaves for oracle modalities. We describe sheafification in terms of a quotient-inductive type of computation trees, and describe sheaves as algebras for the corresponding monad. We also introduce equifoliate trees, an intensional notion of oracle computation given by a (non-propositional) container. Equifoliate trees descend to sheaves, and modally cover them. As an application, we give a concrete description of all Lawvere-Tierney topologies in a realizability topos, closely related to a game-theoretic characterization by Takayuki Kihara.
Cite as

Danel Ahman and Andrej Bauer. Sheaves as Oracle Computations (Invited Talk). In 11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 378, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ahman_et_al:LIPIcs.FSCD.2026.1,
  author =	{Ahman, Danel and Bauer, Andrej},
  title =	{{Sheaves as Oracle Computations}},
  booktitle =	{11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026)},
  pages =	{1:1--1:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-433-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{378},
  editor =	{Pfenning, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2026.1},
  URN =		{urn:nbn:de:0030-drops-263510},
  doi =		{10.4230/LIPIcs.FSCD.2026.1},
  annote =	{Keywords: modality, oracle, sheaf}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2026.4
Strong Normalisation for Asynchronous Effects

Authors: Danel Ahman and Ilja Sobolev

Published in: LIPIcs, Volume 378, 11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026)

Abstract
Asynchronous effects of Ahman and Pretnar complement the conventional synchronous treatment of algebraic effects with asynchrony based on decoupling the execution of algebraic operation calls into signalling that an operation’s implementation needs to be executed, and into interrupting a running computation with the operation’s result, to which the computation can react by installing matching interrupt handlers. Beyond providing asynchrony for algebraic effects, the resulting core calculus also naturally models examples such as pre-emptive multi-threading, (cancellable) remote function calls, and multi-party applications. In this paper, we study the normalisation properties of this calculus. We prove that if one removes general recursion from it, then the remaining calculus is strongly normalising, including both its sequential and parallel parts. To cover more interesting programs, we also prove that the sequential part of the calculus remains strongly normalising when a controlled amount of interrupt-driven recursive behaviour is reintroduced. Our normalisation proofs are structured compositionally as an extension of Lindley and Stark’s ⊤⊤-lifting-based approach for proving strong normalisation of effectful languages. All our results are also formalised in Agda.
Cite as

Danel Ahman and Ilja Sobolev. Strong Normalisation for Asynchronous Effects. In 11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 378, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ahman_et_al:LIPIcs.FSCD.2026.4,
  author =	{Ahman, Danel and Sobolev, Ilja},
  title =	{{Strong Normalisation for Asynchronous Effects}},
  booktitle =	{11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-433-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{378},
  editor =	{Pfenning, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2026.4},
  URN =		{urn:nbn:de:0030-drops-263541},
  doi =		{10.4230/LIPIcs.FSCD.2026.4},
  annote =	{Keywords: Strong normalisation, Girard-Tait method, reducibility, asynchronous effects}
}
Document
DOI: 10.4230/LIPIcs.LICS.2026.4
A Convenient Fibration for Dependently-Typed Probability Theory

Authors: Danel Ahman, Ohad Kammar, and Rasmus Ejlers Møgelberg

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract
We describe semantic structures relevant for interpreting dependent types for statistical and probabilistic modelling. Our development extends the theory of quasi-Borel spaces (qbses) of Staton et. al, which support simply-typed, higher-order probability theory with continuous distributions. It is well-known that qbses can interpret a dependent-type theory supporting dependent function-spaces through the codomain fibration. We define an equivalent split fibration based on the family fibration, which we call quasi-Borel families (qbfs), characterise its structure, equip it with fibred monads of measures and probability, and use them to develop dependently-typed probability theory. We characterise the structure of the qbf fibration that is relevant for dependently-typed probability theory in elementary form. Our characterisations include: context extension, dependent pairs, dependent functions, extensional identity types, fibred products and coproducts, subspaces, a universe of propositions, and straightforward internalisation and externalisation principles for discrete spaces. We use these concepts to define fibred distribution and probability monads, the semantic structure needed to interpret probability distributions under a dependent context. We show that this structure satisfies a fibred version of Kock’s synthetic measure theory. We also use these concepts to develop a qbs counterpart to Kolmogorov’s conditional expectation. Our main result is a version of the conditional expectation that, under standard regularity assumptions, is measurable in both the random variables we are conditioning, and the observation map we are conditioning by.
Cite as

Danel Ahman, Ohad Kammar, and Rasmus Ejlers Møgelberg. A Convenient Fibration for Dependently-Typed Probability Theory. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 4:1-4:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ahman_et_al:LIPIcs.LICS.2026.4,
  author =	{Ahman, Danel and Kammar, Ohad and M{\o}gelberg, Rasmus Ejlers},
  title =	{{A Convenient Fibration for Dependently-Typed Probability Theory}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{4:1--4:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.4},
  URN =		{urn:nbn:de:0030-drops-267915},
  doi =		{10.4230/LIPIcs.LICS.2026.4},
  annote =	{Keywords: probability theory, quasi-Borel space, Grothendieck fibration, fibred monad, conditional expectation, measure theory, random variables, dependent types, quasitopos, probabilistic programming, denotational semantics, synthetic measure theory}
}
Document
DOI: 10.4230/DagRep.11.6.54
Scalable Handling of Effects (Dagstuhl Seminar 21292)

Authors: Danel Ahman, Amal Ahmed, Sam Lindley, and Andreas Rossberg

Published in: Dagstuhl Reports, Volume 11, Issue 6 (2021)

Abstract
Built on solid mathematical foundations, effect handlers offer a uniform and elegant approach to programming with user-defined computational effects. They subsume many widely used programming concepts and abstractions, such as actors, async/await, backtracking, coroutines, generators/iterators, and probabilistic programming. As such, they allow language implementers to target a single implementation of effect handlers, freeing language implementers from having to maintain separate ad hoc implementations of each of the features listed above. Due to their wide applicability, effect handlers are enjoying growing interest in academia and industry. For instance, several effect handler oriented research languages are under active development (such as Eff, Frank, and Koka), as are effect handler libraries for mainstream languages (such as C and Java), effect handlers are seeing increasing use in probabilistic programming tools (such as Uber’s Pyro), and proposals are in the pipeline to include them natively in low-level languages (such as WebAssembly). Effect handlers are also a key part of Multicore OCaml, which incorporates an efficient implementation of them for uniformly expressing user-definable concurrency models in the language. However, enabling effect handlers to scale requires tackling some hard problems, both in theory and in practice. Inspired by experience of developing, programming with, and reasoning about effect handlers in practice, we identify five key problem areas to be addressed at this Dagstuhl Seminar in order to enable effect handlers to scale: Safety, Modularity, Interoperability, Legibility, and Efficiency. In particular, we seek answers to the following questions: - How can we enforce safe interaction between effect handler programs and external resources? - How can we enable modular use of effect handlers for programming in the large? - How can we support interoperable effect handler programs written in different languages? - How can we write legible effect handler programs in a style accessible to mainstream programmers? - How can we generate efficient code from effect handler programs?
Cite as

Danel Ahman, Amal Ahmed, Sam Lindley, and Andreas Rossberg. Scalable Handling of Effects (Dagstuhl Seminar 21292). In Dagstuhl Reports, Volume 11, Issue 6, pp. 54-81, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{ahman_et_al:DagRep.11.6.54,
  author =	{Ahman, Danel and Ahmed, Amal and Lindley, Sam and Rossberg, Andreas},
  title =	{{Scalable Handling of Effects (Dagstuhl Seminar 21292)}},
  pages =	{54--81},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{6},
  editor =	{Ahman, Danel and Ahmed, Amal and Lindley, Sam and Rossberg, Andreas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.6.54},
  URN =		{urn:nbn:de:0030-drops-155800},
  doi =		{10.4230/DagRep.11.6.54},
  annote =	{Keywords: continuations, Effect handlers, Wasm}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2019.14
Decomposing Comonad Morphisms

Authors: Danel Ahman and Tarmo Uustalu

Published in: LIPIcs, Volume 139, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)

Abstract
The analysis of set comonads whose underlying functor is a container functor in terms of directed containers makes it a simple observation that any morphism between two such comonads factors through a third one by two comonad morphisms, whereof the first is identity on shapes and the second is identity on positions in every shape. This observation turns out to generalize into a much more involved result about comonad morphisms to comonads whose underlying functor preserves Cartesian natural transformations to itself on any category with finite limits. The bijection between comonad coalgebras and comonad morphisms from costate comonads thus also yields a decomposition of comonad coalgebras.
Cite as

Danel Ahman and Tarmo Uustalu. Decomposing Comonad Morphisms. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ahman_et_al:LIPIcs.CALCO.2019.14,
  author =	{Ahman, Danel and Uustalu, Tarmo},
  title =	{{Decomposing Comonad Morphisms}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-120-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{139},
  editor =	{Roggenbach, Markus and Sokolova, Ana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.14},
  URN =		{urn:nbn:de:0030-drops-114427},
  doi =		{10.4230/LIPIcs.CALCO.2019.14},
  annote =	{Keywords: container functors (polynomial functors), container comonads, comonad morphisms and comonad coalgebras, cofunctors, lenses}
}
Document
DOI: 10.4230/LIPIcs.TYPES.2013.1
Update Monads: Cointerpreting Directed Containers

Authors: Danel Ahman and Tarmo Uustalu

Published in: LIPIcs, Volume 26, 19th International Conference on Types for Proofs and Programs (TYPES 2013)

Abstract
We introduce update monads as a generalization of state monads. Update monads are the compatible compositions of reader and writer monads given by a set and a monoid. Distributive laws between such monads are given by actions of the monoid on the set. We also discuss a dependently typed generalization of update monads. Unlike simple update monads, they cannot be factored into a reader and writer monad, but rather into similarly looking relative monads. Dependently typed update monads arise from cointerpreting directed containers, by which we mean an extension of an interpretation of the opposite of the category of containers into the category of set functors.
Cite as

Danel Ahman and Tarmo Uustalu. Update Monads: Cointerpreting Directed Containers. In 19th International Conference on Types for Proofs and Programs (TYPES 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 26, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{ahman_et_al:LIPIcs.TYPES.2013.1,
  author =	{Ahman, Danel and Uustalu, Tarmo},
  title =	{{Update Monads: Cointerpreting Directed Containers}},
  booktitle =	{19th International Conference on Types for Proofs and Programs (TYPES 2013)},
  pages =	{1--23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-72-9},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{26},
  editor =	{Matthes, Ralph and Schubert, Aleksy},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TYPES.2013.1},
  URN =		{urn:nbn:de:0030-drops-46235},
  doi =		{10.4230/LIPIcs.TYPES.2013.1},
  annote =	{Keywords: monads and distributive laws, reader, writer and state monads, monoids and monoid actions, directed containers}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact