; http://www.cs.nyu.edu/courses/summer07/G22.2110-001/hw02-scm-example.txt

; Rename this file into 'differentiator.scm'. 

(define (toStrng e)
  (cond
    ((equal? (car e) 'CONST) (number->string (cadr e)))
    ((equal? (car e) 'VAR)   (symbol->string (cadr e)))
    (else
      (let ((op (car e)) (s1 (toStrng (cadr e))) (s2 (toStrng (caddr e))))
        (case op
          ((ADD) (string-append "(" s1 " + " s2 ")"))
          ((SUB) (string-append "(" s1 " - " s2 ")"))
          ((MUL) (string-append "(" s1 " * " s2 ")"))
          ((DIV) (string-append "(" s1 " / " s2 ")")))))))

(define (diff e)
  (cond
    ((equal? (car e) 'CONST) '(CONST 0))
    ((equal? (car e) 'VAR)
      (if (equal? (cadr e) 'x) '(CONST 1) '(CONST 0)))
    (else
      (let ((op (car e)) (e1 (cadr e)) (e2 (caddr e)))
        (case op
          ((ADD SUB) (list op (diff e1) (diff e2)))
          ((MUL) (list 'ADD (list 'MUL e1 (diff e2)) 
                            (list 'MUL e2 (diff e1))))
          ((DIV) (list 'DIV (list 'SUB (list 'MUL e2 (diff e1))
                                       (list 'MUL e1 (diff e2)))
                            (list 'MUL e2 e2))))))))

(define (simplify* e)
  (case (car e)
    ((CONST) e)
    ((VAR) e)
    (else
      (let ((op (car e)) (e1 (cadr e)) (e2 (caddr e)))
        (cond
          ((and (equal? op 'ADD) (equal? e2 '(CONST 0))) e1)
          ((and (equal? op 'ADD) (equal? e1 '(CONST 0))) e2)
          ((and (equal? op 'SUB) (equal? e2 '(CONST 0))) e1)
          ((and (equal? op 'MUL) (equal? e2 '(CONST 0))) '(CONST 0))
          ((and (equal? op 'MUL) (equal? e1 '(CONST 0))) '(CONST 0))
          ((and (equal? op 'MUL) (equal? e2 '(CONST 1))) e1)
          ((and (equal? op 'MUL) (equal? e1 '(CONST 1))) e2)
          (else e))))))

(define (simplify e)
  (case (car e)
    ((CONST) e)
    ((VAR) e)
    ((ADD SUB MUL DIV) (simplify* (list (car e) 
                                        (simplify (cadr e))
                                        (simplify (caddr e)))))))

(define (main e)
  (display (string-append "e = " (toStrng e) "\n"))
  (display (string-append "de/dx = " (toStrng (simplify (diff e))) "\n")))

(main '(ADD (MUL (CONST 3) (VAR x)) (MUL (VAR x) (VAR x))))