Struct ExprGraph 

pub struct ExprGraph { /* private fields */ }

Arena-based expression graph with structural interning.

Identical subexpressions always return the same ExprId — this gives automatic common subexpression elimination (CSE) for free.

Implementations

impl ExprGraph

pub fn to_kernel( &self, outputs: &[ExprId], n_inputs: usize, dialect: Dialect, ) -> ComputeKernel

Generate a compute kernel for the given dialect.

Each work item reads n_inputs f32 values and writes outputs.len() f32 values. Shared subexpressions are computed once per thread.

impl ExprGraph

pub fn compile(&self, expr: ExprId) -> CompiledExpr

Compile a single expression to a closure &[f64] -> f64.

Shared subexpressions (from interning) are computed once. Dead nodes (not reachable from output) are skipped.

Examples found in repository

examples/symbolic_regression.rs (line 264)

fn fitness(expr: &Expr, data: &[(f64, f64)]) -> f64 {
    let mut g = ExprGraph::new();
    let root = expr.to_expr(&mut g);
    let compiled = g.compile(root);

    let mut mse = 0.0;
    for &(x, y) in data {
        let pred = compiled(&[x]);
        if pred.is_nan() || pred.is_infinite() {
            return f64::INFINITY;
        }
        let err = pred - y;
        mse += err * err;
    }
    mse /= data.len() as f64;

    let penalty = 0.001 * expr.size() as f64;
    mse + penalty
}

// --- Selection ---------------------------------------------------------------

fn tournament<'a>(pop: &'a [(Expr, f64)], k: usize, rng: &mut Lcg) -> &'a Expr {
    let mut best_idx = rng.range(pop.len());
    for _ in 1..k {
        let idx = rng.range(pop.len());
        if pop[idx].1 < pop[best_idx].1 {
            best_idx = idx;
        }
    }
    &pop[best_idx].0
}

// --- Main --------------------------------------------------------------------

fn main() {
    println!("=== Symbolic Regression ===\n");
    println!("target: f(x) = x^2 * sin(x)\n");

    let mut rng = Lcg::new(42);
    let data = generate_data(50, &mut rng);

    const POP_SIZE: usize = 200;
    const GENERATIONS: usize = 100;
    const TOURNAMENT_K: usize = 5;

    // Initialize population
    let mut population: Vec<(Expr, f64)> = (0..POP_SIZE)
        .map(|_| {
            let expr = random_expr(4, &mut rng);
            let fit = fitness(&expr, &data);
            (expr, fit)
        })
        .collect();

    let mut best_expr: Option<Expr> = None;
    let mut best_fitness = f64::INFINITY;

    for gen in 0..GENERATIONS {
        // Track best
        for (expr, fit) in &population {
            if *fit < best_fitness {
                best_fitness = *fit;
                best_expr = Some(expr.clone());
            }
        }

        if (gen + 1) % 10 == 0 || gen == 0 {
            let b = best_expr.as_ref().unwrap();
            println!(
                "gen {:>3}: best fitness = {:.6}  nodes = {:>3}  expr = {}",
                gen + 1,
                best_fitness,
                b.size(),
                b.format(),
            );
        }

        // Build next generation
        let mut next_pop = Vec::with_capacity(POP_SIZE);

        // Elitism: keep top 5
        let mut indices: Vec<usize> = (0..population.len()).collect();
        indices.sort_by(|&a, &b| population[a].1.partial_cmp(&population[b].1).unwrap());
        for &i in indices.iter().take(5) {
            next_pop.push(population[i].clone());
        }

        // Fill rest via mutation
        while next_pop.len() < POP_SIZE {
            let parent = tournament(&population, TOURNAMENT_K, &mut rng);
            let child = match rng.range(10) {
                0..=3 => mutate_grow(parent, &mut rng),
                4..=6 => mutate_point(parent, &mut rng),
                7..=8 => mutate_simplify(parent),
                _ => random_expr(4, &mut rng), // fresh blood
            };

            // Skip overly large expressions
            if child.size() > 50 {
                continue;
            }

            let fit = fitness(&child, &data);
            next_pop.push((child, fit));
        }

        population = next_pop;
    }

    // Final results
    println!();
    let best = best_expr.unwrap();
    let mut g = ExprGraph::new();
    let root = best.to_expr(&mut g);
    let simplified = g.simplify(root);
    let expr_str = g.fmt_expr(simplified);
    println!("best expression: {}", expr_str);
    println!("best fitness:    {:.6}", best_fitness);

    // Verify on test points
    println!("\nverification:");
    let compiled = g.compile(simplified);
    for &x in &[-2.0, -1.0, 0.0, 1.0, 2.0] {
        let pred = compiled(&[x]);
        let exact = target(x);
        println!(
            "  f({:>5.1}) = {:>8.4}  (predicted: {:>8.4}, error: {:>8.4})",
            x,
            exact,
            pred,
            (pred - exact).abs()
        );
    }

    // Symbolic derivative via ExprGraph
    let dx = g.diff(simplified, 0);
    let dx = g.simplify(dx);
    println!(
        "\nsymbolic derivative: d/dx [{}] = {}",
        expr_str,
        g.fmt_expr(dx)
    );
}

pub fn compile_many(&self, exprs: &[ExprId]) -> CompiledMany

Compile multiple output expressions to a single closure.

Writes results into the output slice.

pub fn live_set(&self, outputs: &[ExprId]) -> HashSet<usize>

Find all node indices reachable from the given outputs.

impl ExprGraph

pub fn diff(&mut self, expr: ExprId, var: u16) -> ExprId

Differentiate expr with respect to Var(var).

Returns a new ExprId in the same graph. Uses memoization to avoid recomputing derivatives of shared subexpressions.

Examples found in repository

examples/symbolic_regression.rs (line 397)

