Bug report ID:635627 - subst([...] is order-dependent

We have the open bug report ID:635627 - subst([...] is order-dependent.

I have tried a general algorithm which does the substitution in
parallel. These are the steps I have implemented:

1. Switch off simplification during the phase of substitution.
2. Replace first the left hand side of each equation with a gensym
   and substitute the gensym into the expression.
3. Then replace the gensym with the right hand side of the equation.
4. Resimplify the new expression.

With the new code we get e.g. for the examples of the bug report:

(%i5) subst ([a=b,b=a], sin(a)+sin(b));
(%o5) sin(b)+sin(a)

(%i6) subst([a=0,b=0],atan2(a,b));
atan2: atan2(0,0) is undefined.
-- an error. To debug this try: debugmode(true);

(%i7) subst(["="="+","["="*"],[x=1,x=2]);
(%o7) (x+1)*(x+2)

(%i8) subst(["["="*","="="+"],[x=1,x=2]);
(%o8) (x+1)*(x+2)

(%i9) subst([a=[1,2],b=[3,4]],a+b);
(%o9) [4,6]

In addition to the function sublis subst can do parallel substitution
not only for atoms on the left hand side, but for expressions too:

(%i10) subst([x^2=y^2,y^2=x^2],exp(x^2)+sin(y^2));
(%o10) %e^y^2+sin(x^2)

There is no change for a call of $substitute with three arguments and
with one equation as a first argument. 

There is one big problem. The code of to_poly_solve expects a function
subst, which does not do the substitution in parallel, but does the
substitution along the list of equations.

This is a typical list of equations we get in to_poly_solve. 

(%i3) ll;
(%o3) [%g2652 = %i,x = %c2654,%c2654 = 2*%pi*%z2659+%pi/2]

This is what to_poly_solve expects:

(%i4) subst(ll,x);
(%o4) 2*%pi*%z2659+%pi/2

When I load the modified function $substitute, which does the
substitution in parallel we get:

(%i5) load("subst.lisp");
(%o5) "subst.lisp"

(%i6) subst(ll,x);
(%o6) %c2654

The last substitution for the symbol %c2654 is no longer done with the
code which does the substitution in parallel.

The testsuite has no problems. The only problem is the code of
to_poly_solve.

So, the question arises, if the substitution in parallel is desired. If
we wish to have this feature, the code of to_poly_solve must be modified
in a way that it does not depend on the current behavior of $substitute
to do the substitution step by step for the equations in the list.


This is the code of the modified routine $substitute:

(defmfun $substitute (old new &optional (expr nil three-arg?))
  (cond (three-arg? (maxima-substitute old new expr))
        (t
         (let ((l old) (z new))
           (cond ((and ($listp l)
                       ($listp (cadr l))
                       (null (cddr l)))
                  ;; A nested list.
                  ($substitute (cadr l) z))
                 ((and ($listp l)
                       (eq (caar (cadr l)) 'mequal)
                       (null (cddr l)))
                  ;; A list with one equation.
                  ($substitute (cadr l) z))
                 ((notloreq l) (improper-arg-err l '$substitute))
                 ((eq (caar l) 'mequal)
                  ;; Do substitution for one equation.
                  (maxima-substitute (caddr l) (cadr l) z))
                 (t
                  ;; We have a list of equations. 
                  ;; We do parallel substitution.
                  (let (gensymbol genlist eqn ($simp nil))
                    ;; At first substitute a gensym for the expressions
                    ;; of the left hand side of the equations.
                    (do ((l (cdr l) (cdr l)))
                        ((null l) z)
                      (setq eqn (car l))
                      (when (not (eq 'mequal (caar eqn)))
                        (improper-arg-err old '$substitute))
                      (setq gensymbol (gensym))
                      ;; Store the gensym and the new expression 
                      ;; into a list.
                      (push (cons gensymbol (caddr eqn)) genlist)
                      ;; Substitute a gensym for the old expression.
                      (setq z (maxima-substitute gensymbol (cadr eqn)
z)))
                      ;; Substitute the new epressions for the gensyms.
                      (do ((l genlist (cdr l)))
                          ((null l)
                           ;; Resimplify the new expression and 
                           ;; return the result.
                           (let (($simp t)) (resimplify z)))
                        (setq z (maxima-substitute (cdar l) (caar l)
z))))))))))

Dieter Kaiser