<p>One apparent strength of his approach is that it allows higher-order functions (i.e. lambda terms) to be observable outcomes, which measure theory generally makes quite tricky. (The basic problem is that spaces of measurable functions generally have no Borel $\sigma$-algebra for which the application function - sometimes called "eval" - is measurable; see the intro to the paper <a href="http://projecteuclid.org/euclid.ijm/1255631584">Borel structures for function spaces</a>.) Scott does this using a Gödel encoding from lambda terms to natural numbers, and working directly with the encoded terms. One weakness to this approach may be that the encoding could be difficult to extend with real numbers as program values. (Edit: This is not a weakness - see Andrej's comment below.)</p>

<p>Using CPS seems to be primarily for imposing a total order on computations, to impose a total order on access to the random source. The state monad should do just as well.</p>

<p>Scott's "random variables" seem to be the same as Park's "sampling functions" in his <a href="https://www.cs.cmu.edu/~fp/papers/popl05.pdf">operational semantics</a>. The technique of transforming standard-uniform values into values with any distribution is more widely known as <a href="http://en.wikipedia.org/wiki/Inverse_transform_sampling">inverse transform sampling</a>.</p>

<p>I believe there's just one fundamental difference between Ramsey's and Scott's semantics. Ramsey's interprets programs as computations that build a measure on program outputs. Scott's assumes an existing uniform measure on <em>inputs</em>, and interprets programs as transformations of those inputs. (The output measure can in principle be computed using <a href="http://en.wikipedia.org/wiki/Pushforward_measure">preimages</a>.) Scott's is analogous to using the Random monad in Haskell.</p>

<p>In its overall approach, Scott's semantics seems most similar to the second half of <a href="http://students.cs.byu.edu/~ntoronto/dissertation.pdf">my dissertation on probabilistic languages</a> - except I stuck with first-order values instead of using a clever encoding, used infinite trees of random numbers instead of streams, and interpreted programs as arrow computations. (One of the arrows computes the transformation from the fixed probability space to program outputs; the others compute preimages and approximate preimages.) My dissertation's chapter 7 explains why I think interpreting programs as transformations of a fixed probability space is better than interpreting them as computations that build a measure. It basically comes down to "fixpoints of measures are way complicated, but we understand fixpoints of programs pretty well."</p>

CC BY-SA 3.0
2014-10-10T09:12:10.600Z
Quick question: there are lot's of probabilistic process calculi. It's known that $\lambda$-calculi can be embedded precisely into process calculi (I'm simplifying a bit), following Milner's pioneering [Functions as Processes](http://hal.inria.fr/inria-00075405/en). If we use Milner's techniques to embed a $\lambda$-calculus in a probabilistic process calculus, we get a probabilistic $\lambda$-calculus. What would be the relationship between that and Scott's approach?
Martin Berger
CC BY-SA 3.0
2014-10-10T11:41:33.323Z
@Martin: I really can't answer that quickly because I don't know much about process calculi, but it seems like it would be worth looking into. I'd be curious to know what the properties of the process calculi look like after transferring them over, and whether the transferred properties could be leveraged in any way.
Neil Toronto
CC BY-SA 3.0
2014-10-10T11:48:10.183Z
Every countably based $T_0$-space embeds in the graph model. Via this embedding we can then happily marry $\lambda$-calculus with topology and compute with, say, real numbers. The embedding is quite natural: a point is represented by the filter of its basic neighborhoods.
Andrej Bauer
CC BY-SA 3.0
2014-10-10T11:54:06.027Z
@Andrej: So extending the encoding with real numbers shouldn't be a problem, then?
Neil Toronto
CC BY-SA 3.0
2014-10-10T11:56:12.513Z
As I said, as soon as you choose a countable base $(B_n)_n$ on a $T_0$-space that gives you an encoding of the space: a point $x$ is encoded as the set $\{n \in \mathbb{N} \mid x \in B_n\}$.
Andrej Bauer
CC BY-SA 3.0
2014-10-10T13:48:13.603Z
@NeilToronto Yes, it's an interesting subject. There is a large number of different process calculi, and several different ways of turning them stochastic. There are also different ways of encoding $\lambda$-calculus. The precise stochastic  $\lambda$-calculus on arrives at by reflecting the encoding would depend on all these details.
Martin Berger
CC BY-SA 3.0
2014-10-10T03:01:49.643Z
2014-10-10T11:58:07.700Z
2014-10-10T11:58:07.700Z
Neil Toronto
<p>Recently, Dana Scott proposed stochastic lambda calculus, an attempt to introduce probabilistic elements into (untyped) lambda calculus based on a semantics called graph model.  You can find his slides on line for example <a href="http://www.humboldt-kolleg.iam.unibe.ch/talks/Scott.pdf">here</a> and his paper in <em>Journal of Applied
Logic</em>, vol. 12 (2014).</p>

<p>However, by a quick search on the Web, I found similar previous research, for example, <a href="http://www.cs.tufts.edu/~nr/pubs/pmonad.pdf">that for Hindley-Milner type system</a>.  The way they introduce probabilistic semantics is similar to Scott's (in the former, they use monads while in the latter Scott uses continuation-passing style).</p>

<p>In which way is the Scott's work different from previous work available, in terms of theories themselves or their possible applications?</p>

CC BY-SA 3.0
2015-12-22T18:13:49.677Z
Since it took me a while to find it, here's a link:
http://www.sciencedirect.com/science/article/pii/S1570868314000238
Blaisorblade
<lo.logic><pl.programming-languages><lambda-calculus>
Scott's stochastic lambda calculi
Pteromys
# Scott's stochastic lambda calculi

(Asked by: username_0 on 2014-10-08)

Recently, Dana Scott proposed stochastic lambda calculus, an attempt to introduce probabilistic elements into (untyped) lambda calculus based on a semantics called graph model. You can find his slides on line for example [here](http://www.humboldt-kolleg.iam.unibe.ch/talks/Scott.pdf) and his paper in *Journal of Applied
Logic*, vol. 12 (2014).

However, by a quick search on the Web, I found similar previous research, for example, [that for Hindley-Milner type system](http://www.cs.tufts.edu/~nr/pubs/pmonad.pdf). The way they introduce probabilistic semantics is similar to Scott's (in the former, they use monads while in the latter Scott uses continuation-passing style).

In which way is the Scott's work different from previous work available, in terms of theories themselves or their possible applications?

**Tags:** lo.logic, pl.programming-languages, lambda-calculus
> **Comments:**
> **username_1**: Since it took me a while to find it, here's a link: http://www.sciencedirect.com/science/article/pii/S1570868314000238  

---

## 1 answers

### Answer by username_2 on 2014-10-10. Score: 15 | Accepted answer

One apparent strength of his approach is that it allows higher-order functions (i.e. lambda terms) to be observable outcomes, which measure theory generally makes quite tricky. (The basic problem is that spaces of measurable functions generally have no Borel $\sigma$-algebra for which the application function - sometimes called "eval" - is measurable; see the intro to the paper [Borel structures for function spaces](http://projecteuclid.org/euclid.ijm/1255631584).) Scott does this using a Gödel encoding from lambda terms to natural numbers, and working directly with the encoded terms. One weakness to this approach may be that the encoding could be difficult to extend with real numbers as program values. (Edit: This is not a weakness - see Andrej's comment below.)

Using CPS seems to be primarily for imposing a total order on computations, to impose a total order on access to the random source. The state monad should do just as well.

Scott's "random variables" seem to be the same as Park's "sampling functions" in his [operational semantics](https://www.cs.cmu.edu/~fp/papers/popl05.pdf). The technique of transforming standard-uniform values into values with any distribution is more widely known as [inverse transform sampling](http://en.wikipedia.org/wiki/Inverse_transform_sampling).

I believe there's just one fundamental difference between Ramsey's and Scott's semantics. Ramsey's interprets programs as computations that build a measure on program outputs. Scott's assumes an existing uniform measure on *inputs*, and interprets programs as transformations of those inputs. (The output measure can in principle be computed using [preimages](http://en.wikipedia.org/wiki/Pushforward_measure).) Scott's is analogous to using the Random monad in Haskell.

In its overall approach, Scott's semantics seems most similar to the second half of [my dissertation on probabilistic languages](http://students.cs.byu.edu/~ntoronto/dissertation.pdf) - except I stuck with first-order values instead of using a clever encoding, used infinite trees of random numbers instead of streams, and interpreted programs as arrow computations. (One of the arrows computes the transformation from the fixed probability space to program outputs; the others compute preimages and approximate preimages.) My dissertation's chapter 7 explains why I think interpreting programs as transformations of a fixed probability space is better than interpreting them as computations that build a measure. It basically comes down to "fixpoints of measures are way complicated, but we understand fixpoints of programs pretty well."

> **Comments:**
> **username_3**: Quick question: there are lot's of probabilistic process calculi. It's known that $\lambda$-calculi can be embedded precisely into process calculi (I'm simplifying a bit), following Milner's pioneering [Functions as Processes](http://hal.inria.fr/inria-00075405/en). If we use Milner's techniques to embed a $\lambda$-calculus in a probabilistic process calculus, we get a probabilistic $\lambda$-calculus. What would be the relationship between that and Scott's approach?  
> **username_2**: @Martin: I really can't answer that quickly because I don't know much about process calculi, but it seems like it would be worth looking into. I'd be curious to know what the properties of the process calculi look like after transferring them over, and whether the transferred properties could be leveraged in any way.  
> **username_4**: Every countably based $T_0$-space embeds in the graph model. Via this embedding we can then happily marry $\lambda$-calculus with topology and compute with, say, real numbers. The embedding is quite natural: a point is represented by the filter of its basic neighborhoods.  
> **username_2**: @Andrej: So extending the encoding with real numbers shouldn't be a problem, then?  
> **username_4**: As I said, as soon as you choose a countable base $(B_n)_n$ on a $T_0$-space that gives you an encoding of the space: a point $x$ is encoded as the set $\{n \in \mathbb{N} \mid x \in B_n\}$.  
> **username_3**: @NeilToronto Yes, it's an interesting subject. There is a large number of different process calculi, and several different ways of turning them stochastic. There are also different ways of encoding $\lambda$-calculus. The precise stochastic  $\lambda$-calculus on arrives at by reflecting the encoding would depend on all these details.  

---

