# [Haskell-cafe] Help on syntactic sugar for combining lazy & strict monads?

Benjamin Redelings benjamin.redelings at gmail.com
Tue Aug 10 15:57:15 UTC 2021

Hi Olaf,

If you recall, I actually wrote to this list asking for help. Adam
Scibior's response was quite helpful, but this conversation, as far as I
can tell, has not provided any help, so I will regretfully have to stop
replying at some point.  Unfortunately, I don't have enough time to
respond to everything - my apologies!

I may be able to clarify some of the questions that you asked. But I
doubt that I can actually satisfy all of your concerns.  So, perhaps
these responses will mostly clarify our points of disagreement.

1. It seems like you are assuming that the semantics of a probabilistic
program is determined by running it under a rejection sampling
interpreter.  Such an interpreter would:

(a) interpret statements like "x <- normal 0 1" by performing a
(pseudo)random sample from the distribution

(b) interpret statements like "2.0 observed_from normal z 1" by
first sampling from "normal z 1" and then rejecting the program run if
the sample from "normal z 1" does not satisfy (2.0==).

That is a rejection sampler, and it would work if the observations did
not have probability 0.  But it is only one kind of sampler.  There are
other kinds of samplers, that you (maybe?) have not considered:

* importance sampling: the paper that I recommended is using the
observation statements to weight the samples by the probability DENSITY
of the observations.  This is called "importance sampling" -- we
generate sampling from one distribution, but reweight them to
approximate a different distribution.

