SICP Exercise 2.58

Question

Suppose we want to modify the differentiation program so that it works with ordinary mathematical notation, in which + and * are infix rather than prefix operators. Since the differentiation program is defined in terms of abstract data, we can modify it to work with different representations of expressions solely by changing the predicates, selectors, and constructors that define the representation of the algebraic expressions on which the differentiator is to operate.

1. Show to do this in order to differentiate algebraic expressions presented in infix form, such as (x + (3 * (x + (y + 2)))). To simplify the task, assume that + and * always take two arguments and that expressions are fully parenthesised.
2. The problem becomes substantially harder if we allow standard algebraic notation, such as (x + 3 * (x + y + 2)), which drops unnecessary parentheses and assumes that multiplication is done before addition. Can you design appropriate predicates, selectors, and constructors for this notation such that our derivative program still works?

Answer

The easiest way to start here is probably the constructors. The only thing that needs to be modified is the list construction, as can be seen in the highlighted lines.

(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))))

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

Let us now turn our attention to the predicates that determine whether something is a sum or a product, or neither. Before, we had to check if the first element of a list (the car​) was an operator such as '* or '+​. Now, this should be the second element or the cadr. This is the only change needed here.

(define (product? x)
  (and (pair? x) (eq? (cadr x) '*)))

(define (sum? x)
  (and (pair? x) (eq? (cadr x) '+)))

And finally, the selectors. We only need to modify multiplier and addend here. These used to be the second list element, but now are the first. The multiplicand and augend remain in their position on the third place in the list and do not have to be changed at all.

(define (multiplier p) (car p))
(define (multiplicand p) (caddr p))

(define (addend s) (car s))
(define (augend s) (caddr s))

Let’s test the function from the question:

(deriv '(x + (3 * (x + (y + 2)))) 'x)

Result:

4

The result is correct, since \[\frac{\partial}{\partial x}(x+(3\times (x+(y+2))))\] \[=\frac{\partial}{\partial x}(x+3(x+y+2))\] \[=\frac{\partial}{\partial x}(4x+3y+6)\] \[=4\]

Now for the second part of the question.

First, we need a function to figure out the lowest priority operator within the expression. If + exists, it always has the lowest priority, followed by * and finally ** with the highest priority. We can use memq for this:

(define (lowest-op exp)
  (cond ((memq '+ exp) '+)
        ((memq '* exp) '*)
        ((memq '** exp) '**)
        (else (error "expression contains no operand: LOWEST-OP" exp))))

This works because the conditionals are evaluated in order. If a + exists anywhere in the equation, it will be returned as lowest-op.

This now allows us to rewrite our sum?, product? and exponentiation? functions using lowest-op:

(define (sum? x) (eq? (lowest-op x) '+))
(define (product? x) (eq? (lowest-op x) '*))
(define (exponentiation? x) (eq? (lowest-op x) '**))

Next, we need to turn our attention to the selectors. For the selectors targeting the second operand (augend, multiplicand and exponent), we can simply use memq with the operator. However, if we have a regular function like (x + 2), this will return (2) rather than 2 for the augend. To prevent this, we add another function to check whether the second operand is atomic i.e. a single value rather than an expression.

(define (atomic? exp) (null? (cdr exp)))

(define (augend s)
  (if (atomic? (cdr (memq '+ s))) (car s) s))

(define (multiplicand p)
  (if (atomic? (cdr (memq '* p))) (car p) p))

(define (exponent p)
  (if (atomic? (cdr (memq '** p))) (car p) p))

Unfortunately, Scheme does not come with an inverse function of memq, so getting the first operand is a little more difficult. Some Scheme dialects have a function called list-head serving a similar purpose, but mine does not. I used an implementation of this function by saulgoode that can be found here: http://paste.lisp.org/display/146734

This can then be used to write a function to get the first operand:

(define (get-first-operand exp operator)
  (list-head exp (- (length exp)
                    (length (memq operator exp)))))

Now we can rewrite addend, multiplier and base, again making sure to check for atomicity.

(define (addend s)
  (let ((a (get-first-operand s '+)))
    (if (atomic? a) (car a) a)))

(define (multiplier p)
  (let ((a (get-first-operand p '*)))
    (if (atomic? a) (car a) a)))

(define (base p)
  (let ((a (get-first-operand p '**)))
    (if (atomic? a) (car a) a)))

And that’s it. We don’t need to change the constructors at all.