Feature synthesis by bottom-up enumerative search with observational equivalence — the canonical enumerative method from Solar-Lezama's Introduction to Program Synthesis.

Given a frame and a numeric target column, it searches for a small, interpretable arithmetic expression over the other columns whose values track the target.

The engine:

• enumerates programs by increasing AST size (so the first representative of any behaviour is the smallest — interpretability for free);
• evaluates each candidate incrementally by combining the cached result vectors of its subprograms (one vector op), never re-interpreting the whole tree;
• keeps exactly one program per observational-equivalence class — candidates producing the same column (up to a float tolerance) are interchangeable, so duplicates are dropped rather than re-explored;
• breaks commutative symmetry (never both a+b and b+a) and uses protected operators (sqrt|x|, log(|x|+1)) plus a denominator guard so domain errors never arise;
• caps each size layer by fit score when it grows large (a cost-guided tractability bound over distinct behaviours, not a lossy beam over raw syntax).

fit returns the best SynthesizedFeature; predict is its expression. synthesizeFeatures returns the whole ranked, deduplicated feature bank — useful as automated feature engineering feeding a downstream model.

Deferred (documented next steps, not yet implemented): skeleton enumeration with closed-form least-squares coefficient fitting, hard-row counterexample sampling for very large frames, and piecewise (condition-abduction) features.