SICP Exercise 2.56: Differentiating Exponentials

Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule

d(un) = nxn-1 du
 dx          dx

by adding a new clause to the deriv program and defining appropriate procedures exponentiation?, base, exponent, and make-exponentiation. (You may use the symbol ** to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself.

Let's start with the procedures... And in fact let's do them in the reverse order in which they're listed above, and start with make-exponentiation. Like the implementations of make-sum and make-product we want to build in some rules that reduce the expression to its simplest form. For exponents we can define the following reductions:

• 1 raised to the power of anything is 1.
• Anything raised to the power of 0 is 1.
• Anything raised to the power of 1 is itself.
• If both the base and the exponent are numbers then make-exponentiation can calculate and return the exponent.

In any other case we simply build up the appropriate list representation and return that. This gives us the following implementation:

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

Let's check this works:

> (make-exponentiation 1 24)
1
> (make-exponentiation 2 4)
16
> (make-exponentiation 'a 3)
(** a 3)
> (make-exponentiation 5 'b)
(** 5 b)
> (make-exponentiation 'a 'b)
(** a b)
> (make-exponentiation 'a 1)
a
> (make-exponentiation 'a 0)
1
> (make-exponentiation 4 1)
4
> (make-exponentiation 4 0)
1

The selectors and predicates then just follow the same pattern as the equivalents for sums and products:

(define (base x) (cadr x))
(define (exponent x) (caddr x))
(define (exponentiation? x)
  (and (pair? x) (eq? (car x) '**)))

And again, a quick test:

> (base (make-exponentiation 'a 'b))
a
> (exponent (make-exponentiation 'a 'b))
b
> (exponentiation? (make-exponentiation 'a 'b))
#t
> (exponentiation? (make-product 'a 'b))
#f

All we need to do now is to extend deriv, adding a clause that uses exponentiation? to test whether or not the expression is an exponentiation and, if it is, applies the differentiation rule:

(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))))
        ((exponentiation? exp)
         (make-product
           (make-product (exponent exp)
                         (make-exponentiation (base exp)
                                              (make-sum (exponent exp) -1)))
           (deriv (base exp) var)))
        (else
         (error "unknown expression type -- DERIV" exp))))

Let's give this a spin:

> (deriv (make-exponentiation 'a 5) 'a)
(* 5 (** a 4))
> (deriv (make-exponentiation 'a 'b) 'a)
(* b (** a (+ b -1)))
> (deriv (make-exponentiation 'a (make-sum 'a 'b)) 'a)
(* (+ a b) (** a (+ (+ a b) -1)))

SICP Exercise 2.55: Quoted Quotes

Eva Lu Ator types to the interpreter the expression

(car ''abracadabra)

To her surprise, the interpreter prints back quote. Explain.

As noted in footnote 34, the single quotation mark is equivalent to the special form quote... and in fact the single quotation mark is simply an abbreviation for quote. So the interpreter will process Eva's expression as if it were:

(car (quote (quote abracadabra)))

The outer quote quotes the inner expression, and so produces the list:

'(quote abracadabra)

car then returns the first element from this - i.e. quote.

SICP Exercise 2.54: Equal Lists

Two lists are said to be equal? if they contain equal elements arranged in the same order. For example,

(equal? '(this is a list) '(this is a list))

is true, but

(equal? '(this is a list) '(this (is a) list))

is false. To be more precise, we can define equal? recursively in terms of the basic eq? equality of symbols by saying that a and b are equal? if they are both symbols and the symbols are eq?, or if they are both lists such that (car a) is equal? to (car b) and (cdr a) is equal? to (cdr b). Using this idea, implement equal? as a procedure.

The footnote in this exercise indicates that eq? may not be a reliable test of whether two numbers are equal. I.e. even if (= a b) evaluates to #t, you're not guaranteed that (eq? a b) will also evaluate to #t. Let's try to produce a solution that will not just cope with symbols correctly, but also numbers.

If we sneak a peak at the next sections in the book we're told about the predicates:

• number?, which identifies numbers ("The differentiation program with abstract data")
• symbol?, which identifies symbols ("Representing algebraic expressions")

If we extend the definition of equal? above so that it also includes the condition that if a and b are both numbers then a and b are equal? if the numbers are = then this should give us what we want.

We can then implement equal? as a cond expression, with a clause for each of the conditions we need to test for. Each clause's predicate needs to test that both a and b are of the same type and, if so, apply the appropriate logic to determine whether they're equal or not. We'll also need a final else clause that will catch all the cases where a and b are of different types - in these cases we know that a and b are not equal?, and so we can return #f.

Here's the procedure I produced:

(define (equal? a b)
  (cond ((and (pair? a) (pair? b))
           (and (equal? (car a) (car b)) (equal? (cdr a) (cdr b))))
        ((and (null? a) (null? b)) #t)
        ((and (number? a) (number? b)) (= a b))
        ((and (symbol? a) (symbol? b)) (eq? a b))
        (else #f)))

Let's give it a spin:

> (equal? '(this is a list) '(this is a list))
#t
> (equal? '(this is a list) '(this (is a) list))
#f
> (equal? (list 1 2 3 4) '(1 2 3 4))
#t
> (equal? (list 'a 'b 'c) '(a b c))
#t
> (equal? (list 1 2 'a 4) '(1 2 3 4))
#f