SICP Exercise 2.58: Infix Operators... Part (a), The Easy Teen-age New York Version

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 how 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 parenthesized.
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?

Given that the last exercise took somewhat longer than I'd intended, and in an attempt to regain some momentum, I've decided I'll split this exercise into two posts, one for each part of this question. In this post we'll deal with part (a) only, which allows us to ignore the associativity of the operations and just handle infix expressions with two operands.

This will be the shorter of the two posts...

Let's look at the difference between the prefix notation introduced in the book (i.e. prior to the work we did in exercise 2.57) and what we need for the first part of the exercise. In the book we represent ax + b as (+ (* a x) b), while for this part we want to be able to support representing it as ((a * x) + b). In both cases we have a 3-tuple at each level within the expression consisting of an operator and two operands. The difference between the prefix and infix notations is simply that in the former the operator is the first element of the tuple, whilst in the latter it is the second element.

Given that the sole difference between the two notations is the location of the operator (and, by implication, the first operand) we should be able to take the basic implementation of the program we have from the book and exercise 2.56 and simply change the procedures that will be affected by this change in ordering. I.e. the tests, constructors and the selectors for the first operand.

So our tests become:

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

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

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

...and the constructors become:

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

(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-exponentiation base exponent)
  (cond ((=number? base 1) 1)
        ((=number? exponent 0) 1)
        ((=number? exponent 1) base)
        ((and (number? base) (number? exponent)) (expt base exponent))
        (else (list base '** exponent))))

...and the selectors for the first operand become:

(define (addend s) (car s))

(define (multiplier p) (car p))

(define (base x) (car x))

The remainder of our program is unchanged.

So let's construct some expressions:

> (make-sum 'x 3)
'(x + 3)
> (make-product 'x 'y)
'(x * y)
> (make-product (make-product 'x 'y) (make-sum 'x 3))
'((x * y) * (x + 3))
> (make-exponentiation 'a 'b)
'(a ** b)
> (make-exponentiation 'a (make-sum 'a 'b))
'(a ** (a + b))

All looks good, so let's try a few tests:

> (sum? (make-sum 'x 3))
#t
> (product? (make-sum 'x 3))
#f
> (product? (make-product 'x 'y))
#t
> (exponentiation? (make-product 'x 'y))
#f
> (exponentiation? (make-exponentiation 'a 'b))
#t
> (sum? (make-exponentiation 'a 'b))
#f

And let's check the selectors:

> (addend (make-sum 'x 3))
'x
> (augend (make-sum 'x 3))
3
> (multiplier (make-product 'x 'y))
'x
> (multiplicand (make-product 'x 'y))
'y
> (base (make-exponentiation 'a (make-sum 'a 'b)))
'a
> (exponent (make-exponentiation 'a (make-sum 'a 'b)))
'(a + b)

Finally, let's test that deriv still works:

> (deriv (make-sum 'x 3) 'x)
1
> (deriv (make-product 'x 'y) 'x)
'y
> (deriv (make-product (make-product 'x 'y) (make-sum 'x 3)) 'x)
'((x * y) + (y * (x + 3)))
> (deriv (make-exponentiation 'a (make-sum 'a 'b)) 'a)
'((a + b) * (a ** ((a + b) + -1)))

All appears in order, so now onto part (b)...