Module grammar 

Expression trees as probabilistic grammars: genetic programming as exact Bayesian inference

ArithmeticGrammarPrior is a probabilistic context-free grammar over TreeGenome expression trees, written as a fugue program. Every node at tree path p (root key "node", children "node/0", "node/0/1", …) emits real probabilistic choices at path-keyed addresses:

Site	Address	Distribution
leaf-vs-function	<path>#leaf	Bernoulli(terminal_prob) (forced at max depth)
terminal kind	<path>#tkind	Categorical([p_var, p_const])
variable index	<path>#var	Categorical(uniform over n_vars)
constant value	<path>#const	Normal(0, const_std)
function choice	<path>#func	Categorical(uniform over F::functions())

Because the structure of an execution is encoded in its own choices, the generic trace machinery becomes genetic programming for free:

• Subtree regeneration mutation is fugue’s ordinary single-site MH: a flip of one #leaf bit (or a change of #func arity) births or kills the subtree below it, with the fresh sites drawn from this grammar and the reversible-jump corrections applied by propose_and_score — no bespoke acceptance math anywhere in this crate.
• Subtree crossover is a CrossoverKernel whose mask is the union of both parents’ addresses under one shared node path (subtree_crossover_mask): swapping that block grafts each parent’s subtree into the other, and the re-score replays each child consistently because the grafted choices themselves describe the new structure.

Parsimony needs no ad-hoc penalty: deeper trees pay more grammar prior mass by construction.

Note: tree genomes are decoded from particles by replay (the model returns the built TreeGenome); the flat TraceGenome encoding of TreeGenome is unrelated to this grammar’s address scheme, so EvolutionModel::score/to_weighted_trace (which replay to_trace) do not apply to grammar-driven trees — use the SMC/MH drivers, which never need them.

Structs

ArithmeticGrammarPrior

A probabilistic context-free grammar prior over arithmetic expression trees.

GaussianRegression

Gaussian-noise regression of a dataset under a candidate expression tree, as an observation program — per-datum observe statements, with the noise scale either fixed or a latent site jointly inferred with the program. This is the capability the scalar-factor fitness could never express: hyperparameters of the “fitness” become posterior quantities, read straight off the particle traces at addr!("sigma").

Enums

NoiseSpec

How the observation noise enters the regression likelihood.

Functions

subtree_crossover_mask

A value-independent, pair-symmetric subtree crossover mask for [fugue::CrossoverKernel]: picks one node path present in both parents uniformly at random and returns the union of the two parents’ addresses under that path. Swapping that block grafts each parent’s subtree into the other; the kernel’s mandatory re-score replays each child consistently (the grafted choices encode the new structure) and rejects off-support or low-density grafts via the product-target Metropolis ratio.

Type Aliases

CrossoverMaskFn

The mask-closure type consumed by [fugue::CrossoverKernel].