<p>The comment below is correct, but it's important to understand the meaning of "finite" or "compact" elements of a domain. These are the denotations of objects computable in finite time, so their appearance in a semantic model is not for proof-theoretic convenience - they represent the strong connection between the model and actual computation. </p>

CC BY-SA 3.0
2015-04-06T02:11:59.893Z
2015-04-06T02:11:59.893Z
Michael Mislove
<p>Well, Mislove's quote already contains a positive answer: the category of dcpos is carteisan closed and also closed under the probabilistic powerdomain. It can indeed be used to give a denotational semantics to higher-order probabilistic computation. However, dcpos fail to satisfy the "usual approximation assumptions" that every element can be approximated by "finite" elements in some sense, as is the case for algebraic and continuous cpos. These assumptions help with certain denotational arguments but are not needed to give a semantics per se. </p>

CC BY-SA 3.0
2015-02-22T12:05:06.107Z
2015-02-22T12:05:06.107Z
user32177
<p>The following is an extended comment, it does not answer your question in the terms you posed it but does give a semantics for higher-order probabilistic calculi which you may find of interest.</p>

<p>In the past few years there has been a very active line of research around so-called <em>quantitative denotational semantics</em> of linear logic, based on the idea (originally due to Girard [1]) that higher-order programs may be modeled by power series.  In the probabilistic case, this takes the form of so-called <em>probabilistic coherence spaces</em> (PCS), also introduced by Girard [2] and studied in depth by Danos and Ehrhard [3].  PCS yield models of both typed and untyped probabilistic calculi which are of a very different nature than power domains and other monad-related models.  In particular, PCS give what is thus far the only known fully abstract model of probabilistic PCF [4], which is notoriously difficult and seemingly impossible to achieve with power domains (cf. the work of <a href="http://www.lsv.ens-cachan.fr/~goubault/" rel="nofollow">Jean Goubault-Larrecq</a>).</p>

<p>Apart from Ehrhard, quantitative semantics is now actively developed by <a href="http://www.pps.univ-paris-diderot.fr/~pagani/" rel="nofollow">Michele Pagani</a> and coauthors, I suggest you look at his web page for additional references.</p>

<p>[1] Jean-Yves Girard, Normal functors, power series and $\lambda$-calculus. Annals of Pure and Applied Logic 37 (2):129-177, 1988.</p>

<p>[2] Jean-Yves Girard, <a href="http://iml.univ-mrs.fr/~girard/LLcup.pdf.gz" rel="nofollow">Between logic and quantic: a tract</a>. In <em>Linear logic in computer science</em>, CUP, 2004.</p>

<p>[3] Vincent Danos and Thomas Ehrhard, <a href="http://www.pps.univ-paris-diderot.fr/~danos/pdf/pcsaamohpc.pdf" rel="nofollow">Probabilistic coherence spaces as a model of higher-order probabilistic computation</a>. Information and Computation 209(6): 966-991, 2011.</p>

<p>[4] Thomas Ehrhard, Michele Pagani and Christine Tasson, <a href="http://www.pps.univ-paris-diderot.fr/~pagani/fapcoh.pdf" rel="nofollow">Probabilistic coherence spaces are fully abstract for probabilistic PCF</a>. In <em>Proceedings of POPL</em>, pp. 309-320, 2014.</p>

CC BY-SA 3.0
2014-12-30T22:06:51.420Z
2014-12-31T05:28:44.617Z
2014-12-31T05:28:44.617Z
Damiano Mazza
<p>Equivalently, is there a known denotational semantics for probabilistic higher-order functional programming languages? Specifically, is there a domain model of pure untyped $\lambda$-calculus extended by a symmetric random binary choice operation.</p>

<h3>Motivation</h3>

<p>Cartesian closed categories provide a semantics to higher-order $\lambda$-calculi. Probabilistic powerdomains provide semantics to stochastic programs. A CCC closed under a probabilistic powerdomain operation would provide a semantics to a stochastic higher-order functional programming language.</p>

<h3>Related Work</h3>

<p>Tix, Keimel, and Plotkin (2004) [1] give modern constructions of the lower-, upper-, and convex- powerdomain operations, but remark that</p>

<blockquote>
  <p>It still is an open problem whether there is a cartesian closed category of continuous domains which is closed under the construction of probabilistic powerdomains.</p>
</blockquote>

<p>Mislove (2013) [2,3] gives semantics for continuous random variables in a first-order language, but remarks that</p>

<blockquote>
  <p>Even though the probabilistic power domain leaves the CCC of directed complete posets (dcpos, for short) and Scott-continuous maps invariant, there is no Cartesian closed category of domains – dcpos that satisfy the usual approximation assumption – that is known to be invariant under this construct. The best that is known is that the category of coherent domains is invariant under the probabilistic choice monad [4], but this category is not Cartesian closed.</p>
</blockquote>

<h3>References</h3>

<ol>
<li>Regina Tix, Klaus Keimel, and Gordon Plotkin (2004)
<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.714&amp;rep=rep1&amp;type=pdf" rel="nofollow">"Semantic domains for combining probability and non-determinism"</a>.</li>
<li>Michael Mislove (2013)
<a href="http://www.entcs.org/mislove/anatomy1.pdf" rel="nofollow">"Anatomy of a domain of continuous random variables I"</a></li>
<li>Michael Mislove (2013)
<a href="http://www.entcs.org/mislove/anatomy2.pdf" rel="nofollow">"Anatomy of a domain of continuous random variables II"</a></li>
<li>Jung, A. and R. Tix (1998)
<a href="http://www.cs.bham.ac.uk/~axj/pub/papers/Jung-Tix-1998-The-troublesome-probabilistic-powerdomain.pdf" rel="nofollow">"The troublesome probabilistic powerdomain"</a></li>
</ol>

