*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

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

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

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

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

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

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

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