61A Homework 12

Due by 11:59pm on Thursday, 8/7

Readings: You might find the following references useful:

Submission: See the online submission instructions. We have provided the following starter file: hw12.scm

Table of Contents


The following problems develop a system for symbolic differentiation of algebraic expressions. The derive Scheme procedure takes an algebraic expression and a variable and returns the derivative of the expression with respect to the variable. Symbolic differentiation is of special historical significance in Lisp. It was one of the motivating examples behind the development of the language. Differentiating is a recursive process that applies different rules to different kinds of expressions:

; Derive returns the derivative of exp with respect to var.
(define (derive exp var)
  (cond ((number? exp) 0)
        ((variable? exp) (if (same-variable? exp var) 1 0))
        ((sum? exp) (derive-sum exp var))
        ((product? exp) (derive-product exp var))
        ((exponentiation? exp) (derive-exponentiation exp var))
        (else 'Error)))

To implement the system, we will use the following abstract data types. Sums and products are lists, and they are simplified on construction:

; Variables are represented as symbols
(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

; Numbers are compared with =
(define (=number? exp num)
  (and (number? exp) (= exp num)))

; Sums are represented as lists that start with +.
(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 (sum? x)
  (and (pair? x) (eq? (car x) '+)))
(define (addend s) (cadr s))
(define (augend s) (caddr s))

; Products are represented as lists that start with *.
(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 (product? x)
  (and (pair? x) (eq? (car x) '*)))
(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))

(define (test-sum)
  (assert-equal '(+ a x) (make-sum 'a 'x))
  (assert-equal '(+ a (+ x 1)) (make-sum 'a (make-sum 'x 1)))
  (assert-equal 'x (make-sum 'x 0))
  (assert-equal 'x (make-sum 0 'x))
  (assert-equal 4 (make-sum 1 3)))

(define (test-product)
  (assert-equal '(* a x) (make-product 'a 'x))
  (assert-equal 0 (make-product 'x 0))
  (assert-equal 'x (make-product 1 'x))
  (assert-equal 6 (make-product 2 3)))

Question 1

Implement derive-sum, a procedure that differentiates a sum by summing the derivatives of the addend and augend. Use the abstract data type for a sum:

(define (derive-sum exp var)


(define (test-derive-sum)
  (assert-equal 1 (derive '(+ x 3) 'x)))


Question 2

Implement derive-product, which applies the product rule to differentiate products:

(define (derive-product exp var)


(define (test-derive-product)
  (assert-equal 'y (derive '(* x y) 'x))
  (assert-equal '(+ (* x y) (* y (+ x 3)))
                (derive '(* (* x y) (+ x 3)) 'x)))


Question 3

Implement an abstract data type for exponentiation: a base raised to the power of an exponent. You can simplify the cases when exponent is 0 or 1, or when base is a number and exponent is an integer by returning numbers from the constructor make-exponentiation. (You can use the built-in function expt in your implementation!) In other cases, you can represent the exponentiation as a triple (^ base exponent):

; Exponentiations are represented as lists that start with ^.
(define (make-exponentiation base exponent)


(define (base exponentiation)


(define (exponent exponentiation)


(define (exponentiation? exp)


(define (test-exponentiation)
  (let ((x^2 (make-exponentiation 'x 2)))
    (assert-equal 'x (make-exponentiation 'x 1))
    (assert-equal 1  (make-exponentiation 'x 0))
    (assert-equal 16 (make-exponentiation 2 4))
    (assert-equal '(^ x 2) x^2)
    (assert-equal 'x (base x^2))
    (assert-equal 2  (exponent x^2))
    (assert-equal #t (exponentiation? x^2))
    (assert-equal #f (exponentiation? 1))
    (assert-equal #f (exponentiation? 'x))


Question 4

Implement derive-exponentiation, which uses the power rule to derive exponentiations:

(define (derive-exponentiation exp var)


(define (test-derive-exponentiation)
  (let ((x^2 (make-exponentiation 'x 2))
        (x^3 (make-exponentiation 'x 3)))
    (assert-equal '(* 2 x) (derive x^2 'x))
    (assert-equal '(* 3 (^ x 2)) (derive x^3 'x))
    (assert-equal '(+ (* 3 (^ x 2)) (* 2 x)) (derive (make-sum x^3 x^2) 'x))


Question 5

We want to implement the exp procedure. So, we write the following recursive procedure:
(define (exp-recursive b n)
  (if (= n 0)
      (* b (exp-recursive b (- n 1)))))

Try to evaluate

(exp-recursive 2 (exp-recursive 2 15))

You will notice that it causes a segmentation fault in STk, meaning that STk ran out of memory when trying to evaluate that value. To fix this, we need to use tail recursion! Implement the exp procedure using tail recursion:

(define (exp b n)
  ;; Computes b^n.
  ;; b is any number, n must be a non-negative integer.


(define (test-exp)
  (assert-equal 8 (exp 2 3))
  (assert-equal 1 (exp 9.137 0))
  (assert-equal 1024 (exp 4 5))
  (assert-equal 6.25 (exp 2.5 2))
  ;; A test that would break STk if this was not tail recursive.
  ;; The output is humongous, so we don't print out the entire output
  ;; Instead we just get the last two digits.
  (assert-equal 56 (remainder (exp 2 (exp 2 15)) 100)))


Optional Problems

Question 6

We now notice that we can write a faster version of exp that computes its answer much faster using the method of repeated squaring:

(define (square x) (* x x))

(define (fast-exp-recursive b n)
  (cond ((= n 0)
        ((even? n)
	 (square (fast-exp-recursive b (/ n 2))))
	 (* b (fast-exp-recursive b (- n 1))))))

The previous exp procedure took a linear number of recursive calls, because it always reduced n by 1. However, fast-exp halves the value of n every two recursive calls at most, and so it takes a logarithmic number of recursive calls. See SICP for more details.

However, this new procedure is not tail recursive, and as a result can use up a lot of memory. In particular, the following will crash STk after a few seconds of computation:

(fast-exp-recursive 1 (- (fast-exp-recursive 2 20000) 1))

Bonus question: Why did we subtract 1? In other words, why doesn't the following crash the interpreter?

(fast-exp-recursive 1 (fast-exp-recursive 2 20000))

Back to the original question - write fast-exp using tail recursion so that this no longer crashes. See SICP, Exercise 1.16, for a hint.

(define (fast-exp b n)
  ;; Computes b^n tail recursively by the method of repeated squaring.


(define (test-fast-exp)
  (assert-equal 8 (fast-exp 2 3))
  (assert-equal 1 (fast-exp 9.137 0))
  (assert-equal 1024 (fast-exp 4 5))
  (assert-equal 6.25 (fast-exp 2.5 2))
  ;; Takes about a second or so if implemented with a
  ;; logarithmic number of steps
  (assert-equal 36 (remainder (fast-exp 2 (fast-exp 2 20)) 100))
  ;; Takes about 10 seconds.  Will crash if not tail recursive.
  (assert-equal 1 (fast-exp 1 (- (fast-exp 2 20000) 1)))