[kragen]

what's the scenario where you'd materialize the values of all those terms at once? maybe cache-invalidation-based incremental evaluation, like acar's self-adjusting computation? affine arithmetic (or raa) seems like it could be a good fit for that kind of thing, because it can handle small input changes within the affine approximation (with just a multiply-accumulate) and sometimes would benefit from being able to recursively subdivide the input space into smaller intervals without recomputing unaffected parts of the expression

on the other hand, if i am merely evaluating a polynomial with n terms, such as 3x⁴ - 2x³ + 17x² + x - 4 for n = 5, i only have three aa objects at any one time during evaluation of the expression, regardless of n. in this case the program might look like this

    a ← x; a ← a⁴; b ← 3; a ← a · b
    b ← x; b ← b³; c ← -2; b ← b · c; a ← a + b
    b ← x; b ← b²; c ← 17; b ← b · c; a ← a + b
    b ← x; a ← a + b
    b ← -4; a ← a + b

this assumes we have three registers for aa objects, creatively called a, b, and c; that we can only do arithmetic on these registers; and that the power operations are unary (otherwise they require an additional register)

this is true of any polynomial

with horner's-rule evaluation we can cut this down to two registers

    a ← 3
    b ← x; a ← a · b; b ← -2; a ← a + b
    b ← x; a ← a · b; b ← 17; a ← a + b
    b ← x; a ← a · b; b ← 1;  a ← a + b
    b ← x; a ← a · b; b ← -4; a ← a + b

obviously there do exist expressions with deeper minimum evaluation stacks, but i think they're only worst-case logarithmic in expression size, aren't they?

[moonchild]

(dynamic) computation forms a dag, not a tree. i think a sum scan (n inputs -> n outputs) will trigger the worst case. it might be that computations tend to be tree-shaped, so you rarely hit the worst case, but that helps everybody out, not just affine arithmetic

[kragen]

that's a good point; i was thinking of single-output expressions, where i think always evaluating the deepest subtree first limits your space usage to worst-case logarithmic?

[moonchild]

even single-output is a dag; you can explode the dag into a tree, but then you pay in time. suppose some expensive term x is used to compute n other terms. after computing x, assuming we want to share it, we have to compute all n terms before killing x; hence x sticks around longer than it might. (this doesn't necessarily lead to explosion, but i'm pretty sure you can use this to construct a scenario that needs a large number of live terms to avoid compromising time complexity; at least n live terms if the dag has nlogn nodes)