Title: Probabilistic Relational Reasoning via Metrics,
Abstract: The Fuzz programming language [Reed and Pierce, 2010] uses an elegant linear
type system combined with a monad-like type to express and reason about
probabilistic sensitivity properties, most notably $\epsilon$-differential
privacy. We show how to extend Fuzz to capture more general relational
properties of probabilistic programs, with approximate, or $(\epsilon,
\delta)$-differential privacy serving as a leading example. Our technical
contributions are threefold. First, we introduce the categorical notion of
comonadic lifting of a monad to model composition properties of probabilistic
divergences. Then, we show how to express relational properties in terms of
sensitivity properties via an adjunction we call the path construction.
Finally, we instantiate our semantics to model the terminating fragment of Fuzz
extended with types carrying information about other divergences between
distributions.