Racket

;
;   *************    SIMPLIFY    **********
;

(define (simplify e rs)
  (if (pair? e)
      (rewrite (simplify-subexpr e rs) rs)
      (rewrite e rs)))

(define (simplify-subexpr es rs)
  (if (not (null? es))
      (cons (simplify (car es) rs) (simplify-subexpr (cdr es) rs))
      `()))

(define (rewrite e rs)
  (define mresult 0)
  (if (not (null? rs))
      (begin
        (set! mresult (match e (caar rs) `()))
        (if (not (equal? `fail mresult))
            (substitude (cdar rs) mresult)
            (rewrite e (cdr rs))))
      e))

(define (substitude rr mlist)
  (if (pair? rr)
      (cons (substitude (car rr) mlist) (substitude (cdr rr) mlist))
      (if (is-var? rr)
          (replace rr mlist)
          rr)))

(define (replace v mlist)
  (if (equal? v (caar mlist))
      (cdar mlist)
      (replace v (cdr mlist))))

(define (match e lr mlist)
  (if (equal? mlist `fail)
      `fail
      (if (pair? lr)
          (if (pair? e)
              (match (cdr e) (cdr lr) (match (car e) (car lr) mlist))
              `fail)
          (if (is-var? lr)
              (if (on-mlist lr mlist)
                  (if (equal? (replace lr mlist) e)
                      mlist
                      `fail)
                  (cons (cons lr e) mlist))
              (if (equal? lr e)
                  mlist
                  `fail)))))

(define (on-mlist v mlist)
  (if (null? mlist)
      #f
      (if (equal? v (caar mlist))
          #t
          (on-mlist v (cdr mlist)))))

(define (is-var? t)
  (and (not (pair? t)) (not (number? t))))


(simplify (devir