fn main() {
    println!("=== Symbolic Regression ===\n");
    println!("target: f(x) = x^2 * sin(x)\n");

    let mut rng = Lcg::new(42);
    let data = generate_data(50, &mut rng);

    const POP_SIZE: usize = 200;
    const GENERATIONS: usize = 100;
    const TOURNAMENT_K: usize = 5;

    // Initialize population
    let mut population: Vec<(Expr, f64)> = (0..POP_SIZE)
        .map(|_| {
            let expr = random_expr(4, &mut rng);
            let fit = fitness(&expr, &data);
            (expr, fit)
        })
        .collect();

    let mut best_expr: Option<Expr> = None;
    let mut best_fitness = f64::INFINITY;

    for gen in 0..GENERATIONS {
        // Track best
        for (expr, fit) in &population {
            if *fit < best_fitness {
                best_fitness = *fit;
                best_expr = Some(expr.clone());
            }
        }

        if (gen + 1) % 10 == 0 || gen == 0 {
            let b = best_expr.as_ref().unwrap();
            println!(
                "gen {:>3}: best fitness = {:.6}  nodes = {:>3}  expr = {}",
                gen + 1,
                best_fitness,
                b.size(),
                b.format(),
            );
        }

        // Build next generation
        let mut next_pop = Vec::with_capacity(POP_SIZE);

        // Elitism: keep top 5
        let mut indices: Vec<usize> = (0..population.len()).collect();
        indices.sort_by(|&a, &b| population[a].1.partial_cmp(&population[b].1).unwrap());
        for &i in indices.iter().take(5) {
            next_pop.push(population[i].clone());
        }

        // Fill rest via mutation
        while next_pop.len() < POP_SIZE {
            let parent = tournament(&population, TOURNAMENT_K, &mut rng);
            let child = match rng.range(10) {
                0..=3 => mutate_grow(parent, &mut rng),
                4..=6 => mutate_point(parent, &mut rng),
                7..=8 => mutate_simplify(parent),
                _ => random_expr(4, &mut rng), // fresh blood
            };

            // Skip overly large expressions
            if child.size() > 50 {
                continue;
            }

            let fit = fitness(&child, &data);
            next_pop.push((child, fit));
        }

        population = next_pop;
    }

    // Final results
    println!();
    let best = best_expr.unwrap();
    let mut g = ExprGraph::new();
    let root = best.to_expr(&mut g);
    let simplified = g.simplify(root);
    let expr_str = g.fmt_expr(simplified);
    println!("best expression: {}", expr_str);
    println!("best fitness:    {:.6}", best_fitness);

    // Verify on test points
    println!("\nverification:");
    let compiled = g.compile(simplified);
    for &x in &[-2.0, -1.0, 0.0, 1.0, 2.0] {
        let pred = compiled(&[x]);
        let exact = target(x);
        println!(
            "  f({:>5.1}) = {:>8.4}  (predicted: {:>8.4}, error: {:>8.4})",
            x,
            exact,
            pred,
            (pred - exact).abs()
        );
    }

    // Symbolic derivative via ExprGraph
    let dx = g.diff(simplified, 0);
    let dx = g.simplify(dx);
    println!(
        "\nsymbolic derivative: d/dx [{}] = {}",
        expr_str,
        g.fmt_expr(dx)
    );
}

impl ExprGraph

pub fn fmt_expr(&self, expr: ExprId) -> String

Format an expression as a human-readable string.

Examples found in repository

examples/symbolic_regression.rs (line 87)

    fn format(&self) -> String {
        let mut g = ExprGraph::new();
        let root = self.to_expr(&mut g);
        g.fmt_expr(root)
    }

    /// Evaluate at a point using ExprGraph's compiled eval.
    fn eval_at(&self, x: f64) -> f64 {
        let mut g = ExprGraph::new();
        let root = self.to_expr(&mut g);
        g.eval(root, &[x])
    }
}

// --- Random expression generation -------------------------------------------

fn random_expr(depth: usize, rng: &mut Lcg) -> Expr {
    if depth == 0 || (depth < 3 && rng.uniform() < 0.3) {
        return match rng.range(3) {
            0 => Expr::X,
            1 => Expr::Lit(
                (rng.uniform() * 4.0 - 2.0) * 10.0_f64.powi(-((rng.uniform() * 2.0) as i32)),
            ),
            _ => Expr::X,
        };
    }

    match rng.range(5) {
        0 => Expr::Add(
            Box::new(random_expr(depth - 1, rng)),
            Box::new(random_expr(depth - 1, rng)),
        ),
        1 | 2 => Expr::Mul(
            Box::new(random_expr(depth - 1, rng)),
            Box::new(random_expr(depth - 1, rng)),
        ),
        3 => Expr::Sin(Box::new(random_expr(depth - 1, rng))),
        _ => Expr::Neg(Box::new(random_expr(depth - 1, rng))),
    }
}

// --- Mutation operators ------------------------------------------------------

/// Grow mutation: replace a random subtree with a new random one.
fn mutate_grow(expr: &Expr, rng: &mut Lcg) -> Expr {
    let size = expr.size();
    let target = rng.range(size);
    grow_at(expr, target, &mut 0, rng)
}

fn grow_at(expr: &Expr, target: usize, counter: &mut usize, rng: &mut Lcg) -> Expr {
    if *counter == target {
        *counter += expr.size(); // skip subtree
        return random_expr(3, rng);
    }
    *counter += 1;
    match expr {
        Expr::X => Expr::X,
        Expr::Lit(v) => Expr::Lit(*v),
        Expr::Add(a, b) => Expr::Add(
            Box::new(grow_at(a, target, counter, rng)),
            Box::new(grow_at(b, target, counter, rng)),
        ),
        Expr::Mul(a, b) => Expr::Mul(
            Box::new(grow_at(a, target, counter, rng)),
            Box::new(grow_at(b, target, counter, rng)),
        ),
        Expr::Sin(a) => Expr::Sin(Box::new(grow_at(a, target, counter, rng))),
        Expr::Neg(a) => Expr::Neg(Box::new(grow_at(a, target, counter, rng))),
    }
}

/// Point mutation: change a single node's operation.
fn mutate_point(expr: &Expr, rng: &mut Lcg) -> Expr {
    let size = expr.size();
    let target = rng.range(size);
    point_at(expr, target, &mut 0, rng)
}

fn point_at(expr: &Expr, target: usize, counter: &mut usize, rng: &mut Lcg) -> Expr {
    if *counter == target {
        *counter += 1;
        return match expr {
            Expr::X => Expr::Lit(rng.uniform() * 2.0 - 1.0),
            Expr::Lit(_) => Expr::X,
            Expr::Add(a, b) => Expr::Mul(a.clone(), b.clone()),
            Expr::Mul(a, b) => Expr::Add(a.clone(), b.clone()),
            Expr::Sin(a) => Expr::Neg(a.clone()),
            Expr::Neg(a) => Expr::Sin(a.clone()),
        };
    }
    *counter += 1;
    match expr {
        Expr::X => Expr::X,
        Expr::Lit(v) => Expr::Lit(*v),
        Expr::Add(a, b) => Expr::Add(
            Box::new(point_at(a, target, counter, rng)),
            Box::new(point_at(b, target, counter, rng)),
        ),
        Expr::Mul(a, b) => Expr::Mul(
            Box::new(point_at(a, target, counter, rng)),
            Box::new(point_at(b, target, counter, rng)),
        ),
        Expr::Sin(a) => Expr::Sin(Box::new(point_at(a, target, counter, rng))),
        Expr::Neg(a) => Expr::Neg(Box::new(point_at(a, target, counter, rng))),
    }
}

