# The Central Valuations Monad

Xiaodong Jia, Michael Mislove, Vladimir Zamdzhiev

► To cite this version:

Xiaodong Jia, Michael Mislove, Vladimir Zamdzhiev. The Central Valuations Monad. CALCO 2021 - 9th International Conference on Algebra and Coalgebra in Computer Science, Aug 2021, Salzburg, Austria. 10.4230/LIPIcs.CALCO.2021.18 . hal-03258065v3

HAL Id: hal-03258065

https://inria.hal.science/hal-03258065v3

Submitted on 2 Dec 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Central Valuations Monad

## Xiaodong Jia

School of Mathematics, Hunan University, Changsha, China

## Michael Mislove

Department of Computer Science, Tulane University, New Orleans, LA, USA

## Vladimir Zamdzhiev

Université de Lorraine, CNRS, Inria, LORIA, F 54000 Nancy, France

### Abstract

We give a commutative valuations monad $\mathcal{Z}$ on the category **DCPO** of dcpo's and Scott-continuous functions. Compared to the commutative valuations monads given in [2], our new monad $\mathcal{Z}$ is larger and it contains all push-forward images of valuations on the unit interval [0, 1] along lower semi-continuous maps. We believe that this new monad will be useful in giving domain-theoretic denotational semantics for statistical programming languages with continuous probabilistic choice.

**2012 ACM Subject Classification** Theory of computation → Denotational semantics

**Keywords and phrases** Valuations, Commutative Monad, DCPO, Probabilistic Choice, Recursion

**Digital Object Identifier** 10.4230/LIPIcs.CALCO.2021.18

**Category** Early Ideas

**Acknowledgements** We thank the anonymous reviewers for their feedback which led to improvements of this paper. Xiaodong Jia acknowledges the support of NSFC (No. 12001181).

## 1 Introduction

The valuations monad $\mathcal{V}$ on the category **DCPO** of dcpo's and Scott-continuous functions is a staple of the domain-theoretic approach for denotational semantics of programming languages with probabilistic choice and recursion [3, 4]. For a dcpo $D$, $VD$ consists of *subprobability valuations* on $D$, which are the Scott-continuous functions $\nu$ from the set $\sigma D$ of Scott open subsets of $D$ to $[0, 1]$ satisfying *strictness* ($\nu(\emptyset) = 0$) and *modularity* ($\nu(U) + \nu(V) = \nu(U \cup V) + \nu(U \cap V)$). The set $VD$ is a dcpo in the *stochastic order*: $\nu_1 \le \nu_2$ if and only if $\nu_1(U) \le \nu_2(U)$ for all $U \in \sigma D$. The unit of $\mathcal{V}$ at dcpo $D$ is the map $\eta_D: D \to VD :: x \mapsto \delta_x$, where $\delta_x$ is the *Dirac valuation* at $x$, defined by $\delta_x(U) = 1$ if $x \in U$ and $\delta_x(U) = 0$ otherwise. For a Scott-continuous map $f: D \to VE$, the *Kleisli extension* $f^\dagger$ of $f$ is defined by $f^\dagger(\nu)(U) = \int_{x \in X} f(x)(U) d\nu$ for $\nu \in VD$ and $U \in \sigma E$. The integral in this definition is a Choquet type integral: for a general Scott-continuous function $h: D \to [0, 1]$, the value of $\int_{x \in X} hd\nu$ is defined to be the Riemann integral $\int_0^1 \nu(h^{-1}(t, 1))dt$. Following this, the action of $\mathcal{V}$ on a Scott-continuous function $g: D \to E$ between dcpo's $D$ and $E$ is $\mathcal{V}(g) \stackrel{\text{def}}{=} (\eta_E \circ g)^\dagger$; concretely, for $\nu \in VD$ and $U \in \sigma E$, $\mathcal{V}(g)(\nu)(U) = \nu(g^{-1}(U))$. Subprobability valuations on general topological spaces and the corresponding integral of lower semi-continuous functions against subprobability valuations can be defined similarly [3].

