[Haskell-cafe] Explicit approach to lazy effects For probability monad?

[Jared Tobin]

On Wed, Nov 13, 2019 at 11:58:59AM -0500, Benjamin Redelings wrote:
> On 11/10/19 4:21 PM, Olaf Klinke wrote:
> > I believe that with the right monad, you won't need to think about
> > side-effects, at least not the side-effects that are manual fiddling
> > with registering variables. Haskell should do that for you.
>
> So, I'm trying to implement a random walk on the space of Haskell
> program traces.
>
> This means that logically Haskell is kind of running at two levels:
>
> (1) there is an inner random program that we are making a trace of.
>
> (2) there is another outer program that modifies these traces.
>
> [..]
>
> So, I'm not sure if it is correct that I would not need side-effects. 
> However, if I could avoid side-effects, that would be great.

FWIW, I believe it's possible to avoid effects, though I'm not sure if
it can be done particularly efficiently.

Instead of maintaining an external "database of randomness" (à la
Wingate et al. 2011 -- i.e. the "registered" variables that you can
supply randomness to), you should be able to directly annotate
probabilistic nodes in your syntax tree with PRNG state snapshots.  When
you need randomness for the "outer program" semantics, you just iterate
the PRNG states on-site.

The representationally elegant way to do this seems to be to use a free
monad to denote your probabilistic programs and a cofree comonad to
represent their execution traces.  The cofree comonad allows you to
annotate the probabilistic syntax tree nodes with the required state
(parameter space value, log-likelihood, PRNG state), and then perturb
them lazily as required via a comonadic 'extend'.

I wrote up a couple of prototypes of this sort of setup awhile back:

  * https://jtobin.io/simple-probabilistic-programming
  * https://jtobin.io/comonadic-mcmc

Whether this can yield anything usefully efficient is an open question.
It does avoid the annoying "observe" and "sample" syntax, at least.

-- jared
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: not available
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20191114/644f265e/attachment.sig>