/// Simplify mutation: convert to ExprGraph, simplify, convert back.
/// Falls back to identity if conversion back would be complex.
fn mutate_simplify(expr: &Expr) -> Expr {
    let mut g = ExprGraph::new();
    let root = expr.to_expr(&mut g);
    let simplified = g.simplify(root);
    let s = g.fmt_expr(simplified);

    // Quick check: if simplified form is much shorter, it's better
    let orig = expr.format();
    if s.len() < orig.len() {
        // Re-evaluate to confirm it still works
        let test = g.eval::<f64>(simplified, &[1.0]);
        let orig_test = expr.eval_at(1.0);
        if (test - orig_test).abs() < 1e-10 || (test.is_nan() && orig_test.is_nan()) {
            // Return a new tree built from the simplified graph
            return expr_from_graph(&g, simplified);
        }
    }
    expr.clone()
}

/// Reconstruct an Expr tree from an ExprGraph node.
fn expr_from_graph(g: &ExprGraph, id: ExprId) -> Expr {
    match g.node(id) {
        tang_expr::node::Node::Var(_) => Expr::X,
        tang_expr::node::Node::Lit(bits) => {
            let v = f64::from_bits(bits);
            if v == 0.0 {
                Expr::Lit(0.0)
            } else {
                Expr::Lit(v)
            }
        }
        tang_expr::node::Node::Add(a, b) => Expr::Add(
            Box::new(expr_from_graph(g, a)),
            Box::new(expr_from_graph(g, b)),
        ),
        tang_expr::node::Node::Mul(a, b) => Expr::Mul(
            Box::new(expr_from_graph(g, a)),
            Box::new(expr_from_graph(g, b)),
        ),
        tang_expr::node::Node::Neg(a) => Expr::Neg(Box::new(expr_from_graph(g, a))),
        tang_expr::node::Node::Sin(a) => Expr::Sin(Box::new(expr_from_graph(g, a))),
        // For operations we don't represent in our AST, just evaluate as literal
        _ => {
            let v = g.eval::<f64>(id, &[1.0]); // fallback
            Expr::Lit(v)
        }
    }
}

// --- Fitness evaluation ------------------------------------------------------

fn target(x: f64) -> f64 {
    x * x * x.sin()
}

fn generate_data(n: usize, rng: &mut Lcg) -> Vec<(f64, f64)> {
    (0..n)
        .map(|i| {
            let x = -3.0 + 6.0 * i as f64 / (n - 1) as f64;
            let noise = (rng.uniform() - 0.5) * 0.01;
            (x, target(x) + noise)
        })
        .collect()
}

/// Evaluate fitness: MSE + complexity penalty.
fn fitness(expr: &Expr, data: &[(f64, f64)]) -> f64 {
    let mut g = ExprGraph::new();
    let root = expr.to_expr(&mut g);
    let compiled = g.compile(root);

    let mut mse = 0.0;
    for &(x, y) in data {
        let pred = compiled(&[x]);
        if pred.is_nan() || pred.is_infinite() {
            return f64::INFINITY;
        }
        let err = pred - y;
        mse += err * err;
    }
    mse /= data.len() as f64;

    let penalty = 0.001 * expr.size() as f64;
    mse + penalty
}

// --- Selection ---------------------------------------------------------------

fn tournament<'a>(pop: &'a [(Expr, f64)], k: usize, rng: &mut Lcg) -> &'a Expr {
    let mut best_idx = rng.range(pop.len());
    for _ in 1..k {
        let idx = rng.range(pop.len());
        if pop[idx].1 < pop[best_idx].1 {
            best_idx = idx;
        }
    }
    &pop[best_idx].0
}

// --- Main --------------------------------------------------------------------

fn main() {
    println!("=== Symbolic Regression ===\n");
    println!("target: f(x) = x^2 * sin(x)\n");

    let mut rng = Lcg::new(42);
    let data = generate_data(50, &mut rng);

    const POP_SIZE: usize = 200;
    const GENERATIONS: usize = 100;
    const TOURNAMENT_K: usize = 5;

    // Initialize population
    let mut population: Vec<(Expr, f64)> = (0..POP_SIZE)
        .map(|_| {
            let expr = random_expr(4, &mut rng);
            let fit = fitness(&expr, &data);
            (expr, fit)
        })
        .collect();

    let mut best_expr: Option<Expr> = None;
    let mut best_fitness = f64::INFINITY;

    for gen in 0..GENERATIONS {
        // Track best
        for (expr, fit) in &population {
            if *fit < best_fitness {
                best_fitness = *fit;
                best_expr = Some(expr.clone());
            }
        }

        if (gen + 1) % 10 == 0 || gen == 0 {
            let b = best_expr.as_ref().unwrap();
            println!(
                "gen {:>3}: best fitness = {:.6}  nodes = {:>3}  expr = {}",
                gen + 1,
                best_fitness,
                b.size(),
                b.format(),
            );
        }

        // Build next generation
        let mut next_pop = Vec::with_capacity(POP_SIZE);

        // Elitism: keep top 5
        let mut indices: Vec<usize> = (0..population.len()).collect();
        indices.sort_by(|&a, &b| population[a].1.partial_cmp(&population[b].1).unwrap());
        for &i in indices.iter().take(5) {
            next_pop.push(population[i].clone());
        }

        // Fill rest via mutation
        while next_pop.len() < POP_SIZE {
            let parent = tournament(&population, TOURNAMENT_K, &mut rng);
            let child = match rng.range(10) {
                0..=3 => mutate_grow(parent, &mut rng),
                4..=6 => mutate_point(parent, &mut rng),
                7..=8 => mutate_simplify(parent),
                _ => random_expr(4, &mut rng), // fresh blood
            };

            // Skip overly large expressions
            if child.size() > 50 {
                continue;
            }

            let fit = fitness(&child, &data);
            next_pop.push((child, fit));
        }

        population = next_pop;
    }

    // Final results
    println!();
    let best = best_expr.unwrap();
    let mut g = ExprGraph::new();
    let root = best.to_expr(&mut g);
    let simplified = g.simplify(root);
    let expr_str = g.fmt_expr(simplified);
    println!("best expression: {}", expr_str);
    println!("best fitness:    {:.6}", best_fitness);

    // Verify on test points
    println!("\nverification:");
    let compiled = g.compile(simplified);
    for &x in &[-2.0, -1.0, 0.0, 1.0, 2.0] {
        let pred = compiled(&[x]);
        let exact = target(x);
        println!(
            "  f({:>5.1}) = {:>8.4}  (predicted: {:>8.4}, error: {:>8.4})",
            x,
            exact,
            pred,
            (pred - exact).abs()
        );
    }

    // Symbolic derivative via ExprGraph
    let dx = g.diff(simplified, 0);
    let dx = g.simplify(dx);
    println!(
        "\nsymbolic derivative: d/dx [{}] = {}",
        expr_str,
        g.fmt_expr(dx)
    );
}