While it is well-known that $\mathcal{V}$ can be restricted to a commutative monad on the category **DOM** of domains and Scott-continuous functions, it is unknown whether $\mathcal{V}$ can be restricted to any Cartesian closed full subcategory of **DOM**. This is known as the *Jung-Tix problem* [5].

One may note that the category **DCPO** itself is Cartesian closed and $\mathcal{V}$ is a monad on it. What does one lose if we use the category **DCPO** and monad $\mathcal{V}$ for semantics? A short answer is that compared to **DOM**, $\mathcal{V}$ is not known to be commutative over **DCPO**, which is an important property for the denotational semantics of programming languages.

<figure><img src="image_2.png" /></figure>

© Xiaodong Jia, Michael Mislove, and Vladimir Zamdzhiev;
licensed under Creative Commons License CC-BY 4.0

9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021).

Editors: Fabio Gadducci and Alexandra Silva; Article No. 18; pp. 18:1–18:5

<figure><img src="image_3.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
## 18:2 The Central Valuations Memoad

Commutativity of $\mathcal{V}$ over **DCPO** is equivalent to showing the following Fubini-style equation

$$ \int_{x \in D} \int_{y \in E} h(x, y)d\mu d\nu = \int_{y \in E} \int_{x \in D} h(x, y)d\nu d\mu \quad (1) $$

holds for all dcpo's $D$ and $E$, all Scott-continuous functions $h: D \times E \to [0, 1]$ and all $\nu \in \mathcal{V}D, \mu \in \mathcal{V}E$. As pointed out in [2], the main difficulty in establishing (1) over **DCPO** is that the Scott topology on the product dcpo $D \times E$ may be different from the product topology $\sigma D \times \sigma E$. Actually, we do know that Equation (1) holds for those functions $h$ that are continuous when $D \times E$ is given the product topology $\sigma D \times \sigma E$ ([4, Lemma 2.37]).

Instead of directly proving (1), we showed (together with Lindenhovius) how to construct three submonads of $\mathcal{V}$ that are commutative on **DCPO**, and used each one to give a sound and (strongly) adequate semantics to PFPC (Probabilistic FixPoint Calculus) [2]. The simplest of those three monads is the monad $\mathcal{M}$. For each dcpo $D$, $\mathcal{MD}$ is defined to be the smallest sub-dcpo of $\mathcal{VD}$ that contains $\mathcal{SD}$, the family of simple valuations on $D$, where a simple valuation is a finite convex sum of Dirac valuations. The other two commutative monads are denoted $\mathcal{W}$ and $\mathcal{P}$ and the following inclusions hold for each dcpo $D: \mathcal{SD} \subseteq \mathcal{MD} \subseteq \mathcal{WD} \subseteq \mathcal{PD} \subseteq \mathcal{VD}$.

Each of our three monads is large enough to interpret discrete probabilistic choice in PFPC [2]. However, it is unclear if any of these monads is large enough to interpret continuous probabilistic choice. In this note, we define a new commutative valuations monad $\mathcal{Z}$ on the category **DCPO** which is larger than $\mathcal{M}, \mathcal{W}$ and $\mathcal{P}$ with the hope of addressing this problem.

# 2 Central Valuations

Our idea for defining $\mathcal{Z}$ is inspired by the notion of centre in group theory (which always forms an abelian subgroup) and the notion of centre of a premonoidal category (which always forms a monoidal subcategory) [6].

**Definition 1.** A subprobability valuation $\nu$ on a dcpo $D$ is called a central valuation if for any dcpo $E$, any valuation $\mu$ on $E$, and any Scott-continuous function $h: D \times E \to [0, 1]$, we have

$$ \int_{x \in D} \int_{y \in E} h(x, y)d\mu d\nu = \int_{y \in E} \int_{x \in D} h(x, y)d\nu d\mu. $$

We shall write $\mathcal{Z}D$ for the set of all central valuations on a dcpo $D$.

It is easy to see that simple valuations are central, and that the central valuations are closed under directed suprema under the stochastic order. Thus, for each dcpo $D$, $\mathcal{Z}D$ is a sub-dcpo of $\mathcal{VD}$ containing $\mathcal{SD}$. Moreover, we have the following theorem, which can be proved using the *disintegration formula* in [1].

