TuringLang / JuliaBUGS.jl / 14523911609

push

github

Generating Julia function for log density evaluation (#278)

### Motivation

JuliaBUGS compiles BUGS programs into a directed probabilistic graphical
model (PGM), which implicitly defines the dependency structure between
variables. While this graph allows for execution strategies like
topological traversal and parallelization, a significant challenge
arises from the BUGS language semantics: every element within an array
can be treated as an individual random variable.

This fine-grained dependency structure means that a naive way to
generate Julia source based on the variable-level graph would often
require fully unrolling all loops. This approach is infeasible,
especially for large datasets or complex models, and poses significant
difficulties for automatic differentiation (AD) tools to analyze the
program.

### Proposed Changes

This PR introduces an initial implementation for generating a
specialized Julia function dedicated to computing the log density of the
model. The core idea is to operate on a higher level of abstraction than
individual variable nodes.

The algorithm proceeds as follows:

1. **Statement-Level Dependence Graph:** Construct a dependence graph
where nodes represent the *statements* in the BUGS program, rather than
individual random variables. Edges represent dependencies between these
statements.
2. **Acyclicity Check:** Verify if this statement-level graph contains
any cycles (including self-loops).
3. **Topological Sort & Loop Fission:** If the graph is acyclic, perform
a topological sort on the statements. Based on this order, restructure
the program, applying full loop fission. This separates loops operating
on different variables, ensuring that computations occur in a valid
dependency order.
4. **Code Generation:** Generate a Julia function based on the
topologically sorted and fissioned sequence of statements. Specialized
code is generated for:
    * Deterministic assignments (`=`).
    * Stochastic assignments / Priors (`... (continued)

300 of 349 new or added lines in 4 files covered. (85.96%)

2028 of 2441 relevant lines covered (83.08%)

130365.16 hits per line