# A probabilistic language

Probabilistic programming languages are an attempt to unify a
variety of probabilistic models. For instance, Koller et al's
stochastic lambda calculus [2], and Pfeffer's

IBAL
language [3], both can express tree- and table- structured
distributions, Bayes nets, and probabilistic grammars. Ideally, the
language user should just have to worry about specifying the model,
while the implementation takes care of the probability "bookkeeping"
for inference and learning.

I implemented inference for a similar language using the
probability monad.

## The probability monad

Monads are an idea
from category theory, which are used in the functional language Haskell to encapsulate IO and
state-changing effects. Probability distributions form a monad. [4]

The probability monad provides four building blocks with which to
build probabilistic programs:

- choose p A B -
returns A's result with
probability p, B's result with probability 1-p
- then A B - samples A, then returns B (which can depend on A's result)
- return x - always
results in x (i.e., with
probability 1)
- observe p A - returns
the result of A, only in
cases when p is true

(

observe isn't in the basic
probability monad, but it is a fundamental operation in Pfeffer's IBAL
language.) The naive implementations of sampling and support are
efficient, but the naive implementation of inference (and therefore
learning) can take exponentially longer, because it ignores conditional
independence.

## Implementation

I implemented the probability monad in

R4RS
Scheme. (It also requires the

SLIB
library.) The

source,
distributed under the GNU

Lesser General Public
License, was developed using UMB Scheme.

I used

call-with-current-continuation
(also known as

call/cc) to
make inference take advantage of conditional independence. The
implementation of

then A B
starts out by assuming that the distribution of

A isn't needed. But, if it is
needed, then

call/cc calls
a function which computes

A's
distribution, and uses that to compute

B's distribution.

### Strengths

The resulting
implementation is concise - less than 200 lines of Scheme code. It is
well-integrated with the host language; probabilistic programs can use
Scheme programs and built-in functions, and Scheme programs can call
inference routines.

### Weaknesses

The implementation
requires call/cc, which
is in the R4RS standard, but tricky to implement efficiently. Also, it
still wastes some effort (because call/cc
throws out some work)

I haven't
implemented EM so far.

The syntax for
probabilistic programs is awkward. Haskell's do-notation would help,
but Haskell doesn't have call/cc.

There also need to be more test programs.

### To do

choose should be
generalized to return one of several results.

EM should be implemented.

I'd like to avoid using

call/cc,
possibly using

arrows [1],
which are a generalisation of monads.

## References

[1] Hughes, John. 2000. Generalising Monads to Arrows. In

Science of Computer Programming 37,
pp67-111, May 2000.

[2] Koller, Daphne, David McAllester, and Avi Pfeffer. 1997.
Effective Bayesian inference for stochastic programs. In

Fourteenth National Conference on
Artificial Intelligence (AAAI), pages 740-747.

[3] Pfeffer, Avi. 2001. IBAL: An Integrated Bayesian Agent Language.
In

IJCAI 2001.

[4] Ramsey, Norman and Avi Pfeffer. 2002. Stochastic Lambda Calculus
and Monads of Probability Distributions. In

Principles of Programming Languages (POPL)
'02.

Josh
Burdick / jburdick@gradient.cis.upenn.edu / last modified June 17, 2003