**Theorem 2.** The assignment $\mathcal{Z}(-)$ extends to a commutative monad over the category **DCPO** when equipped with the (co)restricted monad operations of $\mathcal{V}$. In other words, $\mathcal{Z}$ is a commutative submonad of $\mathcal{V}$.

**Proof.** The unit of $\mathcal{Z}$ at dcpo $D$ sends each $x \in D$ to $\delta_x$ which is obviously a central valuation.

Let $f: C \to \mathcal{Z}D$ be a Scott-continuous function. Then $f$ can also be viewed as a Scott-continuous map from $C$ to $\mathcal{VD}$, since $\mathcal{Z}D$ is a sub-dcpo of $\mathcal{VD}$. We prove that $f^\dagger: \mathcal{VC} \to \mathcal{VD}$ maps central valuations on $C$ to central valuations on $D$. Towards this end, we pick $\mu$
from $\mathcal{ZC}$, and assume that $E$ is a dcpo, $\nu$ is an arbitrary subprobability valuation on $E$ and $h: D \times E \to [0, 1]$ is a Scott-continuous map. Then by the disintegration formula (see Lemma 3.1(iii) in [1]) we have that

$$ \int_{y \in E} \int_{x \in D} h(x, y)d(f^{\dagger}(\mu))d\nu = \int_{y \in E} \int_{t \in C} \int_{x \in D} h(x, y)df(t)d\mu d\nu, $$

and the right side of the equation is equal to

$$ \int_{t \in C} \int_{x \in D} \int_{y \in E} h(x, y)d\nu df(t)d\mu $$

by the fact that $f(t), t \in D$ and $\mu$ are central valuations. Again, by the disintegration formula that is just $\int_{x \in D} \int_{y \in E} h(x, y)d\nu df^{\dagger}(\mu)$. Hence we have proved that $f^{\dagger}(\mu)$ is indeed a central valuation provided that $\mu$ is. Similar arguments show that the monadic strength also (co)restricts as required. The corresponding (co)restrictions of the monadic operations of $\mathcal{V}$ to $\mathcal{Z}$ validate that $\mathcal{Z}$ is a strong monad on DCPO. The commutativity of $\mathcal{Z}$, which is equivalent to Equation (1) holding for all dcpo's $D$ and $E$ and central valuations $\mu$ and $\nu$ on them, is then obvious by definition of $\mathcal{Z}$.

$\blacksquare$

In fact, it is proved in [2] that all point-continuous valuations are central and therefore $SD \subseteq MD \subseteq WD \subseteq PD \subseteq ZD \subseteq \mathcal{V}D$ for each dcpo $D$. Therefore $\mathcal{Z}$ is the largest commutative submonad of $\mathcal{V}$ known so far. Furthermore, observe that $\mathcal{Z} = \mathcal{V}$ iff $\mathcal{V}$ is a commutative monad on DCPO. The latter has been an open problem since 1989, and our simple observation leads us to believe $\mathcal{Z}$ is a very large commutative submonad of $\mathcal{V}$.

It is not difficult to see that, in order to model sampling against continuous probability distributions on the interval $[0, 1]$, the monad used for the semantics should at least contain the push-forward images of the Lebesgue valuation on $[0, 1]$ (equipped with the metric topology) along lower semi-continuous maps. We can demonstrate even more is true of our new monad $\mathcal{Z}$ (see Theorem 4 below). For this, let us first recall that a space $X$ is called core-compact if the set $OX$ of all open subsets of $X$ is a continuous lattice in the inclusion order. Equivalently, $X$ is core-compact if and only if for each open subset $U$ of $X$ and $x \in U$, there exists an open subset $V$ such that $x \in V \ll U$, where $V \ll U$ means that $V$ is way-below $U$ in the sense of domain theory. Many important spaces are core-compact. For example, each locally compact space is core-compact, and in particular, the unit interval with the usual topology is compact Hausdorff, hence locally compact hence core-compact.