<pr.probability><lambda-calculus><ct.category-theory><denotational-semantics><domain-theory>
Is there any known CCC closed under a probabilistic powerdomain operation?
fritzo
# Is there any known CCC closed under a probabilistic powerdomain operation?

(Asked by: username_0 on 2014-12-30)

Equivalently, is there a known denotational semantics for probabilistic higher-order functional programming languages? Specifically, is there a domain model of pure untyped $\lambda$-calculus extended by a symmetric random binary choice operation.

### Motivation

Cartesian closed categories provide a semantics to higher-order $\lambda$-calculi. Probabilistic powerdomains provide semantics to stochastic programs. A CCC closed under a probabilistic powerdomain operation would provide a semantics to a stochastic higher-order functional programming language.

### Related Work

Tix, Keimel, and Plotkin (2004) [1] give modern constructions of the lower-, upper-, and convex- powerdomain operations, but remark that

> It still is an open problem whether there is a cartesian closed category of continuous domains which is closed under the construction of probabilistic powerdomains.

Mislove (2013) [2,3] gives semantics for continuous random variables in a first-order language, but remarks that

> Even though the probabilistic power domain leaves the CCC of directed complete posets (dcpos, for short) and Scott-continuous maps invariant, there is no Cartesian closed category of domains – dcpos that satisfy the usual approximation assumption – that is known to be invariant under this construct. The best that is known is that the category of coherent domains is invariant under the probabilistic choice monad [4], but this category is not Cartesian closed.

### References

1. Regina Tix, Klaus Keimel, and Gordon Plotkin (2004)
   ["Semantic domains for combining probability and non-determinism"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.714&rep=rep1&type=pdf).
2. username_1 (2013)
   ["Anatomy of a domain of continuous random variables I"](http://www.entcs.org/mislove/anatomy1.pdf)
3. username_1 (2013)
   ["Anatomy of a domain of continuous random variables II"](http://www.entcs.org/mislove/anatomy2.pdf)
4. Jung, A. and R. Tix (1998)
   ["The troublesome probabilistic powerdomain"](http://www.cs.bham.ac.uk/~axj/pub/papers/Jung-Tix-1998-The-troublesome-probabilistic-powerdomain.pdf)

**Tags:** pr.probability, lambda-calculus, ct.category-theory, denotational-semantics, domain-theory


---

## 3 answers

### Answer by username_3 on 2014-12-30. Score: 10 | Accepted answer

The following is an extended comment, it does not answer your question in the terms you posed it but does give a semantics for higher-order probabilistic calculi which you may find of interest.

In the past few years there has been a very active line of research around so-called *quantitative denotational semantics* of linear logic, based on the idea (originally due to Girard [1]) that higher-order programs may be modeled by power series. In the probabilistic case, this takes the form of so-called *probabilistic coherence spaces* (PCS), also introduced by Girard [2] and studied in depth by Danos and Ehrhard [3]. PCS yield models of both typed and untyped probabilistic calculi which are of a very different nature than power domains and other monad-related models. In particular, PCS give what is thus far the only known fully abstract model of probabilistic PCF [4], which is notoriously difficult and seemingly impossible to achieve with power domains (cf. the work of [Jean Goubault-Larrecq](http://www.lsv.ens-cachan.fr/~goubault/)).

Apart from Ehrhard, quantitative semantics is now actively developed by [Michele Pagani](http://www.pps.univ-paris-diderot.fr/~pagani/) and coauthors, I suggest you look at his web page for additional references.

[1] Jean-Yves Girard, Normal functors, power series and $\lambda$-calculus. Annals of Pure and Applied Logic 37 (2):129-177, 1988.

[2] Jean-Yves Girard, [Between logic and quantic: a tract](http://iml.univ-mrs.fr/~girard/LLcup.pdf.gz). In *Linear logic in computer science*, CUP, 2004.

[3] Vincent Danos and Thomas Ehrhard, [Probabilistic coherence spaces as a model of higher-order probabilistic computation](http://www.pps.univ-paris-diderot.fr/~danos/pdf/pcsaamohpc.pdf). Information and Computation 209(6): 966-991, 2011.

[4] Thomas Ehrhard, Michele Pagani and Christine Tasson, [Probabilistic coherence spaces are fully abstract for probabilistic PCF](http://www.pps.univ-paris-diderot.fr/~pagani/fapcoh.pdf). In *Proceedings of POPL*, pp. 309-320, 2014.


---

### Answer by username_1 on 2015-04-06. Score: 4

The comment below is correct, but it's important to understand the meaning of "finite" or "compact" elements of a domain. These are the denotations of objects computable in finite time, so their appearance in a semantic model is not for proof-theoretic convenience - they represent the strong connection between the model and actual computation.


---

### Answer by username_2 on 2015-02-22. Score: 2

Well, Mislove's quote already contains a positive answer: the category of dcpos is carteisan closed and also closed under the probabilistic powerdomain. It can indeed be used to give a denotational semantics to higher-order probabilistic computation. However, dcpos fail to satisfy the "usual approximation assumptions" that every element can be approximated by "finite" elements in some sense, as is the case for algebraic and continuous cpos. These assumptions help with certain denotational arguments but are not needed to give a semantics per se.


---