impl ExprGraph

pub fn eval<S: Scalar>(&self, expr: ExprId, inputs: &[S]) -> S

Evaluate an expression with concrete scalar inputs.

inputs[n] provides the value for Var(n). Walks the graph in topological order (which is just index order, since children are always created before parents).

Examples found in repository

examples/symbolic_regression.rs (line 94)

    fn eval_at(&self, x: f64) -> f64 {
        let mut g = ExprGraph::new();
        let root = self.to_expr(&mut g);
        g.eval(root, &[x])
    }
}

// --- Random expression generation -------------------------------------------

fn random_expr(depth: usize, rng: &mut Lcg) -> Expr {
    if depth == 0 || (depth < 3 && rng.uniform() < 0.3) {
        return match rng.range(3) {
            0 => Expr::X,
            1 => Expr::Lit(
                (rng.uniform() * 4.0 - 2.0) * 10.0_f64.powi(-((rng.uniform() * 2.0) as i32)),
            ),
            _ => Expr::X,
        };
    }

    match rng.range(5) {
        0 => Expr::Add(
            Box::new(random_expr(depth - 1, rng)),
            Box::new(random_expr(depth - 1, rng)),
        ),
        1 | 2 => Expr::Mul(
            Box::new(random_expr(depth - 1, rng)),
            Box::new(random_expr(depth - 1, rng)),
        ),
        3 => Expr::Sin(Box::new(random_expr(depth - 1, rng))),
        _ => Expr::Neg(Box::new(random_expr(depth - 1, rng))),
    }
}

// --- Mutation operators ------------------------------------------------------

/// Grow mutation: replace a random subtree with a new random one.
fn mutate_grow(expr: &Expr, rng: &mut Lcg) -> Expr {
    let size = expr.size();
    let target = rng.range(size);
    grow_at(expr, target, &mut 0, rng)
}

fn grow_at(expr: &Expr, target: usize, counter: &mut usize, rng: &mut Lcg) -> Expr {
    if *counter == target {
        *counter += expr.size(); // skip subtree
        return random_expr(3, rng);
    }
    *counter += 1;
    match expr {
        Expr::X => Expr::X,
        Expr::Lit(v) => Expr::Lit(*v),
        Expr::Add(a, b) => Expr::Add(
            Box::new(grow_at(a, target, counter, rng)),
            Box::new(grow_at(b, target, counter, rng)),
        ),
        Expr::Mul(a, b) => Expr::Mul(
            Box::new(grow_at(a, target, counter, rng)),
            Box::new(grow_at(b, target, counter, rng)),
        ),
        Expr::Sin(a) => Expr::Sin(Box::new(grow_at(a, target, counter, rng))),
        Expr::Neg(a) => Expr::Neg(Box::new(grow_at(a, target, counter, rng))),
    }
}

/// Point mutation: change a single node's operation.
fn mutate_point(expr: &Expr, rng: &mut Lcg) -> Expr {
    let size = expr.size();
    let target = rng.range(size);
    point_at(expr, target, &mut 0, rng)
}

fn point_at(expr: &Expr, target: usize, counter: &mut usize, rng: &mut Lcg) -> Expr {
    if *counter == target {
        *counter += 1;
        return match expr {
            Expr::X => Expr::Lit(rng.uniform() * 2.0 - 1.0),
            Expr::Lit(_) => Expr::X,
            Expr::Add(a, b) => Expr::Mul(a.clone(), b.clone()),
            Expr::Mul(a, b) => Expr::Add(a.clone(), b.clone()),
            Expr::Sin(a) => Expr::Neg(a.clone()),
            Expr::Neg(a) => Expr::Sin(a.clone()),
        };
    }
    *counter += 1;
    match expr {
        Expr::X => Expr::X,
        Expr::Lit(v) => Expr::Lit(*v),
        Expr::Add(a, b) => Expr::Add(
            Box::new(point_at(a, target, counter, rng)),
            Box::new(point_at(b, target, counter, rng)),
        ),
        Expr::Mul(a, b) => Expr::Mul(
            Box::new(point_at(a, target, counter, rng)),
            Box::new(point_at(b, target, counter, rng)),
        ),
        Expr::Sin(a) => Expr::Sin(Box::new(point_at(a, target, counter, rng))),
        Expr::Neg(a) => Expr::Neg(Box::new(point_at(a, target, counter, rng))),
    }
}

/// Simplify mutation: convert to ExprGraph, simplify, convert back.
/// Falls back to identity if conversion back would be complex.
fn mutate_simplify(expr: &Expr) -> Expr {
    let mut g = ExprGraph::new();
    let root = expr.to_expr(&mut g);
    let simplified = g.simplify(root);
    let s = g.fmt_expr(simplified);

    // Quick check: if simplified form is much shorter, it's better
    let orig = expr.format();
    if s.len() < orig.len() {
        // Re-evaluate to confirm it still works
        let test = g.eval::<f64>(simplified, &[1.0]);
        let orig_test = expr.eval_at(1.0);
        if (test - orig_test).abs() < 1e-10 || (test.is_nan() && orig_test.is_nan()) {
            // Return a new tree built from the simplified graph
            return expr_from_graph(&g, simplified);
        }
    }
    expr.clone()
}

/// Reconstruct an Expr tree from an ExprGraph node.
fn expr_from_graph(g: &ExprGraph, id: ExprId) -> Expr {
    match g.node(id) {
        tang_expr::node::Node::Var(_) => Expr::X,
        tang_expr::node::Node::Lit(bits) => {
            let v = f64::from_bits(bits);
            if v == 0.0 {
                Expr::Lit(0.0)
            } else {
                Expr::Lit(v)
            }
        }
        tang_expr::node::Node::Add(a, b) => Expr::Add(
            Box::new(expr_from_graph(g, a)),
            Box::new(expr_from_graph(g, b)),
        ),
        tang_expr::node::Node::Mul(a, b) => Expr::Mul(
            Box::new(expr_from_graph(g, a)),
            Box::new(expr_from_graph(g, b)),
        ),
        tang_expr::node::Node::Neg(a) => Expr::Neg(Box::new(expr_from_graph(g, a))),
        tang_expr::node::Node::Sin(a) => Expr::Sin(Box::new(expr_from_graph(g, a))),
        // For operations we don't represent in our AST, just evaluate as literal
        _ => {
            let v = g.eval::<f64>(id, &[1.0]); // fallback
            Expr::Lit(v)
        }
    }
}