**Lemma 3.** Let $X$ be a core-compact topological space. Let $D, E$ be dcpos, and $f: X \to D$ a lower semi-continuous map, i.e., $f$ is continuous when $D$ is equipped with the Scott topology. Then the map $f \times \mathrm{id}_E: X \times \Sigma E \to D \times E$ is also lower semi-continuous, where $\Sigma E$ denotes the topological space $(E, \sigma E)$ and $X \times \Sigma E$ is the topological product of $X$ and $\Sigma E$.

**Proof.** First, we assume that $X$ is core-compact and prove that $f \times \mathrm{id}_E$ is lower semi-continuous. Towards this end, we pick a Scott open subset $O$ of $D \times E$, and assume that $f \times \mathrm{id}_Y((x_0, e_0)) \in O$, that is $(f(x_0), e_0) \in O$. We must find an open neighbourhood $U$ of $x_0$ in $X$ and a Scott open neighbourhood $V$ of $e_0$ in $E$ such that $f \times \mathrm{id}_Y(U \times V) \subseteq O$. We let $A = \{x \in X | (f(x), e_0) \in O\}$. Then $A$ is just $f^{-1}(O_{e_0})$, where $O_{e_0} = \{d \in D | (d, e_0) \in O\}$. Since $f: X \to D$ is lower semi-continuous and $O_{e_0}$ is Scott open in $D$, we know that $A$ is an open neighbourhood of $x_0$ in $X$. Now the core-compactness of $X$ enables us to find, in $X$, an open subset $U$ and a sequence of open subsets $U_i, i \in \mathbb{N}$ such that $x_0 \in U \ll \dots \ll U_n \dots \ll U_1 \ll A$. For each $U_n, n \in \mathbb{N}$, we define $V_n = \{e | f(x, e) \in O \text{ for all } x \in U_n\}$ and
18:4 The Central Valuations Memoad

let $V = \bigcup_{n \in \mathbb{N}} V_n$. Since for each $n \in \mathbb{N}$, $U_n \subseteq A$, we have for all $x \in U_n$, $(f(x), e_0) \in O$. Thus we know that $e_0 \in V_n$ for each $n \in \mathbb{N}$, and hence $e_0 \in V$. Moreover, for any $(x, e) \in U \times V$, there exists a natural number $n$ such that $e \in V_n$, then it follows that $f \times \mathrm{id}_E((x, e)) = (f(x), e) \in f(U) \times V_n \subseteq f(U_n) \times V_n \subseteq O$. The last inclusion is due to the construction of $V_n$. To sum up, it is true that $f \times \mathrm{id}_E(U \times V) \subseteq O$. Since $U$ is an open subset of $X$ which contains $x_0$ and $e_0 \in V$, we finish the proof by showing that $V$ is Scott open in $E$. To this end we let $\{e_i\}_{i \in I}$ be a directed subset of $E$ with $\sup_{i \in I} e_i \in V$. For each $i \in I$, set $W_i = \{x \in X \mid (f(x), e_i) \in O\}$. It is easy to see that $\{W_i \mid i \in I\}$ is a directed family of open subsets of $X$. Since $\sup_{i \in I} e_i \in V = \bigcup_{n \in \mathbb{N}} V_n$, $\sup_{i \in I} e_i$ is in some $V_n$. This means that for each $x \in U_n$, $(f(x), \sup_{i \in I} e_i) \in O$. Because $O$ is Scott open, for each $x \in U_n$, there exists $i \in I$ such that $(f(x), e_i) \in O$, i.e., $x \in W_i$. Hence we have that $\sup_{i \in I} e_i \in V_n \subseteq \bigcup_{i \in I} W_i$. Remember that $U_{n+1} \ll U_n$, it follows that $U_{n+1} \subseteq W_j$ for some $j \in I$. By definition of $W_j$, we know that $f(U_{n+1}) \times \{e_j\} \subseteq O$, which means that $e_j \in V_{n+1}$, this time by definition of $V_{n+1}$. So we find $j \in I$ with $e_j \in V_{n+1} \subseteq V$, and indeed $V$ is Scott open in $E$. ◀

