On Feller continuity and full abstraction Barthe, Gilles; Crubillé, Raphaëlle; Dal Lago, Ugo ...
Proceedings of ACM on programming languages,
08/2022, Volume:
6, Issue:
ICFP
Journal Article
Peer reviewed
Open access
We study the nature of applicative bisimilarity in λ-calculi endowed with operators for sampling from contin- uous distributions. On the one hand, we show that bisimilarity, logical equivalence, and ...testing equivalence all coincide with contextual equivalence when real numbers can be manipulated through continuous functions only. The key ingredient towards this result is a notion of Feller-continuity for labelled Markov processes, which we believe of independent interest, giving rise a broad class of LMPs for which coinductive and logically inspired equivalences coincide. On the other hand, we show that if no constraint is put on the way real numbers are manipulated, characterizing contextual equivalence turns out to be hard, and most of the aforementioned notions of equivalence are even unsound.
In order to reason about effects, we can define quantitative formulas to describe behavioural aspects of effectful programs. These formulas can for example express probabilities that (or sets of ...correct starting states for which) a program satisfies a property. Fundamental to this approach is the notion of quantitative modality, which is used to lift a property on values to a property on computations. Taking all formulas together, we say that two terms are equivalent if they satisfy all formulas to the same quantitative degree. Under sufficient conditions on the quantitative modalities, this equivalence is equal to a notion of Abramsky's applicative bisimilarity, and is moreover a congruence. We investigate these results in the context of Levy's call-by-push-value with general recursion and algebraic effects. For example, the results apply to (combinations of) nondeterministic choice, probabilistic choice, global store, and error.
Algebras can be used to interpret the behaviour of effectful programs. In particular, we use Eilenberg-Moore algebras given over a complete lattices of truth values, which specify answers to queries ...about programs. The algebras can be used to formulate a quantitative logic of behavioural properties, specifying a congruent notion of program equivalence coinciding with a notion of applicative bisimilarity. Many combinations of effects can be interpreted using these algebras. In this paper, we specify a method of generically combining effects and the algebras used to interpret them. At the core of this method is the tensor of complete lattices, which combines the carrier sets of the algebras. We show that this tensor preserves complete distributivity of complete lattices. Moreover, the universal properties of this tensor can then be used to properly combine the Eilenberg-Moore algebras. We will apply this method to combine the effects of probability, global store, cost, nondeterminism, and error effects. We will then compare this method of combining effects with the more traditional method of combining equational theories using interaction laws.
We study the observational theory of Thielecke's (recursive) CPS-calculus, a target language for CPS transforms designed to bring out the jumping, imperative nature of continuation-passing.
We define ...a labelled transition system for the CPS-calculus from which we derive a (weak) labelled bisimilarity that completely characterises Morris' context-equivalence. We prove a context lemma showing that Morris' context-equivalence coincides with a simpler context-equivalence closed under a certain class of contexts. Then we profit of the determinism of the CPS-calculus to give a simpler labelled characterisation of Morris' equivalence, resembling Abramsky's applicative bisimilarity. We enhance our bisimulation proof-methods with up-to bisimilarity and up-to context proof techniques. We use our bisimulation proof techniques to study the algebraic theory of the CPS-calculus proving two new algebraic laws that we conjecture cannot be derived using the original axiomatic semantics for the CPS-calculus. Finally, we prove the full abstraction of Thielecke's encoding of the CPS-calculus into a fragment of Fournet and Gonthier's Join-calculus with single pattern definitions.
This paper investigates operationally-based theories of a simply-typed functional programming language with countable non-determinism. The theories are based upon lower, upper, and convex variants of ...applicative similarity and bisimilarity, and the main result presented here is that these relations are compatible. The differences between the relations are illustrated by simple examples, and their continuity properties are discussed. It is also shown that, in some cases, the addition of countable non-determinism to a programming language with finite non-determinism alters the theory of the language.
PDF
