What is the right notion of module for probabilistic programs?
Purely probabilistic program modules (i.e., those not using internal state) are exchangeable: calls can be commuted and discarded without changing the behaviour.
In general, memory access is neither commutative nor discardable. However, there are many interesting probabilistic program modules that involve state privately, but from the perspective of the user are exchangeable. A source of examples are the Exchangeable Random Processes (XRPs), such as Polya’s urn implementation of the Beta-Bernoulli process.
Suppose a module’s external behavior is exchangeable. Does that mean that there is an implementation of that module that is purely probabilistic, i.e., without using state even internally?
Authors: Nate Ackerman, Cameron Freer, Dan Roy, Sam Staton, Hongseok Yang.
Extended abstract: [PDF]