Expression Simplification

Question

I have this code to calculate derivatives:

(define (diff x expr)
  (if  (not (list? expr))
    (if  (equal? x expr) 1 0)
    (let ((u (cadr expr)) (v (caddr expr)))
     (case (car expr)
       ((+) (list '+ (diff x u) (diff x v)))
       ((-) (list '- (diff x u) (diff x v)))
       ((*) (list '+
                   (list  '* u (diff x v))
                   (list  '* v (diff x u))))
        ((/) (list ‘div (list '-
                  (list  '* v (diff x u))
                  (list  '* u (diff x v)))
                  (list  '* u v)))
))))

How can I simplify algebraic expressions?

instead of x + x show 2x

and

instead of x * x show x^2

Answer 1

Simplification of algegraic expressions is quite hard, especially compared to the computation of derivates. Simplification should be done recursively. You simplify the innermost expressions first. Don't try too much at a time. I'd start with the most basic simplifications only e.g:

 0 + x -> x
 0 * x -> 0
 1 * x -> x
 x ^ 0 -> 1
 x ^ 1 -> x

Replace subtraction by addition and division by multiplication

 x - y -> x + (-1)*x
 x / y -> x ^ (-1)

This may not look as a simplification, but it will simplify your code. You can always reverse this step at the end.

Then you use associativity and commutativity to sort your terms. Move numerical values to the left side, sort variables by some predefined order (it doesn't have to be alphabetical but it should always be the same)

 (x * y) * z -> x * (y * z)
 x * 2 -> 2 * x
 2 * (x * 3) -> 2 * (3 * x)

Simplify exponents

  (x ^ y) ^ z -> x^(y * z)

Simplify the numerical parts.

 2 * (3 * x) -> 6 * x
 2 + (3 + x) -> 5 + x

Once you have done this you can think about collecting common expressions.

Answer 2

Perhaps this code from PAIP will be useful. It's Common Lisp, which is quite similar to Scheme. The entry point is the simp function.

Note that it also uses this file.

Historical note: The relevant PAIP chapter refers to Macsyma, the computer algebra system developed in MIT in the 1960s, and was the basis for Mathematica, Maple (now in Matlab) and other tools.