pub fn eval_many<S: Scalar>(&self, exprs: &[ExprId], inputs: &[S]) -> Vec<S>

Evaluate multiple output expressions, sharing intermediate values.

impl ExprGraph

pub fn new() -> Self

Create a new graph pre-populated with ZERO, ONE, TWO.

Examples found in repository

examples/symbolic_regression.rs (line 85)

    fn format(&self) -> String {
        let mut g = ExprGraph::new();
        let root = self.to_expr(&mut g);
        g.fmt_expr(root)
    }

    /// Evaluate at a point using ExprGraph's compiled eval.
    fn eval_at(&self, x: f64) -> f64 {
        let mut g = ExprGraph::new();
        let root = self.to_expr(&mut g);
        g.eval(root, &[x])
    }
}

// --- Random expression generation -------------------------------------------

fn random_expr(depth: usize, rng: &mut Lcg) -> Expr {
    if depth == 0 || (depth < 3 && rng.uniform() < 0.3) {
        return match rng.range(3) {
            0 => Expr::X,
            1 => Expr::Lit(
                (rng.uniform() * 4.0 - 2.0) * 10.0_f64.powi(-((rng.uniform() * 2.0) as i32)),
            ),
            _ => Expr::X,
        };
    }

    match rng.range(5) {
        0 => Expr::Add(
            Box::new(random_expr(depth - 1, rng)),
            Box::new(random_expr(depth - 1, rng)),
        ),
        1 | 2 => Expr::Mul(
            Box::new(random_expr(depth - 1, rng)),
            Box::new(random_expr(depth - 1, rng)),
        ),
        3 => Expr::Sin(Box::new(random_expr(depth - 1, rng))),
        _ => Expr::Neg(Box::new(random_expr(depth - 1, rng))),
    }
}

// --- Mutation operators ------------------------------------------------------

/// Grow mutation: replace a random subtree with a new random one.
fn mutate_grow(expr: &Expr, rng: &mut Lcg) -> Expr {
    let size = expr.size();
    let target = rng.range(size);
    grow_at(expr, target, &mut 0, rng)
}

fn grow_at(expr: &Expr, target: usize, counter: &mut usize, rng: &mut Lcg) -> Expr {
    if *counter == target {
        *counter += expr.size(); // skip subtree
        return random_expr(3, rng);
    }
    *counter += 1;
    match expr {
        Expr::X => Expr::X,
        Expr::Lit(v) => Expr::Lit(*v),
        Expr::Add(a, b) => Expr::Add(
            Box::new(grow_at(a, target, counter, rng)),
            Box::new(grow_at(b, target, counter, rng)),
        ),
        Expr::Mul(a, b) => Expr::Mul(
            Box::new(grow_at(a, target, counter, rng)),
            Box::new(grow_at(b, target, counter, rng)),
        ),
        Expr::Sin(a) => Expr::Sin(Box::new(grow_at(a, target, counter, rng))),
        Expr::Neg(a) => Expr::Neg(Box::new(grow_at(a, target, counter, rng))),
    }
}

/// Point mutation: change a single node's operation.
fn mutate_point(expr: &Expr, rng: &mut Lcg) -> Expr {
    let size = expr.size();
    let target = rng.range(size);
    point_at(expr, target, &mut 0, rng)
}

fn point_at(expr: &Expr, target: usize, counter: &mut usize, rng: &mut Lcg) -> Expr {
    if *counter == target {
        *counter += 1;
        return match expr {
            Expr::X => Expr::Lit(rng.uniform() * 2.0 - 1.0),
            Expr::Lit(_) => Expr::X,
            Expr::Add(a, b) => Expr::Mul(a.clone(), b.clone()),
            Expr::Mul(a, b) => Expr::Add(a.clone(), b.clone()),
            Expr::Sin(a) => Expr::Neg(a.clone()),
            Expr::Neg(a) => Expr::Sin(a.clone()),
        };
    }
    *counter += 1;
    match expr {
        Expr::X => Expr::X,
        Expr::Lit(v) => Expr::Lit(*v),
        Expr::Add(a, b) => Expr::Add(
            Box::new(point_at(a, target, counter, rng)),
            Box::new(point_at(b, target, counter, rng)),
        ),
        Expr::Mul(a, b) => Expr::Mul(
            Box::new(point_at(a, target, counter, rng)),
            Box::new(point_at(b, target, counter, rng)),
        ),
        Expr::Sin(a) => Expr::Sin(Box::new(point_at(a, target, counter, rng))),
        Expr::Neg(a) => Expr::Neg(Box::new(point_at(a, target, counter, rng))),
    }
}

/// Simplify mutation: convert to ExprGraph, simplify, convert back.
/// Falls back to identity if conversion back would be complex.
fn mutate_simplify(expr: &Expr) -> Expr {
    let mut g = ExprGraph::new();
    let root = expr.to_expr(&mut g);
    let simplified = g.simplify(root);
    let s = g.fmt_expr(simplified);

    // Quick check: if simplified form is much shorter, it's better
    let orig = expr.format();
    if s.len() < orig.len() {
        // Re-evaluate to confirm it still works
        let test = g.eval::<f64>(simplified, &[1.0]);
        let orig_test = expr.eval_at(1.0);
        if (test - orig_test).abs() < 1e-10 || (test.is_nan() && orig_test.is_nan()) {
            // Return a new tree built from the simplified graph
            return expr_from_graph(&g, simplified);
        }
    }
    expr.clone()
}

/// Reconstruct an Expr tree from an ExprGraph node.
fn expr_from_graph(g: &ExprGraph, id: ExprId) -> Expr {
    match g.node(id) {
        tang_expr::node::Node::Var(_) => Expr::X,
        tang_expr::node::Node::Lit(bits) => {
            let v = f64::from_bits(bits);
            if v == 0.0 {
                Expr::Lit(0.0)
            } else {
                Expr::Lit(v)
            }
        }
        tang_expr::node::Node::Add(a, b) => Expr::Add(
            Box::new(expr_from_graph(g, a)),
            Box::new(expr_from_graph(g, b)),
        ),
        tang_expr::node::Node::Mul(a, b) => Expr::Mul(
            Box::new(expr_from_graph(g, a)),
            Box::new(expr_from_graph(g, b)),
        ),
        tang_expr::node::Node::Neg(a) => Expr::Neg(Box::new(expr_from_graph(g, a))),
        tang_expr::node::Node::Sin(a) => Expr::Sin(Box::new(expr_from_graph(g, a))),
        // For operations we don't represent in our AST, just evaluate as literal
        _ => {
            let v = g.eval::<f64>(id, &[1.0]); // fallback
            Expr::Lit(v)
        }
    }
}

// --- Fitness evaluation ------------------------------------------------------

