# 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

### Differentiation

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

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

(test-derive-sum)``````

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

(test-derive-product)``````

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

(test-exponentiation)``````

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

(test-derive-exponentiation)``````

### Question 5

We want to implement the `exp` procedure. So, we write the following recursive procedure:
``````(define (exp-recursive b n)
(if (= n 0)
1
(* 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)))

(test-exp)``````

## 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)
1)
((even? n)
(square (fast-exp-recursive b (/ n 2))))
(else
(* 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)))
)

(test-fast-exp)``````