**Theorem 4.** Let $X$ be a core-compact space and $f$ be a lower semi-continuous map from $X$ to a dcpo $D$. If $\nu$ is a valuation on $X$, then $f_*(\nu) \stackrel{\mathrm{def}}{=} \lambda O \in \sigma D.\nu(f^{-1}(O))$, the push-forward valuation along $f$, is a central valuation on $D$. In particular, for a core-compact dcpo $D$, all valuations on $D$ are central, i.e., $\mathcal{V}D = \mathcal{Z}D$.

**Proof.** By definition, we prove for any dcpo $E$, continuous valuations $\mu$ on $E$ and Scott-continuous map $h: D \times E \to [0, 1]$ the equation

$$ \int_{x \in D} \int_{y \in E} h(x, y) d\mu df_*(\nu) = \int_{y \in E} \int_{x \in D} h(x, y) df_*(\nu) d\mu $$

holds.

Note that for each $y \in E$, the map $g \stackrel{\mathrm{def}}{=} (x \mapsto \int_{y \in E} h(x, y) d\mu): D \to [0, 1]$ is Scott-continuous, and $f: X \to D$ is lower semi-continuous. Hence for the left side of the above equation we have

$$ \int_{x \in D} \int_{y \in E} h(x, y) d\mu df_*(\nu) = \int_{x \in X} g(f(x)) d\nu = \int_{x \in X} \int_{y \in E} h(f(x), y) d\mu d\nu. $$

The first equality follows from the so-called *change-of-variable* formula, which can be found in [4]. As a consequence of it, we also have that

$$ \int_{y \in E} \int_{x \in D} h(x, y) df_*(\nu) d\mu = \int_{y \in E} \int_{x \in X} h(f(x), y) d\nu d\mu. $$

Since $X$ is core-compact and the function $f: X \to D$ is lower semi-continuous, by Lemma 3 we know that $f \times \mathrm{id}_E: X \times \Sigma E \to X \times Y$ is lower semi-continuous. This implies that the map $(x, y) \mapsto h(f(x), y): X \times \Sigma E \to [0, 1]$ is lower semi-continuous. Hence by Lemma 2.37 in [4] we know that $\int_{x \in X} \int_{y \in E} h(f(x), y) d\mu d\nu = \int_{y \in E} \int_{x \in X} h(f(x), y) d\nu d\mu$, which finishes the proof.

The second claim is a straightforward consequence of the first one. ◀

**Theorem 5.** Let $f: [0, 1] \to D$ be a lower semi-continuous map into a dcpo $D$. If $\nu$ is any continuous valuation on $[0, 1]$, then $f_*(\nu)$ is a central valuation on $D$.

**Proof.** Since $[0, 1]$ is core-compact in the usual topology, the result follows from Theorem 4. ◀
We have not been able to establish the above theorem for any of the monads *M*, *W* or *P*,
so we believe that *Z* is a promising candidate for modeling *continuous probabilistic choice*.
We plan to address this in future work.

References

1 Jean Goubault-Larrecq, Xiaodong Jia, and Clément Théron. A Domain-Theoretic Approach to Statistical Programming Languages, 2021. Preprint. URL: https://arxiv.org/abs/2106.16190.

2 Xiaodong Jia, Bert Lindenhovius, Michael Mislove, and Vladimir Zamdzhiev. Commutative monads for probabilistic programming languages. In *Logic in Computer Science (LICS 2021)*, 2021. arXiv:2102.00510.

3 C. Jones and Gordon D. Plotkin. A probabilistic powerdomain of evaluations. In *Proceedings of the Fourth Annual Symposium on Logic in Computer Science (LICS '89)*, Pacific Grove, California, USA, June 5-8, 1989, pages 186-195. IEEE Computer Society, 1989. doi:10.1109/LICS.1989.39173.

4 Claire Jones. *Probabilistic Non-determinism*. PhD thesis, University of Edinburgh, UK, 1990.
URL: http://hdl.handle.net/1842/413.

5 Achim Jung and Regina Tix. The troublesome probabilistic power domain. In *Comprox III, Third Workshop on Computation and Approximation*, volume 13, pages 70–91, 1998.

6 John Power and Edmund Robinson. Premonoidal Categories and Notions of Computation. *Math. Struct. Comput. Sci.*, 7(5):453–468, 1997. doi:10.1017/S0960129597002375.