fn target(x: f64) -> f64 {
    x * x * x.sin()
}

fn generate_data(n: usize, rng: &mut Lcg) -> Vec<(f64, f64)> {
    (0..n)
        .map(|i| {
            let x = -3.0 + 6.0 * i as f64 / (n - 1) as f64;
            let noise = (rng.uniform() - 0.5) * 0.01;
            (x, target(x) + noise)
        })
        .collect()
}

/// Evaluate fitness: MSE + complexity penalty.
fn fitness(expr: &Expr, data: &[(f64, f64)]) -> f64 {
    let mut g = ExprGraph::new();
    let root = expr.to_expr(&mut g);
    let compiled = g.compile(root);

    let mut mse = 0.0;
    for &(x, y) in data {
        let pred = compiled(&[x]);
        if pred.is_nan() || pred.is_infinite() {
            return f64::INFINITY;
        }
        let err = pred - y;
        mse += err * err;
    }
    mse /= data.len() as f64;

    let penalty = 0.001 * expr.size() as f64;
    mse + penalty
}

// --- Selection ---------------------------------------------------------------

fn tournament<'a>(pop: &'a [(Expr, f64)], k: usize, rng: &mut Lcg) -> &'a Expr {
    let mut best_idx = rng.range(pop.len());
    for _ in 1..k {
        let idx = rng.range(pop.len());
        if pop[idx].1 < pop[best_idx].1 {
            best_idx = idx;
        }
    }
    &pop[best_idx].0
}

// --- Main --------------------------------------------------------------------

fn main() {
    println!("=== Symbolic Regression ===\n");
    println!("target: f(x) = x^2 * sin(x)\n");

    let mut rng = Lcg::new(42);
    let data = generate_data(50, &mut rng);

    const POP_SIZE: usize = 200;
    const GENERATIONS: usize = 100;
    const TOURNAMENT_K: usize = 5;

    // Initialize population
    let mut population: Vec<(Expr, f64)> = (0..POP_SIZE)
        .map(|_| {
            let expr = random_expr(4, &mut rng);
            let fit = fitness(&expr, &data);
            (expr, fit)
        })
        .collect();

    let mut best_expr: Option<Expr> = None;
    let mut best_fitness = f64::INFINITY;

    for gen in 0..GENERATIONS {
        // Track best
        for (expr, fit) in &population {
            if *fit < best_fitness {
                best_fitness = *fit;
                best_expr = Some(expr.clone());
            }
        }

        if (gen + 1) % 10 == 0 || gen == 0 {
            let b = best_expr.as_ref().unwrap();
            println!(
                "gen {:>3}: best fitness = {:.6}  nodes = {:>3}  expr = {}",
                gen + 1,
                best_fitness,
                b.size(),
                b.format(),
            );
        }

        // Build next generation
        let mut next_pop = Vec::with_capacity(POP_SIZE);

        // Elitism: keep top 5
        let mut indices: Vec<usize> = (0..population.len()).collect();
        indices.sort_by(|&a, &b| population[a].1.partial_cmp(&population[b].1).unwrap());
        for &i in indices.iter().take(5) {
            next_pop.push(population[i].clone());
        }

        // Fill rest via mutation
        while next_pop.len() < POP_SIZE {
            let parent = tournament(&population, TOURNAMENT_K, &mut rng);
            let child = match rng.range(10) {
                0..=3 => mutate_grow(parent, &mut rng),
                4..=6 => mutate_point(parent, &mut rng),
                7..=8 => mutate_simplify(parent),
                _ => random_expr(4, &mut rng), // fresh blood
            };

            // Skip overly large expressions
            if child.size() > 50 {
                continue;
            }

            let fit = fitness(&child, &data);
            next_pop.push((child, fit));
        }

        population = next_pop;
    }

    // Final results
    println!();
    let best = best_expr.unwrap();
    let mut g = ExprGraph::new();
    let root = best.to_expr(&mut g);
    let simplified = g.simplify(root);
    let expr_str = g.fmt_expr(simplified);
    println!("best expression: {}", expr_str);
    println!("best fitness:    {:.6}", best_fitness);

    // Verify on test points
    println!("\nverification:");
    let compiled = g.compile(simplified);
    for &x in &[-2.0, -1.0, 0.0, 1.0, 2.0] {
        let pred = compiled(&[x]);
        let exact = target(x);
        println!(
            "  f({:>5.1}) = {:>8.4}  (predicted: {:>8.4}, error: {:>8.4})",
            x,
            exact,
            pred,
            (pred - exact).abs()
        );
    }

    // Symbolic derivative via ExprGraph
    let dx = g.diff(simplified, 0);
    let dx = g.simplify(dx);
    println!(
        "\nsymbolic derivative: d/dx [{}] = {}",
        expr_str,
        g.fmt_expr(dx)
    );
}

pub fn len(&self) -> usize

Total number of nodes in the graph.

pub fn is_empty(&self) -> bool

Whether the graph is empty (it never is after construction).

pub fn node(&self, id: ExprId) -> Node

Look up the node for an ExprId.

Examples found in repository

examples/symbolic_regression.rs (line 216)

fn expr_from_graph(g: &ExprGraph, id: ExprId) -> Expr {
    match g.node(id) {
        tang_expr::node::Node::Var(_) => Expr::X,
        tang_expr::node::Node::Lit(bits) => {
            let v = f64::from_bits(bits);
            if v == 0.0 {
                Expr::Lit(0.0)
            } else {
                Expr::Lit(v)
            }
        }
        tang_expr::node::Node::Add(a, b) => Expr::Add(
            Box::new(expr_from_graph(g, a)),
            Box::new(expr_from_graph(g, b)),
        ),
        tang_expr::node::Node::Mul(a, b) => Expr::Mul(
            Box::new(expr_from_graph(g, a)),
            Box::new(expr_from_graph(g, b)),
        ),
        tang_expr::node::Node::Neg(a) => Expr::Neg(Box::new(expr_from_graph(g, a))),
        tang_expr::node::Node::Sin(a) => Expr::Sin(Box::new(expr_from_graph(g, a))),
        // For operations we don't represent in our AST, just evaluate as literal
        _ => {
            let v = g.eval::<f64>(id, &[1.0]); // fallback
            Expr::Lit(v)
        }
    }
}

pub fn nodes_slice(&self) -> &[Node]

Read-only access to the node arena for serialization.

pub fn var(&mut self, n: u16) -> ExprId

Create a variable node.

Examples found in repository