* MCMC: my approach is based on MCMC, and so performs a random walk
over the space of program traces.  In this case, running the program
must compute the probability DENSITY of samples from the prior (like "x
<- normal 0 1") as well as observations (like observing 2.0 from "normal
z 1").

These three alternative interpreters are alternative ways of sampling
from the posterior distribution.  However, none of these three
interpreters constitutes the semantics of the probabilistic program.

I mentioned the Giry monad (which I am no expert on) because it gives
semantics that is not based on any interpreter.  I do not think that the
semantics of probabilistic programs should be given by an interpreter.
Perhaps we disagree on this.

2. You wrote "If the observe_from statement is never demanded, then what
semantics should it have?"

> run_lazy do > x <- normal 0 1 > y <- normal x 1 > z <- normal y 1 > 2.0 observe_from normal z 1 > return y The semantics that it should have seems fairly obvious? This program leads to the following (un-normalized!) probability density on (x,y,z): Pr(x) * Pr(y|x) * Pr(z|y) * Pr(2.0|z) = normal_pdf(x,0,1) * normal_pdf(y,x,1) * normal_pdf(z,y,1) * normal_pdf(2.0,z,1) Therefore, the program leads to both (i) a distribution on (x,y,z) and (ii) a distribution on the return value y. I don't think this has anything to to with whether there is a result that is demanded, but perhaps we disagree on that. 3. You wrote "But conditioning usually is a function "Observation a -> Dist a -> Dist a" so you must use the result of the conditioning somehow." I was initially very confused by this, because it sounded like you are saying that because people USUALLY do something, therefore I HAVE AN OBLIGATION to do something. But, now I realize that you mean "IT MUST BE THE CASE that you use the result of the conditioning somehow". It is indeed the case that the "observe_from" command affects the intepreter somehow. I think this is pretty simple ... the observe_from statement has a side-effect. For both (i) importance-sampling interpreters and (ii) MCMC interpreters, the side-effect is to weight the current trace by the probability (or probability density) of the observation. However, like the "put" command in the state monad, the result "()" of the observation is not demanded. So in that sense, I am not "using the result". It is perhaps interesting that the lazy state monad does not have the problem that "put" commands are ignored. 4. You wrote "And isn't the principle of Monte Carlo to approximate the posterior by sampling from it?" I am not really sure what this means. Sometimes you can generate samples directly from the posterior, and sometimes you can't. In most situations where you have observations, you CANNOT generate samples from the posterior. For example, in MCMC, we talk about the distribution of the sampled points CONVERGING to the posterior. If an MCMC chain has points X[t] for t = 0...\infty, there is no t where X[t] is distributed according to the posterior distribution. 5. You wrote "I claim that once you have typed everything, it becomes clear where the problem is." That is an interesting claim. I don't think that there is actually "problem" per se, so I am not were that typing everything can reveal where it is. Also, this exact same issue comes up in the Practical Probabilistic Programming with Monads paper, and they have typed everything. So, I guess I disbelieve this claim, until I see evidence to the contrary. I guess we will see, after I finish programming the type system. 6. You wrote: > I believe I understand the Giry monad well, and it is my measuring > stick for functional probabilistic programming. Even more well-suited > for programming ought to be the valuation monad, because that is a > monad on domains, the [*] semantic spaces of the lambda calculus. > Unfortunately, to my knowledge until now attempts were unsuccessful to > find a cartesian closed category of domains which is also closed under > this probabilistic powerdomain construction. > > [*] There are of course other semantics, domains being one option. Given your expertise in this area, I doubt that I can shed any light on this. I presume that you have read https://arxiv.org/pdf/1811.04196.pdf, and similar papers. This is getting pretty far afield from my original question. 7. You wrote: >> >> 2. The paper "Practical Probabilistic Programming with Monads" - >> https://doi.org/10.1145/2804302.2804317 > > Wasn't that what you linked to in your original post? As said above, > measure spaces is the wrong target category, in my opinion. There is > too much non constructive stuff in there. See the work of Culbertson > and Sturtz, which is categorically nice but not very constructive. The link was indeed in my original post, but it did not seem like you had read it, since you did not consider the possibility of probabilistic programs generating WEIGHTED samples. Also, the idea that probabilistic programs should not yield measures seems weird. Partly because I am not sure what your alternative is, and partly because everybody else seems to disagree with you. For example, the following paper assumes measures: https://link.springer.com/chapter/10.1007/978-3-030-72019-3_16 Again, this is getting pretty far away from my original question. 8. You wrote: > Perhaps I am being too much of a point-free topologist here. Call me > pedantic. Or I don't understand sampling at all. To me, a point is an > idealised object, only open sets really exist and are observable. If > the space is discrete, points are open sets. But on the real line you > can not measure with infinite precision, so any observation must > contain an interval. That aligns very nicely with functional > programming, where only finite parts of infinite lazy structures are > ever observable, and these finite parts are the open sets in the > domain semantics. So please explain how observing 2.0 from a > continuous distribution is not nonsensical. You haven't actually shown that observing 2.0 from a continuous distribution is nonsensical. What you have done is stated that you don't like it, and that you would like people to represent observations as intervals instead of points. However, its not my job to convince you that point observations make sense, so I think I'll just leave that where it is. OK, that's enough for now. -BenRI On 7/22/21 2:15 AM, Olaf Klinke wrote: >> However, a lazy interpreter causes problems when trying to introduce >> *observation* statements (aka conditioning statements) into the monad >> [3]. For example, >> >> run_lazy do
>>    x <- normal 0 1
>>    y <- normal x 1
>>    z <- normal y 1
>>    2.0 observe_from normal z 1
>>    return y
>>
>> In the above code fragment, y will be forced because it is returned, and
>> y will force x.  However, the "observe_from" statement will never be
>> forced, because it does not produce a result that is demanded.
>
> I'm very confused. If the observe_from statement is never demanded,
> then what semantics should it have? What is the type of observe_from?
> It seems it is
> a -> m a -> m ()
> for whatever monad m you are using. But conditioning usually is a
> function
> Observation a -> Dist a -> Dist a
> so you must use the result of the conditioning somehow. And isn't the
> principle of Monte Carlo to approximate the posterior by sampling from
> it? I tend to agree with your suggestion that observations and
> sampling can not be mixed (in the same do-notation) but the latter
> have to be collected in a prior, then conditioned by an observation.
>
> What is the semantic connection between your sample and obsersvation
> monad? What is the connection between both and the semantic
> probability distributions? I claim that once you have typed
> everything, it becomes clear where the problem is.
>
> Olaf
>
> P.S. It has always bugged me that probabilists use elements and events
> interchangingly, while this can only be done on discrete spaces. So
> above I would rather like to write
> (2.0==) observe_from (normal 0 1)
> which still is a non-sensical statement if (normal 0 1) is a
> continuous distribution where each point set has probability zero.
-------------- next part --------------
An HTML attachment was scrubbed...
`