A model of stochastic memoization and name generation in probabilistic programming: categorical semantics via monads on presheaf categories

Stochastic memoization is a higher-order construct of probabilisticprogramming languages that is key in Bayesian nonparametrics, a modularapproach that allows us to extend models beyond their parametric limitationsand compose them in an elegant and principled manner. Stochastic memoization issimple and useful in practice, but semantically elusive, particularly regardingdataflow transformations. As the naive implementation resorts to the statemonad, which is not commutative, it is not clear if stochastic memoizationpreserves the dataflow property -- i.e., whether we can reorder the lines of aprogram without changing its semantics, provided the dataflow graph ispreserved. In this paper, we give an operational and categorical semantics tostochastic memoization and name generation in the context of a minimalprobabilistic programming language, for a restricted class of functions. Ourcontribution is a first model of stochastic memoization of constant Bernoullifunctions with a non-enumerable type, which validates data flowtransformations, bridging the gap between traditional probability theory andhigher-order probability models. Our model uses a presheaf category and a novelprobability monad on it.Comment: To be published in the MFPS 2023 Proceedings as part of the Electronic Notes in Theoretical Informatics and Computer Science (ENTICS) serie