examples/symbolic_regression.rs (line 60)

    fn to_expr(&self, g: &mut ExprGraph) -> ExprId {
        match self {
            Expr::X => g.var(0),
            Expr::Lit(v) => g.lit(*v),
            Expr::Add(a, b) => {
                let a = a.to_expr(g);
                let b = b.to_expr(g);
                g.add(a, b)
            }
            Expr::Mul(a, b) => {
                let a = a.to_expr(g);
                let b = b.to_expr(g);
                g.mul(a, b)
            }
            Expr::Sin(a) => {
                let a = a.to_expr(g);
                g.sin(a)
            }
            Expr::Neg(a) => {
                let a = a.to_expr(g);
                g.neg(a)
            }
        }
    }

pub fn lit(&mut self, v: f64) -> ExprId

Create a literal node.

Examples found in repository

examples/symbolic_regression.rs (line 61)

    fn to_expr(&self, g: &mut ExprGraph) -> ExprId {
        match self {
            Expr::X => g.var(0),
            Expr::Lit(v) => g.lit(*v),
            Expr::Add(a, b) => {
                let a = a.to_expr(g);
                let b = b.to_expr(g);
                g.add(a, b)
            }
            Expr::Mul(a, b) => {
                let a = a.to_expr(g);
                let b = b.to_expr(g);
                g.mul(a, b)
            }
            Expr::Sin(a) => {
                let a = a.to_expr(g);
                g.sin(a)
            }
            Expr::Neg(a) => {
                let a = a.to_expr(g);
                g.neg(a)
            }
        }
    }

pub fn add(&mut self, a: ExprId, b: ExprId) -> ExprId

Add two expressions.

Examples found in repository

examples/symbolic_regression.rs (line 65)

    fn to_expr(&self, g: &mut ExprGraph) -> ExprId {
        match self {
            Expr::X => g.var(0),
            Expr::Lit(v) => g.lit(*v),
            Expr::Add(a, b) => {
                let a = a.to_expr(g);
                let b = b.to_expr(g);
                g.add(a, b)
            }
            Expr::Mul(a, b) => {
                let a = a.to_expr(g);
                let b = b.to_expr(g);
                g.mul(a, b)
            }
            Expr::Sin(a) => {
                let a = a.to_expr(g);
                g.sin(a)
            }
            Expr::Neg(a) => {
                let a = a.to_expr(g);
                g.neg(a)
            }
        }
    }

pub fn mul(&mut self, a: ExprId, b: ExprId) -> ExprId

Multiply two expressions.

Examples found in repository

examples/symbolic_regression.rs (line 70)

    fn to_expr(&self, g: &mut ExprGraph) -> ExprId {
        match self {
            Expr::X => g.var(0),
            Expr::Lit(v) => g.lit(*v),
            Expr::Add(a, b) => {
                let a = a.to_expr(g);
                let b = b.to_expr(g);
                g.add(a, b)
            }
            Expr::Mul(a, b) => {
                let a = a.to_expr(g);
                let b = b.to_expr(g);
                g.mul(a, b)
            }
            Expr::Sin(a) => {
                let a = a.to_expr(g);
                g.sin(a)
            }
            Expr::Neg(a) => {
                let a = a.to_expr(g);
                g.neg(a)
            }
        }
    }

pub fn neg(&mut self, a: ExprId) -> ExprId

Negate an expression.

Examples found in repository

examples/symbolic_regression.rs (line 78)

    fn to_expr(&self, g: &mut ExprGraph) -> ExprId {
        match self {
            Expr::X => g.var(0),
            Expr::Lit(v) => g.lit(*v),
            Expr::Add(a, b) => {
                let a = a.to_expr(g);
                let b = b.to_expr(g);
                g.add(a, b)
            }
            Expr::Mul(a, b) => {
                let a = a.to_expr(g);
                let b = b.to_expr(g);
                g.mul(a, b)
            }
            Expr::Sin(a) => {
                let a = a.to_expr(g);
                g.sin(a)
            }
            Expr::Neg(a) => {
                let a = a.to_expr(g);
                g.neg(a)
            }
        }
    }

pub fn recip(&mut self, a: ExprId) -> ExprId

Reciprocal (1/x).

pub fn sqrt(&mut self, a: ExprId) -> ExprId

Square root.

pub fn sin(&mut self, a: ExprId) -> ExprId

Sine.

Examples found in repository

examples/symbolic_regression.rs (line 74)

    fn to_expr(&self, g: &mut ExprGraph) -> ExprId {
        match self {
            Expr::X => g.var(0),
            Expr::Lit(v) => g.lit(*v),
            Expr::Add(a, b) => {
                let a = a.to_expr(g);
                let b = b.to_expr(g);
                g.add(a, b)
            }
            Expr::Mul(a, b) => {
                let a = a.to_expr(g);
                let b = b.to_expr(g);
                g.mul(a, b)
            }
            Expr::Sin(a) => {
                let a = a.to_expr(g);
                g.sin(a)
            }
            Expr::Neg(a) => {
                let a = a.to_expr(g);
                g.neg(a)
            }
        }
    }

pub fn atan2(&mut self, y: ExprId, x: ExprId) -> ExprId

atan2(y, x).

pub fn exp2(&mut self, a: ExprId) -> ExprId

Base-2 exponential.

pub fn log2(&mut self, a: ExprId) -> ExprId

Base-2 logarithm.

pub fn select(&mut self, cond: ExprId, a: ExprId, b: ExprId) -> ExprId

Branchless select: returns a if cond > 0, else b.

impl ExprGraph

pub fn simplify(&mut self, expr: ExprId) -> ExprId

Simplify an expression by applying rewrite rules to fixpoint.

Bottom-up: simplify children first, then match parent. Iterates until no more changes occur.

Examples found in repository

examples/symbolic_regression.rs (line 197)

fn mutate_simplify(expr: &Expr) -> Expr {
    let mut g = ExprGraph::new();
    let root = expr.to_expr(&mut g);
    let simplified = g.simplify(root);
    let s = g.fmt_expr(simplified);

    // Quick check: if simplified form is much shorter, it's better
    let orig = expr.format();
    if s.len() < orig.len() {
        // Re-evaluate to confirm it still works
        let test = g.eval::<f64>(simplified, &[1.0]);
        let orig_test = expr.eval_at(1.0);
        if (test - orig_test).abs() < 1e-10 || (test.is_nan() && orig_test.is_nan()) {
            // Return a new tree built from the simplified graph
            return expr_from_graph(&g, simplified);
        }
    }
    expr.clone()
}

