[kazinator]

How do we make compilers smart enough to know that “sum(reverse(x))” can be rewritten to “sum(x)”.

That examle is pretty easy; you apply a pattern match to the tree which looks for the pattern (sum (reverse ?var)) and rewrites it to (sum ?var).

In Common Lisp, we would use define-compiler-macro on the sum function which looks for the argument form being (reverse whatever), in which case the macro returns the form (sum whatever).

Not so fast, though; order of summing matters in floating-point! And over integers too, in the presence of overflows (in junk languages without bignums). That is to say, if we add together three or more integers, the arithmetic result can be in range of the type, but some orders might overflow, whereas others do not.

[rntz]

> And over integers too, in the presence of overflows (in junk languages without bignums)

I don't think this is true. Modular addition is commutative and associative. As long as the behavior of overflow is modular (as it is in 2's complement), order shouldn't matter. And if the behavior of overflow is to trap, then it should trap regardless of the order you add the numbers in. I guess if you care about the stack trace you get being the same even under optimizations, then you could argue this isn't a safe optimization. And if the behavior of overflow is undefined, it's undefined whether you reverse the list or not.

Maybe you're thinking of Javascript, which not only doesn't have bignums, but uses floating point even for integers?

[AnimalMuppet]

Seconded. I can't see any encoding system that has fixed-sized integers (and therefore can overflow) where the result of addition is order-dependent. I mean, I'm sure you could design one. But if there's an example of an actually-used encoding that has this property, I'd like to hear it. (And as you said, using floats doesn't count...)

[kazinator]

The result of the addition isn't order dependent; whether or not there is overflow is order-dependent.

I put that into my original comment for the sake of completeness, in an additional edit after the floating-point remark. Ironically, it was to fend off smart-alecky follow-ups about how I forgot integer overflow.

A higher-level language should have a plus operator/function that traps integer overflows if it doesn't provide bignums.

If a sum function is defined as a simple left fold over the sequence using that plus, then part of the semantics of that sum is to throw the exception as soon as adding the next element from the sequence to the left accumulator overflows.

If an order-permuting operation is removed from the expression, it can introduce an overflow where there was none. Perhaps the programmer had that apparently useless order-permuting operation precisely to prevent overflow.

[AnimalMuppet]

I was going to ask, once again, how that is possible, but I think I figured it out while reading this, though you don't explicitly state it.

It can happen if some of the numbers are negative. For a simple example, if overflow occurs at 100, 50+60-20 overflows, but 50-20+60 does not.

[kazinator]

It's very hard to be aware of the numerous details you find obvious yourself when you're communicating.

Also, by the way, I have an intuition that the issue might not specifically prevent the removal of a reverse operation. That is to say, if a series with some positives or negative integers does/doesn't overflow under a left fold, I have a hunch that it does/doesn't under a right fold.

If this can be proven, then that specific case is fine over integers (optimizing away reverse).

[dllthomas]

[1, intmax, -1]

[kazinator]

> And if the behavior of overflow is to trap, then it should trap regardless of the order you add the numbers in.

How come? Suppose A + B doesn't trap, and if T0 = A + B, then T0 + C doesn't trap. Why should (A + B) + C trap?

[prodigal_erik]

Say you have a register whose range is -9..+9. (5-1)+5 doesn't trap but (5+5)-1 does.

[kazinator]

I understand how to make an example of this; the question is why should (5-1)+5 trap, just because (5+5)-1 does.

[rntz]

Ah, good point! I was thinking of unsigned overflow, but signed overflow is a different matter, as pointed out elsewhere in this thread. I retract my statement about trapping overflow.

[pschanely]

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.

[kazinator]

> 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.