Applying operations until convergence

It often happens that you want to perform a series of operations on an expression, until the expression no longer changes. If it is just a single operation, you can use the repeat=True parameter to the algorithm. Let us have a look at a simple example:

ex:=Q Q Q Q Q Q; substitute(ex, $Q->A+B, A->3, B->5$);

$\displaystyle{}Q Q Q Q Q Q$

$\displaystyle{}\left(A% +B\right) \left(A% +B\right) \left(A% +B\right) \left(A% +B\right) \left(A% +B\right) \left(A% +B\right)$

Here the A->3 and B->5 bits of the substitution rule did not get applied because substitute only ran once. By adding the repeat=True flag you get the expected result:

ex:=Q Q Q Q Q Q; substitute(ex, $Q->A+B, A->3, B->5$, repeat=True);

$\displaystyle{}Q Q Q Q Q Q$

$\displaystyle{}262144$

However, this only works if you have a single algorithm to work with. If you want to apply a series of algorithms, you need to use the Cadabra specific converge construction (which is an extension of Python). It works very similar to a while loop, and will run until the indicated expression no longer changes. Here is an example:

ex:=Q Q Q Q Q Q; converge(ex): substitute(_, $Q->A+B, A B->3$, repeat=True); distribute(_);

$\displaystyle{}Q Q Q Q Q Q$

Q Q Q Q Q Q

$\displaystyle{}\left(A +B\right) \left(A +B\right) \left(A +B\right) \left(A +B\right) \left(A +B\right) \left(A +B\right)$

(A + B) (A + B) (A + B) (A + B) (A + B) (A + B)

$\displaystyle{}A A A A A A +A A A A A B +A A A A B A +A A A A B B +A A A B A A +A A A B A B +A A A B B A +A A A B B B +A A B A A A +A A B A A B +A A B A B A +A A B A B B +A A B B A A +A A B B A B +A A B B B A +A A B B B B +A B A A A A +A B A A A B +A B A A B A % +A B A A B B +A B A B A A +A B A B A B +A B A B B A +A B A B B B +A B B A A A +A B B A A B +A B B A B A +A B B A B B +A B B B A A +A B B B A B +A B B B B A +A B B B B B +B A A A A A +B A A A A B +B A A A B A +B A A A B B +B A A B A A +B A A B A B % +B A A B B A +B A A B B B +B A B A A A +B A B A A B +B A B A B A +B A B A B B +B A B B A A +B A B B A B +B A B B B A +B A B B B B +B B A A A A +B B A A A B +B B A A B A +B B A A B B +B B A B A A +B B A B A B +B B A B B A +B B A B B B +B B B A A A % +B B B A A B +B B B A B A +B B B A B B +B B B B A A +B B B B A B +B B B B B A +B B B B B B$

A A A A A A + A A A A A B + A A A A B A + A A A A B B + A A A B A A + A A A B A B + A A A B B A + A A A B B B + A A B A A A + A A B A A B + A A B A B A + A A B A B B + A A B B A A + A A B B A B + A A B B B A + A A B B B B + A B A A A A + A B A A A B + A B A A B A + A B A A B B + A B A B A A + A B A B A B + A B A B B A + A B A B B B + A B B A A A + A B B A A B + A B B A B A + A B B A B B + A B B B A A + A B B B A B + A B B B B A + A B B B B B + B A A A A A + B A A A A B + B A A A B A + B A A A B B + B A A B A A + B A A B A B + B A A B B A + B A A B B B + B A B A A A + B A B A A B + B A B A B A + B A B A B B + B A B B A A + B A B B A B + B A B B B A + B A B B B B + B B A A A A + B B A A A B + B B A A B A + B B A A B B + B B A B A A + B B A B A B + B B A B B A + B B A B B B + B B B A A A + B B B A A B + B B B A B A + B B B A B B + B B B B A A + B B B B A B + B B B B B A + B B B B B B

$\displaystyle{}A A A A A A +18A A A A +135A A +540 +135B B +18B B B B +B B B B B B$

A A A A A A + 18A A A A + 135A A + 540 + 135B B + 18B B B B + B B B B B B

$\displaystyle{}A A A A A A +18A A A A +135A A +540 +135B B +18B B B B +B B B B B B$

A A A A A A + 18A A A A + 135A A + 540 + 135B B + 18B B B B + B B B B B B

$\displaystyle{}A A A A A A +18A A A A +135A A +540 +135B B +18B B B B +B B B B B B$

A A A A A A + 18A A A A + 135A A + 540 + 135B B + 18B B B B + B B B B B B

$\displaystyle{}A A A A A A +18A A A A +135A A +540 +135B B +18B B B B +B B B B B B$

A A A A A A + 18A A A A + 135A A + 540 + 135B B + 18B B B B + B B B B B B

We have added semicolons to every line in order to show precisely what happens: in the first iteration, the substitution expands $Q$ to $A+B$. This gives an expression in which there are no $AB$ factors yet. Those arise only once the distribute algorithm is called. At the second iteration, the substitution algorithm then replaces the $AB$ product with $3$.

As far as the output is concerned, the last line is repeated 4 times. First as the result of the working substitute, then because of the distribute call which follows (and does nothing). The loop then runs once more because the expression has changed, creating two more output lines. As this is a bit verbose, one would normally suppress the printing inside the converge block and only print at the end, as in:

ex:=Q Q Q Q Q Q; converge(ex): substitute(_, $Q->A+B, A B->3$, repeat=True) distribute(_) ;

$\displaystyle{}Q Q Q Q Q Q$

$\displaystyle{}A A A A A A% +18A A A A% +135A A% +540% +135B B% +18B B B B% +B B B B B B$

Note the semi-colon ; at the very end of the converge block, which triggers printing of the final result.