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