In-fix derivation (sicp exercise 2.58 b)

In part 2.3.2 Symbolic Differentiation, we develop a system to calculate simple derivations of calculations in prefix form( such as: + 2 5).

In 2.58 the task is to change this to in-fix form (going with the last example 2 + 5). In addition, it should be able to handle several different operations in a single list(for example 2 * x * x + 5 * x + 3), and correctly prioritize the operations so as to give a correct derivative, without modifying the original deriv procedure.

After going through a lot of dead-end solutions(many of which involved playing around with make-sum and make-product to read ahead and see what else is in the list but were cumbersome and lacking in "elegance") I finally figured out an elegant solution that makes sense.

Here's the initial code that the new data must be matched to:

(define (deriv exp var)
  (cond ((number? exp) 0)
 ((variable? exp)
  (if (same-variable? exp var) 1 0))
 ((sum? exp)
  (make-sum (deriv (addend exp) var)
     (deriv (augend exp) var)))
 ((product? exp)
  (make-sum
   (make-product (multiplier exp)
   (deriv (multiplicand exp) var))
   (make-product (deriv (multiplier exp) var)
   (multiplicand exp))))
 (else
  (error "unknown expression type -- DERIV" exp))))

To achieve it, the "detector functions" (in this case sum? and product?) must be changed to figure if there is a corresponding operation anywhere in the top level.

(define (has-operation? x target)
  (cond ((and (pair? x) (pair? (cdr x)) (eq? (cadr x) target)) #t)
        ((and (pair? x) (pair? (cdr x))) (sum? (cddr x)))
        (else #f)))
(define (sum? x)
        (has-operation? x '+))

(define (product? x)
        (has-operation? x '*))

With this
x * 5 + x * 4

Would be detected as a sum (it would also be detected as a product, but it is derivs job to make sure the operations are handled in the right order).

We want it to be correctly handled as
(x * 5) + (x * 4)

To this end, we redefine addend and augend as:

addend => everything before the +
augend => everything after the +

(define (addend s)
  (before-op s '+))
       
(define (augend s)
  (after-op s '+))

(define (before-op s target)
  (define (list-before s target)
    (if (or (null? s) (eq? (car s) target))
        '()
        (cons (car s) (list-before (cdr s) target))))
  (clean (list-before s target)))

(define (after-op s target)
  (define (list-after s target)
    (cond ((null? (cdddr s)) (caddr s))
          ((eq? target (cadr s)) (cddr s))
          (else (list-after (cddr s) target))))
  (clean (list-after s target)))
    
(define (clean target)
  (cond ((not (pair? target)) target)
        ((null? (cdr target)) (car target))
        (else target)))

In the same way we handle mutiplier and multiplicand(reusing the overlapping code of course)

(define (multiplier p) (before-op p '*))

(define (multiplicand p) 
  (after-op p '*))

The make-product and make-sums are barely changed. The order of the outputted list is about all that changes:

(define (make-sum a1 a2)
  (cond ((and (number? a1) (number? a2)) (+ a1 a2))
        ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        (else (list a1 '+ a2))))

(define (make-product m1 m2) 
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list m1 '* m2))))

The other stuff provided by the problem needed for the program to work:

(define (variable? x) (symbol? x))

(define (=number? exp num)
  (and (number? exp) (= exp num)))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

As a test of all this, passing some derivations:

; x^2 + 2x + 5
(deriv '(x * x + (x + x + 5)) 'x)
;Value 120: ((x + x) + 2)
; 2x + 2

;x^3 + 5x^2 - 3x + 8
(deriv '(x * x * x + x * x * 5 + x * -3 + 8) 'x)
;Value 121: (((x * (x + x)) + (x * x)) + (((x * 5) + (x * 5)) + -3))
;3x^2 + 10x - 3

As to further improvements... Well there is still a lot of work that could be done on simplifying the outputs.

Overall though I am very happy with this solution and would be comfortable adding more operations to deriv(simply add the most "top-level" ops at the top, and they will then properly calculate their subs before operating on them)