Stochastic lambda calculus and monads of probability distributions
Authors:
Open Access
- 1 January 2002
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 37 (1) , 154-165
Abstract
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 theexpectationquery can be much less efficient than current best practices in probabilistic modeling. We therefore present a language ofmeasure 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.Keywords
This publication has 17 references indexed in Scilit:
- QuickCheck2000
- Stochastic processes as concurrent constraint programs1999
- Type-directed partial evaluation1996
- A calculus of stochastic systems for the specification, simulation, and hidden state estimation of mixed stochastic/nonstochastic systemsTheoretical Computer Science, 1995
- Efficient inference in Bayes networks as a combinatorial optimization problemInternational Journal of Approximate Reasoning, 1994
- Why Functional Programming MattersThe Computer Journal, 1989
- BAYESIAN INFERENCE1988
- Arithmetic coding for data compressionCommunications of the ACM, 1987
- A categorical approach to probability theory1982
- Cpo's of measures for nondeterminismTheoretical Computer Science, 1980