Category Archives: Publications

Research publications by Andrej Bauer

Programming with Algebraic Effects and Handlers

With Matija Pretnar.

Abstract: Eff is a programming language based on the algebraic approach to computational effects, in which effects are viewed as algebraic operations and effect handlers as homomorphisms from free algebras. Eff supports first-class effects and handlers through which we may easily define new computational effects, seamlessly combine existing ones, and handle them in novel ways. We give a denotational semantics of eff and discuss a prototype implementation based on it. Through examples we demonstrate how the standard effects are treated in eff, and how eff supports programming techniques that use various forms of delimited continuations, such as backtracking, breadth-first search, selection functionals, cooperative multi-threading, and others.

Download paper: eff.pdf

ArXiv version: arXiv:1203.1539v1 [cs.PL]

To read more about eff, visit the eff page.

On the Bourbaki-Witt Principle in Toposes

With Peter LeFanu Lumsdaine.

Abstract: The Bourbaki-Witt principle states that any progressive map on a chain-complete poset has a fixed point above every point. It is provable classically, but not intuitionistically. We study this and related principles in an intuitionistic setting. Among other things, we show that Bourbaki-Witt fails exactly when the trichotomous ordinals form a set, but does not imply that fixed points can always be found by transfinite iteration. Meanwhile, on the side of models, we see that the principle fails in realisability toposes, and does not hold in the free topos, but does hold in all cocomplete toposes.

Download paper: bw.pdf
ArXiv version: arXiv:1201.0340v1 [math.CT]

This paper is an extension of my previous paper on the Bourbaki-Witt and Knaster-Tarski fixed-point theorems in the effective topos (arXiv:0911.0068v1).

Constructive gem: an injection from Baire space to natural numbers

I am not sure whether to call this one a constructive gem or stone. I suppose it is a matter of personal taste. I think it is a gem, albeit a very unusual one: there is a topos in which $\mathbb{N}^\mathbb{N}$ can be embedded into $\mathbb{N}$. Continue reading Constructive gem: an injection from Baire space to natural numbers

Stone Duality for Skew Boolean Algebras with Intersections

With Karin Cvetko Vah.

For the last two months or so I got “distracted” by a topic which is not properly my core interest, namely non-commutative algebra. It was very strange at first, but now that I got used to non-commutative lattices (yes, there is such a thing) it’s kind of fun. Anyhow, Karin Cvetko Vah and I worked out Stone duality for skew Boolean algebras with intersections. Classical Stone duality tells us that Boolean algebras are dual to Stone spaces (zero-dimensional compact Hausdorff spaces), and that the generalized Boolean algebras (which are like Boolean algebras without a top element) are dual to Boolean spaces (zero-dimensional locally-compact Hausdorff spaces). Our skew version of duality says that right-handed skew Boolean algebras with intersections are dual to surjective etale maps between Boolean spaces. It is quite a mouthful to say “right-handed skew Boolean algebra with intersections”, let alone get used to it, but in a certain sense this is a very natural non-commutative structure. And we can get rid of the “right-handed” condition to obtain duality for “skew Boolean algebras with intersections”, as well as several other versions. We use the duality to construct a right-handed skew Boolean algebra with intersections which does not have a lattice section. It has been an open question whether such skew lattices exist.

Download: sba.pdf

arXiv: 1106.0425

Abstract: We extend Stone duality between generalized Boolean algebras and Boolean spaces, which are the zero-dimensional locally-compact Hausdorff spaces, to a non-commutative setting. We first show that the category of right-handed skew Boolean algebras with intersections is dual to the category of surjective étale maps between Boolean spaces. We then extend the duality to skew Boolean algebras with intersections, and consider several variations in which the morphisms are restricted. Finally, we use the duality to construct a right-handed skew Boolean algebra without a lattice section.

And now I can get back to homotopy type theory and Coq hacking.

Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions

Jens Blanck and I presented a paper at Computability and Complexity in Analysis 2009 with a complicated title (I like complicated titles):

Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions

which has been published in Volume 16, Issue 18 of the Journal of Universal Computer Science. I usually just post the abstract, but this time I would like to explain the general idea informally, the way one can do it on a blog. But first, here is the abstract:

Abstract: We prove general theorems about unique existence of effective subalgebras of classical algebras. The theorems are consequences of standard facts about completions of metric spaces within the framework of constructive mathematics, suitably interpreted in realizability models. We work with general realizability models rather than with a particular model of computation. Consequently, all the results are applicable in various established schools of computability, such as type 1 and type 2 effectivity, domain representations, equilogical spaces, and others.

Download paper: effalg.pdf or directly from JUCS

Continue reading Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions