Function libslide::partial_evaluator::flatten::flatten_mul_or_div

fn flatten_mul_or_div(o_lhs: RcExpr, o_rhs: RcExpr, is_div: bool) -> RcExpr

Flattens a multiplication or division, folding constants and like terms as far as possible. The flattened expression is always normalized to a multiplication.

10 * 2x / 5 / 2 / 4x -> x^2/2

How this is done

Consider the expression x*2/y/(5/(x/y)) ~ (/ (/ (* x 2) y) (/ 5 (/ x y))). If they can be unrolled to a series of terms *x, *2, /y, /5, *x, /y, all we have to do is combine like terms and constants, and we're done. Turns out the trickier, and more interesting part, is exactly how to unfold the expression. (There's a reason our example is mostly division.)

Note that the flattening process does not play with commutativity; doing so would never correct.

First, let's assume we've unfolded all subexpressions. This means that all subexpressions will be in multiplicative form; in particular, the example above becomes

x*2*(1/y)/(5*(1/(x*(1/y)))) ~ (/ (* (* x 2) (/ 1 y)) (* 5 (/ 1 (* x (/ 1 y)))))

As we unfold subexpressions, we attach their operands to a double-ended list. The left side of the list represents terms that should be multiplied in the final expression, and the right side represents terms that should be divided. Initially this is just the LHS and RHS of the top level expression. We also keep a registry of unfoldable terms and a variable to fold constants into. In our example, this initially looks like

          mul                       div                    registry       const
----------------------||----------------------------
| (* (* x 2) (/ 1 y)) || (* 5 (/ 1 (* x (/ 1 y)))) |           ∅            1
----------------------||----------------------------
                      ^^-- pivot

Now we go down the list and unfold any binary expression we see, or add fully-unfolded terms to the registry.

We always handle the "multiplication" side first.

Multiplication side

This part is pretty straightforward. When we see a multiplication, we just add both operand to the front of the list. Unfolding (* (* x 2) (/ 1 y)), we get

          mul                       div                  registry       const
--------------------||----------------------------
| (* x 2) | (/ 1 y) || (* 5 (/ 1 (* x (/ 1 y)))) |           ∅            1
--------------------||----------------------------

Which unfolds to

          mul                   div                    registry       const
------------------||----------------------------
| x | 2 | (/ 1 y) || (* 5 (/ 1 (* x (/ 1 y)))) |           ∅            1
------------------||----------------------------

In the next two steps see an unfoldable and a constant, which we add to the registry an fold accordingly.

   mul                  div                    registry       const
----------||----------------------------
| (/ 1 y) || (* 5 (/ 1 (* x (/ 1 y)))) |        {x: 1}          2
----------||----------------------------            ^-- mul: +1, div: -1 for this field

When we see a division, we add the first operand to the multiplication side and the second operand to the division side.

 mul                div                    registry       const
----||--------------------------------
| 1 || (* 5 (/ 1 (* x (/ 1 y)))) | y |      {x: 1}          2
----||--------------------------------

Folding the last term, we only get the division side remaining.

m                div                    registry       const
-||--------------------------------
||| (* 5 (/ 1 (* x (/ 1 y)))) | y |      {x: 1}          2
-||--------------------------------

Division side

This part is a bit trickier because we need to handle nested divisions, which may be equivalent to multiplications on the top level. Maybe it's already clear how to do this; if not, we'll get to it in a bit.

First, let's unfold the first multiplication on the division side by adding both operands to the division side.

To understand why this work, observe that 1 / (2 * 3) is equivalent to (1 / 2) / 3.

m                div                  registry       const
-||------------------------------
||| y | 5 | (/ 1 (* x (/ 1 y))) |      {x: 1}          2
-||------------------------------

The next two terms are added to the registry and constant-folded, respectively.

m           div                  registry       const
-||----------------------
||| (/ 1 (* x (/ 1 y))) |      {x: 1, y: -1}     2/5
-||----------------------

Now we see a division A on the division side. This is the same thing as multiplying the reciprocal of A on the top level!

Let's break down a simpler example. Observe that 1 / (2 / 3) is equivalent to 3 / 2. The flattening list for 1 / (2 / 3) after the folding of 1 looks like

m     div       const
-||----------
||| (/ 2 3) |     1
-||----------

Now we simply add the reciprocal of the division expression to the multiplication side.

    mul     d   const
----------||-
| (/ 3 2) |||     1
----------||-

And we already know this gets unfolded as

 mul  div   const
----||----
| 3 || 2 |    1
----||----

So we can skip adding the entire division to the multiplication side, instead adding the operands where appropriate. The rest of the constant folding follows trivially.

Back to the original example, whose current state is

m           div                  registry       const
-||----------------------
||| (/ 1 (* x (/ 1 y))) |      {x: 1, y: -1}     2/5
-||----------------------

Let's apply our "division in division" algorithm: the left operand gets divided, and the right operand gets multiplied.

      mul         div         registry       const
----------------||----
| (* x (/ 1 y)) || 1 |      {x: 1, y: -1}     2/5
----------------||----

Now we unfold the new expressions on the multiplication side.

     mul        div         registry       const
--------------||----
| x | (/ 1 y) || 1 |      {x: 1, y: -1}     2/5
--------------||----

Two steps this time:

 mul    div           registry       const
----||--------
| 1 || 1 | y |      {x: 2, y: -1}     2/5
----||--------

Three steps this time:

m  d        registry       const
-||-
||||      {x: 2, y: -2}     2/5
-||-

And now, all that needs to be done is to construct the flattened expression 2/5 * x^2 / y^-2.