tang-expr 0.1.0

RISC expression graph for symbolic computation, differentiation, and compilation
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

# tang-expr

Symbolic expression graphs. Trace Rust math into a DAG, differentiate it, simplify it, compile it to native closures or WGSL compute shaders.

## The pipeline

```
  Rust code           trace           symbolic
  with ExprId   ─────────────►   expression graph
                                       │
                          ┌────────────┼────────────┐
                          │            │            │
                        diff       simplify      deps
                          │            │            │
                     derivatives   fewer nodes   sparsity
                          │            │         bitmask
                          └────────────┼────────────┘
                                       │
                          ┌────────────┼────────────┐
                          │            │            │
                       compile      eval        to_wgsl
                          │            │            │
                     Box<dyn Fn>    f64 value    WGSL kernel
                      (CPU)                      (GPU)
```

## Quickstart

```rust
use tang_expr::{trace, ExprId};

// trace a function into a graph
let (graph, y) = trace(|g| {
    let x = ExprId::var(g, 0);
    let y = ExprId::var(g, 1);
    x * x + y * y
});

// evaluate
let result = graph.eval(y, &[3.0, 4.0]); // 25.0

// differentiate
let mut graph = graph;
let dy_dx = graph.diff(y, ExprId::var(&graph, 0));
let gradient = graph.eval(dy_dx, &[3.0, 4.0]); // 6.0

// simplify
let simplified = graph.simplify(dy_dx);

// compile to native Rust
let f = graph.compile(y);
assert_eq!(f(&[3.0, 4.0]), 25.0);

// compile to WGSL for GPU
let kernel = graph.to_wgsl(&[y], 2);
```

## 9 RISC primitives

All of mathematics reduces to these operations:

```
Add   Mul   Neg   Recip   Sqrt   Sin   Atan2   Exp2   Log2
```

Plus `Var` (input), `Lit` (constant), and `Select` (branchless ternary).

`ExprId` implements the full `Scalar` trait, so `sin`, `cos`, `tan`, `exp`, `ln`, `min`, `max`, `pow`, `atan2` etc. all work through decomposition into the 9 primitives. You trace normal tang math and get a graph for free.

## Sparsity analysis

Know which outputs depend on which inputs without evaluating:

```rust
let sparsity = graph.jacobian_sparsity(&outputs, n_vars);
// sparsity[i] is a u64 bitmask: bit j set means output i depends on var j
```

Supports up to 64 input variables.

## Design

- **Structural interning** — identical subexpressions always share the same `ExprId` (automatic CSE)
- **Thread-local graph** — `trace()` isolates graphs cleanly; `with_graph()` for manual control
- **Memoized differentiation** — `diff()` caches results to avoid redundant work
- **Fixpoint simplification** — rewrites until convergence: constant folding, identity/annihilation rules, cancellation (`x + (-x) → 0`, `x * (1/x) → 1`)
- **Dead code elimination** — `compile()` only emits reachable operations

## License

[MIT](../../LICENSE)