Constant expression hoisting for iteration loops

[djdarcy]

Constant expression hoisting for iteration loops

Problem

When an expression like does_exist primesum(n,2) == trisum(666) is evaluated, the RHS trisum(666) contains no free variables — it's a constant. But the current evaluation engine recomputes it on every iteration of n, turning an O(1) computation into O(N) redundant calls.

For cheap functions this is negligible. For expensive ones like trisum(666) (which computes a 98-digit number by summing 36 rows of base-666 digit arrangements), the overhead is significant — especially when N could be in the billions.

Proposed solution

Constant folding / expression hoisting: Before entering the iteration loop, walk the AST and identify subexpressions that contain no free variables (no iteration variables like n, m, etc.). Evaluate these once and replace them with their computed values.

Detection strategy

def find_free_vars(node) -> set:
    """Return set of variable names referenced in this AST node."""
    if isinstance(node, Variable): return {node.name}
    if isinstance(node, FunctionCall): return union(find_free_vars(arg) for arg in node.args)
    if isinstance(node, BinaryOp): return find_free_vars(node.left) | find_free_vars(node.right)
    ...

def hoist_constants(expr, iter_vars):
    """Pre-evaluate subexpressions with no free iteration variables."""
    free = find_free_vars(expr)
    if not (free & iter_vars):  # No overlap with iteration variables
        return Literal(evaluate(expr))  # Compute once, replace with constant
    # Otherwise recurse into children
    ...

Examples

Expression	Free vars	Hoisted?
primesum(n,2)	{n}	No — depends on iteration var
trisum(666)	{}	Yes — computed once
primesum(n,2) == trisum(666)	LHS: {n}, RHS: {}	RHS hoisted
primesum(n, m)	{n, m}	No — both are iteration vars
tri(36) + 1	{}	Yes — entire subexpression hoisted
primesum(n, 2) == 666	LHS: {n}, RHS: {}	RHS already a literal (no change)

Implementation location

The hoisting pass should run in find_matches() (in prime-square-sum.py) after parsing and before the iteration loop begins. The AST is already available from the grammar parser.

Impact

• Core use case: does_exist primesum(n,2) == trisum(666) — the project's central question. Without hoisting, this recomputes a 98-digit number billions of times.
• General benefit: Any expression mixing iteration variables with constant function calls benefits automatically.
• No API change: Pure internal optimization, transparent to users.

Related

• Issue Smart Early Termination: Stop iteration when computed values exceed threshold #23: Smart early termination (complementary — hoisting reduces per-iteration cost, Smart Early Termination: Stop iteration when computed values exceed threshold #23 reduces iteration count)
• Issue Multi-variable iteration strategies (product, parallel, adaptive) #42: Multi-variable iteration strategies (hoisting applies to multi-var too)

[djdarcy]

Acceptance Criteria — Issue #60: Constant expression hoisting

Must Have

1. AST free-variable detection: A function find_free_vars(node) -> set[str] that walks the parsed AST and returns the set of variable names referenced. This is the foundation for hoisting decisions.

2. Pre-evaluation pass: Before the iteration loop in find_matches(), identify all subexpressions whose find_free_vars() result has no overlap with the iteration variables (e.g., n, m). Evaluate these subexpressions once and replace them with literal values.

3. Correct behavior for the core use case:

   python prime-square-sum.py --expr "does_exist primesum(n,2) == trisum(666)"

   trisum(666) must be computed exactly once (not per-iteration). The computed constant should be visible when running with -vv or higher verbosity (e.g., [hoisted] trisum(666) = 37005...290).

4. Nested constant expressions: Compound expressions like tri(36) + 1 or trisum(tri(36)) where the entire subtree has no free variables should also be hoisted as a single constant.

5. No change for variable-dependent expressions: primesum(n, 2) must NOT be hoisted (it depends on iteration var n). Mixed expressions like primesum(n, 2) + trisum(666) should hoist only the trisum(666) subtree.

6. Zero regressions: All existing tests pass. The optimization is transparent — same results, just faster.

Should Have

7. Verbosity output (-v or -vv): Log hoisted expressions and their computed values so users can verify the optimization is active. Channel: 'optimization' or 'hoist'.

8. Timing comparison: At -vv, show time saved (e.g., [hoist] trisum(666) evaluated once in 0.3s (saved ~N recomputations)).

Nice to Have

9. Partial hoisting in function arguments: In primesum(n, tri(36)), the second argument tri(36) is constant even though the function call itself depends on n. Hoist the argument subtree.

10. Cache for repeated constant subexpressions: If the same constant appears in multiple places in the expression, compute once and reuse.

Verification

• Unit test: expression with trisum(666) on RHS runs in O(1) RHS evaluations regardless of --max-n
• Unit test: primesum(n, 2) is NOT hoisted (still evaluated per-iteration)
• Unit test: nested constants like tri(tri(4)) are fully hoisted
• Integration test: does_exist primesum(n,2) == trisum(10) still finds n=7