Canonicalization

Canonicalization

This document will serve as a place to discuss ideas on how to better do canonicalization. In other words, the things that are currently done by things like Mul.flatten and Add.flatten. Feel free to edit it with your own ideas.

Objects requiring custom logic

I think it would be helpful to list all the kinds of objects we can think of that require custom logic. Since Mul seems to be the most common case, I will just use it exclusively here.

Objects already handled in Mul.flatten

• Infinities: oo, -oo, zoo, and nan. These objects generally eat up other objects, where it is mathematically correct. For example, oo*positive = oo, zoo*non-zero = zoo, nan*anything=nan.

• Imaginary unit: I should combine with I to make -1 automatically. Integer powers of I are automatically evaluated, and complex numbers with real and imaginary parts are not automatically evaluated in a product, so I think this is the only case.

• Non-commutatives: This is a tricky one, and in some sense, completely different from the rest. The only issue here is that the order should be preserved. Also, any commutative expression should be pull out. The way this is done right now is to keep track separately of the "commutative part" and the "non-commutative part". The commutative part is treated almost as a separate Mul multiplying the non-commutative part.

• Numbers: Specifically, Integers, Rationals, and Floats. These are always combined into a single number. In Mul.flatten, they are treated separately as the coefficient.

• Rational powers of rational numbers: Right now, we apply a canonicalization algorithm on rational powers of rational numbers, which reduces powers of the factors of the numbers (we don't factor very large integers, but this is irrelevant here I think). For example, (63/16)**(5/6), 3**(5/3)*(7/16)**(5/6), and (63)**(5/6)/(8*2**(1/3)) are all changed into 3*6**(2/3)*7**(5/6)/16. Once again, all terms must be gathered for this to happen correctly. For example, sqrt(2) and sqrt(6) by themselves to not simplify, but sqrt(2)*sqrt(6) simplfies to 2*sqrt(3). See

Problems

• Commutativity means that we have to consider how an object combines with everything in the Mul, not just what it is next to. So, for example, zoo*x does not reduce to zoo by default, because x could be 0 (in which case it would become nan). But zoo*x*3 should reduce to zoo*x, i.e., the 3 should absorb into the zoo. How can we use Python's double dispatch along with this?

• Commutativity also means that the order of the final expression can (and should) be canonicalized, so that it's easy to assert that x*y == y*x.

• Associativity holds for anything in a Mul, but if rules conflict with each other x*(y*z) might not give the same thing as (x*y)*z, because of the order that things are evaluated in by Python (or by whatever method we end up using). Is this a problem even with non-conflicting rules? How should we deal with conflicting rules?

Unevaluated expressions

• What degree of non-evaluation should we allow? Should we allow 1*1*1*1 (currently impossible). Should we allow to create x*y and y*x as different objects? What about x*(y*z) and (x*y)*z? How are these expressions treated by other functions, which implicitly expect canonicalization to have occurred.