Great observations. For the purposes of this exploration, I am entirely assuming arbitrary precision integers (and the math geek in me is really enjoying your use of the adjective "junk", above).
Bigger picture, I want to rewrite "sum(reverse(x))" without explicitly saying so. How do we optimize that expression using the definitions of sum and reverse? Note that in my discussion of this in my second example, I am inconsistent here: I expand the definition of reverse() but treat sum() as a primitive. That said, I am pretty sure that the example still works if you substitute the appropriate definition of sum as "reduce(add,x)"; the derivation is just longer.
> I want to rewrite "sum(reverse(x))" without explicitly saying so.
You can endow functions with attributes (standard functions in the language library, and possibly user-defined ones). The reverse function can carry the attribute that it only changes the order of the elements of its argument. This is encoded as some boolean predicate: (order-identity-p x) is true if x is reverse. And if x is other things, like the identity function, the sort function and whatnot.
Then our optimzer looks for the pattern/rewrite (sum (f? arg?)) -> (sum arg?), where there is a semantic constraint: the pattern matches subject to the predicate (order-identity-p f?). This is effectively part of the match; if the predicate fails, there is no match.
Now the sum function could also be "patterned out". There could be a predicate which asserts that certain arguments of a function are sequences whose order doesn't matter to the outcome. This predicate could be list valued. If an argument has no such arguments, it returns nil/false, otherwise a list of the argument positions or whatever.
So then we're looking for the pattern (f? (g? arg?)) -> (f? arg) which is very general, and can be met in lots of ways. For instance, suppose f? and g? are the same function, and f? is idempotent. One of the rules that applies is that g? satisfies (order-identity-p g?), and (order-irrelevant-args f?) returns (1), where we note that (g? ...) is argument 1 of f?. For any argument argument expression which is an orer-identity-p function call, if that argument's position is in the list returned by order-irrelevant-args on the main constituent function, we can remove that order-altering function from the argument.
We code all that up into the tree walking engine, and then just suitably declare attributes on functions.
Bigger picture, I want to rewrite "sum(reverse(x))" without explicitly saying so. How do we optimize that expression using the definitions of sum and reverse? Note that in my discussion of this in my second example, I am inconsistent here: I expand the definition of reverse() but treat sum() as a primitive. That said, I am pretty sure that the example still works if you substitute the appropriate definition of sum as "reduce(add,x)"; the derivation is just longer.