Bean Machine Retrospective, part 4

Did I actually build a compiler? Yes and no.

Traditionally we think of a compiler as a program which takes as its input the text of a program written in one language (C#, say), and produces as its output an equivalent" program written in another language (MSIL, say). A more modern conception is: a compiler is a collection of code analysis services, and one of those services is translation.

I made a great many assumptions when embarking on this project. Some of the more important ones were as follows:

Assumption: we must implement everything necessary for a source-to-source translation, but that is not enough. The primary use case of Beanstalk is outputting samples from a posterior, not outputting an equivalent program text. Translation may be a secondary use case, but we will not succeed by stopping there.

We're building a compiler in order to build a better calculator.

Static and dynamic analysis

Traditional translating compilers such as the C# compiler perform a static" analysis of the code; that is, they analyze only (1) the text of the program and (2) metadata associated with already-compiled artifacts such as libraries. The code is not executed in a static analysis.

Dynamic" analysis is by contrast an analysis of code while the code is running.

Assumption: correct static analysis of Python is impossible for at least two reasons.

1) Python is an extremely dynamic language; it is difficult to definitively know what any program identifier refers to, for example, without actually running the program to find out.

2) The model may depend upon non-stochastic model elements that are unknowable by static analysis. Model parameters or observed values can (and will!) be read from files or queried from databases, and those values must be present in the graph that we deduce.

We must build a dynamic analyzer; we're going to run a modified version of the model code to find out what it does.

Pure functions, acyclic graph

For our purposes we define a pure function as one that:

• Always terminates normally; it does not go into an infinite loop or throw an exception
• Is idempotent: it always produces the same output when given the same input
• Its action does not depend on mutating global state
• Its action does not mutate global state

Examples of impure functions are easily produced:

mean = 1.0@random_variabledef normal(): global mean mean = mean + 1.0 # UH OH return Normal(mean, 1.0)

Or, just as bad:

mean = tensor([1.0])@random_variabledef normal(): global mean mean[0] += 1.0 return Normal(mean, 1.0)

Assumptions:

• Model builders will write pure functions. In particular, model builders will not mutate a tensor in place" such that the mutation causes a change of behaviour elsewhere in the model
• Beanstalk is not required to detect impure functions, though it may
• Beanstalk may memoize model functions

Also: a Bayesian network never has cycles; the distribution of each node depends solely on the distributions of its ancestor nodes.

Assumptions:

• Model builders will write models where no random variable depends upon itself, directly or indirectly.
• Beanstalk is not required to detect cycles (though in practice, it does)

Note that a model may contain recursion if the recursion terminates. This is legal:

@random_variabledef normal(n): if n <= 0: mean = 0.0 else: mean = normal(n-1) return Normal(mean, 1.0)queries = [ normal(0) ]observations = { normal(2): tensor(0.0) }

Next time on FAIC: Having made these and other assumptions, I embarked upon an implementation. But before I can explain the implementation, I should probably answer some nagging questions you might have about what exactly that random_variable decorator does.