/// Reconstruct an Expr tree from an ExprGraph node.
fn expr_from_graph(g: &ExprGraph, id: ExprId) -> Expr {
    match g.node(id) {
        tang_expr::node::Node::Var(_) => Expr::X,
        tang_expr::node::Node::Lit(bits) => {
            let v = f64::from_bits(bits);
            if v == 0.0 {
                Expr::Lit(0.0)
            } else {
                Expr::Lit(v)
            }
        }
        tang_expr::node::Node::Add(a, b) => Expr::Add(
            Box::new(expr_from_graph(g, a)),
            Box::new(expr_from_graph(g, b)),
        ),
        tang_expr::node::Node::Mul(a, b) => Expr::Mul(
            Box::new(expr_from_graph(g, a)),
            Box::new(expr_from_graph(g, b)),
        ),
        tang_expr::node::Node::Neg(a) => Expr::Neg(Box::new(expr_from_graph(g, a))),
        tang_expr::node::Node::Sin(a) => Expr::Sin(Box::new(expr_from_graph(g, a))),
        // For operations we don't represent in our AST, just evaluate as literal
        _ => {
            let v = g.eval::<f64>(id, &[1.0]); // fallback
            Expr::Lit(v)
        }
    }
}

// --- Fitness evaluation ------------------------------------------------------

fn target(x: f64) -> f64 {
    x * x * x.sin()
}

fn generate_data(n: usize, rng: &mut Lcg) -> Vec<(f64, f64)> {
    (0..n)
        .map(|i| {
            let x = -3.0 + 6.0 * i as f64 / (n - 1) as f64;
            let noise = (rng.uniform() - 0.5) * 0.01;
            (x, target(x) + noise)
        })
        .collect()
}

/// Evaluate fitness: MSE + complexity penalty.
fn fitness(expr: &Expr, data: &[(f64, f64)]) -> f64 {
    let mut g = ExprGraph::new();
    let root = expr.to_expr(&mut g);
    let compiled = g.compile(root);

    let mut mse = 0.0;
    for &(x, y) in data {
        let pred = compiled(&[x]);
        if pred.is_nan() || pred.is_infinite() {
            return f64::INFINITY;
        }
        let err = pred - y;
        mse += err * err;
    }
    mse /= data.len() as f64;

    let penalty = 0.001 * expr.size() as f64;
    mse + penalty
}

// --- Selection ---------------------------------------------------------------

fn tournament<'a>(pop: &'a [(Expr, f64)], k: usize, rng: &mut Lcg) -> &'a Expr {
    let mut best_idx = rng.range(pop.len());
    for _ in 1..k {
        let idx = rng.range(pop.len());
        if pop[idx].1 < pop[best_idx].1 {
            best_idx = idx;
        }
    }
    &pop[best_idx].0
}

// --- Main --------------------------------------------------------------------

fn main() {
    println!("=== Symbolic Regression ===\n");
    println!("target: f(x) = x^2 * sin(x)\n");

    let mut rng = Lcg::new(42);
    let data = generate_data(50, &mut rng);

    const POP_SIZE: usize = 200;
    const GENERATIONS: usize = 100;
    const TOURNAMENT_K: usize = 5;

    // Initialize population
    let mut population: Vec<(Expr, f64)> = (0..POP_SIZE)
        .map(|_| {
            let expr = random_expr(4, &mut rng);
            let fit = fitness(&expr, &data);
            (expr, fit)
        })
        .collect();

    let mut best_expr: Option<Expr> = None;
    let mut best_fitness = f64::INFINITY;

    for gen in 0..GENERATIONS {
        // Track best
        for (expr, fit) in &population {
            if *fit < best_fitness {
                best_fitness = *fit;
                best_expr = Some(expr.clone());
            }
        }

        if (gen + 1) % 10 == 0 || gen == 0 {
            let b = best_expr.as_ref().unwrap();
            println!(
                "gen {:>3}: best fitness = {:.6}  nodes = {:>3}  expr = {}",
                gen + 1,
                best_fitness,
                b.size(),
                b.format(),
            );
        }

        // Build next generation
        let mut next_pop = Vec::with_capacity(POP_SIZE);

        // Elitism: keep top 5
        let mut indices: Vec<usize> = (0..population.len()).collect();
        indices.sort_by(|&a, &b| population[a].1.partial_cmp(&population[b].1).unwrap());
        for &i in indices.iter().take(5) {
            next_pop.push(population[i].clone());
        }

        // Fill rest via mutation
        while next_pop.len() < POP_SIZE {
            let parent = tournament(&population, TOURNAMENT_K, &mut rng);
            let child = match rng.range(10) {
                0..=3 => mutate_grow(parent, &mut rng),
                4..=6 => mutate_point(parent, &mut rng),
                7..=8 => mutate_simplify(parent),
                _ => random_expr(4, &mut rng), // fresh blood
            };

            // Skip overly large expressions
            if child.size() > 50 {
                continue;
            }

            let fit = fitness(&child, &data);
            next_pop.push((child, fit));
        }

        population = next_pop;
    }

    // Final results
    println!();
    let best = best_expr.unwrap();
    let mut g = ExprGraph::new();
    let root = best.to_expr(&mut g);
    let simplified = g.simplify(root);
    let expr_str = g.fmt_expr(simplified);
    println!("best expression: {}", expr_str);
    println!("best fitness:    {:.6}", best_fitness);

    // Verify on test points
    println!("\nverification:");
    let compiled = g.compile(simplified);
    for &x in &[-2.0, -1.0, 0.0, 1.0, 2.0] {
        let pred = compiled(&[x]);
        let exact = target(x);
        println!(
            "  f({:>5.1}) = {:>8.4}  (predicted: {:>8.4}, error: {:>8.4})",
            x,
            exact,
            pred,
            (pred - exact).abs()
        );
    }

    // Symbolic derivative via ExprGraph
    let dx = g.diff(simplified, 0);
    let dx = g.simplify(dx);
    println!(
        "\nsymbolic derivative: d/dx [{}] = {}",
        expr_str,
        g.fmt_expr(dx)
    );
}

impl ExprGraph

pub fn deps(&self, expr: ExprId) -> u64

Compute a bitmask of which Var(n) indices appear in expr.

Bit n is set if Var(n) is reachable from expr. Supports up to 64 variables.

pub fn jacobian_sparsity(&self, outputs: &[ExprId], n_vars: usize) -> Vec<u64>

Compute the Jacobian sparsity pattern.

Returns one u64 bitmask per output expression. Bit j of result[i] is set if outputs[i] depends on Var(j).

impl ExprGraph

pub fn to_wgsl(&self, outputs: &[ExprId], n_inputs: usize) -> WgslKernel

Generate a WGSL compute shader that evaluates expressions in parallel.

Each work item reads n_inputs values and writes outputs.len() values. The generated shader uses f32 (GPU native). Shared subexpressions are computed once per thread.

The caller handles device/pipeline/dispatch (no wgpu dependency here).

Trait Implementations

impl Clone for ExprGraph

fn clone(&self) -> ExprGraph

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Default for ExprGraph

fn default() -> Self

Returns the “default value” for a type.