Stochastic Lambda Calculus and Monads of Probability Distributions
Probability distributions are
useful for expressing the meanings of
probabilistic languages, which support formal modeling of and reasoning
about uncertainty.
Probability distributions form a monad,
and the monadic definition leads to a simple, natural
semantics for
a stochastic
lambda calculus, as well as simple,
clean implementations of common queries.
But the monadic implementation of the expectation query
can be much less efficient than current best practices in
probabilistic modeling.
We therefore present a language of measure terms, which
can not only denote discrete probability distributions but can also support the
best known modeling techniques.
We give a translation of stochastic lambda calculus into measure
terms.
Whether one translates into the probability
monad or into measure terms, the results of the translations denote
the same probability distribution.
Full paper
The paper is available as
US Letter PostScript (439K),
US Letter PDF (289K---may be flaky),
and
US Letter TeX DVI (99K).
You can also see slide from a talk delivered at POPL'02.